数据结构简介.ppt

1、数据结构与算法Data Structures and Algorithms,乔 海燕 电话Email : ,课程安排,理论： 3课时/周 + 作业 实验：课时/两周 + 作业 总成绩：平时40%(包括听课 、作业 、实验 、 期中） + 期末60% 教学用书： 数据结构(C语言版），严蔚敏、吴伟民，清华大学出版社，1997年 参考书： 1数据结构，许卓群，张乃孝，杨冬青，唐世渭，高等教育出版社，1987年 2A Practical Introduction to Data Structures and Algorithm Analysis. Clifford A.

2、Shaffer 电子工业出版社2002。,什么是数据结构？,什么是数据结构？ 为什么学习数据结构？达到什么目的？ 应该掌握哪些内容？技能？ 如何学习？,从电话号码查询说起,问题：你有一叠亲友和客户等的名片，需要在其中查找某个人的卡片。,解法1：顺序查找 卡片组织：顺序（线性逻辑结构）,如何组织数据（逻辑关系）以便实现数据上的处理,从电话号码查询说起,解法1的实现(1)： 使用数组存储卡片；,如何用C/C+表示数据，即数据的存储结构,用C+表示： struct Card string name; string phone; ; Card phones100;,从电话号码查询说起,解法1的实现(1

3、)： 算法的实现；,如何用C/C+实现算法（如查找）,int sequentialSearch(Card st, int n, string const ,用C+表示： struct Card string name; string phone; ;,从电话号码查询说起,解法1的实现(2)： 使用链表存储卡片；,如何设计/选择存储数据的方式（存储结构）便于数据上操作（如查找）的实现,用C+表示： struct Node Card data; Node * next; ; Node *head;,从电话号码查询说起,解法1的实现(2)： 使用链表存储卡片；,如何评价以上两种实现? 掌握评价算法的

4、基本技能,struct Node Card data; Node * next; ;,Node* sequentialSearchLinked(Node *head, string const ,从电话号码查询说起,解法2：二分查找。 条件：先把卡片按照姓名排序； 组织结构：线性逻辑结构; 存储结构：连续结构（数组，又称 随机存取结构）,从电话号码查询说起,解法3：二叉查找树； 数据组织（逻辑关系）：二叉树型结构；,从电话号码查询说起,解法3：二叉查找树； 数据组织：二叉树型结构； 存储结构：二叉链表；,struct TreeNode Card data; TreeNode *llink,*r

5、link; ;,root,从电话号码查询说起,解法4： 设计一个用于查询电话号码的class,class Telephone public: Telephone():count(0); Telephone(); Card *find(const string ,从电话号码查询说起,解法5：使用联合容器map,int main() map phones; /初始化一个map容器 phones“Dai Yun = “34035188”; /插入记录 phones“Liang Hao = “84133365”; phonesZhang Hen = “34567890”; phones“Wang Mi

6、ng = “66908143”; phones“Luo Feng = “84134566”; map:iterator cur = phones.find(Zhang Min); if (cur != phones.end() /如果查找失败，cur指向容器“末尾”，否则指向找到的记录 cout Zhang Mins phone is (*cur).second endl; else cout Zhang Min doesnt exist in phones. endl; ,map是一个 解决查找问题的数据结构,什么是数据结构-示例,例1 卡片的计算机检索系统。 所处理的基本数据（数据元素）：

7、 每个卡片由（姓名， 电话，地址) 组成； 数据元素间的关系（逻辑结构）： 一个按姓名顺序排列的线性查找表，或者按照姓名顺序的二叉查找树结构； 所需的操作： 一组作用在这些表上的运算（查询、插入、修改等）； 怎样存储这些数据及其关系使得上述操作容易实现存储结构。,从以上例子看出，用计算机解决问题时我们需要 分析问题，抽象出一个数学模型：基本数据元素以及它们之间的逻辑关系； 解决问题需要在上述集合上实现的运算； 实现数据元素集合的存储和运算。,在实际软件开发过程中 把数学模型与运算“打包”起来形成一个“抽象数据类型” 抽象数据类型的实现成为一个工具或者构件； 抽象数据类型也是这个工具的实现者（制

8、造者）和使用者的一个协议，使得使用者和实现者可以独立工作，互不影响，只要他们遵守这个协议。,程序 = 算法 + 数据结构,数据结构： 一种程序构件（programming construct)、工具; 编程中常用的数据组织形式及其操作的抽象； 编程： 数据结构的选择， 算法的设计与评价,从电话号码查询说起学习什么？,处理的数据是什么？需要什么样的数据操作？ 如何组织数据（逻辑结构）？ 如何存储数据（存储结构）？ 如何实现操作（算法的实现）？ 常见特定数据组织形式与操作构成ADT（抽象数据类型）, 其实现便是一个数据结构，解决问题的一个组件/工具； 是否有数据结构和算法适用于当前问题？ 如何评价

9、不同的解法（算法的时间复杂度和空间复杂度）？,学习数据结构的目的,掌握常用的数据结构及其应用 学会合理地组织数据， 有效地表示数据和处理数据 掌握算法设计技术和分析技术 掌握使用计算机解决问题的方法和技能，提高程序设计水平,第一章 概论,数据结构概念 抽象数据类型 算法的概念 算法的度量,数据结构的概念,数据是客观事物的符号表示,是信息的载体；可用于计算机处理或者人工交流和处理。 数据元素是数据的基本单位 数据结构是相互间具有某些关系的数据元素的集合。它包括下面三方面的内容： 1）数据的逻辑结构，表示数据元素间的关系； 2）数据的运算，是数据元素集上所允许的操作； 3）数据的存储结构，指如何在

10、计算机上数据元素及其关系。,逻辑结构的类型,数据的逻辑结构(D, R) 可分为下列几种: D = d1, d2, , dn 1. 集合: 数据元素同“属于一个集合”. R = 2. 线性结构: R= (d1, d2), (d2, d3), , (dn-1, dn), 即除开始和终结节点d1, dn外,每个节点有一个前驱和一个后继 3. 树状结构: (D, R) 构成树, 即每个元素最多有一个前驱, 可以有多个后继 4. 图状结构: (D, R)构成一个图.,数据的存储结构,以上讨论的数据只涉及其逻辑结构，或者逻辑形式，不涉及如何在计算机中表示或者存储。 数据元素集合在物理存储器上的存储方式称为

11、数据的存储结构，或者物理结构。 数据结构的存储包含数据元素的存储及其逻辑关系的存储 顺序存储结构与链式存储结构是最基本的存储结构。,理解数据的逻辑结构和存储结构,数据元素集合的存储：顺序结构,顺序的方法: 将数据元素顺序存储在一片连续的存储区。 数组提供顺序结构支持。 例如, D = d1, d2, d3, d4, d5 R = (d1,d2), (d2, d3), (d3, d4),(d4, d5) 假定一个结点占一个单元, d1存放于200号单元.,d1,d2,d3,d4,d5,200,201,202,203,204,数据元素集合的存储：链式结构,这种结构是给数据元素附加一个指针字段, 指

12、出其后继的存储位置。指针和结构类型提供支持。,数据项,指针项,指针项可以有多个, 以指示多个后继. 例如, R = (d1, d2), (d1, d3), (d2, d4), (d2, d5), (d3, d6),d1,d2,d3,d6,d5,d4,d1,d2,d3,d4,d5,d6,空指针,重点掌握顺序结构和链式结构及其特点,数据的表示：数据类型,一般的高级语言都提供了一些数据类型, 如整数型, 字符型等. 数据类型是一个值的集合和定义在此集合上的一组操作的总称. 用户还可以定义自己的数据类型. 数据类型可分为原子类型(不可分解的,如int, bool, char 等) 和结构类型(由其他类

13、型构成) 例，图书（登录号，书名，作者）数据元素的表示 struct Book int idNum； string title; string author; ,抽象数据类型(ADT),数据类型为程序员提供了极大的方便: 它将集合及其上的操作与其实现细节分离开来.程序员只需要了解此集合由哪些值构成, 可以进行那些运算. 我们将此概念进一步推广为抽象数据类型. 抽象数据类型(Abstract Data Types) 由一个数据模型(数据元素集和数据元素间的关系)及其上的一组操作构成. 使用信息隐蔽和数据封装， 使用和实现相分离,理解ADT，能够使用自己的语言举例说明什么是ADT。,ADT在OO语

14、言中的实现,抽象数据类型可以由C+的类(Class)来描述. 例如，表示圆的class class Circle private: float r, x, y; public: Circle(float v1,float v2, float v3); float area ()= return pi*r*r; ;,算法的概念,一个算法是对特定问题求解步骤的一种描述,它是指令的有穷序列. 算法具有以下特性: 1) 有穷性: 一个算法总是在执行有穷步后结束 2) 确定性: 算法的每一步都必须是明确地定义的. 3) 可行性: 算法中的每一步都是可以通过已经实现的操作来完成的 4) 输入: 一个算法有

