第二章 顺序表.ppt

《第二章 顺序表.ppt》由会员分享，可在线阅读，更多相关《第二章 顺序表.ppt（28页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构第2章 线性表 栈和队列 串第3章 数组和广义表 线性结构（逻辑、存储和运算）线性结构特点：在数据元素的非空有限集 (a1,a2,an)中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中每个数据元素均只有一个前驱除最后一个外，集合中每个元素均只有一个后继2第二章第二章 线性表线性表2.1 2.1 线性表定义及基本操作线性表定义及基本操作2.2 2.2 线性表的顺序存储线性表的顺序存储2.3 2.3 线性表的链式存储线性表的链式存储 2 2.3.1.3.1 单链表单链表 2.3.22.3.2 双

2、向链表双向链表 2.3.32.3.3 循环链表循环链表2.4 2.4 栈栈 2.4.12.4.1栈的定义及其基本操作栈的定义及其基本操作 2.4.22.4.2顺序栈的表示和实现顺序栈的表示和实现 *2.4.32.4.3链栈的表示和实现链栈的表示和实现32.52.5 队列队列 2.5.12.5.1队列的定义及其基本操作队列的定义及其基本操作 2.5.22.5.2顺序队列的表示和实现顺序队列的表示和实现 *2.5.32.5.3链队列的表示和实现链队列的表示和实现2.62.6 串串 2.6.12.6.1串的定义及其基本操作串的定义及其基本操作 2.6.22.6.2顺序串的表示和实现顺序串的表示和实现

3、 *2.6.32.6.3链串的表示和实现链串的表示和实现 *2.6.42.6.4串的模式匹配串的模式匹配4L=（a1,a2,ai-1，ai,ai1，,an）n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标下标i，是元素是元素ai的序号的序号，表示，表示ai在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点2.1.1线性表的基本概念线性表的基本概念定义：线性表是定义：线性表是n(n0)个数据元素的有限序列个数据元素的有限序列,可记作：可记作：2.1 线性表的定义及基本操作52、线性表的结构是通过数据元素

4、之间的相邻关系来体现的。、线性表的结构是通过数据元素之间的相邻关系来体现的。说明：说明：1 1、数据元素可以是一个数，一个符号或一个记录等，但、数据元素可以是一个数，一个符号或一个记录等，但同同一线性表中的元素必须属于同一种数据对象一线性表中的元素必须属于同一种数据对象。例例1 1、一年的月份号（、一年的月份号（1 1，2 2，3 3，4 4，5 5，1212）例例2 2、英文字母表（、英文字母表（a,a,b,b,c,c,，z z ）例例3 3、某单位的电话号码簿、某单位的电话号码簿 姓名姓名 电话号码电话号码 蔡颖蔡颖 6321444463214444 陈红陈红 63217777632177

5、77 刘建平刘建平 6321666663216666 王小林王小林 6321888863218888 张力张力 6321555563215555 .由于上述关系是线性的-线性结构。6(1)初始化操作 initlist(L)建立一个空表。(2)求表长操作 getlen(L)返回线性表L的长度。(3)元素定位操作locate(L,x)返回元素x在线性表L中第一次出现的位置，存在，返回其位序，否则，返回-1(4)取元素操作 getelem(L,i)返回线性表L的第i个元素的值。(5)插入操作 insert(L,x,i)在线性表L 的第i个位置上插入一个值为x的元素。i的合法取值范围是：1in1(6)

6、删除操作 delete(L,i)删除线性表L的第i个元素，i的合法到值范围是：1in1(7)输出操作 print(L)(8)按先后顺序输出线性表L的所有元素值。2.1.2线性表的基本操作7说明:1 上面列出的操作，只是线性表的一些常用的基本操作；2 不同的应用，基本操作可能是不同的；3 线性表的复杂操作可通过基本操作实现；82.22.2顺序表顺序表 -线性表的顺序存储结构线性表的顺序存储结构 2.2.12.2.1顺序表的定义顺序表的定义 1 1.定义：用一组地址连续的存储单元将逻辑上相邻的定义：用一组地址连续的存储单元将逻辑上相邻的元素存放在物理地址也相邻的存储单元。元素存放在物理地址也相邻的

