数据结构+DS02

1、（第二讲）（第二讲）绍兴文理学院绍兴文理学院计算机系计算机应用教研室计算机系计算机应用教研室2 第第2 2章章 线性表（线性表（1 1）3TKS 3 31 1、线性表的类型定义、线性表的类型定义 定义定义 线性表线性表(liner_list)(liner_list)是具有相同数据类型的是具有相同数据类型的n(n=0)n(n=0)个数个数据元素的有限序列，通常记为：据元素的有限序列，通常记为：(a(a1 1，a a2 2， a ai-1i-1，a ai i，a ai+1i+1，a an n) ) 其中其中n n为表长，为表长， n n0 0 时称为空表。时称为空表。 线性表结构例线性表结构例 例

2、例1 1：数学中的数列（数学中的数列（1111，1313，1515，1717，1919，2121） 例例2 2：英文字母表（英文字母表（A, B, C, D, EA, B, C, D, E Z Z）。）。 例例3 3：某单位的电话号码簿。某单位的电话号码簿。 姓姓 名名 电话号码电话号码 蔡蔡 颖颖 6321444463214444 刘建平刘建平 6321666663216666 王小林王小林 6321888863218888 张张 力力 6321555563215555 .4TKS 4 4 说明说明 ：线性表的数据元素可以是各种各样的，但同一线性表中的元线性表的数据元素可以是各种各样的，但同

3、一线性表中的元素必须是同一类型的；素必须是同一类型的； ：在表中在表中 a ai-1i-1领先于领先于a ai i，a ai i领先于领先于a ai+1i+1，称，称a ai-1i-1是是a ai i的直接前驱，的直接前驱，a ai+1i+1是是a ai i的直接后继；的直接后继；在线性表中，除第一个元素和最后一个元素之外，其他元素在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；特征的数据结构称为线性结构。线性表是一种线性

4、数据结构； ：a ai i是线性表的第是线性表的第i i 个元素，称个元素，称i i为数据元素为数据元素a ai i 的序号，每一个的序号，每一个元素在线性表中的位置，仅取决于它的序号；元素在线性表中的位置，仅取决于它的序号；5 例例 2-1 2-1 假设假设: :有两个集合有两个集合A A和和B B分别用两个线性表分别用两个线性表LALA和和LBLB表示，即表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合：线性表中的数据元素即为集合中的成员。现要求一个新的集合A=ABA=AB。上述问题可演绎为：上述问题可演绎为： 要求对线性表作如下操作：要求对线性表作如下操作：扩大线性表扩大

