文档介绍：算法与流程图
第章
图与网的定义和术语
目标
数据结构与算法
C程序的基本结构
用流程图描述算法
用C语言描述算法
图与网的定义和术语
2
引例: 首先分析学籍档案类问题。设一个班级有50个学生,这个班级的学籍表如表所示。
我们可以把表中每个学生的信息看成一个记录,表中的每个记录又由7个数据项组成。该学籍表由50个记录组成,记录之间是一种顺序关系。这种表通常称为线性表,数据之间的逻辑结构称为线性结构,其主要操作有检索、查找、插入或删除等。
学籍表
序号
学号
姓名
性别
英语
数学
物理
01
20030301
李明
男
86
91
80
02
20030302
马琳
男
76
83
85
50
20030350
刘薇薇
女
88
93
90
数据结构的基本概念和术语6-1
图与网的定义和术语
3
又如,对于学院的行政机构,可以把该学院的名称看成树根,把下设的若干个系看成它的树枝中间结点,把每个系分出的若干专业方向看成树叶,这样就形成一个树型结构,如下图所示。
树中的每个结点可以包含较多的信息,结点之间的关系不再是顺序的,而是分层、分叉的结构。树型结构的主要操作有遍历、查找、插入或删除等。
数据结构的基本概念和术语6-2
图专业设置
图与网的定义和术语
4
最后分析交通问题。如果把若干个城镇看成若干个顶点,再把城镇之间的道路看成边,它们可以构成一个网状的图,这种关系称为图型结构或网状结构。这是一个图论方面的问题。交通图的存储和管理确实不属于单纯的数值计算问题,而是一种非数值的信息处理问题。
数据结构的基本概念和术语6-3
图交通示意图
图与网的定义和术语
5
一般来说,数据结构研究的是一类普通数据的表示及其相关的运算操作。数据结构是一门主要研究怎样合理地组织数据,建立合适的数据结构,提高计算机执行程序所用的时间效率和空间效率的学科。
数据结构的基本概念和术语6-4
6
数据(Data)-----描述客观事物的数字、字符以及所有能够输入到计算机中并被计算机处理的信息的总称。
数据元素(Data Element)------是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。数据元素除了可以是一个数字或一个字符串以外,它也可以由一个或多个数据项组成。
数据项(Data Item)---是有独立含义的数据的最小单位,有时也称为字段(Field)。
数据结构的基本概念和术语6-5
图与网的定义和术语
7
数据对象(Data Object)---是具有相同性质的数据元素的集合,是数据的一个子集。例如,整数数据对象是集合N={0,±1, ±2,…},字母字符数据对象是集合C={'A', 'B', …, 'Z'}。本节的学籍表也可看成一个数据对象。
数据结构(Data Structure)---是带有结构的数据元素的集合,它是指数据元素之间的相互关系,即数据的组织形式、存储形式以及定义在它们之上的一组运算。不论是存储结构的设计,还是运算的算法设计,都必须考虑存储空间的开销和运行时间的效率。
数据结构的基本概念和术语6-6
图与网的定义和术语
8
在解决实际问题时,当确定了数据结构之后,需进一步研究与之相关的一组操作(也称运算),主要有插入、删除、排序、查找等。为了实现某种操作(如查找),常常需要设计一种算法。算法(Algorithm)是对特定问题求解步骤的一种描述,是指令的有限序列。描述算法需要一种语言,可以是自然语言、数学语言或者是某种计算机语言。
什么是算法
图与网的定义和术语
9
(1) 输入:一个算法应该有零个、一个或多个输入。
(2) 有穷性:一个算法必须在执行有穷步骤之后正常结束,而不能形成无穷循环。
(3) 确定性:算法中的每一条指令必须有确切的含义,不能产生多义性。
(4) 可行性:算法中的每一个指令必须是切实可执行的,即原则上可以通过已经实现的基本运算执行有限次来实现。
(5) 输出:一个算法应该至少有一个输出,这些输出是同输入有某种特定关系的量。
算法的特性
图与网的定义和术语
10