第3章线性表及其存储结构

1、3.1线性表的基本线性表的基本概念概念3.2线性表的顺序线性表的顺序存储及运算存储及运算3.3线性表的链式线性表的链式存储及运算存储及运算3.1 线性表的基本概念线性表的基本概念 线性表是由线性表是由 n (n0)个数据元素个数据元素 a1 ,a2 ,an 组成的一个有限序列。表中的每一个数据元组成的一个有限序列。表中的每一个数据元素，除了第一个外，有且只有一个前件；除素，除了第一个外，有且只有一个前件；除了最后一个外，有且只有一个后件。即线性了最后一个外，有且只有一个后件。即线性表或是一个空表或可以表示为：表或是一个空表或可以表示为： （a1 ,a2 ,ai ,an）其中其中 ai（i=1,

2、2,n) 是属于数据对象的元素，通常也称其为线性是属于数据对象的元素，通常也称其为线性表中的一个结点。表中的一个结点。 数据元素在线性表中的位置，只取决于它们数据元素在线性表中的位置，只取决于它们自己的序号自己的序号 。非空线性表的结构特征为：非空线性表的结构特征为： 有且只有一个根结点有且只有一个根结点a a1 1 , ,它无前件；它无前件； 有且只有一个终端结点有且只有一个终端结点a an n , ,它无后件；它无后件； 除根结点与终端结点外，其他所有结点除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线有且只有一个前件，也有且只有一个后件。线性表中结点的个数性表中

3、结点的个数n称为线性表的长度。当称为线性表的长度。当 n=0时，称为空表。时，称为空表。 在稍微复杂的线性表中，一个数据元素还在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成。例如，某班的学可以由若干个数据项组成。例如，某班的学生情况登记表是一个复杂的线性表，表中每生情况登记表是一个复杂的线性表，表中每一个学生的情况就组成了线性表中的每一个一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括学号、姓名、性元素，每一个数据元素包括学号、姓名、性别、入学成绩别、入学成绩4个数据项。个数据项。 3.2线性表的顺序存储及其运算线性表的顺序存储及其运算 3.2.1 线性表的顺序存储线

4、性表的顺序存储 线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。 线性表的顺序存储结构具有两个基本特点：线性表的顺序存储结构具有两个基本特点： 线性表中所有元素所占的存储空间是连线性表中所有元素所占的存储空间是连续的；续的； 线性表中各数据元素在存储空间中是按线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。逻辑顺序依次存放的。 假设线性表中的第一个数据元素的存储地假设线性表中的第一个数据元素的存储地址（即首地址）为址（即首地址）为 adr(aadr(a1 1) )，每一个数据元，每一个数据元素占素占k k个字节，则线性表中第个字节，则线性表中第i i个元素个元素a ai

5、i在计在计算 机 存 储 空 间 中 的 存 储 地 址 为 ：算 机 存 储 空 间 中 的 存 储 地 址 为 ：adr(aadr(ai i)=adr(a)=adr(a1 1)+(i-1)k)+(i-1)k长度为长度为n n的线的线性表在性表在计算机计算机中的顺中的顺序存储序存储结构如结构如图图3-13-1所示。所示。 在程序设计语言中，通常定义一个一维数组在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。来表示线性表的顺序存储空间。 应注意数组的基本类型要与线性表中数据元应注意数组的基本类型要与线性表中数据元素的类型相同。素的类型相同。 数组需要根据情况预设足够的大小，同

6、时数组需要根据情况预设足够的大小，同时还需要一个变量指出线性表在数组中的当前还需要一个变量指出线性表在数组中的当前状况，如元素个数或最后一个元素在数组中状况，如元素个数或最后一个元素在数组中的位置等。这两方面的信息共同描述一个顺的位置等。这两方面的信息共同描述一个顺序表，可将它们封装在一起。对序表，可将它们封装在一起。对c语言，顺语言，顺序表可定义如下：序表可定义如下： 对对c语言，顺序表可定义如下：语言，顺序表可定义如下：#define maxlength 50 typedef int elemtype; typedef struct elemtype listmaxlength; int

