[工学]数据结构简介.ppt

数据结构 Data Stuctures 乔 海燕 电话：020Email : qiaohy@sysu.edu.cn 什么是数据结构？ 什么是数据结构？ 为什么学习数据结构？达到什么目的？ 应该掌握哪些内容？技能？ 如何学习？ 从电话号码查询说起 问题：你有一叠亲友和客户等的名片，需要在其中查找某个人的卡片。 从电话号码查询说起 解法1的实现(1)： 使用数组存储卡片； 从电话号码查询说起 解法1的实现(1)： 算法的实现； 从电话号码查询说起 解法1的实现(2)： 使用链表存储卡片； 从电话号码查询说起 解法1的实现(2)： 使用链表存储卡片； 从电话号码查询说起 解法2：二分查找。 条件：先把卡片按照姓名排序； 组织结构：线性逻辑结构; 存储结构：连续结构（数组，又称 随机存取结构） 从电话号码查询说起 解法3：二叉查找树； 数据组织（逻辑关系）：二叉树型结构； 从电话号码查询说起 解法3：而叉查找树； 数据组织：二叉树型结构； 存储结构：二叉链表； 从电话号码查询说起 解法4：使用联合容器map 从电话号码查询说起—学习什么？ 处理的数据是什么？需要什么样的数据操作？ 如何组织数据（逻辑结构）？ 如何存储数据（存储结构）？ 如何实现操作（算法的实现）？ 常见特定数据组织形式与操作构成ADT（抽象数据类型）, 其实现便是一个数据结构，解决问题的一个组件/工具； 是否有数据结构和算法适用于当前问题？ 如何评价不同的解法（算法的时间复杂度和空间复杂度）？ 学习数据结构的目的 第一章 概论 数据结构的概念 逻辑结构的类型 数据的存储结构 存储结构的分类: 顺序结构 存储结构的分类: 链式结构 数据类型(Data Type) 抽象数据类型(ADT) ADT在OO语言中的实现 算法的概念 算法的描述 算法的描述 算法设计 算法分析 算法分析 时间复杂度 练习 将下列复杂度用O表示： T(n)? (n+10)3 T(n) ? n1/2 + 10log n T(n) ? n! + 2n T(n) = T(n-1) + n2 计算代码的时间复杂度 for (i=1; i=n; i++) for (j=1; j=i; j++) for (k=1; k=j;k++) x = i+j-k; struct Node{ int data; Node * next; Node() {next=NULL:}; Node(int k, Node * link=NULL) {data=k; next = link}; } ; 画出下列代码执行过程示意图： Node first_node(12);. Node *p0 = first_node; Node *p1 = new Node(13); p0-next = p1; Node *p2 = new Node(15, p0); p1-next = p2; 解决同一问题的算法可以有多种。 我们希望从中选出最优的算法，效率高或者存储空间小。为此，需要对算法进行评估，分析。 通常考虑两个度量： 时间复杂度：算法运行时需要的总步数，通常是问题规模的函数。 空间复杂度：算法执行时所占用的存储空间，通常是问题规模的函数。 通常有两种方法： 事后统计：不同算法的程序运行在同一组输入上，根据时间和空间的统计来比较优劣。 缺陷：事先编写程序； 依赖于程序运行的软硬件环境。 事前估计：一种不考虑算法的程序运行软硬件环境的分析方法。一个算法的运行工作量的大小只依赖于问题的规模。 对于给定规模的问题，计算算法运行的总“步数”： 在算法中不依赖于输入规模的语句都可看作基本操作，基本操作的一次运行视为一步； 统计算法从开始到运行终止时所需总操作步数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 += a[i]; // 每次循环计一步 return s; // 计1步 } 总计步数:　n + 2 问题的规模即数组的规模n 包含函数调用的赋值语句的程序步数： 　for (int i=0;jn;i++) A[i]=i; x = sum (A, n); 总步数：循环步数 + 调用的步数 + 1 即 T(n)= n+ (