PowerPoint 演示文稿 - 天津科技大学.ppt

《PowerPoint 演示文稿 - 天津科技大学.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加8/3/20211第二章线性表2.1线性表的类型定义线性表(LinearList)：由n(n≧)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(a1，a2，…,an)这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况

2、下可以不同。例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）8/3/20212第二章线性表例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….8/3/20213第二章线性表例4、一副扑克的点数（2，3，4，…，J，Q，K，A）从以上例子可看出线性

3、表的逻辑特征是：在非空的线性表中，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。8/3/20214第二章线性表含有n个元素的线性表是一个数据结构Linear_list=(D,R)其中D={ai

4、aiD0,i=1,2,,n,n0}R={N},N={

5、ai-1,aiD0,i=2

6、,3,,n}D0为某个数据对象（可为任何数据类型）对应的逻辑图如下：线性表与线性结构的关系。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。抽象数据类型的定义为：P19a1a2ai-1aian……8/3/20215第二章线性表线性表的操作还有合并、拷贝、排序等复杂运算例2-1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。voidunion(List&La，ListLb){La-len=listlength(La);Lb-len=listlengt

7、h(Lb);for(I=1;I<=lb-len;I++){getelem(lb，I，e);if(!locateelem(la，e，equal))listinsert(la，++la-en，e)}}时间复杂度为O(mn)8/3/20216第二章线性表例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：voidmergelist(listla，listlb，list&lc)initlist(lc)

8、;I=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while((I<=la-len)&&(j<=lb-len)){getelem(la，I，ai);getelem(lb，j，bj);8/3/20217第二章线性表if(ai<=bj){listinsert(lc，++k，ai);++I;}else{listinsert(lc，++k，bj);++j;}}while(I<=la-len){getelem((la，I++，ai);listinsert

9、(lc，++k，ai);}while(j<=lb-len){getelem((lb，j++，bj);listinsert(lc，++k，bi);}}//MergeList算法的时间复杂度分析(O(m+n))8/3/20218第二章线性表2.2线性表的顺序存储结构1顺序表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第I+1个数据元素的存储位置LOC(ai

10、+1)和第i个数据元素的存储位置LOC(aI)之间满足下列关系：LOC(ai+1)=LOC(ai)+l线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(I-1)*l8/3/20219第二章线性表由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。#defineListSize