7、length; seqlist; 今后使用此定义时，今后使用此定义时，maxlength及及elemtype要根据实际问题的需要可重新要根据实际问题的需要可重新选定。选定。 3.2.2顺序表的基本运算顺序表的基本运算 1.1.顺序表的插入顺序表的插入 设长度为设长度为 n 的顺序表为（的顺序表为（a1,a2,ai,an），），要在顺序表的第要在顺序表的第i(1in)个元素个元素ai之前插之前插入一个新入一个新 元素元素x，插入后得到长度为，插入后得到长度为 n+1的的线性表线性表(a1,a2,ai-1,x, ai,an)，即，即 (a1,a2,ai-1, ai, ai+1,an+1)，其中，其

8、中ai 为新插入的元素为新插入的元素x，ai+1 为原表中的为原表中的ai ，其，其余类推，余类推，an+1为原表中为原表中an 。 一般情况下，要在第一般情况下，要在第i(1in)个元素之个元素之前插入一个新元素时，首先要从最后一个元前插入一个新元素时，首先要从最后一个元素开始，直到第素开始，直到第i个元素之间共个元素之间共 n-i+1 个元个元素依次向后移动一个位置。移动结束时，第素依次向后移动一个位置。移动结束时，第i个位置就被空出，然后将新元素插入，插入个位置就被空出，然后将新元素插入，插入结束线性表的长度增结束线性表的长度增1 1。在平均情况下，插入。在平均情况下，插入一个新元素，需

9、要移动表中一半的元素。一个新元素，需要移动表中一半的元素。 注意：注意：若最后一个元素之后没有多余的自由若最后一个元素之后没有多余的自由空间（即表的大小空间（即表的大小n=maxlength）时，那么）时，那么插入一个元素，将会发生上溢。插入一个元素，将会发生上溢。 在顺序表在顺序表l l中的第中的第i i个元素之前插入一个新元个元素之前插入一个新元素素x x的算法的算法insertlistinsertlist描述如下：描述如下： void insertlist(seqlist *l,int i, elemtype x) int j,n=l-length;if(in+1) printf(n i

10、值不合法值不合法); exit(1); if(n=maxlength) printf(n 表空间上溢表空间上溢); exit(1);for(j=n-1;j=i-1;j-) l-listj+1=l-listj;/*数据元数据元素依次向后移动一个位置素依次向后移动一个位置*/ l-listi-1=x; /*插入插入x */ l-length+; /*表长增加表长增加1*/ 2.顺序表的删除顺序表的删除 通常，在长度为通常，在长度为 n 的顺序表中，要删除线的顺序表中，要删除线性表的第性表的第i(1in)个元素个元素ai 。得到长度为。得到长度为 n-1n-1的线性表的线性表( (a a1 1,a

11、a2 2,a ai i-1-1,a ai i+1+1,a an n) ) 。 即即 (a1, a2,ai-1,ai,ai+1,an-1)，其中其中ai 为原表中的为原表中的ai+1 ，其余类推，其余类推，an-1为原表中为原表中an 。 一般情况下，要删除第一般情况下，要删除第i (1in )个个元素，需要从第元素，需要从第i+1 个元素开始，直到第个元素开始，直到第n 个元素之间，共有个元素之间，共有n-i 个元素依次向前移动个元素依次向前移动了一个位置。删除结束后，顺序表的长度就了一个位置。删除结束后，顺序表的长度就缩小了。在平均情况下，要在顺序表中删缩小了。在平均情况下，要在顺序表中删除

