计算机导论7 数据结构与算法ppt课件.ppt

计算机导论,第 7 讲,数据结构与算法,数据结构（data structure）数据结构的基本概念典型的数据结构 算法（algorithm）算法的基本概念算法的描述方法衡量算法的优劣,数据结构与算法,1、数据结构的基本概念 数据结构（data structure）：数据元素之间抽象化的关联构造。（重在元素之间的逻辑关系及数据处理） 数据结构的作用 （1）Pascal之父Nicklaus Wirth：算法 + 数据结构 = 程序 （2）数据结构是程序设计之前必须先考虑好的问题 （3）以数据为中心设计程序，因此，数据结构是关键。数据结构设计得当，程序设计得心应手，事半功倍；数据结构设计不好，程序设计事倍功半，甚至无从下手。,数据结构,1、数据结构的基本概念 数据结构的使用 强调灵活运用，数据结构课程讲授典型的数据结构与处理算法，但 实际应用中要综合，要变通，要深刻理解数据结构的思想，要有自己的 设计。要学会将看似截然不同的问题抽象成相同的数据结构。例如：（1）某班级学生信息表的处理：线性表 （2）某单位组织结构信息的处理：树 （3）某地区公路网信息的处理：图以上问题都能在数据结构课程中找到标准的数据结构和处理算法。 （4）补考排考场的处理这个问题可用“图”来组织数据，但在数据结构课程中没有相应算法。,数据结构,1、数据结构的基本概念 数据元素和数据项 （1）数据（data）：所有能输入计算机并被计算机程序所处理的符号的总称。 （2）数据元素（data element）：数据的基本单位，通常作为一个整体进行处理。又称结点（node）或记录（record）。 （3）数据项（data item）：数据的不可分割的、具有独立意义的最小单位。有时称为字段或域（field）。（数据元素有哪些组成成分）,数据结构,数据元素（一名学生）,学号,6012410109,姓名,张三,性别,男,政治面貌,党员,数据项1,数据项2,数据项3,数据项4,1、数据结构的基本概念 逻辑结构与物理结构 （1）数据逻辑结构（data logical structure）：数据元素之间存在的一种或多种特定的关系。 （2）数据物理结构（data physical structure）：数据在计算机中的存放方式，即数据逻辑结构在计算机存储器中的实现。（数据是如何在存储器中存放的）,数据结构,1、数据结构的基本概念 四种基本的逻辑结构,数据结构,集合,线性结构,树形结构,图形结构,2、典型的数据结构 线性表（list）：n （n0）个数据元素的有限序列（a1 , a2 , , an）。 （1）长度：线性表中数据元素的个数。 （2）空表：长度为0的线性表。 （3）直接前驱（immediate predecessor）与直接后继（immediate successor）ai是ai+1的直接前驱，ai+1是ai的直接后继。 （4）基本操作：初始化空表、求长度、判断空表、置空、取第i号元素、定位（给定元素值）、修改元素、插入元素、删除元素。,数据结构,2、典型的数据结构 线性表 （5）栈（stack）：只能在一端进行插入和删除操作的线性表。栈的插入：进栈、入栈、压栈栈的删除：退栈、出栈、弹栈栈的操作特点：先进后出（后进先出） （6）队列（queue）：只允许在表的一端插入元素，在表的另一端删除元素。队头：删除端队尾：插入端。队列的操作特点：先进先出（后进后出）,数据结构,2、典型的数据结构 线性表 （7）线性表的应用（1）一组数据元素，互相之间地位平等（可能有先后次序，除此 之外没有其他逻辑关系）。 例如：30名学生、10个班级、100本书等 例如：操作系统中的进程表、FAT表（2）栈的应用： 例如：子程序调用的实现、表达式计算的实现、语法分析等（3）队列的应用： 例如：操作系统中的作业队列、打印队列、缓冲区等,数据结构,2、典型的数据结构 树（tree）： n（n0）个结点的非线性结构；有且只有一个结点称为 根（root）；余下结点分为m(m0)个不相交的集合，每个集合又是一 棵树，称为根的子树（subtree）。,数据结构,A,B,C,D,G,E,F,I,H,J,根,子树,2、典型的数据结构 树 树的应用：一组数据元素，互相之间地位不平等，有严格的上下级层次 关系。 例如：文件索引的B+树、目录组织的树形结构网络交换机的生成树某单位的组织结构（如辽科院，之下分n多二级教学单位和职能部门，每个 二级单位/部门下又分教研室、科室等）某些棋类对弈问题,数据结构,例：人机对奕问题,2、典型的数据结构 图（graph）：n个数据元素，任意两个元素之间都可能存在逻辑关系。 （1）逻辑结构：G = ( V, E )V：顶点（图结点）的有穷集合。E：边（两个顶点间的关系）的有穷集合。,数据结构,1,2,3,4,1,3,4,无向图,有向图,2,2、典型的数据结构 图 （2）图的应用：一组数据元素，互相之间地位平等，互相之间都可能 存放某种逻辑关系。 例如：网络中的路由器交通图、电路图、列车运行图、地下管网棋类对弈迷宫、一笔画很多人工智能问题 ,数据结构,例：多叉路口交通灯管理问题,例：多城市间最小距离问题,例：【八皇后问题】高斯1850年提出：在88格的国际象 棋上摆放八个皇后，使其不能互相攻击，即任意两个 皇后都不能处于同一行、同一列或同一斜线上，问有 多少种摆法？这个问题可以抽象成图的问题，用图形结构和图的遍历算法来解决。,例：【华容道游戏】如何使大方块（曹操）从重围中走出 来？（除大方块可以最终移出出口外，所有块都只 能在盒内向相邻的空格移动，）,这个问题可以抽象成图的问题，用图形结构和图的遍历算法来解决。,出 口,1、算法的基本概念 算法（algorithm）：为求解问题而采取的方法和步骤。 算法分类：数值运算算法、非数值运算算法。 算法的特征 （1）有穷性：包含有限的操作步骤。（步骤数和时间上都有限） （2）确定性：每一个步骤都是确定的，没有歧义。 （3）有效性：每一个步骤都有效执行，并得到确定的结果。 （4）有零个或多个输入：从外界取得必要的信息。 （5）有一个或多个输出：整个算法必须获得结果。,算法,2、算法的描述方法 流程图（flowchart） （1）基本符号（2）例：求最大公约数,算法,起止框,输入输出框,处理框,判断框,流线,连接点,开始,输入m，n,r = m % n,r = 0?,m = nn = r,输出n,结束,Y,N,2、算法的描述方法 伪代码（pseudo code）： 类似程序设计语言，但不那么严格、不那么形式化的算法描述方法。 （1）赋值、输入、输出 （2）程序块、顺序执行：begin end （3）选择执行：if、switch （4）循环执行：while、for,算法,例：求最大公约数begin input m, n; r = m % n; while r 0 begin m = n; n = r; end output n;end,3、衡量算法的优劣 算法设计的要求 （1）易读性：格式整洁，命名规范。易于阅读和理解，易于调试修改和扩充。 （2）健壮性：对于非法输入，算法应作出反应或处理。（容错） （3）高效性：达到所需的时空性能。尽可能省时间（时间效率高）、省空间（空间效率高）。,算法,3、衡量算法的优劣 复杂度（complexity） 用O(关于n的表达式)作为时间或空间复杂度的表示，其中 “关于n的表达式”忽略常数项、低次项。 （n代表问题规模，一般代表待处理的数据量数据元素数） 常见时间复杂度（time complexity） O(1)常数阶（算法所需时间与问题规模无关） O(logan)对数阶 O(n)线性阶（算法所需时间与问题规模成正比） O(n2)平方阶、O(n3)立方阶、 O(an)指数阶 O(nlogan),算法,3、衡量算法的优劣 常见空间复杂度（space complexity） O(1)常数阶（算法所需辅助空间与问题规模无关） O(logan)对数阶 O(n)线性阶（算法所需辅助空间与问题规模成正比） O(n2)平方阶、O(n3)立方阶、 O(an)指数阶 O(nlogan),算法,3、衡量算法的优劣 举例：输入正整数 n，输出 n 的所有因数。 begin input n; for k = 1 to n begin if n % k = 0 then output k; end end,算法,时间复杂度：O(n)空间复杂度：O(1),3、衡量算法的优劣 举例：输入 20 个数，求最大值。 begin input max; for k = 1 to 19 begin input t; if t max then max = t; end output max; end,算法,时间复杂度：O(n)空间复杂度：O(1),数据结构专门一门课程讲授数据结构（含线性表、树、图、排序、查找等内容）,相关的主要课程,多了解一些,高德纳唐纳德克努斯,高德纳唐纳德 克努斯算法和程序设计技术的先驱者,1938年出生于密尔沃基。1956年就读凯斯理工学院，1960年同时获学士和硕士学位，之后在伯克利攻读数学博士学位。1963年毕业后，在伯克利任教。1962年，世界著名出版社Addison-Wesley向他约稿，他原计划出7卷。1968年计算机程序设计艺术第一卷出版（基本算法）。同年，到斯坦福任教。第二年，第二卷出版（半数值算法）。1973年，第三卷出版（排序与查找）。,高德纳唐纳德 克努斯算法和程序设计技术的先驱者,1974年，仅36岁就因计算机程序设计艺术而获图灵奖。之后辍笔，但创造了字体设计系统METAFONT、文学化编程、排版系统TEX。1979年，获美国国家科学金奖；1996年，获京都奖。1992年，为专心写作提前退休。2008年，第四卷面世（组合算法）。第五卷（语法算法）、第六卷（语言理论）、第七卷（编译程序）在准备？计算机程序设计艺术被科学美国人评为20世纪最重要的12部科学著作之一。到现在共出19部著作和160余篇论文。,高德纳唐纳德 克努斯算法和程序设计技术的先驱者,如果你认为你是一名真正优秀的程序员读Knuth的计算机程序设计艺术，如果你能读懂整套书的话，请给我发一份你的简历。 Bill Gates 这是一套集所有基础算法之大成的经典之作。当今软件开发人员所掌握的绝大多数计算机程序设计的知识都来源于此。 Byte,迪杰斯特拉（Edsger Wybe Dijkstra ）,1930年出生于荷兰阿姆斯特丹，2002年逝世于荷兰纽南。理论物理学博士。发明最短路径算法（Dijkstra算法）、ALGOL第二代编程语言、结构化定理等。如今的大部分语言都属于类ALGOL语言。ALGOL是图灵奖机器，围绕ALGOL语言共产生了十几位图灵奖得主。1972年获得图灵奖。,约翰霍泼克洛夫特（John Edward Hopcroft）,1939年生于西雅图。1961年获西雅图大学电气工程学士学位，1962年获斯坦福大学硕士学位，1964年获博士学位。曾先后在普林斯顿大学、康乃尔大学、斯坦福大学工作。提出“最坏情况渐近分析法” ，以此衡量算法的效率和优劣。 在高德纳名下与塔扬一起研究图的连通性和平面性测试难题，提出“深度优先搜索算法”。提出“双堆栈叠”数据结构，提出“2-3树”数据结构。主要著作：计算机算法的设计与分析、数据结构和算法、自动机理论，语言和计算的导论和计算机科学：成就与机遇。 1986年获得图灵奖。,罗伯特塔扬 （Robert Endre Tarjan）,1948年4月30日生于加里福尼亚州的波莫纳。1965年在加州理工学院学习数学，同时辅修计算机课程。1969年进入斯坦福大学研究生院，师从高德纳。1972年获博士学位。之后随霍泼克洛夫特去康奈尔大学工作。后来又在伯克利、斯坦福、贝尔实验室工作。与霍泼克洛夫特共同提出“深度优先搜索”算法。提出“合并-搜索”算法，用发明的“动态树”解决最大网络流问题，提出“八字树”数据结构，提出“持久性数据结构”。1986年获得图灵奖。,