线性表的链式存储结构.ppt

第5讲 线性表的 链式存储结构,主讲人：陈红丽,2.3 线性表类型的实现-链式映象,用一组地址任意的存储单元存放线性表中的数据元素。,一、单链表,以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素 或 数据元素的映象),以“结点的序列”表示线性表 称作链表,以线性表中第一个数据元素 的存储地址作为线性表的基地址，称作线性表的头指针,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前附加一个“头结点”，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点。通常称这类单链表为带头结点的单链表。,空指针,线性表为空表时，头结点的指针域为空,结点类型：Typedef struct LNode ElemType data;/数据域 struct Lnode*next;/指针域 LNode;,二、结点和单链表的 C 语言描述,单链表类型：Typedef LNode*LinkList;,若设 LNode*p,*q;LinkList H；则 p，q 和 H 均为以上定义的指针型变量。指针型变量只能作同类型的指针赋值与比较操作。指针型变量的“值”除了由同类型的指针变量赋值得到外，都必须用 C 语言中的动态分配函数得到。例如，p=new LNode;表示在运行时刻系统动态生成了一个 LNode 类型的结点，并令指针 p“指向”该结点。当指针 p 所指结点不再使用，可用 delete p;释放此结点空间。,三、单链表操作的实现,GetElem(L,i,&e)/取第i个数据元素,ListInsert(&L,i,e)/插入数据元素,ListDelete(&L,i,&e)/删除数据元素,ClearList(&L)/重置线性表为空表,InitList(&L)/初始化,DestroyList(&L)/销毁线性表,操作 InitList(&L),链表是一个进行动态存储管理的结构，因此在初始化时不需要按照线性表实际所需最大容量进行预分配。,void InitList_L(LinkList&L)/创建一个带头结点的空链表，L 为指向头结点的指针/InitList,算法时间复杂度：,O(1),L=new LNode;if(!L)exit(1);/存储空间分配失败L-next=NULL;,操作 DestroyList(&L)与ClearList(&L),void DestroyList_L(LinkList/DestroyList,算法时间复杂度：,O(ListLength(L),void ClearList_L(/ClearList,L所指结点的指针域内容赋值给L.即L指向L的后继结点.,p所指结点的指针域内容赋值给L的指针域。即L的指针域指向p的后继结点.,线性表的操作 GetElem(L,i,&e)在单链表中的实现:,j,1,2,3,因此，查找第 i 个数据元素的基本操作为：移动指针，比较指针所指元素的位序j 和 i,单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。因此不论 i 值为多少，都必须从头结点开始起点数，直数到第 i 个为止。头结点可看成是第0个结点。,p 和 j 同步变化，始终保持指针 p 指向第j个结点,Status GetElem_L(LinkList L,int i,ElemType&e)/L是带头结点的链表的头指针，若1iLengthList(L)，则用 e 带回第 i 个元素的值且返回函数值为TRUE,否则返回函数值为FALSE/GetElem_L,算法时间复杂度为:,O(ListLength(L),p=L-next;j=1;/p指向第一个结点，j为计数器,while(p/顺指针向后查找，直到 p 指向第 i 个元素或 p 为空,if(!p|ji)return FALSE;/第 i 个元素不存在e=p-data;/取得第 i 个元素return OK;,线性表的操作 ListInsert(&L,i,e)在单链表中的实现：,有序对 改变为 和,因此，在单链表中第 i 个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。,可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。,Status ListInsert_L(LinkList&L,int i,ElemType e)/L 为带头结点的单链表的头指针，本算法/在链表中第i 个结点之前插入新的元素 e/LinstInsert_L,算法的时间复杂度为:,O(ListLength(L),p=L;j=0;while(p/寻找第 i-1 个结点,if(!p|j i-1)return ERROR;/i 大于表长或者小于1,s=new LNode;/生成新结点if(s=NULL)return ERROR;s-data=e;s-next=p-next;p-next=s;/插入return OK;,s,p,线性表的操作ListDelete(&L,i,&e)在单链表中的实现:,有序对 和 改变为,在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。,q=p-next;p-next=q-next;e=q-data;delete(q);,p,q,Status ListDelete_L(LinkList&L,int i,ElemType&e)/删除以 L 为头指针(带头结点)的单链表中第 i 个结点/ListDelete_L,算法的时间复杂度为:,O(ListLength(L),p=L;j=0;while(p-next/寻找第 i 个结点，并令 p 指向其前趋,q=p-next;p-next=q-next;/删除并释放结点e=q-data;delete(q);return OK;,if(!(p-next)|j i-1)return ERROR;/删除位置不合理,单链表其它算法举例,逆序创建链表,假设线性表(a1，a2，a3，an)的数据元素存储在一维数组 An中，则从数组的最后一个分量起，依次生成结点，并逐个插入到一个初始为空的链表中。,CreateList_L(&L，n，A)/生成含 n 个数据元素的链表,生成链表的过程是一个结点“逐个插入”的过程。,操作步骤：,一、建立一个“空表”；,二、输入数据元素an，建立结点并插入；,三、输入数据元素an-1，建立结点并插入；,an,an,an-1,四、依次类推，直至输入a1为止。,void CreateList_L(LinkList&L,int n，ElemType A)/逆序输入 n 个数据元素，建立带头结点的/单链表/CreateList_L,算法的时间复杂度为:,O(Listlength(L),L=new LNode;if(!L)exit(1);/存储空间分配失败L-next=NULL;/先建立一个带头结点的单链表,for(i=n;i 0;-i)p=new LNode;p-data=Ai-1;/赋元素值 p-next=L-next;L-next=p;/插入,L,20,17,已知线性表（20，17，40，60）思考：算法如何实现？,40,60,q-next=p;/*将新结点插入到表尾*/q=p;p-next=NULL;,回顾 2.1 节中三个例子的算法，看一下当线性表分别以顺序存储结构和链式存储结构实现时，它们的时间复杂度为多少？,void union(List/union,例2-1,基本操作：,ListDelete,LocateElem 和 ListInsert,控制结构：,while循环,void union_Sq(SqList,当以顺序映像实现抽象数据类型线性表时为:O(ListLength(La)ListLength(Lb),算法时间复杂度,void union_L(LinkList,当以链式映像实现抽象数据类型线性表时为:O(ListLength(La)ListLength(Lb),void purge(List/purge,GetElem(Lb,i,e);/取Lb中第 i 个数据元素赋给 e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和 e 相同的数据元素，则插入之,for(i=1;i=Lb_len;i+)/for,InitList(La);/构造(空的)线性表La,例2-2,void purge_Sq(SqList/修改表长/purge_Sq,算法的时间复杂度为O(ListLength2(L),void purge_L(SLink/while/purge_L,算法的时间复杂度为O(ListLength2(L),void purge(List/for/purge,控制结构：基本操作：,for 循环GetElem 和 ListInsert,当以顺序映像实现抽象数据类型线性表时为:O(ListLength(Lb),当以链式映像实现抽象数据类型线性表时为:O(ListLength(Lb),例2-2,算法时间复杂度,typedef SqList OrderedSqList;void purge_OSq(OrderedSqList,typedef LinkList OrderedLinkList;void purge_OL(OrderedLinkList,void MergeList(List La,List Lb,List,控制结构：基本操作：,三个并列的while循环GetElem,ListInsert,当以顺序映像实现抽象数据类型线性表时为:O(ListLength(La)+ListLength(Lb),当以链式映像实现抽象数据类型线性表时为:O(ListLength(La)+ListLength(Lb),例2-3,算法时间复杂度,单链表优点：,(1)能有效利用存储空间；(2)用“指针”指示数据元素之间的后继关系，便于进行“插入”、“删除”等操作。,单链表缺点：,(1)不能随机存取数据元素；(2)它还丢失了一些顺序表有的长处，如线性表的“表长”（单链表中表长是一个隐含值，必须从前到后遍历整个表才能得到）和数据元素在线性表中的“位序”；（3）不便于在表尾插入元素，需遍历整个表才能找到插入的位置。,为了更突出链表的优势，需改进单链表结构的定义。,1增加“表长”、“表尾指针”、“当前位置的 指针”和“当前序号”四个数据域；,2将基本操作中的“位序 i”改变为“指针 p”。,四、一个改进的带头结点的线性链表 类型,typedef struct LNode/结点类型 ElemType data;struct LNode*next;*Link;,typedef struct/链表类型 Link head,tail;/分别指向头结点和/最后一个结点的指针 int len;/指示链表长度 Link current;/指向当前被访问的结点/的指针，初始位置指向头结点 int curpos;/指示当前指针所指结点的/位序,初值为0 OrderedLinkList;,基本操作（自学）见教材P37-38,静态链表（自学）见教材P31-34循环链表双向链表双向循环链表,五、其它形式的链表,最后一个结点的指针域又指向头结点。,1.循环链表,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,a1 a2.an,为了既能立即找到链表的尾结点，也容易找到链表中的第一个结点，可以将头指针设成指向最后一个结点。,a1 a2.an,2.双向链表,typedef struct DuLNode ElemType data;/数据域 struct DuLNode*prior;/指向前驱的指针域 struct DuLNode*next;/指向后继的指针域 DuLNode,*DuLinkList;,双向链表也是由指向头结点的头指针唯一确定，若将头尾结点链接起来则构成双向循环链表。空的双向循环链表则由只含一个自成双环的头结点表示。,空表,非空表,a1 a2.an,双向链表的操作特点：,“查询”和单链表相同,“插入”和“删除”需要同时修改两个方向上的指针。,s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;,p,s,插入,删除,q=p-next；p-next=q-next;p-next-prior=p;delete(q);,q,p,