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