数据结构课件第01章.ppt

数据结构(C语言版) Data Structure,主讲教师 马宁 计算机科学学院 软件工程教研室,学习的直接收益,编程基础 计算机专业考研课程 计算机等级考试课程 软件资格与水平考试课程 进入优秀企业的敲门砖 盖茨说：学通了这本书（程序设计技巧，共三卷，其中第一卷主要为数据结构）来找我吧！,请同学们重视本课程的学习。,总学时：64 学时 讲课学时：48 学时 实验学时：16 学时 教材： 数据结构（ C语言版）严蔚敏、吴伟民 -清华大学出版社,课程安排,参考书目,计算机及软件技术丛书 现代计算机常用数据结构和算法 潘金贵 编著 南京大学出版社 数据结构习题与解析（C语言篇）修订版 李春葆 主编 计算机专业教学辅导丛书 清华大学出版社,程序设计课程与数据结构课程的关系,程序设计强调程序设计的基本概念和做法，如： 数据类型与表达式 程序流程控制 子程序 递归 数据抽象，等 数据结构强调程序设计思想和技术的典型应用，如： 线性表、栈、队列 检索、排序 图、树，等 两者的内容又有交叉,本课程的体系结构,第一章 绪论 介绍数据、数据结构和抽象数据类型的概念。 第二章 第七章 基本数据结构 从抽象数据类型的角度， 分别讨论线性表、栈和队列、 串、数组和广义表、 树、图等基本数据结构及其应用。,1.1 数据结构学科的研究对象 什么是程序、软件？ N.沃思（Niklaus Wirth)教授提出： 程序=算法+数据结构 以上公式说明了如下两个问题： （1）数据上的算法决定如何构造和组织数据 （算法数据结构） （2）算法的选择依赖于作为基础的数据结构 （数据结构算法） 软件=程序+文档（软件工程的观点）,第一章 绪论,2. 电子计算机的主要用途 早期： 主要用于数值计算。 后来： 应用逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。 数据复杂数据结构,例1、电话号码查询问题 查找 ：给出一个姓名，如果存在，打印此人的电话号码； 如果不存在，报告没有这个人的标志。 （1）按顺序存储方式：须遍历表 （2）按姓氏索引方式：索引 要写出好的查找算法，取决于这张表的结构及存储方式。 电话号码表的结构和存储方式决定了查找（算法）的效率。,4. 非数值计算问题举例,书目文件,例2 书目自动检索系统,例3 人机对奕问题,例4 多叉路口交通灯管理问题,求解非数值计算的问题 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？ 数据结构的研究对象是：非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。,5. 数据结构课程的形成和发展 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。,6.数据结构课程所处的地位,1.2 基本概念和术语 1. 数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2. 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。 数据项是数据的不可分割的最小单位。 3. 数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。,4. 数据类型(Data Type)：在一种程序设计语言中，变量所具有的数据种类。 例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 例2、在C语言中 数据类型：基本类型、指针类型、空类型和结构类型 其中，基本类型包括整型、浮点型、字符型和枚举类型,5. 抽象数据类型(Abstract Data Type简称ADT） 抽象数据类型是用户在数据类型基础上新定义的数据类型 抽象数据类型定义包括数据组成和对数据的处理操作 抽象数据类型是数据和数据的使用者的一个接口 抽象数据类型的三元组表示 （D，S，P） D：数据对象 S：D上的关系集 P：对D的基本操作 ADT的作用结构与用户无关，提高代码的复用率,抽象数据类型的定义：包括数据对象定义、数据关系定义和基本操作定义，书写格式为： ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据逻辑关系的定义 基本操作：基本操作的定义 P 8 倒数7行 ADT 抽象数据类型名 （P9 例 1-6 伪码描述） P 8 倒数4行,C+的引用类型,引用类型用于给一个变量取一个别名。例如： int x=0; int /结果为：1,1 在语法上，对引用类型变量的访问与非引用类型相同；但在语义上，对引用类型变量的访问实际访问的是另一个变量（被引用的变量）。,引用类型作为函数的参数类型,#include using namespace std; void swap(int ,指针类型作为函数的参数类型,#include void swap(int *p1, int *p2) int t; t = *p1; *p1 = *p2; *p2 = t; void main() int a=0,b=1; cout a , b endl; /结果为：0,1 swap( /结果为：1,0 ,void f(int *p) *p = 1; p+; /OK *p = 2; /危险! void g(int /b为2，a和c的值未被改变。 ,6. 数据结构(Data Structure) 定义1- 是相互之间存在一种或多种特定关系的数据元素的集合。 Data_Structure = (D,S) D：数据对象 ，S：D上的关系集 定义2- 按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一组运算的集合。,1.3 数据结构的三个方面的含义 逻辑结构- 数据元素间抽象化的相互关系（简称为数据结构）。 与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。 存储结构（物理结构）- 数据元素及其关系在计算机存储器中的存储方式。 是逻辑结构用计算机语言的实现，它依赖于计算机语言。 运算（算法）,1. 逻辑结构 逻辑结构-划分方法一 （1）线性结构- 有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。 例如：线性表、栈、队列、串 （2）非线性结构- 一个结点可能有多个直接前趋和直接后继。 例如：树、图、多维数组、广义表等。,（集合）数据元素间除“同属于一个集合”外，无其它关系 线性结构一个对一个，如线性表、栈、队列 树形结构一个对多个，如树 图状结构多个对多个，如图,逻辑结构-划分方法二,2. 存储结构 存储结构两方面的内容： （1）数据元素自身值的表示（数据域） （2）该结点与其它结点关系的域（链域） 四种基本的存储方法： （1）顺序存储方法（顺序存储结构一维数组） （2）链接存储方法（链式存储结构指针，游标） （3）索引存储方法 （4）散列存储方法 同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。,3. 算法 什么是算法？ 所谓算法(Algorithm) 是指令的有限序列。 是对特定问题求解步骤的一种描述（解题方法） 其中每条指令表示一个或多个操作步骤,算法的五个重要特性 （1）有穷性-执行了有限条指令后一定要终止。 例5、例6 （2）确定性（无二义）-算法的每一步操作都必须有确切定义，不得有任何歧义性。 （3）可（能）行性-算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。 （4）输入数据-一个算法有n (n=0)个初始数据的输入。 （5）输出数据-一个算法有一个或多个的有效信息的输出。,例5 一个不是算法的例子 (1)begin (2)n=0 (3)n=n+1 (4)repeat (3) (5)end,例6 一个不超过100次计数的算法 (1)begin (2)n=0 (3)n=n+1 (4)if n=100 do (5) else repeat(3) (5)output n (6)end,返回,算法的描述和实现 描述-可采用自然语言、数学语言或约定的符号语言。 实现-必须借助程序设计语言提供的数据类型及其运算。 本课的描述-采用类C语言 （P9-13 1.3 课后仔细阅读） 思考：算法与程序有何区别？,算法设计的要求 正确性、可读性、健壮性、高效率与低存储量需求 程序正确性的四个层面： （1）不含语法错误 （2）程序对于n组输入数据能够得出满足规格说明要求的结果 （3）程序对于精心选择的典型、边界性的n组输入数据能得出满足规格说明要求的结果 （4）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举） 算法的效率指算法的执行时间，也称作算法的时间复杂度 算法的存储量需求指算法执行过程中所需的最大存储空间，也称作算法的空间复杂度,算法效率的度量 程序运行所耗费的时间（由下列因素决定）： 算法所选用的策略 问题的规模算法求解问题的输入量（或初始数据量） 书写程序所采用的语言 编译程序所产生的机器代码的质量 机器执行指令的速度 一个算法耗费的时间=算法中每条语句的执行时间之和 若不考虑机器硬、软件因素，可以认为算法“运行工作量”的大小是问题规模的函数。,设：执行每条语句所需时间为单位时间，则： 一个算法的时间耗费：f(n)=所有语句的频度之和 其中， n 为问题的规模 渐近时间复杂度(Asymptotic Time Complexity)： O(f(n) 随问题的规模n的增大， f(n)的增长和f(n) 的数量级（阶） O(f(n)的增长率相同。 时间复杂度：T(n)= O(f(n),算法效率的度量：采用时间复杂度,例7 分析以下程序段的时间复杂度 for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+) x+; ,/* 1 * /,/* 2 * /,频度:指的是该语句重复执行的次数。 一个算法中所有语句的频度之和构成了该算法的运行时间。 语句1的频度是：n-1 语句2的频度是：,时间耗费：f(n)=2n2-2 时间复杂度：T(n)=O(n2),例8 分析以下程序段的时间复杂度 i=1; while (i=n) i=i*2 语句1的频度是：1 设语句2的频度是f(n)，则有： 即 ，取最大值 则该程序段的时间复杂度为：,/* 1 * /,/* 2 * /,例9 x=1; for (i=1;i=n;i+) for (j=1;j=i;j+) for (k=1;k=j;k+) x+; 由于内循环的执行次数虽与规模n无直接关系，但与外循环的变量取值有关。因此从内层向外层循环分析执行次数。,即: T(n)=n(n+1)(2n+1)/6+n(n+1)/2/2 所以： T(n)=O(n3/6+低次项) 取T(n)的数量级阶，得最后结果为： T(n)=O(n3) 当n时，即n足够大时, 常见函数的时间复杂度按数量级递增排列 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) k次方阶O(nk) 2的指数阶O(2n) 阶乘O(n!) n的指数阶O(nn),当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。,有的情况下，算法中基本操作重复执行的次数 还随问题的输入数据集不同而不同。例如： void bubble-sort(int a ，int n) /冒泡排序的算法 for(I=n-1,change=TURE;I=1 最好情况：0次,最坏情况：1+2+3+n-1 =n(n-1)/2 平均时间复