数据结构讲义第一章绪论

数据结构讲义第一章绪论一般来说，用计算机解决一个非数值问题时，大致需要经过以下几个步骤：首先要从分析实际问题入手，从中提取出所要处理的数据对象，并找出这些数据对象之间的关系；然后分析对这些数据对象所要进展的操作；最后设计算法、编出程序，进展测试、调整至得到最终解答。§

1.1数据结构的研究范畴22021/2/24001高等数学樊映川S01…002理论力学罗远祥L01…003高等数学华罗庚S01…004线性代数栾汝书S02………………樊映川001，…华罗庚003，…栾汝书004，………例1-1图书馆的书目检索系统自动化问题按登录号顺序排列的书目文件作者名索引表书名索引表分类号索引表高等数学001，003，…理论力学002，…线性代数004，………L002，…S001，003，………32021/2/24首先要从详细问题抽象出所要处理的数据对象；在这类文档管理的数学模型中，计算机处理的数据对象之间通常存在着一种最简单的线性关系，这类数学模型可称为线性的数据构造。然后分析对这些数据对象所要进展的操作；设计对图书、借阅者、借阅情况等数据进展生成、检索、修改等操作。最后设计算法、编出程序，测试、调整至得到最终解答。根据选定的数据构造和要进展的操作设计算法、编写程序，测试、修改，最终应用到图书馆的借阅管理理论中。例1-1图书馆的书目检索系统自动化问题42021/2/24例1-2计算机和人对弈问题。例1-2计算机和人的井字棋对弈问题井字棋由两人对弈。棋盘为3×3的方格，当一方的3个棋子占同一行、或同一列、或同一对角线时便为胜方。图中所示为对弈过程中井字棋的一个棋局，从当前棋盘格局可以派生出5个格局，而从每一个新的格局又可派生出4个可能出现的格局。以此类推分析可能出现的结果，从而选择最好的位置放置棋子。52021/2/24首先要从详细问题抽象出所要处理的数据对象；假设将从对弈开场到完毕的过程中所有可能出现的格局都画在一张图上，那么可得到一棵倒长的“树〞。“树根〞是对弈开场之前的棋盘格局，而所有的“叶子〞就是可能出现的结局，对弈的过程就是从树根沿树杈到某个叶子的过程。各棋盘数据间的关系表达为“树〞型数据构造。然后分析对这些数据对象所要进展的操作；对棋盘数据进展的根本操作：下棋、悔棋、判断输赢、计算得分等。最后设计算法、编出程序，测试、调整至得到最终解答根据选定的数据构造和要进展的操作设计算法、编写程序，测试、修改，最终应用到人机对弈理论中。例1-2计算机和人的井字棋对弈问题62021/2/24假设要在n个城市间建立通讯网，连通n个城市只需要n-1条线路。每架设一条线路，相应的要付出一定的费用。如何在最节省经费的条件下建立这个连通网？用一个连通网〔各边带有权值的连通图〕来表示n个城市间的通讯网，网中的顶点代表各个城市，边代表城市间的通讯线路，各边的权值表示铺设该条线路需要的费用。afgcdeb191818208153920715例1-3建立n个城市之间的通讯网问题72021/2/24首先要从详细问题抽象出所要处理的数据对象；连通网中的数据对象是各个城市，这些数据对象之间有着多对多的复杂的联络，这组数据对象以及它们之间的复杂关系表达的就是一种“图〞型数据构造。然后分析对这些数据对象所要进展的操作；对城市通讯网数据对象的操作：增加、删除、布网、修改等最后设计算法、编出程序，测试、调整至得到最终解答根据选定的数据构造和要进展的操作设计算法、编写程序，测试、修改，最终应用到通讯网的布网理论中。例1-2计算机和人的井字棋对弈问题82021/2/24杂乱的数据不能表达和交流信息；数据之间是有联络的；数据之间是有构造的；在某种数据构造上可定义一组操作。§

1.1数据结构的研究范畴综上所述，我们可以发现我们用计算机所处理的数据信息具有以下特点：数据构造研究的是从分析实际问题入手，从中提取出所要处理的数据对象，并找出这些数据对象之间的关系，以及对这些数据对象的操作等的学科。92021/2/24数据的各种逻辑构造和存储构造，以及它们之间的相应关系。并对每种构造定义相适应的各种操作。设计出相应的算法。分析算法的效率。§

1.1数据结构的研究范畴102021/2/24数据〔Data〕数据元素〔DataElement〕数据对象〔DataObject〕数据构造〔DataStructure〕逻辑构造〔LogicalStructure〕存储构造〔PhysicalStructure〕§

