c语言线性表知识全解.pptVIP

2000年1月25日 北京理工大学 / 第一章 绪论 小结 理解数据结构、逻辑结构(分类)、存储结构、顺序映像、顺序存储结构、链式映像、链式存储结构、抽象数据类型等 掌握抽象数据类型的定义和实现方法 理解算法的特性(“有穷”性、确定性、可行性、输入、输出性)，区分算法与程序 理解时间复杂度的概念，会计算语句频度和时间复杂度。理解时间复杂度反映的是算法运行时间随问题规模的增长率T(n)=O(f(n)) 推荐习题：4 8 9 10（11 17 20） 课后习题答案：课件+ftp学习资料 作业说明 1、有理数类型的ADT描述与C语言实现 实现—通用准备阶段 实现—具体元素类型与存储结构定义 实现—基本操作实现 实现—基本操作实现 实现—基本操作实现 时间复杂度计算举例 时间复杂度应用举例 两10*10矩阵相乘，执行时间为12ms，已知算法的时间复杂度为T(n)=O(n3),估算31*31的矩阵相乘所需时间 解：考虑到时间复杂度近似与算法执行时间的增长率，故所求为 (31/10)3*12ms≈358ms 算法存储空间需求 存储资源:输入数据+程序本身+辅助空间 空间复杂度:S(n)=O(f(n)) 作业2 计算算法的时间复杂度及count的值 int Time(int n){ count=0;x=2; while(xn/2) { x*=2; count++； } return(count); }//Time /*分析与验证相结合,count:log2n-2,T(n)=O(logn)*/ /*说明：注意复杂度与频度函数的区别与联系*/ 第2—3章 线性结构及线性表、栈和队列 引:三元组或者复数都是在线性结构上进行一些简单访问操作，还有很多不同的问题也类似。为复用有必要进行抽象，将线性结构及其上常见的操作定义为一个基本的普遍适用的ADT 逻辑结构+操作集---抽象数据类型 线性结构+操作集1—线性表 线性结构+操作集2—栈 线性结构+操作集3—队列 线性结构：若干元素按类似a1,a2, a2,a3…, an-1, an的一对一关系构成的有限序列。 存在唯一的被称作“第一个”的数据元素 存在唯一的被称作“最后一个”的数据元素 除第一个外，每个元素都有唯一的“前驱” 除最后一个外，每个元素都有唯一的“后继” 思考:R={a,b,b,c,c,a}是否构成线性结构？ 第二章 线性表 线性表的抽象数据类型定义 线性表的顺序表示和实现 线性表的链式表示和实现 线性表的应用--一元多项式表示及相加 §2.1 线性表的抽象数据类型定义 ADT List{ 数据对象:ai|ai∈ElemSet，i=1,2,…,n,n=0) 数据关系:R={ai-1,ai|ai-1,ai∈D,i=1,2,,n-1}。 线性表也可表示作 (a1,a2,…,an)，n为表 长,n=0时线性表称为空表 基本操作： InitList(L); 操作结果：构造一个空表L DestroyList(L); 初始条件:线性表L已存在 操作结果：销毁线性表L 加工型操作:改变线性表结构的操作,参数Ｌ应采用引用传递方式 ClearList(L)// 将有效元素个数置0, //销毁释放全部空间，清空不然 ListInsert(L,i,e)//注意初始条件及表长改变 //1≤i≤ListLength(L)+1;表长加1 ListDelete(L,i,e)//注意初始条件及表长 //1≤i≤ListLength(L);L与e均引用参数;表长减1 引用型操作:不改变线性表结构的操作 ListEmpty(L) ListLength(L) GetElem(L,i,e) LocateElem(L,e,compare()) //函数作参数,且返回值为位序，找不到则返回0 PriorElem(L,cur_e,pre_e) NextElem(L,cur_e,next_e) ListTraverse(L,visit())//常用以输出链表 例2-1:设计算法求A=A∪B;集合用线性表表示 例2-2 La与Lb中元素非降,归并为线性表Lc §2.2 线性表的顺序表示和实现 1 顺序表:借助元素在存储器中位置上的”相邻”关系表示数据元素间具有的关系，如此存储的线性表称为顺序表. 说明：顺序表各元素存储在