数据结构 C语言版 第2版 李云清 杨庆红 揭安全 第02章_线性表（I）

《数据结构 C语言版 第2版 李云清 杨庆红 揭安全 第02章_线性表（I）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构李云清杨庆红揭安全高等学校精品课程人民邮电出版社（第2版）数据结构揭安全江西省高等学校精品课程E_mail:jieanquan@163.com江西师范大学计算机信息工程学院第2章线性表及其顺序存储线性表顺序表栈队列线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。2.1线性表线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其

2、它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：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、一副

3、扑克的点数（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个

4、内存单元，用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……lenk1k

5、2kikn内存状况2.2.2顺序表的实现用C语言中的数组存储顺序表。C语言中数组的下标是从0开始的，即数组中下标为0的元素对应的是顺序表中的第1个结点，数组中下标为i的元素对应的是顺序表中的第i+1个结点。为了方便，将顺序表中各结点的序号改为和对应数组元素的下标序号一致，即将顺序表中各结点的序号从0开始编号。这样，一个长度为n的顺序表可以表示为{k0,k1,k2,…,kn-1}顺序表的存储结构的C语言描述如下：/*顺序表的头文件，文件名sequlist.h*/#defineMAXSIZE100typed

6、efintdatatype;typedefstruct{datatypea[MAXSIZE];intsize;}sequence_list;表长顺序表的几个基本操作的具体实现：///函数功能:顺序表的初始化—置空表//函数参数:指向sequence_list型变量的指针变量slt//函数返回值:空//文件名:sequlist.c,函数名:init()//

7、/voidinit(sequence_listslt){slt->size=0;}算法2.1顺序表的初始化---置空表///函数功能:在顺序表后部进行插入操作//函数参数:指向sequence_list型变量的指针变量slt//datatype类型的变量x//函数返回值:空//文件名:sequlist.c,函数名:append(

8、)///voidappend(sequence_listslt,datatypex){if(slt->size==MAXSIZE){printf("顺序表是满的!");exit(1);}slt->a[slt->size]=x;slt->size=slt->size+1;}算法2.2在顺序表后部进行插入操作打印顺序表的各结点值/