数据结构_ch2.ppt

1、,数据结构,Data Structure,第2章 线性表及线性表的顺序存储,2.1 线性表的定义 2.2 线性表的顺序存储结构（顺序表） 2.3 顺序表基本算法实现 2.4 顺序表的查找 2.5 插入与删除操作的效率分析 2.6 顺序表应用举例 小结,第一节 线性表的定义,2.1.1 线性表实例,1、需要准备一张大小适当的白纸 2、登记预约情况 3、取消预约（或已经用餐） 4、将记录销毁或存档,第一节 线性表的定义,2.1.1 线性表实例,创建一个空的线性表（准备一张白纸） 插入一个新的元素（书写一个新顾客的信息） 删除一个元素（划掉一个取消预定或已经就餐的顾客的信息） 查找指定的元素（在划掉

2、“约翰”的信息之前，需要查找有关“约翰”的信息是否存在） 清空线性表（将纸张销毁或存档）,第一节 线性表的定义,2.1.2 线性表的定义和基本操作,线性表（Linear List）的定义：线性表是具有相 同类型的n 个数据元素组成的有限序列，通常记为 (a1， a2， ai-1，ai，ai+1，an)。其中，ai是表中元素，n 是表的长度，当n=0时线性表为空表。当n0 时，a1是 第一个元素，也称为表头元素，an是最后一个元素，也 称为表尾元素。a1是a2的直接前驱元素，a2是a3的直接 前驱元素，而a2是a1的直接后继元素，a3是a2的直 接后继元素。,第一节 线性表的定义,2.1.2 线

3、性表的定义和基本操作,线性表的基本操作包括： 1、创建空的线性表； 2、求线性表的长度； 3、插入一个新的元素； 4、删除一个元素； 5、查找指定的元素； 6、清空线性表。,第一节 线性表的定义,2.1.3 线性表的数学定义和逻辑图,从集合论的观点出发，线性表是由两个集合构 成的一个二元组。 LinearList=(D,R) 其中，D= ai| aiElemSet, i=1,2, ,n n1 R=| ai, ai+1iD, i=1,2, ，n Elemset为某一数据对象集；n为线性表的长度。 n=0时，线性表为空表。,第一节 线性表的定义,2.1.3 线性表的数学定义和逻辑图,分数表=(D,

4、R) D=99,100,88,76,89,56,96,98; R=,第一节 线性表的定义,2.1.3 线性表的数学定义和逻辑图,学生名册表(“王雨”,“白雪”,“钱洋”,“赵纯”) 的二元组表示是： 名册表=(D,R) D=王雨,白雪,钱洋,赵纯; R=,第二节 线性表的顺序存储结构（顺序表）,下标从0开始,下标从1开始,第二节 线性表的顺序存储结构（顺序表）,计算机中用一组地址连续的存储单元依次存储线 性表的各个数据元素，称作线性表的顺序存储结构， 也称为顺序表（Sequential List）。 int ElementMaxSize; /*存储线性表内容的数组*/ int Length;

5、/*线性表的长度*/,第二节 线性表的顺序存储结构（顺序表）,typedef int ElemType; typedef struct ElemType ElementMaxSize; /*存储线性表内容的数组*/ int Length; /*线性表的长度*/ SeqList; /*说明List数据类型*/ SeqList List; /*定义顺序表List*/,第二节 线性表的顺序存储结构（顺序表）,typedef int ElemType; typedef struct ElemType ElementMaxSize; /*存储线性表内容的数组*/ int Length; /*线性表的长度

6、*/ SeqList; /*说明List数据类型*/ SeqList List; /*定义顺序表List*/,第三节 顺序表基本算法实现,2.3.1 线性表内容与线性表长度分别存储的算法实现 int ElementMaxSize; /*存储线性表的数据元素*/ int Length; /*线性表长度*/ 1构造一个空表 算法2.1 构造一个空表 void Init_SeqList(int *Length_pointer) /*构造一个空表*/ *Length_pointer =0; ,2插入一个元素（尾插） 算法2.2插入一个元素（尾插） int Insert_Last(int Element

7、,int *Length_pointer,int x) /*插入一个元素(尾插)*/ if (*Length_pointer=MaxSize) printf(表满); return OverFlow; else Element*Length_pointer=x ; /*在表尾插入一个元素*/ (*Length_pointer)+ ; /*线性表长度加1*/ return OK; /*插入成功，返回 */ ,3查找指定元素 算法2.3 查找指定元素x int Location_SeqList(int Element,int Length,int x) /*查找指定元素x*/ int i=0; w