15、零个或者多个输入, 这些输入取自于特定的对象集合 5) 输出:一个算法有一个或者多个输出，它们是与输入有特定关系的量,算法的描述,算法的描述可以用下列语言描述： 自然语言 程序设计语言 介于自然语言和程序设计语言的伪代码 框图,程序和算法有何区别？,算法设计,例 假设有n(=1)个整数a1, a2, , an. 要求对此数列由小到大进行排序。 显然这个数列构成一个线性结构。我们选择顺序存储结构，即用一个数组A存储此数列及排序后的数列。 思路： 1 从未排好序的数列中选出最小的元素，将其放到排好序的数列后 2 重复这个过程，直至排序结束。,写出思路,进一步细化： 1. 循环 i 以1 步长， 从

16、0到 n-2, 执行 （1）j i /Ai 存储从Ai 到An-1的最小整数 (2) 循环 k以1为步长, 从i+1到n-1, 执行 若Ak Aj, 则 j k / 从Ai到An中选出最小整数 (3) t Ai; Ai Aj ; Aj t / 交换Ai, Aj 2. 算法结束.,一定写注释,void selectSort (int a, const int n) / 将整数列a0, , an-1按非递减序排列 for (int i = 0; i n -1; i+) int j = i; / 找出ai到an-1的最小数aj for (int k = i + 1; k n, k+) if (ak

17、aj) j = k; / j指示当前的最小数 /交换ai和aj int temp t = ai; ai= aj; aj = t; ,模板（Template),前一程序只适用于整数列的排序。事实上，此算法适用于任何（定义了比较运算）类型的序列。 我们可以用C+提供的模板机制来设计一个更通用的排序算法。 一个模板函数是适用于很多类型的函数: 在这些类型上运算遵从相同的模式。 它带有类型参数的函数， 当类型参数用特定的参数代换时，编译器生成 针对此类型的特定函数。 同样，一个模板类是带有类型参数的类，它适用于多种类型。通过简单的类型代换，编译器便可生成代换类型的类。,template class d

