《数据结构课件全套版 第一章绪论（无答案）》由会员分享，可在线阅读，更多相关《数据结构课件全套版 第一章绪论（无答案）（24页珍藏版）》请在金锄头文库上搜索。
1、上页 下页节末页结束回顾：u知识点：链表的结构(头结点 )、定义与操作u作业：思考+对比+总结 房浩 马纳u每次作业加一个总结,写明算法设计和测试过程中出现的问题以及后续注意事项，没有就写一次通过u图书表存储及基本操作u自定义类型Book为: 结构体类型书号+书名u自定义类型ElemType为:Book（好处?）u自定义类型LinkList:数据域为ElemType类型的单链表u实现如下函数: ListCreate_L ListPrint_L ListDelete_Lu编写主函数对上述函数进行测试a完整的可运行的程序，注意编码规范和注释b体会与作业1程序的异同n普通的“表”既可用数组来存储，也
2、可以用链表来存储，具体依赖于需要进行的操作种类！上页 下页节末页结束主讲：鲁法明fm_上页 下页节末页结束第一章 绪论l什么是数据结构基本概念和术语n抽象数据类型的表示和实现 算法及其效率度量上页 下页节末页结束l数据(对象):性质相同的数据元素的集合,计算机处理对象l结构:指数据对象的内在结构，或者说数据对象各元素根据相互关系形成的结构.如成绩表 (线性)、文件系统(树型)l数据结构:主要研究非数值计算问题中计算机的操作对象有哪些结构(逻辑结构)、这些结构在计算机中的表示及其操作的定义和实现问题。l学习目标：重点掌握掌握各常见逻辑结构及其操作(ADT)的定义和实现，具体问题中会选择适合的抽象
3、数据类型更好地解决问题l参考书：数据结构与问题求解（Java版）,电子工业出版社+数据结构18001.1 什么是“数据 结构”上页 下页节末页结束1.2 基本概念和术语1、逻辑结构：不考虑实现，仅看问题域中数据元素根据相互间的逻辑关系形成的结构称为数据结构的逻辑结构。通常说的数据结构即此义l分类：如书目表根据 一对一相邻关系形成线性结构、组织机构间根据上下级关系(一对多)形成一个树形数据结构,城市间据通路(多对多)形成图状结构,此外还有集合结构(除同属一个集合外，无其它关联),共四类l形式化定义：Data_Structure=(D,S),其中D数据对象，即元素的有限集,S:集合D上关系的有限集
4、书目1书目n计算机具体求解时,逻辑结构(数据元素及相互关系）需在计算机中加以表示,这称为数据结构的物理结构上页 下页节末页结束逻辑结构(数据元素及关系/结构)在计算机中的表示或者说映像称为该数据结构的物理结构或存储结构数据元素的表示:二进制编码串,称为元素或结点,可用高级语言的数据类型加以定义关系的表示：如 ，可用a与b在存储器中位置上的”相邻”(a前b后)来表示两者之间的关系，也可在a对应的结点中附加一个指针指向b来表示两者之间的关系。前者称作关系的顺序映像，后者称为关系的链式映像2、物理结构(存储结构)ab上页 下页节末页结束(1)顺序存储结构:关系采取顺序映像表示,即借助元素在存储器中的
5、位置上的”相邻”关系隐式表示数据元素间具有关系。此时物理结构对应一个数组 优点:可根据起始地址随机访问各元素 缺点:需事先分配一足够大空间，且插入删除结点需移动大量数据(2)链式存储结构:关系采取链式映像表示,即借助附加信息指针显式表示元素间的关系,对应一个链表 优点是更有效利用空间、插入或者删除结点快,但要顺序访问各元素c1c2物理结构 (存储结构)分类 面向问题域，数据结构除了考虑逻辑结构外，还要考虑其上要进行的操作，两者合称为“抽象数据类型” 面向具体实现，要根据需要进行的操作选择存储结构，若元素个数固定不变只进行元素的遍历或访问则应采取顺序存储;若经常进行元素的插入或删除则通常采用链式
6、存储结构。总之要使“算法效率”尽量高上页 下页节末页结束3、抽象数据类型ADT List 数据对象:ai|aiElemSet，i=1,2,n,n=0) 数据关系:R=|ai-1,aiD,i=1,2,n-1。线性表也可表示作 (a1,a2,an)，n为表 长,n=0时线性表称为空表 基本操作： InitList(&L); 操作结果：构造一个空表L DestroyList(&L); 初始条件:线性表L已存在 操作结果：销毁线性表L ListCreate() 上页 下页节末页结束抽象数据类型指一个数据结构(逻辑结构)及其上的操作(数据运算)ADT= (D,S,P)。定义方式如下： Complex 数
7、据对象：D=e1,e2|e1,e2RealSet 数据关系：R=|e1表示实部，e2表示虚部 基本操作： InitComplex(&Z,v1,v2) /*Z为引用参数，带回操作结果*/ 操作结果:构造一个实部和虚部为v1、v2的复数,用Z带回 DestroyComplex(&Z) /*Z为引用参数，操作中被修改*/ 操作结果：撤销复数Z GetReal(Z,&realPart) /GetImag操作略 初始条件：复数Z存在 操作结果：用realPart带回复数Z实部的值 AddComplex(z1,z2,&sum) /Substract,Multiply等操作略 初始条件：z1与z2是复数 操
8、作结果：用sum带回z1与z2的和 Complex3、抽象数据类型ADTADT抽象数据类型名、方法名等要见名知意，命名规范莫忘初始条件和操作结果描述抽象数据类型定义用于接口说明,不牵扯具体实现上页 下页节末页结束ADT Triplet 数据对象：D=e1,e2,e3|e1,e2,e3ElemType 数据关系：R=, 基本操作： Status InitTriplet(Triplet &T,v1,v2,v3) 操作结果:构造元素值依次为v1、v2、v3的三元组,用T带回 DestroyTriplet (&Z) 操作结果：撤销三元组T Get(T,i,&e) 初始条件：三元组T存在，1 i3 操作
9、结果：用e带回T的第i元的值 IsAscending(T) /IsDescending操作略 初始条件：三元组T已经存在 操作结果：若三个元素按升序排列返回1，否则返回0 Max(T,&e) /Min操作省略 初始条件：三元组T已经存在 操作结果：用e返回三个元素中的最大值ADT Triplet抽象数据类型Triplet的定义上页 下页节末页结束1.3抽象数据类型的实现/头文件包含#include#include#include/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE
10、-1#define OVERFLOW -2/Status等同int,特指函数返回一种状态typedef int Status; 说明：源程序文件扩展名必须为cpp，否则无法使用引用型参数#define定义符号常量,见名知意,一改全改,后无分号typedef声明一种新类型名来代替已有类型名,见名知意函数状态码定义部分编程时需写入源码，写算法时可略上页 下页节末页结束根据定义，线性结构且元素个数固定,无插入删除,用顺序存储采用顺序存储的抽象数据类型“三元组”实际就是基类型double的含3个元素的数组类型.数组类型有两种：静态分配数组如ElemType a3;动态分配数组如ElemType *a;
11、因动态数组更灵活,可自由开辟释放存储空间及更改容量,故顺序存储常用动态数组, double * t.不好理解？给doulbe * 起个别名三元组类型Triplet实现:存储结构定义/-采用动态分配的“顺序”存储结构typedef double ElemType; /自定义元素类型ElemTypetypedef ElemType* Triplet; /自定义Triplet类型上页 下页节末页结束 Status InitTriplet(Triplet &T,ElemType v1, ElemType v2,ElemType v3)/构造三元组T，元素e1,e2,e3分别赋值v1、v2、v3 T=(
12、ElemType *)malloc(3*sizeof(ElemType); /malloc.h if(T=NULL) exit(OVERFLOW) /分配存储空间失败,异常结束进程,stdlib.h T0=v1,T1=v2;T2=v3; return(OK); /InitTripletStatus DestroyTriplet (Triplet &T)/销毁三元组T free(T); /只标明该存储区域可被再次分配，T仍然指向该空间,后常跟T=NULL; T=NULL; return(OK);/DestroyTripletStatus Get (Triplet T, int i,ElemTyp
13、e &e)/1 i3,用e返回T的第i元的值 if(i3)return(error); e=Ti-1; return OK;/GetIsAscending IsDescending Max MinTriplet类型实现:基本操作的实现上页 下页节末页结束作业1：l试定义有理数抽象数据类型，并给出其具体实现(给出存储结构定义和初始化、销毁、输出和加法操作的实现)。l分析：有理数本质是一个整数对(m,n)；前者是分子，后者是分母，且分母不为0. 有理数的操作包括初始化、销毁以及加减乘除。注意选择合适的存储结构，实现时注意通分lStatus InitRational(Rational &Q,Elem
14、Type v1, ElemType v2)lvoid DestroyRational(Rational &Q);lvoid OutputRational (Rational Q);lStatus RationalAdd(Rational Q1,Rational Q2，Rational &Sum)lvoid main()：Rational Q1,Q2,Q;l if( OK=InitRational(Q1,2,3)lif( OK=InitRational(Q2,3,4) )l if( OK=RationalAdd(Q1,Q2,Q)l OutputRational (Q);l上页 下页节末页结束1.
15、4 算法和算法分析1、算法与程序的区别算法是对求解步骤的描述，是指令的有限序列，是写给人看的，不是被编译器编译执行的，故一个指令可表示多个操作；而程序是由某种编程语言编写的代码，需要编译执行，必须是机器可理解的.如在算法中可用a0.4=b5.9,而程序不可算法满足“有穷”性、确定性、可行性、输入、输出等特性，而程序不一定满足有穷性，如操作系统程序算法代表了对问题的解决方案，而程序则是算法在计算机上的特定的实现上页 下页节末页结束2、算法效率的度量频度函数与增长率度量指标:算法运行时间主要取决于基本操作的执行次数(频度)，执行次数通常随问题规模扩大而增加, 增加越快意味着算法随问题规模的扩大,运
16、行时间增长的也快,从而该种算法效果较差;增长越慢算法越好.故可用基本操作的频度随问题规模的增长率反映算法的效率。例：输入n,判断n是否为素数算法1: isPrime=TRUE; for(i=2;in;i+) if(n%i=0) isPrim=FALSE 算法2: isPrime=TURE;for(i=2;i=sqrt(n);i+) if(n%i=0) isPrim=FALSE;F(n)=n-2F(n)=sqrt(n)-1上页 下页节末页结束2、算法效率的度量时间复杂度时间复杂度：频度函数的增长率随着n的增长趋近于函数中“关键项”(去掉低次项和常数项)的增长率，故可用“关键项” 反映算法效率。假设关键项为f(n)，用T(n)=O(f(n)表示算法时间增长率与f(n)增长率同阶.称O(f(n)为算法的渐近时间复杂度，简称时间复杂度算法1: for(isPrime=TRUE,i=2;in;i+) if(n%i=0) isPrime=FALSE;算法2: for(isPrime=TRUE,i=2;i=sqrt(n);i+) if(n%i=0) isPrime=FALSE;F(n)=n-2; f
