ds第二章 线性表

ds第二章 线性表

ID:45847570

大小:934.00 KB

页数:63页

时间:2019-11-18

ds第二章 线性表_第1页
ds第二章 线性表_第2页
ds第二章 线性表_第3页
ds第二章 线性表_第4页
ds第二章 线性表_第5页
资源描述:

《ds第二章 线性表》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加专升本社会类要求:第2章线性表(熟练掌握)2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4线性表应用举例2.1线性表的类型定义线性表(LinearList):由n(n≧)个数据元素(结点)a1,a2,…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表,常常将非空的线性表(n>0)记作:(a1,a2,…an)这里的数据元素ai(1

2、≦i≦n)只是一个抽象的符号,其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表(A,B,C、…、Z)例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。(6,17,28,50,92,188)例3、学生健康情况登记表如下:姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….从以上例子可看出线性表的逻辑特征是:在非空的线性表,有且仅有一个开始结点a1,它没有直接前趋,而仅有一个直接后继a2;有且仅有一个终端

3、结点an,它没有直接后继,而仅有一个直接前趋an-1;其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的,而运算的具体实现则是在存储结构上进行的。抽象数据类型的定义为:P19算法2.1例2-1利用两个线性表LA和LB分别表示两个集合A和B,现要求一个新的集合A=A∪B。voidunion(List&La,ListLb){La-len=listlength(La);Lb-len=listlength(Lb);for(I=1;I<=Lb-len;I++){get

4、elem(Lb,I,e);if(!locateelem(La,e,equal))listinsert(La,++La-len,e)}}算法2.2例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的元素仍按值非递减有序排列。此问题的算法如下:voidmergelist(listla,listlb,list&lc)initlist(lc);i=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while((i<=la-len)&&(j<=

5、lb-len)){getelem(la,i,ai);getelem(lb,j,bj);if(ai<=bj){listinsert(lc,++k,ai);++i;}else{listinsert(lc,++k,bj);++j;}}while(i<=la-len){getelem(la,i++,ai);listinsert(lc,++k,ai);}while(j<=lb-len){getelem(lb,j++,bj);listinsert(lc,++k,bi);}}2.2线性表的顺序存储结构2.2.1线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储

6、单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用l个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第I+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(aI)之间满足下列关系:LOC(ai+1)=LOC(ai)+l线性表的第i个数据元素ai的存储位置为:LOC(ai)=LOC(a1)+(i-1)*l由于C语言中的一维数组也是采用顺序存储表示,故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外,顺序表还应该用一个变量来表示线性表的长度属性,所以我们用结构类型来定义顺

7、序表类型。#defineListSize100typedefintDataType;typedefstruct{DataTypedata[ListSize];intlength;}Sqlist;2.2.2顺序表上实现的基本操作在顺序表存储结构中,很容易实现线性表的一些操作,如线性表的构造、第i个元素的访问。注意:C语言中的数组下标从“0”开始,因此,若L是Sqlist类型的顺序表,则表中第i个元素是l.data[i-1]。以下主要讨论线性表的插入和删除两种运算。1、插入线性表的插入运算是指在表的第i(1≦i≦n+1)个位置上,插入一个新结点x,使长度为n

8、的线性表(a1,…ai-1,ai,…,an)变成长度为n+1的线性表(a1,…a

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。