18、ataList private: T *element; int arraySize; void swap(const int m1, const int m2); int minKey(const int low, const int high); public: dataList(int size = 10): arraySize(size), element(new Tsize) dataList()delete element; void sort(); ;,template void dataList : swap(const int m1, const int m2) T temp

19、 = elementm1; elementm1=elementm2; elementm2= temp; ,template void dataList:sort() for(int i =0; iarraySize-1; i+) int j = minKey(i, arraySize-1); if (j!= i ) swap(j,i); ,算法的评价,算法的设计应满足： 1）正确性：对于合法的输入产生符合要求的输出； 2）可读性：算法应该易读、便于交流， 这也是保证算法正确性的前提；添加注释也是一种增加可读性的办法； 3）健壮性：当输入非法时， 算法还能做出适当的反应而不会崩溃， 如输出错误信

20、息；算法中应该考虑适当的错误处理； 4）效率高且内存消耗小：效率高指运行时间短。存储指算法执行过程中所需的最大存储空间。,算法分析,解决同一问题的算法可以有多种。 我们希望从中选出最优的算法，效率高或者存储空间小。 为此，我们需要对算法进行评估，分析。通常有两种方法： 事后统计：不同算法的程序运行在同一组输入上，根据时间和空间的统计来比较优劣。 缺陷：事先编写程序； 依赖于程序运行的软硬件环境。 习题: 试统计函数selectSort()在不同大小输入上的运行时间.,算法分析,事前估计：一种不考虑算法的程序运行软硬件环境的分析方法。一个算法的运行工作量的大小只依赖于问题的规模。 通常考虑两个度

