《中国计量学院数据结构第2章 线性表》由会员分享，可在线阅读，更多相关《中国计量学院数据结构第2章 线性表（48页珍藏版）》请在金锄头文库上搜索。
1、1,2 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加,2,线性结构的基本特征,在数据元素的非空有限集中 1必存在唯一的 “第一个”元素 2必存在唯一的 “最后一个”元素 3除最后一个元素外，均有唯一的后继 4除第一个元素之外，均有唯一的前驱,3,2.1 线性表的类型定义,线性表 n个数据元素的有限序列 eg. （a1 , , ai-1 , ai , ai+1 , , an ） ai-1是ai的前驱，ai+1是ai的后继,4,ADT List ,数据对象：,D ai | ai ElemSet, i=1,2,.,n
2、, n0 n 为线性表的表长; n=0 时为空表。,数据关系：,R1 |ai-1 , aiD, i=2,.,n ,设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。,抽象数据类型线性表的定义,5,基本操作：,InitList( &L ) 操作结果：初始化，即构造一个空表L DestroyList( &L ) 初始条件：线性表 L 已存在 操作结果：销毁线性表 L ClearList( &L ) 初始条件：线性表L已存在 操作结果：清除表L，即将L重置为空表,6,ListEmpty( L ) 初始条件：线性表L已存在 操作结果：若L为空表
3、，则返回TRUE， 否则FALSE ListLength( L ) 初始条件：线性表L已存在 操作结果：返回L中数据元素个数,7,GetElem( L, i, &e ) 初始条件：线性表L已存在， 且 1iLengthList(L) 操作结果：用 e 返回L中第 i 个元素的值,8,ListInsert( &L, i, e ) 初始条件：线性表L已存在，且 1iLengthList(L)+1 操作结果 ：在L的第i个位序 插入新的元素e，L的长度增1,9,ListDelete(&L, i, &e) 初始条件：线性表L已存在且非空， 1iLengthList(L) 操作结果：删除L的第i个元素，
4、并用 e返回其值，L的长度减1 ADT List,10,2.2 线性表的顺序表示和实现,顺序结构 用连续的存储单元依次存储数据元素 相邻元素ai和ai+1存储在计算机内相邻的物理位置 顺序表 用顺序结构表示的线性表 可用动态数组来表示顺序表,11,用一组连续的存储单元 依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表的起始地址 称作线性表的基地址,12,例如：顺序表,L.length,13,(a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai, , an), ,ListInsert( &L, i, e ),共移动几次？,n i +1,1
5、4,移动元素的平均情况:,假设在第 i 个位序插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需移动次数的期望值(平均值)为：,若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：,O ( n ),15,例如：ListInsert_Sq(L, 5, 66),L.length-1,0,87,56,42,66,16,线性表操作 ListDelete(&L, i, &e)的实现：,首先分析：,删除元素时， 线性表的逻辑结构发生什么变化？,17,(a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an),ai+1
6、,an, ,表的长度减少,共移动几次？,n - i,18,移动元素的平均情况:,假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动次数的期望值为：,若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：,O ( n ),19,L.length-1,0,87,56,例如：ListDelete_Sq(L, 5, e),20,顺序表操作的时间复杂度,访问 插入 删除 查找,O(1),O(n),O(n),O(n),插入和删除要移动大量数据， 不是最佳方案,21,2.3 线性表的链式表示和实现,链式存储特点 用一组任意的存储单元存储数据 存储单元可以
7、是连续的，也可以是不连续的 结点 每个数据元素除了要存储自身的信息之外，还要存储其后继的元素信息。,指针,22,数据元素 + 指针 = 结点 链表 由若干个结点构成的线性表 线性链表（单链表） 结点中除了数据域，只包含一个指针域,数据域,指针域,以线性表第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。,头指针,有时为了操作方便，在第一个结点之前附加一个“头结点”，头结点的数据域可以存储附加信息，其指针域指向第一个结点,线性表为空表时， 头结点的指针域为空,24,LinkList L ; / L 为单链表的头指针,结点和单链表的 C 语言描述,typedef struct LNo
8、de ElemType data ; / 数据域 struct LNode *next ; / 指针域 Lnode , * LinkList ;,25,线性表的操作 GetElem(L, i, &e) 在单链表中的实现:（设 i=3）,j,1,2,3,26,取第i个元素,Status GetElem_L(LinkList ,27,线性表的操作 ListInsert(&L, i , e) 在单链表中的实现：,有序对 改变为 和,28,因此，在单链表中第 i 个结点之前进行插入的基本操作为: 找到线性表中第i-1个结点，然后修改其指向后继的指针。,可见，在链表中插入结点只需要修改指针。若在第 i
9、个结点之前插入元素，修改的是第 i-1 个结点的指针。,Status ListInsert_L(LinkList &L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法 / 在链表中第i 个结点之前插入新的元素 e ,算法的时间复杂度为:,O(ListLength(L),Lnode *p = L; int j = 0; while (p / i 大于表长或者小于1,30,s = (LinkList) malloc ( sizeof (LNode); / 生成新结点 s-data = e; s-next = p-next; p-next = s; / 插入 re
10、turn OK;,s,p,e,31,线性表的操作 ListDelete (&L, i, &e) 在链表中的实现:,有序对 和 改变为 ,32,在单链表中删除第i个结点的基本操作为:找到第i-1个结点，修改其指向后继的指针。,q = p-next; p-next = q-next; e = q-data; free(q);,p,q,Status ListDelete_L(LinkList &L, int i, ElemType &e) / 删除单链表L中第 i 个结点 ,算法的时间复杂度为:,O(ListLength(L),p = L; j = 0; while (p-next / 删除位置不合
11、理,q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK;,34,如何创建单链表？,链表是一个动态的结构，它不需要事先分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。,35,例如：输入 n 个数据元素的值， 建立带头结点的单链表。,操作步骤：,一、建立一个“空表”；,二、输入数据元素，建立结点并插入；,三、重复二，直至输入n个数据为止。,36,四、其它形式的链表,1. 双向链表 typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *
12、prior; / 指向前驱 struct DuLNode *next; / 指向后继 DuLNode, *DuLinkList;,37,最后一个结点的指针域的指针又指回第一个结点的链表,a1 a2 . an,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,2. 循环链表,38,双向循环链表,空表,非空表,a1 a2 . an,39,在计算机中，可以用一个线性表来表示: P = ( p0 , p1 , ，pn ),但是对于形如 S(x) = 1 + 3x10000 2x20000 的多项式，上述表示方法是否合适？,2.4 一元多项式的表示,4
13、0,一般情况下的一元稀疏多项式可写成 P(x) = p1xe1 + p2xe2 + + pmxem 其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 em = n,可以用下列线性表表示： （p1, e1）, (p2, e2), , (pm, em) ）,41,P999(x) = 7x3 - 2x12 - 8x999,例如:,可用如下线性表表示 ( (7, 3), (-2, 12), (-8, 999) ),42,ADT Polynomial 数据对象： 数据关系：,抽象数据类型一元多项式的定义,D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每个
14、元素包含一个 表示系数的实数和表示指数的整数 ,R1 | ai-1 , aiD, i=2,.,n 且ai-1中的指数值ai中的指数值 ,43,CreatPolyn ( &P, m ) DestroyPolyn ( &P ) PrintPolyn ( &P ),基本操作：,操作结果：输入 m 项的系数和指数， 建立一元多项式 P。,初始条件：一元多项式 P 已存在。 操作结果：销毁一元多项式 P。,初始条件：一元多项式 P 已存在。 操作结果：打印输出一元多项式 P。,44,PolynLength( P ) AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa, &
15、Pb ) ADT Polynomial,初始条件：一元多项式 P 已存在。 操作结果：返回一元多项式 P 中的项数。,初始条件：一元多项式 Pa 和 Pb 已存在。 操作结果：完成多项式相加运算，即： Pa = PaPb，并销毁一元多项式 Pb。,45,一元多项式的实现,typedef struct / 项的表示 float coef; / 系数 int expn; / 指数 term, ElemType;,typedef LinkList polynomial; / 用带表头结点的有序链表表示多项式,结点的数据元素类型定义为:,46,Status CreatPolyn ( polynomail &P, int m ) / 输入m项的系数和指数，建立表示一元多项式的有序链表P ,InitList (P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); / 设置头结点的数据元素,for ( i=1; i=m; +i )