1.2数据结构的基本概念112021/2/24数据：描绘客观事物的数字、字符以及一切可以输入到计算机中，并且可以被计算机程序处理的符号的集合。

数据是一个广义的概念，可以指普通的数据〔可参加算术运算〕，也可以指符号〔源程序、产品名称等〕或数字化了的声音、图形、图像等。§

1.2数据结构的基本概念122021/2/24..................北京1983.11河北女赵虹玲101住址出生年月籍贯性别姓名学号数据元素数据项数据元素：数据(集合)中的一个个"个体"，是组成数据的"根本单位"。数据项：构成数据元素的不可分割的数据单位。§

1.2数据结构的基本概念132021/2/24数据对象：性质一样的数据元素的集合，是数据的一个子集。例如：整数集合：N={0，±1，±2，…}

无限集字符集合：C={'A'，'B'，…，'Z'}

有限集§

1.2数据结构的基本概念142021/2/24……129ABZ…………数据数据对象2数据对象1数据元素1数据元素2数据元素1数据元素2数字N字符C数据集合D

={…0,1,…,9,…,A,B,…,Z，…

}数字集合N={0,1,…,9}字母集合C={A,B,…,Z}数据、数据元素、数据对象的关系152021/2/24注：数据构造用来指内存中的数据组织，外存中的数据组织通常称为文件构造。数据构造：(DataStructure)数据构造是带“构造〞的数据元素的集合。“构造〞即指数据元素之间存在的联络。所以数据构造又可以定义为有联络的数据元素的集合。§

1.2数据结构的基本概念162021/2/24四类根本的构造：集合构造线性构造:一对一树状构造：一对多图状构造：多对多§

1.2数据结构的基本概念逻辑构造：(LogicalStructure)数据的逻辑构造是指数据元素之间逻辑关系。172021/2/24综上所述，数据的逻辑构造可概括为：线性构造逻辑构造非线性构造线性表栈队列字符串数组广义表树图§

1.2数据结构的基本概念182021/2/24§

1.2数据结构的基本概念存储构造：(PhysicalStructure)又称物理构造，是数据的逻辑构造在计算机中的表示与实现，它包括数据元素在计算机中的表示以及数据元素之间的关系在计算机中的表示和实现。192021/2/24数据元素的表示：在计算机中，用一个有假设干二进制位组合起来形成的一个位串表示一个数据元素。数据元素之间关系的表示：1、顺序映象〔顺序存储构造〕：以存储位置表示前后关系，整个存储构造中只含数据元素本身的信息。2、非顺序映象〔非顺序——链式存储构造〕：以附加信息(指针)表示前后关系。§

1.2数据结构的基本概念存储构造的实现：202021/2/24逻辑构造…d1d2d3d4…d30a2a1a3a4a30存储构造1.顺序映象〔顺序存储构造〕线性构造〔线性表〕a1a2a3a30刘晓光马广生王民…张玉华男男…女男汉回壮…汉161721…25

姓名性别民族年龄Example212021/2/242、非顺序映象〔非顺序——链式存储构造〕a1a2a3a30∧list……d1d2d3d4

a2a1a4a3d4d1d5d3存储构造Example222021/2/24

抽象数据类型(AbstractDataType)用C语言实现抽象数据类型ADTADT的表示与实现§

1.3

抽象数据类型232021/2/24数学模型抽象数据模型数据结构非形式算法伪语言程序可执行程序用抽象数据类型的概念来指导问题的求解过程：注：一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。§

1.3

抽象数据类型抽象数据类型：(简称ADT)是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。242021/2/24ADT的定义格式

ADT<ADT名>{数据对象:<数据对象的定义>构造关系:<构造关系的定义>根本操作:<根本操作的定义>}ADT<ADT名>根本操作的定义格式为：<操作名称>(参数表)操作前提:<操作前提描绘>操作结果:<操作结果描绘>§

1.3

抽象数据类型252021/2/24数据元素：所有ai属于同一数据对象，i=1，2，……，nn≥0；逻辑构造：所有数据元素ai〔i=1，2，…，n-1〕存在一定逻辑关系；操作 Initial()初始化数据构造；Destroy()销毁数据构造； Get(i)查找第i个元素； Insert(i,b)在第i个位置插入元素b； Delete(i)删除第i个元素；Traverse()遍历整个数据构造抽象数据类型的根本描绘§

1.3

