数据结构第2章(1)

《数据结构第2章(1)》由会员分享，可在线阅读，更多相关《数据结构第2章(1)（47页珍藏版）》请在金锄头文库上搜索。

1、数 据 结 构, 第2章 线性表,目 标,理解线性表的定义及其运算； 掌握顺序表和链表的定义、组织形式、结构特征和类型说明；两种表上实现的插入、删除和按值查找的算法； 掌握循环链表、双(循环)链表的结构特点 理解循环链表、双(循环)链表的插入、删除操作。,本章内容,2.1 线性表的逻辑结构,2.2 线性表的顺序存储及运算实现,2.3 线性表的链式存储及运算实现,2.1 线性表的逻辑结构,2.1.1 线性表的定义 2.1.2 线性表的抽象数据类型定义,2.1.1 线性表的定义,逻辑结构：线性表是一种最简单的线性结构。 它具有以下特点：,存在唯一的“第一元素”，没有前驱； 除第一元素外，其它元素均

2、有唯一的“前驱“。 存在唯一的“最后元素”，没有后继； 除最后元素外，其它元素均有唯一的“后继“；,2.1.1 线性表的定义,（a1, a2, ai-1 , ai, ai1 ，, an）,线性表定义：n个数据元素的有限序列。,n=0时称为,数据元素,第一个元素,ai的直接前趋,ai的直接后继,n为元素总个数，即表长,空表,最后一个元素,下标，是序号，表示元素在表中位置,2.1.2 线性表的抽象数据类型定义,ADT List数据对象：D=ai|aiElemType,i=1,2, ,n,n0数据关系：R=|ai-1,aiElemType,i=2, ,n基本操作：InitList(&L)操作结果：构

3、造一个空的线性表L。ListInsert(&L,int i,ElemType e)初始条件：线性表L已存在，1i L长度+1。操作结果：在L 中第i个位置之前插入元素e，长度加1。 ADT List,2.1.2 线性表的抽象数据类型定义,（1）线性表初始化：InitList(&L) （2）按值查找：LocateElem(L,x) （3）插入操作：ListInsert(&L,i,x) （4）删除操作：ListDelete(&L,i,x),本章内容,2.1 线性表的逻辑结构,2.2 线性表的顺序存储及运算实现,2.3 线性表的链式存储及运算实现,2.2 线性表的顺序存储及运算实现,2.2.1 线性

4、表的顺序存储 2.2.2 顺序表上基本运算的实现 2.2.3 顺序表应用举例,2.2.1 线性表的顺序存储,顺序存储的线性表简称为顺序表。 存储实现 用一组地址连续的存储单元依次存放线性表中的数据元素。 存储时保持物理位置与逻辑顺序一致。 每个数据元素占据的存储量是一个常量 C，则 LOC（ai）= LOC(a1) + (i-1) * C,2.2.1 线性表的顺序存储,顺序表数据类型定义通常将 data 和 length封装成一个结构体作为顺序表的存储结构： #define MAXSIZE *typedef struct ElemType dataMAXSIZE; int length; /顺

5、序表的长度 SqList;,2.2.1 线性表的顺序存储,顺序表数据类型定义(动态分配) #define LIST_INIT_SIZE 100 /初始存储空间 #define LISTINCREMENT 10 /空间分配增量 typedef struct ElemType *elem; /存储空间的基址int length; /当前长度int listsize; /当前分配的存储容量 SqList;,2.2 线性表的顺序存储及运算实现,2.2.1 线性表的顺序存储 2.2.2 顺序表上基本运算的实现 2.2.3 顺序表应用举例,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 2、顺序表

