1、1 1第第2章章 线性表及其顺序存储线性表及其顺序存储线性表线性表顺序表顺序表栈栈队列队列2 2线性表是一种常用的数据结构，本章介绍线性表及其线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。细的设计描述。线性表是一个线性结构，它是一个含有线性表是一个线性结构，它是一个含有n0个结点个结点的有限序列，一般地，一个线性表可以表示成一个的有限序列，一般地，一个线性表可以表示成一个线性序列：线性序列：k1,k2,kn，其中，其中k1是开始结点，是开始结点，kn是终是终端结点。端结点。3 3例例1、2
2、6个英文字母组成的字母表个英文字母组成的字母表 （A，B，C、Z）例例2、某校从、某校从1978年到年到1983年各种型号的计年各种型号的计算机拥有量的变化情况。算机拥有量的变化情况。（6，17，28，50，92，188）4 4姓 名学 号性 别年 龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 贫血.例例3 学生健康情况登记表如下：学生健康情况登记表如下：5 5例例4、一副扑克的点数、一副扑克的点数 （2，3，4，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征
3、是：在非空的线性表，有且仅有一个开始结点在非空的线性表，有且仅有一个开始结点a1，它，它没有直接前趋，而仅有一个直接后继没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点有且仅有一个终端结点an，它没有直接后继，而，它没有直接后继，而仅有一个直接前趋仅有一个直接前趋an-1；其余的内部结点其余的内部结点ai(2in-1)都有且仅有一个直都有且仅有一个直接前趋接前趋ai-1和一个直接后继和一个直接后继ai+1。线性表是一种典型的线性结构。线性表是一种典型的线性结构。6 6线性表采用顺序存储的方式存储就称之为顺序表。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在
4、计算机内存中一组顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。地址连续的存储单元中。顺序表的存储结构如下图所示：顺序表的存储结构如下图所示：len len len lenk1k2k ik n7 7一个一维数组，下标的范围是到，每一个一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素编址，设存储数组元素的第一个字节的地址的第一个字节的地址是是 98，则，则的第一个字节的地址是的第一个字节的地址是 113例例1因此：因此：LOC(M3)=98+5 3=113解：地址计算通式为：解：地址计算通式为
5、：LOC(ai)=LOC(a0)+L*i如顺序表的每个结点占用如顺序表的每个结点占用len个内存单元个内存单元，用，用location(ki)表示顺序表中第表示顺序表中第i个结点个结点ki所占内存空间的第所占内存空间的第1个单个单元的地址。则有如下的关系元的地址。则有如下的关系location(ki+1)=location(ki)+lenlocation(ki)=location(k1)+(i-1)len8 8存储结构要体现数据的逻辑结构存储结构要体现数据的逻辑结构顺序表的存储结构中，内存中物理地址相邻的结点一顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。定具有顺序表
6、中的逻辑关系。9 9n 用用C语言中的数组存储顺序表。语言中的数组存储顺序表。n C语言中数组的下标是从语言中数组的下标是从0开始的，即数组中下标为开始的，即数组中下标为0的元素对应的是顺序表中的第的元素对应的是顺序表中的第1个结点，数组中下标个结点，数组中下标为为i的元素对应的是顺序表中的第的元素对应的是顺序表中的第i+1个结点。个结点。n 为了方便，将顺序表中各结点的序号改为和对应数为了方便，将顺序表中各结点的序号改为和对应数组元素的下标序号一致，即将顺序表中各结点的序号组元素的下标序号一致，即将顺序表中各结点的序号从从0开始编号。这样，一个长度为开始编号。这样，一个长度为n的顺序表可以表
7、示的顺序表可以表示为为 k0,k1,k2,kn-11010顺序表的存储结构的顺序表的存储结构的C语言描述如下：语言描述如下：/*顺序表的头文件，文件名顺序表的头文件，文件名sequlist.h*/#define MAXSIZE 10 typedef int datatype;typedef struct datatype aMAXSIZE;int size;sequence_list;1111顺序表的几个基本操作的具体实现顺序表的几个基本操作的具体实现：/函数功能函数功能:顺序表的初始化顺序表的初始化置空表置空表 /函数参数函数参数:指向指向sequence_list型变量的指针变量型变量的指
8、针变量slt /函数返回值函数返回值:空空 /文件名文件名:sequlist.c,函数名函数名:init()/void init(sequence_list slt)slt-size=0;算法算法2.1顺序表的初始化顺序表的初始化-置空表置空表1212/函数功能函数功能:在顺序表后部进行插入操作在顺序表后部进行插入操作 /函数参数函数参数:指向指向sequence_list型变量的指针变量型变量的指针变量slt /datatype类型的变量类型的变量x /函数返回值函数返回值:空空 /文件名文件名:sequlist.c,函数名函数名:append()/void append(sequence_
9、list slt,datatype x)if(slt-size=MAXSIZE)printf(顺序表是满的顺序表是满的!);exit(1);slt-aslt-size=x;slt-size=slt-size+1;算法算法2.2 在顺序表后部进行插入操作在顺序表后部进行插入操作1313打印顺序表的各结点值打印顺序表的各结点值/函数功能函数功能:打印顺序表的各结点值打印顺序表的各结点值 /函数参数函数参数:sequence_list型变量型变量slt /函数返回值函数返回值:空空 /文件名文件名:sequlist.c,函数名函数名:display()/void display(sequence_l
10、ist slt)int i;if(!slt.size)printf(n顺序表是空的顺序表是空的!);else for(i=0;islt.size;i+)printf(%5d,slt.ai);算法算法2.3 打印顺序表的各结点值打印顺序表的各结点值1414判断顺序表是否为空判断顺序表是否为空 /函数功能函数功能:判断顺序表是否为空判断顺序表是否为空 /函数参数函数参数:sequence_list型变量型变量slt /函数返回值函数返回值:int类型。类型。1表示空表示空,0表示非空表示非空 /文件名文件名:sequlist.c,函数名函数名:empty()/int empty(sequence_
11、list slt)return(slt.size=0?1:0);算法算法2.4 判断顺序表是否为空判断顺序表是否为空1515查找顺序表中值为查找顺序表中值为x的结点位置的结点位置/函数功能函数功能:查找顺序表中值为查找顺序表中值为x的结点位置的结点位置 /函数参数函数参数:sequence_list型变量型变量slt,datatype型变量型变量x /函数返回值函数返回值:int类型。返回类型。返回x的位置值的位置值,-1表示没找到表示没找到 /文件名文件名:sequlist.c,函数名函数名:find()/int find(sequence_list slt,datatype x)int i
12、=0;while(islt.size&slt.ai!=x)i+;return(islt.size?i:1);算法算法2.5 查找顺序表中值为查找顺序表中值为x的结点位置的结点位置1616 取得顺序表中第取得顺序表中第i个结点的值个结点的值/函数功能函数功能:取得顺序表中第取得顺序表中第i个结点的值个结点的值 /函数参数函数参数:sequence_list型变量型变量slt,int型变量型变量i /函数返回值函数返回值:datatype类型。返回第类型。返回第i个结点的值个结点的值 /文件名文件名:sequlist.c,函数名函数名:get()/datatype get(sequence_lis
13、t slt,int i)if(i=slt.size)printf(n指定位置的结点不存在指定位置的结点不存在!);exit(1);else return slt.ai;算法算法2.6 取得顺序表中第取得顺序表中第i个结点的值个结点的值1717顺序表的插入运算是将一个值为顺序表的插入运算是将一个值为x的结点插入到顺的结点插入到顺序表的第序表的第p个位置个位置0pn，即将，即将x插入到插入到kp-1和和kp之间，之间，一般地可表示为：一般地可表示为：插入前：插入前：k0,k1,kp-1,kp,kn-1插入后：插入后：k0,k1,kp-1,x kp,kn-1 插入过程的图示见下图：插入过程的图示见下
14、图：k ik0k1k i-1k n-1k0k1k i-1k n-1xk i后移开始位置后移开始位置后移结束位置后移结束位置插入前插入前插入后插入后p+1 nppp-1p-11818/函数功能函数功能:在顺序表的在顺序表的position位置插入值为位置插入值为x的结点的结点 /函数参数函数参数:指向指向sequence_list型变量的指针变量型变量的指针变量slt /datatype型变量型变量x,int型变量型变量 position /函数返回值函数返回值:空空 文件名文件名:sequlist.c,函数名函数名:insert()/void insert(sequence_list slt,
15、datatype x,int position)int i;if(slt-size=MAXSIZE)printf(n顺序表是满的顺序表是满的!没法插入没法插入!);exit(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的结点的结点1919算法算法2.7中，所花费的时间主要是元素后移操作，对于中，所花费的
16、时间主要是元素后移操作，对于在第在第i个位置上插入一个新的元素，需要移动（个位置上插入一个新的元素，需要移动（n-i）个）个元素，设在第元素，设在第i个位置上插入一个元素的概率为个位置上插入一个元素的概率为pi，且在，且在任 意 一 个 位 置 上 插 入 元 素 的 概 率 相 等，即任 意 一 个 位 置 上 插 入 元 素 的 概 率 相 等，即p0=p1=p2=pn=1/(n+1)，则在一个长度为，则在一个长度为n的顺序表的顺序表中插入一个元素所需的平均移动次数为：中插入一个元素所需的平均移动次数为：22)1(11)(11)(00nnnninninpninii即在长度为即在长度为n的顺
17、序表中插入一个元素平均需要移动的顺序表中插入一个元素平均需要移动表中的一半元素。该算法的时间复杂度为表中的一半元素。该算法的时间复杂度为O（n）。）。2020 顺序表的删除操作是指删除顺序表中的第顺序表的删除操作是指删除顺序表中的第i个结点，个结点，0in-1，一般地可表示为：，一般地可表示为：删除前：删除前：k0,k1,ki-1,ki,ki+1,kn-1 删除后：删除后：k0,k1,ki-1,ki+1,kn-1 删除过程的图示见下图删除过程的图示见下图：k ik0k1k i-1k n-1k0k1k i-1k n-1k i+1前移结束位置前移结束位置前移开始位置前移开始位置删除前删除前删除后删
18、除后k i+12121删除操作的具体实现见算法删除操作的具体实现见算法2.8/函数功能函数功能:删除顺序表中第删除顺序表中第position位置的结点位置的结点 /函数参数函数参数:指向指向sequence_list型变量的指针变量型变量的指针变量slt /int型变量型变量 position /函数返回值函数返回值:空空 文件名文件名:sequlist.c,函数名函数名:dele()/void dele(sequence_list slt,int position)int i;if(slt-size=0)printf(n顺序表是空的顺序表是空的!);exit(1);if(position=s
19、lt-size)printf(n指定的删除位置不存在指定的删除位置不存在!);exit(1);for(i=position;isize-1;i+)slt-ai=slt-ai+1;slt-size-;算法算法2.8 删除顺序表中第删除顺序表中第position位置的结点位置的结点 2222要删除顺序表中的第要删除顺序表中的第i个结点，则需要称动（个结点，则需要称动（n-i-1）个元素，设删除表中第个元素，设删除表中第i个结点的概率为个结点的概率为qi，且在表中每，且在表中每一个位置删除的概率相等，即：一个位置删除的概率相等，即：q0=q1=qn-1=1/n则在一个长度为则在一个长度为n的顺序表中
20、删除一个结点的平均移动的顺序表中删除一个结点的平均移动次数为：次数为：212)1(1)1(1)1(1010nnnninninqninii在一个长为在一个长为n的顺序表中删除一个元素平均需要移动表的顺序表中删除一个元素平均需要移动表中大约一半的元素。该算法的时间复杂度为中大约一半的元素。该算法的时间复杂度为O（n）2323（1）void verge(sequence_list l)将顺序表将顺序表L就地转置，即借助于就地转置，即借助于O（1）的辅助空间。）的辅助空间。（2）void sprit(sequence_lsit*l1,sequence_list*l2,sequence_list*l3)
21、略略 将有序顺序表将有序顺序表L1分裂成两个线性表分裂成两个线性表L2与与L3，L2由表中所奇由表中所奇数组成，数组成，L3由所有偶数组成。由所有偶数组成。顺序表上的一些其它常见算法顺序表上的一些其它常见算法（3）void merge(sequence_lsit*l1,sequence_list*l2,sequence_list*l3)将有序顺序表将有序顺序表L1与与L2合并成有序顺序表合并成有序顺序表L3。2424作业作业nP332.4 void reverse(Sequence_list*slt)n2.5 void insert_order(Sequence_list*slt,datatype x)n下次上课课前交下次上课课前交