抽象数据类型262021/2/24用标准C语言表示和实现ADT描绘时，主要有两个方面：二、用C语言函数实现各操作。一、通过构造体将int、float等固有类型组合到一起，构成一个构造类型，再用typedef为该类型或该类型指针重新起一个名字。用C语言实现抽象数据类型ADT§

1.3

抽象数据类型272021/2/24算法〔Algorithm〕定义算法设计的要求算法的特性算法的描绘方法§

1.4

算法及其描述282021/2/24算法：Algorithmisafinitesetofruleswhich

givesasequenceofoperationforsolvingaspecifictype

ofproblem. 算法是指令的有限序列，是为解决特定问题而规定的一系列操作。§

1.4

算法及其描述292021/2/24算法的特性1.有限性：有限步骤之内正常完毕，不能形成无穷循环。2.确定性：算法中的每一个步骤必须有确定含义，无二义性。3.可行性：算法中的每一步都是可行的。算法翻译成程序语言以后可以在计算机上准确执行，而且可以完成指定的功能。§

1.4

算法及其描述302021/2/24主要区别：1、程序可以是无穷的，算法必须是有穷的。2、程序可以是错误的，算法必须是正确的。3、程序是用程序设计语言描绘，在机器上可以执行。算法可以用框图和自然语言等方式描绘。算法与程序的区别§

1.4

算法及其描述程序：用某种程序设计语言对算法的详细实现312021/2/24算法设计的要求§

1.4

算法及其描述1.正确性〔四个层次〕a.程序没有语法错误；b.程序对于几组输入数据可以得出满足要求的结果；c.程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据可以的除满足要求的结果；d.程序对于一切合法的数据数据都可以产生满足要求的结果。2.可读性：3.强健性：4.高效率和低存储量：322021/2/24例：求n个数的最大值问题max=0;for〔i=1；i<=n;i++〕{scanf("%f",x);if(x>max)max=x;}scanf("%f",x);max=x;for〔i=2；i<=n;i++〕{scanf("%f",x);if(x>max)max=x;}332021/2/24§

1.5

算法的度量评价算法的标准：

算法所占用机器资源的多少

1.时间复杂度：

算法执行所需的机器时间。2.空间复杂度：

算法执行所占用的存储空间。342021/2/24§

1.5

算法的度量事后统计法：把算法变为程序，然后在机器上执行，并计时。1.算法在计算机上不止执行一次，必须屡次执行，然后对结果进展统计分析。2.机器的速度、编译程序的质量等等外在的因素，会影响算法的执行时间。事前分析估计法：在编写算法过程中就要对算法的效率进展分析估算算法的度量方法352021/2/24一个算法的运行时间：是指在计算机上从开场到完毕运行所花费的时间，它大致等于计算机执行一种简单操作(如赋值、比较、计算、转向、返回、输入、输出等)所需的时间与算法中进展简单操作次数的乘积。因为执行一种简单操作所需的时间随机器而异，它是由机器本身硬软件环境决定的，与算法无关，所以我们只讨论影响运行时间的另一个因素——算法中进展简单操作的次数。§

1.5

算法的度量算法的运行时间362021/2/24

语句频度：是指语句被重复执行的次数。“语句〞：指描绘算法的根本语句，它的执行是不可再分割的。一个算法所消耗的时间=算法中每条语句的执行时间之和每条语句的执行时间=语句被重复执行的次数×语句执行一次所需时间§

1.5

算法的度量算法消耗的时间和语句频度372021/2/24矩阵相乘：求各语句频度inti,j,k;for(i=0;i<n;i++)for(j=0;j<n;j++){ c[i][j]=0;

for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];}解:该算法中所有语句的频度之和即算法的时间消耗，我们用T(n)来表示，为：T(n)=2n3+3n2+2n+1Example根本语句1根本语句2n+1

n2(n+1)

n(n+1)

n2

n3

382021/2/24§

1.5

算法的度量算法执行时间的相关因素

问题规模

编写程序的语言编译程序产生的机器代码的质量

计算机执行指令的速度392021/2/24问题规模n

——对不同的问题其含义不同：矩阵阶数多项式运算图集合运算多项式项数顶点个数集合中元素个数§

1.5

算法的度量算法的度量——问题规模402021/2/24§

1.5

算法的度量问题规模与语句频度问题规模与语句频度的关系：语句的频度使用问题规模来表示的，语句频度要表示成问题规模的函数。算法耗时、问题规模、语句频度的关系：算法的消耗时间由算法中所有语句的频度之和来表示，而语句频度是问题规模的函数。412021/2/24时间复杂度：当问题规模n趋近于无穷时，算法消耗时间的增长率(数量级)，表示为问题规模n的函数：T(n)=O(f(n))T(n)=O(f(n))的数学定义:在数学里，假如T(n)=O(f(n))，那么当且仅当