5、线性表LALA，将存在于线性表，将存在于线性表LBLB中而不存在于线性表中而不存在于线性表LALA中的数据元素插入到线性表中的数据元素插入到线性表LALA中去。中去。操作步骤：操作步骤： 从线性表从线性表LBLB中依次察看每个数据元素中依次察看每个数据元素; ;GetElem(L,i,&eGetElem(L,i,&e) ) ee 依值在线性表依值在线性表LALA中进行查访中进行查访; ; LocateElem(LA,e,equalLocateElem(LA,e,equal( )( ) 若不存在，则插入之。若不存在，则插入之。ListInsert(LA,n+1,e)ListInsert(LA,n

6、+1,e)TKS 5 56算法描述如下：算法描述如下： void union(List &La,List Lb) void union(List &La,List Lb) La_lenLa_len= =ListLength(LaListLength(La) ); / ; / 求线性表的长度求线性表的长度 Lb_lenLb_len= =ListLength(LbListLength(Lb) ); ; for(i=1;i=Lb_len;ifor(i=1;i=Lb_len;i+)+) GetElem(Lb,i,&eGetElem(Lb,i,&e) ); / ; / 取取LbLb中第中第i i个数据元

7、素赋给个数据元素赋给e e if(! if(!LocateElem(La,e,equalLocateElem(La,e,equal( )( ) ) ListInsert(La, +La_lenListInsert(La, +La_len, e), e); ; / La / La中不存在和中不存在和 e e 相同的数据元素，则插入之相同的数据元素，则插入之 / union/ unionTKS 6 67 例例 2-2 已知已知线性表线性表LALA和和LBLB中的数据元素按值非递减有序排列，现中的数据元素按值非递减有序排列，现要求将要求将LALA和和LBLB归并为一个新的线性表归并为一个新的线性表L

8、CLC，且，且LCLC中的数据元素仍按值中的数据元素仍按值非递减有序排列。非递减有序排列。上述问题可演绎为：上述问题可演绎为： 要求对线性表作如下操作：要求对线性表作如下操作：构造线性表构造线性表LCLC，将存在于线性表，将存在于线性表LALA和和LBLB中较小的数据元素插入到线性表中较小的数据元素插入到线性表LCLC中去。中去。 操作步骤：操作步骤： 从线性表从线性表LALA和和LBLB中依次察看每个数据元素中依次察看每个数据元素; ; GetElem(LA,i,&aiGetElem(LA,i,&ai) ) aiai GetElem(LB,i,&biGetElem(LB,i,&bi) ) b

9、ibi 把把aiai和和bibi较小的一个插入到较小的一个插入到线性表线性表LCLC中中; ; ListInsert(LC,+LC_len,ListInsert(LC,+LC_len,aiai) )或或ListInsert(LC,+LC_len,ListInsert(LC,+LC_len,bibi) ) 把余下的把余下的LALA或或LBLB中的元素插入到中的元素插入到LCLC中。中。 ListInsert(LC,+LC_len,ListInsert(LC,+LC_len,aiai) )或或ListInsert(LC,+LC_len,ListInsert(LC,+LC_len,bibi) )算法

10、描述如下：算法描述如下： TKS 7 78TKS 8 8void MergeList(List La,List Lb,List &Lcvoid MergeList(List La,List Lb,List &Lc) ) / 本算法将非递减的有序表本算法将非递减的有序表 La 和和 Lb 归并为归并为 Lc InitList(LcInitList(Lc) ); / 构造空的线性表构造空的线性表LcLc i=j=1;k=0;i=j=1;k=0; La_len La_len= =ListLength(La)ListLength(La);Lb_len;Lb_len= =ListLengthListLe

11、ngth(Lb(Lb); ); while(i= La_len)&(j=Lb_len while(i= La_len)&(j=Lb_len) / ) / LaLa 和和 LbLb 均不空均不空 GetElem(La,i+,ai)GetElem(La,i+,ai); ;GetElem(Lb,j+,bjGetElem(Lb,j+,bj) ); if(ai=bj)if(ai=bj)ListInsert(Lc,+k,ai)ListInsert(Lc,+k,ai);+i;+i; elseelse ListInsert(Lc,+k,aj)ListInsert(Lc,+k,aj);+j;+j; while(

12、i=La_len while(i=La_len) / ) / 当当LaLa不空时不空时 GetElem(La,i+,aiGetElem(La,i+,ai) ); ; ListInsert(Lc,+k,aiListInsert(Lc,+k,ai) ); ; / / 插入插入 La La 表中剩余元素表中剩余元素 9 while(j=Lb_len while(jn; / n; / 输入元素个数输入元素个数 for(i=0;in;ifor(i=0;il-elemi cinl-elemi; l-length=n; / l-length=n; / 当前表长当前表长 void listsqlist(sql

13、istvoid listsqlist(sqlist l) l)intint i; i; printf(nlistsqlist:n printf(nlistsqlist:n);); for(i=0;il.length;i+) for(i=0;il.length;i+) printf(%5d,l.elemi); printf(%5d,l.elemi); 补充例补充例1 1 建立建立一个顺序表一个顺序表 S2_1S2_114TKS 1414a a, a a1 1 a a2 2 a ai-1i-1 a ai i a an na ai i e ea an n表的长度增加表的长度增加 a a1 1 a a

14、2 2 a ai-1i-1 分析：分析：插入后使原表长为插入后使原表长为 n n的表的表: :(a(a1 1, ,a,ai-1i-1,a,ai i, ,a,an n) ) 成为表长为成为表长为 n+1 n+1 表表: (a: (a1 1, , ,a ai-1i-1,e,a,e,ai i, , a, an n) ) 算法描述算法描述15TKS 1515 Status ListInsert_Sq(SqList &L,int i,ElemType Status ListInsert_Sq(SqList &L,int i,ElemType e) e) / / 在顺序表在顺序表L L的第的第 i i 个

15、元素之前插入新的元素个元素之前插入新的元素e e, , / / i i 的合法范围为的合法范围为 11i iL.length+1L.length+1 if(iL.length+1) return ERROR if(iL.length+1) return ERROR；/ i/ i值不合法值不合法 q=&(L.elemi-1); / q q=&(L.elemi-1); / q 指示插入位置指示插入位置 for(p=&(L.elemL.length-1);p=q;-p) for(p=&(L.elemL.length-1);p=q;-p) * *(p+1)=(p+1)=* *p; / p; / 插入位

16、置及之后的元素右移插入位置及之后的元素右移 * *q=e; / q=e; / 插入插入e e +L.length +L.length; / ; / 表长增表长增1 1 return OK; return OK; / ListInsert_Sq / ListInsert_Sq 算法算法 2.4 2.4 顺序表中插入一个元素顺序表中插入一个元素 S2_2S2_2算法时间复杂度算法时间复杂度为为: :O( ListLength(L) )16TKS 1616pp p21 18 30 75 42 56 8721 18 3021 18 30 7575L.length-10q8787565642426666

17、p 例如：例如：ListInsert_Sq(LListInsert_Sq(L, 5, 66), 5, 66) 17 分析：分析：删除后使原表长为删除后使原表长为n n的线性表：的线性表： (a(a1 1，a a2 2，.，a ai-1i-1，a ai i，a ai+1i+1，.，a an n) ) 成为表长为成为表长为 n n1 1 的线性表：的线性表： (a(a1 1，a a2 2，.，a ai-1i-1，a ai+1i+1，.，a an n) )a, a a a1 1 a a2 2 a ai-1i-1 a ai i a ai+1 i+1 a an na ai+1i+1a an n表的长度减

18、少表的长度减少a a1 1 a a2 2 a ai-1i-1 算法描述算法描述 TKS 171718 Status ListDelete_Sq(SqList &L, int i, ElemType Status ListDelete_Sq(SqList &L, int i, ElemType &e) &e) if(iL.engthif(iL.ength) return ERROR; / ) return ERROR; / 删除位置不合法删除位置不合法 p=&(L.elemi-1); / p p=&(L.elemi-1); / p 为被删除元素的位置为被删除元素的位置 e=e=* *p; / p

19、; / 被删除元素的值赋给被删除元素的值赋给 q=L.elem+L.length-1; / q=L.elem+L.length-1; / 表尾元素的位置表尾元素的位置 for(+p;p=q;+p) for(+p;p=q;+p) * *(p-1)=(p-1)=* *p; / p; / 被删除元素之后的元素左移被删除元素之后的元素左移 -L.length; / -L.length; / 表长减表长减1 1 return OK; return OK; / ListDelete_Sq / ListDelete_Sq算法时间复杂度为算法时间复杂度为: : O(ListLength(L(ListLengt

20、h(L)假设在第假设在第i i个元素之前插入的概率为个元素之前插入的概率为p pi i，则在长度为，则在长度为n n的线性表的线性表中中插入一个元素所需移动元素次数的插入一个元素所需移动元素次数的期望值期望值为：为：TKS 1818 算法算法 2.5 2.5 顺序表中删除一个元素顺序表中删除一个元素 S2_3S2_319 假设删除第假设删除第 i 个元素的概率为个元素的概率为 p pi i, 则在长度为则在长度为n 的线性表中的线性表中删删除一个元素所需移动元素次数的除一个元素所需移动元素次数的期望值期望值为：为：niidlinqE1)( 假定在线性表中任何一个位置上进行插入和删除的假定在线性

21、表中任何一个位置上进行插入和删除的概率概率都是都是相相等等的，即：的，即：11npinqi1 则：则：2) 1(1111ninnEniis21)(11ninnEnidlTKS 191911) 1(niiisinpE20TKS 20204 4、顺序表的应用、顺序表的应用 例例1 1 在顺序表在顺序表L L中查找第中查找第1 1个值与个值与e e满足满足compare()compare()的元素的位序。的元素的位序。int LocateElem_sq(Sqlist L,ElemTypeint LocateElem_sq(Sqlist L,ElemType e,Status( e,Status(*

22、* compare) compare) (ElemType,ElemType (ElemType,ElemType) ) i=0;i=0; p=L.elem p=L.elem; ; while(iL.length & !( while(iL.length & !(* * compare)( compare)(* *p+,e) +i;p+,e) +i; if(iL.length) return i; if(iL.length) return i; else return -1; else return -1; / LocateElem_Sq/ LocateElem_Sq 算法算法 2.6 2.6 顺序表中查找一个元素顺序表中查找一个元素 S2_4S2_4 例例2 2 已知顺序线性表已知顺序线性表LaLa和和LbLb的元素按值的元素按值非递减排列，归并非递减排列，归并LaLa和和LbLb得到新的顺序线性表得到新的顺序线性表LcLc，LcLc的元素也按值的元素也按值非递减排列非递减排列 21TKS 2121 pa=La.elem;pb=Lb.elempa=La.elem;pb=Lb.elem; ; Lc.listsize=Lc.lengthLc.listsize=Lc.length=La.length+Lb.length=La.length+