8、hile(iLength /*返回x的逻辑位置 */ ,4删除一个元素（删除线性表的第i个元素） 算法2.4删除线性表的第i个元素 int Delete_SeqList(int Element,int *Length_pointer, int i) int j; if(i*Length_pointer) /*判断参数的正确性*/ printf (不存在第i个元素); return Error ; for(j=i-1;j=*Length_pointer-1; j+) /*删除*/ Elementj=Elementj+1; /*向前移动*/ (*Length_pointer)-; /*线性表长度减

9、1*/ return OK ; ,5遍历线性表 算法2.5 遍历线性表 void Show_SeqList(int Element,int Length) /*遍历线性表*/ int j; if (Length=0) printf(空表(NULL)!n); else for(j=0;jLength; j+) /*显示*/ printf( %d,Elementj); ,6清空线性表 算法2.6清空线性表 void SetNull_SeqList(int *Length_pointer) /*清空线性表 */ *Length_pointer =0; 7完整的线性表操作程序,2.3.2 线性表内容与

10、线性表长度存储在一个结构体 中的算法实现 数据定义： typedef int ElemType; typedef struct ElemType ElementMaxSize; int Length; /*线性表的长度*/ SeqList; /*说明List数据类型*/ SeqList List;,1构造一个空表 算法2.7构造一个空表 void Init_SeqList(SeqList *L_pointer) /*构造一个空表*/ L_pointer -Length =0; ,2插入一个元素（尾插） 算法2.8 插入一个元素（尾插） int Insert_Last(SeqList *L_po

11、inter,ElemType x) /*插入一个元素(尾插)*/ if (L_pointer-Length=MaxSize) printf(表满); return OverFlow; else L_pointer-ElementL_pointer-Length=x ; /*在表尾插入一个元素*/ L_pointer-Length+ ; /*线性表长度加1*/ return OK; /*插入成功，返回*/ ,3查找指定元素 算法2.9 查找指定元素 int Location_SeqList(SeqList *L_pointer, ElemType x) /*查找指定元素*/ int i=0; w

12、hile(iLength /*返回x的逻辑位置 */ ,4删除一个元素（删除线性表的第i个元素） 算法2.10 删除线性表的第i个元素 int Delete_SeqList(SeqList * L_pointer, int i) int j; if(i L_pointer -Length) /*判断参数的正确性*/ printf (不存在第i个元素); return Error ; for(j=i-1;jLength-1; j+) /*删除*/ L_pointer -Elementj= L_pointer -Elementj+1; /*向左移动*/ L_pointer -Length-; /*

13、线性表长度减1*/ return OK ; ,5遍历线性表 算法2.11 遍历线性表 void Show_SeqList(SeqList * L_pointer) int j; printf(n); if (L_pointer -Length=0) printf(空表(NULL)!n); else for(j=0;jLength; j+) /*显示*/ printf( %d,L_pointer-Elementj); ,6清空线性表 算法2.12 清空线性表 void SetNull_SeqList(SeqList * L_pointer) /*清空线性表 */ L_pointer-Length

14、 =0; ,2.3.3 线性表中的元素是字符串的算法实现 typedef char ElemType10; typedef struct ElemType ElementMaxSize; int Length; /*线性表的长度*/ SeqList; /*说明List数据类型*/ SeqList List;,int Insert_Last(SeqList *L_pointer,ElemType x) /*插入一个元素(尾插)*/ if (L_pointer -Length=MaxSize) printf(表满); return OverFlow; else strcpy(L_pointer -

15、Element L_pointer Length,x); /*在表尾插入一个元素，注意使用字符串拷贝*/ L_pointer-Length+ ; 线性表长度加1*/ return OK; /* 插入成功，返回 */ ,第四节 顺序表的查找,2.4.1 顺序查找 顺序查找的思想是从表头元素开始，逐个比较每 个元素，直至查找成功，如果一直到表尾元素都没有 找到，则查找失败。,算法2.13 顺序查找 typedef int KeyType; typedef struct list_info KeyType key; /*其它成员的定义*/ ElemType ; typedef struct Elem

16、Type ElementMaxSize; int Length; /*线性表的长度*/ SeqList; /*说明List数据类型*/ int Location_SeqList(SeqList *L_pointer, KeyType x) /*查找指定元素*/ int i=0; while(iLength /*返回x的逻辑位置 */ ,查找字段,第四节 顺序表的查找,2.4.2 二分查找,算法2.14 二分法查找 int Bin_SeqList(SeqList *L_pointer, KeyType x) /*二分法查找指定元素*/ int Low,High,Middle; Low=0; /*

17、low和high存储待查询区域数组下标的上界和下界*/ High= L_pointer-Length-1; while(LowElementMiddle.key) return Middle+1; /*查找成功返回x的逻辑位置*/ else if(xElementMiddle.key) High=Middle-1; /*修改待查询数组区域的下界*/ else Low=Middle+1; /*修改待查询数组区域的上界*/ return -1; /*查找失败返回-1 */ ,第四节 顺序表的查找,2.4.3 顺序查找与二分查找的效率分析,表2.1顺序查找和二分查找的比较次数,第五节 插入与删除操作

18、的效率分析,2.5.1 在顺序表的第i个位置（逻辑位置）插入一个元素,第五节 插入与删除操作的效率分析,算法2.15 插入元素到第i个位置 int Insert_i(int Element,int *Length_pointer,int i,int x) /*插入一个元素到第i个位置)*/ int j; if (*Length_pointer=MaxSize) printf(表满); return OverFlow; else if(i*Length_pointer+1) /*判断插入位置是否正确)*/ printf(n插入位置错误!); return Error; ,else for (j=

19、*Length_pointer;j=i;j-) Elementj= Elementj-1 ; Elementi-1=x ; /*在表中插入一个元素*/ (*Length_pointer)+ ; /*线性表长度加1*/ return OK; /*插入成功，返回 */ ,2.5.2 插入算法的移动次数,表2.2插入算法的移动次数,插入位置越小，移动次数越多。移动的次数不但与插入的位 置有关还与线性表的长度有关。在插入所有位置概率相等的情况 下，平均移动次数为线性表长度的一半。,2.5.3 删除算法的移动次数,表2.3 删除算法的移动次数,移动次数与删除位置和线性表的长度有关。在删除位置概率 相等的

20、情况下，平均移动次数约为线性表长度的一半。,第六节 顺序表应用举例,问题一： 假设有两个由字符组成的线性表，求第二个线性表 中的字符串是否是第一个线性表中的字符串的子串，如 果是，返回第二个线性表在第一个线性表中出现的位置。 第一个线性表称为目标串（或称为主串），第二个线性 表称为模式（或称为子串）。求子串在主串中的位置的 过程称为模式匹配，也称为定位函数。定位函数的 功能准确描述是：求子串T在子串S中的开始位置。,第六节 顺序表应用举例,例如： 主串：aabbccadddeeeee 子串：adddee 则定位函数的计算结果是7。 主串：aabbccadddeeeee 子串：ccaddeee 则定位函数的计算结果是-1，表示不匹配。,第六节 顺序表应用举例,数据定义： typedef char ElemType; /*注意ElemType的实际是字符型*/ typedef struct ElemType ElementMaxSize; int Length; /*线性表的长度*/ SeqList; /*说明SeqList数据类型*/ 2.16 朴素的模式匹配 int index(SeqList * L_pointer1,SeqList * L_pointer2) /*顺序表实现模式匹配*/ int i,j,k;