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

1、第5讲 线性表的 链式存储结构,主讲人：陈红丽,2.3 线性表类型 的实现-链式映象,用一组地址任意的存储单元存放线性表中的数据元素,一、单链表,以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的映象,以“结点的序列”表示线性表 称作链表,以线性表中第一个数据元素 的存储地址作为线性表的基地址，称作线性表的头指针,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前附加一个“头结点”，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点。通常称这类单链表为带头结点的单链表,空指针,线性表为空表时， 头结点的指针域为空,结点类型：

2、 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 “

3、指向”该结点。 当指针 p 所指结点不再使用，可用 delete p; 释放此结点空间,三、单链表操作的实现,GetElem(L, i, if (!L) exit(1); / 存储空间分配失败L-next = NULL,操作 DestroyList ( j = 1; / p指向第一个结点，j为计数器,while (p / 顺指针向后查找，直到 p 指向第 i 个元素或 p 为空,if ( !p | ji ) return FALSE; / 第 i 个元素不存在 e = p-data; / 取得第 i 个元素 return OK,线性表的操作 ListInsert( j = 0; while (

4、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 ( p-next = q-next; e = q-data; delete(q,p,q,Status ListDelete_L(LinkList j = 0; while (p-next / 寻找第 i 个结点，并令 p

5、指向其前趋,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( if (!L) exit(1); / 存储空间分配失败 L-next = NULL; / 先建立一个带头结点的单链表,for (i = n;

6、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,控制结构

7、,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中不存

8、在和 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,当以顺序映像实现抽象数据类型线性表时为

9、: 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

10、( ListLength(La)+ListLength(Lb),当以链式映像实现抽象数据类型线性表时为: O( ListLength (La)+ListLength (Lb),例2-3,算法时间复杂度,单链表优点,1) 能有效利用存储空间； (2) 用“指针”指示数据元素之间的后继关系，便于进行“插入”、“删除”等操作,单链表缺点,1)不能随机存取数据元素 ； (2)它还丢失了一些顺序表有的长处，如线性表的“表长”（单链表中表长是一个隐含值，必须从前到后遍历整个表才能得到）和数据元素在线性表中的“位序”； （3）不便于在表尾插入元素，需遍历整个表才能找到插入的位置,为了更突出链表的优势，需改进

11、单链表结构的定义,1增加“表长”、“表尾指针” 、“当前位置的 指针”和“当前序号”四个数据域,2将基本操作中的“位序 i ”改变为“指针 p,四、一个改进的带头结点的线性链表 类型,typedef struct LNode / 结点类型 ElemType data; struct LNode *next; *Link,typedef struct / 链表类型 Link head, tail; / 分别指向头结点和 / 最后一个结点的指针 int len; / 指示链表长度 Link current; / 指向当前被访问的结点 /的指针，初始位置指向头结点 int curpos; / 指示当

12、前指针所指结点的 /位序,初值为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,双向链表也是由指向头结点的头指针唯一确定，若将头尾结点链接起来则构成双向循环链表。空的双向循环链表则由只含一个自成双环的