《数据结构.第2章.线性表.1.链式》由会员分享，可在线阅读，更多相关《数据结构.第2章.线性表.1.链式（40页珍藏版）》请在金锄头文库上搜索。
1、武汉科技大学Wuhan University of Science and Technology数据结构数据结构 Data StructuresData Structures张 凯 计算机学院 软件工程系2011年3月12日一元多项式的表示及相加第2章 线性表线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现2.3 线性表的链式表示及实现v线性表的链式表示v线性表的链式实现v链表的运算效率分析v线性表的链式表示 逻辑上相邻，物理上不一定相邻2.3 线性表的链式表示及实现a 201BH b 1087H z NULLa1 a2 an / HeadHeadDataLinkDataLinkD
2、ataLinkDataLink链表存放示意图如下：(a，b，c，d，e , z)v线性表的链式表示 线性表的链式存储结构，也称为链表。 数据元素通过指针表示数据元素之间的关系。2.3 线性表的链式表示及实现a1 a2 an / Head特点1：每个存储结点都包含两部分：数据和 。特点2：在单链表中，除了首元结点外，任一结点的存储位置由 指示。 其直接前驱结点的链域的值指针域(链域)v线性链表的有关术语 结点: 数据元素的存储映像。由数据域和指针域两部分组成； 链表: n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为链式存储结构2.3 线性表的链式表示及实现信息域 指针域结点的结构i
3、nfo nexta1 a2 an / Headv线性链表的有关术语 头指针: 是指向链表中第一个结点(或为头结点或为首元结点)的指针。 单链表可由一个头指针唯一确定。2.3 线性表的链式表示及实现a1 a2 an / Head头指针v线性链表的有关术语 头结点: 是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息; 首元结点: 存储第一个数据元素a1的结点2.3 线性表的链式表示及实现a1 an / Head首元结点头结点v线性链表的有关术语 链表设置头结点的作用 插入或删除表中任何结点，都需修改前一结点的 指针域。若链表没有头结点，则首元素结点没有 前驱结点，在其前插入结
4、点或删除结点时需单独 处理，操作较复杂。 带头结点的链表，链表指针是指向头结点的非空 指针，因此空表与非空表的处理是一样的。2.3 线性表的链式表示及实现v一个线性表的逻辑结构为:2.3 线性表的链式表示及实现（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其 存储结构用单链表表示如下，请问其头指针的值是多少 ？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向 链表中第一个结点 的指针，因此关键 是要寻找第一个结 点的地址。ZHAO 7 HeadDataLink3
5、1v上例链表的逻辑结构示意图有以下两种形式2.3 线性表的链式表示及实现区别： 无头结点 有头结点ZHAO QIAN SUNLIHeadZHOU WU ZHENG WANG /ZHAO QIAN SUNLIHeadZHOU WU ZHENG WANG /v线性表的单链表存储结构2.3 线性表的链式表示及实现Typedef struct Lnode ElemType data; /数据域struct Lnode *next; /指针域Lnode, *LinkList; / *LinkList为Lnode类型的指针v线性链表的实现 1.单链表的建立 2.单链表的查找 3.单链表的插入 4.单链表的
6、删除 5.其它链表形式2.3 线性表的链式表示及实现v单链表的建立 难点分析：每个数据元素在内存中是“零散”存放的，其首地址怎么找？又怎么一一链接？ 实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将地址送给前面的指针。2.3 线性表的链式表示及实现v单链表的建立2.3 线性表的链式表示及实现操作步骤： 一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，建立结点并插入；an四、依次类推，直至输入a1为止。anan-1v单链表的建立2.3 线性表的链式表示及实现Void CreateList_L (LinkList Lnext = NU
7、LL; / 先建立一个带头结点的单链表for ( i =n; i0; -i) p=(LinkList)malloc (sizeof(LNode); / 生成新结点scanf ( / 输入元素值pnext = Lnext ; Lnext = p; / 插入到表头 / CreateList_Lv单链表的查找 难点：单链表中想取得第i个元素，必须从头指针出发寻找(顺藤摸瓜)，不能随机存取 。 思路：要修改第i个数据元素，关键是要先找到该结点的指针p，然后用p-data=new_value 即可。2.3 线性表的链式表示及实现v单链表的查找 例1：单链表中 GetElem(L,i, j=1; / 初始
8、化 ,p指向第一个结点,j为计数器while(p +j;/ 顺指针向后查找,直到p指向第i个元素或p为空if(!p|ji) return ERROR; / 第i个元素不存在e=p-data; / 取第i个元素return OK; / GetElem_Lv单链表的插入 单链表中 ListInsert( / 生成新结点 if ( s = NULL) return ERROR; s-data = e; s-next = p-next; p-next = s; / 插入 return OK;(2)(1)(3)eai-1ai-1 spaiv单链表的插入 可见，在链表中插入结点只需修改指针。但同时，若要在
9、第 i个结点之前插入元素，修改的是第 i-1个结点的指针。 因此，在单链表中第 i个结点之前进行插入的基本操作为：找到线性表中第i-1个结点，然后修改其指向后继的指针。2.3 线性表的链式表示及实现v单链表的插入2.3 线性表的链式表示及实现status ListInsert(LinkList j = 0;while (p +j;if (! p | j i-1) return ERROR;s = (LinkList) malloc (sizeof(LNode);s - data=e; s-next= p - next;p - next = s;return OK; / ListInsert_l
10、算法的时间复杂度为： O(ListLength(L)ai-1ai-1v单链表的删除 单链表中 ListDelete( p-next = q-next; e = q-data; free(q); pqv单链表的删除2.3 线性表的链式表示及实现Status ListDelete_L(LinkList j = 0;while (p-next +j; / 寻找第 i 个结点，并令 p 指向其前趋if (!(p-next) | j i-1) return ERROR; / 删除位置不合理q = p-next; p-next = q-next; / 删除并释放结点e = q-data; free(q);
11、return OK; / ListDelete_L算法的时间复杂度为: O(ListLength(L)2.3 线性表的链式表示及实现考虑虑如何将两个有序链链 表并为为一个有序链链表？v单链表的合并 已知：线性表 A、B，分别由单链表 LA , LB 存储，其中数据元素按值非递减有序排列， 要求：将 A ，B 归并为一个新的线性表C , C 的数据元素仍按值非递减排列 。设线性表 C 由单链表 LC 存储。 假设: A=(3，5，8，11) B=(2，6，8，9，11) 预测:合并后 C =(2 , 3 , 5 , 6 , 8 , 8 , 9 , 11 , 11)2.3 线性表的链式表示及实现v
12、单链表的合并 A、B、C用链表可表示为2.3 线性表的链式表示及实现3 511 / 8LA2 611 / 8LB92 3 6 5LC811 8 911 /v单链表的合并 算法主要包括：搜索、比较、插入三个操作： 搜索：需要两个指针搜索两个链表； 比较：比较结点数据域中数据的大小； 插入：将两个结点中数据小的结点插入新链表2.3 线性表的链式表示及实现v单链表的合并2.3 线性表的链式表示及实现3 511 / 8LA2 611 / 8LB92 3 5 6LC8 8 911 11 /PaPbPcPcPaPbPaPbPaPbPbPcPcPcPcPcPcPcv单链表的合并2.3 线性表的链式表示及实现
13、Void MergeList_L(LinkList /释放Lb的头结点 /MergeList_Lpc-next = pa?pa:pb ; /插入剩余段while(pa pc=pa; pa=pa-next;else pc-next=pb; pc=pb; pb=pb-next pa=Lanext; pb=Lbnext; Lc=pc=La； /初始化 v其它链表形式2.3 线性表的链式表示及实现1）双向链表：有两个指针域的链表，称为双链表。# Headprior data nextA. 结点结构B. 特点：可以双向查找表中结点a1 a2 an /# Head空表v其它链表形式2.3 线性表的链式表示
14、及实现1）双向链表：插入运算s-next = p-next; p-next = s;s-next-prior = s; s-prior = p;ai-1 aie spv其它链表形式2.3 线性表的链式表示及实现1）双向链表：删除运算p-next = p-next-next;p-next-prior = p;ai-1 aipai+1v其它链表形式2.3 线性表的链式表示及实现2）循环链表：将表中最后一个结点的指针域指向头结 点( p-next=head)，整个链表形成一个环。# a1 an HeadB.与单链表的区别 (循环条件)和单链表的差别仅在于，判别链表中最后一个结点的条 件不再是“后继是否为空”，而是“后继是否为头结点”。A.特点：从任一结点出发均可找到表中其他结点。v时间效率分析 查找: 因线性链表只能顺序
