数据结构第二章线性表.ppt

第二章 线性表 * 线性结构的基本特征为: 1集合中必存在唯一的一个“第一元素” ； 2集合中必存在唯一的一个 “最后元素” ； 3除最后元素在外，均有 唯一的后继； 4除第一元素之外，均有 唯一的前驱。 线性结构 是一个数据元素的有序（次序）集合。 线性表是一种最简单的线性结构 2.1 线性表的类型定义 2.3 线性表类型的链式表示和实现 2.4 一元多项式的表示及相加 2.2 线性表类型的顺序表示和实现 本章主要内容： 二、线性表的抽象数据类型表示(教材P19) ADT List ADT List 数据对象： 数据关系： 基本操作： D=ai | aiElemSet, i=1,2,n,n0 R= | ai 1, ai D, i=2,n InitList( /建空表，初始化 DestoryList( /撤销表，释放内存 int LengthList( L ); /求表中元素个数，即表长 PriorElem( L, cur_e, /求当前元素cur_e的前驱 NextElem( L, cur_e, /求当前元素cur_e的后继 ListInsertBefore( /在第i个元素之前插入新的元素e ListDelete( /删除第i个元素并返回此元素 2.1 线性表的类型定义 抽象数据类型线性表的定义细解： ADT List 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长; n=0 时的线性表为空表。 数据关系： R1 |ai-1 ,aiD, i=2,.,n 2.1 线性表的类型定义 简言之，一个线性表是n个数据元素 (a1， a2,，ai， ，an)的有限序列。称 i 为 ai 在线 性表中的位序。 基本操作： 结构初始化操作 结构销毁操作 引用型操作 加工型操作 ADT List InitList( 2依值在线性表LA中进行查访; 3若不存在，则插入之。 GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e) 操作步骤： GetElem(Lb, i, e); / 取Lb中第i个数据元素 赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的数据元素，则插入 之 void union(List /求线性表的长度 Lb_len = ListLength(Lb); for (i = 1; i , a1 a2 ai-1 ai an A1 a2 ai-1 ai ean 表的长度增加 Status ListInsert_Sq(SqList / q 指示插入位置 for (p = p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表长增1 return OK; /见下页/ 元素右移 if (L.length = L.listsize) / 当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 if (i L.length+1) return ERROR; / 插入位置不合法 算法：2.4 算法时间复杂度为:O( ListLength(L) ) 考虑移动元素的平均情况: 假设在第 i 个元素之前插入的概率为 Pi，则 在长度为n 的线性表中插入一个元素所需移动元素 次数的期望值为： 若假定在线性表中任何一个位置上进行插入的概 率都是相等的，则移动元素的期望值为： Eis=pi(n-i+1) n+1 i=1 Eis=pi(n-i+1)= n+1 i=1 1 n+1 (n-i+1)= n+1 i=1 n 2 21 18 30 75 42 56 87 21 18 30 75 例如：ListInsert_Sq(L, 5, 66) L.length-1 0 ppp q 87564266 q = / q 指示插入位置 for (p = p = q; - -p) *(p+1) = *p; p 线性表操作: ListDelete( p L.length) return ERROR; / i值不合法 算法：2.5 考虑移动元素的平均情况: 假设删除第 i 个元素的概率为 qi , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望 值为： 若假定在线性表中任何一个位置上进行删除的概 率都是相等的，则移动元素的期望值为： Edl=qi(n-i) n i=1 n Edl=qi(n-i)= n i=1 1 n (n-i)= i=1 n-1 2 21 18 30 75 42 56 87 21 18 30 75 L.length-1 0 ppp q 8756 p = q = L.elem+L.length-1; for (+p; p next; j = 1; / p指向第一个结点，j为计数器 while (p +j; / 顺指针向后查找，直到 p 指向第 i 个元素 / 或 p 为空 if ( !p | ji ) return ERROR; / 第 i 个元素不存在 e = p-data; / 取得第 i 个元素 return OK; 算法：2.8 ai-1 线性表的操作 ListInsert( j = 0; while (p +j; / 寻找第 i-1 个结点 if (!p | j i-1) return ERROR; / i 大于表长或者小于1 s = (LinkList) malloc ( sizeof (LNode); / 生成新结点 s-data = e; s-next = p-next; p-next = s; / 插入 return OK; 算法：2.9 线性表的操作ListDelete ( p-next = q-next; e = q-data; free(q); p q Status ListDelete_L(LinkList L, int i, ElemType 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); return OK; 算法：2.10 操作 ClearList( L-next=p-next; / ClearList free(p); 算法时间复杂度：O(ListLength(L) 算法：2.11 如何从线性表得到单链表？ 链表是一个动态的结构，它不需要予分配空间 ，因此生成链表的过程是一个结点“逐个插入” 的过程。 例如：逆位序输入 n 个数据元素的值，建立带 头结点的单链表。 操作步骤： 一、建立一个“空表”； 二、输入数据元素an，建立结 点并插入； 三、输入数据元素an-1，建立结点 并插入； an an an-1四、依次类推，直至输入a1为止。 void CreateList_L(LinkList L-next = NULL; / 先建立一个带头结点的单链表 for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); /生成新结点 scanf( / 输入元素值 p-next = L-next; L-next = p; / 插入到表头 算法：2.12 回顾 2.1 节中三个例子的算法，看一下当线 性表分别以顺序存储结构和链表存储结构实现时 ，它们的时间复杂度为多少？ void union(List Lb_len =ListLength(Lb); for (i = 1; i next = pa ? ? pa: pb ; /插入非空表的剩余段 while(pa pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pa=La-next; pb=Lb-next; Lc=pc=La； /有头结点 见P31算法2.12 ?是条件运算符（为真 则取第1项） 2.3 线性表的链式表示和实现 最后一个结点的指针域的指针又指向第一个结 点的链表。 a1 a2 . an 2.3.2 循环链表 和单链表的差别仅在于，判别链表中最后一个 结点的条件不再是“后继是否为空”，而是“后继是否 为头结点”。 2.3.3 双向链表 typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList; 在每个结点中有两个指针域，其一指向直接后 继，另一指向直接前驱。 在C语言中可描述如下： 双向循环链表 空表 非空表 a1 a2 . an 双向链表的操作特点： 1、“查询” 和单链表相同。 2、“插入” 和“删除”时需要同时修改两个 方向上的指针。 双向链表的插入操作： 设p已指向第 i 元素，请在第 i 个元素前插入元素 x x的前驱是ai-1： s-prior = p -prior ; ai-1的后继是x： p-prior-next = s ; x的后继是ai： s-next = p ; ai 的前驱是 x：p-prior = s ; 注意：要修改 双向指针！ x s ai-1 ai 指针域的变化： p Status ListInsert_ DuL (DuLinkList /等于表长加1时,指向头结点; /大于表长加1时,p=NUL if (!(s=(DuLinkList) malloc(sizeof (DuLNode) return ERROR; s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return OK; / ListInsert_ DuL 算法：2.18 指针域的变化： 后继方向：ai-1的后继由 ai ( 指针p)变为 ai+1(指针 p -next ); p -prior-next = p-next ; ai-1 ai+1 ai p 双向链表的删除操作： 设p指向第 i 个元素，删除第 i 个 元素 注意：要修改 双向指针！ 前驱方向：ai+1 的前驱由 ai ( 指针p)变为ai-1 (指针 p - prior ); p-next-prior = p -prior ; Status ListDelete_ DuL (DuLinkList /p=NULL，即第i个元素不存在 e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free (p); return OK; / ListDelete_ DuL 算法：2.19 在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn) 一元多项式 2.4 一元多项式的表示和相加 但是对于形如 S(x) = 1 + 3x10000 2x20000 的多项式，上述表示方法是否合适？ n nn xpxpxppxp+=.)( 2 210 一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem 其中：pi 是指数为ei 的项的非零系数， 0 e1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指数值ai中的指数值 CreatPolyn ( / 系数 int expn; / 指数 term, ElemType; typedef OrderedLinkList polynomial; / 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为: Status CreatPolyn ( polynomail e.coef = 0.0; e.expn = -1; SetCurElem (h, e); / 设置头结点的数据元素 for ( i=1; i0的元素的前驱的位置，/并 返回FALSE Status OrderInsert (LinkList /按有序判定函数compare()的约定，将值为e的结 /点插入到有序链表L的适当位置上 void AddPolyn (polynomial hb = GetHead (Lb); /ha和hb分别指向La和Lb的头结点 pa = NextPos ( La, ha); pb = NextPos ( Lb, hb); /pa和pb分别指向La和Lb中当前结点 while ( pa b = GetCurElem ( pb ); /a和b为两表中当前比较元素 switch (*cmp(e1, e2) case -1: / 多项式PA中当前结点的指数值小 ha=qa; qa = NextPos ( Pa, qa); break; case 0: / 两者的指数值相等 sum= a.coef + b.coef ; if ( sum != 0.0 ) /修改多项式PA中当前结点的系数值 SetCurElem (qa, sum); ha=qa; else /删除多项式PA中当前结点 DelFirst (ha, qa); FreeNode (qa); DelFirst(hb, qb); FreeNode(qb); qb=NextPos ( Pb, qb); qa = NextPos ( Pa, qa); break; case 1: /多项式PB中当前结点的指数值小 DelFirst (hb, qb); InsFirst (ha, qb); qb =NextPos ( Pb, qb); ha = NextPos ( Pa, qa); break; /switch /while if (!ListEmpty (Pb) Append (Pa, qb); /链接Pb中剩余结点 FreeNode (hb); / 释放Pb的头结点 / AddPolyn 算法：2.23 本章小结 1.了解线性表的逻辑结构特性是数据元素之间存在着 线性关系，在计算机中表示这种关系的两类不同的存 储结构是顺序存储结构和链式存储结构。用前者表示 的线性表简称为顺序表，用后者表示的线性表简称为 链表。 2.熟练掌握这两类存储结构的描述方法，以及线性表 的各种基本操作的实现。 3.能够从时间和空间复杂度的角度综合比较线性表两 种存储结构的不同特点及其适用场合。 1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾结点， 试从下列提供的答案中选择合适的语句序列。 a.在P结点之后插入S结点的语句序列是 。 b.在P结点之前插入S结点的语句序列是 。 c.在表首插入S结点的语句序列是 。 d.在表尾插入S结点的语句序列是 。 （1）p-next=s; （2）p-next=p-next-next; （3）p-next=s-next; （4）s-next=p-next; （5）s-next=L; （6）s-next=NULL; （7）Q=p; （8）while(p-next!=Q) p=p-next; （9）while(p-next!=NULL) p=p-next; （10）p=Q; （11）p=L; （12）L=S; （13）L=p; 练习 2、已知L是表头结点的非空单链表，且P结点既不是首元结点，也不是尾