第一篇：数据结构讲稿
云淡风清 http://gsqls.blog.163.com/
第1章 数据结构概述
1.1概述
以下为某市部分院校的交通地图情况，要求找出从出发点到目的地之间的最短路径及其长度。
对于此问题，如果手工去做，速度慢(特别地，现实中实际地图信息要比此例复杂许多)，还容易出错，此时可借助于计算机完成。
计算机进行此类信息的处理时，涉及到两个问题：一是现实当中的信息在计算机中如何表示，二是如何对信息进行处理。
信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题不断复杂化，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。
1.1.1编写解决实际问题的程序的一般流程
如何通过编写程序，以比手工更为高效精确的方式解决实际问题呢？一般流程如下：
1、由具体问题抽象出一个适当的数学模型；
2、分析问题所涉及的数据量大小及数据之间的关系；
3、确定如何在计算机中存储数据及体现数据之间的关系？
4、确定处理问题时需要对数据作何种运算？
5、确定算法并编写程序；
5、分析所编写的程序的性能是否良好？若性能不够好则重复以上步骤。
云淡风清 http://gsqls.blog.163.com/ 上面所列举的问题基本上由数据结构这门课程来回答。
《数据结构》是计算机科学中的一门综合性专业基础课，是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。
1.1.2数据结构的例子
1、电话号码查询系统
设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。
姓名
电话号码
陈伟海 *** 李四锋 ***。。
这是一种典型的线性结构。
2、磁盘目录文件系统
磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推。
。。
本问题中各目录从上到小形成了一种一对多的关系，是一种典型的树形结构。
云淡风清 http://gsqls.blog.163.com/
3、交通网络图
下图表明了若干个城市之间的联系：
从图中可看出，一个地方到另外一个地方可以有多条路径，是一种典型的网状结构，数据与数据成多对多的关系。
4、排序问题
对100000个整数进行降序排序。冒泡法程序： #include
a[i]=rand();printf(“n按原序输出：n”);for(i=1;i<=N;i++)
printf(“%8d”,a[i]);system(“pause”);for(j=1;j for(i=N;i>j;i--) if(a[i]>a[i-1]) { a[0]=a[i]; a[i]=a[i-1]; a[i-1]=a[0]; } printf(“n按新次序输出：n”); 云淡风清 http://gsqls.blog.163.com/ for(i=1;i<=N;i++) printf(“%8d”,a[i]);printf(“n”);} 快速排序程序： #include void quick_sort(int a[N+1],int left,int right){ int j,last,temp;if(left { //将划分子集的元素(此处选中间元素)移动到最左边 temp=a[left]; a[left]=a[(left+right)/2]; a[(left+right)/2]=a[left]; last=left;//用last记录比关键字小的元素的最右位置 for(j=left+1;j<=right;j++)//划分子集 if(a[j]>a[left]) { temp=a[last]; a[last]=a[j]; a[j]=temp; last++; } //对形成的新子集递归进行快速排序 quick_sort(a,left,last-1); quick_sort(a,last+1,right);} } void main(){ int i;int a[N+1];srand(time(NULL));for(i=1;i<=N;i++) a[i]=rand();printf(“n按原序输出：n”);for(i=1;i<=N;i++) printf(“%8d”,a[i]);system(“pause”); 云淡风清 http://gsqls.blog.163.com/ quick_sort(a,1,N);printf(“n按新次序输出：n”);for(i=1;i<=N;i++) printf(“%8d”,a[i]);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数据的逻辑结构： 指对数据元素之间逻辑关系的描述。 数据元素之间的关系可以是一种或多种。 数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。其要点有两个方面：一是元素本身，二是元素之间的关系。数据元素之间的逻辑结构有四种基本类型，如下： 云淡风清 http://gsqls.blog.163.com/ ①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。②线性结构：结构中相邻的数据元素之间存在一对一的关系。③树型结构：结构中相邻的数据元素之间存在一对多的关系。 ④图状结构或网状结构：结构中相邻的数据元素之间存在多对多的关系。数据结构数学形式的定义是一个二元组： 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)。 存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。数据操作：对数据要进行的运算。 本课程中将要讨论的三种逻辑结构及其采用的存储结构如下图所示。 云淡风清 http://gsqls.blog.163.com/ 逻辑结构与所采用的存储结构 数据逻辑结构层次关系图 1.2.8数据类型(Data Type)： 指的是一个值的集合和定义在该值集上的一组操作的总称。 数据类型是和数据结构密切相关的一个概念。在C语言中数据类型有：基本类型(如int，float，double，char等)和构造类型(如数组，结构体，共用体等)。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。 1.3数据结构的运算 数据结构的主要运算包括： ⑴建立(Create)一个数据结构； ⑵消除(Destroy)一个数据结构； ⑶从一个数据结构中删除(Delete)一个数据元素； ⑷把一个数据元素插入(Insert)到一个数据结构中； ⑸对一个数据结构进行访问(Access)； ⑹对一个数据结构(中的数据元素)进行修改(Modify)； ⑺对一个数据结构进行排序(Sort)； ⑻对一个数据结构进行查找(Search)。 以上只列举了一些常见运算，实际应用当中可能会遇到许多其它运算。 云淡风清 http://gsqls.blog.163.com/ 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算法基本概念： 算法是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或 云淡风清 http://gsqls.blog.163.com/ 多个操作。 1.5.2算法的基本特征： 算法具有以下五个特性 ①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ②确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 ③可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。 ④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 ⑤输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 1.5.3算法的基本描述方法： 一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述等。 1.5.4算法与程序的异同比较： 算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。 1.5.5评价算法好坏的几个标准： 评价一个好的算法有以下几个标准 ①正确性(Correctness)：算法应满足具体问题的需求。 ②可读性(Readability)：算法应易于供人阅读和交流。可读性好的算法有助于对算法的理解和修改。 ③健壮性(Robustness)：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。 ④通用性(Generality)：算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。⑤效率与存储容量需求：效率指的是算法执行的时间；存储容量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。 1.6算法效率的度量 解决同一个问题的算法可能有多种，如何选择一个效率高的算法呢？应该来讲，与算法效率相关的因素有很多，如下： 云淡风清 http://gsqls.blog.163.com/ 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，对于任意n≥n0，都有T(n)≤c×f(n)，则称该算法的渐进时间复杂度为T(n)=O(f(n))。 一般地，常用最内层循环内的语句中的原操作的执行频度(重复执行的次数)来表示时间复杂度。 2、时间复杂度分析举例： 例：两个n阶方阵的乘法。 云淡风清 http://gsqls.blog.163.com/ for(i=1;i<=n;++i)for(j=1;j<=n;++j){ c[i][j]=0; for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j];} 分析：由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=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<=n;++i){ ++x;s+=x;} 分析：基本语句的语句频度为：n，其时间复杂度为：O(n)，即为线性阶。例：以下程序段： for(i=1;i<=n;++i)for(j=1;j<=n;++j){ ++x; s+=x;} 分析：基本语句的语句频度为：n2，其时间复杂度为：O(n2)，即为平方阶。 定理：若T(n)=amnm+am-1nm-1+„+a1n+a0是一个m次多项式，则T(n)=O(nm)，即复杂度表达式只取一个n趋向于无穷大时的同阶无穷小表达式即可。 通过对算法复杂度的分析，总结出这样一条结论，在计算任何算法的复杂度时，可以忽略所有低次幂和最高次幂的系数，这样可以简化算法分析，并使注意力集中在增长率上。 从本质上来讲，此种策略也就是只考虑对算法复杂度影响最大的因素而忽略次要因素。例：以下程序段： for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) { ++x; a[i,j]=x; } 云淡风清 http://gsqls.blog.163.com/ 分析：基本语句的语句频度为： 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(n㏒n)：线性对数时间阶 O(nk)：k≥2，k次方时间阶 4、常见时间复杂度大小关系分析： 以下六种计算算法时间复杂度的多项式是最常用的，其大小关系通常为： O(1) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。 有的情况下，算法中基本操作重复执行的次数还随输入数据集的不同而不同。例：素数的判断算法。 void prime(int n)//n是一个正整数 { int i=2;while((n%i)!=0 && i*1.0 i++;if(i*1.0>sqrt(n)) printf(“&d 是一个素数n”,n);else printf(“&d 不是一个素数n”,n);} 此例中执行频率最高的语句为i++;，此语句最少执行0次，最多执行sqrt(n)次，对于不同的n，执行次数不确定。 对于此类算法，如果输入数据不同，则算法运行时间也不同，因此要全面分析一个算法，需要考虑算法在最好、最坏、平均情况下的时间消耗。由于最好情况出现的概率太小，因此不具代表性，但是，当最好情况出现的概率大时，应该分析最好情况；虽然最坏情况出现的概率也太小，不具代表性，但是分析最坏情况能够让人们知道算法的运行时间最坏能到什么程度，这一点在实时系统中很重要；分析平均情况是比较普遍的，特别是同一个算法要处理不同的输入时，通常假定输入的数据是等概率分布的。 例：冒泡排序法。 void bubble_sort(int a[],int n) 云淡风清 http://gsqls.blog.163.com/ { int temp;change=false;for(i=n-1;change=TURE;i>1 && change;--i) for(j=0;j if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+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为问题的规模(或大小)。该存储空间一般包括三个方面： 指令常数变量所占用的存储空间； 输入数据所占用的存储空间； 辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。如： 一维数组a[n]：空间复杂度O(n)二维数组a[n][m]：空间复杂度O(n*m)例：数组a中有10000个数，要求将所有数据逆置(即顺序倒过来存放)。为达到逆置目的，有以下两种方案： 方案一： int a[10000],b[10000],i;for(i=0;i<10000;i++)b[10000-i-1]=a[i];for(i=0;i<10000;i++)a[i]=a[b];方案二： int a[10000],t,i;for(i=0;i<10000/2;i++) 云淡风清 http://gsqls.blog.163.com/ { t=a[i];a[i]=a[10000-i-1];a[10000-i-1]=t;} 很明显，方案二中的辅助空间数量为1，而方案一中的辅助空间数量为10000，方案二的空间复杂度优于方案一。 在算法的时间复杂度和空间复杂度中，我们更注重算法的时间性能。因此，在对算法性能的分析当中，通常均主要针对算法时间性能进行分析。 1.6.5学习算法的原因 讲述了这么多关于算法的基础知识，究竟为什么要学习算法呢？ 首先，算法无处不在。算法不仅出现在数学和计算机程序中，更普遍地出现在我们的生活中，在生活中做什么事情都要有一定的顺序，然而不同的顺序带来的效率和成果可能都会不同，只有学好了算法，才能让生活更有趣、更有效率。 其次，算法是程序的灵魂。学习计算机编程，必须要掌握好其灵魂，否则，写出来的程序就像是没有灵魂的躯体。 再次，算法是一种思想。掌握了这种思想，能够拓展思维，使思维变得清晰、更具逻辑性，在生活以及编程上的很多问题，也就更易解决。 最后，算法的乐趣。学习算法不仅仅是为了让它帮助人们更有效地解决各种问题，算法本身的趣味性很强，当通过烦琐的方法解决了一个问题后会感觉到有些疲惫，但是面对同一个问题，如若学会使用算法，更简单有效地解决了这个问题，会发现很有成就感，算法的速度、思想会让人觉得很奇妙。每一个奇妙的算法都是智慧的结晶。 学习算法的理由成千上万，不同的人可能出于不同的目的去学习算法，希望大家能够通过对课程的学习对算法有进一步的理解。 习题一 1、简要回答术语：数据，数据元素，数据结构，数据类型。 2、数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？ 3、数据结构的主要运算包括哪些？ 4、算法分析的目的是什么？算法分析的主要方面是什么？ 云淡风清 http://gsqls.blog.163.com/ 第2章 线性表 下表为某电台提供给听众的若干首英文歌曲名及相关点播情况统计信息： 由于实际的歌曲库可能很大，手工管理效率低，不方便，现请设计一个软件系统实现对此类歌曲库的管理。 分析： 此例中相邻的两首歌之间是一种一对一的关系，属于典型的线性结构，可按线性结构进行组织及管理。 2.1线性结构与线性表 2.1.1线性结构 如果一个数据元素序列满足： ⑴除第一个和最后一个数据元素外，每个数据元素只有一个直接前驱数据元素和一个直接后继数据元素； ⑵第一个数据元素没有前驱数据元素； ⑶最后一个数据元素没有后继数据元素。则称这样的数据结构为线性结构。 线性表、栈、队列、串和数组都属于线性结构。如下图： 云淡风清 http://gsqls.blog.163.com/ 2.1.2线性表 线性表(Linear List)是一种最简单、最常用的线性结构，是一种可以在任意位置进行插入和删除数据元素操作的、由n(n≥0)个相同类型数据元素a1，a2，„，an组成的线性结构。在这种结构中： ⑴存在一个唯一的被称为“第一个”的数据元素； ⑵存在一个唯一的被称为“最后一个”的数据元素； ⑶除第一个元素外，每个元素均有唯一一个直接前驱； ⑷除最后一个元素外，每个元素均有唯一一个直接后继。线性表中的数据元素的个数n称为线性表的长度。当n=0时，称为空表。空线性表用符号()表示。 当n>0时，将非空的线性表记作：(a1，a2，„an)，其中符号ai(1≤i≤n)表示第i个抽象数据元素。 a1称为线性表的第一个(头)结点，an称为线性表的最后一个(尾)结点。a1，a2，„ai-1都是ai(2≤i≤n)的前驱，其中ai-1是ai的直接前驱； ai+1，ai+2，„an都是ai(1≤i ≤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：某校2001级同学的基本情况：{(‘2001414101’，‘张里户’，‘男’，06/24/1983)，(‘2001414102’，‘张化司’，‘男’，08/12/1984)„，(‘2001414102’，‘李利辣’，‘女’，08/12/1984)} ◆若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。◆线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。 ◆对线性表的基本操作如下(实际应用中要根据需要选择相应操作或者添加未列出的操作)： ⑴建立空表L ⑵返回表L的长度，即表中元素个数 ⑶取线性表L中位置i处的元素(1≤i≤n)⑷取i的直接前驱元素 ⑸取i的直接后继元素 ⑹查询元素x在L中的逻辑位置 ⑺在线性表L的位置i处插入元素x，原位置元素后移一个位置 ⑻从线性表L中删除位置i处的元素 ⑼判断线性表是否为空 ⑽清空已存在的线性表 ⑾遍历所有元素 云淡风清 http://gsqls.blog.163.com/ ⑿根据所给关键字查询元素并返回其详细信息 ⒀修改表中元素 ⒁对所有元素按条件排序 2.1.3线性表的抽象数据类型定义 ADT List { 数据对象：D = { ai | ai∈ElemSet, i=1,2,„,n, n≥0 } 数据关系：R = { 操作结果：构造一个空的线性表L； ListLength(L)初始条件：线性表L已存在； 操作结果：返回线性表中的元素个数； GetElem(L,i,e)初始条件：线性表L已存在，1≤i≤ListLength(L)； 操作结果：用e返回L中第i个数据元素的值； ListInsert(L,i,e)初始条件：线性表L已存在，1≤i≤ListLength(L)+1，线性表未满； 操作结果：在线性表L中的第i个位置插入元素e，原来位置及以后的元素都后移； ListLocate(L,e)初始条件：线性表L已存在； 操作结果：返回元素e在L中的逻辑位置，不存在则返回0； ListDelete(L,i)初始条件：线性表L已存在，1≤i≤ListLength(L)； 操作结果：从表L中删除位置i处的元素； ListClear(L)初始条件：线性表L已存在； 操作结果：清空已存在的表； ListTraverse(L)初始条件：线性表L已存在； 操作结果：遍历输出所有元素； ListUpdate(L,i,e)初始条件：线性表L已存在,1≤i≤ListLength(L)； 操作结果：将线性表L中第i个位置的值置为e； ListSort(L)初始条件：线性表L已存在； 操作结果：按一定条件对所有元素重新排序； ListDestroy(L)初始条件：线性表L已存在； 操作结果：释放线性表空间； … 云淡风清 http://gsqls.blog.163.com/ } 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 -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 云淡风清 http://gsqls.blog.163.com/ #include -1 #define MAX_SIZE 100 //最大长度 typedef int Status;//状态 typedef int ElemType;//元素类型，可根据实际需要更改 typedef struct Sqlist { ElemType Elem_Array[MAX_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个数据元素的值，1≤i≤ListLength(L)*/ Status Get_SqList(SqList *L,int i,ElemType *e){ if((i>=1)&&(i<=L->Length)){ *e=L->Elem_Array[i-1];//i位置对应的元素下标为i-1 return OK;} else return ERROR;} 云淡风清 http://gsqls.blog.163.com/ /* 4、顺序线性表的插入 在线性表L中的第i个位置插入元素e，原来位置及以后的元素都后移。要求1≤i≤ListLength(L)+1，线性表未满。实现步骤： (1)将线性表L中的第i个至第n个结点后移一个位置。(2)将结点e插入到结点ai-1之后。 (3)线性表长度加1。*/ Status Insert_SqList(Sqlist *L,int i,ElemType e){ int j;if((i<1)||(i>L->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_Array[j+1]=L->Elem_Array[j]; L->Elem_Array[i-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)(1≤i≤n)计算得：Einsert=n/2。 即在顺序表上做插入运算，平均要移动表上一半结点，当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。 */ /* 5、线性表元素位置查询 返回元素e在L中的逻辑位置，不存在则返回0 云淡风清 http://gsqls.blog.163.com/ */ int Locate_SqList(Sqlist *L,ElemType e){ int i,found=0;//found用于表示是否找到，0：未找到 1：找到 i=0;//从第一个开始查询 while((i if(L->Elem_Array[i]==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(1≦i≦n)，使其成为线性表： L=(a1，„ai-1，ai+1，„，an)要求1≤i≤ListLength(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(i<1||i>L->Length)//指定位置不合适 { printf(“要删除的数据元素不存在!n”); return ERROR; } else { //i位置以后的所有结点前移 for(k=i;k L->Elem_Array[k-1]=L->Elem_Array[k]; 云淡风清 http://gsqls.blog.163.com/ L->Length--;//线性表长度减1 return(OK); } } /* 时间复杂度分析： 删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。 设在线性表L中删除第i个元素的概率为Pi，不失一般性，设删除各个位置是等概率，则Pi=1/n，而删除时移动结点的次数为n-i。 则总的平均移动次数：Edelete=∑Pi*(n-i) (1≤i≤n)计算得：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;i printf(“%8d”,L->Elem_Array[i]);printf(“n------------------END------------------n”);return OK;} /* 9、修改 将线性表L中第i个位置的值置为e。要求线性表L已存在且1≤i≤ListLength(L)。*/ Status Update_SqList(Sqlist *L,int i,ElemType e){ if((i<1)||(i>L->Length))//位置错误 云淡风清 http://gsqls.blog.163.com/ return ERROR;else { L->Elem_Array[i-1]=e;//放置新数据 return OK;} } /* 10、排序 按要求对线性表中元素排序。*/ Status Sort_SqList(Sqlist *L){ int i,j;ElemType temp;for(i=1;i<=L->Length-1;i++) for(j=0;j<=L->Length-i-1;j++) { if(L->Elem_Array[j] { temp=L->Elem_Array[j]; L->Elem_Array[j]=L->Elem_Array[j+1]; L->Elem_Array[j+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、修改n10、排序n 0、结束n请选择：”); scanf(“%d”,&xz); switch(xz) { case 1: if(Init_SqList(&L)==OK) 云淡风清 http://gsqls.blog.163.com/ 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(“请输入要删除元素的位置：”);scanf(“%d”,&i);if(Delete_SqList(&L,i)==OK) printf(“删除成功n”);else printf(“Error！n”);break;case 7: Clear_SqList(&L);break;case 8: Traverse_SqList(&L);break; 云淡风清 http://gsqls.blog.163.com/ case 9: printf(“请输入要修改的元素位置：”); scanf(“%d”,&i); printf(“请输入元素的新内容：n”); scanf(“%d”,&e); if(Update_SqList(&L,i,e)==OK) printf(“修改成功n”); else printf(“Error！n”); break; case 10: Sort_SqList(&L); printf(“排序完成！n”); break; case 0: printf(“谢谢使用，再见！n”); break; default: printf(“输入错误！n”); break; } } } 需要说明的是，本例没有实现空间的动态分配，若要实现动态分配，可参照第三章“栈的动态顺序存储结构”的做法。 2.2.3顺序存储线性表的特点 优点：表中任意一个结点的存取很方便，可以进行随机存取，处于不同位置上的结点的存取时间从理论上来说相同，也能进行插入和删除操作。 缺点： (1)插入和删除不方便。为保持连续存放，操作中需要移动大量元素。 (2)会造成空间的浪费以及不易扩充。所占空间通常情况下大小固定，处理长度变化较大的线性表时，分配空间大小不够，会造成溢出；分配空间太大，会造成浪费。 2.3线性表的链式存储 2.3.1线性表的链式存储结构 链式存储：用一组任意(即不必要连续)的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。 链表中结点所占用的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的，链表中结点的逻辑顺序和物理顺序不一定相同。 为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的 云淡风清 http://gsqls.blog.163.com/ 地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了链表中的结点结构，如下图所示。 data：数据域，存放结点的值。 next：指针域，存放结点的直接后继的地址。 链表通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起。每一个结点只包含一个指针域的链表，称为单链表。 为操作方便，总是在链表的第一个结点之前附设一个头指针变量head指向第一个结点。头结点的数据域可以不存储任何信息(或存放链表长度等辅助信息)，此时通常称为带头结点的单链表。当然，也可以让头结点的数据域存放有效数据，此时称为不带头结点的单链表。相对而言，带头结点的单链表浪费了一个结点的数据域，但会给编程带来一定方便。 带头结点的单链表其基本结构如下： 说明： (1)整个链表由若干个结点组成，一个结点占用一个内存块，而每个结点又分为两大部分：数据域和指针域，其中数据域存放用户数据，指针域用于存放后一个结点的地址，通过指针域将逻辑上前后相邻的结点连接起来，这样，通过前一个结点指针域中存放的地址就可以找到后一个结点。可看出，每个结点的指针域实际上充当了指针变量的角色，只要结点数可变，则意味着指针变量数也可变，而事实上结点所对应的这些内存块完全可以多次动态分配，这也就意味着指针域(相当于指针变量)的个数可以根据需要动态调整，这就解决了前述的“程序中变量个数固定，但问题本身所需变量个数不定”的矛盾。 (2)设置一个头指针变量指向首结点，在带头结点的单链表中，此结点不存放有效数据。(3)末尾结点的指针域设置为空“NULL”表示链表的结束，相当于字符串中的' '。 (4)在没有用户数据的情况下，此链表只有一个结点，此结点既是首结点，又是末结点，结点的指针域为“NULL”，此时表示链表为逻辑“空”，也就是说，链表的初始状态应该如下图所示。 单链表是由表头唯一确定的，因此单链表可以用头指针的名字来命名。例 1、线性表L=(bat，cat，eat，fat，hat)其带头结点的单链表的逻辑状态和物理存储方式如下图所示。 云淡风清 http://gsqls.blog.163.com/ 1、结点的描述与实现 C语言中用带指针的结构体类型来描述 typedef int ElemType;typedef struct Lnode { ElemType data;//数据域，保存结点的值 struct Lnode *next;//指针域，保存后继结点地址 }LNode; //结点的类型 2、结点空间分配及回收的实现 结点存储空间是通过动态内存分配和释放来实现的，即需要时分配，不需要时释放。在C语言中可通过标准函数：malloc()，realloc()，sizeof()，free()等来实现分配。 动态分配：p=(LNode*)malloc(sizeof(LNode));函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。动态释放：free(p);系统回收由指针变量p所指向的内存区。p必须是最近一次调用malloc()函数时的返回值。动态重新分配：p=(LNode*)realloc(p,newsize);先判断当前的指针是否有足够的连续空间，如果有，扩大p指向的地址，并且将p返回，如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来p所指内存区域，同时返回新分配的内存区域的首地址，即重新分配存储器块的地址。返回值：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。 3、最常用的基本操作 ⑴ 结点的赋值 LNode *p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;讲课时板书教案上的几种常见的指针操作。效果如下图。 ⑵常见的指针操作 ①q=p; 云淡风清 http://gsqls.blog.163.com/ ②q=p->next; ③p=p->next; ④q->next=p; ⑤q->next=p->next; 云淡风清 http://gsqls.blog.163.com/ 2.3.2单链式的基本操作 以带头结点的单链表为例。#define OK #define ERROR -1 typedef int Status;//状态 #include “stdlib.h” #include “stdio.h” typedef int ElemType;typedef struct Lnode { ElemType data;//数据域，保存结点的值 struct Lnode *next;//指针域，保存后继结点地址 }LNode; //结点的类型 /* 1、链表初始化(建立空链表)*/ LNode * Init_LinkList(void){ LNode *L;L=(LNode *)malloc(sizeof(LNode));//给头结点分配空间 if(L!=NULL) L->next=NULL;//指针域置为空以作为结束标记 return L;} /* 2、头插入法建表 从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止，每次插入的结点都作为链表的第一个数据结点。 */ 云淡风清 http://gsqls.blog.163.com/ Status Create1_LinkList(LNode *L){ ElemType data;char sfjx=1;//0：结束 1：继续 LNode *p;while(sfjx!=0){ p=(LNode *)malloc(sizeof(LNode));//给新结点分配空间 if(p==NULL) return ERROR;//空间分配不成功 else { printf(“请输入元素内容：”); scanf(“%d”,&data);//读入值 p->data=data;//数据域赋值 //钩链，新创建的结点总是作为第一个数据结点 p->next=L->next; L->next=p; } printf(“是否继续(0：结束 1：继续)：”); scanf(“%d”,&sfjx);} return OK;} /* 3、尾插入法建表 头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。 该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。*/ Status Create2_LinkList(LNode *L){ ElemType data;char sfjx=1;//0：结束 1：继续 LNode *p,*q;//找到已有链表的末结点 q=L;while(q->next!=NULL) q=q->next;while(sfjx!=0){ p=(LNode *)malloc(sizeof(LNode));//给新结点分配空间 if(p==NULL) 云淡风清 http://gsqls.blog.163.com/ return ERROR;//空间分配不成功 else { printf(“请输入元素内容：”); scanf(“%d”,&data);//读入值 p->data=data;//数据域赋值 //钩链，新创建的结点总是作为最后一个结点 q->next=p; q=p;//q重新指向末结点 } printf(“是否继续(0：结束 1：继续)：”); scanf(“%d”,&sfjx);} q->next=NULL;//重设链表结束标记 return(OK);} /* 4、按序号查找，取单链表中的第i个元素。 对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。*/ Status Get_LinkList(LNode *L,int i,ElemType *e){ int j=1;LNode *p;p=L->next;//使p指向第一个结点 while((p!=NULL)&&(j p=p->next;//移动指针p j++; //j计数 } if(p==NULL)//找不到 return(ERROR);else { *e=p->data; return(OK);} } /* 云淡风清 http://gsqls.blog.163.com/ 5、按值查找 按值查找是在链表中，查找是否有结点值等于给定值key的结点? 若有，则返回首次找到的值为key的结点的存储位置；否则返回NULL。 */ LNode *Locate_LinkList(LNode *L,ElemType key){ LNode *p;p=L->next;while((p!=NULL)&&(p->data!=key)) p=p->next;if(p!=NULL)//找到了 return p;else//找不到 return(NULL);} /* 6、单链表的插入，插入到指定位置 在以L为头结点的单链表的第i个位置插入值为e的结点。 插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1所在的结点p，然后生成一个数据域为e的新结点q，q结点作为p的直接后继结点。 */ Status Insert_LinkList(LNode *L,int i,ElemType e){ int j=0;LNode *p,*q;p=L;//找待插入位置的前一个结点位置 while((p!=NULL)&&(j p=p->next; j++;} if((j!=i-1)||(p==NULL))//位置不合适 { printf(“位置不合适，无法插入！n”); return ERROR;} else { q=(LNode *)malloc(sizeof(LNode));//给新结点分配空间 if(q==NULL) return ERROR; else 云淡风清 http://gsqls.blog.163.com/ { //实现插入 q->data=e; q->next=p->next; p->next=q; return OK; } } } /* 7、按序号删除 删除单链表中的第i个结点。 为了删除第i个结点ai，必须找到结点的存储地址。该存储地址是在其直接前趋结点ai-1的next域中，因此，必须首先找到ai-1的存储位置p，然后令p->next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。设单链表长度为n，则删去第i个结点仅当1≤i≤n时是合法的。则当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是p->next!=NULL。显然此算法的时间复杂度也是O(n)。 */ Status Delete1_LinkList(LNode *L,int i){ int j=1;LNode *p,*q;p=L;q=L->next;//找待删除位置的前一个结点位置 while(q!=NULL && j p=q; q=q->next; j++;} if((q==NULL)||(i<=0)){ printf(“位置不合适，无法删除！n ”); return ERROR;} else { //实现删除 p->next=q->next; free(q); return OK;} } 云淡风清 http://gsqls.blog.163.com/ /* 8、按值删除 删除单链表中值为key的第一个结点。 与按值查找相类似，首先要查找值为key的结点是否存在? 若存在，则删除；否则返回NULL。*/ Status Delete2_LinkList(LNode *L,int key){ LNode *p=L,*q=L->next;//找待删除结点位置，q指向其位置，p指向其前驱结点 while(q!=NULL && q->data!=key){ p=q; q=q->next;} if(q!=NULL)//找到了 { //实现删除 p->next=q->next; free(q); return OK;} else { printf(“所要删除的结点不存在！n”); return ERROR;} } /* 9、删除单链表中值为key的所有结点 与按值查找相类似，但比前面的算法更简单。 基本思想：从单链表的第一个结点开始，对每个结点进行检查，若结点的值为key，则删除之，然后检查下一个结点，直到所有的结点都检查。 */ void Delete3_LinkList(LNode *L,int key){ LNode *p=L,*q=L->next;//p始终指向q的前驱，以方便删除操作的实现 while(q!=NULL){ if(q->data==key) { p->next=q->next; 云淡风清 http://gsqls.blog.163.com/ free(q); q=p->next; } else { p=q; q=q->next; } } } /* 10、删除单链表中所有值重复的结点，使得所有结点的值都不相同 与按值查找相类似，但比前面的算法更复杂。 基本思想：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都检查。 */ void Delete4_LinkList(LNode *L){ LNode *p=L->next,*q,*ptr;while(p!=NULL)//检查链表中所有结点 { q=p; ptr=p->next; while(ptr!=NULL)//检查结点p的所有后继结点ptr { if(ptr->data==p->data) { q->next=ptr->next; free(ptr); ptr=q->next; } else { q=ptr; ptr=ptr->next; } } p=p->next;} } /* 云淡风清 http://gsqls.blog.163.com/ 11、修改指定位置的数据 */ Status Modify_LinkList(LNode *L,int i,ElemType e){ int j=1;LNode *p;p=L->next;//找待修改结点位置 while(p!=NULL && j p=p->next; j++;} if((p==NULL)||(i<=0))//找不到 { printf(“位置不合适，无法修改！n ”); return ERROR;} else { p->data=e; return OK;} } /* 12、单链表遍历 以输出为例 */ void Traverse_LinkList(LNode *L){ LNode *p;p=L->next;while(p!=NULL){ printf(“%8d”,p->data); p=p->next;} printf(“n”);} /* 13、单链表的合并 设有两个有序的单链表，它们的头指针分别是La、Lb，将它们合并为以Lc为头指针的有序链表。算法说明：算法中pa，pb分别是待考察的两个链表的当前结点，pc是合并过程中合并的链表的最后一个结点。 云淡风清 http://gsqls.blog.163.com/ 合并了值为-7，-2的结点后示意图如下图所示。 */ LNode *Merge_LinkList(LNode *La,LNode *Lb){ LNode *Lc,*pa,*pb,*pc,*ptr;Lc=La;pc=La;//指向新链表的末结点 pa=La->next;pb=Lb->next;while(pa!=NULL && pb!=NULL){ if(pa->data data)//将pa所指的结点合并，pa指向下一个结点 { pc->next=pa; pc=pa; pa=pa->next; } else if(pa->data>pb->data)//将pb所指的结点合并，pb指向下一个结点 { pc->next=pb; pc=pb; pb=pb->next; 云淡风清 http://gsqls.blog.163.com/ } else//将pa所指的结点合并，pb所指结点删除 { pc->next=pa; pc=pa; pa=pa->next; ptr=pb; pb=pb->next; free(ptr); } } //将剩余的结点链上 if(pa!=NULL) pc->next=pa;else pc->next=pb; free(Lb);return(Lc);} /* 14、单链表的排序 采用插入排序方法，以升序为例 */ void Sort_LinkList(LNode *L){ LNode *p,*q,*r,*s;p=L->next;L->next=NULL;while(p!=NULL){ q=L->next; r=L; while((q!=NULL)&&(p->data>q->data)) { q=q->next; r=r->next; } s=p->next; r->next=p; p->next=q; p=s;} } 云淡风清 http://gsqls.blog.163.com/ /* 15、单链表的释放 */ void Release_LinkList(LNode *L){ LNode *p,*q;p=L;//指向头结点，从此结点开始释放 while(p!=NULL){ q=p->next; free(p); p=q;} } void main(){ int xz=1,i;LNode *L,*L1,*L2;ElemType e;while(xz!=0){ printf(“ 1、链表初始化n 2、头插入法建表n 3、尾插入法建表n 4、按序号查找n 5、按值查找n 6、单链表的插入n”); printf(“ 7、按序号删除n 8、按值删除n 9、删除单链表中指定值的所有结点n10、删除单链表中所有值重复的结点n”); printf(“ 11、修改指定位置的数据n12、单链表遍历n13、单链表的合并n14、单链表的排序n15、单链表的释放n 0、结束n请选择：”); scanf(“%d”,&xz); switch(xz) { case 1: L=Init_LinkList(); if(L!=NULL) printf(“初始化成功！n”); break; case 2: if(Create1_LinkList(L)==OK) printf(“建立成功！n”); else printf(“建立不成功！n”); break; case 3: if(Create2_LinkList(L)==OK) printf(“建立成功！n”); 云淡风清 http://gsqls.blog.163.com/ else printf(“建立不成功！n”);break;case 4: printf(“请输入要查找元素的序号：”);scanf(“%d”,&i);if(Get_LinkList(L,i,&e)==OK) printf(“%dn”,e);else printf(“找不到！n”);break;case 5: printf(“请输入要查找元素的关键字：”);scanf(“%d”,&e);L1=Locate_LinkList(L,e);if(L1!=NULL) printf(“%dn”,L1->data);else printf(“找不到！n”);break;case 6: printf(“请输入要插入元素的内容：”);scanf(“%d”,&e);printf(“请输入插入位置：”);scanf(“%d”,&i);if(Insert_LinkList(L,i,e)==OK) printf(“插入成功！n”);else printf(“插入不成功！n”);break;case 7: printf(“请输入要删除元素的位置：”);scanf(“%d”,&i);if(Delete1_LinkList(L,i)==OK) printf(“成功删除！n”);else printf(“未成功删除！n”);break;case 8: printf(“请输入要元素的内容：”);scanf(“%d”,&e);if(Delete2_LinkList(L,e)==OK) printf(“成功删除！n”);else 云淡风清 http://gsqls.blog.163.com/ printf(“未成功删除！n”);break;case 9: printf(“请输入要元素的内容：”);scanf(“%d”,&e);Delete3_LinkList(L,e);printf(“成功删除！n”);break;case 10: Delete4_LinkList(L);printf(“成功删除！n”); break;case 11: printf(“请输入修改位置：”);scanf(“%d”,&i);printf(“请输入元素的新内容：”);scanf(“%d”,&e);if(Modify_LinkList(L,i,e)==OK) printf(“修改成功！n”);else printf(“修改不成功！n”);break;case 12: Traverse_LinkList(L); break;case 13: L1=Init_LinkList();L2=Init_LinkList();if((L1==NULL)||(L2==NULL)) printf(“初始化不成功！n”);else { printf(“请建立第一个链表：n”); Create2_LinkList(L1); printf(“请建立第二个链表：n”); Create2_LinkList(L2); Sort_LinkList(L1); Sort_LinkList(L2); L=Merge_LinkList(L1,L2); printf(“合并后的结果如下：n”); Traverse_LinkList(L);} break;case 14: 云淡风清 http://gsqls.blog.163.com/ } } Sort_LinkList(L);break;case 15: Release_LinkList(L); break;case 0: printf(“谢谢使用，再见！n”);break;default: printf(“输入错误！n”);break;} 2.4循环链表 循环链表(Circular Linked List)：是一种头尾相接的链表，其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环，这样，从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。 下图是带头结点的单循环链表的示意图。 循环链表的操作： 对于带头结点的单循环链表，除链表的合并外，其它操作和单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上做以下简单修改： 1、判断是否是空链表 head->next==head; 2、判断是否是表尾结点 p->next==head;例：有m个人围成一圈，顺序排号。从第一个人开始报数，凡报到3的人退出圈子，问最后留下的那位是原来的第几号？ 根据问题描述可知，该问题中m个人围坐在一起形成首尾相接的环，比较自然的一种思路是用循环链表模拟这个环。从第3个人开始出圈，相当于从链表中删除一个结点。该程序主要由三个模块组成： 1、建立循环单链表存放初始各人编号； 2、报数并按顺序输出出圈人的编号； 3、输出剩下的人的编号。具体步骤如下： 云淡风清 http://gsqls.blog.163.com/ 第一步：输入人员总数； 第二步：创建循环链表并向单链表中填入人员编号； 第三步：找第一个开始报数的人； 第四步：数到3让此人出圈(删除对应结点)； 第五步：接着开始报数，重复第四步，直到圈中剩余一个为止； 第六步：输出剩下结点中的编号，即为最终所要求的编号。程序源代码： #include “stdio.h” #include “stdlib.h” #define MAXN 100 //最大个数 struct Node { int data;struct Node *next;};void main(){ struct Node *head, *s, *q, *t;int n, m, count=0, i;do//输入总个数 { printf(“请输入总个数(1－%d)：”,MAXN);scanf(“%d”,&m);}while((m<1)||(m>MAXN));do//输入出圈时要数到的个数 { printf(“要数到的个数(1--%d)：”,m);scanf(“%d”,&n);}while((n<1)||(n>m));for(i=0;i { s=(struct Node *)malloc(sizeof(struct Node));s->data=i+1;s->next=NULL;if(i==0){ head=s;q=head;} else { q->next=s;q=q->next;} 云淡风清 http://gsqls.blog.163.com/ } q->next=head;//形成圈 //以下代码输出原始状态 printf(“原始状态：n”);q=head;while(q->next!=head){ printf(“%4d”,q->data);q=q->next;} printf(“%4dn”,q->data);q=head;//以下代码实现出圈 printf(“出圈顺序：n”);do { count++;if(count==n-1){ t=q->next;q->next=t->next;count=0;printf(“%4d”,t->data);free(t);} q=q->next;}while(q->next!=q);printf(“n剩下的是%4dn”,q->data);} 注意：此程序采用的是不带头结点的单链表，以免在循环链表中由于不存放有效数据的头结点的存在而影响计数。 2.5双向链表 双向链表是为了克服单链表的单向性的缺陷而引入的。单链表只能从头到尾单向访问各结点，对操作的限制极大。双向链表(Double Linked List)指构成链表的每个结点中设立两个指针域，一个指向其直接前趋结点，一个指向其直接后继结点，这样形成的链表中有两个方向不同的链，故称为双向链表。 和单链表类似，双向链表一般也增加一个不存放实际有效数据的头结点，从而使某些操作更方便。下面为带头结点的双向链表示意图： 云淡风清 http://gsqls.blog.163.com/ 将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。 2.5.1双向链表的结点及其类型定义 双向链表的结点的类型定义如下。typedef struct Dulnode { ElemType data;struct Dulnode *prior,*next;}DulNode;双向链表结构具有对称性，设p指向双向链表中的某一结点，则其对称性可用下式描述：(p->prior)->next=p=(p->next)->prior;结点p的存储位置存放在其直接前趋结点p->prior的直接后继指针域中，同时也存放在其直接后继结点p->next的直接前趋指针域中。 2.5.2双向链表的基本操作 1、双向链表结点的插入 将值为e的结点插入双向链表中。插入前后链表的变化如下图所示。 ①若插入时仅仅指出直接前驱结点，钩链时必须注意先后次序是：“先右后左”，部分语句组如下： S=(DulNode *)malloc(sizeof(DulNode));S->data=e;S->next=p->next;//先右 p->next->prior=S;//后左 p->next=S;//先右 S->prior=p;//后左 ②若插入时同时指出直接前驱结点p和直接后继结点q，钩链时无须注意先后次序，部分语句组如下： S=(DulNode *)malloc(sizeof(DulNode));S->data=e;p->next=S;S->next=q;S->prior=p;q->prior=S; 2、双向链表结点的删除 设要删除的结点为p，删除时可以不引入新的辅助指针变量，先直接断链，再释放结点。部分语句组如下： p->prior->next=p->next;p->next->prior=p->prior;free(p); 云淡风清 http://gsqls.blog.163.com/ 注意： 与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向。 2.6一元多项式的表示和相加 2.6.1一元多项式的表示 一元多项式如下： p(x)=p0+p1x+p2x2+ „ +pnxn，由n+1个系数唯一确定。则在计算机中可用线性表(p0，p1，p2，„，pn)表示。既然是线性表，就可以用顺序表和链表来实现。两种不同实现方式的元素类型定义如下： 1、顺序存储结构表示的类型 typedef struct { float coef; //系数部分 int expn;//指数部分 } ElemType; 2、链式存储结构表示的类型 typedef struct ploy { float coef; //系数部分 int expn; //指数部分 struct ploy *next;}Ploy;2.6.2一元多项式的相加 不失一般性，设有两个一元多项式： P(x)=p0+p1x+p2x2+ „ +pnxn，Q(x)=q0+q1x+q2x2+ … +qmxm (m 1、顺序存储表示的相加 线性表的定义： typedef struct { ElemType a[MAX_SIZE];int length;}Sqlist;用顺序表示的相加非常简单，访问第i项可直接访问：L.a[i-1].coef，L.a[i-1].expn 2、链式存储表示的相加 当采用链式存储表示时，根据结点类型定义，凡是系数为0的项不在链表中出现，从而可以大大减少链表的长度。 云淡风清 http://gsqls.blog.163.com/ 一元多项式相加的实质是： 指数不同：是链表的合并。 指数相同：系数相加，和为0，去掉结点，和不为0，修改结点的系数域。算法一： 就在原来两个多项式链表的基础上进行相加，相加后原来两个多项式链表不再存在，当然就不再允许对原来两个多项式进行其它操作了。 算法描述： Ploy *add_ploy(ploy *La,ploy *Lb)//将以La，Lb为头指针表示的一元多项式相加 { ploy *Lc,*pc,*pa,*pb,*ptr;float x;Lc=pc=La;pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){ if(pa->expn expn)//将pa所指的结点合并，pa指向下一个结点 { pc->next=pa; pc=pa; pa=pa->next; } else if(pa->expn>pb->expn)//将pb所指的结点合并，pb指向下一个结点 { pc->next=pb; pc=pb; pb=pb->next; } else { x=pa->coef+pb->coef; if(abs(x)<=1.0e-6)//如果系数和为0，删除两个结点 { ptr=pa; pa=pa->next; free(ptr); ptr=pb; pb=pb->next; free(ptr); } else//如果系数和不为0，修改其中一个结点的系数域，删除另一个结点 { 云淡风清 http://gsqls.blog.163.com/ pc->next=pa; pa->coef=x; pc=pa; pa=pa->next; ptr=pb; pb=pb->next;free(pb); } } }//end of while if(pa==NULL) pc->next=pb;else pc->next=pa;return(Lc);} 算法之二： 对两个多项式链表进行相加，生成一个新的相加后的结果多项式链表，原来两个多项式链表依然存在，不发生任何改变，如果要再对原来两个多项式进行其它操作也不影响。 算法描述： Ploy *add_ploy(ploy *La,ploy *Lb)//将以La，Lb为头指针表示的一元多项式相加，生成一个新的结果多项式 { ploy *Lc,*pc,*pa,*pb,*p;float x;Lc=pc=(ploy *)malloc(sizeof(ploy));pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){ if(pa->expn expn) { p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值 p->coef=pa->coef; p->expn=pa->expn; p->next=NULL;//生成的结点插入到结果链表的最后，pa指向下一个结点 pc->next=p; pc=p; pa=pa->next; } else if(pa->expn>pb->expn) { p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值 p->coef=pb->coef;p->expn=pb->expn; p->next=NULL; 云淡风清 http://gsqls.blog.163.com/ pc->next=p;//生成的结点插入到结果链表的最后，pb指向下一个结点 pc=p; pb=pb->next; } else { x=pa->coef+pb->coef; if(abs(x)<=1.0e-6)//系数和为0，pa, pb分别直接后继结点 { pa=pa->next; pb=pb->next; } else//若系数和不为0，生成的结点插入到结果链表的最后，pa, pb分别指向直接后继结点 { p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值 p->coef=x;p->expn=pb->expn; p->next=NULL; pc->next=p; pc=p; pa=pa->next; pb=pb->next; } } }//end of while if(pb!=NULL) while(pb!=NULL) { p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值 p->coef=pb->coef; p->expn=pb->expn; p->next=NULL; pc->next=p; pc=p; pb=pb->next; } if(pa!=NULL) while(pa!=NULL) { p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值 p->coef=pb->coef; p->expn=pa->expn; p->next=NULL; pc->next=p; 云淡风清 http://gsqls.blog.163.com/ } pc=p; pa=pa->next;} return(Lc);习题 二 1、简述下列术语：线性表，顺序表，链表。 2、何时选用顺序表，何时选用链表作为线性表的存储结构合适？各自的主要优缺点是什么？ 3、在顺序表中插入和删除一个结点平均需要移动多少个结点？具体的移动次数取决于哪些因素？ 4、链表所表示的元素是否有序？如有序，则有序性体现于何处？链表所表示的元素是否一定要在物理上是相邻的？有序表的有序性又如何理解？ 5、设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。 6、写一算法从一给定的向量A删除值在x到y(x≤y)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。 7、设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。 《数据结构》教案 课程性质和任务 本课程是计算机专业的主要专业基础课程之一。本课程的参考教学时数为54学时，实际讲课学时为35，实验学时为16。其主要内容包括顺序表、链表、栈、队、串、树和图的结构，以及查找和排序技术。通过本课程的教学，使学生理解计算机软件系统所必须的数据结构及算法的内部逻辑，掌握在软件工程中大量存在的查找和排序技术，并通过大量的上机实习，实现各种数据结构的算法，以便为后续课程的学习提供专业基础知识，同时增强学生编制程序的能力。 课程教学目标 通过本课程的学习，应达到以下目标： 深刻理解数据结构中线性表、栈、队和链的概念、算法及其基本应用。 理解树的基本概念，学会建立二叉树，并在二叉树上进行查找、插入和删除等各种运算。 理解图的基本结构和算法，了解图的路径问题。 熟练掌握几种重要的内部排序和查找技术，了解外部排序的一般过程。 能熟练地运用C语言，准确、清晰地编制与本课程有关的算法，并能上机调试通过。 新疆农业大学数据结构课程教案 第一讲 绪论(对应教材p1—p17) 一、教学目的和要求 要求掌握数据结构中基本概念的定义，理解数据结构研究的主要内容，了解抽象数据类型的表示和实现，理解算法评价的两个指标。 二、授课主要内容 1.数据结构研究的主要内容 2.数据结构中涉及的基本概念 3.算法的概念、描述方法以及评价标准 三、教学重点难点 数据结构中的基本概念、算法的概念、描述方法以及评价标准 四、授课内容和方法 【口述】当今计算机应用的特点：所处理的数据量大且具有一定的关系；对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。 一、什么是数据结构 我们大家知道许多非数值计算问题的数学模型常常是数学方程，如线性方程组、微分方程。所以这类非数值计算问题的解决就归结于对数学模型设计算法、编写程序。然而在现实社会中存在着许多非数值计算问题，其数学模型难以用数学方程描述。 1、举例说明 图书馆的书目检索自动化问题----计算机处理的对象之间存在着线性关系，称为线性的数据结构。 人机对奕问题----计算机处理的对象是一个个格局。所有可能出现的格局是一棵倒置的树。 多岔路口交通灯的管理问题----数学模型是图的数学结构。 【由以上举例引出下列结论：】 非数值计算问题的数学模型是表、树和图之类的数据结构。【总结出定义】 数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的一门学科。（三个要素：对象、关系及操作（运算）） 2、《数据结构》课程的介绍 1968年美国克努特教授开创了数据结构的最初体系： 数据的逻辑结构和存储结构及其操作。 数据结构是一门综合性的专业课程，是一门介于数学、计算机硬件、计算机软件之间的一门核心课程。是设计和实现编译系统、操作系统、数据库系统及其他系统程序和大型应用程序的基础。 二、基本概念和术语 1、数据 数据：是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机 加工的“原料”。 数据元素:是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项:有时，一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。 2、数据对象、数据结构 数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。四类基本结构：集合、线性结构、树形结构、图形结构或网状结构。数据结构的形式定义：数据结构是一个二元组 Data_Structure=(D,S)其中，D 是数据元素的有限集，S 是D上关系的有限集。 例：复数 Complex=(C,R)例：课题小组 Group=(P,R)P={T,G1,„,Gn,S11,„,Snm}1≤n≤3，1≤m≤2，R={R1,R2} R1={ ① 逻辑结构：数据元素之间的逻辑关系。 ② 存储结构(物理结构)：数据元素及其关系在计算机存储器的表示。用于表示数据元素的位串称之为元素或结点。用于表示数据项的位串称之为数据域。 ③ 数据的运算：对数据施加的操作。 算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。 3、数据的两种存储结构： 顺序存储结构：把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于语言的数组来描述的。 链式存储结构：不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑关系是由附加的指针字段表示的，通常要借助于语言的指针类型来描述。 * 4、数据类型、抽象数据类型 数据类型:是一个值的集合和定义在这个值集上的所有的操作。例如，整数类型。数据类型可分为：非结构的原子类型和结构类型。 原子类型的值是不可分解的，结构类型的值是由若干成分按某种结构组成的。 抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和实现是无关的。 抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。抽象数据类型按其值的不同特性，分为三种类型： ① 原子类型:变量的值是不可分解的。 ② 固定聚合类型:变量的值由确定数目的成分按某种结构组成。③ 可变聚合类型:其值的成分数目不确定。 抽象数据类型的形式定义：我们用一个三元组来表示一个抽象数据类型。 （D，S，P） D是数据对象，S是D上的关系集，P是对D的基本操作。 格式： ADT 抽象数据类型名{ 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 }ADT 抽象数据类型名。 数据对象和数据关系的定义用伪码描述。数据基本操作的定义格式： 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 例： ADT Triplet{ 数据对象：D={e1，e2,e3 |e1,e2,e3∈Elemset(定义了关系运算的某个集合)} 数据关系：R1={〈e1,e2>, InitTriplet(&T,v1,v2,v3)DestroyTriplet（&T）Get（T,i,&e）Put(&T,i,e)IsAscending(T)IsDescending(T)Max(T,&e) Min(T,&e) }ADT Triplet 多形数据类型:是其值的成分不确定的数据类型。 三、抽象数据类型的表示与实现 抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。 1、类C语言 精选了C 的一个子集，扩充修改，增强了语言的描述功能。 预定义常量和类型 数据结构的表示：存储结构用类型（typedef）定义来描述。 数据元素类型约定为ElemType. 基本操作的算法用函数描述： 函数类型 函数名（函数参数表）{ //算法说明 语句序列 }//函数名 增加了引用调用的参数传递方式。 赋值语句、选择语句、循环语句、结束语句、输入输出语句、注释语句 基本函数 逻辑运算约定 例：Triplet的表示和实现 //采用动态分配的顺序存储结构 Typedef ElemType * Triplet://由InitTriplet分配三个元素存储空间 //基本操作的函数原型说明 Status InitTriplet(Triplet &T,ElemType v1, ElemType v2, ElemType v3)Status DestroyTriplet（&T）Status Get（T,i,&e）Status Put(&T,i,e)Status IsAscending(T)Status IsDescending(T)Status Max(T,&e)Status Min(T,&e)//基本操作的实现 Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3){ //构造三元组T，依次置T 的三个元素的处值为v1,v2和v3。 T=(ElemType)malloc(3*sizeof(ElemType));//分配三个元素的存储空间 If(!T)exit(OVERFLOW);//分配存储空间失败 T[0]=v1;T[1]=v2;T[2]=v3;return OK;}//InitTriplet Status DestroyTriplet（Triplet &T）{ //销毁三元组T。······ }//Min 四、算法和算法分析 1、算法（Algorithm） 是对特定问题求解步骤的一种描述，它是指令的有限序列。算法具有五个重要特性：有穷性、确定性、可行性、输入、输出 2、算法设计的要求 正确性、可读性、健壮性和效率与低存储量要求 3、算法效率的度量 算法时间是由控制结构和原操作的决定的。做法：选取一种是基本操作的原操作，以该基本操作重复的次数作为算法的时间量度。 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f（n），T（n）=O（f（n）） 它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长绿相同。 语句的频度：是该语句重复执行的次数。 例：求两个n阶方阵的乘积C=A×B，其算法如下： #define n 100 void MatrixMultiply(int A[n][n],int B[n][n],int C[n][n]){ int i,j,k for(i=1;i<=n;++i)n+1 for(j=1;j<=n;++j)n*(n+1) C[i][j]=0;n2 for(k=1;k<=n,k++)n2(n+1) 3C[i][j]=C[i][j]+a[i][k]*b[k][j];n } } T(n)=2n3+3n2+2n+1 3limT(n)/ n=2 T(n)=O(n3)例： （a）{++x;s=0;}（b）for(i=1;i<=n;++i){++x;s+=x;}（c）for(j=1;j<=n;++j)for(k=1;k<=n;k++){++x;s+=x;} 含基本操作“x增1”的语句的频度分别为1,n和n2 时间复杂度是O(1),O(n)和O(n2)。时间复杂度有时与输入有关。 4、算法的存储空间需求 空间复杂度：S（n）=O（f（n）） 五、作业布置 复习回顾c语言中关于结构体和指针部分的内容，以便于后期学习。 六、教学后记 按2 学时讲完。 以前教学中反映出学生对抽象数据类型掌握不好，结构体知识基本不懂，所以要求学生课下自学，下次课抽1学时学习结构体和指针。 学生读程序能力差，循环嵌套分析不出执行次数。考虑布置了一道题目练习。 数据结构参考题目 一、选择 1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（） A.栈 B.队列 C.树 D.图 2.下面程序段的时间复杂度为（）for(i=0;i A.串的长度相等 B.含有相同的字符集 C.都是非空串 D.串的长度相等且对应的字符相同 5．若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（） A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX 6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）A.0 B.1 C.48 D.49 7.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为 （35，51，24，13，68，56，42，77，93） （35，24，13，51，56，42，68，77，93）所采用的排序方法是（） A.插入排序 B.冒泡排序 C.快速排序 D.归并排序 8.已知散列表的存储空间为T[0..16]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（） A.T[2] B.T[4] C.T[8] D.T[10] 9.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（）A.head(tail(head(L)))B.head(head(head(L)))C.tail(head(tail(L)))D.head(head(tail(L)))10.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout，则所有顶点的入度之和为（） A.Dout B.Dout-1 C.Dout+1 D.n 11．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构 12．栈的插入和删除操作在()进行。 A．栈顶 B.栈底 C.任意位置 D指定位置 13．由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A.24 B.71 C.48 D.53 14．一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是()A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 3 15．关于栈和队列的说法中正确的是（） A．栈和队列都是线性结构 B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构 16．关于存储相同数据元素的说法中正确的是（）A．顺序存储比链式存储少占空间 B.顺序存储比链式存储多占空间 C.顺序存储和链式存储都要求占用整块存储空间 D.链式存储比顺序存储难于扩充空间 17．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）A.q→next=s；p→next=s； B.q→next=s；s→next=p； C.q→next=s；q→next=p； D.q→next=s；s→next=q； 18．设一组记录的关键字key值为{62，50，14，27，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）A.1 B.2 C.3 D.4 19．执行下面程序段时，S语句被执行的次数为：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)S;A.n*n B.n*n/2 C.n(n+1)D.n(n+1)/2 20．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）A．O(n)B.O(1)C.O(log2n)D.O(n2)21．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（） A.a，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b 22．关于串的叙述中，正确的是（）A．空串是只含有零个字符的串 B.空串是只含有空格字符的串 C.空串是含有零个字符或含有空格字符的串 D.串是含有一个或多个字符的有穷序列 23．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（） A．front==rear B.(front+1)%m==rear C.rear+1==front D.(rear+1)%m==front 24．设有二维数组 1A［n］［n］表示如下：23456，则A［i］［i］（0≤i≤n-1）的D.i2/2 值为（） A．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 25．高度为h的完全二叉树中，结点数最多为（） hA．2h-1 B.2h+1 C.2-1 D.2h 26．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（） A.mn B.mn-1 C.n(m-1)D.m(n-1)27．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）A.n B.n-1 C.n+1 D.2(n-1)28．关于无向图的邻接矩阵的说法中正确的是（）A.矩阵中非全零元素的行数等于图中的顶点数 B.第i行上与第i列上非零元素总和等于顶点Vi的度数 C.矩阵中的非零元素个数等于图的边数 D.第i行上非零元素个数和第i列上非零元素个数一定相等 29．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）A.1 B.2 C.3 D.4 30．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（） A.36，44，49，55，81，88 B.44，36，49，55，81，88 C.44，36，49，81，55，88 D.44，36，49，55，88，81 二、填空题 1.数据是计算机加工处理的对象（）。2.数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面()。 3.线性表是由n≥0个相同类型组成的有限序列（）。4.栈是一种后进先出的线性表（）。 5.从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前驱结点（）。6.单链表设置头结点的目的是为了简化运算（）。7.树的最大特点是一对多的层次结构（）。8.组成数据的基本单位称为数据元素（）。 9.从非循环链表的某一结点出发，既能找到它的后继结点，又能找到它的前驱结点（）。 10.单链表结点的指针域是用来存放其直接后继结点的首地址的（） 11.数据的存储结构是数据的逻辑结构的存储映象（）。 12.用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系（）。 13.在非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后驱（）。14.树的最大特点是一对多的层次结构（）。15.队列的特点是先进先出（）。 16.由后序遍历序列和中序遍历序列能唯一确定一颗二叉树（）。17.数据的存储结构独立于计算机（）。18.线性表简称为”顺序表”。（） 19.对数据的任何运算都不能改变数据原有的结构特性（）。20.从循环单链表的任一结点出发，可以找到表中的所有结点（）。21.栈是一种先进先出的线性表（）。22.链表的主要缺点是不能随机访问（）。23.二叉树是树的特殊形式（）。24.冒泡排序法是稳定的排序（）。25.算法是对解题方法和步骤的描述（）。26.算法可以用任意的符号来描述（）。 27.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型（）。 28.线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中（）。29.栈是一种先进后出的线性表（）。 30.将插入和删除限定在表的同一端进行的线性表是队列（）。 三、画图题 1.请根据下列二元组画出相应的数据结构 K={15,11,20,8,14,13 } R={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.请根据下列二元组画出相应的数据结构 K={A,B,C,D,E,F,G,H,I,J} R={ K={1,2,3,4,5} R={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>} 5．请根据下列二元组画出相应的数据结构 K={0,1,2,3,4,5,6,7} R={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(4,7),(5,6)} 6．请根据下列二元组画出相应的数据结构 K={1,2,3,4,5,6,7} R={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）} 四、运算题 1．已知一个图的顶点集V和边集H分别为： V＝{0，1，2，3，4，5，6，7} E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}； 按照克鲁斯卡尔算法得到最小生成树，拭写出在最小生成树中依次得到的各条边。______，______，______，______，______，______，______。 2.一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 平均查找长度：（写出计算过程） 3．已知一个图的顶点集V和边集H分别为： V＝{0，1，2，3，4，5，6，7} E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}； 按照普里姆算法得到最小生成树，试写出在最小生成树中依次得到的各条边。（从顶点2出发） ____ __，___ _，___ ___，__ ____，___ ___，__ ____，___ ___。4.写出下图所示的二叉树的前中后序遍历结果： 前序： 中序： 后序： 5.设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉排序树。 五、编程题 1.请编写一个算法，实现十进制整数与二进制数的转换。Void shi_to_er(unsigned x){ 2.写出二分法查找的算法： Int search_bin(Keytype k,sstable st){ 3.请编写一个算法，实现单链表的就地逆置（单链表不带头结点）。LINKLIST *INVERTLINK(LINKLIST *H){ 数 据 结 构 课程设计报告 题 目： 一元多项式计算 专 业： 信息管理与信息系统 班 级： 2012级普本班 学 号： 201201011367 姓 名： 左帅帅 指导老师： 郝慎学 时 间： 一、课程设计题目分析 本课程设计要求利用C语言或C++编写，本程序实现了一元多项式的加法、减法、乘法、除法运算等功能。 二、设计思路 本程序采用C语言来完成课程设计。 1、首先，利用顺序存储结构来构造两个存储多项式A(x)和 B(x)的结构。 2、然后把输入，加，减，乘，除运算分成五个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块。 3、然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能，尽量减少程序运行时错误的出现。 4、最后编写main()主函数以实现对多项式输入输出以及加、减、乘、除，调试程序并将不足的地方加以修改。 三、设计算法分析 1、相关函数说明： (1)定义数据结构类型为线性表的链式存储结构类型变量 typedef struct Polynomial{} (2)其他功能函数 插入函数void Insert(Polyn p,Polyn h) 比较函数int compare(Polyn a,Polyn b) 建立一元多项式函数Polyn Create(Polyn head,int m) 求解并建立多项式a+b，Polyn Add(Polyn pa,Polyn pb) 求解并建立多项式a-b，Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多项式a*b，Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多项式a/b，void Device(Polyn pa,Polyn pb) 输出函数输出多项式，void Print(Polyn P) 销毁多项式函数释放内存，void Destroy(Polyn p) 主函数，void main（） 2、主程序的流程基函数调用说明(1)typedef struct Polynomial { float coef; int expn; struct Polynomial *next;} *Polyn,Polynomial; 在这个结构体变量中coef表示每一项前的系数，expn表示每一项的指数，polyn为结点指针类型，属于抽象数据类型通常由用户自行定义，Polynomial表示的是结构体中的数据对象名。 (2)当用户输入两个一元多项式的系数和指数后，建立链表，存储这两个多项式，主要说明如下： Polyn CreatePolyn(Polyn head,int m)建立一个头指针为head、项数为m的一元多项式 p=head=(Polyn)malloc(sizeof(struct Polynomial));为输入的多项式申请足够的存储空间 p=(Polyn)malloc(sizeof(struct Polynomial));建立新结点以接收数据 Insert(p,head);调用Insert函数插入结点 这就建立一元多项式的关键步骤 (3)由于多项式的系数和指数都是随即输入的，所以根据要求需要对多项式按指数进行降幂排序。在这个程序模块中，使用链表，根据对指数大小的比较，对各种情况进行处理，此处由于反复使用指针对各个结点进行定位，找到合适的位置再利用void Insert(Polyn p,Polyn h)进行插入操作。(4)加、减、乘、除、的算法实现： 在该程序中，最关键的一步是实现四则运算和输出，由于加减算法原则是一样，减法可通过系数为负的加法实现；对于乘除算法的大致流程都是：首先建立多项式a*b，a/b，然后使用链表存储所求出的乘积，商和余数。这就实现了多项式计算模块的主要功能。 (5)另一个子函数是输出函数 PrintPolyn（）； 输出最终的结果，算法是将最后计算合并的链表逐个结点依次输出，便得到整链表，也就是最后的计算式计算结果。由于考虑各个结点的指数情况不同，分别进行了判断处理。 四、程序新点 通过多次写程序，发现在程序在控制台运行时总是黑色的，本次写程序就想着改变一下，于是经过查资料利用system(“Color E0”);可以函数解决，这里“E0，”E是控制台背景颜色，0是控制台输出字体颜色。 五、设计中遇到的问题及解决办法 首先是，由于此次课程设计里使用指针使用比较多，自己在指针多的时候易脑子混乱出错，对于此问题我是采取比较笨的办法在稿纸上写明白后开始进行 4 代码编写。 其次是，在写除法模块时比较复杂，自己通过查资料最后成功写出除法模块功能。 最后是，前期分析不足开始急于写代码，中途出现各种问题，算是给自己以后设计时的一个经验吧。 六、测试（程序截图） 1.数据输入及主菜单 2.加法和减法模块 3.乘法和除法模块 七、总结 通过本次应用C语言设计一元多项式基本计算程序，使我更加巩固了C语言程序设计的知识，以前对指针这一点使用是比较模糊，现在通过此次课程设计对指针理解的比较深刻了。而且对于数据结构的相关算法和函数的调用方面知识的加深。本次的课程设计，一方面提高了自己独立思考处理问题的能力；另一方面使自己再设计开发程序方面有了一定的小经验和想法，对自己以后学习其他语言程序设计奠定了一定的基础。 八、指导老师评语及成绩 附录：（课程设计代码） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn为结点指针类型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系数为0的话释放结点 else { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//将指数相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系数为0的话释放结点 { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指数为新时将结点插入 } 7 } //建立一个头指针为head、项数为m的一元多项式 Polyn Create(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据 printf(“请输入第%d项的系数与指数:”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //调用Insert函数插入结点 } return head;} //销毁多项式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指针后移 q2=q2->next; } } //输出多项式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//项数计数器 if(!q)//若多项式为空，输出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系数大于0且不是第一项 9 if(q->coef!=1&&q->coef!=-1)//系数非1或-1的普通情况 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空 } //求解并建立多项式a+b，返回其头指针 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//当相加系数为0时，释放该结点 } return headc;} //求解并建立多项式a-b，返回其头指针 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//将pb的系数取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢复pb的系数 p->coef*=-1;13 return pd;} //求解并建立多项式a*b，返回其头指针 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//调用Insert函数以合并指数相同的项 } } return hf;} //求解并建立多项式a/b，返回其头指针 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点,存储商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点，存储余数 pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余数是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf(“请输入A(x)的项数:”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多项式A printf(“n”);printf(“请输入B(x)的项数:”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多项式B printf(“n”);printf(“**********************************************n”);printf(“* 多项式操作菜单 printf(”**********************************************n“);printf(”tt 1.输出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.减法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”执行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多项式A(x):“);Print(pa);*n”); printf(“多项式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多项式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多项式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多项式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 数据结构课程设计 1.赫夫曼编码器 设计一个利用赫夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。要求： 1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)初始化：键盘输入字符集大小26、26个字符和26个权值（统计一篇英文文章中26个字母），建立哈夫曼树； 3)编码：利用建好的哈夫曼树生成哈夫曼编码； 4)输出编码（首先实现屏幕输出，然后实现文件输出）； 5)界面优化设计。 代码如下： #include typedef struct HTNode //结构体 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把权值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼树，进行编码 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n请输入权值和字符(用空格隔开): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“输入成功！”);} void Coding_H(int n,HTNode *HT) //对结点进行译码 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]=' '; printf(“************************n”);printf(“Char Codingn”); for(k=1;k<=n;k++) { sp=n-1;p=k;fp=HT[k].Parent; for(;fp!=0;p=fp,fp=HT[fp].Parent) if(HT[fp].Lchild==p) cd[--sp]='0'; else cd[--sp]='1'; HC[k]=(char *)malloc((n-sp)*sizeof(char)); strcpy(HC[k],&cd[sp]); printf(“%c %sn”,HT[k].ch,HC[k]); } printf(“************************n”);free(cd);} void Read(int n,HTNode *HT) //从文件中读出数据 { int i;FILE * fp;if((fp=fopen(“data.txt”,“rb”))==NULL){ printf(“cannot open filen”); exit(0);} for(i=0;i fread(&HT[i].Weight,sizeof(struct HTNode),1,fp);// printf(“%d n”,HT[i].Weight); } Coding_H(n,HT); fclose(fp);} void Print_H(int m,HTNode *HT) //输出赫夫曼造树过程 { int k;printf(“************************n”);printf(“Num Weight Par LCh RCh n”);for(k=1;k<=m;k++){ printf(“%d ”,k); printf(“ %d”,HT[k].Weight); printf(“ %d”,HT[k].Parent); printf(“ %d”,HT[k].Lchild); printf(“ %dn”,HT[k].Rchild); } printf(“************************n”);} void Decode(int m,HTNode *HT) //对输入的电文进行译码 { int i,j=0;char a[10];char endflag='2';i=m;printf(“输入发送的编码，以‘2’结束:”);scanf(“%s”,&a);printf(“译码后的字符：”);while(a[j]!='2'){ if(a[j]=='0') i=HT[i].Lchild; else i=HT[i].Rchild; if(HT[i].Lchild==0) //HT[i]是叶结点 { printf(“%c”,HT[i].ch); i=m; //回到根结点 } j++;} printf(“n”);if(HT[i].Lchild!=0&&a[j]!='2') printf(“ERROR”);} int main() //主函数 { int n,m,c;HTNode HT[N];do { system(“color 2f”); //运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 赫夫曼编译码系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入权值、字母nttt2.把数据写入文件nttt3.输出赫夫曼编码表nttt”); printf(“4.输出赫夫曼译码表nttt5.输入编码并译码.nttt6.从文件中读出数据nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);printf(“输入多少结点:”); scanf(“%d”,&n);m=2*n-1;Create_H(n,m,HT);break; case 2:system(“cls”);Save(n,HT);break; case 3:system(“cls”);Print_H(m,HT);break; case 4:system(“cls”);Coding_H(n,HT);break; case 5:system(“cls”);Decode(m,HT);break; case 6:system(“cls”);Read(n,HT);break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下： 2.学生成绩管理（链表实现）要求： 实现如下功能：增加、查找、删除、输出、退出。 代码如下： #include //定义成绩信息结构体 { char Number[20];char Name[20];char Chinese[20];char English[20];char Math[20];}score;typedef struct node_score //定义成绩信息链表结点，包括数据域和指针域 { score data;struct node_score *next;}node_score,*p_node_score;p_node_score headScore;//定义链表的头指针为全局变量 void PrintScore(score s)//输出信息函数 { printf(“ %10s”,s.Number);printf(“ | %-6s”,s.Name);printf(“ | %-3s”,s.Chinese);printf(“ | %-3s”,s.English); printf(“ | %-3sn”,s.Math);} void View()//输出函数 { p_node_score pNodeScore; pNodeScore=headScore;printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”);while(pNodeScore!= NULL){ PrintScore(pNodeScore->data);//输出学生信息和成绩信息 pNodeScore=pNodeScore->next;} } void Add(){ p_node_score pNodeScore;// 定义一个节点 pNodeScore=(p_node_score)malloc(sizeof(node_score));//为节点分配存储空间 printf(“请输入学号：”);scanf(“%s”,pNodeScore->data.Number);printf(“请输入姓名：”);scanf(“%s”,pNodeScore->data.Name);printf(“请输入语文成绩：”);scanf(“%s”,pNodeScore->data.Chinese);printf(“请输入英语成绩：”);scanf(“%s”,pNodeScore->data.English);printf(“请输入高数成绩：”);scanf(“%s”,pNodeScore->data.Math);if(headScore==NULL){ //如果头结点为空 headScore=pNodeScore; pNodeScore->next=NULL;} else { //如果头结点不为空 pNodeScore->next=headScore; headScore=pNodeScore;//将头结点新结点 } } void Input(){ int n,i;printf(“输入几个学生的数据：”);scanf(“%d”,&n);for(i=0;i Add();printf(“输入成功！”);} int Delete(){ p_node_score pNodeScore,p1;//p1为pNodeScore的前驱 p1=headScore;if(p1==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char DeleteNumber[20]; printf(“请数入要删除的学生学号:”);scanf(“%s”,DeleteNumber);if(strcmp(p1->data.Number,DeleteNumber)==0) { //如果要删除的结点在第一个 headScore=p1->next; pNodeScore=p1; printf(“学号为%s的学生信息已经删除！n”,DeleteNumber); return 0;} else { pNodeScore=p1->next; while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,DeleteNumber)==0) { p1->next=pNodeScore->next; printf(“学号为%s的学生信息已经删除！n”,DeleteNumber); return 0; } else { //否则，结点向下一个，p1仍为pNodeScore的前驱 p1=pNodeScore; pNodeScore=pNodeScore->next; } } } printf(“没有此学号的学生！”);} int Change(){ p_node_score pNodeScore; pNodeScore=headScore;if(pNodeScore==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char EditNumber[20];printf(“请输入你要修改的学生学号：”);scanf(“%s”,EditNumber);while(pNodeScore!=NULL){ if(strcmp(pNodeScore->data.Number,EditNumber)==0) { //用strcmp比较两字符串是否相等，相等则返回0 printf(“原来的学生成绩信息如下：n”);//输出原来的成绩信息 printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); PrintScore(pNodeScore->data); printf(“语文新成绩:”); scanf(“%s”,pNodeScore->data.Chinese); printf(“英语新成绩:”); scanf(“%s”,pNodeScore->data.English); printf(“高数新成绩:”); scanf(“%s”,pNodeScore->data.Math); printf(“成绩已经修改！”); return 0; } pNodeScore=pNodeScore->next;//如果不相等，pNodeScore则指向下一个结点 } printf(“没有此学号的学生！n”);//如果找到最后都没有，则输出没有此学号的学生 } int Find(){ p_node_score pNodeScore; pNodeScore=headScore;if(pNodeScore==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char FindNumber[20];printf(“请输入你要查找的学生学号：”);scanf(“%s”,FindNumber);while(pNodeScore!=NULL){ if(strcmp(pNodeScore->data.Number,FindNumber)==0) { printf(“你要查找的学生成绩信息如下：n”); printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); PrintScore(pNodeScore->data); return 0; } pNodeScore=pNodeScore->next;} printf(“没有此学号的学生！n”);} int main() //主函数 { int choice=0;headScore=NULL;int c;do { system(“color 2f”); //运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 学生成绩管理系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入成绩信息nttt2.输出成绩信息nttt3.添加成绩信息nttt”); printf(“4.修改成绩信息nttt5.删除成绩信息nttt6.查询成绩信息nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);Input();break; case 2:system(“cls”);View();break; case 3:system(“cls”);Add();break; case 4:system(“cls”);Change();break; case 5:system(“cls”);Delete();break; case 6:system(“cls”);Find();break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下：第二篇：数据结构讲稿-第一次课-DS绪论
第三篇：数据结构参考材料
第四篇：2012数据结构课程设计
第五篇：数据结构课程设计
点击咨询 