全套课件·《数据结构(C语言版).ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《全套课件·《数据结构(C语言版).ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全套 课件 数据结构 语言版
- 资源描述:
-
1、2022-9-121(C语言版语言版)2022-9-1222022-9-123第第1 1章章 绪论绪论2022-9-1241.1 什么是数据结构什么是数据结构2022-9-125 2022-9-126返回返回返回返回登录号登录号书号书号书名书名作者作者出版社出版社定价定价1ISBN 7-302-02368-9/TP1185 数据结构数据结构严蔚敏严蔚敏 清华大学清华大学222ISBN 7-302-00860-4/TP312 C 程序设计程序设计谭浩强谭浩强 清华大学清华大学17.33ISBN 7-5053-9279-4 /TP311 数据结构数据结构徐孝凯徐孝凯 电子工业电子工业294ISBN
2、 7-5053-8168-7/TP4757 计算机系统原理计算机系统原理张基温张基温 电子工业电子工业255ISBN 7-5609-2351-8/TP316 操作系统原理操作系统原理庞丽萍庞丽萍 华中科技大学华中科技大学22.86ISBN 7-304-01404-0/TP68 数据库基础与应用数据库基础与应用王王 利利 中央电大中央电大23.37ISBN 7-5084-1648-1/TP706 网页制作实例教程网页制作实例教程齐建玲齐建玲 中国水利水电中国水利水电20表表 1-1 图书目录表图书目录表2022-9-127 binrootlibuseretcmathdszhaojiang sha
3、oliqueuetree graphstacksw2022-9-128课程编号 课程名称 先修课程 C1 计算机导论 无 C2 数据结构 C3 汇编语言 C4 C 程序设计 C5 计算机图形学 C6 接口技术 C7 数据库原理 C8 编译原理 C9 操作系统C1,C4C2C1C1C2,C3,C4C3C2,C9C4C1C3C6C5C2C4C9C8C7C12022-9-129 通过以上几例可以认为:数据结构就是研究数据的逻辑结构通过以上几例可以认为:数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且
4、确保经过这些运算后所得到的新结构仍然是原来的结构算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。类型。2022-9-12101 1数据数据(Data)Data)数据数据(Data):是对信息的一种符号表示。在计算机科学中是指所是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。包括有能输入到计算机中并被计算机程序处理的符号的总称。包括等。等。数据元素数据元素(Data Element):是数据的基本单位,在计算机程序中是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据
5、项组成。数据项是数据的不可分一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。割的最小单位。2022-9-1211 数据对象数据对象(Data Object):是性质相同的数据元素的集合。是数据是性质相同的数据元素的集合。是数据的一个子集。的一个子集。数据结构数据结构(Data Structure):是相互之间存在一种或多种特定关系是相互之间存在一种或多种特定关系的数据元素的集合。的数据元素的集合。2022-9-12122022-9-1213 数据结构主要指逻辑结构和物理结构。数据结构主要指逻辑结构和物理结构。数据之间的相互关系称为逻辑结构。通常分为数据之间的相互关系称为逻辑
6、结构。通常分为 类基本结构:类基本结构:结构中的数据元素除了同属于一种类型外,别无其它关系。结构中的数据元素除了同属于一种类型外,别无其它关系。结构中的数据元素之间存在一对一的关系。结构中的数据元素之间存在一对一的关系。结构中的数据元素之间存在一对多的关系。结构中的数据元素之间存在一对多的关系。结构中的数据元素之间存在多对多的关系。结构中的数据元素之间存在多对多的关系。2022-9-12142022-9-1215 2022-9-1216 数据对象可以是有限的,也可以是无限的。数据对象可以是有限的,也可以是无限的。数据结构不同于数据类型,也不同于数据对象,它不仅要描述数据类型的数据数据结构不同于
7、数据类型,也不同于数据对象,它不仅要描述数据类型的数据对象,而且要描述数据对象各元素之间的相互关系。对象,而且要描述数据对象各元素之间的相互关系。2022-9-12172022-9-12182022-9-12192022-9-12202022-9-12212022-9-1222 1.2 算法描述算法描述 2022-9-12232022-9-1224 2022-9-12252022-9-12262022-9-1227 1.3 算法分析与评价算法分析与评价 2022-9-12282022-9-12292022-9-12301数据结构研究的是数据的表示和数据之间的关系。从逻辑上数据结构研究的是数据的
8、表示和数据之间的关系。从逻辑上讲,数据有集合、线性、树和图四种结构。从存储结构上讲,讲,数据有集合、线性、树和图四种结构。从存储结构上讲,数据有顺序结构、链接结构、索引结构和散列结构四种。理论数据有顺序结构、链接结构、索引结构和散列结构四种。理论上,任一种数据逻辑结构都可以用任一种存储结构来实现。上,任一种数据逻辑结构都可以用任一种存储结构来实现。2在集合结构中,数据处于无序的、各自独立的状态;在线性在集合结构中,数据处于无序的、各自独立的状态;在线性结构中,数据之间是结构中,数据之间是1对对1的关系;在树结构中,数据之间是的关系;在树结构中,数据之间是1对对多的关系;在图结构中,数据之间是多
9、对多的关系。多的关系;在图结构中,数据之间是多对多的关系。3就存储结构而言,一个数组占有一片连续的存储空间,每个就存储结构而言,一个数组占有一片连续的存储空间,每个元素的物理存储单元是按下标位置从元素的物理存储单元是按下标位置从0开始连续编号的,相邻元开始连续编号的,相邻元素之间其存储位置也相邻。对于任一种数据的逻辑结构,若能素之间其存储位置也相邻。对于任一种数据的逻辑结构,若能够把元素之间的逻辑关系对应地转换为数组下标位置之间的物够把元素之间的逻辑关系对应地转换为数组下标位置之间的物理关系,则就能够利用数组来实现其顺序存储结构。理关系,则就能够利用数组来实现其顺序存储结构。2022-9-12
10、314抽象数据类型是数据和对数据进行各种操作的集合体。这抽象数据类型是数据和对数据进行各种操作的集合体。这里所说的数据是广义的,是带有结构的数据,它可以具有任何里所说的数据是广义的,是带有结构的数据,它可以具有任何逻辑结构和存储结构。逻辑结构和存储结构。5算法的评价指标主要为正确性、健壮性、可读性和有效性算法的评价指标主要为正确性、健壮性、可读性和有效性四个方面。有效性又包括时间复杂度四个方面。有效性又包括时间复杂度(性性)和空间复杂度和空间复杂度(性性)两个两个方面。一个算法的时间和空间复杂度越好,就越节省时间和空方面。一个算法的时间和空间复杂度越好,就越节省时间和空间,则表明该算法越有效。
11、间,则表明该算法越有效。6算法的时间复杂度和空间复杂度通常用数量级的形式表示算法的时间复杂度和空间复杂度通常用数量级的形式表示出来。数量级的形式可分为常量级,对数级、线性级、平方级、出来。数量级的形式可分为常量级,对数级、线性级、平方级、立方级等多个级别。当数据处理量较大时,处于前面级别的算立方级等多个级别。当数据处理量较大时,处于前面级别的算法比处于后面级别的算法更有效。法比处于后面级别的算法更有效。2022-9-12322022-9-1233 线性表 2022-9-1234 常常将非空的线性表常常将非空的线性表(n0)记作:记作:(a1,a2,an)这里的数据元素这里的数据元素 ai(1i
12、n)只是一个抽象的符号,其具体含只是一个抽象的符号,其具体含义在不同的情况下可以不同。义在不同的情况下可以不同。2022-9-1235例例1、26个英文字母组成的字母表个英文字母组成的字母表 (A,B,C、Z)例例2、从、从1978年到年到1983年各种型号的计算机拥有量的变化情况。年各种型号的计算机拥有量的变化情况。(6,17,28,50,92,188)例例3、2022-9-1236从以上例子可看出线性表的逻辑特征是:从以上例子可看出线性表的逻辑特征是:在非空的线性表,有且仅有一个开始结点在非空的线性表,有且仅有一个开始结点a1,它没有直接它没有直接前趋,而仅有一个直接后继前趋,而仅有一个直
13、接后继a2;有且仅有一个终端结点有且仅有一个终端结点an,它没有直接后继,而仅有一个它没有直接后继,而仅有一个直接前趋直接前趋a n-1;其余的内部结点其余的内部结点ai(2in-1)都有且仅有一个直接前趋都有且仅有一个直接前趋a i-1和和一个直接后继一个直接后继a i+1。线性表是一种典型的线性结构。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的,而运算的具体实现则数据的运算是定义在逻辑结构上的,而运算的具体实现则是在存储结构上进行的。是在存储结构上进行的。2022-9-12372 线性表的基本运算 2022-9-1238。2022-9-1239 1.线性表的顺序存储结构 20
14、22-9-12402022-9-12412022-9-12422022-9-1243 这样,一个线性表的顺序存储结构需要两个分量。为体现数组这样,一个线性表的顺序存储结构需要两个分量。为体现数组data和和length之间的内在联系,通常将它们定义在一个结构类型中。之间的内在联系,通常将它们定义在一个结构类型中。此处的元素类型用此处的元素类型用ElemType来表示。来表示。综上所述,综上所述,在在C C语言中,可用下述类型定义来描述顺序表:语言中,可用下述类型定义来描述顺序表:#define MaxLen 100 /线性表的容量线性表的容量 typedef int ElemType /在实际
15、应用中,将在实际应用中,将ElemType定义成实际类型定义成实际类型 typedef struct ElemType dataMaxLen;/定义存储表中元素的数组定义存储表中元素的数组 int length;/线性表的实际长度线性表的实际长度 sqList;sqList L;/定义表结构的变量定义表结构的变量2022-9-1244 本节将讨论采用顺序存储结构之后,如何实现线性表的基本运本节将讨论采用顺序存储结构之后,如何实现线性表的基本运算,并讨论各算法时间复杂度。算,并讨论各算法时间复杂度。1初始化顺序表初始化顺序表initlist(L)的实现的实现 顺序表的初始化即构造一个空表,顺序表
16、顺序表的初始化即构造一个空表,顺序表L是否为空取决于其是否为空取决于其元素个数是否为元素个数是否为0,因此,只要将表,因此,只要将表L中的表长度置为中的表长度置为0,就可以实,就可以实现建空表的功能。现建空表的功能。void initlist(sqList*L)L-length=0;2求线性表长度求线性表长度Getlen(L)的实现的实现 求线性表的长度算法如下:求线性表的长度算法如下:int Getlen(sqList*L)return L-length;该算法的时间复杂度为该算法的时间复杂度为O(1)2022-9-12453按序号取元素按序号取元素Getelem(L,i)的实现的实现 按前
17、面的约定,序号为按前面的约定,序号为i的元素存储在数组下标为的元素存储在数组下标为i-1的数组的数组元素中,所以可直接从该数组元素中取得值。元素中,所以可直接从该数组元素中取得值。i的有效值应大的有效值应大于等于于等于1和小于等于线性表的实际长度。和小于等于线性表的实际长度。ElemType Getelem(sqLlist*L,int i)if(iL-length)printf(“error”);exit(1);return L-datai-1;4查找运算查找运算locate(L,x)的实现的实现要 确定值为确定值为x的元素在的元素在L表中的位置,需要依次比较各元素。当表中的位置,需要依次比较
18、各元素。当查询到第一个满足条件的数据元素时,返回其序号,否则返回查询到第一个满足条件的数据元素时,返回其序号,否则返回0,表示查找失败。,表示查找失败。2022-9-1246查找操作的具体实现算法如下:查找操作的具体实现算法如下:int Locate(sqList*L,ElemType x)int i;i=0;while(ilength&L-datai!=x)i+;if(ilength)return i;else return 0;5顺序表的插入算法顺序表的插入算法inselem(L,i,x)的实现的实现 顺序表的插入是指在表的第顺序表的插入是指在表的第 i个位置上插入一个值为个位置上插入一个
19、值为 x的的新元素,插入后使原表长为新元素,插入后使原表长为 n的表:的表:(a1,a2,ai-1,ai,ai+1,an),成为表长为成为表长为 n+1n+1的表:的表:由算法可知,对于表长为由算法可知,对于表长为n的顺序表,在查找过程中,数据的顺序表,在查找过程中,数据元素比较次数最少为元素比较次数最少为1,最多为,最多为 n,元素比较次数的平均值为元素比较次数的平均值为(n+1)/2,时间复杂度为时间复杂度为 O(n)。2022-9-1247 (a1,a2,ai-1,x,ai,ai+1,an),i 的取值范围为的取值范围为1iin+1。下图表示一个顺序表中的数组在进行插入运算前下图表示一个
20、顺序表中的数组在进行插入运算前后,数据元素在数组中的下标变化。后,数据元素在数组中的下标变化。0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1 ai+1 i+2 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i x i+1 ai i+2ai+1 numanum 插入插入x插入前插入前插入后插入后2022-9-1248void Inselem(sqList*L,int i,Elemtype x)if(iL-length+1)printf(“Error!”);/插入位置出错插入位置出错 exit(1);if(L-length=MaxLen)printf
21、(“overflow!”);/表已满表已满 exit(1);for(j=L-length;j=i;j-)L-dataj+1=L-dataj;/数据元素后移数据元素后移 L-datai=x;/插入插入x L-length+;/表长度加表长度加1 2022-9-1249 )1(11inpEniiin11112)1(11)1(Eniniiinninninp假设表中任何位置插入概率是均等的假设表中任何位置插入概率是均等的,即即Pi=1/(n+1),则:则:该算法的时间主要花费在移动数据元素上,移动个数取决于插该算法的时间主要花费在移动数据元素上,移动个数取决于插入位置入位置 i和表的长度和表的长度n。
22、所以可以用数据元素的移动操作来估计算法所以可以用数据元素的移动操作来估计算法的时间复杂度。在第的时间复杂度。在第 i个位置上插入个位置上插入 x,共需要移动共需要移动 n-i+1个元素,个元素,i 的取值范围为的取值范围为:1i n+1,即有即有 n+1个位置可以插入。个位置可以插入。当当i=n+1时,不需要移动结点;当时,不需要移动结点;当i=1时需要移动时需要移动n个结点个结点。由此。由此可以看出,算法在最好的情况下时间复杂性为可以看出,算法在最好的情况下时间复杂性为O(1),最坏的时间复最坏的时间复杂性是杂性是O(n)。由于插入的位置是随机的,因此,需要分析执行该算法移动数由于插入的位置
23、是随机的,因此,需要分析执行该算法移动数据元素的平均值。设在第据元素的平均值。设在第i个位置上作插入的概率为个位置上作插入的概率为Pi,则平均移动则平均移动数据元素的次数:数据元素的次数:2022-9-1250 由此可以看出,在线性表上做插入操作需要移动表中一由此可以看出,在线性表上做插入操作需要移动表中一半的数据元素,当半的数据元素,当n较大时,算法的效率是比较低的,所以较大时,算法的效率是比较低的,所以在线性表上进行插入操作的时间复杂度为在线性表上进行插入操作的时间复杂度为(n)。顺序表的删除运算是指将表中第顺序表的删除运算是指将表中第 i 个元素从线性表中去掉,个元素从线性表中去掉,原表
24、长为原表长为 n 的线性表的线性表(a1,a2,ai-1,ai,ai+1,an)。进行删除以后的线性表表长变为进行删除以后的线性表表长变为 n-1的表的表(a1,a2,ai-1,ai+1,an),i 的取值范围为:的取值范围为:1in。图图2-5表示一个顺序表的数组在进行删除运算前后,其数表示一个顺序表的数组在进行删除运算前后,其数据元素在数组中的下标变化。据元素在数组中的下标变化。2022-9-1251图图2-5 线性表中的删除运算示意图线性表中的删除运算示意图a1a2ai-1ana1a2.ai-1aiai+1.an.MaxLen-1012in-1n删除aiMaxLen-1012.i-1i+
25、1 i+2n-1下标数据元素下标数据元素删除前删除后ai+1i-1i+1an-1.2022-9-1252 在线性表上完成上述运算通过以下两个操作来实现:在线性表上完成上述运算通过以下两个操作来实现:(1)(1)线性表中第线性表中第i个至第个至第n个元素(共个元素(共n-i+1个元素)依次向前移个元素)依次向前移动一个位置。将所删除的元素动一个位置。将所删除的元素ai覆盖掉,从而保证逻辑上相邻覆盖掉,从而保证逻辑上相邻的元素物理位置也相邻。的元素物理位置也相邻。(2)(2)修改线性表长度,使其减修改线性表长度,使其减1。线性表的删除算法如下:线性表的删除算法如下:void Delelem(sqL
展开阅读全文