《-线性表及其顺序存储》由会员分享，可在线阅读，更多相关《-线性表及其顺序存储（101页珍藏版）》请在金锄头文库上搜索。
1、数据结构,李云清 杨庆红 揭安全,人民邮电出版社,高等学校精品课程（省级） 国家十二五规划教材,高等学校精品课程（省级） 国家十二五规划教材,第2章 线性表及其顺序存储,揭安全, 江西师范大学计算机信息工程学院,线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。,2.1线性表,线性表是一个线性结构，它是一个含有n0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,kn
2、，其中k1是开始结点，kn是终端结点。,例1、26个英文字母组成的字母表（A，B，C、Z）,例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）,例3 学生健康情况登记表如下：,例4、一副扑克的点数（2，3，4，J，Q，K，A） 从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1； 其余的内部结点ai(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。,2.2
3、.1顺序表,线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。,如顺序表的每个结点占用len个内存单元，用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系location (ki+1) = location (ki) +lenlocation (ki) = location(k1) + (i-1)len,2.2顺序表,顺序表的存储结构如下图所示：,存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。,存储地址 location(k1)
4、 location(k1)+(i-1)l en,结点序号 1 2 i n,len len len len,2.2.2顺序表的实现,用C语言中的数组存储顺序表。C语言中数组的下标是从0开始的，即数组中下标为0的元素对应的是顺序表中的第1个结点，数组中下标为i的元素对应的是顺序表中的第i+1个结点。为了方便，将顺序表中各结点的序号改为和对应数组元素的下标序号一致，即将顺序表中各结点的序号从0开始编号。这样，一个长度为n的顺序表可以表示为 k0, k1, k2, , kn-1,顺序表的存储结构的C语言描述如下： /*顺序表的头文件，文件名sequlist.h */#define MAXSIZE 10
5、0typedef int datatype;typedef structdatatype aMAXSIZE;int size;sequence_list;,表长,顺序表的几个基本操作的具体实现 ：,/ / 函数功能:顺序表的初始化置空表 / / 函数参数:指向sequence_list型变量的指针变量slt / / 函数返回值:空 / / 文件名:sequlist.c, 函数名:init() / /void init(sequence_list slt)slt-size=0; 算法2.1顺序表的初始化-置空表,/ / 函数功能:在顺序表后部进行插入操作 / / 函数参数:指向sequence_
6、list型变量的指针变量slt / / datatype类型的变量x / / 函数返回值:空 / / 文件名:sequlist.c, 函数名:append() / /void append(sequence_list slt,datatype x)if(slt-size=MAXSIZE)printf(“顺序表是满的!“);exit(1);slt-aslt-size=x;slt-size=slt-size+1; 算法2.2 在顺序表后部进行插入操作,打印顺序表的各结点值,/ / 函数功能:打印顺序表的各结点值 / / 函数参数:sequence_list型变量slt / / 函数返回值:空 /
7、/ 文件名:sequlist.c, 函数名:display() / /void display(sequence_list slt)int i;if(!slt.size) printf(“n顺序表是空的!“);elsefor(i=0;islt.size;i+) printf(“%5d“,slt.ai); 算法2.3 打印顺序表的各结点值,判断顺序表是否为空,/ / 函数功能:判断顺序表是否为空 / / 函数参数:sequence_list型变量slt / / 函数返回值:int类型。1表示空,0表示非空 / / 文件名:sequlist.c,函数名:empty() / /int empty(s
8、equence_list slt)return (slt.size=0 ? 1:0); 算法2.4 判断顺序表是否为空,查找顺序表中值为x的结点位置,/ / 函数功能:查找顺序表中值为x的结点位置 / / 函数参数:sequence_list型变量slt,datatype型变量x / / 函数返回值:int类型。返回x的位置值,-1表示没找到 / / 文件名:sequlist.c,函数名:find() / /int find(sequence_list slt,datatype x)int i=0;while( isize=MAXSIZE)printf(“n顺序表是满的!没法插入!“);exi
9、t(1);if(positionslt-size)printf(“n指定的插入位置不存在!“);exit(1);for(i=slt-size;iposition;i-) slt-ai=slt-ai1;slt-aposition=x; slt-size+; 算法2.7 在顺序表的position位置插入值为x的结点,算法2.7中，所花费的时间主要是元素后移操作，对于在第i个位置上插入一个新的元素，需要移动（n-i）个元素，设在第i个位置上插入一个元素的概率为pi，且在任意一个位置上插入元素的概率相等，即p0=p1=p2=pn=1/(n+1)，则在一个长度为n的顺序表中插入一个元素所需的平均移动次数为：,即在长度为n的顺序表中插入一个元素平均需要移动表中的一半元素。该算法的时间复杂度为O（n）。,
