数据结构与算法教程 教学课件 ppt 作者 朱明方 吴及 第2章 顺序表及其运算

1、第二章 线性表的顺序存储及其运算,2.1 线性表的概念 一、线性表的结构特性 二、线性表的抽象数据类型 2.2 顺序表及其运算 一、什么是顺序表 二、顺序表的运算 2.3 栈 一、栈的概念 二、栈的抽象数据类型 三、顺序栈及其操作实现 四、栈应用例,第二章 线性表的顺序存储及其运算,2.4 队列 一、队列及其抽象数据类型 二、顺序队列及其操作实现 三、队列应用例 四、优先队列 2.5 数组与矩阵的表示 一、数组的顺序分配 二、规则矩阵的压缩存储 三、稀疏矩阵的三元组顺序表表示,2.1 线性表的概念,一、线性表的结构特性 属性相同的数据元素按某种关系排列的表 例： 农历节气表 ( 立春, 雨水, 惊蛰, 春分, 清明, , 大雪, 冬至, 小寒, 大寒 ) 表中元素是字符 抗灾衣被捐赠登记表 按捐赠时间先后 ( 单位, 姓名, 棉被, 棉衣裤, 毛衣裤, 帽类 ) 奥运会各国家队奖牌数统计表 按金牌、银牌、铜牌数多少 ( 国家, 金牌数, 银牌数, 铜牌数 ) 表中元素为记录,2.1 线性表的概念,线性表( Linear List ) 具有相同特性数据元素的有限序列； 可描述为：B=(

2、D, R ) D= ai | i=1, 2, , n ; R= ( ai, ai+1) | i=1, 2, , n-1 ； 也可以简单表示为： B=( a1, a2, , ai, , an ) 表中元素个数 n 表长度， n=0 时称为空表； 结构特性： 元素之间具有线性关系 (元素在位置上有序)； 元素在表中的位置由其序号决定； 表长度可变；,2.1 线性表的概念,二、线性表的抽象数据类型 数据部分： 数据元素，数据元素之间的关系描述； 操作部分： 根据应用需要确定 按照功能可以归纳为以下基本类型： 属性设置：确定类型的基本属性值； 读取属性：读取类型的属性值； 插入：在对象的指定位置加入新的数据元素； 删除：删除对象中的指定数据元素； 查找：在对象查找满足条件的数据元素； 遍历：按某种方式不重复地访问对象中所有数据元素； 关系访问：访问对象中有特定关系的元素；,2.1 线性表的概念,ADT LIST 数据： 线性表 L= ( a0, a1, , an) , n0 ； 操作： void InitList ( *L) ; / 初始化 L指向的线性表 ElemType GetElemli

3、st (*L, int pos ) ; / 得到表中第pos个元素 int FindList ( *L, ElemType item ) ; / 查找给定关键字元素 / 修改表中指定元素 int ModifyList (*L, ElemType item ) ;,2.1 线性表的概念,int InsertList (*L, ElemType item ) ; / 向表中插入元素 int DeleteList (*L, ElemType item ) ; / 删除表中元素 int LenthList (*L) ; / 求表的长度 void SortList (*L) ; / 按关键字值对表元素排序 void TraverseList (*L) ; / 对表进行遍历并输出 void ClearList (*L) ; / 清除表中所有元素 ,2.2 顺序表及其运算,一、什么是顺序表 顺序表线性表的顺序存储（向量式存储） 存储方法: 表中元素按逻辑顺序依次放在连续存储空间中; 每个元素所占存储单元长度相同； 例： 利用数组实现线性表的顺序存储,要求： 数组长度 表长度 表中元素地址计算： AD

4、R( ai )=ADR( a1 ) + ( i -1 )* k k为每个元素所占字节数；,1234 : : n,2.2 顺序表及其运算,二、 顺序表的运算 若对表示顺序表的数组空间采用动态分配， 对顺序表结构作如下定义： #define MaxSize 100 typedef struct ElemType listMaxSize ; / 存储线性表的数组 int len ; / 线性表长度 SeqList ； 数据结构操作的实现与具体的存储结构有关 以下考虑以SeqList为类型的顺序表基本操作（运算）的实现 最基本的操作（运算）：(1) 在表中插入一个元素 (2) 删除表中某个元素,2.2 顺序表及其运算,1. 顺序表初始化 为存储线性表动态分配数组空间，置初始线性表为空 void InitList (SeqList *L ) / 动态分配存储空间 L -List =(ElemType*)malloc(MaxSize*sizeof(ElemType) ； if ( ! L-list ) printf( “ Memory allocation failure ! n“ ) ； exi

