数据结构教案

第一章绪论§1.1什么是数据结构一．数据结构的概念NiklausWirth说过Algorithm+DataStructures=Programs，其中程序设计:为计算机处理问题编制一组指令集，算法:处理问题的策略，数据结构:问题的数学模型。在计算机发展的早期，主要用于数值计算，例如：结构静力分析计算线性代数方程组，全球天气预报、环流模式方程，但是随着计算机应用领域的扩大和硬、软件技术的发展，非数值计算问题越来越多（占90%）例1：学生信息检索，计算机处理的对象之间存在一种简单的线性关系，这类数学模型可以归结为线性数据结构。例2：计算机和人对弈（八皇后问题等），为了得到合理的布局，计算机要存储当前的布局，从最初的布局开始，每个布局都会衍生出许多新的布局，这时计算机所要处理的是一颗对弈树，也是一种典型的数据结构。例3：教学计划的编排（交通灯），一个教学计划包含许多课程，课程间有些必须按规定的先后顺序进行，有些则没有次序要求，各个课程间的次序关系可用图来表示。也是一种典型的数据结构由此可见，描述这类非数值计算问题的数学模型已不再是数学方程，而是诸如表、树、图之类的数据结构，因此说，数据结构主要是研究非数值计算的程序设计中所出现的计算机操作对象以及它们之间关系和操作的学科。二．数据结构的产生和发展1968年以独立的学科设立，之后不断发展，目前已成为计算机专业的核心课程和许多非计算机专业的选修课程。§1.2有关概念和术语一．数据结构的概念1．数据:所有能被输入到计算机中，且被计算机处理的符号的集合计算机操作的对象的总称，是计算机处理的信息的某种特定的符号表示形式2．数据元素:数据中的一个“个体”，数据结构中讨论的基本单位，一个数据元素可能包含若干数据项，数据项：数据结构中讨论的最小单位，数据元素是数据项的集合，例如运动员（数据元素）姓名俱乐部名称出生日期参加日期职务业绩其中出生日期年月日是组合项3．数据对象：性质相同的数据元素的集合，是数据的一个子集，4．数据结构：是相互之间存在一种或多种特定关系的数据元素的集合，数据元素的关系称为结构。二．数据结构的表示数据结构是一个二元组：Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。严格地讲，以上定义仅是数据的逻辑结构的定义，逻辑结构可以看作是从一个具体问题抽象出来的数学模型，与数据的存储无关。数据的逻辑结构可归结为以下四类：线性结构、树形结构、图状结构、集合结构。集合结构：属于同一集合，别无其他关系（常用其他结构表示）线性结构：数据元素之间存在一对一的关系树状结构：数据元素之间存在一对多的关系图状结构：数据元素之间存在多对多的关系（a）集合结构（b）线性结构（c）树型结构（d）图形结构图1.4四类基本结构的示意图数据的存储结构─━逻辑结构在存储器中的映象，他所研究的是数据结构在计算机中的实现，主要有顺序存储、链式存储、索引和散列存储数据元素的映象方法即关系的映象方法：（表示<x,y>的方法）顺序映象以存储位置的相邻表示后继关系，y的存储位置和x的存储位置之间差一个常量C，而C是一个隐含值，整个存储结构中只含数据元素本身的信息，通常用数组来实现。链式映象以附加信息(指针)表示后继关系，需要用一个和x在一起的附加信息指示y的存储位置，不要求物理位置的相邻。在不同的编程环境中，存储结构可有不同的描述方法，当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如:以三个带有次序关系的整数表示一个长整数时，可利用C语言中提供的整数数组类型，定义长整数为:typedefintLong_int[3]；三、数据类型数据类型：在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。因为类型明显或隐含地规定了，在程序执行期间，变量或表达式所有可能取值的范围，以及在这些之上允许进行的操作。数据类型是一个值的集合和定义在此集合上的一组操作的总称。四．抽象数据类型(AbstractDataType简称ADT)1．定义：是指一个数学模型以及定义在此数学模型上的一组操作，和数据类型本质相同，抽象指的是数学模型的数学抽象特性，而且抽象数据类型的范围更广。ADT有两个重要特征:数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。例如抽象数据类型复数的定义：ADTComplex{数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：R1＝{<e1,e2>|e1是复数的实数部分,|e2是复数的虚数部分}基本操作：InitComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex假设:z1和z2是上述定义的复数，则Add(z1,z2,z3)操作的结果将得到z3=z1+z2抽象数据类型的描述方法2．抽象数据类型可用（D，S，P）三元组表示其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。§1.3抽象数据类型的表示和实现：抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现预处理：#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1#defineOVERFLOW-2#include<stdio.h>#include<stdlib.h>typedefintStatus;C语言中的运算符（）、[]、->、。！~++--+（正）-(负)*(指针)&sizeof(类型)*/%+-<<>><=<>>=!===&^|&&||=+=-=*=/=%=>>=<<=&=^=|=,(逗号)§1.4算法和算法的衡量一、算法算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1．有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；2．确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；3．可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；4．有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；5．有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。二、算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；c．程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；d．程序对于一切合法的输入数据都能得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。2.可读性算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；3．健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4．高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。三、算法效率的衡量方法和准则通常有两种衡量算法效率的方法:事后统计法缺点：1。必须执行程序2．其它因素掩盖算法本质事前分析估算法和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))，称T(n)为算法的(渐近)时间复杂度如何估算算法的时间复杂度？算法=控制结构+原操作（固有数据类型的操作）算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间，算法的执行时间与原操作执行次数之和成正比从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作，在算法中重复执行的次数作为算法运行时间的衡量准则例1for(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];}基本操作:乘法操作，时间复杂度:O(n3)例2voidselect_sort(inta[],intn){//将a中整数序列重新排列成自小至大有序的整数序列。for(i=0;i<n-1;++i){j=i;for(k=i+1;k<n;++k)if(a[k]<a[j])j=k;if(j!=i)a[j]←→a[i]}//select_sort基本操作:比较(数据元素)操作，时间复杂度:O(n2)四、算法的存储空间需求算法的空间复杂度：S(n)=O(g(n))表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括:1．输入数据所占空间;2．程序本身所占空间；3．辅助变量所占空间。若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。学习要点：1.熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。2.了解抽象数据类型的定义、表示和实现方法。3．理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。4．掌握计算语句频度和估算算法时间复杂度的方法。

第二章线性表线性结构是一个数据元素的有序（次序）集线性结构的基本特征:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。§2.1线性表的逻辑结构一、线性表的类型定义抽象数据类型线性表的定义如下：ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}二、基本操作：{结构初始化}1．InitList(&L)操作结果：构造一个空的线性表L。{销毁结构}2．DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。{引用型操作}3．ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。4．ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。5．PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。6．NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。7．GetElem(L,cur_e,&next_e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：用e返回L中第i个元素的值。8．LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。9．ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。{加工型操作}10．ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。11．PutElem(L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：L中第i个元素赋值同e的值。12．ListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。13．ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList利用上述定义的线性表可以完成其它更复杂的操作例2-1假设有两个集合A和B分别用两个线性表LA和LB表示（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合A＝A∪B。上述问题可演绎为，要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。1．从线性表LB中依次取得每个数据元素;GetElem(LB,i)→e2．依值在线性表LA中进行查访;LocateElem(LA,e,equal())3．若不存在，则插入之。ListInsert(LA,n+1,e)voidunion(List&La,ListLb){//将所有在线性表Lb中但不在La中的数据元素插入到La中La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal())ListInsert(La,++La_len1,e);//La中不存在和e相同的数据元素，则插入之}}//union例2-2已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。voidpurge(List&La,ListLb){//已知线性表Lb中的数据元素依值非递减有序排列(Lb是有序表)，//构造线性表La，使其只包含Lb中所有值不相同的数据元素InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!equal(en,e)){ListInsert(La,++La_len,e);en=e;}//La中不存在和e相同的数据元素，则插入之}}//purge例2-3归并两个“其数据元素按值非递减有序排列的”线性表LA和LB，求得线性表LC也具有同样特性设La=(a1,…,ai,…,an)Lb=(b1,…,bj,…,bm)Lc=(c1,…,ck,…,cm+n)则Ck=k=1,2,…,m+n1．分别从LA和LB中取得当前元素ai和bj；2．若ai≤bj，则将ai插入到LC中，否则将bj插入到LC中。voidMergeList(ListLa,ListLb,List&Lc){//已知线性表La和Lb中的元素按值非递减排列。//归并La和Lb得到新的线性表Lc，//Lc的元素也按值非递减排列。InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=Lb_len)){//La和Lb均非空GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//merge_list§2.2线性表的顺序存储和基本操作的实现顺序表用一组地址连续的存储单元依次存放线性表中的数据元素，线性表的起始地址，称作线性表的基地址，以“存储位置相邻”表示有序对<ai-1，ai>即：所有数据元素的存储位置均取决于第一个数据元素的存储位置Loc(ai)=Loc(a1)+(I-1)*l，1≤i≤n,l=sizeof(ElemType)顺序映像的C语言描述//-----线性表的动态分配顺序存储结构-----#defineLIST_INIT_SIZE80//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;//俗称顺序表线性表的基本操作的实现初始化在顺序映像中的实现StatusInitList_Sq(SqList&L){//构造一个空的线性表L。L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_Sq线性表的建立StatusCreaList_Sq(SqList&L)

{

intlength,i,data;

printf("输入表的长度\n");

scanf("%d",&length);

InitList_Sq(L);

printf("输入表中数据\n");for(i=0;i<length;i++){scanf("%d",&data);L.elem[i]=data;}L.length=length;returnOK;}//Crea_Sq3、线性表操作LocateElem(L,e,compare())的实现：intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在顺序线性表L中查找第1个值与e满足compare()的元素的位序。//若找到，则返回其在L中的位序，否则返回0。i=1;//i的初值为第1元素的位序p=L.elem;//p的初值为第1元素的存储位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq此算法的时间复杂度为:O(ListLength(L))4、线性表操作ListInsert(&L,i,e)的实现：问：插入元素时，线性表的逻辑结构发生什么变化？(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)StatusListInsert_Sq(SqList&L,intpos,ElemTypee){//在顺序线性表L的第pos个元素之前插入新的元素e，//pos的合法值为1≤pos≤Listlength_Sq(L)+1if(pos<1||pos>L.length+1)returnERROR;//插入位置不合法if(L.length>=L.listsize){//当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存储容量}q=&(L.elem[pos-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1returnOK;}//ListInsert_Sq性能分析：从I位置插入x，ai到an都要后移，共需移动n-I+1个元素，1≤i≤n+1，平均移动次数：，令，此算法的时间复杂度为:O(ListLength(L))5、线性表操作ListDelete(&L,i,&e)的实现：问：删除元素时，线性表的逻辑结构发生什么变化？(a1,…,ai-1,ai,ai+1,…,an)改变为(a1,…,ai-1,ai+1,…,an)StatusListDelete_Sq(SqList&L,intpos,ElemType&e){//在顺序线性表L中删除第pos个元素，并用e返回其值。//pos的合法值为1≤pos≤ListLength_Sq(L)if((pos<1)||(pos>L.length))returnERROR;//删除位置不合法p=&(L.elem[pos-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p)*(p-1)=*p;//被删除元素之后的元素左移--L.length;//表长减1returnOK;}//ListDelete_Sq性能分析：删除第I个元素，aI+1到an都要前移，共需移动n-I个元素，1≤i≤n，平均移动次数：，令，则此算法的时间复杂度为:O(ListLength(L))应用举例例1、线性表的合并StatusMerg_Sq(SqListLa,SqListLb,SqList&Lc)

{

ElemType*pa,*pb,*pc;

ElemType*pa_last,*pb_last;

pa=La.elem;

pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last){if(*pa<=*pb) *pc++=*pa++;else *pc++=*pb++; }while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;returnOK;}//Merg_Sq例2、将一个线性表分两部分，其中前面的比a1小，后面的比a1大//将表分成两部分,前面的比原来的第一元素小,后面的比第一个大

①StatusPart_Sq1(SqList&L)

{

ElemType*p,*p_last,*q,*s;

ElemTypee,et;

p=L.elem;p_last=L.elem+L.length-1;

e=*p;

for(q=p+1;q<=p_last;q++)

if(*q<e)

{

et=*q; for(s=q-1;s>=p;s--)*(s+1)=*s; *p=et; p++; }returnOK;}//Part_Sq②StatusPart_Sq2(SqList&L){inti,j,t;i=0;j=L.length-1;t=*L.elem;while(i<j){while(i<j&&L.elem[j]>=t)j--;L.elem[i]=L.elem[j];while(i<j&&L.elem[i]<=t)i++;L.elem[j]=L.elem[i];}L.elem[i]=t;returnOK;}//Part_Sq§2.3线性表类型的链式映象和基本操作的实现由于线性表的顺序存储是用物理位置上的相邻实现了逻辑上的相邻，因此对元素插入或移动时，运行效率低，但可以随机存取任一元素，链式存储不需用地址连续的存储单元来实现，它通过链表来实现逻辑上的相邻，但同时失去了顺序表可随机存取的优点。一、单链表1．定义：用一组地址任意的存储单元存放线性表中的数据元素，以元素(数据元素的映象)+指针(指示后继元素存储位置的)=结点(表示数据元素)，以“结点的序列”表示线性表称作链表，以线性表中第一个数据元素a1的存储地址作为线性表的地址，为线性表的头指针2．结点的C语言描述typedefstructLNode{ElemTypedata;//数据域structLnode*next;//指针域}LNode,*LinkList;二、单链表操作的实现1．voidCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带表头结点的单链线性表L。L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新结点scanf(&p->data);//输入元素值p->next=L->next;L->next=p;//插入到表头}}//CreateList_L算法的时间复杂度为:O(Listlength(L))建立LinkListCreaList1()

{//逆位序输入n个元素的值，建立带表头结点的单链线性表L

LinkListL;

ElemTypex;

LNode*s;

L=(LNode*)malloc(sizeof(LNode));L->next=NULL;scanf("%d",&x);

while(x!=flag)

{

s=(LNode*)malloc(sizeof(LNode));

s->data=x;

s->next=L->next;

L->next=s;

scanf("%d",&x);

}

returnL;}//Crea_LinkListLinkListCreaList2(){//顺序输入n个元素的值，建立带表头结点的单链线性表L。LinkListL,p,q;ElemTypex;L=(LNode*)malloc(sizeof(LNode));q=L;scanf("%d",&x);while(x!=flag){p=(LNode*)malloc(sizeof(LNode));p->data=x;q->next=p;q=p;scanf("%d",&x);}q->next=NULL;returnL;}//Crea_LinkList2．线性表的操作GetElem(L,i,&e)在链表中的实现:基本操作为:使指针p始终指向线性表中第j个数据元素StatusGetElem_L(LinkListL,intpos,ElemType&e){//L为带头结点的单链表的头指针。当线性表中存在第pos个元素存在时，则将第pos个数据元素的值赋给e并返回OK，否则返回ERRORp=L->next;j=1;//初始化，p指向第一个结点，j为计数器while(p&&j<pos){//顺指针向后查找，直到p指向第pos个元素或p为空p=p->next;++j;}if(!p||j>pos)returnERROR;//第pos个元素不存在e=p->data;//取第pos个元素returnOK;}//GetElem_L算法的时间复杂度为:O(ListLength(L))3．线性表的操作ListInsert(&L,i,e)在链表中的实现:基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针，有序对<ai-1,ai>改变为<ai-1,e>和<e,ai>StatusListInsert_L(LinkListL,intpos,ElemTypee){//在带头结点的单链表L中第pos个数据元素之前插入数据元素ep=L;j=0;while(p&&j<pos-1){p=p->next;++j;}//寻找第pos-1个结点if(!p||j>pos-1)returnERROR;//pos小于1或者大于表长s=(LinkList)malloc(sizeof(LNode));//生成新结点s->data=e;s->next=p->next;//插入L中p->next=s;returnOK;}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))StatusListInsert_L(LinkListL,intpos,ElemTypee){//在没有头结点的单链表L中第pos个数据元素之前插入数据元素es=(LinkList)malloc(sizeof(LNode));//生成新结点s->data=e;if(pos==1){s->next=L;L=s;}else{j=0;p=L;while(p&&j<pos-1){p=p->next;++j;}//寻找第pos-1个结点if(!p||j>pos-1)returnERROR;//pos小于1或者大于表长s->next=p->next;//插入L中p->next=s;}returnOK;}//LinstInsert_L4．线性表的操作ListDelete(&L,i,&e)在链表中的实现:基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针，有序对<ai-1,ai>和<ai,ai+1>改变为<ai-1,ai+1>StatusListDelete_L(LinkListL,intpos,ElemType&e){//在带头结点的单链表L中，删除第pos个元素，并由e返回其值p=L;j=0;while(p->next&&j<pos-1){//寻找第pos个结点，并令p指向其前趋p=p->next;++j;}if(!(p->next)||j>pos-1)returnERROR;//删除位置不合理q=p->next;p->next=q->next;//删除并释放结点e=q->data;free(q);returnOK;}//ListDelete_L算法的时间复杂度为:O(ListLength(L))StatusListDelete_L(LinkListL,intpos,ElemType&e){//在没有头结点的单链表L中，删除第pos个元素，并由e返回其值if(pos==1)L=L->next;else{p=L;j=0;while(p->next&&j<pos-1){//寻找第pos个结点，并令p指向其前趋p=p->next;++j;}if(!(p->next)||j>pos-1)returnERROR;//删除位置不合理q=p->next;p->next=q->next;//删除并释放结点e=q->data;free(q);}returnOK;}//ListDelete_L算法的时间复杂度为:O(ListLength(L))5.求表的长度：intListLeng_L(LinkListL){LNode*p=L->next;intj=0;while(p!=NULL){p=p->next;j++;}returnj;}//Leng_LinkList6．查找LNode*LocaElem(LinkListL,ElemTypee){LNode*p=L->next;while(p!=NULL&&p->data!=e) p=p->next;returnp;}//Loca_LinkList应用举例例1．逆置：voidreverse(LinkList&L)（中科院93年试题）

{

LNode*p,*q;

p=L->next;L->next=NULL;while(p){q=p;p=p->next;q->next=L->next;L->next=q;}}例2：两个链表的合并voidMerg_LinkList(LinkListLa,LinkListLb,LinkList&Lc){LinkListpa,pb,pc;Lc=pc=La;pa=La->next;pb=Lb->next;while(pa&&pb)if(pa->data<=pb->data){ pc->next=pa; pc=pa; pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}pc->next=pa?pa:pb;free(Lb);}//Merg_LinkList例3已知单链表L，写一算法，删除其重复结点(北京工业大学96年试题)StatusPur_LinkList(LinkList&L){LNode*p,*q,*r;p=L->next;if(p==NULL)returnERROR;while(p->next){q=p;while(q->next)if(q->next->data==p->data) { r=q->next; q->next=r->next; free(r); }else q=q->next;p=p->next;}returnOK;}//Pur_LinkList例4：逆向合并(中国科技大学97年研究生入学试题）voidRev_MergList(LinkListA,LinkListB,LinkList&C){LinkListq,pa,pb,pc,pre;pa=A->next;pb=B->next;pre=NULL;while(pa&&pb){if(pa->data<pb->data){ pc=pa; q=pa->next; pa->next=pre; pa=q;}else{pc=pb;q=pb->next;pb->next=pre;pb=q;}pre=pc;}while(pa){q=pa->next;pa->next=pc;pc=pa;pa=q;}while(pb){q=pb->next;pb->next=pc;pc=pb;pb=q;}A->next=pc;C=A;}//Rev_MergList例5StatusDeleteBetween(LinkList&L,ElemTypemink,ElemTypemaxk){LNode*p,*q;p=L;while(p->next->data<mink)p=p->next;if(p->next){q=p->next;while(q->data<maxk)q=q->next;p->next=q;}returnOK;}6、判断La是否包含在Lb中(清华大学94年研究生入学试题）intInclude(LinkListLa,LinkListLb){LinkListpa,pb;pa=La->next;pb=Lb->next;if(pa==NULL)returnTRUE;while(pb&&pa->data>=pb->data)if(pa->data==pb->data) returnInclude(pa,pb);else pb=pb->next;returnFALSE;}用上述定义的单链表实现线性表的操作时，存在的问题：1．单链表的表长是一个隐含的值；2．在单链表的最后一个元素最后插入元素时，需遍历整个链表；3．在链表中，元素的“位序”概念淡化，结点的“位置”概念强化。改进链表的设置：1．增加“表长”、“表尾指针”和“当前位置的指针”三个数据域；2．将基本操作中的“位序i”改变为“指针p”*四、一个带头结点的线性链表类型typedefstructLNode{//结点类型ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct{//链表类型Linkhead,tail;//指向头结点和最后一个结点intlen;//指示链表长度Linkcurrent;//指向当前访问的结点的指针，//初始位置指向头结点}LinkList.StatusMakeNode(Link&p,ElemTypee);//分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERRORvoidFreeNode(Link&p);//释放p所指结点链表的基本操作:{结构初始化和销毁结构}StatusInitList(LinkList&L);//构造一个空的线性链表L，//头指针、尾指针和当前指针均指向头结点，表长为零StatusDestroyList(LinkList&L);//销毁线性链表L，L不再存在{引用型操作}StatusListEmpty(LinkListL);//判表空intListLength(LinkListL);//求表长StatusPrior(LinkListL);//改变当前指针指向其前驱StatusNext(LinkListL);//改变当前指针指向其后继ElemTypeGetCurElem(LinkListL);//返回当前指针所指数据元素StatusLocatePos(LinkListL,inti);//改变当前指针指向第i个结点StatusLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));//若存在与e满足函数compare()判定关系的元素，则移动当前指针指向第1个满足条件的元素，并返回OK;否则返回ERRORStatusListTraverse(LinkListL,Status(*visit)());//依次对L的每个元素调用函数visit(){加工型操作}StatusClearList(LinkList&L);//重置为空表StatusSetCurElem(LinkList&L,ElemTypee);//更新当前指针所指数据元素StatusAppend(LinkList&L,Links);//一串结点链接在最后一个结点之后StatusInsAfter(LinkList&L,ElemTypee);//将元素e插入在当前指针之后StatusDelAfter(LinkList&L,ElemType&e);//删除当前指针之后的结点{这里定义的大部分算法都将结点和指针的概念封装在算法中}StatusInsAfter(LinkList&L,ElemTypee){//若当前指针在链表中，则将数据元素e插入在线性链表L中，当前指针所指结点之后,并返回OK;否则返回ERROR。if(!L.current)returnERROR;if(!MakeNode(s,e))returnERROR;s->next=L.current->next;L.current->next=s;RreturnOK;}//InsAfterStatusDelAfter(LinkList&L,ElemType&e){//若当前指针及其后继在链表中，则删除线性链表L中当前指针所指结点之后的结点，并返回OK;否则返回ERROR。if(!(L.current&&L.current->next))returnERROR;q=L.current->next;L.current->next=q->next;e=q->data;FreeNode(q);returnOK;}//DelAfter{利用上述定义的线性链表可以完成线性表的其它操作}例1:StatusListInsert_L(LinkListL,inti,ElemTypee){//在带头结点的单链线性表L的第i个元素之前插入元素eif(!LocatePos(L,i-1))returnERROR;//i值不合法if(InsAfter(L,e))returnOK;//插入在第i-1个结点之后elsereturnERROR;}//ListInsert_L例2:voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lcint(*compare)(ElemType,ElemType))){//已知单链线性表La和Lb的元素按值非递减排列，归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列if(!InitList(Lc))returnERROR;//存储空间分配失败LocatePos(La,0);LocatePos(Lb,0);//当前指针指向头结点if(DelAfter(La,e))a=e;elsea=MAXC;//MAXC为常量最大值if(DelFirst(Lb,e))b=e;elseb=MAXC;//a和b为两表中当前比较元素while(!(a=MAXC&&b=MAXC)){//La或Lb非空if((*compare)(a,b)<=0){//a≤bInsAfter(Lc,a);if(DelAfter(La,e1)a=e1;elsea=MAXC;}else{//a＞bInsAfter(Lc,s);if(DelAfter(Lb,e)b=e1;elseb=MAXC;}}DestroyList(La);DestroyList(Lb);//销毁链表La和LbreturnOK;}//MergeList_L四、其它形式的链表1．循环链表最后一个结点的指针域的指针又指回第一个结点的链表（将在多项式中详细说明）通常在实际的操作中，保留尾结点的地址，这样合并时比较容易p=r1->next;r1->next=r2->next->next;r2->next=p;例如：猴子选大王（复旦大学97年研究生入学试题）voidSeleKing(){LinkListL,p,q;inti,n,m;printf("inputmonkeynum\n");scanf("%d",&n);L=(LNode*)malloc(sizeof(LNode));L->data=1;p=L;i=2;while(i<=n){q=(LNode*)malloc(sizeof(LNode));q->data=i;i++;p->next=q;p=q;}p->next=L;i=0;p=q;printf("inputm\n");scanf("%d",&m);while(p!=p->next){p=p->next;i++;if(i%m==0) q->next=p->next;else q=p;}printf("king=%d",p->data);}//Seleking2.双向链表（1）//-----线性表的双向链表存储结构-----typedefstructDuLNode{ElemTypedata;//数据域structDuLNode*prior;//指向前驱的指针域structDuLNode*next;//指向后继的指针域}DuLNode,*DuLinkList;（2）.基本操作：建立：DuLinkListCreaList_Du(){DuLinkListhead,p,q;ElemTypex,flag=32767;head=(DuLNode*)malloc(sizeof(DuLNode));head->prior=NULL;head->next=NULL;q=head;scanf("%d",&x);while(x!=flag){p=(DuLNode*)malloc(sizeof(DuLNode));p->data=x;p->next=NULL;q->next=p;p->prior=q;q=p;scanf("%d",&x);}returnhead;}//Crea_DuLinkList得到某个元素的值或地址DuLinkListGetElem_Du(DuLinkListL,inti){intj=0;DuLinkListp;p=L;while(p&&j<i){p=p->next;j++;}if(!p||j>i)returnNULL;elsereturnp;}//Get_DuLinkLIst插入某个元素：StatusListInsert_Du(DuLinkList&L,inti,ElemTypee){DuLinkListp,s;p=GetElem_Du(L,i-1);if(p==NULL){ printf("noi-1node\n"); returnERROR;}else{ if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) exit(OVERFLOW); s->data=e; if(p->next!=NULL) { s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; } else { s->prior=p; s->next=p->next; p->next=s; } returnOK;}}//Inse_DuLinkList删除某个元素：StatusListDelete_Du(DuLinkList&L,inti,ElemType&e){DuLinkListp;if(!(p=GetElem_Du(L,i)))returnERROR;e=p->data;if(p->next==NULL) p->prior->next=p->next; else { p->prior->next=p->next; p->next->prior=p->prior; }free(p);returnOK;}//Dele_DuLinkListStatusPrin_DuLinkList(DuLinkListL){DuLinkListp;p=L->next;while(p){printf("%4d",p->data);p=p->next;}returnOK;}3。静态链表//静态链表

（1）基本操作#include"common.h"

#defineMAXSIZE20

typedefcharElemType;

typedefstructSNode{

ElemTypedata;

intcur;

}SNode,SLinkList[MAXSIZE];

初始化：StatusInit_SLinkList(SLinkList&S)

{

inti;

for(i=0;i<MAXSIZE-1;i++)S[i].cur=i+1;S[MAXSIZE-1].cur=0;returnOK;}分配单元：intMalloc_SLinkList(SLinkList&S){inti;i=S[0].cur;if(S[0].cur)S[0].cur=S[i].cur;returni;}释放单元StatusFree_SLinkList(SLinkList&S,intk){S[k].cur=S[0].cur;S[0].cur=k;returnOK;}//Free_SLinkLIst输出：StatusPrin_SLinkList(SLinkListS,inti){intt=s[i].cur;while(t!=0){ printf("%4c",S[t].data); t=S[t].cur;}returnOK;}（2）应用举例例1求(A-B)U(B-A)voidDiff(SLinkList&Space,int&S){inti,j,k,r,m,n,p;charc;Init_SLinkList(Space);S=Malloc_SLinkList(Space);r=S;printf("inputaelemnum\n");scanf("%d",&m);getchar();for(j=1;j<=m;++j){i=Malloc_SLinkList(Space);scanf("%c",&Space[i].data);Space[r].cur=i;r=i;}Space[r].cur=0;printf("inputbelemnum\n");scanf("%d",&n);getchar();for(j=1;j<=n;j++){scanf("%c",&c);p=S;k=Space[S].cur;while(k!=Space[r].cur&&Space[k].data!=c){ p=k; k=Space[k].cur; }if(k==Space[r].cur){ i=Malloc_SLinkList(Space); Space[i].data=c; Space[i].cur=Space[r].cur; Space[r].cur=i; }else { Space[p].cur=Space[k].cur; Free_SLinkList(Space,k); if(k==r)r=p; }}}//Diff例2插入排序voidList_InseSort(SLinkLists,int&p){inti,j,q;ElemTypee;s[0].data=32767;s[0].cur=1;printf("%c",&e);s[1].data=e;s[1].cur=0;i=2;scanf("%c",&e);while(e!='\0'){s[i].data=e;p=s[0].cur;q=0;while(e>s[p].data&&s[p].cur!=0){ q=p; p=s[p].cur; }s[i].cur=p;s[q].cur=i;scanf("%c",&e);i++;}p=s[0].cur;}§2.4一元多项式的表示一元多项式的表示在计算机中，可以用一个线性表来表示：P=(p0,p1,…，pn)但是对于形如S(x)=1+3x10000–2x20000的多项式，上述表示也就不恰当了。一般情况下的一元多项式可写成Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi是指数为ei的项的非零系数，0≤e1<e2<┄<em=n它可以用其数据元素为(系数项，指数项)的线性表来表示（（p1,e1）,(p2,e2),┄,(pm,em)）例如：线性表（(7,3),(-2,12),(-8,999)）表示多项式P999(x)=7x3-2x12-8x999抽象数据类型一元多项式的定义如下：ADTPolynomial{数据对象：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0}{TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,且ai-1中的指数值＜ai中的指数值，i=2,...,n}基本操作：CreatPolyn(&P,m)操作结果：输入m项的系数和指数，建立一元多项式P。DestroyPolyn(&P)初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。PrintPolyn(&P)初始条件：一元多项式P已存在。操作结果：打印输出一元多项式P。AddPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相加运算，即：Pa=Pa＋Pb，并销毁一元多项式Pb。SubtractPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相减运算，即：Pa=Pa－Pb，并销毁一元多项式Pb。MultiplyPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相乘运算，即：Pa=Pa×Pb，并销毁一元多项式Pb。PolynLength(P)初始条件：一元多项式P已存在。操作结果：返回一元多项式P中的项数。}ADTPolynomial如此定义的多项式可以看成是一个有序表(对其数据元素中的指数项而言),则多项式定义中的各个操作均可利用有序表的操作来完成。二、基本操作的实现//多项式

#include"common.h"

#defineflag32767

typedefstructPolyNode{

floa