数据结构2线性表

《数据结构2线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章数组2.1线性表2.2顺序表2.3单链表2.4线性链表的其他变形2.5单链表的应用：多项式及其运算2.1线性表线性表(LinearList)：由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(a1，a2，…an)()这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例子例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各

2、种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….例4、一副扑克的点数（2，3，4，…，J，Q，K，A）线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结

3、点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1线性表的逻辑结构：线性结构数据的运算是定义在逻辑结构上的。运算的具体实现则是在（物理）存储结构上进行的。线性表只能“顺序存取”数组与线性表的异同：数组id与位置的对应。线性表是线性排列的“对象”。线性表的特点线性表上实现的基本操作1.构造2.随机访问：取第i个位置上的元素。3.插入：线性表的插入运算是指在表的第I(1≦i≦n+1个位置上，插入一个新结点x。4.删除：线性表的删除运算是指将表的第i(1≦i≦n)结点删除。5.查找：寻

4、找具有特定数据的节点。6.归并、复制、计数、排序。线性表的实现顺序表：用顺序方法存储的线性表叫顺序表。顺序存储：用一组连续的存储空间，依次存储线性表的元素。特点：其逻辑结构与物理结构（顺序结构相同。注意:顺序表是顺序存储，随机存取。实现顺序存储一种最好的方式是用数组。[例]顺序表{a0,a1,a2,…,an-1}地址bb+cb+2cb+3cb+icb+(n-1)C元素a0a1a2a3…an-1空闲区位置0123…n-1Loc(a[i])=loc(a[0])+i*c顺序表的抽象数据结构p43顺序表上实现的基

5、本运算1.查找例：在顺序表{12，15，33，45，67，89，57，78}查找57（找到），查找66（找不到）。121533456789577801234567程序实现TempletintSeqlist::Find(type&x)const{Inti=0；while(i<=last&&data[i]!=x)i++;If(i>last)return-1;//没找到Elsereturni;//找到}查找算法的时间复杂度问题规模：表的长度，设它的值为n。算法的时间：主要化费在

6、循环比较语句上。比较结点的次数依赖于（表的长度，被查找元素位置）。最好情况：a0=x；这时，其时间复杂度O（1）；最坏情况：找不到；比较语句将循环执行n次，其时间复杂度O（n）平均复杂度：在长度为n的线性表中第i个位置上找到一个结点，令Efd(n)表示找到结点的期望值（即比较的平均次数），则在第i个位置上找到一个结点的比较次数为i+1。故Efd(n)=∑pi(i+1)假设在表中任何位置(0≦i≦n-1)上查找结点的机会是均等的，则p0=p1=p2=…=pn-1=1/n因此，在等概率插入的情况下，Efd(n

7、)=∑(i+1)/n=(n+1)/2在顺序表上做查找运算，算法的平均时间复杂度为O(n)。2.插入例：在顺序表{12，15，33，45，67，89，57，78}的第三个元素处插入元素44。12153345678957780123456744程序实现TempletintSeqlist::Insert(type&x,inti){If(i<0

8、

9、i>last+1

10、

11、last==MaxSize-1)return0;//procondition校验Else{last++;for(i

12、ntj=last;j>i;j--)data[j]=data[j-1];data[i]=x;//插入return1;插入算法的时间复杂度问题规模：表的长度，设它的值为n。算法的时间：主要化费在循环的结点后移语句上。移动结点的次数（依赖于表的长度，插入位置）。最好情况：i=n；由于循环变量的终值大于初值，结点后移语句将不进行；这是，其时间复杂度O（1）；最坏情况：当i=1时，结点后移语句将循环执行n次，其时间复杂度O（n）；平均复