数据结构zmz2顺序表.ppt

主讲：郑梦泽 信息工程学院 大家好 第二章2.2 顺序表 一、线性表的定义 一、线性表的定义 书目文件 各条书目信息之间存在一个对一个的线性关系 数据对象、数据元素（记录）、数据项（属性） 数据操作：查找，插入，删除，修改等 在数据元素的非空有限集中 存在存在唯一唯一的一个被称作的一个被称作“ “第一个第一个” ”的数据元素的数据元素 存在存在唯一唯一的一个被称作的一个被称作“ “最后一个最后一个” ”的数据元素的数据元素 除第一个外，集合中的每个数据元素均除第一个外，集合中的每个数据元素均只有一个只有一个 前驱前驱 除最后一个外，集合中的每个数据元素均除最后一个外，集合中的每个数据元素均只有一只有一 个后继个后继 一、线性表的定义（特点） 定义：一个线性表是n个数据元素的有限序列 例 打字游戏（B,H,Y,UT) 特征：有限、序列、同构 元素个数n表长度，n=0空表 1| ai-1，aiD, i=2，n ,i为线性表中位置 基本操作： 结构初始化操作 结构销毁操作 引用型操作(只读操作) 加工型操作(修改操作) ADT List 二、线性表的抽象数据类型定义 初始化操作： InitList(否则返回FALSE ListLength(L) /求线性表的表长 初始条件：线性表L已存在 操作结果：返回L中数据元素个数 GetElem(L, i , int n; /*元素个数na1=200; p-length=20; length elem 表长 三、线性表的顺序存储结构方案二 缺点：表容量难以扩充 length表长 listsize 表容量 elem存储区首地址 a1 a2 an 0 1 length-1 listsize-1 elem 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 int aListSize; SqList; SqList L; /*假设数据元素为整型变量*/ 四、顺序表的C语言实现 Status ListEmpty_Sq(SqList L) if(L.length= = 0)return True; elsereturn False; 初始化 （静态 表） 判空 void DestroyList_Sq(SqList if(L.elem)free(L.elem); L.elem=NULL; Status GetElem_Sq(SqList L, int i, int elsee=L.elemi-1; return True; int ListLength_Sq(SqList L) return L.length; 求表长 销毁表 取数据 元素值 四、顺序表的C语言实现 int LocateElem_Sq(SqList L, int e) 顺序表查找: (返回元素的序列号) 算法时间复杂度：O(n ) 找64 iiiiiii 5 13 19 21 37 56 64 75 查找成功 L.elemL.lengthL.listsize while (i L L.length+1).length+1) printfprintf(“(“位置不对位置不对” ”);return );return FalseFalse; ; if(if(L.lengthL.length= = =ListSizeListSize) ) printfprintf(“ (“数据溢出数据溢出” ”); return ); return FalseFalse; ; for(for(j j= =L.lengthL.length ; ; j=i j=i ; ; j j-)-) L.elemL.elem j+1 j+1 = = L.elemL.elem j j ; ; L.elemL.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.lengthL.length- - a1 a2 ai ai+1 an 1 2 i i+1 L.length ai+1 ai+2 an StatusStatus ListDelete_SqListDelete_Sq ( ( SqListSqList return );return FalseFalse; ; if(if(L.lengthL.length= = =0 0) ) printfprintf(“ (“表已空表已空” ”); return ); return FalseFalse; ; for(for(j j=i+1 =i+1 ; ; j=j=L.lengthL.length ; ; j j+)+) L.elemL.elem j-1 j-1 = = L.elemL.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 207 Lb Lc 11 4La lengthelem 35811 i j k La_len Lb_len 2 j k 3 k i 5 k i 6 j k 8 i k 8 j k 9 j k 11 i k 11 j k 15 j k 20 j k MergeList_Sq(SqList La, SqList Lb, SqList int a,b; InitList_Sq(Lc); i=j=k=1; Lc.len=La.len + Lb.len; /* 新的长度 */ while(i=La.len) 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