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

第2章 线性表及其顺序存储 例1 一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是 98 ，则Ｍ[３]的第一个字节的地址是 作业 P33\2.4 void reverse(Sequence_list *slt) 2.5 void insert_order(Sequence_list *slt, datatype x) 下次上课课前交 * 线性表 顺序表 栈 队列 线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。 2.1线性表 线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。 例1、26个英文字母组成的字母表 （A，B，C、…、Z） 例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188） ……. ……. ……. …….. …….. 贫血 17 男 790634 张立立 健康 21 男 790633 刘建平 一般 20 女 790632 陈 红 健康 18 男 790631 王小林 健康情况 年 龄 性 别 学 号 姓 名 例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顺序表 线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。 2.2顺序表 顺序表的存储结构如下图所示： 存储地址 location(k1) location(k1)+(i-1)l en 结点序号 1 2 i n len len …… len …… len k1 k2 k i k n 内存状况 113 因此：LOC( M[3] ) = 98 + 5 ×3 =113 解：地址计算通式为： LOC(ai) = LOC(a0) + L *i 如顺序表的每个结点占用len个内存单元，用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系 location (ki+1) = location (ki) +len location (ki) = location(k1) + (i-1)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 typedef int datatype; typedef struct{ datatype a[MAXSIZE]; int size; }sequence_list; 表长 顺序表的几个基本操作的具体实现 ： /?????????????????????????????????????????????????/ /? 函数功能:顺序表的初始化—置空表 ?/ /? 函数参数:指向sequence_list型变量的指针变量slt ?/ /?