数据结构第二章教学.ppt
第二章 线性表线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继主讲教师：戴磊 2.1 线性表的类型定义 定义：一个线性表是n 个数据元素的有限序列,a,()n ia a a 2 1如例 英文字母表（A,B,C,.Z)是一个线性表例数据元素 特征：v 元素个数n 表长度，n=0 空表v1in 时lai 的直接前驱是ai-1，a1 无直接前驱lai 的直接后继是ai+1，an 无直接后继v 元素同构，且不能出现缺项例2-1假设有两个集合A 和B 分别用两个线性表LA 和LB 表示（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合A A B。要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB 中而不存在于线性表LA 中的数据元素插入到线性表LA 中。1从线性表LB 中依次取得每个数据元素;GetElem(LB,i)e2依值在线性表LA 中进行查访;LocateElem(LA,e,equal()3若不存在，则插入之。ListInsert(LA,n+1,e)voidunion(List&La,ListLb)/将所有在线性表Lb 中但不在La 中的数据元素插入到La 中La_len=ListLength(La);Lb_len=ListLength(Lb);/求线性表的长度for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/取Lb 中第i 个数据元素赋给eif(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La 中不存在和e 相同的数据元素，则插入之/union例2-2 已知一个非纯集合B，试构造一个纯集合A，使A 中只包含B 中所有值各不相同的数据元素。voidpurge(List&La,ListLb)/已知线性表Lb 中的数据元素依值非递减有序排列(Lb 是有序表)/构造线性表La，使其只包含Lb 中所有值不相同的数据元素InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);/求线性表的长度for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/取Lb 中第i 个数据元素赋给eif(!equal(en,e)ListInsert(La,+La_len,e);en=e;/La 中不存在和e 相同的数据元素，则插入之/purge例2-3 归并两个“其数据元素按值非递减有序排列的”线性表LA 和LB，求得线性表LC 也具有同样特性设La=(a1,ai,an)Lb=(b1,bj,bm)Lc=(c1,ck,cm+n)则Ck=k=1,2,m+n1分别从LA 和LB 中取得当前元素ai 和bj；2若aibj，则将ai 插入到LC 中，否则将bj 插入到LC 中。voidMergeList(ListLa,ListLb,List&Lc)/已知线性表La 和Lb 中的元素按值非递减排列。/归并La 和Lb 得到新的线性表Lc，/Lc 的元素也按值非递减排列。InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len)&(j=Lb_len)/La 和Lb 均非空GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;elseListInsert(Lc,+k,bj);+j;while(i=La_len)GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j=Lb_len)GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/merge_list 2.2 线性表的顺序表示和实现 顺序表：v 定义：用一组地址连续的存储单元存放一个线性表叫v 元素地址计算方法：lLOC(ai)=LOC(a1)+(i-1)*LlLOC(ai+1)=LOC(ai)+Ll 其中：uL 一个元素占用的存储单元个数uLOC(ai)线性表第i 个元素的地址v 特点：l 实现逻辑上相邻物理地址相邻l 实现随机存取v 实现：可用C 语言的一维数组实现a1a2an01n-112n内存V数组下标元素序号M-1/线性表的动态分配顺序存储结构#define LIST_INIT_SIZE 100#define LISTINCREMENT 10 typedef struct ElemType*elem;int length;int listsize;SqList;备用空间数据元素不是简单类型时,可定义结构体数组或动态申请和释放内存ElemType*p=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);free(p);线性表的初始化在顺序映像中的实现StatusInitList_Sq(SqList&L)/构造一个空的线性表L。L.elem=(ElemType*)malloc(LISTINCREMENT*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/存储分配失败L.length=0;/长度为0L.listsize=LISTINCREMENT;/初始存储容量returnOK;/InitList_Sq 线性表初始化 插入v 定义：线性表的插入是指在第i（1 i n+1）个元素之前插入一个新的数据元素x，使长度为n 的线性表a,ai 1()n ia a a,2 1-变成长度为n+1的线性表x,i()n ia a a a a,1 2 1-需将第n至第i共（n-i+1)个元素后移v 算法Ch2_1.c此算法的时间复杂度为:O(ListLength(L)Status ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序线性表L 中第i 个位置之前插入新的元素e，/i 的合法值为1iListLength_Sq(L)+1 if(iL.length+1)return ERROR;/i 值不合法 if(L.length=L.listsize)/当前存储空间已满，增加分配 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存储分配失败 L.elem=newbase;/新基址 L.listsize+=LISTINCREMENT;/增加存储容量 q=&(L.elemi-1);/q 为插入位置 for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移*q=e;/插入e+L.length;/表长增1 return OK;/ListInsert_Sq C 源代码：int sxbcr(int i,int x,int v,int*p)int j,n;n=*p;if(in+1)return(0);else for(j=n;j=i;j-)vj=vj-1;vj=x;*p=+n;return(1);内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1xv 算法时间复杂度T(n)l 设Pi 是在第i 个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：删除v 定义：线性表的删除是指将第i（1 i n）个元素删除，使长度为n 的线性表 变成长度为n-1的线性表 需将第i+1至第n共（n-i)个元素前移v 算法Ch2_2.c此算法的时间复杂度为:O(ListLength(L)Status ListDelete_Sq(SqList&L,int i,ElemType&e)if(iL.length)return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p;-L.length;return OK;/ListDelete_SqC 源代码：int sxbsc(int i,int v,int*p)int j,n;n=*p;if(in)return(0);else for(j=i;jn;j+)vj-1=vj;*p=-n;return(1);内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2v 算法评价l 设Qi 是删除第i 个元素的概率，则在长度为n 的线性表中删除一个元素所需移动的元素次数的平均次数为：故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低线性表操作LocateElem(L,e,compare()的实现：int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序线性表L中查找第1个值与e满足compare()的元素的位序。/若找到，则返回其在L中的位序，否则返回0。i=1;/i的初值为第1元素的位序p=L.elem;/p的初值为第1元素的存储位置while(i=L.length&!(*compare)(*p+,e)+i;if(i=L.length)return i;elsereturn 0;/LocateElem_Sq此算法的时间复杂度为:O(ListLength(L)定位 顺序存储结构的优缺点v 优点l 逻辑相邻，物理相邻l 可随机存取任一元素l 存储空间使用紧凑v 缺点l 插入、删除操作需要移动大量的元素l 预先分配空间需按最大空间分配，利用不充分l 表容量难以扩充
