数据结构zmz2顺序表.ppt
主讲：郑梦泽主讲：郑梦泽信息工程学院信息工程学院大家好大家好第二章第二章2.2 顺序表顺序表一、线性表的定义一、线性表的定义书目文件书目文件各条书目信息之间存在一个对一个的线性关系各条书目信息之间存在一个对一个的线性关系数据对象、数据元素（记录）、数据项（属性）数据对象、数据元素（记录）、数据项（属性）数据操作：查找，插入，删除，修改等数据操作：查找，插入，删除，修改等在数据元素的非空有限集中存在存在唯一唯一的一个被称作的一个被称作“第一个第一个”的数据元素的数据元素存在存在唯一唯一的一个被称作的一个被称作“最后一个最后一个”的数据元素的数据元素除第一个外，集合中的每个数据元素均除第一个外，集合中的每个数据元素均只有一个只有一个前驱前驱除最后一个外，集合中的每个数据元素均除最后一个外，集合中的每个数据元素均只有一只有一个后继个后继一、线性表的定义（特点）定义：一个线性表是n个数据元素的有限序列例例 打字游戏（打字游戏（B,H,Y,U.T)特征：有限、序列、同构元素个数n表长度，n=0空表1in时ai-1是ai的直接前驱，a1无直接前驱ai+1是ai的直接后继，an无直接后继运算：存取 插入 删除 查找 合并 分解 排序 求长度数据元素数据元素一、线性表的定义（逻辑结构）ADT List 数据对象数据对象：D=ai|ai ElemSet,i=1,2,n,n0,n表长表长,n=0,空表空表 数据关系数据关系：R=|ai-1，ai D,i=2，n,i为线性表中为线性表中位置位置 基本操作基本操作：结构结构初始化初始化操作操作 结构结构销毁销毁操作操作 引用型引用型操作操作(只读操作只读操作)加工型加工型操作操作(修改操作修改操作)ADT List二、线性表的抽象数据类型定义初始化操作初始化操作：InitList(&L)操作结果：构造一个空线性表操作结果：构造一个空线性表L结构销毁操作结构销毁操作：DestroyList(&L)初始条件：线性表初始条件：线性表L已存在已存在 操作结果：销毁线性表操作结果：销毁线性表L二、线性表的抽象数据类型定义引用型操作引用型操作：ListEmpty(L)/线性表判空线性表判空 初始条件：线性表初始条件：线性表L已存在已存在 操作结果：若操作结果：若L为空表，返回为空表，返回TRUE;否则返回否则返回FALSE ListLength(L)/求线性表的表长求线性表的表长 初始条件：线性表初始条件：线性表L已存在已存在 操作结果：返回操作结果：返回L中数据元素个数中数据元素个数 GetElem(L,i,&e)/求线性表的第求线性表的第i个元素个元素 初始条件：线性表初始条件：线性表L已存在，且已存在，且1i ListLength(L)操作结果：用操作结果：用e返回返回L中第中第i个数据元素的值个数据元素的值 LocateElem(L,e)/定位函数定位函数 初始条件：线性表初始条件：线性表L已存在已存在 操作结果：返回操作结果：返回L中第中第1个与个与e相同的元素的位序相同的元素的位序i二、线性表的抽象数据类型定义引用型操作引用型操作：PriorElem(L,e,&pre_e)/求数据元素的前驱求数据元素的前驱 初始条件：线性表初始条件：线性表L已存在已存在 操作结果：若操作结果：若e是是L中元素，且不是第一个，则用中元素，且不是第一个，则用pre_e返回其前驱返回其前驱 NextElem(L,e,&next_e)/求数据元素的后继求数据元素的后继 初始条件：线性表初始条件：线性表L已存在已存在 操作结果：若操作结果：若e是是L中元素中元素,且不是最后一个且不是最后一个,则用则用next_e返回其后继返回其后继 ListTraverse(L,visit()/线性表遍历线性表遍历 初始条件：线性表初始条件：线性表L已存在已存在,visit()为某个访问函数为某个访问函数 操作结果：依次对操作结果：依次对L中每个元素调用函数中每个元素调用函数visit()。二、线性表的抽象数据类型定义加工型操作加工型操作：ClearList(&L)/线性表置空线性表置空 初始条件：线性表初始条件：线性表L已存在已存在 操作结果：将操作结果：将L重置为空表重置为空表 ListInsert(&L,i,e)/插入数据元素插入数据元素 初始条件：线性表初始条件：线性表L已存在，且已存在，且1i ListLength(L)+1 操作结果：在操作结果：在L中第第中第第i个位置之前插入元素个位置之前插入元素e,L的长度加的长度加1 ListDelete(&L,i,&e)/删除数据元素删除数据元素 初始条件：线性表初始条件：线性表L已存在且非空，已存在且非空，1i ListLength(L)操作结果：删除操作结果：删除L的第的第i个元素个元素,并用并用e返回其值返回其值,L的长度减的长度减1 二、线性表的抽象数据类型定义 三、线性表的顺序存储结构an.ai.a2a1LlLOC(a2)=LOC(a1)+Ll其中：uL一个元素占用的存储单元个数uLOC(ai)线性表第i个元素的地址lLOC(ai+1)=LOC(ai)+LlLOC(ai)=LOC(a1)+(i-1)*L顺序表定义：用一组地址连续的存储单元存放一个线性表叫元素地址计算方法：三、线性表的顺序存储结构an.ai.a2a1Lv特点：l实现逻辑上相邻 物理地址相邻l实现随机存取v用什么数据类型来实现？v一维数组！顺序表#define M 100int aM;int n;/*元素个数元素个数na1=200;p-length=20;lengthelem表长三、线性表的顺序存储结构方案二方案二缺点：表容量难以扩充缺点：表容量难以扩充length表长listsize表容量elem存储区首地址a1a2an01length-1listsize-1elem L.elem=(int*)malloc(M*sizeof(int);free(L.elem);L.elem=(int*)realloc(L.elem,(L.listsize+20)*sizeof(int);SqList L;int elemM;=int *elem;动态动态申请申请和和释放释放内存内存int*elem=(ElemType*)malloc(M*sizeof(int);elem=(int*)realloc(elem,M*2*sizeof(int);free(elem);L.listsize=100;三、线性表的顺序存储结构方案三方案三/*/*定义定义动态动态顺序表顺序表*/*/#define M 100 /线性表初始大小线性表初始大小typedef struct int *elem;/存储空间基址存储空间基址 int length;/当前表长当前表长 int listsize;/当前分配的存储容量当前分配的存储容量SqList;void InitList_Sq(SqList&L)#define ListSize 100typedef struct int length=0;int aListSize;SqList;SqList L;/*假设数据元素为整型变量假设数据元素为整型变量*/四、顺序表的C语言实现Status ListEmpty_Sq(SqList L)if(L.length=0)return True;elsereturn False;初始化初始化（静静态态表）表）判空判空void DestroyList_Sq(SqList&L)L.length=0;if(L.elem)free(L.elem);L.elem=NULL;Status GetElem_Sq(SqList L,int i,int&e)if(iL.length)return False;elsee=L.elemi-1;return True;int ListLength_Sq(SqList L)return L.length;求表长求表长销毁表销毁表取取数数据据元素值元素值四、顺序表的C语言实现int LocateElem_Sq(SqList L,int e)顺序表查找:(返回元素的序列号)算法时间复杂度：算法时间复杂度：O(n)找找64iiiiiii 5 13 19 21 37 56 64 75查找成功查找成功L.elemL.lengthL.listsizewhile(i=L.length&L.elem i !=e)i+;if(i=L.length)return i;return 0;int i=1;/*elem0不用，使不用，使i和数组下标统一和数组下标统一*/四、顺序表的C语言实现顺序表在i的位置插入元素xelem0不用四、顺序表的C语言实现a1a2aiai+1an12ii+1L.lengthL.length+1anai+1aix1.1.从表尾开始后移从表尾开始后移从表尾开始后移从表尾开始后移2.2.插入元素插入元素插入元素插入元素L.elemi=xL.elemi=x3.3.什么时候不能插入什么时候不能插入什么时候不能插入什么时候不能插入4.4.长度长度长度长度+1 +1 L.length+L.length+StatusStatus ListInsert_Sq ListInsert_Sq(SqList&(SqList&L L,int,int i i,int,int x x)if(if(i i1|L L.length+1).length+1)printf(“printf(“位置不对位置不对”);return”);return FalseFalse;if(if(L.lengthL.length=ListSizeListSize)printf(“printf(“数据溢出数据溢出”);return”);return FalseFalse;for(for(j=L.length j=L.length;j=i j=i;j j-)-)L.elem L.elem j+1 j+1 =L.elem =L.elem j j;L.elem L.elemi i=x x;lengthlength+;return return TrueTrue;顺序表插入算法：四、顺序表的C语言实现判断判断i值合法性值合法性判断是否判断是否溢出溢出元素后移元素后移插入插入算法时间复杂度：算法时间复杂度：O(n)顺序表删除第i位置上的元素elem0不用四、顺序表的C语言实现1.1.从第从第从第从第i+1i+1个位个位个位个位置开始置开始置开始置开始前移前移前移前移2.2.什么时候不能删除什么时候不能删除什么时候不能删除什么时候不能删除3.3.长度长度长度长度-1 -1 L.length-L.length-a1a2aiai+1an12ii+1L.lengthai+1ai+2anStatusStatus ListDelete_Sq ListDelete_Sq(SqList&(SqList&L L,int,int i i)if(if(i i1|L L.length).length)printf(“printf(“位置不对位置不对”);return”);return FalseFalse;if(if(L.lengthL.length=0 0)printf(“printf(“表已空表已空”);return”);return FalseFalse;for(for(j=i+1 j=i+1;j=L.length j=L.length;j j+)+)L.elem L.elem j-1 j-1 =L.elem =L.elem j j;lengthlength-;return return TrueTrue;顺序表删除算法：四、顺序表的C语言实现算法时间复杂度：算法时间复杂度：O(n)例：例：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)268911 15 207Lb Lc114Lalengthelem35811 ijkLa_lenLb_len2jk3ki5ki6jk8ik8jk9jk11ik11jk15jk20jkMergeList_Sq(SqList La,SqList Lb,SqList&Lc)讨论：两个有序顺序表的合并讨论：两个有序顺序表的合并void MergeList_Sq(SqList La,SqList Lb,SqList&Lc)int i,j,k;int a,b;InitList_Sq(Lc);i=j=k=1;Lc.len=La.len+Lb.len;/*新的长度新的长度*/while(i=La.len)&(j=Lb.len)GetElem_Sq(La,i,a);GetElem_Sq(Lb,j,b);if(a=b)ListInsert_Sq(Lc,k+,a);i+;else ListInsert_Sq(Lc,k+,b);j+;while(i=La.len)GetElem_Sq(La,i+,a);ListInsert_Sq(Lc,k+,a);while(j=Lb.len)GetElem_Sq(Lb,j+,b);ListInsert_Sq(Lc,k+,b);顺序表特点总结分析优点编程简单查找元素方便缺点插入、删除效率低数组长度受限空间浪费很大解决方法“链式存储”链表
