《数据结构》-线性表的链式表示和实现

2.1 线性表的类型定义,2.3 线性表的链式表示和实现,2.4 一元多项式的表示及相加,2.2 线性表的顺序表示和实现,第二章 线性表,2.3 线性表的链式表示和实现,线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，它的存储位置可用一个简单、直观的公式来表示。其主要缺点有下面两个： （1）作插入或删除操作时，需移动大量元素。 （2）在为长度变化较大的线性表预先分配存储空间时，必须按最大可能空 间分配（在某些情况下最大空间甚至是不可知的）。存储空间不能得 到充分利用。 而链式存储结构，它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。,2.3.1 线性链表,（1）定义 特点：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。 为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素 的存储映像，即结点（node）。如图2.4所示： 数据域 指针域 图2.4 结点结构 数据域：存储数据元素的信息。 指针域：存储直接后继的存储位置。 n个结点（ （1in）链结成一个链表，即为线性表 的链式存储结构。由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。,注意：整个链表的存取必须从头指针开始进行； 头指针指示链表中第一个结点的存储位置； 线性链表中最后一个结点的指针为“空”（NULL）。,例如：线性表（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG）共8个数据元素。其链式存储结构如图2.5所示： 存储地址 数据域 指针域 1 LI 43 头指针H 7 QIAN 13 13 SUN 1 31 19 WANG NULL 25 WU 37 31 ZHAO 7 37 ZGENG 19 43 ZHOU 25 图2.5 线性链表示例,（2）线性表的单链表存储结构的C语言描述 typedef struct LNodeElemTypedata;struct LNode*next;LNode, *LinkList;,（3）线性表的带头结点的单链表存储结构的图形表示带头结点的“空”单链表 L NULL带头结点的“非空”单链表 L a1 a2 an ,线性链表的逻辑状态,H,非空表,空表,线性表的操作 GetElem(L, i, &e)在单链表中的实现:,j,1,2,3,因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i,单链表是一种非顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。,令指针 p 始终指向线性表中第 j 个数据元素,Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针，以 e 返回第 i 个元素 / GetElem_L,算法时间复杂度为:,O(n),p = L-next; j = 1; / p指向第一个结点，j为计数器,while (p / 顺指针向后查找，直到 p 指向第 i 个元素 / 或 p 为空,if ( !p | ji ) return ERROR; / 第 i 个元素不存在e = p-data; / 取得第 i 个元素return OK;,（4）单链表的插入和删除运算 P a b (a)插入前 P a b s x (b)插入后图2.6 在单链表中插入结点时指针变化情况用语句描述如下：snext = pnext;pnext = s; P a b c图2.7 在单链表中删除结点时指针变化情况用语句描述如下：pnext pnextnext；,Status ListInsert_L (LinkList /ListInsert_L,单链表的插入运算,算法2.6如下：,Status ListDelete_L (LinkList /ListDelete_L,单链表的删除运算,算法2.7如下：,操作 ClearList(&L) 在链表中的实现:,void ClearList( / ClearList,delete(p);,算法时间复杂度：,O(n),如何从线性表得到单链表？,链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。,例如：逆位序输入 n 个数据元素的值， 建立带头结点的单链表。,操作步骤：,一、建立一个“空表”；,二、输入数据元素an， 建立结点并插入；,三、输入数据元素an-1， 建立结点并插入；,an,an,an-1,四、依次类推，直至输入a1为止。,void CreateList_L(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 / CreateList_L,算法的时间复杂度为:,O(n),L = new LNode; L-next = NULL; / 先建立一个带头结点的单链表,for (i = n; i 0; -i) p = new LNode; scanf( / 插入,（5） 算法2.8如下： void MergeList_L (LinkList /释放Lb的头结点 /MergeList_L,单链表的合并算法,（6）静态链表 C语言描述 #defineMAXSIZE100/链表的最大长度 typedefstruct ElemTypedata;intcur; component, SLinkListMAXSIZE;,图形表示 例如： 数组下标 数据域 指针域 0 1 1 ZHAO2 2 QIAN3 3 SUN4 4 LI9 5 ZHOU 6 6 WU7 7 ZHENG8 8 WANG0 9 SHI5 这种存储结构仍需要预先分配一个较大的空间，但在作线性表的插入和删除操作时不需要移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。,2.3.2 循环链表,（1）定义 循环链表（circular linked list）是另一种形式的链式存储结构。 特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环。 从表中任一结点出发均可找到表中其他结点。,（2）图形表示 H (a) 非空表 H (b)空表 图2.8 单循环链表 循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或pnext是否为空，而是它们是否等于头指针。,2.3.3 双向链表,（1）定义 双向链表（double linked list）：双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱。 前驱 数据元素 后继 图2.9 结点结构,（2）图形表示 L (a) 空的双向循环链表 L A B C (b) 非空的双向循环链表 图2.10 双向链表示例,（3）C语言描述typedef struct DulNode ElemTypedata;struct DulNode*prior;struct DulNode*next;DulNode, * DuLinkList;,（4）双向循环链表的插入和删除运算 P a b x s 图2.11 在双向链表中插入一个结点时指针的变化情况 P a b c 图2.12 在双向链表中删除结点时指针的变化情况,Status ListInsert_DuL (DuLinkList /ListInsert_DuL,双向循环链表的插入运算,算法2.9如下：,Status ListDelete_DuL (DuLinkList /ListDelete_DuL,双向循环链表的删除运算,算法2.10如下：,例子:集合运算,例：求解（AB）（BA） 使用静态链表法求解。即，由终端输入集合元素，先建立表示集合A的静态链表S，而后在输入集合B的元素的同时查找S表，若存在和B相同的元素，则从S表中删除之，否则将此元素插入S表。,为算法的清晰可见，我们先给出3个过程：,1，将整个数组空间初始化成一个链表。 算法2.11如下： void InitSpace_SL (SLinkList /InitSpace_SL,2，从备用空间取得一个结点。 算法2.12如下： int Malloc_SL (SLinkList /Malloc_SL,3