7、存储单元。2.2.元素地址计算方法：元素地址计算方法：LOC(ai+1)=LOC(ai)+k (2in)LOC(ai)=LOC(a1)+(i-1)*k (1in)内存空间a1a2aianLoc(a1)+k逻辑地址12in空闲Loc(a1)Loc(a1)+(i-1)kLoc(a1)+(n-1)k图图2.1 顺序表顺序表其中：其中：k 一个元素占用的存储单元个数一个元素占用的存储单元个数 LOC(ai)顺序表顺序表第第i个元素的地址个元素的地址 LOC(a1)顺序表的基址顺序表的基址9特点：特点：实现逻辑上相邻实现逻辑上相邻物理地址相邻物理地址相邻实现随机存取实现随机存取实现：实现：可用可用C C

8、语言的一维数组实现语言的一维数组实现,这里采用这里采用动态分配的一维数组动态分配的一维数组，在初始化时先，在初始化时先用函数用函数mallocmalloc（）（）为顺序表分配一个基本容量，为顺序表分配一个基本容量，在操作过程中，若顺序表的空间不足，再用函数在操作过程中，若顺序表的空间不足，再用函数reallocrealloc（）（）增加空间。增加空间。10typedef int ElemType;/*在实际问题中，根据需要定义所需的数据类型*/#define INITSIZE 100/*顺序表存储空间的初始分配量*/typedef struct ElemType *data;/*存储空间基地址

9、*/int length;/*顺序表当前长度,即已存入的元素个数*/int listsize;/*当前存储空间容量*/sqlist;动态申请和释放内存ElemType*data=(ElemType*)malloc(INITSIZE*sizeof(ElemType);free(data);顺序表的类型定义顺序表的类型定义：元素存放在data0到datalength-1中。112.2.2基本操作在顺序表上的实现基本操作在顺序表上的实现(1)初始化操作：初始化操作：构造一个空的顺序表构造一个空的顺序表L L void initlist(sqlist*L)/*/*构造一个空的顺序表构造一个空的顺序表L

10、*/L*/L-data=(ElemType*)malloc(INITSIZE*sizeof(ElemType);if(!L-data)printf(“OVERFLOW!n”);exit(1);/*/*存储分配失败存储分配失败*/L-length=0;/*/*长度为长度为0*/0*/L-listsize=INITSIZE;/*/*初始存储容量初始存储容量*/算法性能分析:时间性能 O(1)空间性能 O(1)12(2)求表长操作求表长操作 统计顺序表统计顺序表L L数据元素的个数数据元素的个数int getlen(sqlist L)/*统计顺序表统计顺序表L数据元素的个数数据元素的个数*/retu

11、rn(L.length);算法性能分析:时间性能 O(1)空间性能 O(1)13(3)取元素操作取元素操作取出顺序表取出顺序表L L的的第第i i个个数据元素的值数据元素的值,将值通过将值通过参数参数e e带回，成功返回带回，成功返回1,1,失败返回失败返回0.0.注意注意i i的合法取值范围的合法取值范围:1:1 i lengthint getelem(sqlist L,int i,ElemType*e)/*取出顺序表取出顺序表L的第的第i个数据元素的值个数据元素的值*/if(i=1&i=L.length)*e=L.datai-1;return 1;else return 0;算法性能分析:

12、时间性能 O(1)空间性能 O(1)14算法性能分析:时间性能 查找成功:平均时间复杂度查找失败:空间性能 O(1)(4)元素定位操作元素定位操作int locate(sqlist L,ElemType x)/*从线性表中查找具有给定值从线性表中查找具有给定值x x的第一个元素的第一个元素 若找到，则返回其在若找到，则返回其在L L中的位序，否则返回中的位序，否则返回0 0。*/int i=0;/*从前向后扫描顺序表从前向后扫描顺序表,没找到没找到i值加值加1*/while(iL.length&L.datai!=x)i+;if(i=L.length)/*没找到返回没找到返回0*/return

13、0;else return i+1;/*找到返回位序找到返回位序*/ni=11_nT(n)=pi*ti=i=O(n)n+1_2ni=1T(n)=n=O(n)15(5)插入操作插入操作在线性表中指定位置在线性表中指定位置i i前插入一个元素前插入一个元素x,x,成功返回成功返回1 1，失败，失败返回返回0 0。插入元素时，线性表的逻辑结构由插入元素时，线性表的逻辑结构由(a1,ai-1,ai,an)改变为改变为(a1,ai-1,x,ai,an)算法思想算法思想：1 1）检查）检查i i值是否超出所允许的范围（值是否超出所允许的范围（1in+1），），若若超出，则进行超出，则进行“超出范围超出范围

14、”错误处理；错误处理；2)2)存储空间不足，增加存储空间存储空间不足，增加存储空间3 3）将线性表的第）将线性表的第i i个元素和它后面的所有元素均向个元素和它后面的所有元素均向后移动一个位置；后移动一个位置；4 4）将新元素）将新元素x x写入到空出的第写入到空出的第i i个位置上；个位置上；5 5）使线性表的长度增）使线性表的长度增1 1。并且表的长度增加并且表的长度增加116内存内存a1a2aiai+1an01i-1数组下标数组下标n-1in12i元素序号元素序号i+1nn+1内存内存a1a2aiai+1an01i-1数组下标数组下标n-1in12i元素序号元素序号i+1nn+1an-1