12、一个元素，需要移动表中一半的元素。除一个元素，需要移动表中一半的元素。 在顺序表在顺序表l l中删除第中删除第i i个元素并用个元素并用x x 返回其返回其值的算法值的算法deletelistdeletelist描述如下：描述如下： void deletelist(seqlist *l,int i, elemtype *x) int j,n=l-length;if(in) printf( n i值不合法值不合法!); exit(1);*x=l-listi-1; /*将被删元素的值，赋给将被删元素的值，赋给*x */for(j=i;jlistj-1=l-listj; /*元素依次向前移动一个位置

13、元素依次向前移动一个位置 */l-length-; /*表长减少表长减少1 */ 3.顺序表的初始化顺序表的初始化 构造一个空的顺序表构造一个空的顺序表l（即表的初始化）的（即表的初始化）的算法如下：算法如下： void initlist(seqlist *l) /*构造一个空的顺序表构造一个空的顺序表l */ l-length=0;/*线性表长度赋线性表长度赋0值值*/ 4.顺序表的长度顺序表的长度 确定顺序表确定顺序表l的长度算法如下：的长度算法如下：int listlength(seqlist *l) /*求线性表求线性表l的长度的长度*/return(l-length);/*返回返回l

14、的长度的长度*/ 5.5.取顺序表的第取顺序表的第i i个元素个元素 从顺序表中取第从顺序表中取第i（1in）个数据元素的算）个数据元素的算法如下法如下:(用于在表中用于在表中随机的访问任意一个结点随机的访问任意一个结点 )elemtype getelem(seqlist *l,int i)/*取表中第取表中第i个数据元素个数据元素*/if(il-length) printf(n i值非法值非法!); exit(1);return(l-listi-1); 6.6.顺序表的定位运算顺序表的定位运算 根据某个指定的元素值或数据项的值根据某个指定的元素值或数据项的值x，对对顺序表顺序表l进行查找，若

15、进行查找，若l中有元素的值与中有元素的值与x相同，相同，则返回首次找到的元素在则返回首次找到的元素在l中的位置；若查找中的位置；若查找失败，则返回失败，则返回-1的算法如下：的算法如下：int locateelem( seqlist *l, elemtype x)/*查找与查找与x相匹配的元素并返回相匹配的元素并返回其其位置位置*/int i=0,n=l-lenth;if(n=0) printf(n empty list !); exit(1); /*若空表，则返回若空表，则返回*/while(ilisti-1!=x) i+;if(inext=null; / /* *表初值为空表初值为空* *

16、/ / rear=h; / /* *尾指针指向表头结点尾指针指向表头结点* */ /while(ch=getchar()!=n) p=(linklist)malloc(sizeof(listnode); / /* *生成新结点生成新结点* */ / if(!p) printf(n 存储分配失败存储分配失败); exit(1); p-data=ch; p-next=p; / /* *新结点插入表尾新结点插入表尾* */ / rear=p; / /* *尾指针指向新结点尾指针指向新结点* */ /return(h); / /* *返回头指针返回头指针* */ / 后进先出表：后进先出表：在建立单连

17、表时，将每次在建立单连表时，将每次生成的新结点，总是插入到当前链表的表头生成的新结点，总是插入到当前链表的表头结点之后作为当前链表的首结点。若用换行结点之后作为当前链表的首结点。若用换行符符nn作为输入结束标志，则建立带表头作为输入结束标志，则建立带表头结点的后进先出单链表的算法如下：结点的后进先出单链表的算法如下： linklist createlist_fr( ) linklist h,p; char ch; h =(linklist)malloc(sizeof(listnode); /*生成表头结点生成表头结点*/ if(!h) printf(n 存储分配失败存储分配失败); exit(

18、1); h-next=null; /*表初值为空表初值为空*/while(ch=getchar()!=n) p=(linklist)malloc(sizeof(listnode); / /* *生成新结点生成新结点* */ / if(!p) printf(n 存储分配失败存储分配失败); exit(1); p-data=ch; p-next=h-next; h-next=p;/*插入表头结点之后插入表头结点之后*/return(h); /*返回头指针返回头指针*/ 有序单链表：有序单链表：是指原表中结点的数据值是指原表中结点的数据值，按从小到大（或从大到小）的顺序排列。，按从小到大（或从大到小

19、）的顺序排列。为了建立一个有序单链表，每次生成的新结为了建立一个有序单链表，每次生成的新结点，总是插入到当前链表的合适位置。在带点，总是插入到当前链表的合适位置。在带表头结点的单链表中，所有位置上的插入操表头结点的单链表中，所有位置上的插入操作都是一致的，不需要做特殊处理。作都是一致的，不需要做特殊处理。 若用换行符若用换行符nn作为输入结束标志，作为输入结束标志，prepre为指向当前结点前件的指针、为指向当前结点前件的指针、curcur为指向当前为指向当前结点的指针，则建立带表头结点的有序单链结点的指针，则建立带表头结点的有序单链表的算法如下：表的算法如下： linklist create

20、list_or( ) linklist h,pre,cur; /*pre将指向将指向当前结点的前件，当前结点的前件，cur将指向当前结点将指向当前结点*/ char ch; h =(linklist)malloc(sizeof(listnode); / /* *生成表头结点生成表头结点* */ / if(!h) printf(n 存储分配失败存储分配失败); exit(1); h-next=null;/ /* *表初值为空表初值为空* */ /while(ch=getchar( )!=n) pre=h;/ /* *prepre指向当前结点的前件指向当前结点的前件* */ / cur=h-nex

21、t;/ /* *curcur指当前结点指当前结点* */ / while(cur&cur-datanext; cur=(linklist)malloc(sizeof(listnode); / /* *生成新结点生成新结点* */ / if(!cur) printf(n 存储分配失败存储分配失败); exit(1); cur-data=ch; cur-next=pre-next; / /* *新结点插新结点插在在prepre所指结点的后面所指结点的后面* */ / pre-next=cur;/ /* *尾指针指向新结点尾指针指向新结点* */ /return(h); / /* *返回头指针返回头

22、指针* */ / 容易看出，以上容易看出，以上3 3个算法的时间复杂度均个算法的时间复杂度均为为o(n)o(n)。 2 2）查找结点）查找结点 在对单链表进行插入或删除运算时，总是在对单链表进行插入或删除运算时，总是首先要找到插入或删除的位置，这就需要对首先要找到插入或删除的位置，这就需要对线性链表进行扫描查找。线性链表进行扫描查找。 通常，有查找第通常，有查找第i个结点或查找具有给定元个结点或查找具有给定元素值的结点，两种情况。素值的结点，两种情况。 查找单链表中的第查找单链表中的第i i个结点个结点 在带表头结点的单链表中，查找第在带表头结点的单链表中，查找第i个结点个结点。不能像在顺序表

23、中那样，只能从单链表的头。不能像在顺序表中那样，只能从单链表的头指针出发，沿着结点的链域逐个向下，直到搜指针出发，沿着结点的链域逐个向下，直到搜索到第索到第i个结点为止。此时，个结点为止。此时，p指向第指向第i个结点。个结点。 在带表头结点的单链表在带表头结点的单链表h中，查找第中，查找第i个结点个结点的算法如下：的算法如下：linklist getelem(linklist h, int i ) int j=1; / /* *j j累计当前扫描的结点数累计当前扫描的结点数* */ / linklist p; p=h-next; / /* *p p指向第一个结点指向第一个结点* */ / wh

24、ile(p&jnext; j+;if(j=i&p)return(p);/*找到返回指向该结点的指针找到返回指向该结点的指针*/else return(null); /*第第i个结点不存在，返回个结点不存在，返回null*/ 在单链表中查找给定值的结点在单链表中查找给定值的结点 依据给定的数据项的值依据给定的数据项的值x，在带表头结点，在带表头结点的单链表中查找。若找到，则通过的单链表中查找。若找到，则通过i返回首次返回首次找到的结点的位置，同时，返回指向该结点找到的结点的位置，同时，返回指向该结点的指针的指针p。若查找失败，则返回。若查找失败，则返回null。在带表头结点的单链表在带表头结点的

25、单链表h中查找中查找x的算法：的算法：linklist locateelem(linklist h,elemtype x,int *i) linklist p; /*p为指针为指针*/ p=h-next; /*p指向第一个结点指向第一个结点*/ *i=1; while(p&p-data!=x)/*向下搜索向下搜索*/ p=p-next; (*i)+; if(p-data=x)return(p); /*找到返回结点位置找到返回结点位置*/ else return(null);/*没找到返回没找到返回null*/ 以上两个，查找算法的时间复杂度均为以上两个，查找算法的时间复杂度均为o(n)。 3）

26、单链表的插入）单链表的插入 单链表的插入，是指在单链表中插入一个单链表的插入，是指在单链表中插入一个新结点。有两种情况：在单链表的第新结点。有两种情况：在单链表的第i个位置个位置插入一个新结点和在有序单链表中插入一个插入一个新结点和在有序单链表中插入一个新结点。新结点。 在单链表的第在单链表的第i个位置插入一个新结点个位置插入一个新结点 假设单链表中有假设单链表中有n个结点，插入位置个结点，插入位置i的允的允许取值范围为许取值范围为1至至n+1。在第。在第i个位置插入一个位置插入一个新结点，首先，要找到第个新结点，首先，要找到第i-1个结点，然后个结点，然后将新结点插入到第将新结点插入到第i-

27、1个结点之后。若指针个结点之后。若指针pre指向第指向第i-1个结点，个结点，cur指向新结点，插指向新结点，插入就是让新结点的指针域指向原来的第入就是让新结点的指针域指向原来的第 i个结个结点，即点，即cur-next=pre-next，并且修改，并且修改第第i-1个结点的指针域，让其指向新结点。即个结点的指针域，让其指向新结点。即pre-next=curpre-next=cur。插入过程如图。插入过程如图3-63-6所示：所示： h pre cur 图3-6 在单链表的第i个位置插入结点示意图/ai-1aian 0 x 在第在第i i个位置，插入一个值为个位置，插入一个值为x x的新结点算

28、法：的新结点算法： insertlist(linklist h,int i,elemtypeinsertlist(linklist h,int i,elemtype x) x) linklistlinklist pre,cur; pre,cur;pre=getelempre=getelem(h ,i-1);(h ,i-1);/ /* *调用查找函数使调用查找函数使prepre指向第指向第i-1i-1个结点个结点* */ /if(!pre) printf(n i值不合法值不合法);exit(1);cur=(linklist)mallco(sizeof(listnode); /*生成新结点生成新结

29、点*/if(!cur)printf(n 存储分配失败存储分配失败);exit(1); cur-data=x;/*新结点的值为新结点的值为x*/cur-next=pre-next;/ /* *新结点的指针新结点的指针域值指向原来的第域值指向原来的第i i个结点个结点* */ /pre-next=cur;/ /* *第第i-1i-1个结点的指针域值个结点的指针域值指向新结点指向新结点* */ / 在有序单链表中插入一个新结点在有序单链表中插入一个新结点 要在一个带表头结点的有序单链表要在一个带表头结点的有序单链表h h中插入一中插入一个值为个值为x x的新结点。就必须对生成的新结点，依的新结点。就

30、必须对生成的新结点，依据值据值x x的大小在表中找到合适的插入位置，然后的大小在表中找到合适的插入位置，然后将其插入到链表中。算法如下：将其插入到链表中。算法如下：insertorder(linklist h, elemtype x)linklist cur,pre;pre=h;cur=h-next;while(cur&cur-datanext;/*cur指向当前结点指向当前结点*/ cur=(linklist)malloc(sizeof(listnode);/*生成新结点生成新结点*/if(!cur) printf(n 存储分配失败存储分配失败); exit(1); cur-data=x;/

31、*新结点值为新结点值为x*/cur-next=pre-next;/*插入插入新结点新结点*/ pre-next=cur;/*pre指向新结点指向新结点*/ 从单链表插入新结点的过程中，可以看出对从单链表插入新结点的过程中，可以看出对线性链表进行插入操作时，没有发生数据元素线性链表进行插入操作时，没有发生数据元素的移动，只是改变了有关结点的指针域。的移动，只是改变了有关结点的指针域。 在以上两个插入结点的算法中，时间复杂度在以上两个插入结点的算法中，时间复杂度的数量级均为的数量级均为o(n)o(n)。 4）单链表的删除操作）单链表的删除操作 单链表的删除操作，是指在单链表中，删除单链表的删除操作

32、，是指在单链表中，删除包括指定元素的结点。有两种情况：一是删除包括指定元素的结点。有两种情况：一是删除单链表的第单链表的第i i个结点，二是删除单链表中，具个结点，二是删除单链表中，具有给定值有给定值x x的结点。均不移动表中的数据元素的结点。均不移动表中的数据元素，只需改变，被删除结点的前一个结点指针。，只需改变，被删除结点的前一个结点指针。 删除单链表的第删除单链表的第i个结点个结点 设单链表中有设单链表中有n n个结点，删除第个结点，删除第i i个结点个结点时，时，i i的允许取值范围为的允许取值范围为1 1至至n n。与插入类似。与插入类似，首先要找到第，首先要找到第i-1i-1个结点

33、。再用指针个结点。再用指针prepre指向该结点，用指针指向该结点，用指针curcur指向第指向第i i个结点。个结点。然后使第然后使第i-1i-1个结点的指针指向第个结点的指针指向第i+1i+1个结个结点点(pre-next=cur-next)(pre-next=cur-next)。最后用函数。最后用函数freefree释放第释放第i i个结点所占空间。删除过程如个结点所占空间。删除过程如图图3-73-7所示。所示。 在带表头结点的单链表在带表头结点的单链表h中，删除第中，删除第i个个结点的算法如下：结点的算法如下： pre cur h 图3-7 删除单链表的第i个结点示意图 an 0/ai

34、-1aiai+1deletelist1(linklist h,int i, elemtype *x)linklist pre,cur;pre=getelem(h,i-1);/*用用getelem函数找第函数找第i-1个结点并使个结点并使pre指指向它向它*/if(pre=null|pre-next=null) /*判断判断i值是否合法值是否合法*/ printf(n i值不合法值不合法!); exit(1); cur=pre-next;/*cur指第指第i个结点个结点*/pre-next=cur-next;/*使第使第i-1个结点个结点的指针指向第的指针指向第i+1个结点个结点*/*x=cur

35、-data;/*第第i个结点的值由个结点的值由x返回返回*/free(cur); /*释放第释放第i个结点所占的空间个结点所占的空间*/ 删除单链表中具有给定值的结点删除单链表中具有给定值的结点 在带表头结点的单链表在带表头结点的单链表h中，搜索具有给中，搜索具有给定值定值x的结点，若找到，就删除该结点。这种的结点，若找到，就删除该结点。这种删除情况的算法如下：删除情况的算法如下：deletelist2(linklist h ,elemtype x) linklist p,pre;p=h-next;/*p指向链表的第指向链表的第1个结点个结点*/pre=h; /*pre指向第指向第1个结点的前

36、件个结点的前件*/while(p&p-data!=x) /*沿链表指针域，向后查找具有给定值沿链表指针域，向后查找具有给定值x的结点的结点*/pre=p; /*记住前一结点记住前一结点*/p=p-next; /*指针指针p后移一个结点后移一个结点*/ if(p-data=x) pre-next=p-next;/*删除值为删除值为x的的结点结点*/ free(p);/*释放值为释放值为x的结点空间的结点空间*/ else printf(n 链表中没有具有值为链表中没有具有值为x的结点的结点);此算法的时间复杂度的数量级为此算法的时间复杂度的数量级为o(n)。 2.2.循环链表及其基本运算循环链表

37、及其基本运算 从单链表任一结点出发查找其前面的结点是从单链表任一结点出发查找其前面的结点是很困难的。为了克服这一缺点，我们使带表头很困难的。为了克服这一缺点，我们使带表头结点的单链表中的最后一个结点的指针指向头结点的单链表中的最后一个结点的指针指向头结点，使整个链表构成一个环形，这种链式存结点，使整个链表构成一个环形，这种链式存储结构被称为循环链表，如图储结构被称为循环链表，如图3-83-8所示。特别地所示。特别地，只有头结点的循环链表称为空循环链表，如，只有头结点的循环链表称为空循环链表，如图图3-93-9所示。所示。 h 图3-8 循环链表示意图 /a1a2an h 头指针 表头结点 图3

38、-9空循环链表/ 带头结点的循环带头结点的循环链表中，可看出循链表中，可看出循环链表的结构与前环链表的结构与前面所讨论的单链表面所讨论的单链表相比，具有以下两相比，具有以下两个特点：个特点： 1）头结点的数据域为任意或者根据需要来头结点的数据域为任意或者根据需要来设置，头结点的指针域指向线性表的第一个设置，头结点的指针域指向线性表的第一个元素的结点，头指针指向表头结点。元素的结点，头指针指向表头结点。 2）最后一个结点的指针域不是最后一个结点的指针域不是null，而，而是指向表头结点。即在循环链表中没有空指是指向表头结点。即在循环链表中没有空指针，所有结点的指针构成了一个环状链。针，所有结点的

39、指针构成了一个环状链。 在循环链表中，在循环链表中， 只要指出表中任何一个结只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。所有的结点，而线性单链表做不到这一点。 循环链表的插入和删除的方法与线性单链循环链表的插入和删除的方法与线性单链表基本相同，不再赘述。表基本相同，不再赘述。 只须注意一点：在单链表的结构中，空表只须注意一点：在单链表的结构中，空表的条件是的条件是h-next=null,而在循环链表结构而在循环链表结构中，空表的条件是中，空表的条件是h-next=h。 3. 双向链表双向链表 从循环链表

40、的结构特征可看出，若要找一从循环链表的结构特征可看出，若要找一个结点的直接前件结点需要兜一个圈子才行个结点的直接前件结点需要兜一个圈子才行，这当然是很不方便的。就像乘单向环行的，这当然是很不方便的。就像乘单向环行的公交车一样，公交车一样，若坐过了站，就要多坐许多站若坐过了站，就要多坐许多站 才能到达预定的地点。因此，任何城市的公交才能到达预定的地点。因此，任何城市的公交车，除单行道外，都是双向行驶的。为类似的车，除单行道外，都是双向行驶的。为类似的目的，可以将单向链表改为双向链表。目的，可以将单向链表改为双向链表。 图3-10双向链表结点结构 prior data next 双向链表的每个结点

41、含有两个指针域：一双向链表的每个结点含有两个指针域：一个指向其直接前件结点，称为个指向其直接前件结点，称为prior；一个指；一个指向其直接后件结点，称为向其直接后件结点，称为next。双向链表结点。双向链表结点的结构如图的结构如图3-10所示，双向链表的逻辑结构如所示，双向链表的逻辑结构如图图3-11所示。 h 图3-11 双向链表示意图0 0 有了两个方向的链指针之后，在链表上进有了两个方向的链指针之后，在链表上进行访问非常方便，但是在双向链表上进行插行访问非常方便，但是在双向链表上进行插入和删除运算，要涉及两个指针的链接，故入和删除运算，要涉及两个指针的链接，故比单链表的插入与删除运算复

42、杂些。比单链表的插入与删除运算复杂些。 3.3.33.3.3线性链表应用举例线性链表应用举例 设多项式设多项式pn(x)=a0+a1x+a2x2+anxn 其其中中ai(i=0, ,1, ,2, , ,n)是是x的的i次幂的系数（即次幂的系数（即x的幂指数为的幂指数为i）。线性表（）。线性表（ a0, ,a1, ,a2, , ,an ）可唯一确定多项式）可唯一确定多项式pn(x)。两个多项式相加两个多项式相加，如果采用顺序存储结构来存储此线性表，由如果采用顺序存储结构来存储此线性表，由于多项式中可能有多项的系数为于多项式中可能有多项的系数为0，顺序存储，顺序存储就会浪费大量存储空间。故应采用单链表来存就会浪费大量存储空间。故应采用单链表来存储该线性表。在单链表中，每个结点设储该线性表。在单链表中，每个结点设3个域个域，