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