第2章-线性表及其顺序存储.

数据结构高等学校精品课程（省级）国家十二五规划教材高等学校精品课程（省级）国家十二五规划教材第2章线性表及其顺序存储揭安全江西师范大学计算机信息工程学院线性表顺序表栈队列线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。2.1线性表线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17贫血……..……..…….…….…….例3学生健康情况登记表如下：例4、一副扑克的点数（2，3，4，…，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。2.2.1顺序表线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。如顺序表的每个结点占用len个内存单元，用location(ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系location(ki+1)=location(ki)+lenlocation(ki)=location(k1)+(i-1)len2.2顺序表顺序表的存储结构如下图所示：存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。存储地址location(k1)location(k1)+(i-1)len结点序号12inlenlen……len……lenk1k2kikn内存状况2.2.2顺序表的实现用C语言中的数组存储顺序表。C语言中数组的下标是从0开始的，即数组中下标为0的元素对应的是顺序表中的第1个结点，数组中下标为i的元素对应的是顺序表中的第i+1个结点。为了方便，将顺序表中各结点的序号改为和对应数组元素的下标序号一致，即将顺序表中各结点的序号从0开始编号。这样，一个长度为n的顺序表可以表示为{k0,k1,k2,…,kn-1}顺序表的存储结构的C语言描述如下：/*顺序表的头文件，文件名sequlist.h*/#defineMAXSIZE100typedefintdatatype;typedefstruct{datatypea[MAXSIZE];intsize;}sequence_list;表长顺序表的几个基本操作的具体实现：///函数功能:顺序表的初始化—置空表//函数参数:指向sequence_list型变量的指针变量slt//函数返回值:空//文件名:sequlist.c,函数名:init()///voidinit(sequence_listslt){slt-size=0;}算法2.1顺序表的初始化---置空表///函数功能:在顺序表后部进行插入操作//函数参数:指向sequence_list型变量的指针变量slt//datatype类型的变量x//函数返回值:空//文件名:sequlist.c,函数名:append()///voidappend(sequence_listslt,datatypex){if(slt-size==MAXSIZE){printf(顺序表是满的!);exit(1);}slt-a[slt-size]=x;slt-size=slt-size+1;}算法2.2在顺序表后部进行插入操作打印顺序表的各结点值///函数功能:打印顺序表的各结点值//函数参数:sequence_list型变量slt//函数返回值:空//文件名:sequlist.c,函数名:display()///voiddisplay(sequence_listslt){inti;if(!slt.size)printf(\n顺序表是空的!);elsefor(i=0;islt.size;i++)printf(%5d,slt.a[i]);}算法2.3打印顺序表的各结点值判断顺序表是否为空///函数功能:判断顺序表是否为空//函数参数:sequence_list型变量slt//函数返回值:int类型。1表示空,0表示非空//文件名:sequlist.c,函数名:empty()///intempty(sequence_listslt){return(slt.size==0?1:0);}算法2.4判断顺序表是否为空查找顺序表中值为x的结点位置///函数功能:查找顺序表中值为x的结点位置//函数参数:sequence_list型变量slt,datatype型变量x//函数返回值:int类型。返回x的位置值,-1表示没找到//文件名:sequlist.c,函数名:find()///intfind(sequence_listslt,datatypex){inti=0;while(islt.size&&slt.a[i]!=x)i++;return(islt.size?i:−1);}算法2.5查找顺序表中值为x的结点位置取得顺序表中第i个结点的值///函数功能:取得顺序表中第i个结点的值//函数参数:sequence_list型变量slt,int型变量i//函数返回值:datatype类型。返回第i个结点的值//文件名:sequlist.c,函数名:get()///datatypeget(sequence_listslt,inti){if(i0||i=slt.size){printf(\n指定位置的结点不存在!);exit(1);}elsereturnslt.a[i];}算法2.6取得顺序表中第i个结点的值顺序表的插入运算是将一个值为x的结点插入到顺序表的第i个位置0≤i≤n，即将x插入到ki-1和ki之间，如果i=n，则表示插入到表的最后，一般地可表示为：插入前：{k0,k1,…,ki-1,ki,…,kn-1}插入后：{k0,k1,…,ki-1,x,ki,…,kn-1}插入过程的图示见下图：kik0k1ki-1kn-1k0k1ki-1kn-1xki后移开始位置后移结束位置插入前插入后///函数功能:在顺序表的position位置插入值为x的结点//函数参数:指向sequence_list型变量的指针变量slt//datatype型变量x,int型变量position//函数返回值:空文件名:sequlist.c,函数名:insert()///voidinsert(sequence_listslt,datatypex,intposition){inti;if(slt-size==MAXSIZE){printf(\n顺序表是满的!没法插入!);exit(1);}if(position0||positionslt-size){printf(\n指定的插入位置不存在!);exit(1);}for(i=slt-size;iposition;i--)slt-a[i]=slt-a[i−1];slt-a[position]=x;slt-size++;}算法2.7在顺序表的position位置插入值为x的结点算法2.7中，所花费的时间主要是元素后移操作，对于在第i个位置上插入一个新的元素，需要移动（n-i）个元素，设在第i个位置上插入一个元素的概率为pi，且在任意一个位置上插入元素的概率相等，即p0=p1=p2=…=pn=1/(n+1)，则在一个长度为n的顺序表中插入一个元素所需的平均移动次数为：22)1(11)(11)(00nnnninninpninii即在长度为n的顺序表中插入一个元素平均需要移动表中的一半元素。该算法的时间复杂度为O（n）。顺序表的删除操作是指删除顺序表中的第i个结点，0≤i≤n-1，一般地可表示为：删除前：{k0,k1,…,ki-1,ki,ki+1,,…,kn-1}删除后：{k0,k1,…,ki-1,ki+1,…,kn-1}删除过程的图示见下图：kik0k1ki-1kn-1k0k1ki-1kn-1ki+1前移结束位置前移开始位置删除前删除后ki+1删除操作的具体实现见算法2.8///函数功能:删除顺序表中第position位置的结点//函数参数:指向sequence_list型变量的指针变量slt//int型变量position//函数返回值:空文件名:sequlist.c,函数名:dele()///voiddele(sequence_listslt,intposition){inti;if(slt-size==0){printf(\n顺序表是空的!);exit(1);}if(position0||position=slt-size){printf(\n指定的删除位置不存在!);exit(1);}for(i=position;islt-size-1;i++)slt-a[i]=slt-a[i+1];slt-size--;}算法2.8删除顺序表中第position位置的结点要删除顺序表中的第i个结点，则需要称动（n-i-1）个元素，设删除表中第i个结点的概率为qi，且在表中每一个位置删除的概率相等，即：q0=q