第二章 线性表091001.ppt

第二章线性表线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继2.1 线性表的类型定义线性表的类型定义1、线性表、线性表线性表线性表(Linear List)：由由n(n0)个数据元素个数据元素(结点结点)a1，a2，an组成的有限序列。组成的有限序列。其中：数据元素的个数其中：数据元素的个数n定义为表的定义为表的长度长度。当当n=0时称为时称为空表空表 常将非空的线性表常将非空的线性表(n0)记作：记作：(a1，a2，an)说明说明：数据元素：数据元素ai(1i n)只是一个抽象的符号，只是一个抽象的符号，其具体含义在不同的情况下可以不同。其具体含义在不同的情况下可以不同。例例1、26个英文字母组成的字母表个英文字母组成的字母表 （A，B，C、Z）例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱.例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况：（6，17，28，50，92，188）例4、一副扑克的点数（2，3，4，J，Q，K，A）从以上例子可看出线性表线性表的逻辑特征逻辑特征是：在非空的线性表，有且仅有一个开始结点在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点有且仅有一个终端结点an，它没有直接后继，它没有直接后继，而仅有一个直接前趋而仅有一个直接前趋a n-1；其余的内部结点其余的内部结点ai(2 i n-1)都有且仅有一都有且仅有一个直接前趋个直接前趋a i-1和一个直接后继和一个直接后继a i+1。线性表是一种典型的线性结构线性表是一种典型的线性结构。2、抽象数据类型线性表线性表的定义ADT List 数据对象数据对象：Dai|aiElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n基本操作基本操作：InitList(&L)初始化初始化 操作结果：构造一个空的线性表L。DestroyList(&L)结构销毁结构销毁 初始条件：线性表L已存在。操作结果：销毁线性表L。引用型操作引用型操作 ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。GetElem(L,i,&e)初始条件：线性表L已存在，1iLengthList(L)操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare()初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第第1个个与e满足满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。ListTraverse(L,visit()初始条件：线性表L已存在。操作结果：依次依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。加工型操作加工型操作 ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(L,i,&e)初始条件：线性表L已存在，1iLengthList(L)操作结果：L中第i个元素赋值同e的值。ListInsert(&L,i,e)初始条件：线性表L已存在，1iLengthList(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1iLengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。ADTListvoid union(List&La，List Lb)La _ len=Listlength(La);Lb_len=Listlength(Lb);for(i=1;i=Lb _ len;i+)GetElem(Lb，i，e);if(!LocateElem(La，e，equal)ListInsert(La，+La _ len，e);例2-1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。3 3、算法讲解、算法讲解算法算法2.2例例2-2 已知线性表已知线性表LA和线性表和线性表LB中的数中的数据元素按值非递减有序排列，现要求将据元素按值非递减有序排列，现要求将LA和和LB归并为一个新的线性表归并为一个新的线性表LC，且且LC中的元素仍按值非递减有序排列。中的元素仍按值非递减有序排列。此问题的算法如下：此问题的算法如下：void MergeList(List La，List Lb，List&Lc)InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb _ len=ListLength(Lb);while(i=La_len)&(j=Lb_len)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，bi);数据的运算是定义在逻辑结构上的，而运算的数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。具体实现则是在存储结构上进行的。2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.2.1顺序表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+L线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*L图示a1a2aibb+L b+L*(I-1)12i内存元素序号 b+L*(n-1)备用空间an n返回typedef struct card int num;char name20;char author10;char publisher30;float price;elemtype;#defineLIST_INIT_SIZE100/线性表初始空间，是单位空间的倍数#defineLISTINCREMENT10/分配空间增量typedefstructElemType*elem;/存储空间起始地址intlength;/当前长度intlistsize;/当前分配空间SqList;例如：SqListl,*pl;下面为用C语言描述的可动态分配的一维数组：2.2.2 顺序表上实现的基本操作顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第些操作，如线性表的构造、第i个元素的访问。个元素的访问。1.1.顺序表的初始化顺序表的初始化:顺序表的初始化即构造一个顺序表的初始化即构造一个空表空表。算法如下：。算法如下：Status InitList_Sq(SqList&L)L.elem=(ElemType*)malloc(sizeof(ElemType)*LIST_INIT_SIZE);if (!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;2、插入插入:线性表的插入运算是指在表的第i(1in+1)个位置上，插入一个新结点e，使长度为n的线性表(a1，ai-1，ai，an)变成长度为n+1的线性表(a1，ai-1，e，ai，an)算法2.4图示StatusListInsert_sq(SqList&L，ElemTypee，inti)/在顺序线性表 L 的第i个元素之前插入新的元/素 e，i的合法值为1iL.length+1,若表/中容量不足，则按该顺序表的预定义增量扩容 if(iL.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.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;+L.length;returnOK;内存a1a2aiai+1an01i-1数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1数组下标n-1in12i元素序号i+1nn+1an-1e返回现在分析算法的复杂度。这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是n-i+1。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。当i=n时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。3、删除删除线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表：(a1，ai-1，ai，ai+1，an)变成长度为n-1的线性表(a1，ai-1，ai+1，an)内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2StatusListDelete(SqList&L，inti,ElemType&e)/在顺序线性表L中删除第 i 个元素，并用e/返回其值，i的合法值为 1iL.length。If(iL.length)returnERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p;-L.length;returnOK;分析：该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若i=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故式中，Qi表示删除表中第i个结点的概率。在等概率的假设下，p1=p2=p3=pn=1/n由此可得：即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。结论1：在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低 4.4.按值查找按值查找 线性表中的按值查找是指在线性表中查找与给定值e相等的数据元素。在顺序表中完成该运算最简单的方法是：从第一个元素 a1 起依次和e比较，直到找到一个与e相等的数据元素，则返回它在顺序表中的存储下标或序号（二者差一）；或者查遍整个表都没有找到与 e 相等的元素，返回-1或0。intLocate_Sq(SqListL,ElemTypee)i=0;/此题与书不同p=L.elem;2.2.3 顺序表应用举例顺序表应用举例while(i=L.length)return-1;elsereturni;/*返回的是存储位置*/算法2.6 例例 1有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc)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(pbdata表示p指向结点的数据域(*p).nextp-next表示p指向结点的指针域 说明：通常将标识链表的头指针说明为头指针说明为LinkListLinkList类型类型的变量，如：LinkListLinkList head head;当head有定义时，NULL，则表示一个空表；第一个结点的地址，即链表的头指针；将指向某结点的指针变量说明为指针变量说明为LNodeLNode *类型类型，如:LNodeLNode *p *p；例如：p=malloc(sizeof(LNode)；free(p)；引用方法引用方法 练习：指针赋值的操作练习：指针赋值的操作指针指向结点指针指向结点 p=qq p指针指向后继指针指向后继 p=q-next指针移动指针移动 p=p-nextqppppq链指针改接链指针改接 p-next=q链指针改接后继链指针改接后继 p-next=q-nextpq练习：指针赋值的操作练习：指针赋值的操作ZHAOQIANSUNLIZHOUWUZHENGWANGH 例例 线性表线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771952数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针110130135160头指针head165170200205hat200.cat135eat170.matNullbat130fat110jat205lat160165例1、已知线形表的链式表示如下：求该线形表 线性表:(bat，cat，eat，fat，hat，jat，lat，mat)bat cat eat mat head 二、基本算法二、基本算法1 1、建立单链表、建立单链表动态地建立单链表的常用方法有如下两种：动态地建立单链表的常用方法有如下两种：1)1)头插法建表头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。到当前链表的表头上，直到读入结束标志为止。StatusStatusCreateList(LinkListLinkList&L&L)/表长不定L=NULL;/先建立一个空的单链表先建立一个空的单链表 scanf(x);while(x!=FLAG)p=(LNode*)malloc(sizeof(LNode);/省略不成功时的语句pdata=x;pnext=L;L=p;scanf(x);returnOK;/CreateList 254218762976182542182542254225在头部插入建立单链表在头部插入建立单链表2、尾插法建表尾插法建表 头插法建立链表虽然算法简单，但头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾前链表的表尾上，为此必须增加一个尾指针指针r r，使其始终指向当前链表的尾结使其始终指向当前链表的尾结点。点。例：初始状态：头指针初始状态：头指针H=NULL，尾指针尾指针 r=NULL;按线性按线性表中元素的顺序依次读入数据元素，不是结束标志时，表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到申请结点，将新结点插入到 r 所指结点的后面，然后所指结点的后面，然后 r 指向新结点（但第一个结点有所不同，读者注意下面算指向新结点（但第一个结点有所不同，读者注意下面算法中的有关部分）。法中的有关部分）。在尾部插入建立单链表H=NULL r=NULL /*初始状态*/29rH7629rH187629rH2542187629rH42187629rH编程分析：编程分析：如果第一个生成的结点是开始结点，如果第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。位置是在其前趋结点的指针域中。如果我们在链表的开始结点之前附加一个结如果我们在链表的开始结点之前附加一个结点，并称它为点，并称它为头结点头结点，那么会带来以下两个优，那么会带来以下两个优点：点：a a、由于开始结点的位置被存放在头结点的由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需作就和在表的其它位置上的操作一致，无需进行特殊处理；进行特殊处理；b b、无论链表是否为空，其头指针是指向无论链表是否为空，其头指针是指向头结点（空表中头结点的指针域为空），因头结点（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了此空表和非空表的处理也就统一了。头结点头结点：在单链表第一个结点前附设一个结点：在单链表第一个结点前附设一个结点线性表为空线性表为空:头结点指针域为空头结点指针域为空;heada1a2头结点an .head空表带头结点的算法如下：StatusCreateList_L(LinkList&L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;r=L;scanf(&x);while(x!=flag)p=malloc(sizeof(LNode);p-data=x;p-next=r-next;r-next=p;r=p;/r指向新的尾结点 scanf(&x);returnOK;练习：如果不带头结点算法如何设计StatusCreateList_L(LinkList&L)/无头结点L=NULL;r=NULL;scanf(&x);while(x!=flag)p=malloc(sizeof(LNode);p-data=x;if(L=NULL)L=p;/第一个结点的处理elser-next=p;/其它结点的处理r=p;/r指向新的尾结点scanf(%d,&x);if(r!=NULL)r-next=NULL;/对于非空表，最后结点的指针域放空指针returnOK;上述算法里动态申请新结点空间时未加错误处理，可作下列处理：p=(LinkList)malloc(sizeof(LNode)if(p=NULL)error(Nospacefornodecanbeobtained);returnERROR;以上算法的时间复杂度均为O(n)。2、查找运算查找运算 1 1）按序号查找）按序号查找 在链表中，即使知道被访问结点的序号在链表中，即使知道被访问结点的序号i i，也不能象也不能象顺序表中那样直接按序号顺序表中那样直接按序号i i访问结点，而只能从链表的访问结点，而只能从链表的头指针出发，顺链域头指针出发，顺链域nextnext逐个结点往下搜索，直到搜索逐个结点往下搜索，直到搜索到第到第i i个结点为止。因此，个结点为止。因此，链表不是随机存取结构链表不是随机存取结构。设单链表的长度为设单链表的长度为n n，要查找表中第要查找表中第i i个结点，仅当个结点，仅当11inin时，时，i i的值是合法的。但有时需要找头结点的位的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第置，故我们将头结点看做是第0 0 个结点，其算法如下：个结点，其算法如下：Status GetElem(LinkList L,int i,ElemType&e)p=L-next;j=1;while(p&jnext;j+;if(!p|ji)return ERROR;e=p-data;return OK;La1a2头结点an .2）查找元素操作（练习）LNode*LocateElem_L(LinkList L，ElemType e)/在 L 所指的链表中查找第一个值和 e 相等的数据元素，/若存在，则返回它在链表中的位置，即指向该数据元/素所在结点的指针；否则返回 NULL p=L;p=L;while(p&p-data!=e)p=p-next;while(p&p-data!=e)p=p-next;return p;/return p;/LocateElemLocateElem_L_LLNode*LocateNode(LinkListhead，ElemTypekey)p=headnext;while(p&pdata!=key)p=pnext;returnp;该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。heada1a2头结点an .同样是按值查找两者有何不同pabes插入：在线性表两个数据元素a和b间插入e，已知p指向as-next=p-next;p-next=s;3 3、插入运算、插入运算 插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如：具体算法如下：StatusListInsert_L(LinkList&L，ElemTypee，inti)p=L;j=0;/头结点while(p&jnext;i+;if(!p|ji-1)error(positionerror);return(ERROR);s=(LinkList)malloc(sizeof(LNode);sdata=e;snext=pnext;pnext=s;returnOK/算法2.94 删除运算删除：单链表中删除b，设p指向apabcp-next=p-next-next;设链表的长度为n，合法的插入位置是1in+1。当i=1时，要找到的是头结点，当i=n+1时，应该找到的是结点an。因此，算法的时间主要耗费在查找操作上，故时间复杂度亦为O(n)。具体算法如下：算法2.10StatusListDelete_L(LinkList&L，inti,ElemType&e)p=L;j=0;while(p-next&jnext;+j;if(!(p-next|ji-1)returnERROR;q=pnext;pnext=qnext;e=q-data;free(q);returnOK;显然此算法的时间复杂度也是O(n)。从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。单链表特点单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢练习与分析：将两个非递减排列的单链表归并为一个新的非递减排列的单链表（算法2.12)先回顾算法2.2已知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：voidmergelist(listla，listlb，list&lc)initlist(lc);i=j=1;k=0;la_len=listlength(la);lb-len=listlength(lb);while(i=la_len)&(j=lb_len)getelem(la，i，ai);getelem(lb，j，bj);if(ai=bj)listinsert(lc，+k，ai);+i;elselistinsert(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，bi);数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。顺序表的实现voidmergelist_sq(sqliatla,sqliatlb,sqliat&lc)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(papa_last&pbpb_last)if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;while(pbnext;pb=lb-next;lc=pa=la;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(lb);静态链表定义如下：#defineMAXSIZE1000/*足够大的数*/typedefstructelemtypedata;intcur;component,SlinkNodeMAXSIZE;这种链表的结点中也有数据域data和指针域cur，与前面所讲的链表中的指针不同，该指针是结点的相对地址(数组的下标)，称之为静态指针，这种链表称之为静态链表。空指针用0表示,表明表尾。数组的第零分量看作头结点。data cur012345三三 静态链表静态链表1zhao3li5qian4sun2zhou0与链表的主要区别动态链表静态链表结点是系统分配用户事先定义结点地址是与该类型同类型的指针表示数组下标存储地址不一定连续地址连续与线性表的主要区别：物理地址连续，但逻辑结构不一定连续。2.3.2 循环链表(circularlinkedlist)循环链表循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点特点：头尾相接无须增加存储量，仅对表的链接方式稍作改变，却使得从表中任一结点出发均可找到表中其他结点，提高查找效率，更加方便灵活。带头结点的循环链表 单循环链表单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。hh空表操作与单链表基本一致,循环条件不同单链表单链表p或或p-next=NULL循环链表循环链表p-next=H 练习：两个用尾指针标识的单循环链表的连接headaheadaheadbheadb headaheada-next=-next=headbheadb-next-next-next-nextfreefree headbheadb-next=-next=headaheada-next?-next?例、在链表上实现将两个线性表例、在链表上实现将两个线性表(a a1 1，a a2 2，a a3 3，aan n)和和(b b1 1，b b2 2，b3b3，b bn n)链接成一个线性表的运算。链接成一个线性表的运算。LinkListconnect(LinkListheada，LinkListheadb)/heada、headb均为用尾指针表示的单循环链表p=headanext;headanext=(headbnext)nextfree(headbnext);headbnext=p;return(headb);2.3.32.3.3双链表（双链表（double Linked listdouble Linked list）双向链表双向链表(double linked list)double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：typedefstructDuLNodeElemTypedata;structDuLNode*prior，*next;DuLNode,*DuLinkList;DuLinkListhead;priordatanextpriorbnextprioranextL空双向循环链表：非空双向 循环链表：LAB和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：(pprior)next=p=(pnext)prior 即结点*p的存储位置既存放在其前趋结点*(pprior)的直接后继指针域中，也存放 在它的后继结点*(pnext)的直接前趋指针域中。bcapStatus ins_dulist(DuLinkList p,ElemType e)s=(DuLinkList)malloc(sizeof(DuLNode);s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;return OK;算法描述算法评价：T(n)=O(1)xSbaP插入：在结点p前插入数据域为x的结点bcaPStatus del_dulist(DuLinkList&L,int i,ElemType&e)if(!(p=GetElemP_dul(L,i)return ERROR;e=&p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);return OK;删除算法描述算法评价：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;小结：如何选取存储结构呢？通常有以下几点考虑：基于存储的考虑顺序表的存储空间是静态分配的,链表不用事先估计存储规模，但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。基于运算的考虑如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。基于环境的考虑顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是考虑的一个因素。总之，两中存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。2.4线性表的应用举例一元多项式的表示及相加一元多项式的表示及相加一元多项式的表示：Pn(x)=P0+P1x+P2x2+Pnxn可用线性表P表示P=(P0,P1,P2,Pn)但对S(x)这样的多项式浪费空间S(x)=1+3x1000+2x20000其中用数据域含两个数据项的线性表表示其存储结构可以用顺序存储结构，也可以用单链表(P P1 1,e,e1 1),(P),(P2 2,e,e2 2),.(),.(P Pm m,e,em m)00e1e2 e1e2 e em m Pi Pi 为为非零系数）非零系数）一般：一般：Pn(xPn(x)=P)=P1 1x xe1e1+P+P2 2x xe2e2+P Pm mx xemem抽象数据类型一元多项式的定义 p40 一元多项式单链表的结点定义typedef struct node float coef;int exp;struct node *next;polynomial;coefexpnext-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多项式相加设设p,q分别指向分别指向A,B中某一结点，中某一结点，p,q初值是第一结点初值是第一结点比较比较p-exp与与q-expp-exp exp:p结点是和多项式中的一项 p后移,q不动p-exp q-exp:q结点是和多项式中的一项结点是和多项式中的一项 将将q插在插在p之前之前,q后移后移,p不动不动p-exp=q-exp:系数系数相加相加0：从：从A表中删去表中删去p,释放释放p,q，p,q后移后移 0：修改：修改p系数域系数域,释放释放q，p,q后移后移直到直到p或或q为为NULL 若若q=NULL，结束结束 若若p=NULL，将将B中剩余部分连到中剩余部分连到A上即可上即可运算规则q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre q-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 1