第二章(1)顺序表

2,第2章线性表栈和队列串第3章数组和广义表,线性结构,（逻辑、存储和运算）,线性结构特点：在数据元素的非空有限集(a1,a2,an)中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中每个数据元素均只有一个前驱除最后一个外，集合中每个元素均只有一个后继,3,第二章线性表,2.1线性表定义及基本操作2.2线性表的顺序存储2.3线性表的链式存储2.3.1单链表2.3.2双向链表2.3.3循环链表2.4栈2.4.1栈的定义及其基本操作2.4.2顺序栈的表示和实现*2.4.3链栈的表示和实现,4,2.5队列2.5.1队列的定义及其基本操作2.5.2顺序队列的表示和实现*2.5.3链队列的表示和实现2.6串2.6.1串的定义及其基本操作2.6.2顺序串的表示和实现*2.6.3链串的表示和实现*2.6.4串的模式匹配,5,L=（a1,a2,ai-1，ai,ai1，,an）,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标i，是元素ai的序号，表示ai在表中的位置,n为元素总个数，即表长,空表,线性终点,2.1.1线性表的基本概念定义：线性表是n(n0)个数据元素的有限序列,可记作：,2.1线性表的定义及基本操作,6,2、线性表的结构是通过数据元素之间的相邻关系来体现的。,说明：1、数据元素可以是一个数，一个符号或一个记录等，但同一线性表中的元素必须属于同一种数据对象。,例1、一年的月份号（1，2，3，4，5，12）例2、英文字母表（a,b,c,，z）例3、某单位的电话号码簿,由于上述关系是线性的-线性结构。,7,(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)删除操作delete(L,i)删除线性表L的第i个元素，i的合法到值范围是：1in1输出操作print(L)按先后顺序输出线性表L的所有元素值。,2.1.2线性表的基本操作,8,说明:1上面列出的操作，只是线性表的一些常用的基本操作；2不同的应用，基本操作可能是不同的；3线性表的复杂操作可通过基本操作实现；,9,2.2顺序表-线性表的顺序存储结构2.2.1顺序表的定义1.定义：用一组地址连续的存储单元将逻辑上相邻的元素存放在物理地址也相邻的存储单元。,2.元素地址计算方法：,LOC(ai+1)=LOC(ai)+k(2in)LOC(ai)=LOC(a1)+(i-1)*k(1in),图2.1顺序表,其中：k一个元素占用的存储单元个数LOC(ai)顺序表第i个元素的地址LOC(a1)顺序表的基址,10,特点：实现逻辑上相邻物理地址相邻实现随机存取实现：可用C语言的一维数组实现,这里采用动态分配的一维数组，在初始化时先用函数malloc（）为顺序表分配一个基本容量，在操作过程中，若顺序表的空间不足，再用函数realloc（）增加空间。,11,typedefintElemType;/*在实际问题中，根据需要定义所需的数据类型*/#defineINITSIZE100/*顺序表存储空间的初始分配量*/typedefstructElemType*data;/*存储空间基地址*/intlength;/*顺序表当前长度,即已存入的元素个数*/intlistsize;/*当前存储空间容量*/sqlist;,动态申请和释放内存ElemType*data=(ElemType*)malloc(INITSIZE*sizeof(ElemType);free(data);,顺序表的类型定义：,元素存放在data0到datalength-1中。,12,2.2.2基本操作在顺序表上的实现,(1)初始化操作：构造一个空的顺序表Lvoidinitlist(sqlist*L)/*构造一个空的顺序表L*/,L-data=(ElemType*)malloc(INITSIZE*sizeof(ElemType);if(!L-data)printf(“OVERFLOW!n”);exit(1);/*存储分配失败*/L-length=0;/*长度为0*/L-listsize=INITSIZE;/*初始存储容量*/,算法性能分析:时间性能O(1)空间性能O(1),13,(2)求表长操作统计顺序表L数据元素的个数intgetlen(sqlistL)/*统计顺序表L数据元素的个数*/,return(L.length);,算法性能分析:时间性能O(1)空间性能O(1),14,(3)取元素操作取出顺序表L的第i个数据元素的值,将值通过参数e带回，成功返回1,失败返回0.注意i的合法取值范围:1ilengthintgetelem(sqlistL,inti,ElemType*e)/*取出顺序表L的第i个数据元素的值*/,if(i=1,算法性能分析:时间性能O(1)空间性能O(1),15,算法性能分析:时间性能查找成功:平均时间复杂度查找失败:空间性能O(1),(4)元素定位操作intlocate(sqlistL,ElemTypex)/*从线性表中查找具有给定值x的第一个元素若找到，则返回其在L中的位序，否则返回0。*/,inti=0;/*从前向后扫描顺序表,没找到i值加1*/while(ilength+1)return0;/*存储空间不足，增加存储空间*/if(L-length=L-listsize)L-data=(ElemType*)realloc(L-data,(L-listsize+1)*sizeof(ElemType);if(!L-data)printf(“OVERFLOWER!n”);return0;L-listsize+;/*将序号i的结点及之后的结点后移一位*/for(j=L-length-1;j=i-1;j-)L-dataj+1=L-dataj;/*在序号i处放入x*/L-datai-1=x;/*表长加1*/L-length+;return1;,19,顺序表插入操作时间性能分析：,20,（6）删除操作,在顺序表中删除第i个元素：顺序表的逻辑结构由(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,ai+1,an)算法思想1）检查i值是否超出所允许的范围（1in），若超出，则进行“超出范围”错误处理；2）将表的第i个元素后面的所有元素均向前移动一个位置；3）使表的长度减1。,21,删除前,删除后,图2.3顺序表删除操作前后变化,22,intdelete(sqlist*L，inti)intj;/*检查位置的合法性*/if(iL-length)return0;/*将表的第i个元素后面的所有元素均向前移动一个位置*/for(j=i;jlen-1;j+)L-dataj-1=L-dataj;/*表长减1*/L-length-;return1;,23,算法时间性能分析,故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低,设Pi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素的平均次数为：,时间主要花费在元素前移上,等概率,24,（7）输出操作,voidprint(sqlistL)inti;for(i=0;ilength;i+)printf(“%4d”,L-datai);printf(“n”);,25,例有两个顺序表L1和L2，其元素均为非递减有序排列，编写算法，将其合并成一个顺序表L，要求L也是非递减有序排列。例如L1=(2,2,3),L2=(1,3,3,4),则L=(1,2,2,3,3,3,4)。,算法思想：设表L是一个空表，为使L也是非递减有序排列，可设两个指针i,j分别指向表L1和L2中的元素，从两个顺序表的第1个元素开始进行比较:若L1.dataiL2.dataj,将L1.datai插入到L表尾若L1.dataiL2.dataj,将L2.dataj插入到L表尾如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表L中。,26,voidmerge(sqlistL1,sqlistL2,sqlist*L)inti,j;/*i是L1中元素下标,j是L2中元素下标*/i=0;j=0;/*表L初始化*/,initlist(L);while(ilength+1,L1.datai);i+;else/*将L1.dataj插入到L尾部*/insert(L,L-length+1,L2.dataj);j+;,27,/*L1中元素有剩余,将表L1余下的元素插入到表L尾部*/while(ilength)insert(L,L-length+1,L1.datai);i+;/*L2中元素有剩余,将表L2余下的元素插入到表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),28,顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充,29,总程序,typedefintelemtype;typedefstructelemtype*data;intlen,listsize;sqlist,*psqlist;main()sqlistla;init(,30,综合应用1.在顺序表给定值之前插入一个元素,1)查找2)if存在,插入elseerror;Insert(sqlist*l,intx)inti;i=locate(l,x);if(i!=-1)insert(l,i,x);,31,2.将x插入到已按数据域值从小到大排列的有序表中。,Insert(sqlist*l,intx)if(l-len=l-listsize)printf(“overflow”);elsefor(i=l-len-1;i=0;i-)if(l-dataix)l-datai+1=l-datai;elsebreak;L-datai+1=x;L-len+;,32,3.顺序表给定元素删除.,1)查找2)存在,删除x,不存在error.Delete(sqlist*l,intx)inti;i=locate(l,x);if(i!=-1)delete(l,i);,33,4.删除线性表L中所有值为x的数据元素.,Deletex(sqlist*l,Elemtypex)inti=0,k=0;while(ilen)if(l-datai=x)k+;elsel-datai-k=l-datai;i+;l-len=l-len-k;,34,5.实现顺序表的就地逆置。,converse(Sqlist*l)intr=l-len/2;for(i=0;idatai;l-datai=l-datal-len-i-1;l-datal-len-i-1=x;,35,6.合并(1-a)无序表简单首尾相接合并,merge1(Sqlist*La,Sqlist*Lb,Sqlist*Lc)for(i=0,j=0;ilen;i+,j+;)Lc-dataj=La-datai;for(i=0;ilen;i+,j+)Lc-dataj=Lb-datai;,36,(1-b)无序表合并(不保留相同元素)例:假设利用两个线性有LA和LB分别表示两个集合A和B,现要求一个新的集合A=AUB.,算法思想:扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中.只要从线性表LB中依次取每个数据元素,并依值在线性表LA中进行查访,若不存在,则插入.,37,voidunion(sqlist*LA,sqlistLB)for(i=0;ilen+,LB.datai);,38,(2)有序表的合并(已知线性表LA和LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按值非递减有序.假如设LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)则LC=(2,3,5,6,8,8,9,11,11,15,20).,算法思想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i,j分别指向表LA和LB中的元素，从两个顺序表的第1个元素开始进行比较:若LA.dataiLB.dataj,将LA.datai插入到LC表尾若LA.dataiLB.dataj,将LB.dataj插入到LC表尾如此进行下去，直到其中一个