第二章线性表2.1线性表的类型定义4.线性表的逻辑结构例子：英文字母表(A,B,…,Z)；车辆登记表。5.线性表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系<ai,ai+1>。2.1线性表的类型定义2.1线性表的类型定义练习2：两个线性表LA和LB中的数据元素按值非递减有序排列，现将LA和LB归并为一个新的线性表，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)voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);i=j=1;k=0;while((i<=La_len)&&(j<=Lb_len)){GetElem(La,i,a);GetElem(Lb,j,b);if(a<=b){ListInsert(Lc,++k,a);++i;}else{ListInsert(Lc,++k,b);++j;}}while(i<=La_len){GetElem(La,i++,a);ListInsert(Lc,++k,a);}while(j<=Lb_len){GetElem(Lb,j++,b);ListInsert(Lc,++k,b);}}O(ListLength(La)+ListLength(Lb))特点：存储单元地址连续（需要一段连续空间）逻辑上相邻的数据元素其物理位置也相邻存储密度大（100%）随机存取元素序号与存储位置存在如下关系：顺序表：按顺序存储方式构造的线性表。2.2线性表的顺序表示和实现原型：externvoid*malloc(unsignedintnum_bytes);用法：#include<alloc.h>功能：分配长度为num_bytes字节的内存块说明：如果分配成功则返回指向被分配内存的指针，否则返回空指针NULL。当内存不再使用时，应使用free()函数将内存块释放。2.2线性表的顺序表示和实现2.2线性表的顺序表示和实现2.2线性表的顺序表示和实现2.2线性表的顺序表示和实现原型：externvoid*realloc(void*mem_address,unsignedintnewsize);用法：#include<alloc.h>功能：改变mem_address所指内存区域的大小为newsize长度。说明：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。当内存不再使用时，应使用free()函数将内存块释放。2.2线性表的顺序表示和实现2.2线性表的顺序表示和实现2.2线性表的顺序表示和实现2.2线性表的顺序表示和实现顺序表的归并，表中元素非递减排列。voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(…);if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while((pa<=pa_last)&&pb<=pb_last)){if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;}内容回顾内容回顾内容回顾练习已知A、B、C为三个元素值递增有序的顺序表，现要求对A作如下运算，删去那些即在B中出现又在C中出现的元素，实现上述算法并分析时间复杂度。A=A-(B∩C)A=(1,2,6,6,8,9,10,10,11,15)B=(1,2,6,6,7,9,10,15)C=(3,4,6,7,7,9,9,9,10,12)A=(1,2,8,11,15)分析:先从B和C中找出公有元素,记为same；A中从当前位置开始,凡小于same的元素均保留(存到新的位置),等于same的跳过；大于same时就再找下一个same.voidSqList_Intersect_Delete(SqList&A,SqListB,SqListC){pa=A.elem;pa_