【教学课件】第2章线性表.ppt

2.1 线性表的逻辑结构2.2 线性表的顺序表示和实现2.3 线性表的链接表示和实现2.4 一元多项式的表示及相加,目录,第 二 章 线性表,线性结构特点：,空或者只有一个结点。或者 1、存在唯一的一个被称之为“第一个”的结点。2、存在唯一的一个被称之为“最后一个”的结点。3、除第一个结点之外，每个结点均只有一个前驱结点。4、除最后一个结点之外，每个结点均只有一个后继结点。,2.1 线性表的逻辑结构,线性表(Linear_list)是a1,a2,an,n(0)个数据元素的有限序列。对n0,除了第一个和最后一个元素外，其余各节点有且仅有一个直接前驱和直接后继。特点：同一性 有限性 有序性 n=0 称空表 n0 常记作（a1,a2,an）n:称线性表的表长,1.线性表的定义,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2）,i,j,k,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2）,i,j,k,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）,i,j,k,LA（3，5，8，11）LB（2，6，8，9，11，15，20）LC（2，3，5，6，8，8，9，11，11，15，20）合并的方法如下：,2.基本操作：插入、删除、查找 e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC，并仍为递增序。,Void Mergelist(List La,list Lb,list/Mergelist La Lb,时间复杂性:和表 LA、LB 中的结点个数（之和）成正比。,合并操作的算法实现,1、物理存储位置的计算：顺序表示：在物理位置上紧靠在一起。如用数组表示线性表。,设第一个结点的存储地址为 LOC(a1),余类推。设每个结点占用 L 个单元。则：,an,ai-1,a2,a1,ai,LOC(ai)=LOC(ai-1)+L=LOC(ai-2)+2L=LOC(ai-(i-1)+(i-1)L=LOC(a1)+(i-1)L,随机存取：访问任何一个数据元素或结点花费同样多时间。,2.2 线性表的顺序表示和实现,an,ai-1,a2,a1,ai,2、在 c 中的表示和实现：,#define MAXSIZE 100typedef struct data type dataMAXSIZE;int len;seqlist;,表示：,建立一个顺序存储的线性表：,seqlist*init_seqlist()seqlist*L;L=malloc(sezeof(seqlist);L-len=-1;(L.len=-1,表示线性表中无数据元素)return L;/init_seq;,主函数调用：Main()Seqlist*L;L=init_seqlist();./生成顺序存/储的线性表,3、插入和删除的时间复杂性分析：,插入（在线性表的第 i 个位置上插入x）：,251247893614,123456789,25124799893614,99插入,251247893614,251247893614,251247893614,插第 4 个结点之前，移动 6（41）次。在一般情况下，插在第 i 个结点之前，移动 n-(i-1)次。,3、插入和删除的时间复杂性分析：,插第 4 个结点之前，移动 6（41）次。在一般情况下，插在第 i 个结点之前，移动 n-(i-1)次 插在第 1 个结点之前，移动 n 次 插在第 2 个结点之前，移动 n-1 次 插在第 i 个结点之前，移动 n-(i-1)次插在第 n 个结点之前，移动 1 次。插在第 n 个结点之后，移动 0 次。,总共 n+1 种情况,在长度为 n 的线性表中插入一个结点的平均次数为：(n-i+1)/(n+1)=n/2 时间复杂性为 O(n)。,i=1,n,3、插入和删除的时间复杂性分析：,删除（删除线性表的第 i 个结点）：,251247893614,123456789,2512473614,2512473614,2512473614,删除第 4 个结点，移动 64 次。在一般情况下，删除第 i 个结点，移动 n-i 次。,删除,3、插入和删除的时间复杂性分析：,删除第 4 个结点，移动 64 次。在一般情况下，删除第 i 个结点，移动 n-i 次 删除第 1 个结点，移动 n-1 次 删除第 2 个结点，移动 n-2 次 删除第 i 个结点，移动 n-i 次删除第 n 个结点，移动 0 次。,总共 n 种情况,在长度为 n 的线性表中删除一个结点的平均次数为：(n-i)/n=(n-1)/2 时间复杂性为 O(n)。,i=1,n,另外，通过 KEY 查找结点，代价 O(n)。查找第 i 个结点，代价O(1)。,3、插入、删除、查找的实现算法：,插入,Int insert_seqlist(seqlist*L,int i,datatype x)if(L-len=MAXSIZE-1)printf(“overflow”);return(-1);/*表空间已满，不能插入*/if(iL-len+1)printf(“Infeasible”);return(0);/*检查插入位置的正确性*/if(j=L-len;j=I;j-)L-dataj+1=L-dataj;/*结点移动*/L-datai-1=x;/*新元素插入*/L-len+;/*表的长度增加*/return(1);/*插入成功，返回*/initList_Sq;线性表的第 i 个结点存于 L-elemi-1 之中。,3、插入、删除、查找的实现算法：,删除,将第i个元素从线性表中去掉步骤：将ai+1an顺序上移 修改len指针（相当于修改表长），使之指向最后一个元素,Int Delete_seqlist(seqlist*L,int i)if(iL-len+1)printf(“No this value of i”);return(0);for(j=i;jlen;j+)L-dataj-1=L-dataj;/*向上移动*/L-len-;return(1);/*删除成功*/,3、插入、删除、查找的实现算法：,查找,查找算法？（同学自己编写）,4、线性表应用举例：,（1）.将顺序表（a1,a2,an）重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值均比a1大（这里假设数据元素的类型具有可比性，不妨设为整型）。,（2）.有顺序表A和B,其元素均按从小到大的升序排列，编写算法将他们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。,顺序存储结构的优点和缺点,优点：1.无需为表示结点间的逻辑关系而增加额外的存储空间；2.可方便地随机存取表中的任一元素。缺点：1.插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；2.由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。,2.3 线性表的链式存储,链表定义：采用链式存储结构的线性表称为链表。现在我们从两个角度来讨论链表：1.从实现角度看，链表可分为动态链表和静态链表；2.从链接方式的角度看，链表可分为单链表、循环链 表和双链表。,2.3.1 单链表 2.3.2 单链表上的基本运算 2.3.3 循环链表 2.3.4 双向链表*2.3.5 静态链表 2.3.6 顺序表和链表的比较,链表,2.3.1 单链表,结点（Node）为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node）。单链表：链表中的每个结点只有一个指针域，我们将这种链表称为单链表。单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。头指针：指向链表头结点的指针。,单链表的示例图,带头结点的单链表示意图,有时为了操作的方便，还可以在单链表的第一个结点之前附设一个头结点。带头结点的空单链表 带头结点的单链表,单链表的存储结构描述,typedef struct Node/*结点类型定义*/ElemType data；struct Node*next；Node,*LinkList；/*LinkList为结构指针类型*/,2.3.2 单链表上的基本运算,线性表的基本运算：建立单链表 单链表查找 单链表插入操作 单链表删除 算法应用示例：求单链表的长度 求两个集合的差,建立单链表,头插法建表算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。,头插法建表算法,Linklist CreateFromHead()LinkList L;Node*s;int flag=1;/*设置一个标志，初值为1，当输入“$”时，flag为0，建表结束*/L=(Linklist)malloc(sizeof(Node)；/*为头结点分配存储空间*/L-next=NULL;while(flag)c=getchar();if(c!=$)/*为读入的字符分配存储空间*/s=(Node*)malloc(sizeof(Node);s-data=c;s-next=L-next;L-next=s;elseflag=0;,尾插法建表,C1,s,r,L,尾插法建表算法,Linklist CreateFromTail()/*将新增的字符追加到链表的末尾*/LinkList L;Node*r,*s;int flag=1;L=(Node*)malloc(sizeof(Node);/*为头结点分配存储空间*/L-next=NULL;r=L;/*r指针始终动态指向链表的当前表尾*/while(flag)/*标志，初值为1。输入“$”时flag为0，建表结束*/c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s else flag=0;r-next=NULL;,单链表查找,按序号查找 算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L-next）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点（p=L-next），用j做记数器，累计当前扫描过的结点数（初值为0），当j=i 时，指针p所指的结点就是要找的第i个结点。算法实现，算法演示。,按序号查找算法实现,/*在带头结点的单链表L中查找第i个结点，若找到(1in)，则返回该结点的存储位置;否则返回NULL*/Lnode*Get(LinkList L,int i)Lnode*p；p=L；j=0；/*从头结点开始扫描*/while(p-next!=NULL&(jnext；j+；/*扫描下一结点*/*已扫描结点计数器*/if（i=j）return p；/*找到了第i个结点*/else return NULL；/*找不到，i0或in*/,按值查找算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。算法实现，算法演示。,按值查找算法实现,/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/Node*Locate(LinkList L,ElemType key)Node*p;p=L-next;/*从表中第一个结点比较*/while(p!=NULL)if(p-data!=key)p=p-next;else break;/*找到结点key，退出循环*/return p;,单链表插入操作,算法描述：要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向第i个结点。,s,a1,ai-1,ai,s,pre,L,单链表插入操作算法实现,void InsList(LinkList L,int i,ElemType e)/*在带头结点的单链表L中第i个结点之前插入值为e的新结点。*/Node*pre,*s;pre=L;int k=0;while(pre!=NULL,单链表删除,算法描述：欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使p指向第i-1个结点，而后删除第i个结点并释放结点空间。,单链表删除算法实现,void DelList(LinkList L,int i,ElemType*e)/*在带头结点的单链表L中删除第i个元素，并保存其值到变量*e中*/Node*p,*r;p=L;int k=0;while(p-next!=NULL/*释放被删除的结点所占的内存空间*/,求单链表的长度,算法描述：可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点,从第一个元素开始“数”，一直“数”到最后一个结点（p-next=NULL）。intListLength(LinkList L)/*L为带头结点的单链表*/Node*p;p=L-next;j=0;/*用来存放单链表的长度*/while(p!=NULL)p=p-next;j+;return j;算法演示链接。,求两个集合的差,已知：以单链表表示集合，假设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求两个集合的差，即A-B。算法思想：由集合运算的规则可知，集合的差A-B中包含所有属于集合A而不属于集合B的元素。具体做法是，对于集合A中的每个元素e，在集合B的链表LB中进行查找，若存在与e相同的元素，则从LA中将其删除。算法实现算法演示链接,求两个集合的差算法实现,void Difference(LinkList LA,LinkList LB)/*此算法求两个集合的差集*/Node*pre;*p,*r;pre=LA;p=LA-next;/*p向表中的某一结点，pre始终指向p的前驱*/while(p!=NULL)q=LB-next;/*扫描LB中的结点，寻找与LA中*P结点相同的结点*/while(q!=NULL,2.3.3 循环链表,循环链表(Circular Linked List)是一个首尾相接的链表。特点：将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。带头结点循环单链表示意图。,带头结点的循环单链表示意图,空链表,带头结点的一般形式,带尾结点的一般形式,循环单链表合并为一个循环单链表,已知：有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。算法思想：先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾Q，使它的链域指向第一个表的头结点。,循环单链表合并算法实现,LinkList merge_1(LinkList LA,LinkList LB)/*此算法将两个链表的首尾连接起来*/Node*p,*q;p=LA;q=LB;while(p-next!=LA)p=p-next;/*找到表LA的表尾*/while(q-next!=LB)q=q-next;/*找到表LB的表尾*/q-next=LA;/*修改表LB 的尾指针，使之指向表LA 的头结点*/p-next=LB-next;/*修改表LA的尾指针，使之指向表LB 中的第一个结点*/free(LB);return(LA);,2.3.4 双向链表,双向链表：在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双(向)链表(Double Linked List)。双向链表的结构定义：typedef struct Dnode ElemType data；struct DNode*prior，*next；DNode,*DoubleList；,双链表的结构定义,双链表的结点结构,双向循环链表示意图,空的双向循环链表,非空的双向循环链表,双向链表的前插操作,算法描述：欲在双向链表第i个结点之前插入一个的新的结点，则指针的变化情况如图所示。,双向链表的前插操作算法实现,void DlinkIns(DoubleList L,int i,ElemType e)DNode*s,*p;/*首先检查待插入的位置i是否合法*/*若位置i合法，则让指针p指向它*/s=(DNode*)malloc(sizeof(DNode);if(s)s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;return TRUE;else return FALSE;算法演示连接。,双向链表的删除操作,算法描述：欲删除双向链表中的第i个结点，则指针的变化情况如图所示。,双向链表的删除操作算法实现,intDlinkDel(DoubleList L,int i,ElemType*e)DNode*p;/*首先检查待插入的位置i是否合法*/*若位置i合法，则让指针p指向它*/*e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);return TRUE;,双向链表应用举例,已知：设一个循环双链表L=（a,b,c,d）编写一个算法将链表转换为L=（b,a,c,d）。算法思想：实际上是交换表中前两个元素的次序。算法实现：voidswap(DLinkList L)DNode*p,*q,*h;h=L-next;/*h指向表中的第一个结点，即a*/p=h-next;/*p指向b结点*/q=h-prior;/*保存a 结点的前驱*/h-next=p-next;p-next-prior=h;/*变换指针指向*/p-prior=q;p-next=h;L-next=p;,*2.3.5 静态链表,基本概念：游标实现链表的方法：定义一个较大的结构数组作为备用结点空间（即存储池）。当申请结点时，每个结点应含有两个域：data域和next域。data域存放结点的数据信息，next域为游标指示器，指示后继结点在结构数组中的相对位置（即数组下标）。数组的第0个分量可以设计成表的头结点，头结点的next域指示了表中第一个结点的位置，为0表示静态单链表的结束。我们把这种用游标指示器实现的单链表叫做静态单链表(Static Linked List)。静态链表的结构定义，静态链表的插入和删除操作示例。基本操作：初始化、分配结点与结点回收、前插操作、删除。,静态链表的结构定义,#define Maxsize=链表可能达到的最大长度typedef struct ElemType data;int cursor;Component,StaticListMaxsize;,静态链表的插入和删除操作示例,已知：线性表 a，b，c，d，f，g，h，i），Maxsize=11,静态链表初始化,算法描述：初始化操作是指将这个静态单链表初始化为一个备用静态单链表。设space为静态单链表的名字，av为备用单链表的头指针，其算法如下：void initial(StaticList space,int*av)int k;space0-cursor=0;/*设置静态单链表的头指针指向位置0*/for(k=0;kcursor=k+1;/*连链*/spaceMaxsize-1=0;/*标记链尾*/*av=1;/*设置备用链表头指针初值*/,静态链表分配结点与结点回收,分配结点int getnode(int*av)/*从备用链表摘下一个结点空间，分配给待插入静态链表中的元素*/int i=*av;*av=space*av.cur;return i;结点回收void freenode(int*av,int k)/*将下标为 k的空闲结点插入到备用链表*/spacek.cursor=*av;*av=k;,静态链表前插操作,算法描述：1、先从备用单链表上取一个可用的结点；2、将其插入到已用静态单链表第i个元素之前。void insbefore(StaticList space,int i,int*av)j=*av;/*j为从备用表中取到的可用结点空间的下标*/av=spaceav-cursor;/*修改备用表的头指针*/spacej-data=x;k=space0-cursor;/*k为已用静态单链表的第一个元素的下标值*/for(m=1;mcursor;spacej-cursor=spacek-cursor;/*修改游标域*/spacek-cursor=j;,静态链表删除,算法描述：首先寻找第i-1个元素的位置，之后通过修改相应的游标域进行删除；在将被删除的结点空间链到可用静态单链表中，实现回收。void delete(StaticList space;int i;int*av)k=space0-cursor;for(m=1,mcursor;j=spacek-cursor;spacek-cursor=spacej-cursor;/*从删除第i个元素*/spacej-cursor=*av;/*将第i 个元素占据的空间回收*/av=j;/*置备用表头指针以新值*/,2.3.6 顺序表和链表的比较,1基于空间的考虑 2基于时间的考虑 3基于语言的考虑,2.4 一元多项式的表示及相加,一个一元多项式Pn(x)可按升幂的形式写成：Pn(x)=p0+p1x+p2x2+p3x3+pnxn 在计算机内，可以用一个线性表P来表示：P=（p0，p1，p2，pn）用单链表存储多项式的结点结构如下：typedef struct Polynode int coef;int exp;Polynode*next;Polynode,*Polylist;,建立多项式链表,算法描述：输入多项式的系数和指数，用尾插法建立一元多项式的链表。Polylist polycreate()Polynode*head,*rear,*s;int c,e;rear=head=(Polynode*)malloc(sizeof(Polynode);/*建立多项式的头结点，rear 始终指向单链表的尾*/scanf(“%d,%d”,多项式的单链表表示示意图,说明：图示分别为多项式A(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x8,两个多项式相加,运算规则：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。算法实现，算法演示若p-expexp，则结点p所指的结点应 是“和多项式”中的一项，令指针p后移；若p-expq-exp，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移；若p-exp=q-exp，则将两个结点中的系数相加，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点。,两个多项式相加算法实现,void polyadd(Polylist polya;Polylist polyb)/*p和q分别指向polya和polyb链表中的当前计算结点*/*pre指向和多项式链表中的尾结点*/while p!=NULL&q!=NULL）if（p-expexp）/*将p结点加入到和多项式中*/else if(p-exp=q-exp）/*若指数相等，则相应的系数相加。若系数为0则删除p，q节点*/else/*将q结点加入到和多项式中*/./*将多项式polya或polyb中剩余的结点加入到和多项式中*/,