《数据结构与算法设计》d

第1章 绪论,第 2 页,第1章 绪论,1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型 1.4 算法和算法分析,1.1 什么是数据结构,一个例子,第 3 页,1.1 什么是数据结构,关东军和不抵抗 一个完整的“9.18事变” 2008年09月17日 17:17凤凰历史综合 我们必须全面地了解一下“9.18事变”的全过程。我们应当知道一个完整的”9.18事变”。,第 4 页,一个例子：在线查询,今天是9.18事变纪念日，无意中看到几篇文章发现，原来9.18事变的罪魁祸首居然是被周恩来称之为民族英雄的张学良！正是因为他我国东北才被日寇占领14年之久，才有了后来的8年抗战！,9.18事变,9.18事变,缺陷： 系统反应滞后 不支持多用户并发访问 不支持海量数据,第 5 页,1.1 什么是数据结构,例：基于关键字匹配的全文搜索引擎 正文切分 建立关键词-文档倒排表结构 提供基于关键字匹配的全文检索服务,1.1 什么是数据结构,2008年 5月 12日 在 四川省 西北部 汶川 地区 发生 了 里氏 8.0 级 地震 ， 波及 四川 成都 、 绵阳 、 德阳 、 雅安 、 陕西 和 甘肃 等 部分 地区 。 在 地震 发生 之前 ， 绵竹县 发生 了 蛤蟆 结群 上街 ， 远 在 湖北 西部 的 水塘 水体 一夜 之间 消失 等 异常 现象 。,2008年5月12日在四川省西北部汶川地区发生了里氏8.0级地震，波及四川成都、绵阳、德阳、雅安、陕西和甘肃等部分地区。在地震发生之前，绵竹县发生了蛤蟆结群上街，远在湖北西部的水塘水体一夜之间消失等异常现象。,正文文档：,分词结果：,分词：将连续的字序列按照一定的规范重新组合成词序列的过程,建立关键词-文档倒排表结构,2008年,5月,12日,四川,汶川,厨师,发生,美国国防部长莱昂E.帕内塔宣布，对于新西兰海军舰艇访问美国国防部和海岸警卫队在美国和全世界各地的设施一事，他已经放松了有关的限制。 。,2008年5月12日在四川省西北部汶川地区发生了里氏8.0级地震，波及四川成都、绵阳、德阳、雅安、陕西和甘肃等部分地区。在地震发生之前，绵竹县发生了蛤蟆结群上街，远在湖北西部的水塘水体一夜之间消失等异常现象。,四川厨师们用了一些一直以来都被粤菜忽略的食材来制作菜式，另外在调味及配搭方面都做得非常出色。所谓海蜇花，就是海蜇头，也就是海蜇的底部吸管的部位，这个部位的海蜇口感非常爽脆，但缺点是海蜇本身没有味道，所以厨师们用了山西老陈醋、日本黑芝麻油及越南的顶级角露来调味，而且调校得酸中带香，香中带鲜，鲜中又带甜，直县不错。另外，厨师们更以黑木耳,美国,文档集,关键词典,如何管理关键词典？,1.1 什么是数据结构,简单的办法 char * dictionary = (char *)maolloc(); char * target = ; for (int i=0;isize;i+) If (strcmp(dictionaryi, target)=0) return getDocumentsbyWord(i); ,第 8 页,关键词 只有属于同一词典的关系（集合关系） 查找不命中时，需要遍历所有关键词,1.1 什么是数据结构,排序的办法 char * dictionary = (char *)maolloc(); char * target = ; sort(dictionary); for (int i=0;isize;i+) int ret = strcmp(dictionaryi, target); If (ret=0) return getDocumentsbyWord(i); else if (ret0) return NULL; ,第 9 页,关键词在词典中是有序的，在逻辑上是一种线性关系。 如何排序？ 可以根据有序性，构建快速查找方法,1.1 什么是数据结构,快速查找方法(B+树),第 10 页,1.1 什么是数据结构,利用计算机进行问题求解 方程求解 建立数学模型及求解算法，编制程序 输入参数 计算机根据相应求解算法计算 输出计算结果 银行ATM服务 建立业务对象模型和业务处理算法，构建计算机处理系统 客户输入（帐号/密码，服务类型，钞票） 计算机处理 输出（钞票/打印条）,第 11 页,第 12 页,1.1 什么是数据结构, 处理数据的种类, 数据,数值数据,非数值数据,数（整数，实数） 字符 字符串 文字 布尔值 图形 图像 声音,数据：所有能输入到计算机中，并能被其存储、加工、处理的符号的集合。 数据就是客观对象的符号表示。,程序,第 13 页,1.1 什么是数据结构,数值问题 例1：已知游泳池的长len、宽width和深度depth，求体积volume。 建立模型涉及的对象：len，width，depth 和 volume 对象之间的关系： volume =lenwidth depth 设计求解问题的方法 编程 main ( ) int len, width , depth ，volume ;scanf (”%d%d%d”, ,例2：求一组整数 (M个)中的最大值,第 14 页,建立模型 涉及对象： M个整数 对象之间的关系：大小关系 设计求解问题的方法： 基本操作是“比较两个数的大小” 设第一个数为当前最大值，逐一比较其余n-1个数，如某数大于当前最大值，则当前最大值更新为新的最大值 编程： main ( ) int *d, M, i, max; scanf (”%d”, ,第 15 页,1.1 什么是数据结构,非数值问题 例2：已知学生选课情况，安排课程考试的日程，要求在尽可能短的时间内完成考试。,第 16 页,1.1 什么是数据结构, 建立模型 问题涉及的对象：课程 课程之间的关系：同一学生选修的课程之间有某种“冲突”关系。 要求：同一个学生选修的课程不能安排在同一时间进行内考试。,第 17 页,1.1 什么是数据结构,D,E,F,C,B,A,顶点：表示课程,同一学生选修 的课程用一条边连接,有边连接的课程不能 安排在同一时间考试,第 18 页,1.1 什么是数据结构,设计求解问题的方法 课程考试可用图的着色法求解问题。 每一种颜色代表一个考试时间，着上相同颜色的顶点是可以安排在同一时间考试的课程； 用尽可能少的颜色为图的顶点着色，相邻的顶点着上不同的颜色。,B,如下是一种考试日程： 1: 算法分析(A) 计算机图形学(C) 2: 形式语言(B) 模式识别人工智能（D) 3: 计算机网络(E) 4: 人工智能(F),第 19 页,1.1 什么是数据结构,求解考试日程的流程 设：G表示课程关系图，V是图G中所有尚未着色的顶点集合，NEW表示可以用新颜色着色的顶点集合。,1)i=1；V = 图中所有顶点的集合 2)若 V 非空 DO 置 NEW 为空集合； 在 V 中取一点，找出所有与之“不相邻”的顶点； 将这些顶点加入 NEW，从 V 中去掉这些顶点 （第 i 天考试课程为 NEW 中顶点所对应的课程） 以某种形式输出NEW中顶点所对应的课程； i = i+1； 3)若 V 空，结束, 编程 存储图，集合 实现图/集合的操作,第 20 页,1.1 什么是数据结构,数值问题与非数值问题的比较,数值问题 * 对象：len,wide,area 用数值表示 * 对象之间的关系： area = len wide 用方程或函数表示 * 数据存储：可用程序设计语言中的实型变量存储数据 * 问题求解方法：某种数值计算方法求解,非数值问题 * 对象：课程用课程名表示 * 对象之间的关系： 课程间有“冲突”关系 * 数据存储：要保存数据及数据之间的关系 * 问题求解方法,不能用数值表示,课程之间的这种关系 不能用方程或函数表示,第 21 页,1.1 什么是数据结构,1968年美国D.E.Knuth 教授出版：The Art of Computer Programming计算机程序设计技巧开创了数据结构的最初体系。计划共写7卷，然而出版三卷之后，已震惊世界，获得计算机科学界的最高荣誉图灵奖，年仅36岁。,1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。,第 22 页,1.1 什么是数据结构,什么是数据结构？ 数据结构是一门研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。 数据结构所研究的问题 非数值数据之间的结构关系，及如何表示，如何存储，如何处理。,第 23 页,1.1 什么是数据结构,数据结构随着程序设计的发展而发展 结构化阶段：数据结构算法程序 面向对象阶段：(数据结构算法)程序 数据结构的发展并未终结 研究的范围不断扩展，算法不断更新 描述手段、使用语言不断更新,第 24 页,第1章 绪论,1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型 1.4 算法和算法分析,第 25 页,1.2 基本概念和术语,数据(data)：客观对象的符号表示。 数据元素(data element)：数据的基本单位，在计算机程序中作为一个整体考虑和处理，通常具有完整确定的实际意义。(节点、顶点、记录) 数据项(data item)：数据不可分割的最小标识单位。一个数据元素可由若干数据项组成，通常不具有完整确定的实际意义。(字段),第 26 页,1.2 基本概念和术语,数据结构(data structure)：相互之间存在一种或多种特定关系的、具有相同特征的数据元素的集合。 数据结构：带有结构和操作的数据元素集合。 结构：数据元素之间的关系； 操作：对数据的加工处理 。,第 27 页,1.2 基本概念和术语,每种结构讨论两方面问题： 1) 数据的逻辑结构：从具体问题抽象出来的数据模型，反映了事物的组成及事物之间的逻辑关系。 2) 数据的存储结构(也称为物理结构)：解决各种逻辑结构在计算机中的物理存储和表示。 同一种逻辑结构可以采用不同的表示方式，即采用不同的映射关系来建立数据的逻辑结构到存储结构的转换。,第 28 页,1.2 基本概念和术语：数据的逻辑结构,数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。有四种 集合：数据元素间除“同属于一个集合”外，无其它关系 线性结构：一个对一个，如线性表/栈/队列 树形结构：一个对多个，如树 图状结构：多个对多个，如图,第 29 页,1.2 基本概念和术语：数据的逻辑结构,线性结构 学生基本情况登记表，记录了每个学生的学号、姓名、专业、政治面貌。按学生的学号顺序排列。,学生间学号顺序关系 是一种线性结构关系,线性结构：除第一个元素和最后一个元素外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。,学号 姓名 专业 政治面貌 001王洪 计算机 党员 002 孙文 计算机 团员 003谢军 计算机 团员 004李辉 计算机 团员 005沈祥福 计算机 党员 006余斌 计算机 团员007巩力 计算机 团员008孔令辉 计算机 团员,第 30 页,1.2 基本概念和术语：数据的逻辑结构,树形结构 假设某家族有10个成员A、B、C、D、E、F、G、H、I、J，他们之间的血缘关系可以用图表示。,树形结构：每一个元素只有一个直接前趋，有0个或多个直接后继。,第 31 页,1.2 基本概念和术语：数据的逻辑结构,图形结构 工程进度图。,图形结构：每一个元素可以有0个或多个直接前趋，有0个或多个直接后继。,第 32 页,1.2 基本概念和术语：数据的逻辑结构,数据结构的表示 图示表示 图示表示是由顶点和边构成的图，其中顶点表示数据，边表示数据之间的结构关系。 二元组表示 二元组表示是用一个二元组（D，S）表示数据结构，其中 D 是数据元素集合，S 是 D 上关系的集合。,第 33 页,1.2 基本概念和术语：数据的逻辑结构,例：学生基本情况表的二元组表示（D，S）,D = 001，002，003，004，005，006，007，008 S = R R = , , , , , , ,第 34 页,1.2 基本概念和术语：数据的逻辑结构,例：家族树的二元组表示（D，S）,D = A，B，C，D，E，F，G，H，I，J S = R R = , , , , , , , , ,第 35 页,1.2 基本概念和术语：数据的存储结构,数据的存储结构 逻辑结构：从操作对象抽象出来的数学模型。 存储结构：逻辑结构在计算机中的表示,包含 “数据元素”的映象和“关系”的映象。实质是内存分配，具体实现依赖于计算机语言。 数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。 一种数据的逻辑结构可以用多种存储结构来存储；而采用不同的存储结构，其数据处理的效率往往是不同的。,第 36 页,1.2 基本概念和术语：数据的存储结构,常见的存储结构 顺序存储方式 链式存储方式 散列方式 索引方式。 顺序存储方式：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如，用一维数组存储线性结构。 链式存储方式：借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。例如，用链表(指针)存储线性结构。,第 37 页,1.2 基本概念和术语：数据的存储结构,顺序存储结构,元素n,.,元素i,.,元素2,元素1,L0,L0+m,L0+(i-1)*m,L0+（n-1)*m,存储地址,存储内容,Loc(元素i) = L0 +（i-1) * m,第 38 页,1.2 基本概念和术语：数据的存储结构,链式存储结构,1536,元素2,1400,元素1,1386,元素3,元素4,1345,h,