5、t (1) ； L-len = 0 ； / 置初始线性表为空 ,2. 顺序表的插入运算 在表中第 i个位置插入一个元素 item 设表长为 len 插入前：A= ( a0, a1, , ai-1, ai, , alen-1 ) 表长为 len 插入后：A= ( a 0, a 1, , a i-1, a i, a i+1, , a len ) 表长为 len+1 表首元素位置不变，表向后增长 ak 0 k i A与A 的关系：a k = item k = i ak-1 i klen 实现算法： 考虑因素： 表长不能超出给定空间上溢处理 若所给插入位置不合理，要处理 正常插入操作后表长应增加1,2.2 顺序表及其运算,2.2 顺序表及其运算,算法描述： void insertlist (SeqList *L, ElemType item, int i ) int j ; if ( L-len =MaxSeze ) / 若表空间满，不能插入 printf (“表满！n“) ； exit (1) ； if ( i L-len-1 ) i = L-len ； for ( j=L-len-1 ;

6、j=i ; j- ) L-list j+1 = L-list j ； L-list i = item ； L-len + + ； ,2.2 顺序表及其运算,算法分析： 时间复杂度： 决定本算法执行时间的主要操作：数据元素移动次数； 设表长为n，表中第i个位置插入，移动元素次数为： n i 设在各位置插入数据元素的概率为Pi ，平均移动次为： 设各位置插入的概率相等，即： Pi = 1/(n+1)，则有： 即：插入一元素的时间复杂度为：O(n) 空间复杂度：原地工作( in place ) 思考：在有序顺序表中插入一个数据元素， 算法？,2.2 顺序表及其运算,3. 顺序表的删除运算 在表中删除第pos个元素 删除前：(b0，b1 ，bi ，bi+1 ，bn-1) 表长为 n ； 删除后：(b0，b1，bi-1，bi+1，bn-2 ) 表长为 n-1 ； 算法考虑：表空( L-len = 0)不能做删除 下溢处理； 指定的删除位置不存在，要处理； 正常删除操作，表长 n 减 1； 算法描述：参考教材 算法分析： 与插入运算类似； 平均时间复杂度： O(n)； 空间复杂度：原地工作 思考：

7、在有序顺序表中删除指定元素， 算法？,2.2 顺序表及其运算,4. 顺序表的查找 从线性表中查找具有给定值的第一个元素 设L为无序表，实现算法： int FindList (SeqList *L , ElemType item) int i ; for ( i= 0; ilen; i+) if ( L-list i = item ) return i ; return -1 ; / -1查找失败标志 思考：若 L为有序表，实现算法？,2.2 顺序表及其运算,算法复杂度： 时间复杂度： 算法运行时间主要由比较元素的次数决定，当查找 元素在表中第 i 个位置时，其比较次数为： i + 1 设表长为 n ，若表中各元素被查找的概率相等，元素值不等， 则查找一个元素的平均比较次数为： 若没有查到所查元素（查找失败）比较次数为：n 即：其时间复杂度为：O(n) 空间复杂度： 原地工作 ( in place ) 其他运算(操作)算法参考教材,2.2 顺序表及其运算,顺序表的主要优点 ： 容易实现 ； 直观、易理解； 顺序表的限制： 对存储空间有要求； 插入、删除操作的效率较低 ；,2.3 栈,一、

8、什么是栈(Stack) 问题1：要求正、逆过程保证严格的相反顺序 例： 进入大沙漠考察与原路返回：,2.3 栈,问题2：多级中断的进入与返回 假设某系统执行时遇有4级中断，其保护各级中断现场与恢复 现场的过程为： (打印机) (磁盘) (采集卡) (电源) 1级中断 2级中断 3级中断 4级中断 保存现场1 保存现场2 保存现场3 a: b: c: end return return return,2.3 栈,为保证中断正确执行，须依次记住每层中断的现场及返回地址； 进入中断 当各层中断“返回”时，则要按记入的相反次序逐个恢复现场继续执行； 中断返回,2.3 栈,从上述表的特点看栈的结构特性： 表中元素有序线性表 元素进入与退出顺序相反特殊性 栈限制插入、删除操作只能在一端进行的特殊线性表 表中允许进行插入、删除操作的一端栈顶， 另一端栈底； 如：( a1，a2，a3，a4，an-1 ) 栈底 栈顶 栈结构特性：栈中元素后进先出 ( LIFO ) 结论：可用于记忆正、逆顺序；,2.3 栈,二、栈的抽象数据类型 ADT Stack 数据： 栈S 以Stack 为存储类型； 操作： void Initstack ( *s) ; / 初始化S指向的栈 void Push ( *s, ElemType item) ; / 元素进栈 ElemType Pop ( *s) ; / 元素退栈 ElemType GetTop ( *s) ; / 读取栈顶元素值 int Emptype Stack ( *s) ; / 判断栈是否空 int FullStack ( *s) ; / 判断栈是否满 void ClearStack ( *s) ; / 清空栈 ,2.3 栈,三、顺序栈 栈的顺序存储顺序栈 最先入栈的元素栈底 最后入栈的元素栈顶 假定：以数组 stack MaxSize 存储栈， 数组空间采用动态分配； 用 top 指示栈顶位置， 定义顺序栈 SeqStack 的结构类型为： #define MaxSize 100 typedef struct ElemType stackMaxSiz

《数据结构与算法教程 教学课件 ppt 作者 朱明方 吴及 第2章 顺序表及其运算》由会员E****分享，可在线阅读，更多相关《数据结构与算法教程 教学课件 ppt 作者 朱明方 吴及 第2章 顺序表及其运算》请在金锄头文库上搜索。