线性表的链式存储结构.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; / 指向后继的指针域 DuLNo