n n线性表线性表的类型的类型定义定义n n线性表线性表的的顺序表示和实现顺序表示和实现n n线性表线性表的的链式表示和实现链式表示和实现n n一元多项式一元多项式的的表示表示及相加及相加 线性表是最简单常用的数据结构，顺序存储结构,链式存储结构也是应用中最常用的存储方法。这一部分内容和方法掌握了，有助于理解和掌握后续章节的内容：如栈、队列、串是特殊的线性表，数组和广义表是线性表的扩展；有助于理解和掌握树和图等复杂的数据结构的存储结构和操作算法，因为树和图的存储结构大多或是这两种存储结构的扩充，或是它们的组合，因此这一章的内这一章的内容非常重要容非常重要，应很好地学习、理解和掌握。线性表的类型定义线性表的类型定义具有相同特性的数据元素的有限序列。具有相同特性的数据元素的有限序列。(a1,ai1,ai,ai+1,an)线性表中的元素个数n称为线性表的长度。线性表的记号线性表的记号第i个元素ai在表中的位序线性表的特点线性表的特点除第一个元素外，其他每一个元素除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。素有一个且仅有一个直接后继。ADTList数据对象数据对象:D=ai|aiElemSet,i=1,2,n,n0数据关系数据关系:R1=|ai-1,aiD,i=2,nADT线性表线性表的定义的定义基本操作基本操作:InitList(&L)/初始化初始化操作结果操作结果:构造一个空的线性表构造一个空的线性表L。DestroyList(&L)/撤销撤销初始条件初始条件:线性表线性表L已存在已存在。操作结果操作结果:销毁线性表销毁线性表L。ClearList(&L)/置空置空初始条件初始条件:线性表线性表L已存在已存在。操作结果操作结果:将将L重置为空表重置为空表。ListEmpty(L)/判空判空初始条件初始条件:线性表线性表L已存在已存在。操作结果操作结果:若若L为空表为空表,则返回则返回TRUE,否则返回否则返回FALSE。ListLength(L)/求长求长初始条件初始条件:线性表线性表L已存在已存在。操作结果操作结果:返回返回L中数据元素的个数中数据元素的个数。GetElem(L,i,&e)/读元素读元素初始条件初始条件:线性表线性表L已存在已存在,1iListLength(L)。操作结果操作结果:用用e返回返回L中第中第i个元素的值个元素的值。LocateElem(L,e,compare()/查找查找(定位定位)初始条件初始条件:线性表线性表L已存在已存在,compare()是数据是数据元素判定函数元素判定函数。操作结果操作结果:返回返回L中第中第1个与个与e满足关系满足关系compare()的数据元素的位序的数据元素的位序,若这若这样的数据元素不存在样的数据元素不存在,则返回值为则返回值为0。NextElem(L,cur_e,&next_e)/求后继求后继初始条件初始条件:线性表线性表L已存在已存在。操作结果操作结果:若若cur_e是是L的数据元素的数据元素,且不是且不是最最后一后一个个,则用则用next_e返回它的后继返回它的后继,否则操作失败否则操作失败,next_e无定义无定义。 PriorElem(L,cur_e,&pre_e)/求前驱求前驱初始条件初始条件:线性表线性表L已存在已存在。操作结果操作结果:若若cur_e是是L的数据元素的数据元素,且不是且不是第第一一个个,则用则用pre_e返回它的前驱返回它的前驱,否则操作失败否则操作失败,pre_e无定义无定义。 ListDelete(&L,i,&e)/删除删除初始条件初始条件:线性表线性表L已存在且非空已存在且非空,1iListLength(L)。操作结果操作结果:删除删除L的第的第i个数据元素个数据元素,并并用用e返回其值返回其值,L的长度减的长度减1。ListInsert(&L,i,e)/前插前插(入入)初始条件初始条件:线性表线性表L已存在已存在,1iListLength(L)+1。操作结果操作结果:在在L中第中第i个位置之前插入新的个位置之前插入新的数据数据元元素素e,L的长度加的长度加1。ListTraverse(L,visit()/遍历遍历初始条件初始条件:线性表线性表L已存在已存在。操作结果操作结果:依次对依次对L的每一个数据元的每一个数据元素调用函数素调用函数visit()。一旦一旦visit()失败失败,则操作失败则操作失败。 ADTList例例2-0 线性表的复制线性表的复制voidListCopy(ListLa,List&Lb)/将已存在的线性表La复制到线性表Lb中InitList(&Lb);La_len=ListLength(La);Lb_len=0;GetElem(La,i,e);/读La中第i个元素的值赋给eListInsert(Lb,+Lb_len,e);/在Lb的表尾插入新元素e,Lb的表长增1/ListCopyfor(i=1;i=La_len;i+)P20 例例2-1 利用线性表求集合的并利用线性表求集合的并 (1)集合集合A - List la ,List la ,集合集合B - List lbList lb算法的基本思想算法的基本思想:扩大la(就地工作),将存在于lb中而不存在于la中的元素插入la中(插入位置可随意)。 集合集合 A（或或 B）中的元素相异中的元素相异, la（或或 lb）亦然亦然。具体做法具体做法:从lblb中依次读出每一个元素,并在lala 中查访,若不存在,则添入lala中。P20 例例2-1 利用线性表求集合的并利用线性表求集合的并(2)voidunion(List&La,ListLb)/将所有在La中但不在Lb中的元素插入到La中La_len=ListLength(La);Lb_len=ListLength(Lb);GetElem(Lb,i,e);/读Lb中第i个元素的值赋给eif(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在与e相同的元素,则插入之/unionfor(i=1;i=Lb_len;i+)本算法时间复杂度：O（ListLength(La)ListLength(Lb)） P20 例例2-1 有序表的归并有序表的归并 (1) 将两个均为升序线性表la 、lb合并成一个新的升序线性表lc算法的基本思想算法的基本思想: :先设lclc为空表，然后按从表头到表尾顺序对la la 、lblb中的当前元素a a、b b进行比较，将较小者插到lclc的表尾。具体做法具体做法具体做法具体做法: :1) 设置两个指针i i 、j j分别为分别为la la 、lblb中当前进行比较的元素a a、b b的位序，i i和j j的初值均为，再设置指针k k表示lclc的表尾位置，初值为 。La= La= (3,5(3,5 ,8,8 ,11),11)Lb= Lb= (2(2 ,6,8,6,8 ,9,9 ,11,11 ,15,15 , ,20)20)LcLc= = ()()i ij jk k P20 例例2-1 有序表的有序表的归并归并 (2)2)元素a a、b b比较后，将较小者插入lclc ，同时应后移较小者所在线性表（lala或lb lb ）的指针（i i或j j）。La= La= (3,5(3,5 ,8,8 ,11),11)Lb= Lb= (2(2 ,6,8,6,8 ,9,9 ,11,11 ,15,15 , ,20)20)LcLc= = (2,3,5,6(2,3,5,6) )i ij jk kLa= La= (3,5(3,5 ,8,8 ,11),11)Lb= Lb= (2(2 ,6,8,6,8 ,9,9 ,11,11 ,15,15 , ,20)20)LcLc= = (2,3)(2,3)i ij jk ki i,8), ,5 5) )k kk ki i P20 例例2-1 有序表的归有序表的归并并 (3)3)当一个表的所有元素均已插入lclc后，另一个表尚有残尾，应将其接到lclc之后。La= La= (3,5(3,5 ,8,8 ,11),11)Lb= Lb= (2(2 ,6,8,6,8 ,9,9 ,11,11 ,15,15 , ,20)20)LcLc= = (2(2 ,3,5,3,5 ,6,8,6,8 ,8,8 ,9,9 ,11),11)i ij jk k1111 ,15,15 , ,2020,11,11 ,15,15 , ,20)20)P21 例例2-1 有序表的归并有序表的归并 (4)voidMergeList(ListLa,ListLb,List&Lc)/将两个均为升序表la 、lb归并为新的升序表lcInitList(Lc);i=1;j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);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)&(j=Lb_len)/La和Lb均有待插元素while(i=La_len)/La尚有剩余元素（残尾）GetElem(La,i+,ai);ListInsert(Lc,+k_,ai);while(j+=+时时 0 0, ,) )(a(a时时 0 0,) )(a(ailiLOCiiLOC1线性表的顺序结构的特点线性表的顺序结构的特点以元素的“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。 由此,只要确定了线性表的基地址,线性表中的任一数据元素都可随机存取。顺序表的类型顺序表的类型定义定义#defineLIST_INIT_SIZE100/线性表存储空间的初始分配量#defineLISTINCREMENT10/线性表存储空间的分配增量typedefstructElemType*elem;/线性表存储空间基址intlength;/当前线性表长度intlistsize;/当前分配的线性表存储容量/（以sizeof(ElemType)为单位）SqList;存放线性表元素的一维数组设设A=（a1,a2,a3,.an）是一线性表，是一线性表，L是是SqList类型的结构变量，用于存放线性表类型的结构变量，用于存放线性表A，则则L在内存的状态如图所示：在内存的状态如图所示：a1a2ai-1aiai+1an01i-2i-1in-199L.elemL.lenghtL.listsizeL.elemLn100注意注意:A中第中第i个元素个元素ai是是L.elemi-1 顺序表的基本操作算法1.初始化初始化StatusInitList_Sq(SqList&L)/构造一个空的顺序线性表L。L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)if(!L_elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE; returnOK;由于在顺序顺序表中逻辑关系相邻的结点物理位置上也相邻，因此在进行插入插入和删除删除操作时须移动须移动一些元素。 2.插入插入插入元素时，线性表逻辑结构发生的变化逻辑结构发生的变化:(a1,ai-1,ai,an)变为变为(a1,ai-1,e,ai,an)a1a2ai-1aiana1a2ai-1aie an,表的长度增1插入算法的主要步骤插入算法的主要步骤:1）若若i不合法，算法结束，并返回不合法，算法结束，并返回0；否；否则转则转2）；2）若当前存储空间已满，增加分配；若当前存储空间已满，增加分配；3）将第将第i个元素及之后的元素从表尾往前个元素及之后的元素从表尾往前依次向后移动一个位置依次向后移动一个位置;4）插入新的元插入新的元素素;5）表长表长+1。StatusListInsert_sq(Sqlist&L,inti,ElemTypee)/在顺序表L中第i个位置之前插入新的元素eif(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);/q为插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;+L.length;returnOK;/ListInsert_sq插入位置插入位置移动元素个数移动元素个数1n2n-1in-i+1n1n+10算法时间复杂度分析算法时间复杂度分析算法时间复杂度取决于移动元素的个数，移动元算法时间复杂度取决于移动元素的个数，移动元素的个数不仅与表长有关，而且与插入位置有关。素的个数不仅与表长有关，而且与插入位置有关。a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an n0 01 1i-1i-1i-2i-2n-1n-1 设在线性表的任何位置插入元素的概率相同，即设在线性表的任何位置插入元素的概率相同，即p pi i= 1/(n+1) = 1/(n+1) ，则则设设pi为在第为在第i个元素之前插入元素的概率，在长度个元素之前插入元素的概率，在长度为为n的顺序表中插入一个元素，所需移动元素个数数的顺序表中插入一个元素，所需移动元素个数数学期望值为：学期望值为：由此可见由此可见在顺序表中插入一个元素在顺序表中插入一个元素，平均要移动表的一半元素。，平均要移动表的一半元素。表长为表长为n的顺序表，插入算法的时间复杂度为的顺序表，插入算法的时间复杂度为O（n）3.删除删除删除元素时，线性表逻辑结构发生的变化逻辑结构发生的变化:(a1,ai-1,ai,ai+1,an)变为变为(a1,ai-1,ai+1,an)a1a2ai-1aiai+1ana1a2ai-1 an,表的长度减1ai+1删除算法的主要步骤删除算法的主要步骤:1）若若i不合法或表不合法或表L空，算法结束，并返空，算法结束，并返回回0；否则转；否则转2）2）将第将第i个元素之后的元素（不包括第个元素之后的元素（不包括第i个个元素）从元素）从ai+1往后依次向前移动一个位置往后依次向前移动一个位置;3）表长表长-1。StatusListDelete_Sq(SqList&L,inti,ElemType&e)if(iL.length)returnERROR;p=&(L.elemi-1);/p为被删除元素的位置e=*p;q=L.elem+L.length-1;/表尾元素的位置for(+p;p=q;+p)*(p-1)=*p;-L.length;/表长减1returnOK;/ListDelete_Sq删除算法的移动平均次数删除算法的移动平均次数Edl=(n-1)/2在顺序表中一个元素在顺序表中一个元素，平均要移动表的一半元素。，平均要移动表的一半元素。表长为表长为n的顺序表，删除算法的时间复杂度为的顺序表，删除算法的时间复杂度为O（n）4.查找查找(定位定位)StatusLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)/在顺序表L中查找第1个值与e满足关系compare()/元素,若找到,则返回其位序;否则返回0i=1;p=L.elem;while(i=L.Length&!(*compare)(*p+,e)+i;if(i=L.Length)returni;elsereturn0;/LocateElem_Sq查找算法中的基本操作为查找算法中的基本操作为“两元素的比较两元素的比较”，算法的时间复杂度为，算法的时间复杂度为O（L.Length）P26 有序顺序表的归并有序顺序表的归并voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc)/将两个均为升序顺序表La 、Lb归并为新的升序顺序表Lcpa=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+;/MergeList_Sq该算法中的基本操作为该算法中的基本操作为“元素赋值元素赋值”，算法，算法的时间复杂度为的时间复杂度为O（La.Length+Lb.Length）习习 题题 将数据将数据元素类型为整型的ADT表LA拆成两个分别存储奇数和偶数的拆成两个分别存储奇数和偶数的ADT表LB和LC。 数据结构题集数据结构题集 P17P18 2.11、2.21、2.25 线性表的线性表的顺序存储结构的的优缺点优点：无须为表示结点间的逻辑关系而增加额外的无须为表示结点间的逻辑关系而增加额外的 存储空间存储空间; ;可以方便的随机存取表中的任一结点。可以方便的随机存取表中的任一结点。为克服为克服顺序表表的的缺点，可采用另外一种存储结构。可采用另外一种存储结构。缺点：插入和删除运算不方便，需移动大量元素；插入和删除运算不方便，需移动大量元素；由于要求占用连续的存储空间，存储分配只由于要求占用连续的存储空间，存储分配只 能按最大存储空间预先进行，致使存储空间能按最大存储空间预先进行，致使存储空间 不能得到充分利用；表的容量难以扩充。不能得到充分利用；表的容量难以扩充。线性表的链式表示和实现线性表的链式表示和实现为表示表中元素间的逻辑关系，对元素ai来说，除了存储元素本身的信息之外，还需存储一个指示其直接后继ai+1的信息。这两部分信息组成数据元素ai的存储映象，称为结点。它包括两个域：数据域：存储数据元素信息的域。指针域：存储直接后继存储位置的域。线性表的链式表示线性表的链式表示(用链式存储结构存储的线性表称为链表链表)ai数据域指针域ai+1结点在在c语言中可用语言中可用“结构指针结构指针”来描来描述述:TypedefstructLnodeElemTypedata;structLnode*next;Lnode,*LinkList;元素的元素的存储位置间的关系存储位置间的关系头指针头指针类型类型用一组任意的存储单元存储线性表的各个数据元素。ann个结点链接成一个链表，即为线性表的个结点链接成一个链表，即为线性表的链式存储结构。链式存储结构。由于此链表的每个结点中只由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。包含一个指针域，故又称线性链表或单链表。aiai+1a1LinkList型型整个链表元素的存取必须从头指针开始进整个链表元素的存取必须从头指针开始进行，头指针指示链表中第一个结点的存储位置。行，头指针指示链表中第一个结点的存储位置。同时，由于最后一个元素没有直接后继，则线同时，由于最后一个元素没有直接后继，则线性链表中最后一个结点的指针为性链表中最后一个结点的指针为“空空(NIL)”。单链表可由头指针唯一确定。单链表可由头指针唯一确定。101010121014101610181020102210241026李李 NULL孙孙 1010赵赵 1024钱钱 1014例如，线性表（例如，线性表（赵，钱，孙，李赵，钱，孙，李）的）的链式存储结构如下：链式存储结构如下：10181010101410241018赵赵 1024钱钱 1014孙孙 1010李李 NULL线性表的链式结构的特点线性表的链式结构的特点1通过保存直接后继元素的存储位置的指针来表示数据元素之间的逻辑关系；2插入删除操作可通过修改结点的指针实现，无须移动元素；3不能随机存取元素；假设假设L是是linklist型的变量，则型的变量，则L为为单链表单链表的的头指针头指针，它指向表中第一个结点。若它指向表中第一个结点。若L为空为空(L=nil)，则所表示则所表示的线性表的线性表为为“空表空表”，其长度为，其长度为“零零”。头结点：头结点：根据需要在单链表的第一个结点之前附根据需要在单链表的第一个结点之前附设的一个结点。设的一个结点。头结点的指针域存储指向第一个结点头结点的指针域存储指向第一个结点的指针的指针,如图如图2（a）所示，此时头指针指向头结点。若所示，此时头指针指向头结点。若线性表为线性表为“空空”，则头结点的指针域为，则头结点的指针域为“空空”，如图，如图2（b）所示。所示。图图2带头结点的单链表带头结点的单链表设设p是指向结点是指向结点ai的指针，则的指针，则pnext表示指向结表示指向结点点ai+1的指针，的指针，pdata=ai，pnextdata=ai+1L(a)a1a2an(b)L附设头结点的好处：附设头结点的好处：一个单链表附设了头结点后，所有结点都有了前驱结点。这样一来：对所有结点的许多基本操作可统一处理对所有结点的许多基本操作可统一处理（因为单链表的许多基本操作均需要有指向待处理结点的前驱结点的指针）；头结点的可用于存储附加信息头结点的可用于存储附加信息（诸如表长等类）。若无特殊声明，则约定单链表均带头结点。线性表基本操作线性表基本操作(部分部分)在单链表中的实现：在单链表中的实现：1、在单链表中，读取第读取第i i个元素个元素必须从头指针出发寻找，因此，单链表是非随机存取的存储结构。单链表是非随机存取的存储结构。StatusGetElem_L(LinkListL,inti,ElemType&e)/L为带头结点的单链表的头指针p=Lnext;j=1;while(p&ji)returnERROR;e=pdata;returnOK;/GetElem_L该算法的核心是顺指针寻查，该算法的核心是顺指针寻查，while循环体中的语句频度与被查元循环体中的语句频度与被查元素在线性表中的位置有关。因此，素在线性表中的位置有关。因此，对长度为对长度为n的单链表而言，该算法的单链表而言，该算法的时间复杂度为的时间复杂度为O(n)。2 2、 插入插入在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为单链表中指向a的指针。如图3(a)所示。abP图图3(a)图图3(b)sx插入后的单链表如图3(b)所示。abPsnext=pnext;pnext=s; 、次序次序颠倒不得颠倒不得! !1）查找链表L的第i-1个元素结点；2）为新元素建立结点；3）修改第i-1个元素结点的指针和新元素结点指针完成插入；插入操作主要步骤：插入操作主要步骤：StatusListInsert_L(LinkList&L,inti,ElemTypee)/在带头结点的单链线性表L中第i个位置/之前插入元素ep=L;j=0;while(p&ji-l)returnERROR;s=(LinkList)malloc(sizeof(LNode)sdata=e;snext=pnext;pnext=s;returnOK;/LinstInsert_L插入算法插入算法若要删除线性表中元素b，仅需修改其前驱结点（结点a）的指针即可。pnext=pnextnext;若p为指向结点a指针，则修改指针的语句为：3 3、删除、删除Pacb1)查找链表的第i-1个元素结点,使指针p指向它,将指针q指向第i个结点；2)修改第i-1个元素结点指针，使其指向第i个元素结点的后继；3)回收q指针所指的第i个结点空间。删除操作主要步骤：删除操作主要步骤：StatusListDelete_L(LinkList&L,inti,ElemType&e)/在带头结点的单链表L中，删除第i个元素，并由e返回其值p=L;j=0;while(pnext&jnext;+j;if(!(pnext)|ji-1)returnERRORq=pnext;pnext=qnext;e=qdata;free(q);returnOK;/ListDelete_L虽然在单链表中插入或删除元素时无须移动元素，虽然在单链表中插入或删除元素时无须移动元素，但为寻查第但为寻查第i个元素，需执行个元素，需执行GetElem_L运算。因此上运算。因此上述两个运算的时间复杂度均为述两个运算的时间复杂度均为O(n)。删除算法删除算法 逆位序逆位序输入n个数据元素的值，建立带头结点的单链表。(采用头插法头插法)操作步骤：操作步骤：一、建立一个“空”表；二、输入数据元素an，建立结点并插入表表头头；三、输入数据元素an-1，建立结点并插入表表头头；ananan-1四、依次类推，直至输入a1为止。P30 动态建立单链表的算法动态建立单链表的算法voidCreateList_L(LinkList&L,intn)/逆序输入n个元素的值，建立带头结点的单链表LL=(LinkList)malloc(sizeof(LNode);Lnext=null;for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(&pdata);pnext=Lnext;Lnext=p;/CreateList_L算法的时间复杂度为算法的时间复杂度为O(n)P31 有序单链表的归并有序单链表的归并(就地工作)将两个均为升序将两个均为升序链表链表La a 、LbLb归并为新的归并为新的升序升序链表链表LcLc线性链表归并操作图示5 52 2 7Lb7 73 3n9 9La8 852n9 即即Lc8377LcviodMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)pa=La-next;pb=Lb-next;Lc=pc=La;/La的头结点作为Lc的头结点while(pa!=NULL)&(pb!=NULL)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);/释放Lb的头结点/MergeList_L注意：注意：La、Lb和和Lc不可移动；不可移动；不可释放不可释放La的的头结点头结点；操作的结果仅保存链表操作的结果仅保存链表Lc，而两而两 操作链表不复存在操作链表不复存在。 习习 题题数据结构题集数据结构题集 P17P18 2.19、2.22、2.26 静静态态链链表表有的高级语言中无“指针”数据类型，不能动态分配结点。此时可借助一维数组来描述线性链表。把这种用数组描述的链表就称为静态链表.类型说明如下：#defineMAXSIZE1000typedefstructElemTypedata;intcur;/指示结点在数组中的相对位置component;SLinkListMAXSIZE;这种存储结构仍须预先分配一个较大的存储空间，但在作线性表的插入和删除时不需移动元素，仍需修改指针，故仍具有链式结构的主要优点。0WANG8ZHENG7WU6ZHOU5LI4SUN3QIAN2ZHAO1012345678910静态链表示例静态链表示例5SHI0WANG8ZHENG8WU6ZHOU9LI4SUN3QIAN2ZHAO1012345678910修改前状态(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)修改后状态(ZHAO,QIAN,SUN,LI,SHI,ZHOU,WU,WANG)LI和和ZHOU之间之间插入插入SHI删除删除ZHENG循环链表是线性表的另一种链式存储结构。它的特点是链表的最后一个结点的指针域不为最后一个结点的指针域不为空而是指向头结点。空而是指向头结点。(a)非空表非空表单循环链表循环链表的操作和线性链表基本一致，差别仅循环链表的操作和线性链表基本一致，差别仅在于在于“指针是否为空指针是否为空”改为改为“指针是否为指针是否为头指针头指针”。循循环环链链表表(b)空表空表HHa1anA=B;有时在循环链表中设立尾指针可使操作简化。A例如将两个设立尾指针的循环链表A、B合并，仅需改变两个指针值即可仅需改变两个指针值即可。Bb1bnAApp=Anext;Anext=Bnextnext;a1amBnext=p;nextdataprior双向链表：双向链表：多重链表是每个结点含有两个或两个以上指针域的链表。双向链表是一种二重链表，每个结点含两个指针域：前驱指针域前驱指针域和后继指针域。使用它可方便地查找某个结点的直接前驱直接前驱和直接后继。双向链表在c语言中可描述描述如下：typedefstructDuLNodeElemTypedata;structDuLNode*prior,*next;DuLNode,*DuLinkList;结点结构结点结构如下：双向链双向链表表在双向链表中，若d为指向表中某一结点的指针，d则有：dnextprior=abcdpriornext=d双向链表也有循环表：双向链表也有循环表：a1anLL空的双向循环链表非空的双向循环链表具体算法描述见具体算法描述见P37算法算法2.19在双向链表中进行插入和删除操作时和单链表有很大的不同，需要同时修改两个方向的指针的值。ppriornext=pnext；abc1、删除结点删除结点b：需修改两个指针值ppnextprior=pprior；2、插入结点插入结点x：需修改四个指针值abxspsprior=pprior;ppriornext=s;snext=p;pprior=s;具体算法描述见具体算法描述见P36算法算法2.18用上述定义的单链表实现线性表的操作用上述定义的单链表实现线性表的操作时，时，存在的问题：存在的问题：改进链表的设置：改进链表的设置：1单链表的表长单链表的表长是一个隐含的值；是一个隐含的值；1增加增加“表长表长”、“表尾指针表尾指针”两个数据域；两个数据域；2在单链表的最后一个元素之后插入元在单链表的最后一个元素之后插入元素时，需遍历整个链表；素时，需遍历整个链表；3在链表中，元素的在链表中，元素的“位序位序”概念淡化，概念淡化，结点的结点的“位置位置”概念加强。概念加强。2将基本操作中的将基本操作中的“位序位序i”改变为改变为“指针指针p”。从实际应用角度从实际应用角度重新定义线性链表重新定义线性链表类型及其基本操作如下：类型及其基本操作如下：typedefstructLNode/结点类型结点类型ElemTypedata;structLNode*next;*Link,*Position;typedefstruct/链表类型链表类型Linkhead,tail;/分别指向头结点和/最后一个结点的指针intlen;/指示链表长度LinkList;StatusMakeNode(Link&p,ElemTypee);/分配由p指向的值为e的结点，并返回OK；/若分配失败，则返回ERRORvoidFreeNode(Link&p);/释放p所指结点链表的基本操作链表的基本操作: :StatusInitList(LinkList&L);/构造一个空的线性链表L，其头指针、/尾指针均指向头结点，表长为零。StatusDestroyList(LinkList&L);/销毁线性链表L，L不再存在。StatusClearList(LinkList&L);/重置L为空表StatusInsFirst(Linkh,Links);/h指向头结点，将s结点插入在第一个结点之前StatusDelFirst(Linkh,Link&q);/h指向头结点，删除第一个结点并以q返回StatusAppend(LinkList&L,Links);/在L的表尾链接由指针s所指的一串结点StatusRemove(LinkList&L,Link&q);/删除L的尾结点并以q返回，L的尾指针指向新尾结点StatusSetCurElem(Link&p,ElemTypee);/已知p指向线性链表中的一个结点,用e更新p结点中数据元素的值StatusInsBefore(LinkList&L,Link&p,Links);/将s所指结点插入在线性链表L中p所指结点之前并修改p指向新插结点StatusInsAfter(LinkList&L,Link&p,Links);/将s所指结点插入在线性链表L中p所指结点之后并修改p指向新插结点ElemTypeGetCurElem(Linkp);/已知p指向线性链表中的一个结点,返回p结点中数据元素的值StatusListEmpty(LinkListL);/判表空intListLength(LinkListL);/求表长PositionPriorPos(LinkListL，Linkp);/改变当前指针p指向其前驱PositionNextPos(LinkListL,Linkp);/改变当前指针p指向其后继PositionGetHead(LinkListL);/返回L的头结点的位置PositionGetLast(LinkListL);/返回L的尾结点的位置StatusLocatePos(LinkListL,inti,Link&p);/返回指针p，p指向L的第i个结点StatusLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType);/返回L中第1个与e满足函数compare()判定/关系的元素的位置StatusListTraverse(LinkListL,Status(*visit)();/依次对L的每个元素调用函数visit()StatusListInsert_L(LinkListL,inti,ElemTypee)/在带头结点的单链表L的第i个元素之前插入元素eif(!LocatePos(L,i-1,h)returnERROR;/i值不合法if(!MakeNode(s,e)returnERROR;/结点存储分配失败InsFirst(h,s);returnOK;/ListInsert_L利用上述定义的基本操作，易实现诸如删、利用上述定义的基本操作，易实现诸如删、插和表合并等操作。插入操作的算法如下：插和表合并等操作。插入操作的算法如下：nnnxpxpxppxP+ + + + += =.)(2210在计算机中，可用一个线性表来表示在计算机中，可用一个线性表来表示:P=(p0,p1,，pn)一、一元多项式的表示一、一元多项式的表示一元多项式的表示及相加一元多项式的表示及相加上述表示法上述表示法只存储各项的系数只存储各项的系数，而幂指数，而幂指数隐含在隐含在“位序位序”之中。宜采用顺序存储结构存储。之中。宜采用顺序存储结构存储。p0p1pn下标下标01n浪费空间浪费空间操作不便操作不便一般情况下的一元稀疏多项式稀疏多项式可写成Pn(x)=p1xe1+p2xe2+pmxem 其中：pi 是指数为ei 的项的非零系数，0e1e2em=n可以下列线性表表示:（(p1,e1),(p2,e2), ,( pm,em)）但是对于形如但是对于形如S(x)=1+3x100002x30000的多项式，上述表示方法合适吗？的多项式，上述表示方法合适吗？P=(1,0,0,3,0,0,-2)9999个个19999个个此为以指数值为关键字的有序表ADTPolynomial数据对象数据对象：Dai|aiTermSet,i=1,2,.,m,m0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数.二、二、ADTADT一元多项式的定义一元多项式的定义数据关系：数据关系：R1|ai-1,aiD,i=2,.,n且ai-1中的指数值ai中的指数值CreatPolyn(&P,m)/构建操作结果：操作结果：输入m项的系数和指数，建立一元多项式P。基本操作基本操作：DestroyPolyn(&P)/销毁初始条件：初始条件：一元多项式P已存在。操作结果：操作结果：销毁一元多项式P。PrintPolyn(&P)/打印初始条件：初始条件：一元多项式P已存在。操作结果：操作结果：打印输出一元多项式P。PolynLength(P)/求项数初始条件初始条件：一元多项式P已存在。操作结果操作结果：返回一元多项式P中的项数。AddPolyn(&Pa,&Pb)/相加初始条件初始条件：一元多项式Pa和Pb已存在。操作结果操作结果：完成多项式相加运算,即:Pa=PaPb，并销毁一元多项式Pb。SubtractPolyn(&Pa,&Pb)/相减初始条件初始条件：一元多项式Pa和Pb已存在。操作结果操作结果：完成多项式相减运算,即:Pa=PaPb，并销毁一元多项式Pb。MultiplyPolyn(&Pa,&Pb)/相乘初始条件初始条件：一元多项式Pa和Pb已存在。操作结果操作结果：完成多项式运算,即:Pa=PaPb，并销毁一元多项式Pb。ADTPolynomialtypedefstructfloatcoef;/系数intexpn;/指数term,ElemType;/结点类型的定义:三、三、ADTADT一元多项式的实现一元多项式的实现/一元多项式类型的定义:typedefLinkListPolynomial/用带头结点的有序链表表示一元多项式因表示一元多项式的是有序链表，有序链表的基本操作定义与线性链表略有不同：LocateElem的职能不同；另需增加按有序关系进行插入的操作OrderInsert。主要区别(1)两操作中的compare()均为有序关系判定函数；(2)LocateElem的的参数指针q的返回值不同；(3)OrderInsert中新结点的插入应使原线性链表保持原来的有序性。详见详见P42之说明之说明。说明：说明：/基本操作的函数原型说明voidCreatPolyn(Polynomial&P,intm)；/构建输入m项的系数和指数，建立多项式PvoidDestroyPolyn(Polynomial&P)；/销毁多项式PvoidPrintPolyn(PolynomialP)；/打印输出多项式PvoidPolynLength(PolynomialP);/返回多项式P中的项数voidAddPolyn(Polynomial&Pa,Polynomial&Pb)；/完成多项式相加运算,即:Pa=PaPb，并销毁多项式PbvoidSubtractPolyn(Polynomial&Pa,Polynomial&Pb)；/完成多项式相减运算,即:Pa=PaPb，并销毁多项式PbvoidMultiplyPolyn(Polynomial&Pa,Polynomial&Pb)；/完成多项式相乘运算,即:Pa=PaPb，并销毁多项式Pb建立有序链表算法：建立有序链表算法：/基本操作的算法描述(部分)voidCreatPolyn(polynomail&P,intm)/输入m项的系数和指数，建立表示多项式的有序链表PInitList(P);h=GetHead(P);e.coef=0.0;e.expn=-1;SetCurElem(h,e);/设置头结点的数据元素for(i=1;i=m;+i)/依次输入m个非零项scanf(e.coef,e.expn);if(!LocateElem(P,e,q,(*cmp)()/当前链表中不存在该指数项if(MakeNode(s,e)InsFirst(q,s);intcmp(trema,tremb);/依a的指数值)b的指数值，分别返回-1、0和1一元多项式的相加一元多项式的相加设有两个多项式：A(x)=7+3x+9x8+5x17和B(x)=8x+22x7-9x8，可用两个带头结点的单链表表示如下：图中每个结点表示多项式中的一项.。相加的运算规则相加的运算规则：指数相同的项系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。“和多项式”链表中的结点无须另外生成，只需从B中摘取并加到A上。设qa和qb分别指向A,B中当前进行比较的结点a和b，比较的是结点的指数项，有三种情况：1)若a.expnb.expn则qb结点为和多项式中的一项；3)若a.expn=b.expn则将两结点中的系数相加系数相加，当系数之和不为零系数之和不为零时，修改qa结点中的系数域，释放qb结点；当系数之和为零系数之和为零时，则从表A中删去qa结点，同时释放qa和qb所指结点。papa-1-17 07 03 13 19 89 85 175 17pbpb-1-18 18 122 722 7-9 8-9 811 1voidAddpolyn(polynomial&pa,polynomial&pb)/多项式加法ha=GetHead(pa);hb=GetHead(pb);qa=NextPos(pa,ha);qb=NextPos(pb,hb);While(!qa&!pb)a=GetCurElem(qa);b=GetCurElem(qb);switch(*cmp(a,b)case-1:ha=qa;qa=NextPos(pa,qa);break;一元多项式相加算法：一元多项式相加算法：case0:sum=a.coef+b.coef;if(sum!=0.0)SetCurElem(qa,sum);ha=qa;elseDelFirst(ha,qa);FreeNode(qa);DelFirst(hb,qb);FreeNode(qb);qb=NextPos(pb,hb);qa=NextPos(pa,ha);break;case1:DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(pb,hb);ha=NextPos(pa,ha);break;/switch/whileif(!Empty(pb)Append(pa,qb);FreeNode(hb);/addpolyn习习 题题数据结构题集数据结构题集 P18P20 2.32、2.39、2.41 实实 验验 题题实验一实验一 线性表线性表实验目的：实验目的：1.1.学会运用基本数据结构进行稍为复杂程学会运用基本数据结构进行稍为复杂程 序的设计。序的设计。 2.2.学会根据实际问题选择合适的数据的学会根据实际问题选择合适的数据的 存储结构。存储结构。 3.3.掌握线性表的顺序表示与实现和链式掌握线性表的顺序表示与实现和链式 表示与实现。表示与实现。1)1)约瑟夫约瑟夫 ( (Josehus) ) 问题问题设有设有N个人围坐一圈，现从某人开始报数，个人围坐一圈，现从某人开始报数，数到数到M的人出列，接着从出列的下一个人重新报的人出列，接着从出列的下一个人重新报数，数到数，数到M的人又出列，如此下去直到所有人都的人又出列，如此下去直到所有人都出列为止。试给出他们的出列次序。出列为止。试给出他们的出列次序。 要求要求: :(1)(1)用不带头结点的单向循环链表为存储结构用不带头结点的单向循环链表为存储结构 模拟整个过程；模拟整个过程； (2)(2)输出出列各人的编号。输出出列各人的编号。实验内容：实验内容：2)2)设计一个一元多项式简单的计算器。设计一个一元多项式简单的计算器。要求要求: :(1)用带头结点的单链表表示多项式，表中每用带头结点的单链表表示多项式，表中每一个结点表示多项式中的一项一个结点表示多项式中的一项；(2)一元多项式简单计算器的基本功能为：一元多项式简单计算器的基本功能为：输入并建立多项式；输出多项式；两个多项式输入并建立多项式；输出多项式；两个多项式相加；两个多项式相减；相加；两个多项式相减；*两个多项式相乘。两个多项式相乘。第二章第二章线性表的线性表的小结小结本章学习了线性表的顺序存储结构本章学习了线性表的顺序存储结构(顺序表顺序表)，链式存，链式存储结构储结构(线性链表线性链表),循环链表循环链表,双向链表，以及在这两种存双向链表，以及在这两种存储结构下如何实现线性表的基本操作。在此需再次强调：学储结构下如何实现线性表的基本操作。在此需再次强调：学习本课程不仅要从概念和方法上了解每一种数据结构的逻辑习本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学会如何使其在计算机上实结构和基本操作，更重要的是要学会如何使其在计算机上实现。即如何在计算机上存储线性表，如何在计算机上实现线现。即如何在计算机上存储线性表，如何在计算机上实现线性表的操作。我们已经看到，在不同的存储结构下，线性表性表的操作。我们已经看到，在不同的存储结构下，线性表的同一操作的算法是不同的。在顺序表存储结构下，线性表的同一操作的算法是不同的。在顺序表存储结构下，线性表的插入删除操作，通过移动元素实现的插入删除操作，通过移动元素实现;在链式存储结构下，在链式存储结构下，线性表的插入删除操作，通过修改指针实现。同时还应学会，线性表的插入删除操作，通过修改指针实现。同时还应学会，对于某一实际问题，如何选择合适的存储结构，如何在某种对于某一实际问题，如何选择合适的存储结构，如何在某种存储结构下实现对数据对象的操作，我们要通过存储结构下实现对数据对象的操作，我们要通过数据结构数据结构数据结构的学习，很好地理解各种存储结构是如何存储和数据结构的学习，很好地理解各种存储结构是如何存储和表达数据对象的有关信息的，各种存储结构下操作的特点。表达数据对象的有关信息的，各种存储结构下操作的特点。为实际问题的程序设计打下坚实的基础。为实际问题的程序设计打下坚实的基础。