〔c为非零常数〕时间复杂度§

1.5

算法的度量时间复杂度和大O表示法422021/2/24数据构造中常用的时间复杂度数量级有7个，按照数量级递增排序有:O(1)常数型O(log2n)对数型f(n)=log2nO(n)线性型f(n)=nO(n2)平方型f(n)=n2O(n3)立方型f(n)=n3O(2n)指数型f(n)=2n随着n的增大，T(n)增长速度较慢的算法为优，即T(n)的数量级O(f(n))较小的算法效率较高。

432021/2/241.确定所解决问题的问题规模n；2.找出算法中的所有根本语句；3.计算出所有根本语句的语句频度，并把他们相加得出T(n);4.求出T(n)的数量级f(n)，那么T(n)=O(f(n))即为算法的时间复杂度§

1.5

算法的度量算法的时间复杂度的估算步骤442021/2/24循环语句的整体、函数调用语句不能算作根本语句，因为它们还包括循环体或函数体。在一个算法中，有些语句可能很少被执行，且与程序的问题规模无关，在估算时间复杂度是，可以不考虑他们。一般只考虑与程序的问题规模有关的语句的语句频度。在实际计算语句频度时，可以不考虑循环语句和条件语句本身，而只考虑他们所包含的循环体和条件体。§

1.5

算法的度量算法的时间复杂度的估算452021/2/24求时间复杂度：交换i和j的内容

Temp=i;i=j;j=temp;Example以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。假如算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。462021/2/24求时间复杂度：(1)x=0;y=0;(2)for(k-1;k<=n;k++)(3)x++;(4)for(i=1;i<=n;i++)(5)for(j=1;j<=n;j++)(6)y++;Example在多数情况下，只要选出算法中含在嵌套层数最多的，即最内层的循环体中的根本语句，该根本语句的执行次数(语句频度)就可作为算法的时间度量。472021/2/24主要任务：分析算法在实现时所需要的辅助空间单元个数。用空间复杂度作为算法所需存储空间的量度，记做：

S(n)=O(f(n)

)

存储空间寄存本身所用的指令、常数、变量和输入数据（取决于问题本身，与算法无关）对数据进行操作的辅助存储空间（与算法有关）§

1.5

算法的度量算法的空间复杂度482021/2/24数据构造与其它课程关系图：数据结构数据库人工智能专业基础课操作系统编译原理非线性程序设计离散数学语言程序设计计算机原理设计§

1.5

算法的度量492021/2/24〔1〕A=〔K，R〕，其中：K={a，b，c，d，e，f，g}R={r}r={〈a,b〉,〈b,c〉,〈c,d〉,〈d,e〉,〈e,f〉,〈f,g〉}〔2〕B=〔K，R〕，其中：K={a，b，c，d，e，f，g，h}R={r}r={〈d,b〉,〈d,g〉,〈d,a〉,〈b,c〉,〈g,e〉,〈g,h〉,〈a,f〉}〔3〕C=〔K，R〕，其中：K={1，2，3，4，5，6}R={r}r={〔1,2〕,〔2,3〕,〔2,4〕,〔3,4〕,〔3,5〕,〔3,6〕,〔4,5〕,〔4,6〕}这里的圆括号对表示两结点是双向的。

练

习1、有以下几种用二元组表示的数据构造，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种构造。502021/2/24A对应逻辑图形如下，它是一种线性构造。

练

习〔1〕A=〔K，R〕，其中：K={a，b，c，d，e，f，g}R={r}r={〈a,b〉,〈b,c〉,〈c,d〉,〈d,e〉,〈e,f〉,〈f,g〉}1、有以下几种用二元组表示的数据构造，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种构造。512021/2/24B对应逻辑图形如下，它是一种树形构造。

练

习1、有以下几种用二元组表示的数据构造，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种构造。〔2〕B=〔K，R〕，其中：K={a，b，c，d，e，f，g，h}R={r}r={〈d,b〉,〈d,g〉,〈d,a〉,〈b,c〉,〈g,e〉,〈g,h〉,〈a,f〉}522021/2/24C对应逻辑图形如下，它是一种图形构造。

练

习1、有以下几种用二元组表示的数据构造，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种构造。〔3〕C=〔K，R〕，其中：K={1，2，3，4，5，6}R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}532021/2/24

voidSelectSort(intb[],intn){ inti,j,k,x; for(i=0;i