第2章 线性表

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

1、第二章线性表2.1线性表的概念及运算2.1.1线性表的逻辑结构2.1.2线性表的运算2.2线性表的顺序存储2.2.1顺序表2.2.2顺序表的基本运算2.3线性表的链式存储2.3.1单链表2.3.2单链表的基本运算2.3.3循环链表2.3.4双向链表2.3.5静态链表（基本概念）2.4顺序表和链表的比较2.1线性表的概念及运算线性表(LinearList)：由n(n≧)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(a1，a2，…an)

2、例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（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；有

3、且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。a1a2a3a4a5a6利用线性表的基本操作清除表L中多余的重复节点PURGE(Linear_list*L){inti=1,j,x,y;while(i

4、x==y)DELETE(L,j);elsej++;}i++;}}2.2线性表的顺序存储结构2.2.1线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用C个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+c线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*c3

5、52749186054778341020123456789cccccccccca+i*ca由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度，所以我们用结构类型来定义顺序表类型。#defineMaxSize1024typedefintDataType;typedefstruct{DataTypedata[MaxSize];intlast;}Sequenlist;2.2.2顺序表上的基本运算C语言中的数组下标从“0”开始，因此，

6、若L是Sequenlist类型的顺序表变量，则表中第i个元素是l.data[i-1]。若L是Sqlist类型的顺序表指针变量，则表中第i个元素是(*l).data[i-1]或l->data[i-1]。以下主要讨论顺序表的插入和删除两种运算。1、插入线性表的插入运算是指在表的第i(0≦i≦n)个位置上，插入一个新结点x，使长度为n的线性表：(a0，…ai-1，ai，…，an-1),变成长度为n+1的线性表(a0，…ai-1，x，ai，…，an-1)intInsert(sequenlist*l,DataTypex,inti){//顺

7、序表从0开始,i的位置为i-1intj;if(i<0

8、

9、i>l->last+1){printf("Positionerror");returnNULL;}if(l->last>=MaxSize-1){printf("overflow");returnNULL;}for(j=l->last;j>=i-1;j--)l->data[j+1]=l->data[j];l->data[i-1]=x;l->last++;return1;}分析算法的复杂度。这里的问题规模是，设表的长度为n。该算法的时间主要花费在结点后移语句的循环上，该语句的执

10、行次数（即是移动结点的次数）。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。当i=n时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当i=0时，结点后移语句将循环执行n次，需移动表中所有结点，这