数据结构第二章-线性表part4

一、单链表二、结点和单链表的C语言描述三、线性表的操作在单链表中的实现四、一个带头结点的单链表类型五、其它形式的链表六、有序表类型2.3线性表的链式表示和实现一、单链表用一组任意的存储单元存储线性表中的数据元素（这组存储单元可以是连续的，也可以是不连续的）。为了表示每个元素ai与其直接后继元素ai+1之间的逻辑关系，对元素ai来说，除了存储元素本身的信息之外，还需存储一个指针信息，它指示直接后继元素的存储位置。这两部分信息组成数据元素ai的存储映象，称为结点。datanext结点数据域指针域以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素或数据元素的映象)以“结点的序列”表示线性表（每个结点中只包含一个指针域）称作单链表线性表（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)的线性链表存储结构：存储地址数据域指针域1LI437QIAN1313SUN119WANGNull25WU3731ZHAO737ZHENG1943ZHOU25头指针H31线性链表的逻辑状态ZHAOQIANSUNLIZHOUWUZHENGWANG∧H用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针来指示的，逻辑上相邻的两元素其物理位置不要求紧邻。通常把链表画成用箭头相连接的结点的序列，结点之间的箭头表示链域中的指针。由此可见，单链表可由头指针唯一确定。以线性表中第一个数据元素a1的存储地址作为线性表的地址，称作线性表的头指针。当线性表为空时，头指针为空。头结点a1a2…...an^头指针头指针有时为了操作方便，在第一个结点之前虚加一个“头结点”，头结点的指针域指向第一个结点的存储位置；以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空TypedefstructLNode{ElemTypedata;//数据域structLnode*next;//指针域}LNode,*LinkList;二、结点和单链表的C语言描述LinkListL；//L为单链表的头指针ai=p-data;ai+1=p-next-dataaiai+1ai+2P三、单链表操作的实现GetElem(L,i,&e)//取第i个数据元素ListInsert(&L,i,e)//插入数据元素ListDelete(&L,i,e)//删除数据元素ClearList(&L)//重置线性表为空表CreateList(&L,n)//生成含n个数据元素的链表L线性表的操作GetElem(L,i,&e)在单链表中的实现:211830754256∧pppj123在单链表中，任何两个元素的存储位置之间没有固定的联系，然而每个元素的存储位置都包含在其直接前趋结点的信息中。在单链表中，取得第i个数据元素必须从头指针出发寻找。因此，查找第i个数据元素的基本操作为：移动指针，比较j和i。单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。令指针p始终指向线性表中第j个数据元素。StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素}//GetElem_L算法时间复杂度为:O(ListLength(L))p=L-next;j=1;//p指向第一个结点，j为计数器while(p&&ji){p=p-next;++j;}//顺指针向后查找，直到p指向第i个元素或p为空if(!p||ji)returnERROR;//第i个元素不存在e=p-data;//取得第i个元素returnOK;ai-1线性表的操作ListInsert(&L,i,e)在单链表中的实现：有序对ai-1,ai改变为ai-1,e和e,aieaiai-1因此，在单链表中第i个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。StatusListInsert_L(LinkListL,inti,ElemTypee){//L为带头结点的单链表的头指针，本算法//在链表中第i个结点之前插入新的元素e}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))……p=L;j=0;while(p&&ji-1){p=p-next;++j;}//寻找第i-1个结点if(!p||ji-1)returnERROR;//i大于表长或者小于1s=(LinkList)malloc(sizeof(LNode));//生成新结点s-data=e;s-next=p-next;p-next=s;//插入returnOK;eai-1aiai-1spC语言中的两个标准函数：malloc和free假设p和q是linklist型的变量，则执行p=(linklist)malloc(sizeof(node))的作用是：由系统生成一个node型的结点，同时将该结点的起始位置赋给指针变量p;执行free(q)的作用是由系统回收一个node型的结点，回收后的结点可以备作再次生成结点时用。因此，单链表是一种动态结构，整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是可以由系统应需求即时生成。建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从空表的初始状态起，依次建立各元素结点，并逐个插入链表。线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对ai-1,ai和ai,ai+1改变为ai-1,ai+1ai-1aiai+1ai-1在单链表中删除第i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;free(q);pqStatusListDelete_L(LinkListL,inti,ElemType&e){//删除以L为头指针(带头结点)的单链表中第i个结点}//ListDelete_L算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p-next&&ji-1){p=p-next;++j;}//寻找第i个结点，并令p指向其前趋if(!(p-next)||ji-1)returnERROR;//删除位置不合理q=p-next;p-next=q-next;//删除并释放结点e=q-data;free(q);returnOK;操作ClearList(&L)在链表中的实现:voidClearList(&L){//将单链表重新置为一个空表while(L-next){p=L-next;L-next=Null;}}//ClearListfree(p);算法时间复杂度：O(ListLength(L))头结点a1a2…...an^Lp如何从线性表得到单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。例如：逆位序输入n个数据元素的值，建立带头结点的单链表。操作步骤：一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，建立结点并插入；ananan-1四、依次类推，直至输入a1为止。voidCreateList_L(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表}//CreateList_L算法的时间复杂度为:O(Listlength(L))L=(LinkList)malloc(sizeof(LNode));L-next=NULL;//先建立一个带头结点的单链表for(i=n;i0;--i){p=(LinkList)malloc(sizeof(LNode));scanf(&p-data);//输入元素值p-next=L-next;L-next=p;//插入}回顾2.1节中三个例子的算法，看一下当线性表分别以链表存储结构表示时，它们的实现算法的时间复杂度为多少？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);}//for}//union控制结构：基本操作：for循环GetElem,LocateElem和ListInsert当以顺序映像实现抽象数据类型线性表时为:O(ListLength(La)×ListLength(Lb))当以链式映像实现抽象数据类型线性表时为:O(ListLength(La)×ListLength(Lb))例2-1算法时间复杂度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;}}//for}//purge控制结构：基本操作：for循环GetElem和ListInsert当以顺序映像实现抽象数据类型线性表时为:O(ListLength(Lb))当以链式映像实现抽象数据类型线性表时为:O(ListLength2(Lb))例2-2算法时间复杂度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循环GetElem,ListInsert当以顺序映像实现抽象数据类型线性表时为:O(ListLength(La)+ListLength(Lb))当以链式映像实现抽象数据类型线性表时为:O(ListLength2(La)+ListLength2(Lb))例2-3算法时间复杂度用上述定义的单链表实现线性表的操作时，存在的问题：改进链表的设置：1．单链表的表长是一个隐含的值；1．增加“表长”、“表尾指针”和“当前位置的指针”三个数据域；2．在单链表的最后一个元素之后插入元素时，需遍历整个链表；3．在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。2．将基本操作中的“位序i”改变为“指针p”。四、改进的线性链表类型typedefstructLNode{//结点类型ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct{//链表类型Linkhead,tail;//分别指向头结点和最后一个结点的指针intlen;//指示链表长度Linkcurrent;//指向当前被访问的结点的//指针，初始位置指向头结点}LinkList;头结点a1…ai...an^headcurrenttailStatusMakeNode(Link&p,ElemTypee);//分配由p指向的值为e的结点，并返回OK，//若分配失败，则返回ERRORvoidFreeNode(Link&p);//释放p所指结点链表的基本操作:{结构初始化和销毁结构}StatusInitList(LinkLis