6、的查找 3、顺序表的插入 4、顺序表的删除,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 算法分析： 顺序表的初始化即构造一个空表，对表是一个加工型的运算。因此，需将L设为指针参数或引用参数。 需要动态申请空间。 将表中 length置为0，表示表中没有数据元素。 将表中 listsize等于初始分配的动态空间大小。,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 算法实现：,Status InitList_Sq(SqList ,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 算法实现：,void InitList_Sq(SqList ,2.2.2 顺序表上基本运算的

7、实现,1、顺序表的初始化 算法分析： 算法实现： 性能分析：时间复杂度为O(1)。 线性表进行求长度或判空表等操作时，直接读线性表的长度L.length或判断L.length是否等于0就可以实现相应操作。,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 2、顺序表的查找 3、顺序表的插入 4、顺序表的删除,2.2.2 顺序表上基本运算的实现,2、按值查找 算法分析： 初始条件：L存在，元素。 操作结果：返回在L中首次出现的的序号或地址，称查找成功; 否则，返回一特殊值表示查找失败。 算法实现：,2.2.2 顺序表上基本运算的实现,2、按值查找 算法实现：,int LocateElem_

8、Sq(SqList L, ElemType x) int i=0;while(iL.length ,数组形式实现！,2.2.2 顺序表上基本运算的实现,2、按值查找 算法实现：,int LocateElem_Sq(SqList L, ElemType x) int i=1; ElemType *p=L.elem;while(i=L.length ,指针形式实现！,2.2.2 顺序表上基本运算的实现,2、按值查找 算法分析： 算法实现： 性能分析：最好情况是查找第一个元素，时间复杂度O(1); 最坏情况是查找失败，时间复杂度为O(n);等概率的前提下，查找成功时，平均比较次数为（n+1）/2;时

9、间复杂度为O(n);,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 2、顺序表的查找 3、顺序表的插入 4、顺序表的删除,2.2.2 顺序表上基本运算的实现,3、插入运算 算法分析： 初始条件：L存在，1=i=n+1,为的表长。 操作结果：L的第 i 个位置上插入x ，表长+1。 插入成功：移动元素，插入元素，长度加1。 插入不成功：溢出；i不合法。 算法实现：,2.2.2 顺序表上基本运算的实现,3、插入运算 算法分析： 插入不成功：A、最初的存储空间大小是固定的。所以，有可能出现 “溢出”现象。B、插入位置i代表元素序号，取值范围为： 1 = i = L.length+1 。所以

10、，有可能超出范围。 算法实现：,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 算法实现：,Status ListInsert_Sq(SqList ,数组形式实现！,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 算法实现：,Status ListInsert_Sq (SqList ,数组形式实现！,溢出的处理： ElemType *newbase; newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) exit(OVERFLOW); L.elem=

11、newbase; L.listsize+=LISTINCREMENT;,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 算法实现：,Status ListInsert_Sq (SqList ,指针形式实现！,2.2.2 顺序表上基本运算的实现,3、插入运算 算法的时间性能分析： 元素的移动个数决定着算法的时间复杂度。 最好情况是插入在最后面，时间复杂度为O(1); 最坏情况是插入在最前面，时间复杂度为O(n); 等概率的情况下，元素的移动次数为n/2，时间复杂度为O(n)。,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 2、顺序表的查找 3、顺序表的插入 4、顺序表的删除,2

12、.2.2 顺序表上基本运算的实现,4、删除运算 算法分析： 初始条件：L存在，1=i=n。 操作结果：删除L中序号为i的元素，并用x返回其值，表长1。 删除成功：移动元素；表长减1。 删除不成功：空表；i不合法。 算法实现：,2.2.2 顺序表上基本运算的实现,4、删除运算 算法分析： 删除不成功：A、删除位置不合法：i是序号，1 = i =L.lengthB、对空表无法进行删除操作，L.length=0。 算法实现：,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 算法实现：,Status ListDelete_Sq (SqList ,数组形式实现！,2.2.2 顺序表上基本运算的实

13、现,1、顺序表的初始化 算法实现：,Status ListDelete_Sq (SqList ,指针形式实现！,2.2.2 顺序表上基本运算的实现,1、顺序表的初始化 算法实现：,Status ListDelete_Sq (SqList ,有时会出现不需要返回删除值的情况！,2.2.2 顺序表上基本运算的实现,4、删除运算 算法的时间性能分析： 元素的移动个数决定着算法的时间复杂度。 最好情况：删除最后一个元素， O(1); 最坏情况：删除第一个元素， O(n); 等概率的情况：元素的移动次数为(n-1)/2，时间复杂度为O(n)。,2.2.2 顺序表上基本运算的实现,涉及到位置的必须判断位置

14、的合法性； 进行插入时需要判断溢出，进行删除时，需要判断空表； 插入和删除算法的时间复杂度为O(n)，所以该存储方式不适宜做插入和删除操作；读取顺序表中的元素时，时间复杂度为O(1) ，所以该存储方式适宜做读取操作。,2.2 线性表的顺序存储及运算实现,2.2.1 线性表的顺序存储 2.2.2 顺序表上基本运算的实现 2.2.3 顺序表应用举例,2.2.3 顺序表应用举例,例1: 编写有序表的插入算法。 例2：编写删除顺序表中所有值为x的元素的算法。 例3：编写删除表中值相同的多余元素的算法。 例4：编写顺序表的合并算法。,2.2.3 顺序表应用举例,例1：编写算法。将给定元素x插入到有序表L中的合适位置，使得L仍然有序。 算法分析： 实现算法：,2.2.3 顺序表应用举例,例2：编写算法。从顺序表L中删除所有值为x的元素。 算法分析： 实现算法：,2.2.3 顺序表应用举例,例3：编写算法。从顺序表L中删除所有重复的元素。 算法分析： 实现算法：,2.2.3 顺序表应用举例,例4：编写算法。有顺序有序表A和B，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大有序排列的。 算法分析： 实现算法：,掌握线性表的顺序存储的实现及顺序表的存储类型定义。 掌握顺序表的创建、查找、插入和删除算法及算法的分析（时间复杂度）。,总 结,Thank You！,