数据结构c语言版严蔚敏PPT.ppt
《数据结构c语言版严蔚敏PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构c语言版严蔚敏PPT.ppt（814页珍藏版）》请在冰点文库上搜索。
算法与数据结构,教材：
数据结构（C语言版）。
严蔚敏，吴伟民编著。
清华大学出版社。
参考文献：
1数据结构。
张选平，雷咏梅编，严蔚敏审。
机械工业出版社。
2数据结构与算法分析。
CliffordA.Shaffer著，张铭，刘晓丹译。
电子工业出版社。
3数据结构习题与解析（C语实言版）。
李春葆。
清华大学出版社。
4数据结构与算法。
夏克俭编著。
国防工业出版社。
第1章绪论,目前，计算机已深入到社会生活的各个领域，其应用已不再仅仅局限于科学计算，而更多的是用于控制，管理及数据处理等非数值计算领域。
计算机是一门研究用计算机进行信息表示和处理的科学。
这里面涉及到两个问题：
信息的表示，信息的处理。
信息的表示和组织又直接关系到处理信息的程序的效率。
随着应用问题的不断复杂，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。
因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。
编写解决实际问题的程序的一般过程：
如何用数据形式描述问题?
即由问题抽象出一个适当的数学模型;问题所涉及的数据量大小及数据之间的关系;如何在计算机中存储数据及体现数据之间的关系?
处理问题时需要对数据作何种运算?
所编写的程序的性能是否良好?
上面所列举的问题基本上由数据结构这门课程来回答。
计算机求解问题的一般步骤,1.1数据结构及其概念,算法与数据结构是计算机科学中的一门综合性专业基础课。
是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。
1.1.1数据结构的例子,例1：
电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：
（a1,b1），（a2,b2），（an,bn），其中ai,bi（i=1，2n）分别表示某人的名字和电话号码。
本问题是一种典型的表格问题。
如表1-1，数据与数据成简单的一对一的线性关系。
表1-1线性表结构,例2：
磁盘目录文件系统磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推：
本问题是一种典型的树型结构问题，如图1-1，数据与数据成一对多的关系，是一种典型的非线性关系结构树形结构。
图1-1树形结构,例3：
交通网络图从一个地方到另外一个地方可以有多条路径。
本问题是一种典型的网状结构问题，数据与数据成多对多的关系，是一种非线性关系结构。
数据（Data）：
是客观事物的符号表示。
在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素（DataElement）：
是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
一个数据元素可由若干个数据项（DataItem）组成。
数据项是数据的不可分割的最小单位。
数据项是对客观事物某一方面特性的数据描述。
数据对象（DataObject）：
是性质相同的数据元素的集合，是数据的一个子集。
如字符集合C=A,B,C,。
1.1.2基本概念和术语,数据结构（DataStructure）：
是指相互之间具有（存在）一定联系（关系）的数据元素的集合。
元素之间的相互联系（关系）称为逻辑结构。
数据元素之间的逻辑结构有四种基本类型，如图1-3所示。
集合：
结构中的数据元素除了“同属于一个集合”外，没有其它关系。
线性结构：
结构中的数据元素之间存在一对一的关系。
树型结构：
结构中的数据元素之间存在一对多的关系。
图状结构或网状结构：
结构中的数据元素之间存在多对多的关系。
数据结构的形式定义是一个二元组：
Data-Structure=（D，S）其中：
D是数据元素的有限集，S是D上关系的有限集。
例2：
设数据逻辑结构B=（K，R）K=k1,k2,k9R=，画出这逻辑结构的图示，并确定那些是起点，那些是终点,1.1.3数据结构的形式定义,图1-3四类基本结构图,1.1.4数据结构的存储方式,数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。
数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。
元素之间的关系在计算机中有两种不同的表示方法：
顺序表示和非顺序表示。
由此得出两种不同的存储结构：
顺序存储结构和链式存储结构。
顺序存储结构：
用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构（关系）。
链式存储结构：
在每一个数据元素中增加一个存放另一个元素地址的指针（pointer），用该指针来表示数据元素之间的逻辑结构（关系）。
例：
设有数据集合A=3.0,2.3,5.0,-8.5,11.0，两种不同的存储结构。
顺序结构：
数据元素存放的地址是连续的；链式结构：
数据元素存放的地址是否连续没有要求。
数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。
数据结构的三个组成部分：
逻辑结构：
数据元素之间逻辑关系的描述D_S=（D，S）存储结构：
数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。
数据操作：
对数据要进行的运算。
本课程中将要讨论的三种逻辑结构及其采用的存储结构如图1-4所示。
数据类型（DataType）：
指的是一个值的集合和定义在该值集上的一组操作的总称。
数据类型是和数据结构密切相关的一个概念。
在C语言中数据类型有：
基本类型和构造类型。
数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
1.1.5数据类型,数据结构的主要运算包括：
建立（Create）一个数据结构；消除（Destroy）一个数据结构；从一个数据结构中删除（Delete）一个数据元素；把一个数据元素插入（Insert）到一个数据结构中；对一个数据结构进行访问（Access）；对一个数据结构（中的数据元素）进行修改（Modify）；对一个数据结构进行排序（Sort）；对一个数据结构进行查找（Search）。
1.1.6数据结构的运算,抽象数据类型（AbstractDataType，简称ADT）：
是指一个数学模型以及定义在该模型上的一组操作。
ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。
因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。
ADT的形式化定义是三元组：
ADT=（D，S，P）其中：
D是数据对象，S是D上的关系集，P是对D的基本操作集。
1.2抽象数据类型,ADT的一般定义形式是：
ADT数据对象：
数据关系：
基本操作：
ADT其中数据对象和数据关系的定义用伪码描述。
基本操作的定义是：
（）初始条件：
操作结果：
初始条件：
描述操作执行之前数据结构和参数应满足的条件;若不满足，则操作失败，返回相应的出错信息。
操作结果：
描述操作正常完成之后，数据结构的变化状况和应返回的结果。
1.3.1算法算法（Algorithm）：
是对特定问题求解方法（步骤）的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
算法具有以下五个特性有穷性：
一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：
算法中每一条指令必须有确切的含义。
不存在二义性。
且算法只有一个入口和一个出口。
可行性：
一个算法是能行的。
即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。
1.3算法分析初步,输入：
一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
输出：
一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
一个算法可以用多种方法描述，主要有：
使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。
算法和程序是两个不同的概念。
一个计算机程序是对一个算法使用某种程序设计语言的具体实现。
算法必须可终止意味着不是所有的计算机程序都是算法。
在本门课程的学习、作业练习、上机实践等环节，算法都用C语言来描述。
在上机实践时，为了检查算法是否正确，应编写成完整的C语言程序。
评价一个好的算法有以下几个标准正确性（Correctness）：
算法应满足具体问题的需求。
可读性（Readability）：
算法应容易供人阅读和交流。
可读性好的算法有助于对算法的理解和修改。
健壮性（Robustness）：
算法应具有容错处理。
当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。
通用性（Generality）：
算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。
1.3.2算法设计的要求,算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。
其方法通常有两种：
事后统计：
计算机内部进行执行时间和实际占用空间的统计。
问题：
必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。
事前分析：
求出该算法的一个时间界限函数。
1.3.3算法效率的度量,效率与存储量需求：
效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般地，这两者与问题的规模有关。
与此相关的因素有：
依据算法选用何种策略；问题的规模；程序设计的语言；编译程序所产生的机器代码的质量；机器执行指令的速度；撇开软硬件等有关部门因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用n表示），或者说，它是问题规模的函数。
算法分析应用举例,算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作T（n）=O（f（n），称作算法的渐近时间复杂度（AsymptoticTimecomplexity），简称时间复杂度。
一般地，常用最深层循环内的语句中的原操作的执行频度（重复执行的次数）来表示。
“O”的定义：
若f（n）是正整数n的一个函数，则O（f（n）表示M0，使得当nn0时，|f（n）|M|f（n0）|。
表示时间复杂度的阶有：
O
（1）：
常量时间阶O（n）：
线性时间阶O（n）：
对数时间阶O（nn）：
线性对数时间阶,O（nk）：
k2，k次方时间阶例两个n阶方阵的乘法for（i=1，i=n;+i）for（j=1;j=n;+j）cij=0;for（k=1;k=n;+k）cij+=aik*bkj;由于是一个三重循环，每个循环从1到n，则总次数为：
nnn=n3时间复杂度为T（n）=O（n3）例+x;s=0;将x自增看成是基本操作，则语句频度为，即时间复杂度为
（1）。
如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为
（1），即常量阶。
例for（i=1;i=n;+i）+x;s+=x;语句频度为：
2n，其时间复杂度为：
O（n），即为线性阶。
例for（i=1;i=n;+i）for（j=1;j=n;+j）+x;s+=x;语句频度为：
2n2，其时间复杂度为：
O（n2），即为平方阶。
定理：
若A（n）=amnm+am-1nm-1+a1n+a0是一个m次多项式，则A（n）=O（nm）例for（i=2;i=n;+i）for（j=2;j=i-1;+j）+x;ai,j=x;语句频度为：
1+2+3+n-2=（1+n-2）（n-2）/2=（n-1）（n-2）/2=n2-3n+2时间复杂度为O（n2），即此算法的时间复杂度为平方阶。
一个算法时间为O
（1）的算法，它的基本运算执行的次数是固定的。
因此，总的时间由一个常数（即零次多项式）来限界。
而一个时间为O（n2）的算法则由一个二次多项式来限界。
以下六种计算算法时间的多项式是最常用的。
其关系为：
O
（1）O（n）O（n）O（nn）O（n2）O（n3）指数时间的关系为：
O（2n）O（n!
）O（nn）当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。
因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。
有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。
例1：
素数的判断算法。
Voidprime（intn）/*n是一个正整数*/inti=2;while（n%i）!
=0嵌套的最深层语句是i+；其频度由条件（n%i）!
=0&i*1.0sqrt（n）决定，显然i*1.0sqrt（n），时间复杂度O（n1/2）。
例2：
冒泡排序法。
Voidbubble_sort（inta，intn）change=false;for（i=n-1;change=TURE;i1最好情况：
0次最坏情况：
1+2+3+n-1=n（n-1）/2平均时间复杂度为：
O（n2）,1.3.4算法的空间分析,空间复杂度（Spacecomplexity）：
是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。
记作：
S（n）=O（f（n）其中：
n为问题的规模（或大小）该存储空间一般包括三个方面：
指令常数变量所占用的存储空间;输入数据所占用的存储空间;辅助（存储）空间。
一般地，算法的空间复杂度指的是辅助空间。
一维数组an：
空间复杂度O（n）二维数组anm：
空间复杂度O（n*m）,习题一,1简要回答术语：
数据，数据元素，数据结构，数据类型。
2数据的逻辑结构？
数据的物理结构？
逻辑结构与物理结构的区别和联系是什么？
3数据结构的主要运算包括哪些？
4算法分析的目的是什么？
算法分析的主要方面是什么？
5分析以下程序段的时间复杂度，请说明分析的理由或原因。
第2章线性表,线性结构是最常用、最简单的一种数据结构。
而线性表是一种典型的线性结构。
其基本特点是线性表中的数据元素是有序且是有限的。
在这种结构中：
存在一个唯一的被称为“第一个”的数据元素；存在一个唯一的被称为“最后一个”的数据元素；除第一个元素外，每个元素均有唯一一个直接前驱；除最后一个元素外，每个元素均有唯一一个直接后继。
2.1线性表的逻辑结构,线性表（LinearList）：
是由n（n0）个数据元素（结点）a1，a2，an组成的有限序列。
该序列中的所有结点具有相同的数据类型。
其中数据元素的个数n称为线性表的长度。
当n=0时，称为空表。
当n0时，将非空的线性表记作：
（a1，a2，an）a1称为线性表的第一个（首）结点，an称为线性表的最后一个（尾）结点。
2.1.1线性表的定义,a1，a2，ai-1都是ai（2in）的前驱，其中ai-1是ai的直接前驱;ai+1，ai+2，an都是ai（1in-1）的后继，其中ai+1是ai的直接后继。
2.1.2线性表的逻辑结构,线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。
线性表中的结点可以是单值元素（每个元素只有一个数据项）。
例1:
26个英文字母组成的字母表：
（A，B，C、Z）,例2：
某校从1978年到1983年各种型号的计算机拥有量的变化情况：
（6，17，28，50，92，188）例3：
一副扑克的点数（2，3，4，J，Q，K，A）线性表中的结点可以是记录型元素，每个元素含有多个数据项，每个项称为结点的一个域。
每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。
例4：
某校2001级同学的基本情况：
（2001414101，张里户，男，06/24/1983），（2001414102，张化司，男，08/12/1984），（2001414102，李利辣，女，08/12/1984）若线性表中的结点是按值（或按关键字值）由小到大（或由大到小）排列的，称线性表是有序的。
2.1.3线性表的抽象数据类型定义,ADTList数据对象：
D=ai|aiElemSet,i=1,2,n,n0数据关系：
R=|ai-1,aiD,i=2,3,n基本操作：
InitList（&L）操作结果：
构造一个空的线性表L；,线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。
对线性表的数据元素可以访问、插入和删除。
ListLength（L）初始条件：
线性表L已存在；操作结果：
若L为空表，则返回TRUE，否则返回FALSE；.GetElem（L,i,&e）初始条件：
线性表L已存在，1iListLength（L）；操作结果：
用e返回L中第i个数据元素的值；ListInsert（L,i,&e）初始条件：
线性表L已存在，1iListLength（L）；操作结果：
在线性表L中的第i个位置插入元素e；ADTList,2.2线性表的顺序存储,顺序存储：
把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。
用这种方法存储的线性表简称顺序表。
顺序存储的线性表的特点：
线性表的逻辑顺序与物理顺序一致;数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。
设有非空的线性表：
（a1，a2，an）。
顺序存储如图2-1所示。
2.2.1线性表的顺序存储结构,在具体的机器环境下：
设线性表的每个元素需占用l个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。
则线性表中第i+1个数据元素的存储位置LOC（ai+1）和第i个数据元素的存储位置LOC（ai）之间满足下列关系：
LOC（ai+1）=LOC（ai）+l线性表的第i个数据元素ai的存储位置为：
LOC（ai）=LOC（a1）+（i-1）*l,在高级语言（如C语言）环境下：
数组具有随机存取的特性，因此，借助数组来描述顺序表。
除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。
#defineOK1#defineERROR-1#defineMAX_SIZE100typedefintStatus;typedefintElemType;typedefstructsqlistElemTypeElem_arrayMAX_SIZE;intlength;SqList;,2.2.2顺序表的基本操作,顺序存储结构中，很容易实现线性表的一些操作：
初始化、赋值、查找、修改、插入、删除、求长度等。
以下将对几种主要的操作进行讨论。
1顺序线性表初始化StatusInit_SqList（SqList*L）L-elem_array=（ElemType*）malloc（MAX_SIZE*sizeof（ElemType）;if（!
L-elem_array）returnERROR;elseL-length=0;returnOK;,2顺序线性表的插入在线性表L=（a1，ai-1，ai，ai+1，an）中的第i（1in）个位置上插入一个新结点e，使其成为线性表：
L=（a1，ai-1，e，ai，ai+1，an）实现步骤
（1）将线性表L中的第i个至第n个结点后移一个位置。
（2）将结点e插入到结点ai-1之后。
（3）线性表长度加1。
算法描述StatusInsert_SqList（Sqlist*L，inti，ElemTypee）intj;if（iL-length-1）returnERROR;if（L-length=MAX_SIZE）printf（“线性表溢出!
n”）;returnERROR;for（j=L-length1;j=i-1;-j）L-Elem_arrayj+1=L-Elem_arrayj;/*i-1位置以后的所有结点后移*/L-Elem_arrayi-1=e;/*在i-1位置插入结点*/L-length+;returnOK;,时间复杂度分析在线性表L中的第i个元素之前插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。
设在线性表L中的第i个元素之前插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi=1/（n+1），而插入时移动结点的次数为n-i+1。
总的平均移动次数：
Einsert=pi*（n-i+1）（1in）Einsert=n/2。
即在顺序表上做插入运算，平均要移动表上一半结点。
当表长n较大时，算法的效率相当低。
因此算法的平均时间复杂度为O（n）。
3顺序线性表的删除在线性表L=（a1，ai-1，ai，ai+1，an）中删除结点ai（1in），使其成为线性表：
L=（a1，ai-1，ai+1，an）实现步骤
（1）将线性表L中的第i+1个至第n个结点依此向前移动一个位置。
（2）线性表长度减1。
算法描述ElemTypeDelete_SqList（Sqlist*L，inti）intk;ElemTypex;,if（L-length=0）printf（“线性表L为空!
n”）;returnERROR;elseif（iL-length）printf（“要删除的数据元素不存在!
n”）;returnERROR;elsex=L-Elem_arrayi-1;/*保存结点的值*/for（k=i;klength;k+）L-Elem_arrayk-1=L-Elem_arrayk;/*i位置以后的所有结点前移*/L-length-;return（x）;,时间复杂度分析删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。
设在线性表L中删除第i个元素的概率为Pi，不失一般性，设删除各个位置是等概率，则Pi=1/n，而删除时移动结点的次数为n-i。
则总的平均移动次数：
Edelete=pi*（n-i）（1in）Edelete=（n-1）/2。
即在顺序表上做删除运算，平均要移动表上一半结点。
当表长n较大时，算法的效率相当低。
因此算法的平均时间复杂度为O（n）。
4顺序线性表的查找定位删除在线性表L=（a1，a2，an）中删除值为x的第一个结点。
实现步骤
（1）在线性表L查找值为x的第一个数据元素。
（2）将从找到的位置至最后一个结点依次向前移动一个位置。
（3）线性表长度减1。
算法描述StatusLocate_Delete_SqList（Sqlist*L，ElemTypex）/*删除线性表L中值为x的第一个结点*/inti=0,k;,while（ilength）/*查找值为x的第一个结点*/if（L-Elem_arrayi!
=x）i+;elsefor（k=i+1;klength;k+）L-Elem_arrayk-1=L-Elem_arrayk;L-length-;break;if（iL-length）printf（“要删除的数据元素不存在!
n”）;returnERROR;returnOK;,时间复杂度分析时间主要耗费在数据元素的比较和移动操作上。
首先，在线性表L中查找值为x的结点是否存在;其次，若值为x的结点存在，且在线性表L中的位置为i，则在线性表L中删除第i个元素。
设在线性表L删除数据元素概率为Pi，不失一般性，设各个位置是等概率，则Pi=1/n。
比较的平均次数：
Ecompare=pi*i（1in）Ecompare=（n+1）/2。
删除时平均移动次数：
Edelete=pi*（n-i）（1in）Edelete=（n-1）/2。
平均时间复杂度：
Ecompare+Edelete=n，即为O（n）,2.3线性表的链式存储,2.3.1线性表的链式存储结构,链式存储：
用一组任意的存储单元存储线性表中的数据元素。
用这种方法存储的线性表简称线性链表。
存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
链表中结点的逻辑顺序和物理顺序不一定相同。
为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址（或位置），称为指针（pointer）或链（link），这两部分组成了链表中的结点结构，如图2-2所示。
链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。
每一个结只包含一个指针域的链表，称为单链表。
为操作方便，总是在链
升级会员 