2023年数据结构讲稿

2023年数据结构讲稿 云淡风清 第1章 数据结构概述 1.1概述 以下为某市部分院校的交通地图情况，要求找出从出发点到目的地之间的最短路径及其长度。 对于此问题，如果手工去做，速度慢(特别地，现实中实际地图信息要比此例复杂许多)，还容易出错，此时可借助于计算机完成。 计算机进行此类信息的处理时，涉及到两个问题：一是现实当中的信息在计算机中如何表示，二是如何对信息进行处理。 信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题不断复杂化，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 1.1.1编写解决实际问题的程序的一般流程 如何通过编写程序，以比手工更为高效精确的方式解决实际问题呢？一般流程如下： 1、由具体问题抽象出一个适当的数学模型； 2、分析问题所涉及的数据量大小及数据之间的关系； 3、确定如何在计算机中存储数据及体现数据之间的关系？ 4、确定处理问题时需要对数据作何种运算？ 5、确定算法并编写程序； 5、分析所编写的程序的性能是否良好？若性能不够好则重复以上步骤。 云淡风清 上面所列举的问题基本上由数据结构这门课程来回答。 数据结构是计算机科学中的一门综合性专业基础课，是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。 1.1.2数据结构的例子 1、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。 姓名 电话号码 陈伟海 13612345588 李四锋 13056112345 。 这是一种典型的线性结构。 2、磁盘目录文件系统 磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推。 。 本问题中各目录从上到小形成了一种一对多的关系，是一种典型的树形结构。 云淡风清 3、交通网络图 下图表明了若干个城市之间的联系： 从图中可看出，一个地方到另外一个地方可以有多条路径，是一种典型的网状结构，数据与数据成多对多的关系。 4、排序问题 对100000个整数进行降序排序。 冒泡法程序： #include #include #include #define N 100000 void main() int i,j; int aN+1; srand(time(NULL); for(i=1;i ai=rand(); printf(n按原序输出：n); for(i=1;i printf(%8d,ai); system(pause); for(j=1;j for(i=N;ij;i-) if(aiai-1) a0=ai; ai=ai-1; ai-1=a0; printf(n按新次序输出：n); 云淡风清 for(i=1;i printf(%8d,ai); printf(n); 快速排序程序： #include #include #include #define N 100000 void quick_sort(int aN+1,int left,int right) int j,last,temp; if(left /将划分子集的元素(此处选中间元素)移动到最左边 temp=aleft; aleft=a(left+right)/2; a(left+right)/2=aleft; last=left;/用last记录比关键字小的元素的最右位置 for(j=left+1;j if(ajaleft) temp=alast; alast=aj; aj=temp; last+; /对形成的新子集递归进行快速排序 quick_sort(a,left,last-1); quick_sort(a,last+1,right); void main() int i; int aN+1; srand(time(NULL); for(i=1;i ai=rand(); printf(n按原序输出：n); for(i=1;i printf(%8d,ai); system(pause); 云淡风清 quick_sort(a,1,N); printf(n按新次序输出：n); for(i=1;i printf(%8d,ai); printf(n); 运行可知，两者速度差异非常明显，主要是排序所花的时间差别很大。可看出，同样的问题，采用不同方法进行处理，有可能呈现出非常大的性能方面的差异。 还可以找到许多其它例子，如图书馆的书目检索系统自动化问题，教师资料档案管理系统，多叉路口交通灯的管理问题等。 1.2基本概念和术语 1.2.1数据(Data)： 是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。 1.2.2数据元素(Data Element)： 是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。 1.2.3数据对象(Data Object)： 是性质相同的数据元素的集合，是数据的一个子集，其中的数据元素可以是有限的，也可以是无限的。如整数集合：N=0，1，2，是无限集，而字符集合：C=A，B，Z则为有限集。 1.2.4数据的逻辑结构： 指对数据元素之间逻辑关系的描述。 数据元素之间的关系可以是一种或多种。 数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。其要点有两个方面：一是元素本身，二是元素之间的关系。数据元素之间的逻辑结构有四种基本类型，如下： 云淡风清 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。 线性结构：结构中相邻的数据元素之间存在一对一的关系。 树型结构：结构中相邻的数据元素之间存在一对多的关系。 图状结构或网状结构：结构中相邻的数据元素之间存在多对多的关系。 数据结构数学形式的定义是一个二元组： DataStructure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 例：设数据逻辑结构B=(K，R)，其中： K=k1, k2, , k9 R=， 画出这逻辑结构的图示，并确定哪些是起点，哪些是终点。 1.2.5数据的物理结构： 又称存储结构，指数据结构在计算机内存中的存储方式。 数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的存储。 元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。 顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。 链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer)，用该指针来表示数据元素之间的逻辑结构(关系)。 例：设有数据集合A=3.0,2.3,5.0,-8.5,11.0，两种不同的存储结构。 顺序结构：数据元素存放的地址是连续的； 链式结构：数据元素存放的地址是否连续没有要求。 数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。 在C语言中，用一维数组表示顺序存储结构；通过结构体类型实现的链表来表示链式存储结构。 1.2.6数据结构(Data Structure)： 按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。 1.2.7数据结构的三个组成部分： 逻辑结构：数据元素之间逻辑关系的描述：D_S=(D，S)。 存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。 数据操作：对数据要进行的运算。 本课程中将要讨论的三种逻辑结构及其采用的存储结构如下图所示。 云淡风清 逻辑结构与所采用的存储结构 数据逻辑结构层次关系图 1.2.8数据类型(Data Type)： 指的是一个值的集合和定义在该值集上的一组操作的总称。 数据类型是和数据结构密切相关的一个概念。在C语言中数据类型有：基本类型(如int，float，double，char等)和构造类型(如数组，结构体，共用体等)。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。 1.3数据结构的运算 数据结构的主要运算包括： 建立(Create)一个数据结构； 消除(Destroy)一个数据结构； 从一个数据结构中删除(Delete)一个数据元素； 把一个数据元素插入(Insert)到一个数据结构中； 对一个数据结构进行访问(Acce)； 对一个数据结构(中的数据元素)进行修改(Modify)； 对一个数据结构进行排序(Sort)； 对一个数据结构进行查找(Search)。 以上只列举了一些常见运算，实际应用当中可能会遇到许多其它运算。 云淡风清 1.4抽象数据类型(Abstract Data Type) 1.4.1抽象数据类型简介： 简称ADT，是指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。 ADT的形式化定义是三元组：ADT=(D，S，P) 其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。 说明： ADT和数据类型实质上是一个概念，其区别是：ADT的范畴更广,它不再局限于系统已定义并实现的数据类型，还包括用户自己定义的数据类型。 ADT的定义是由一个值域和定义在该值域上的一组操作组成。包括定义，表示和实现三个部分。 ADT的最重要的特点是抽象和信息隐蔽。抽象的本质就是抽取反映问题本质的东西，忽略非本质的细节，使所设计的结构更具有一般性，可以解决一类问题。信息隐蔽就是对用户隐藏数据存储和操作实现的细节，使用者了解抽象操作或界面服务，通过界面中的服务来访问这些数据。 ADT不考虑物理结构以及算法的具体实现。 例：整数的数学概念和对整数所能进行的运算构成一个ADT，C语言中的变量类型int就是对这个抽象数据类型的一种物理实现。 1.4.2ADT的一般定义形式： ADT的一般定义形式是： ADT 数据对象： 数据关系： 基本操作： ADT 其中数据对象和数据关系的定义用伪码描述。 基本操作的定义是： () 初始条件： 操作结果： 说明： 初始条件：描述操作执行之前数据结构和参数应满足的条件；若不满足，则操作失败，返回相应的出错信息。 操作结果：描述操作正常完成之后，数据结构的变化状况和应返回的结果。 1.5算法(Algorithm) 1.5.1算法基本概念： 算法是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或 云淡风清 多个操作。 1.5.2算法的基本特征： 算法具有以下五个特性 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 1.5.3算法的基本描述方法： 一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述等。 1.5.4算法与程序的异同比较： 算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。 1.5.5评价算法好坏的几个标准： 评价一个好的算法有以下几个标准 正确性(Correctne)：算法应满足具体问题的需求。 可读性(Readability)：算法应易于供人阅读和交流。可读性好的算法有助于对算法的理解和修改。 健壮性(Robustne)：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。 通用性(Generality)：算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。 效率与存储容量需求：效率指的是算法执行的时间；存储容量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。 1.6算法效率的度量 解决同一个问题的算法可能有多种，如何选择一个效率高的算法呢？应该来讲，与算法效率相关的因素有很多，如下： 云淡风清 1、算法选用何种策略； 2、问题的规模； 3、程序设计的语言； 4、编译程序所产生的机器代码的质量； 5、内存的大小； 6、外存的大小； 7、机器执行指令的速度； 8、其它。 而确定算法效率的方法通常有两种： 1.6.1事后统计： 先实现算法，然后运行程序，测算其时间和空间的消耗。 缺点： 1、必须先依据算法编制程序并运行程序，耗费人力物力； 2、依赖软硬件环境，容易掩盖算法本身的优劣。由于算法的运行与计算机的软硬件等环境因素有关，不容易发现算法本身的优劣。同样的算法用不同的编译器编译出的目标代码数量不同，完成算法所需的时间也不同；若计算机的存储空间较小，算法运行时间也就会延长； 3、没有实际价值。测试花费不少时间但并没有解决现实中的实际问题。 1.6.2事前分析： 仅仅通过比较算法本身的复杂性来评价算法的优劣，不考虑其它的软硬件因素，通常考查算法所用的时间和所需的存储空间。 算法复杂性的度量可以分为时间复杂度和空间复杂度。 1.6.3算法的时间复杂度(Time complexity) 1、算法的时间复杂度 算法的时间复杂度用于度量一个算法所用的时间。 算法所用的时间主要包括程序编译时间和运行时间。由于一个算法一旦编译成功可以多次运行，因此可以忽略编译时间，只讨论算法的运行时间。 算法的运行时间依赖于加、减、乘、除、等基本的运算以及参加运算的数据量的大小，另外，与计算机硬件和操作环境等也有关系。要想准确地估算时间是不可行的，而影响算法时间最为主要的因素是问题的规模，即输入量的多少。同等条件下，问题的规模越大，算法所花费的时间也就越长。例如，求1+2+3+n的算法，即n个整数的累加求和，这个问题的规模为n。因此，运行算法所需的时间T是问题规模n的函数，记作T(n)。 同等条件下，相同或类似的基本操作在真正程序运行过程中所花费的时间也差不多，这样，如果两个不同算法中一个所含基本操作多而另一个所含基本操作少，则包含基本操作少的算法其花费时间也就较少。因此，通常用算法中基本语句的执行次数来作为度量算法速度快慢的依据，而这种度量时间复杂度的方法得出的不是时间量，而是一种增长趋势的度量，即当问题规模n增大时，T(n)也随之变大。换言之，当问题规模充分大时，算法中基本语句的执行次数为在渐进意义下的阶，称为算法的渐进时间复杂度，简称时间复杂度，通常用大O记号表示。用数学语言通常描述为：若当且仅当存在正整数n和n0，对于任意nn0，都有T(n)cf(n)，则称该算法的渐进时间复杂度为T(n)=O(f(n)。 一般地，常用最内层循环内的语句中的原操作的执行频度(重复执行的次数)来表示时间复杂度。 2、时间复杂度分析举例： 例：两个n阶方阵的乘法。 云淡风清 for(i=1;i cij=0; for(k=1;k cij+=aik*bkj; 分析：由于是一个三重循环，每个循环从1到n，则总次数为： nnn=n3，时间复杂度为T(n)=O(n3)。 例： +x; s=0; 分析：将x自增看成是基本操作，则语句频度为1，即时间复杂度为O(1) 。 如果将s=0也看成是基本操作，则语句频度为2，其时间复杂度仍为O(1)，即常量阶。 只要T(n)不是问题规模n的函数，而是一个常数，它的时间复杂度则均为O(1)。 例：以下程序段： for(i=1;i +x; s+=x; 分析：基本语句的语句频度为：n2 ，其时间复杂度为：O(n2)，即为平方阶。 定理：若T(n)=amnm+am-1nm-1+a1n+a0是一个m次多项式，则T(n)=O(nm)，即复杂度表达式只取一个n趋向于无穷大时的同阶无穷小表达式即可。 通过对算法复杂度的分析，总结出这样一条结论，在计算任何算法的复杂度时，可以忽略所有低次幂和最高次幂的系数，这样可以简化算法分析，并使注意力集中在增长率上。 从本质上来讲，此种策略也就是只考虑对算法复杂度影响最大的因素而忽略次要因素。 例：以下程序段： for(i=2;i for(j=2;j +x; ai,j=x; 云淡风清 分析：基本语句的语句频度为： 1+2+3+n-2 =(1+n-2)(n-2)/2 =(n-1)(n-2)/2 =(n2-3n+2)/2 按上述定理，时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。 一个算法时间复杂度为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数(即零次多项式)来界定。而一个时间为O(n2)的算法则由一个二次多项式来界定。 3、常见表示时间复杂度的阶： O(1)：常量时间阶 O(n)：线性时间阶 O(n)：对数时间阶 O(nn)：线性对数时间阶 O(nk)：k2，k次方时间阶 4、常见时间复杂度大小关系分析： 以下六种计算算法时间复杂度的多项式是最常用的，其大小关系通常为： O(1) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。 有的情况下，算法中基本操作重复执行的次数还随输入数据集的不同而不同。 例：素数的判断算法。 void prime(int n)/n是一个正整数 int i=2; while(n%i)!=0 & i*1.0 i+; if(i*1.0sqrt(n) printf(&d 是一个素数n,n); else printf(&d 不是一个素数n,n); 此例中执行频率最高的语句为i+;，此语句最少执行0次，最多执行sqrt(n)次，对于不同的n，执行次数不确定。 对于此类算法，如果输入数据不同，则算法运行时间也不同，因此要全面分析一个算法，需要考虑算法在最好、最坏、平均情况下的时间消耗。由于最好情况出现的概率太小，因此不具代表性，但是，当最好情况出现的概率大时，应该分析最好情况；虽然最坏情况出现的概率也太小，不具代表性，但是分析最坏情况能够让人们知道算法的运行时间最坏能到什么程度，这一点在实时系统中很重要；分析平均情况是比较普遍的，特别是同一个算法要处理不同的输入时，通常假定输入的数据是等概率分布的。 例：冒泡排序法。 void bubble_sort(int a,int n) 云淡风清 int temp; change=false; for(i=n-1;change=TURE;i1 & change;-i) for(j=0;j if(ajaj+1) temp=aj; aj=aj+1; aj+1=temp; change=TURE; 最好情况：0次 最坏情况：1+2+3+n-1=n(n-1)/2平均时间复杂度为：O(n2) 1.6.4算法的空间复杂度(Space complexity) 1、算法的空间复杂度 算法的空间复杂度是指在算法的执行过程中需要的辅助空间数量。辅助空间数量指的不是程序指令、常数、指针等所需要的存储空间，也不是输入数据所占用的存储空间，辅助空间是除算法本身和输入输出数据所占据的空间外，算法临时开辟的存储空间。算法的空间复杂度分析方法同算法的时间复杂度相似，设S(n)是算法的空间复杂度，通常可以表示为： S(n)=O(f(n) 其中：n为问题的规模(或大小)。 该存储空间一般包括三个方面： 指令常数变量所占用的存储空间； 输入数据所占用的存储空间； 辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。 如： 一维数组an：空间复杂度O(n) 二维数组anm：空间复杂度O(n*m) 例：数组a中有10000个数，要求将所有数据逆置(即顺序倒过来存放)。 为达到逆置目的，有以下两种方案： 方案一： int a10000,b10000,i; for(i=0;i int a10000,t,i; for(i=0;i 云淡风清 t=ai; ai=a10000-i-1; a10000-i-1=t; 很明显，方案二中的辅助空间数量为1，而方案一中的辅助空间数量为10000，方案二的空间复杂度优于方案一。 在算法的时间复杂度和空间复杂度中，我们更注重算法的时间性能。因此，在对算法性能的分析当中，通常均主要针对算法时间性能进行分析。 1.6.5学习算法的原因 讲述了这么多关于算法的基础知识，究竟为什么要学习算法呢？ 首先，算法无处不在。算法不仅出现在数学和计算机程序中，更普遍地出现在我们的生活中，在生活中做什么事情都要有一定的顺序，然而不同的顺序带来的效率和成果可能都会不同，只有学好了算法，才能让生活更有趣、更有效率。 其次，算法是程序的灵魂。学习计算机编程，必须要掌握好其灵魂，否则，写出来的程序就像是没有灵魂的躯体。 再次，算法是一种思想。掌握了这种思想，能够拓展思维，使思维变得清晰、更具逻辑性，在生活以及编程上的很多问题，也就更易解决。 最后，算法的乐趣。学习算法不仅仅是为了让它帮助人们更有效地解决各种问题，算法本身的趣味性很强，当通过烦琐的方法解决了一个问题后会感觉到有些疲惫，但是面对同一个问题，如若学会使用算法，更简单有效地解决了这个问题，会发现很有成就感，算法的速度、思想会让人觉得很奇妙。每一个奇妙的算法都是智慧的结晶。 学习算法的理由成千上万，不同的人可能出于不同的目的去学习算法，希望大家能够通过对课程的学习对算法有进一步的理解。 习题一 1、简要回答术语：数据，数据元素，数据结构，数据类型。 2、数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？ 3、数据结构的主要运算包括哪些？ 4、算法分析的目的是什么？算法分析的主要方面是什么？ 云淡风清 第2章 线性表 下表为某电台提供给听众的若干首英文歌曲名及相关点播情况统计信息： 由于实际的歌曲库可能很大，手工管理效率低，不方便，现请设计一个软件系统实现对此类歌曲库的管理。 分析： 此例中相邻的两首歌之间是一种一对一的关系，属于典型的线性结构，可按线性结构进行组织及管理。 2.1线性结构与线性表 2.1.1线性结构 如果一个数据元素序列满足： 除第一个和最后一个数据元素外，每个数据元素只有一个直接前驱数据元素和一个直接后继数据元素； 第一个数据元素没有前驱数据元素； 最后一个数据元素没有后继数据元素。 则称这样的数据结构为线性结构。 线性表、栈、队列、串和数组都属于线性结构。 如下图： 云淡风清 2.1.2线性表 线性表(Linear List)是一种最简单、最常用的线性结构，是一种可以在任意位置进行插入和删除数据元素操作的、由n(n0)个相同类型数据元素a1，a2，an组成的线性结构。在这种结构中： 存在一个唯一的被称为“第一个”的数据元素； 存在一个唯一的被称为“最后一个”的数据元素； 除第一个元素外，每个元素均有唯一一个直接前驱； 除最后一个元素外，每个元素均有唯一一个直接后继。 线性表中的数据元素的个数n称为线性表的长度。 当n=0时，称为空表。空线性表用符号()表示。 当n0时，将非空的线性表记作：(a1，a2，an)，其中符号ai(1in)表示第i个抽象数据元素。 a1称为线性表的第一个(头)结点，an称为线性表的最后一个(尾)结点。 a1，a2，ai-1都是ai(2in)的前驱，其中ai-1是ai的直接前驱； ai+1，ai+2，an都是ai(1i n-1)的后继，其中ai+1是ai的直接后继。 线性结构是最常用、最简单的数据结构，而线性表是一种典型的线性结构，其基本特点是可以在任意位置进行插入和删除等操作，且数据元素是有限的。 线性表可以用顺序存储结构或链式存储结构实现。用顺序存储结构实现的线性表称为顺序表，用链式存储结构实现的线性表称为链表。链表主要有单链表、循环单链表和循环双链表三种。顺序表和链表各有优缺点，并且优缺点刚好相反，在实际应用中要根据情况选择对操作及性能有利的存储结构。 线性表中的数据元素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：某校2023级同学的基本情况：(2023414101，张里户，男，06/24/1983)， (2023414102，张化司，男，08/12/1984) ， (2023414102，李利辣，女，08/12/1984) 若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。 线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。 对线性表的基本操作如下(实际应用中要根据需要选择相应操作或者添加未列出的操作)： 建立空表L 返回表L的长度，即表中元素个数 取线性表L中位置i处的元素(1in) 取i的直接前驱元素 取i的直接后继元素 查询元素x在L中的逻辑位置 在线性表L的位置i处插入元素x，原位置元素后移一个位置 从线性表L中删除位置i处的元素 判断线性表是否为空 清空已存在的线性表 遍历所有元素 云淡风清 根据所给关键字查询元素并返回其详细信息 修改表中元素 对所有元素按条件排序 2.1.3线性表的抽象数据类型定义 ADT List 数据对象：D = ai | aiElemSet, i=1,2,n, n0 数据关系：R = | ai-1, aiD, i=2,3,n 基本操作： InitList(&L) 初始条件：无 操作结果：构造一个空的线性表L； ListLength(L) 初始条件：线性表L已存在； 操作结果：返回线性表中的元素个数； GetElem(L,i,e) 初始条件：线性表L已存在，1iListLength(L)； 操作结果：用e返回L中第i个数据元素的值； ListInsert(L,i,e) 初始条件：线性表L已存在，1iListLength(L)+1，线性表未满； 操作结果：在线性表L中的第i个位置插入元素e，原来位置及以后的元素都后移； ListLocate(L,e) 初始条件：线性表L已存在； 操作结果：返回元素e在L中的逻辑位置，不存在则返回0； ListDelete(L,i) 初始条件：线性表L已存在，1iListLength(L)； 操作结果：从表L中删除位置i处的元素； ListClear(L) 初始条件：线性表L已存在； 操作结果：清空已存在的表； ListTraverse(L) 初始条件：线性表L已存在； 操作结果：遍历输出所有元素； ListUpdate(L,i,e) 初始条件：线性表L已存在,1iListLength(L)； 操作结果：将线性表L中第i个位置的值置为e； ListSort(L) 初始条件：线性表L已存在； 操作结果：按一定条件对所有元素重新排序； ListDestroy(L) 初始条件：线性表L已存在； 操作结果：释放线性表空间； 云淡风清 ADT List 2.2线性表的顺序存储 2.2.1线性表的顺序存储结构 顺序存储：把线性表的结点按逻辑顺序依次存入地址连续的一组存储单元里。用这种方法存储的线性表简称顺序表。 顺序存储的线性表的特点： 线性表的逻辑顺序与物理顺序一致； 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现的。 设有非空的线性表：(a1，a2，an) 。顺序存储如下图所示。 在具体的机器环境下，设线性表的每个元素需占用len个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置，则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足下列关系： Loc(ai+1)=Loc(ai)+l 线性表的第i个数据元素ai的存储位置为： Loc(ai)=Loc(a1)+(i-1)*len 高级语言中同一个数组的各个元素占用连续存储单元，具有随机存取(指存取同一数组各元素的时间开销相同，不受所处位置的限制)的特性，故而在高级语言中通常用数组来存储顺序表。除了用数组来存储线性表的元素之外，顺序表还应该表示线性表的长度属性以方便某些操作，所以用结构体类型来定义顺序表类型。 #include #include #define OK 1 #define ERROR -1 #define MAX_SIZE 100 /最大长度 typedef int Status; /状态 typedef int ElemType;/元素类型，可根据实际需要更改 typedef struct Sqlist ElemType *Elem_Array;/线性表存储空间地址 int Length;/线性表长度 SqList; 注意：C语言中数组的下标值是从0开始，第i个元素的下标值是i-1 。 2.2.2顺序表的基本操作 顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。 以下将对几种主要的操作进行讨论。 #include 云淡风清 #include #define OK 1 #define ERROR -1 #define MAX_SIZE 100 /最大长度 typedef int Status; /状态 typedef int ElemType;/元素类型，可根据实际需要更改 typedef struct Sqlist ElemType Elem_ArrayMAX_SIZE;/线性表存储空间地址 int Length;/线性表长度 SqList; /* 1、初始化 构造一个空的线性表 */ Status Init_SqList(SqList *L) L-Length=0; return OK; /* 2、测长度 返回线性表中的元素个数 */ int Length_SqList(SqList *L) return L-Length; /* 3、取元素 用e返回L中第i个数据元素的值，1iListLength(L) */ Status Get_SqList(SqList *L,int i,ElemType *e) if(i=1)&(iLength) *e=L-Elem_Arrayi-1;/i位置对应的元素下标为i-1 return OK; else return ERROR; 云淡风清 /* 4、顺序线性表的插入 在线性表L中的第i个位置插入元素e，原来位置及以后的元素都后移。 要求1iListLength(L)+1，线性表未满。 实现步骤： (1)将线性表L中的第i个至第n个结点后移一个位置。 (2)将结点e插入到结点ai-1之后。 (3)线性表长度加1。 */ Status Insert_SqList(Sqlist *L,int i,ElemType e) int j; if(iL-Length+1)/位置错误 return ERROR; else if(L-Length=MAX_SIZE)/线性表上溢 /实际开发中达到空间上限时可用remalloc()函数重新分配空间，扩大空间容量 return ERROR; else /i-1位置以后的所有结点后移 for(j=L-Length-1;j=i-1;-j) L-Elem_Arrayj+1=L-Elem_Arrayj; L-Elem_Arrayi-1=e;/在i-1位置插入结点 L-Length+;/线性表长度增1 return OK; /* 时间复杂度分析： 在线性表L中的第i个位置插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。 设在线性表L中的第i个位置插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。 总的平均移动次数：Einsert=pi*(n-i+1) (1in) 计算得：Einsert=n/2。 即在顺序表上做插入运算，平均要移动表上一半结点，当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。 */ /* 5、线性表元素位置查询 返回元素e在L中的逻辑位置，不存在则返回0 云淡风清 */ int Locate_SqList(Sqlist *L,ElemType e) int i,found=0;/found用于表示是否找到，0：未找到 1：找到 i=0;/从第一个开始查询 while(iLength)&(found=0) if(L-Elem_Arrayi=e) found=1; else i+; if(found=1) return i+1;/返回逻辑位置编号 else return 0;/未找到，返回0 /* 6、删除指定位置元素 在线性表： L=(a1，ai-1，ai， ai+1，an) 中删除结点ai(1in)，使其成为线性表： L= (a1，ai-1，ai+1，an) 要求1iListLength(L)，线性表未空。 实现步骤： (1)将线性表L中的第i+1个至第n个结点依此向前移动一个位置。 (2)线性表长度减1。 */ Status Delete_SqList(Sqlist *L,int i) int k; if(L-Length=0)/线性表空 printf(线性表L为空!n); return ERROR; else if(iL-Length)/指定位置不合适 printf(要删除的数据元素不存在!n); return ERROR; else /i位置以后的所有结点前移 for(k=i;kLength;k+) L-Elem_Arrayk-1=L-Elem_Arrayk; 云淡风清 L-Length-;/线性表长度减1 return (OK); /* 时间复杂度分析： 删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。 设在线性表L中删除第i个元素的概率为Pi，不失一般性，设删除各个位置是等概率，则Pi=1/n，而删除时移动结点的次数为n-i。 则总的平均移动次数：Edelete=Pi*(n-i) (1in) 计算得：Edelete=(n-1)/2 即在顺序表上做删除运算，平均要移动表上一半结点，当表长n较大时，算法的效率相当低，因此算法的平均时间复杂度为O(n)。 */ /* 7、清空 */ Status Clear_SqList(Sqlist *L) L-Length=0; return OK; /* 8、遍历 以输出为例 */ Status Traverse_SqList(Sqlist *L) int i; printf(共有%d个元素，以下为具体内容：n,L-Length); for(i=0;iLength;i+) printf(%8d,L-Elem_Arrayi); printf(n-END-n); return OK; /* 9、修改 将线性表L中第i个位置的值置为e。要求线性表L已存在且1iListLength(L)。 */ Status Update_SqList(Sqlist *L,int i,ElemType e) if(iL-Length)/位置错误 云淡风清 return ERROR; else L-Elem_Arrayi-1=e;/放置新数据 return OK; /* 10、排序 按要求对线性表中元素排序。 */ Status Sort_SqList(Sqlist *L) int i,j; ElemType temp; for(i=1;iLength-1;i+) for(j=0;jLength-i-1;j+) if(L-Elem_ArrayjElem_Arrayj+1) temp=L-Elem_Arrayj; L-Elem_Arrayj=L-Elem_Arrayj+1; L-Elem_Arrayj+1=temp; return OK; /* 主函数 */ void main() int xz=1,i; SqList L; ElemType e; while(xz!=0) printf( 1、初始化n 2、测长度n 3、取元素n 4、插入n 5、查询n 6、删除n 7、清空n 8、遍历n 9、修改n 10、排序n 0、结束n请选择：); scanf(%d,&xz); switch(xz) case 1: if(Init_SqList(&L)=OK) 云淡风清 printf(初始化成功！n); else printf(初始化未成功！n); break; case 2: printf(线性表长度为：%dn,Length_SqList(&L); break; case 3: printf(请输入要取元素的位置：); scanf(%d,&i); if(Get_SqList(&L,i,&e)=OK) printf(指定位置上的元素为：%dn,e); else printf(Error！n); break; case 4: printf(请输入要插入的位置：); scanf(%d,&i); printf(请输入要插入的元素内容：n); scanf(%d,&e); if(Insert_SqList(&L,i,e)=OK) printf(插入成功n); else printf(Error！n); break; case 5: printf(请输入要查询的元素内容：); scanf(%d,&e); printf(此元素逻辑位置为：%d(0表示未找到)。n,Locate_SqList(&L,e); break; case 6: printf(请输入要删除元素的位置：