1、数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构数据结构期末复习(1)数据结构（数据结构（C版）版）清华大学出版社清华大学出版社第第 1 章章 绪绪 论论数据结构的兴起和发展数据结构的兴起和发展数据结构的研究对象数据结构的研究对象 数据结构的基本概念数据结构的基本概念算法及算法分析算法及算法分析本章的基本内容是：本章的基本内容是：数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.1 数据结构的兴起和发展数据结构的兴起和发展 程序设计的实质是什么程序设计的实质是什么?数据表示：数据表示：将数据存储在计算机中将数据存储在计算机中数据处理：数据处理：处理数据，求解问题处
2、理数据，求解问题数据结构问题起源于程序设计数据结构问题起源于程序设计 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 数据结构随着程序设计的发展而发展数据结构随着程序设计的发展而发展 数据结构的发展并未终结数据结构的发展并未终结1.无结构阶段无结构阶段2.结构化阶段：数据结构算法程序结构化阶段：数据结构算法程序3.面向对象阶段：面向对象阶段：（数据结构算法）程序（数据结构算法）程序1.1 数据结构的兴起和发展数据结构的兴起和发展 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.2 数据结构的研究对象数据结构的研究对象 计算机求解问题计算机求解问题:问题问题抽象出问题的
3、模型抽象出问题的模型求模型的解求模型的解 问题问题数值问题、非数值问题数值问题、非数值问题 数数 值值 问问 题题数学方程数学方程 非数值问题非数值问题数据结构数据结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构数据结构：相互之间存在一定：相互之间存在一定关系关系的数据元素的集合。的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。存储结构：又称为物理结构，是数据及其逻辑结构在存储结构：又称为物理结构，是数据及其逻辑结构在计算机计算
4、机中的表示。中的表示。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念存储结构实质上是内存分配，存储结构实质上是内存分配，在具体实现时，依赖于计算机语言。在具体实现时，依赖于计算机语言。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构从逻辑上分为四类：数据结构从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念集合太松散，课内几乎不讨论。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构从逻辑上分为四类：
5、数据结构从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构从逻辑上分为四类：数据结构从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；树结构：数据元素之间存在树结构：数据
6、元素之间存在 着一对多的层次关系；着一对多的层次关系；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构从逻辑上分为四类：数据结构从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；树结构：数据元素之间存在树结构：数据元素之间存在 着一对多的层次关系；着一对多的层次关系；图结构：数据元素之间存在图结构：数据元素之间存在 着多对多的任意关系。着多对多的任意关系。1
7、.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社通常有两种存储结构：通常有两种存储结构：1.顺序存储结构：用一组顺序存储结构：用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元数据元素之间的逻辑关系由元素的素的存储位置存储位置来表示。来表示。batcateat起始地址起始地址例：（例：（bat,cat,eat）1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社通常有两种存储结
8、构：通常有两种存储结构：1.顺序存储结构：用一组顺序存储结构：用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元数据元素之间的逻辑关系由元素的素的存储位置存储位置来表示。来表示。2.链接存储结构：用一组链接存储结构：用一组任意任意的存储单元存储数据元素，数的存储单元存储数据元素，数据元素之间的逻辑关系用据元素之间的逻辑关系用指针指针来表示来表示。例：（例：（bat,cat,eat）1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念0200020803000325 bat0200 cat0325 eat 数据结构（数据结
9、构（C版）版）清华大学出版社清华大学出版社逻辑结构和存储结构之间的关系逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，是数据的逻辑结构属于用户视图，是面向问题面向问题的，的，反映了数据内部的构成方式；数据的存储结构反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是属于具体实现的视图，是面向计算机面向计算机的。的。一种数据的逻辑结构可以用多种存储结构来存一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效储，而采用不同的存储结构，其数据处理的效率往往是不同的。率往往是不同的。1.3 数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版
10、）清华大学出版社清华大学出版社1.3 1.3 数据结构的基本概念（小结）数据结构的基本概念（小结）数据的操作：插入、删除、修改、检索、排序等数据的操作：插入、删除、修改、检索、排序等 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 顺序存储顺序存储链式存储链式存储集合集合线性结构线性结构树结构树结构图结构图结构 非数值问题非数值问题 数数据据表表示示数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 欧几里德算法mnr例：欧几里德算法例：欧几里德算法辗转相除法辗转相除法求两个自然数求两个自然数 m 和和 n 的最大公约数的最大公约数数据结构（数据结构（C版）版）清华大学出版
11、社清华大学出版社算法的描述方法算法的描述方法自然语言自然语言 优点：容易理解优点：容易理解缺点：冗长、二义性缺点：冗长、二义性使用方法：粗线条描述算法思想使用方法：粗线条描述算法思想 注意事项：避免写成自然段注意事项：避免写成自然段数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 输入输入m 和和n；求求m除以除以n的余数的余数r；若若r等于等于0 0，则，则n为最大公约数，为最大公约数，算法结束；否则执行第步；算法结束；否则执行第步；将将n的值放在的值放在m中，将中，将r的值放的值放在在n中；中；重新执行第步。重新执行第步。例：欧几里德算法例：欧几里德算法自然语言数据结构（数据结构
12、（C版）版）清华大学出版社清华大学出版社优点：流程直观优点：流程直观 缺点：缺少严密性、灵活性缺点：缺少严密性、灵活性使用方法：描述简单算法使用方法：描述简单算法注意事项：注意抽象层次注意事项：注意抽象层次算法的描述方法算法的描述方法流程图流程图 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社N开始输入m和n r=m%nr=0m=n；n=r 输出n结束Y流 程 图例：欧几里德算法例：欧几里德算法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社优点：能由计算机执行优点：能由计算机执行 缺点：抽象性差，对语言要求高缺点：抽象性差，对语言要求高使用方法：算法需要验证使用方法：算
13、法需要验证注意事项：将算法写成子函数注意事项：将算法写成子函数算法的描述方法算法的描述方法程序设计语言程序设计语言 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社#include int CommonFactor(int m,int n)int r=m%n;while(r!=0)m=n;n=r;r=m%n;return n;void main()coutCommonFactor(63,54)endl;程序设计语言例：欧几里德算法例：欧几里德算法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社伪代码伪代码（Pseudocode）：介于自然语言和）：介于自然语言和程序设计语言
14、之间的方法，它采用某一程序程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自设计语言的基本语法，操作指令可以结合自然语言来设计。然语言来设计。优点：表达能力强，抽象性强，容易理解优点：表达能力强，抽象性强，容易理解使用方法：使用方法：7 2算法的描述方法算法的描述方法伪代码伪代码 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 1.r=m%n;2.循环直到循环直到 r 等于等于0 2.1 m=n;2.2 n=r;2.3 r=m%n;3.输出输出 n;伪 代 码上述伪代码再具体一些，用上述伪代码再具体一些，用C+的函数来的函数来描述。请同学们自行完成！描述。
15、请同学们自行完成！例：欧几里德算法例：欧几里德算法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社算法分析算法分析（Algorithm Analysis）：对算法所需要的）：对算法所需要的计算机资源计算机资源时间时间和和空间空间进行估算。进行估算。时间复杂性（时间复杂性（Time Complexity）空间复杂性（空间复杂性（Space Complexity）数据结构（数据结构（C版）版）清华大学出版社清华大学出版社算法的时间复杂度分析算法的时间复杂度分析算法的算法的执行时间执行时间每条语句执行时间之和每条语句执行时间之和执行次数执行次数执行一次的时间执行一次的时间指令系统、编译的代
16、码质量指令系统、编译的代码质量单位时间单位时间每条语句每条语句执行次数执行次数之和之和for(i=1;i=n;i+)for(j=1;j=n;j+)x+;基本语句基本语句的执行次数的执行次数数据结构（数据结构（C版）版）清华大学出版社清华大学出版社问题规模：问题规模：输入量的多少。输入量的多少。基本语句：基本语句：是执行次数与整个算法的执行次是执行次数与整个算法的执行次数成数成正比的操作指令。正比的操作指令。for(i=1;i=n;i+)for(j=1;j=n;j+)x+;问题规模：n基本语句：x+数据结构（数据结构（C版）版）清华大学出版社清华大学出版社定义定义 若存在两个正的常数若存在两个正
17、的常数c和和n0，对于任意，对于任意nn0，都有都有T(n)cf(n)，则称，则称T(n)=O(f(n)n0问题规模问题规模n执执行行次次数数n0之前的之前的情况无关情况无关紧要紧要T(n)cf(n)v当问题规模充分大时在渐近意义下的阶当问题规模充分大时在渐近意义下的阶大大O符号符号数据结构（数据结构（C版）版）清华大学出版社清华大学出版社定理：若定理：若A(n)=amnm+am-1nm-1+a1n+a0是一个是一个m次多项式，则次多项式，则A(n)=O(nm)。说明：在计算算法时间复杂度时，可以说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。忽略所有低次幂和最高次幂的系数。
18、大大O符号符号数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例例1-5 +x;例例1-6 for(i=1;i=n;+i)+x;例例1-7 for(i=1;i=n;+i)for(j=1;j=n;+j)+x;例例1-8 for(i=1;i=n;+i)for(j=1;j=i-1;+j)+x;数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例例1-9 for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;例例1-10 for(i=1;i=n;i=2*i)+x;(1)(log2n)(n)(nlog2n)(n2
19、)(n3)(2n)(n!)数据结构（数据结构（C版）版）清华大学出版社清华大学出版社最好情况、最坏情况、平均情况最好情况、最坏情况、平均情况例：在一维整型数组例：在一维整型数组A n 中顺序查找与给定值中顺序查找与给定值k相等相等的元素（假设该数组中有且仅有一个元素值为的元素（假设该数组中有且仅有一个元素值为k）。int Find(int A,int n)for(i=0;i=MaxSize合理的插入位置：合理的插入位置：1ilength+1（i指的是元素的序号）指的是元素的序号）2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入 435122442a1
20、a2a3a40 1 2 3 4422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.如果表满了，则抛出如果表满了，则抛出上溢上溢异常异常;2.如果元素的插入位置不合理，则抛出如果元素的插入位置不合理，则抛出位置位置异常异常;3.将最后一个元素至第将最后一个元素至第i个元素分别向后移动一个位置；个元素分别向后移动一个位置；4.将元素将元素x填入位置填入位置i处；处；5.表长加表长加1；算法描述算法描述伪代码伪代码2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入数据结构（
21、数据结构（C版）版）清华大学出版社清华大学出版社template void SeqList:Insert(int i,T x)if(length=MaxSize)throw 上溢上溢;if(ilength+1)throw 位置位置;for(j=length;j=i;j-)-)dataj=dataj-1;datai-1=x;length+;算法描述算法描述C+描述描述2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入基本语句基本语句？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社操作接口：操作接口：T Delete(int i)删除前：删除前
22、：(a1,ai-1,ai,ai+1,an)删除后：删除后：(a1,ai-1,ai+1,an)顺序表的实现顺序表的实现删删 除除2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例：（例：（35,33,12,24,42），），删除删除i=2的数据元素。的数据元素。仿照顺序表的插入操作，完成：仿照顺序表的插入操作，完成：1.分析边界条件；分析边界条件；2.分别给
23、出伪代码和分别给出伪代码和C+描述的算法；描述的算法；3.分析时间复杂度。分析时间复杂度。2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现删删 除除 535a1a2a3a40 1 2 3 4422412334a5122442数据结构（数据结构（C版）版）清华大学出版社清华大学出版社顺序表的实现顺序表的实现按位查找按位查找操作接口：操作接口：T Get(int i)2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 n算法描述：算法描述：template T SeqList
24、:Get(int i)if(i=1&i=length)return i-1;时间复杂度时间复杂度？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社顺序表的优缺点顺序表的优缺点 顺序表的优点：顺序表的优点：无需为表示表中元素之间的逻辑关系而增加额外的无需为表示表中元素之间的逻辑关系而增加额外的存储空间；存储空间；随机存取：可以快速地存取表中任一位置的元素。随机存取：可以快速地存取表中任一位置的元素。顺序表的缺点：顺序表的缺点：插入和删除操作需要移动大量元素；插入和删除操作需要移动大量元素；表的容量难以确定，表的容量难以扩充；表的容量难以确定，表的容量难以扩充；造成存储空间的造成存储空间
25、的碎片碎片。2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社单链表的实现单链表的实现按位查找按位查找操作接口：操作接口：T Get(int i);v核心操作（关键操作）：核心操作（关键操作）：工作指针后移工作指针后移。从头结点。从头结点（或开始结点）出发，通过工作指针的反复后移而将（或开始结点）出发，通过工作指针的反复后移而将整个单链表整个单链表“审视审视”一遍的方法称为一遍的方法称为扫描扫描（或遍历）（或遍历）。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现firsta1pa2panaipp查找成功查找成功p
26、查找失败查找失败数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.工作指针工作指针p初始化初始化;累加器累加器j初始化初始化;2.1 工作指针工作指针p后移后移;2.2 累加器累加器j加加1;2.循环直到循环直到p为空或为空或p指向第指向第i个结点个结点3.若若p为空，则第为空，则第i个元素不存在，抛出查找位置个元素不存在，抛出查找位置异常；否则查找成功，返回结点异常；否则查找成功，返回结点p的数据元素；的数据元素；2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现按位查找按位查找算法描述算法描述伪代码伪代码数据结构（数据结构（C版）版）清华大学出
27、版社清华大学出版社template T LinkList:Get(int i)p=first-next;j=1;while(p&jnext;j+;if(!p)throw 位置位置;else return p-data;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现按位查找按位查找算法描述算法描述C+描述描述p+能否完成指针后移？能否完成指针后移？a1a2ppp数据结构（数据结构（C版）版）清华大学出版社清华大学出版社单链表的实现单链表的实现插入插入操作接口：操作接口：void Insert(int i,T x);2.3 线性表的链接存储结构及实现线性表的链
28、接存储结构及实现如何实现结点如何实现结点ai-1、x和和ai之间逻辑关系的变化？之间逻辑关系的变化？pxsfirsta1ai-1anai算法描述：算法描述：s=new Node;s-data=x;s-next=p-next;p-next=s;数据结构（数据结构（C版）版）清华大学出版社清华大学出版社注意分析注意分析边界边界情况情况表头、表尾。表头、表尾。单链表的实现单链表的实现插入插入2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现firsta1anaipxs算法描述：算法描述：s=new Node;s-data=x;s-next=p-next;p-next=s;pxs由于单链表带
29、头结点，由于单链表带头结点，表头、表中、表尾三种表头、表中、表尾三种情况的操作语句一致。情况的操作语句一致。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社算法描述算法描述伪代码伪代码 1.工作指针工作指针p初始化；累加器初始化；累加器j清零；清零；2.查找第查找第i-1个结点并使工作指针个结点并使工作指针p指向该结点；指向该结点；3.若查找不成功，说明插入位置不合理，抛出插入若查找不成功，说明插入位置不合理，抛出插入位置异常；否则，位置异常；否则，3.1 生成一个元素值为生成一个元素值为x的新结点的新结点s；3.2 将新结点将新结点s插入到结点插入到结点p之后；之后；2.3 线性表
30、的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现插入插入数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 template void LinkList:Insert(int i,T x)p=first;j=0;while(p&j-next;j+;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现算法描述算法描述C+描述描述单链表的实现单链表的实现插入插入 if(!p)throw 位置位置;else s=new Node;s-data=x;s-next=p-next;p-next=s;，基本语句？时间复杂度？基本语句？时间复杂度？数据结构（数据结构（C版
31、）版）清华大学出版社清华大学出版社单链表的实现单链表的实现删除删除操作接口：操作接口：T Delete(int i);2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现p如何实现结点如何实现结点ai-1和和ai之间逻辑关系的变化？之间逻辑关系的变化？firsta1ai-1ai+1ai算法描述：算法描述：q=p-next;x=q-data;p-next=q-next;delete q;q数据结构（数据结构（C版）版）清华大学出版社清华大学出版社单链表的实现单链表的实现删除删除2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现算法描述：算法描述：q=p-next;x=q-dat
32、a;p-next=q-next;delete q;注意分析注意分析边界边界情况情况表头、表尾。表头、表尾。pqpq表尾的特殊情况：表尾的特殊情况：虽然被删结点不存在，虽然被删结点不存在，但其前驱结点却存在。但其前驱结点却存在。p-next=NULLfirsta1ana2数据结构（数据结构（C版）版）清华大学出版社清华大学出版社算法描述算法描述伪代码伪代码 1.工作指针工作指针p初始化；累加器初始化；累加器j清零；清零；2.查找第查找第i-1个结点并使工作指针个结点并使工作指针p指向该结点；指向该结点；3.若若p不存在或不存在或p不存在后继结点，则抛出位置异常；不存在后继结点，则抛出位置异常；否
33、则，否则，3.1 暂存被删结点和被删元素值；暂存被删结点和被删元素值；3.2 摘链，将结点摘链，将结点p的后继结点从链表上摘下；的后继结点从链表上摘下；3.3 释放被删结点；释放被删结点；3.4 返回被删元素值；返回被删元素值；2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现删除删除数据结构（数据结构（C版）版）清华大学出版社清华大学出版社template T LinkList:Delete(int i)p=first;j=0;while(p&jnext;j+;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现算法描述算法描述C+描述描述单链表的实
34、现单链表的实现删除删除 if(!p|!p-next)throw“位置位置”;else q=p-next;x=q-data;p-next=q-next;delete q;return x;数据结构（数据结构（C版）版）清华大学出版社清华大学出版社存储分配方式比较存储分配方式比较顺序表采用顺序存储结构，即用一段地址顺序表采用顺序存储结构，即用一段地址连续连续的的存储单元存储单元依次依次存储线性表的数据元素，数据元素之存储线性表的数据元素，数据元素之间的逻辑关系通过间的逻辑关系通过存储位置存储位置来实现。来实现。单链表采用链接存储结构，即用一组单链表采用链接存储结构，即用一组任意任意的存储的存储单元
35、存放线性表的元素。用单元存放线性表的元素。用指针指针来反映数据元素之来反映数据元素之间的逻辑关系。间的逻辑关系。2.4 顺序表和单链表的比较顺序表和单链表的比较数据结构（数据结构（C版）版）清华大学出版社清华大学出版社2.4 顺序表和单链表的比较顺序表和单链表的比较时间性能比较时间性能比较 时间性能时间性能是指实现基于某种存储结构的基本操作（即是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。算法）的时间复杂度。按位查找：按位查找：顺序表的时间为顺序表的时间为(1)，是随机存取；，是随机存取；单链表的时间为单链表的时间为(n)，是顺序存取。，是顺序存取。插入和删除：插入和删除：顺序表需
36、移动表长一半的元素，时间为顺序表需移动表长一半的元素，时间为(n)；单链表不需要移动元素，在给出某个合适位置的指单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为针后，插入和删除操作所需的时间仅为(1)。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社2.4 顺序表和单链表的比较顺序表和单链表的比较空间性能比较空间性能比较 结点的存储密度：结点的存储密度：顺序表中每个结点的存储密度为顺序表中每个结点的存储密度为1（只存储数据元（只存储数据元素），没有浪费空间；素），没有浪费空间；单链表的每个结点的存储密度单链表的每个结点的存储密度next=NULL;rea
37、r-next=s;rear=s;如何没有头结点会怎样？如何没有头结点会怎样？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 xs特殊线性表特殊线性表队列队列链队列的实现链队列的实现入队入队操作接口：操作接口：void EnQueue(T x);fronta2anrearrear算法描述：算法描述：s-next=NULL;rear-next=s;rear=s;如何没有头结点会怎样？如何没有头结点会怎样？a1数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 xs特殊线性表特殊线性表队列队列链队列的实现链队列的实现入队入队操作接口：操作接口：void EnQueue(T x);
38、fronta2anrearrearfront=rear=NULL xsrear算法描述：算法描述：s-next=NULL;rear=s;front=s;如何没有头结点会怎样？如何没有头结点会怎样？a1front数据结构（数据结构（C版）版）清华大学出版社清华大学出版社特殊线性表特殊线性表队列队列链队列的实现链队列的实现入队入队template void LinkQueue:EnQueue(T x)s=new Node;s-data=x;s-next=NULL;rear-next=s;rear=s;数据结构（数据结构（C版）版）清华大学出版社清华大学出版社特殊线性表特殊线性表队列队列链队列的实现
39、链队列的实现出队出队fronta1a2anrearp算法描述：算法描述：p=front-next;front-next=p-next;数据结构（数据结构（C版）版）清华大学出版社清华大学出版社特殊线性表特殊线性表队列队列链队列的实现链队列的实现出队出队fronta1a2anrearp考虑边界情况：队列中只有一个元素？考虑边界情况：队列中只有一个元素？fronta1prearrear算法描述：算法描述：if(p-next=NULL)rear=front;如何判断边界情况？如何判断边界情况？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社template T LinkQueue:DeQu
40、eue()if(rear=front)throw 下溢下溢;p=front-next;x=p-data;front-next=p-next;if(p-next=NULL)rear=front;delete p;return x;特殊线性表特殊线性表队列队列链队列的实现链队列的实现出队出队数据结构（数据结构（C版）版）清华大学出版社清华大学出版社循环队列和链队列的比较循环队列和链队列的比较时间性能时间性能:循环队列和链队列的基本操作都需要常数时间循环队列和链队列的基本操作都需要常数时间O(1)。空间性能空间性能:循环队列：必须预先确定一个固定的长度，所以有循环队列：必须预先确定一个固定的长度，所
41、以有存储元素个数的限制和空间浪费的问题。存储元素个数的限制和空间浪费的问题。链队列：没有队列满的问题，只有当内存没有可用链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。指针域，从而产生了结构性开销。特殊线性表特殊线性表队列队列数据结构（数据结构（C版）版）清华大学出版社清华大学出版社串的比较：串的比较：通过组成串的通过组成串的字符字符之间的比较来进行的。之间的比较来进行的。给定两个串：给定两个串：X=x1x2xn和和Y=y1y2ym，则：，则：1.当当n=m且且x1=y1，xn=y
42、m时，称时，称X=Y；2.当下列条件之一成立时，称当下列条件之一成立时，称XY：nm且且xi=yi（1 in）；）；存在存在kmin(m,n)，使得使得xi=yi(1ik-1)且且xkyk。特殊线性表特殊线性表串串串的逻辑结构串的逻辑结构例：例：S1=ab12cd，S2=ab12，S3=ab13数据结构（数据结构（C版）版）清华大学出版社清华大学出版社第四章第四章 广义线性表广义线性表本章的基本内容是：本章的基本内容是：数组的逻辑结构特征数组的逻辑结构特征数组的存储方式及寻址方法数组的存储方式及寻址方法特殊矩阵和稀疏矩阵的压缩存储方法特殊矩阵和稀疏矩阵的压缩存储方法广义表的基本概念和存储结构广
43、义表的基本概念和存储结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社第四章第四章 广义线性表广义线性表线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制插入、删除位置限制插入、删除位置线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制元素类型为字符限制元素类型为字符栈栈仅在表尾进行插入和删除操作的线性表。仅在表尾进行插入和删除操作的线性表。队列队列在一端进行插入操作，而另一端进行在一端进行插入操作，而另一端进行删除操作的线性表。删除操作的线性表。串串零个或多个字符组成的有限序列零个或多个字符组成的有限序列 。特殊
44、线性表特殊线性表数据结构（数据结构（C版）版）清华大学出版社清华大学出版社第四章第四章 广义线性表广义线性表线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。将元素的类型进行扩充将元素的类型进行扩充广义线性表广义线性表（多维）数组（多维）数组线性表中的数据元素可以是线性表中的数据元素可以是线性表，但所有元素的类型相同。线性表，但所有元素的类型相同。广义表广义表线性表中的数据元素可以是线性表，线性表中的数据元素可以是线性表，且元素的类型可以不相同。且元素的类型可以不相同。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数组的定义数组的定义数组是由一组数组是
45、由一组类型相同类型相同的数据元素构成的的数据元素构成的有序有序集集合合，每个数据元素称为一个数组元素（简称为元每个数据元素称为一个数组元素（简称为元素），每个元素受素），每个元素受n(n1)个个线性关系线性关系的约束，的约束，每每个元素在个元素在n个线性关系中的序号个线性关系中的序号i1、i2、in称为称为该元素的下标，并称该数组为该元素的下标，并称该数组为 n 维数组。维数组。数组的特点数组的特点元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。广义线性表广义线性表多维数组多
46、维数组数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广义线性表广义线性表多维数组多维数组 a11 a12 a1n a21 a22 a2n am1 am2 amnA=例如，元素例如，元素a22受两个线性关系的约束，在行上有受两个线性关系的约束，在行上有一个行前驱一个行前驱a21和一个行后继和一个行后继a23，在列上有一个列，在列上有一个列前驱前驱a12和和一个列后继和和一个列后继a32。数组示例数组示例数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数组的基本操作数组的基本操作 存取：给定一组下标，读出对应的数组元素；存取：给定一组下标，读出对应的数组元素；修改：给定一组下
47、标，存储或修改与其相对应的修改：给定一组下标，存储或修改与其相对应的数组元素。数组元素。存取和修改操作本质上只对应一种操作存取和修改操作本质上只对应一种操作寻址寻址数组应该采用何种方式存储？数组应该采用何种方式存储？数组没有插入和删除操作，所以，不用预留空间，数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。适合采用顺序存储。广义线性表广义线性表多维数组多维数组数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广义线性表广义线性表多维数组多维数组l2h2 l1h1(a)二维数组二维数组aij前面的元素个数前面的元素个数=阴影部分的面积阴影部分的面积=整行数每行元素个数整行数
48、每行元素个数+本行中本行中aij前面的元素个数前面的元素个数=(i-l1)(h2-l21)(j-l2)本行中本行中aij前面的元素个数前面的元素个数每行元素个数每行元素个数整整行行数数aij按行优先存储的寻址按行优先存储的寻址数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广义线性表广义线性表多维数组多维数组第第l1行行第第l1+1行行al1l2 al1h2 a(l1+1)l2 a(l1+1)h2 aij ah1h2Loc(aij)Loc(al1l2)(i-l1)(h2-l21)(j-l2)个元素个元素Loc(aij)Loc(al1l2)(il1)(h2l21)(jl2)c按行优先存
49、储的寻址按行优先存储的寻址按列优先存储的寻址方法与此类似。按列优先存储的寻址方法与此类似。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Loc(aijk)=Loc(a000)+(im2m3+jm3+k)c 广义线性表广义线性表多维数组多维数组 n（n2）维维数组一般也采用数组一般也采用按行优先和按列按行优先和按列优先两种存储方优先两种存储方法。法。请自行推导请自行推导任一元素存储地任一元素存储地址的计算方法。址的计算方法。数组的存储结构与寻址数组的存储结构与寻址多维数组多维数组数据结构（数据结构（C版）版）清华大学出版社清华大学出版社采用采用链接链接存储结构存储三元组表，每个非零元
50、素对应存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为：的三元组存储为一个链表结点，结构为：rowcolitemdownrightrow：存储非零元素的行号存储非零元素的行号col：存储非零元素的列号存储非零元素的列号item：存储非零元素的值存储非零元素的值right：指针域，指向同一行中的下一个三元组指针域，指向同一行中的下一个三元组down：指针域，指向同一列中的下一个三元组指针域，指向同一列中的下一个三元组矩阵的压缩存储矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储十字链表十字链表数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 2 0 2M=3