15、x图图2.2顺序表插入操作顺序表插入操作插入前插入前插入后插入后17int insert(sqlist*L,int i,ElemType x)int j;/*判断位置合法性判断位置合法性*/if(iL-length+1)return 0;/*存储空间不足，增加存储空间存储空间不足，增加存储空间*/if(L-length=L-listsize)L-data=(ElemType*)realloc(L-data,(L-listsize+1)*sizeof(ElemType);if(!L-data)printf(“OVERFLOWER!n”);return 0;L-listsize+;/*将将序号序号

16、i的结点及之后的结点后移一位的结点及之后的结点后移一位*/for(j=L-length-1;j=i-1;j-)L-dataj+1=L-dataj;/*在序号在序号i处放入处放入x*/L-datai-1=x;/*表长加表长加1*/L-length+;return 1;18顺序表插入操作时间性能分析：顺序表插入操作时间性能分析：设设Pi是在第是在第i个元素之前插入一个元素的概率，则在个元素之前插入一个元素的概率，则在长度为长度为n的线性表中插入一个元素时，所需移动的的线性表中插入一个元素时，所需移动的元素的平均次数为：元素的平均次数为：插入操作的时间主要花费在元素后移上插入操作的时间主要花费在元素

17、后移上19（6）删除操作）删除操作在顺序表中删除第在顺序表中删除第i个元素：个元素：顺序表的逻辑结构由顺序表的逻辑结构由(a1,ai-1,ai,ai+1,an)改变为改变为(a1,ai-1,ai+1,an)算法思想算法思想1）检查）检查i值是否超出所允许的范围（值是否超出所允许的范围（1in），），若若超出，则进行超出，则进行“超出范围超出范围”错误处理；错误处理；2）将表的第）将表的第i个元素后面的所有元素均向前移动一个元素后面的所有元素均向前移动一个位置；个位置；3）使表的长度减）使表的长度减1。20内存内存a1a2aiai+1an01i-1数组下标数组下标n-1in12i元素序号元素序号

18、i+1nn+1内存内存a1a2ai+1数组下标数组下标01i-1n-2in-112i元素序号元素序号i+1n-1nanai+2删除前删除前删除后删除后图图2.3 顺序表删除操作前后变化顺序表删除操作前后变化21int delete(sqlist*L，int i)int j;/*检查位置的合法性检查位置的合法性*/if(iL-length)return 0;/*将表的第将表的第i个元素后面的所有元素均向前移动一个元素后面的所有元素均向前移动一个位置个位置*/for(j=i;jlen-1;j+)L-dataj-1=L-dataj;/*表长减表长减1*/L-length-;return 1;22q算

19、法时间性能分析算法时间性能分析故在故在顺序表中插入或删除顺序表中插入或删除一个元素时，平均移一个元素时，平均移动表的一半元素，当动表的一半元素，当n n很大时，很大时，效率很低效率很低设设Pi是删除第是删除第i个元素的概率，则在长度为个元素的概率，则在长度为n的线性表的线性表中删除一个元素所需移动的元素的平均次数为：中删除一个元素所需移动的元素的平均次数为：时间主要花费在元素前移上时间主要花费在元素前移上等概率23（7）输出操作）输出操作 void print(sqlist L)int i;for(i=0;ilength;i+)printf(“%4d ”,L-datai);printf(“n”

20、);24 例例 有有两两个个顺顺序序表表L1L1和和L2L2，其其元元素素均均为为非非递递减减有有序序排排列列，编编写写算算法法，将将其其合合并并成成一一个个顺顺序序表表L L，要要求求L L也是也是非递减非递减有序排列。有序排列。例如例如L1=(2,2,3),L2=(1,3,3,4L1=(2,2,3),L2=(1,3,3,4),),则则L=(1,2,2,3,3,3,4)L=(1,2,2,3,3,3,4)。算算法法思思想想：设设表表L L是是一一个个空空表表，为为使使L L也也是是非非递递减减有有序序排列，可设两个指针排列，可设两个指针i,ji,j分别指向表分别指向表L1L1和和L2L2中的元

21、素，中的元素，从两个顺序表的第从两个顺序表的第1 1个元素开始进行比较个元素开始进行比较:若若L1.dataiL1.dataiL2.dataj,L2.dataj,将将L1.dataiL1.datai插入到插入到L L表尾表尾若若L1.dataiL2.dataj,L1.dataiL2.dataj,将将L2.datajL2.dataj插入到插入到L L表尾表尾如如此此进进行行下下去去，直直到到其其中中一一个个表表被被扫扫描描完完毕毕，然然后后再再将未扫描完的表中剩余的所有元素放到表将未扫描完的表中剩余的所有元素放到表L L中。中。25void merge(sqlist L1,sqlist L2,s

22、qlist*L)int i,j;/*i/*i是是L1L1中元素下标中元素下标,j j是是L2L2中元素下标中元素下标*/i=0;j=0;/*/*表表L L初始化初始化*/initlist(L);while(iL1.length&jL2.length)/*/*从头开始比较从头开始比较L1.dataiL1.datai和和L2.dataj*/L2.dataj*/if(L1.datailength+1,L1.datai);i+;else/*/*将将L1.datajL1.dataj插入到插入到 L L 尾部尾部*/insert(L,L-length+1,L2.dataj);j+;26 /*L1中元素有剩

23、余,将表将表L1L1余下的元素插入到表余下的元素插入到表L L尾部尾部 */while(ilength)insert(L,L-length+1,L1.datai);i+;/*L2中元素有剩余,将表将表L2L2余下的元素插入到表余下的元素插入到表L L尾部尾部 */while(jlength)insert(L,L-length+1,L2.dataj);j+;L-length=L1-length+L2-length;时间性能分析：O(L1-length+L2-length)=O(m+n)27作业：（1）设A和B是两个非递减的顺序表，编写算法，把A和B中都存在的元素组成新的由大到小排列的顺序表C，并分析算法的时间复杂度。（2）编写算法，删除顺序表A中元素值在x到y之间的所有元素。28