数据结构第二章 线性表课件

第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加线性结构：是一个数据元素的有序集例如（A，B，C，D，E，……Z）（32，25，76，28，96）注：1、一个数据元素的集合2、这些数据元素是有序的线性结构的特征：1、唯一的“第一个元素”2、唯一的“最后一个元素”3、除最后一个元素外，所有元素都有唯一的后继4、除第一个元素外，所有元素都有唯一的前驱二、抽象数据类型的线性表的定义ADTList{数据对象：D={ai|ai∈ElemSet，i=1，2，3……n，n>=0}数据关系：R1={<ai-1，ai>|ai-1，ai∈D，i=，2，3，…n}基本操作}基本操作：1、{结构初始化}InitList（&L）结果：构造一个空的线性表L2、{销毁结构}DestroyList（&L）初始条件：线性表L已经存在结果：销毁线性表L3、{引用型操作}ListEmpty（L）；ListLength（L）PriorElem（L.cur_e,&pre_e）；NextElem（L.cur_e,&next_e）；GetElem（L，e，&e）；LocateElem(L，e，compare（）);ListTraverse（L，visit（））4、{加工型操作}ClearList（&L）PutElem（L，i，&e）ListInsert(&L，i，e)ListDelete(&L，i，&e）注：1、InitList（&L）和ClearList（&L）的区别2、除了初始化操作外，每一个操作都有一个初始条件和操作结果3、任何一种抽象数据类型，都包含有初始化操作和销毁操作voidunion(List&La，ListLb){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、先对原表进行排序2、然后插入voidpurge(List&La，ListLb){InitList(La);La-len=Listlength(La);Lb-len=Listlength(Lb);for(I=1;I<=Lb-len;I++){GetElem(lb，I，e);if（ListEmpty（La）||！Equal（en，e））{Listinsert(la，++la-len，e)；en=e；}}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;}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线性表的顺序存储结构一、线性表的顺序映像1、线性表的顺序映像:把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用c个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(aI)之间满足下列关系：LOC(ai+1)=LOC(ai)+c线性表的第i个数据元素ai的存储位置为：

LOC(ai)=LOC(a1)+(i-1)*c

a1a2a3ai-1aian结论：所有数据元素的存储位置均取决于第一个数据元素的存储位置。2、顺序映像的c语言描述#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}Sqlist;注：1、由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。2、线性表的长度是可以变化的，但是在设计的时候先给定一个值，相应的存储空间的大小是这个值的倍数二、顺序表上实现的基本操作1、线性表的初始化操作StatusInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));If(!L.elem)exit(OVERFLOW);L.length=0;L.Listsize=LIST_INIT_SIZE:returnOK;}注：1、基本操作：元素的移动2、时间复杂度：O（n）3、ListInsert(&L,I,e)问：插入元素时，线性表的逻辑结构发生什么变化4、ListDelete（&L,I,&e）问：删除元素时，线性表的逻辑结构发生什么变化

三、顺序存储线性表的优缺点1、优点：对每一个元素都可以随机存储2、缺点：在进行插入、删除操作的时候，必须移动线性表中的元素2.3线性表的链式表示和实现一、单链表1、单链表：链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。p……2、以线性表中的第一个数据元素a1的存储地址作为线性表的地址，称作线性表的头指针。

……通常在第一个元素前面加一个结点，作为头结点。这时头指针指向头结点。如果为空表，则头结点的指针域为空。a1a2a3an-1ana1a2an-1an显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，同时，由于终端结点无后继，故终端结点的指针域为空，即null（图示中也可用^表示)。例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat)注：单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针名是head，则把链表称为表head。4、用C语言描述的单链表如下：TypedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;二、链表上的操作1、GetElem（L，i，&e）基本操作：使指针p始终指向线性表中第j个数据元素（2）按值查找StatusGetElem(linklistL,intkey，ElemType&e){p=L–>next;while(p&&p–>data!=key)p=p–>next;if(!p)returnerror;elsereturnp;}该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。2、ListInsert（&L,i,e）P29基本操作：找到线性表中第i-1个结点，修改其指向后继的指针，并且插入新结点3、ListDelete（&L,i,&e）P30基本操作：找到线性表中第i-1个结点，修改其指向后继的指针，并释放删除的结点4、CreatList（LinkList&L）（1）尾插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾上，直到读入结束标志为止。VoidCreate_L(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=null;p=L;for(i=1;i<n;i++){q=(LinkList)malloc(sizeof(LNode));scanf(&p->data);p–>next=q;p=q;p->next=null;}return(L);}5、用上述定义的单链表实现线性表的操作时，存在的问题：（1）单链表的表长是一个隐含的值（2）在单链表的最后，一个元素最后插入元素时，需要遍历整个链表（3）在链表中，元素的“位序”概念淡化，结点的“位置”概念强化。改进链表的设置：增加“表长”，“表尾指针”，“当前位置的指针”三个数据域三、一个带头结点的线性表类型1、结点结构：TypedefstructLNode{ElemTypedata;structLNode*next;}*Link,*Position;2、链表类型：Typedefstruct{Linkhead,tail;Intlen;Linkcurrent;}LinkList;3、基本操作：(1)InitList（LinkList&L）(2)DestroyList(LinkList&L)(3)Prior(LinkListL);Next(LinkListL);GetCurElem(LinkListL);LocatePos(LinkListL,inti);LocateElem(LinkListL,ElemTypee,compare());ListTraverse(LinkListL,Status(*visit)());(4)ClearList(LinkList&l);SetCurElem(LinkList&L,ElemTypee);Append(LinkList&L,Links)InsAfter(LinkList&L,ElemTypee);DelAfter(LinkList&L,ElemType*e)StatusInsAfter(LinkList&L,ElemTypee){if(!L.current)returnError;if(!MakeNode(s,e))returnError;s->next=L.current->next;L.current->next=s;returnok;}四、循环链表

循环链表时一种头尾相接的链表。最后一个结点的指针指向第一个结点的链表。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：

a1an

….head⑴非空表⑵空表例、在链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算。linklistconnect(linklisttaila，linklisttailb){linklistp=taila—>next;taila—>next=(tailb—>next)—>nextfree(tailb—>next);tailb—>next=p;return(tailb);}五、双链表1、双向链表(Doublelinkedlist):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：

typedefstructDulNode{ElemTypedata;structDulNode*prior，*next;}DulNode,*DulNode;

设指针p指向某一结点，(p—>prior)—>next=p=(p—>next)—>prior即结点*p的存储位置既存放在其前趋结点*(p—>prior)的直接后继指针域中，也存放在它的后继结点*(p—>next)的直接前趋指针域中。2、插入和删除ai-1eaipqq—>dat