21、量： 时间复杂度：算法执行的操作的总数作为问题规模的函数。 空间复杂度：算法执行时所占用的存储空间作为问题规模的函数。,时间复杂度,对于给定规模的问题，计算算法运行的总“步数”： 在算法中选取一种基本操作作为“程序步”（多种不同的操作可视为一个程序步，或者不同的操作具有不同的权）； 统计算法从开始到运行终止时所需总程序步数T, 并将其视为问题规模n的函数T(n). T(n) 称为算法的时间复杂度。,例 迭代累加求和 float sum(int a, const int n) float s = 0.0; / 计一步 for (int i = 0; i n; i+ ) s += ai; / 每次

22、循环计步: 赋值 return s; 总计步数:n + 问题的规模即数组的规模n,包含函数调用的赋值语句的程序步数： x = sum (A, n); 总步数：调用的步数 + 1 即 (n + ) + 1,基本运算的完成时间不应该依赖于所涉及参数值,求总程序步数(数组的大小n为问题的规模) ： void selectSort (int a, const int n) for (int i = 0; i n -1; i+) int j = i;/计一次 for (int k = i + 1; k n, k+) if (ak aj) j = k;/ if 语句最多计步 /此循环总步数= 2*(n-i

23、-1) int temp t = ai; ai= aj; aj = t; / 计3步 / n-1 次循环, 每次 1 + *(n-i-1) + 3 /总计 T(n) = n-2i=0(1 + (n-i-1) + 3) = （n+4)*(n-1) / T(n) 与输入有关系.,时间复杂度T(n)可能依赖于输入，即不同的输入（相同的规模）其复杂度不同，譬如排序算法此时可以计算平均复杂度或者最坏情况复杂度 平均复杂度(The Average Case)：所有可能输入数据集的期望值 最坏情况复杂度(The Worst Case)：估算最坏情况下时间复杂度的一个上界这也是通常所指的复杂度,复杂度的度量通

24、常计算到数量级如果f(n)是一个函数，并且存在一个常数c, 当n充分大时， 则记为T(n) = O(f(n) 如 T(n) = 3n2 +12n, 则T(n) = O(n2) 累加求和的例子: T(n) = O(n) 排序的例子: T(n) = O(n2),T(n) = c f(n),算法的复杂度用大O表示： 方法：计算T(n)的上界并按降幂排列，如 T(n)f(n)=100n3 - 20n2 + 5n + 10000 则 T(n) = O(n3) 注意，不写T(n)=O(3n2)，或 T(n) =O(n2 + log n) 常见的复杂度：O(1), O(log2 n), O(n), O(nlog2 n) , O(n2), O(2n), O(n!) 理解T(n)=O(f(n) 的含义。,只记增长最快的项，系数为1,n,T(n),200log2n,100n,5n2,2n,20,10,2000,1000,不同时间复杂度算法区别有多大？,T1(n) = 100nlog n , T2(n) = n2,更快的机器还是更快的算法,换一个快10倍的机器能否解决更大的问题呢？,n:原机器一小时解决问题规模，n:新机器一小时解决问题规模,空间复杂度,计算算法运行过程所占用的存储量作为问题规模的函数 S(n) = O(f(n). 通常以简单变量的存储空间为单位 算法的存储空间包