《数据结构》 (计科、电信专业) ? DGZ.SWFU Data Structure 计算机的应用: 数值计算:如进制转换、求圆面积、体积、求解一元二次方程的解等 非数值计算:控制、管理、数据处理等方面 ——相对来说比较复杂:历史、现状、未来;直觉、灵感、发散性思维 ——只要是人脑能解决的,就能通过编程得出和人相同的结果. ? DGZ.SWFU Data Structure 程序=算法+数据结构+语言+程序设计方法 《数据结构》: 研究数据的逻辑结构、物理结构及其操作的学科. 算法是灵魂,数据结构是加工对象,语言是工具,编程需采用合适的方法.而算法在很大程度上受到加工对象即数据结构的限制,甚至在某些情况下数据结构起决定性的作用. ? DGZ.SWFU Data Structure 第一章 绪论 1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1 算法1.4.2 算法设计的要求1.4.3 算法效率的度量1.4.4 算法的存储空间需求 ? DGZ.SWFU Data Structure 一、教学目的与要求 了解数据结构的基本概念,认识算法和算法分析;初步学会对空间复杂度和时间复杂度进行估算二、主要教学内容 数据结构的基本概念和相关术语;抽象数据类型的表示与实现;算法和算法分析;算法效率的度量;算法的存储空间的需求三、教学重点、难点 数据结构、算法和算法分析、空间复杂度、时间复杂度四、授课方法及手段 采用多媒体大屏幕投影授课五、讲课具体内容(讲稿) ? DGZ.SWFU Data Structure 什么是数据结构 计算机解决问题的步骤 实际问题 工程师 数学模型 数学家 算法 程序员 程序 结果 数据结构——研究计算机的操作对象(数据)以及它们之间的关系和操作等的学科. ? DGZ.SWFU Data Structure 《数据结构》的地位——综合性的专业基础课 ? DGZ.SWFU Data Structure 基本概念和术语 数据:计算机程序处理的符号的总称.数据元素:数据的基本单位.通常作为一个整体进行处理.数据项:数据的不可分割的最小单位.一个数据元素可以由若干个数据项构成.数据对象:性质相同的数据元素的集合.数据结构:相互间存在一种或多种关系的数据元素的集合. ? DGZ.SWFU Data Structure 例:图书信息表 登录号 书名 作者 出版社 定价(元) 00001 C++语言基础教程 徐孝凯 清华大学 26.00 00002 计算机辅助制造 李德庆 机械工业 3.30 00003 计算机系统原理 张基温 电子工业 25.00 00004 数据结构 严蔚敏 清华大学 28.00 数据项 数据元素 数据对象 ? DGZ.SWFU Data Structure 数据的结构 逻辑结构: 数据元素之间的逻辑关系物理结构: 数据结构在计算机中的表示,又称存储结构 算法的设计取决于选定的逻辑结构 算法的实现依赖于采用的存储结构 ? DGZ.SWFU Data Structure 逻辑结构: (1) 线性结构 结点之间关系:一对一 特点:开始结点和终端结点都是惟一的,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱结点,有且仅有一个后继结点. "队列"就是典型的线性结构. … ? DGZ.SWFU Data Structure (2) 树形结构 结点之间关系:一对多. 特点:开始结点惟一,终端结点不惟一.除终端结点以外,每个结点有一个或多个后续结点;除开始结点外,每个结点有且仅有一个前驱结点. 如:西南林业大学学科专业图 ? DGZ.SWFU Data Structure (3) 图形结构 结点之间关系:多对多. 特点:没有开始结点和终端结点,所有结点都可能有多个前驱结点和多个后继结点. 如:昆明市公交车站点图 ? DGZ.SWFU Data Structure 逻辑结构的表示 例1:有一种数据结构B1=(D,S),其中,D={1,5,8,12,20,26,34},S={s}s={<1,8>,<8,34>,<34,20>,<20,12>12,26>,<26,5>},画出其逻辑结构表示 ? DGZ.SWFU Data Structure 逻辑结构的表示 例2:有一种数据结构B2=(D,S), 其中, D={a,b,c,d,e,f,g,h,i,j} S={s} s={,, b,e>, ,d,h>, , },画出其逻辑结构表示. ? DGZ.SWFU Data Structure (1)集合(离散点)(2)线性结构(一对一)(3)树形结构(一对多)(4)图状结构或网状结构(多对多) 第二章 线性表第三章 栈和队列第四章 串第五章 数组和广义表 :第六章 树和二叉树 ——数据结构中不讨论 :第七章 图 本书结构—数据结构部分 ? DGZ.SWFU Data Structure 物理结构 (1)顺序存储结构:所有存储结点相继存放在一个连续的存储区中.用存储结点间的位置关系表示数据元素之间的逻辑关系.(2)链式存储结构:通过在结点上附加一个指针域来表示结点间的逻辑关系,每个指针指向一个与本结点有逻辑关系的结点.(3)索引存储结构(4)散列存储结构 ? DGZ.SWFU Data Structure 顺序存储:链式存储: ? DGZ.SWFU Data Structure 算法和算法分析 算法(Algorithm):对特定问题求解步骤的描述.算法的五个重要特性:(1)有穷性:算法必须在执行有穷步之后结束,每一步都可在有穷时间内完成.(2)确定性:对相同的输入只能得出相同的输出(3)可行性:算法所描述的操作都是可实现的(4)输入:0个或多个输入(5)输出:1个或多个输出 ? DGZ.SWFU Data Structure 算法描述 用文字描述用流程图描述用一种程序设计语言描述…… 算法描述 例:欧几里德算法——辗转相除法求两个自然数 m 和n的最大公约数 ? DGZ.SWFU Data Structure 欧几里德算法(有穷性、确定性、可行性) m n r 算法描述(一)——自然语言 优点:容易理解缺点:冗长、二义性使用方法:粗线条描述算法思想 注意事项:避免写成自然段 ? DGZ.SWFU Data Structure 步骤1:将m除以n得到余数r;步骤2:若r等于0,则n为最大公约数,算法结束;否则执行步骤3;步骤3:将n的值放在m中,将r的值放在n中,重新执行步骤1; 算法描述(二)——流程图 ? DGZ.SWFU Data Structure 优点:流程直观 缺点:缺少严密性、灵活性使用方法:描述简单算法注意事项:注意抽象层次 N 开始 输入m和n r=m % n r=0 m=n;n=r 输出n 结束 Y 算法描述(三)——程序设计语言 ? DGZ.SWFU Data Structure 优点:能由计算机执行 缺点:抽象性差,对语言要求高使用方法:算法需要验证注意事项:将算法写成子函数 #include int CommonFactor(int m, int n){ int r = m % n; while (r != 0)m = n; n = r; r = m % n;return n;}void main( ){ cout< 数据关系:<数据关系的定义> 基本操作:<基本操作的定义>}ADT 抽象的数据类型名基本操作的定义格式为: 基本操作名(参数表) 初始条件:<初始条件描述> 操作结果:<操作结果描述> ? DGZ.SWFU Data Structure 抽象数据类型三元组的定义举例 ADT Triplet{ 数据对象:D = {e1,e2,e3 | e1,e2,e3属于Elemset(定义了关系的某个集合)} 数据关系:R1 = {|} 基本操作:InitTriplet(&T,v1,v2,v3) 初始条件: 无 操作结果: 构造三元组T,元素e1,e2和e3分别被赋予参数v1,v2和v3的值. ? DGZ.SWFU Data Structure 抽象数据类型三元组的定义举例 DestroyTriplet(&T) 初始条件: 三元组T已经存在. 操作结果: 销毁三元组T.Get(T,i,&e) 初始条件: 三元组T已经存在,1<=i<=3. 操作结果: 用e返回三元组T的第i个元素.Put(&T,i,e) 初始条件: 三元组T已经存在,1<=i<=3. 操作结果: 用e值取代三元组T的第i个元素. ? DGZ.SWFU Data Structure 抽象数据类型三元组的定义举例 IsAscending(T) 初始条件: 三元组T已经存在. 操作结果: 如果三元组T的三个元素按升序排列,则返回TRUE; 否则返回FALSE.IsDescending(T) 初始条件: 三元组T已经存在. 操作结果: 如果三元组T的三个元素按降序排列,则返回TRUE; 否则返回FALSE. ? DGZ.SWFU Data Structure 抽象数据类型三元组的定义举例 Max(T,&e) 初始条件: 三元组T已经存在. 操作结果: 用e返回三元组T的最大值.Min(T,&e) 初始条件: 三元组T已经存在. 操作结果: 用e返回三元组T的最小值.}ADT Triplet ? DGZ.SWFU Data Structure 抽象数据类型的表示与实现 类C语言(作了扩充和修改)的表示如:预定义常量和类型 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 typedef int Status其它:P10-11 ? DGZ.SWFU Data Structure 三元组基本操作实现——举例 Status Get(Triple T, int i, Elemtype *e)// 初始条件: 三元组T已经存在.// 操作结果: 用e返回三元组T的第i个元素.if (i<1 || i>3) return ERROR;e=T[i-1]; return OK;} ? DGZ.SWFU Data Structure 算法评价 算法评价的目的:从解决问题的不同算法中选择出较为合适的一种;对现有算法进行改进,从而设计出更好的算法 ? DGZ.SWFU Data Structure (1)正确性层次a:程序不含语法错误;层次b:程序对于几组输入数据能得出满足要求的结果;层次c:程序对于精心选择的典型、苛刻的几组输入数据能够得出满足规格说明要求的结果;层次d:程序对于一切合法的输入数据都能产生满足规格说明要求的结果.(2)可读性(3)健壮性(4)高效率与低存贮量 算法应达到的目标 ? DGZ.SWFU Data Structure 算法效率的度量 (1)事后统计法 例:algo1-1、algo1-2 缺点:必须先运行依据算法编制的程序;所得时间的统计量依赖于计算机的硬件、软件等环境因素,有时容易掩盖算法本身的优劣. ? DGZ.SWFU Data Structure algo1-1.cpp:计算1-1/x+1/x*x… #include #include void main() { struct timeb t1,t2; long t; double x,sum=1,sum1; int i,j,n; printf("请输入x n:"); scanf("%lf%d",&x,&n); ftime(&t1)求得当前时间 */ ? DGZ.SWFU Data Structure algo1-1.cpp: for(i=1;i<=n;i+sum1=1; for(j=1;j<=i;j+sum1=-sum1/x; sum+=sum1; } ftime(&t2)求得当前时间 t=(t2.time-t1.time)*1000+ (t2.millitm-t1.millitm)计算时间差printf("sum=%lf 用时%ld毫秒\n",sum,t);} ? DGZ.SWFU Data Structure algo1-2.cpp(改进算法): sum1=1;for(i=1;i<=n;i+sum1=-sum1/x; sum+=sum1; } 运行以上两个程序,比较当n增长时,两个程序的运行时间的差别. 将前一程序的黄色部分修改为: ? DGZ.SWFU Data Structure 算法效率的度量 (2)事前分析估算法 通常把算法中包含简单操作次数的多少叫做算法的时间复杂度,用它来衡量一个算法的运行时间性能或称计算性能.它是问题规模n的某个函数f(n):T(n) = O(f(n)) ? DGZ.SWFU Data Structure 算法评价 【例】分析以下程序段的时间复杂度 for (i=0; i1&&change; --i)change = false;for (j= 0; j a[j+1]) { a[j] ←→a[j+1]change=TURE;bubble_sort 算法评价 ? DGZ.SWFU Data Structure 算法的存储空间需求 算法的存储量:包括输入数据所占空间、程序本身所占空间和辅助变量所占空间.空间复杂度:通常指辅助变量所占空间,是对一个算法在运行过程中临时占用的存储空间大小的量度.