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

1、.第 2 2 页第第1 1章章 绪论绪论 1.1 1.1 什么是数据结构什么是数据结构 1.2 1.2 基本概念和术语基本概念和术语 1.3 1.3 抽象数据类型抽象数据类型 1.4 1.4 算法和算法分析算法和算法分析.1.1 1.1 什么是数据结构什么是数据结构l一个例子一个例子第 3 3 页.1.1 1.1 什么是数据结构什么是数据结构关东军和不抵抗 一个完整的“事变”2008年09月17日 17:17凤凰历史综合我们必须全面地了解一下“事变”的全过程。我们应当知道一个完整的”事变”。第 4 4 页l一个例子：在线查询一个例子：在线查询今天是事变纪念日，无意中看到几篇文章发现，原来事变的

2、罪魁祸首居然是被周恩来称之为民族英雄的张学良！正是因为他我国东北才被日寇占领14年之久，才有了后来的8年抗战！http:/事变事变缺陷：缺陷：系统反应滞后不支持多用户并发访问不支持海量数据.第 5 5 页1.1 1.1 什么是数据结构什么是数据结构例：基于关键字匹配的全文搜索引擎例：基于关键字匹配的全文搜索引擎l正文切分正文切分l建立关键词建立关键词-文档倒排表结构文档倒排表结构l提供基于关键字匹配的全文检索服务提供基于关键字匹配的全文检索服务.1.1 1.1 什么是数据结构什么是数据结构2008年年 5月月 12日日 在在 四川省四川省 西北部西北部 汶川汶川 地区地区 发生发生 了了 里氏

3、里氏 8.0 级级 地震地震 ， 波及波及 四川四川 成都成都 、 绵阳绵阳 、 德阳德阳 、 雅安雅安 、 陕西陕西 和和 甘甘肃肃 等等 部分部分 地区地区 。 在在 地震地震 发生发生 之前之前 ， 绵竹县绵竹县 发生发生 了了 蛤蟆蛤蟆 结群结群 上街上街 ， 远远 在在 湖北湖北 西部西部 的的 水塘水塘 水体水体 一夜一夜 之间之间 消失消失 等等 异常异常 现象现象 。2008年5月12日在四川省西北部汶川地区发生了里氏级地震，波及四川成都、绵阳、德阳、雅安、陕西和甘肃等部分地区。在地震发生之前，绵竹县发生了蛤蟆结群上街，远在湖北西部的水塘水体一夜之间消失等异常现象。正文文档：分

4、词结果：分词：将连续的字序列按照一定的规范重新组合成词序列的过程.建立关键词建立关键词- -文档倒排表结构文档倒排表结构2008年5月12日四川汶川厨师发生美国国防部长莱昂 E.帕内塔宣布，对于新西兰海军舰艇访问美国国防部和海岸警卫队在美国和全世界各地的设施一事，他已经放松了有关的限制。 。2008年5月12日在四川省西北部汶川地区发生了里氏级地震，波及四川成都、绵阳、德阳、雅安、陕西和甘肃等部分地区。在地震发生之前，绵竹县发生了蛤蟆结群上街，远在湖北西部的水塘水体一夜之间消失等异常现象。四川厨师们用了一些一直以来都被粤菜忽略的食材来制作菜式，另外在调味及配搭方面都做得非常出色。所谓海蜇花，就

5、是海蜇头，也就是海蜇的底部吸管的部位，这个部位的海蜇口感非常爽脆，但缺点是海蜇本身没有味道，所以厨师们用了山西老陈醋、日本黑芝麻油及越南的顶级角露来调味，而且调校得酸中带香，香中带鲜，鲜中又带甜，直县不错。另外，厨师们更以黑木耳美国文档集关键词典如何管理关键词典？.1.1 1.1 什么是数据结构什么是数据结构l简单的办法简单的办法char * dictionary = (char *)maolloc();char * target = ;for (int i=0;isize;i+)If (strcmp(dictionaryi, target)=0) return getDocumentsbyW

6、ord(i);第 8 8 页关键词只有属于同一词典的关系（集合关系）查找不命中时，需要遍历所有关键词.1.1 1.1 什么是数据结构什么是数据结构l排序的办法排序的办法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 9 页关键词在词典中是有序

7、的，在逻辑上是一种线性关系。如何排序？可以根据有序性，构建快速查找方法.1.1 1.1 什么是数据结构什么是数据结构l快速查找方法快速查找方法(B+树树)第 1010 页C HD HA B Chead.1.1 1.1 什么是数据结构什么是数据结构l利用计算机进行问题求解利用计算机进行问题求解方程求解方程求解n建立数学模型及求解算法，编制程序建立数学模型及求解算法，编制程序n输入参数输入参数n计算机根据相应求解算法计算计算机根据相应求解算法计算n输出计算结果输出计算结果银行银行ATM服务服务n建立业务对象模型和业务处理算法，构建计算建立业务对象模型和业务处理算法，构建计算机处理系统机处理系统n客

8、户输入（帐号客户输入（帐号/密码，服务类型，钞票）密码，服务类型，钞票）n计算机处理计算机处理n输出（钞票输出（钞票/打印条）打印条）第 1111 页数值计算非数值计算.第 1212 页1.1 1.1 什么是数据结构什么是数据结构 处理数据的种类处理数据的种类 数据数据数值数据数值数据非数值数据非数值数据 数（整数，实数）数（整数，实数） 字符字符 字符串字符串 文字文字 布尔值布尔值 图形图形 图像图像 声音声音数据数据：所有能输入到计算机中，并能被其存储所有能输入到计算机中，并能被其存储、加工、处理的符号的集合。、加工、处理的符号的集合。数据数据就是客观对象的符号表示。就是客观对象的符号表

9、示。 程序程序原始数据原始数据结果数据结果数据.第 1313 页1.1 1.1 什么是数据结构什么是数据结构l数值问题数值问题 例例1：已知游泳池的长：已知游泳池的长len、宽、宽width和深度和深度depth，求，求体积体积volume。建立模型建立模型涉及的对象：涉及的对象：len，width，depth 和和 volume 对象之间的关系：对象之间的关系： volume =lenwidth depth 设计求解问题的方法设计求解问题的方法编程编程main ( ) int len, width , depth ，volume ;scanf (”%d%d%d”, &len, &am

10、p;width , & volume );volume = len*width*depth;printf (”volume=%dn”, volume);.例例2 2：求一组整数求一组整数 (M(M个个) )中的最大值中的最大值第 1414 页建立模型建立模型 涉及对象：涉及对象： M个整数个整数对象之间的关系：大小关系对象之间的关系：大小关系设计求解问题的方法：设计求解问题的方法：基本操作是基本操作是“比较两个数的大小比较两个数的大小”设第一个数为当前最大值，逐一比较其余设第一个数为当前最大值，逐一比较其余n-1个数，如某个数，如某数大于当前最大值，则当前最大值更新为新的数大于当前最大

11、值，则当前最大值更新为新的最大值最大值编程：编程：main ( ) int *d, M, i, max;scanf (”%d”, &M); d = (int *) malloc(sizeof(int) * M);for( i=0; iM; i+) scanf (”%d”, &di); max = d0; for( i=1; iM; i+) if ( max di) max = di; printf (”The max number is %fn”, max);free(d); .第 1515 页1.1 1.1 什么是数据结构什么是数据结构l非数值问题非数值问题例例2：已知学生选

12、课情况，安排课程考试的日程，要求：已知学生选课情况，安排课程考试的日程，要求在尽可能短的时间内完成考试。在尽可能短的时间内完成考试。学生选课情况表学生选课情况表 姓名姓名 选修课选修课1 选修课选修课2 选修课选修课3 杨润生杨润生 算法分析（算法分析（A） 形式语言（形式语言（B） 计算机网络（计算机网络（E）石石 磊磊 计算机图形学（计算机图形学（C） 模式识别模式识别 （D）魏庆涛魏庆涛 计算机图形学（计算机图形学（C） 计算机网络（计算机网络（E） 人工智能（人工智能（F）马耀先马耀先 模式识别（模式识别（D ） 人工智能（人工智能（F） 算法分析（算法分析（A）齐砚生齐砚生 形式语言

13、（形式语言（B） 人工智能（人工智能（F）.第 1616 页1.1 1.1 什么是数据结构什么是数据结构学生选课情况表学生选课情况表 姓名姓名 选修课选修课1 选修课选修课2 选修课选修课3 杨润生杨润生 算法分析（算法分析（A） 形式语言（形式语言（B） 计算机网络（计算机网络（E）石石 磊磊 计算机图形学（计算机图形学（C） 模式识别模式识别 （D）魏庆涛魏庆涛 计算机图形学（计算机图形学（C） 计算机网络（计算机网络（E） 人工智能（人工智能（F）马耀先马耀先 模式识别（模式识别（D ） 人工智能（人工智能（F） 算法分析（算法分析（A）齐砚生齐砚生 形式语言（形式语言（B） 人工智能（

14、人工智能（F） 建立模型建立模型 问题涉及的对象：课程问题涉及的对象：课程 课程之间的关系：同一学生选修的课程之间有某种课程之间的关系：同一学生选修的课程之间有某种“冲突冲突”关系。关系。 要求：同一个学生选修的课程不能安排在同一时间要求：同一个学生选修的课程不能安排在同一时间进行内考试。进行内考试。 .第 1717 页1.1 1.1 什么是数据结构什么是数据结构学生选课情况表学生选课情况表 姓名姓名 选修课选修课1 选修课选修课2 选修课选修课3 杨润生杨润生 算法分析（算法分析（A） 形式语言（形式语言（B） 计算机网络（计算机网络（E）石石 磊磊 计算机图形学（计算机图形学（C） 模式识

15、别模式识别 （D）魏庆涛魏庆涛 计算机图形学（计算机图形学（C） 计算机网络（计算机网络（E） 人工智能（人工智能（F）马耀先马耀先 模式识别（模式识别（D ） 人工智能（人工智能（F） 算法分析（算法分析（A）齐砚生齐砚生 形式语言（形式语言（B） 人工智能（人工智能（F）D DE EF FC CB BA A顶点：表示课程顶点：表示课程同一学生选修同一学生选修的课程用一条边连接的课程用一条边连接有边连接的课程不能有边连接的课程不能安排在同一时间考试安排在同一时间考试.第 1818 页D DE EF FC CB BA A1.1 1.1 什么是数据结构什么是数据结构l设计求解问题的方法设计求解问

16、题的方法课程考试可用图的着色法求解问题。课程考试可用图的着色法求解问题。每一种颜色代表一个考试时间，着上相同颜色的每一种颜色代表一个考试时间，着上相同颜色的顶点是可以安排在同一时间考试的课程；顶点是可以安排在同一时间考试的课程；用尽可能少的颜色为图的顶点着色，相邻的顶点用尽可能少的颜色为图的顶点着色，相邻的顶点着上不同的颜色。着上不同的颜色。A AC CE EF FB BD D如下是一种考试日程：如下是一种考试日程： 1: 算法分析算法分析(A) 计算机图形学计算机图形学(C) 2: 形式语言形式语言(B) 模式识别人工智能（模式识别人工智能（D) 3: 计算机网络计算机网络(E) 4: 人工

17、智能人工智能(F).第 1919 页1.1 1.1 什么是数据结构什么是数据结构 求解求解考试日程的流程考试日程的流程设：设：G表示课程关系图，表示课程关系图，V是图是图G中所有尚未着色的顶中所有尚未着色的顶点集合，点集合，NEW表示可以用新颜色着色的顶点集合。表示可以用新颜色着色的顶点集合。1)i=11)i=1；V = V = 图中所有顶点的集合图中所有顶点的集合 2)2)若若 V V 非空非空 DODO 置置 NEWNEW 为空集合；为空集合； 在在 V V 中取一点，找出所有与之中取一点，找出所有与之“不相邻不相邻”的顶点；的顶点； 将这些顶点加入将这些顶点加入 NEWNEW，从，从 V

18、 V 中去掉这些顶点中去掉这些顶点 （第（第 i i 天考试课程为天考试课程为 NEW NEW 中顶点所对应的课程）中顶点所对应的课程） 以某种形式输出以某种形式输出NEWNEW中顶点所对应的课程；中顶点所对应的课程； i = i+1i = i+1；3)3)若若 V V 空，结束空，结束 编程编程 存储图，集合存储图，集合 实现图实现图/ /集合的操作集合的操作.第 2020 页1.1 1.1 什么是数据结构什么是数据结构l数值问题与非数值问题的比较数值问题与非数值问题的比较数值问题数值问题* * 对象对象：len,wide,area len,wide,area 用数值表示用数值表示* * 对

19、象之间的关系对象之间的关系： area = len area = len widewide 用方程或函数表示用方程或函数表示* * 数据存储数据存储：可用程序设计：可用程序设计语言中的实型变量存储数据语言中的实型变量存储数据* * 问题求解方法问题求解方法：某种数值：某种数值计算方法求解计算方法求解 非数值问题非数值问题* * 对象对象：课程：课程用用课程名课程名表示表示* * 对象之间的关系对象之间的关系： 课程间有课程间有“冲突冲突”关系关系* * 数据存储数据存储：要保存数据及数据：要保存数据及数据之间的关系之间的关系* * 问题求解方法问题求解方法不能用数值表示不能用数值表示课程之间的

20、这种关系课程之间的这种关系不能用方程或函数表示不能用方程或函数表示.第 2121 页1.1 1.1 什么是数据结构什么是数据结构l19681968年美国年美国D.E.Knuth D.E.Knuth 教授出教授出版：版：The Art of Computer Programming计算机程序计算机程序设计技巧设计技巧开创了数据结构的开创了数据结构的最初体系。最初体系。计划共写计划共写7卷，然卷，然而出版三卷之后，已震惊世界，而出版三卷之后，已震惊世界，获得计算机科学界的最高荣誉获得计算机科学界的最高荣誉图灵奖，年仅图灵奖，年仅36岁。岁。l1938年出生，年出生，25岁毕业于加州理工学院数学岁毕

21、业于加州理工学院数学系，博士毕业后留校任教，系，博士毕业后留校任教，28岁任副教授。岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。岁时，加盟斯坦福大学计算机系，任教授。.第 2222 页1.1 1.1 什么是数据结构什么是数据结构l什么是数据结构？什么是数据结构？ 数据结构数据结构是一门研究是一门研究非数值非数值问题中问题中计算机的计算机的操作对象操作对象以及它们之间的以及它们之间的关系关系和和操作操作的学科的学科。l数据结构所研究的问题数据结构所研究的问题 非数值数据之间的结构关系，及如非数值数据之间的结构关系，及如何表示，如何存储，如何处理。何表示，如何存储，如何处理。.第 232

22、3 页1.1 1.1 什么是数据结构什么是数据结构l数据结构随着程序设计的发展而发展数据结构随着程序设计的发展而发展结构化阶段：数据结构算法程序结构化阶段：数据结构算法程序面向对象阶段：面向对象阶段：(数据结构算法数据结构算法)程序程序l 数据结构的发展并未终结数据结构的发展并未终结研究的范围不断扩展，算法不断更新研究的范围不断扩展，算法不断更新描述手段、使用语言不断更新描述手段、使用语言不断更新.第 2424 页第第1 1章章 绪论绪论 1.1 1.1 什么是数据结构什么是数据结构 1.2 1.2 基本概念和术语基本概念和术语 1.3 1.3 抽象数据类型抽象数据类型 1.4 1.4 算法和

23、算法分析算法和算法分析.第 2525 页1.2 1.2 基本概念和术语基本概念和术语l数据数据(data)(data)：客观对象的符号表示。：客观对象的符号表示。 l数据元素数据元素(data element)(data element)：数据的基本单位，：数据的基本单位，在计算机程序中作为一个整体考虑和处理，通在计算机程序中作为一个整体考虑和处理，通常具有完整确定的实际意义。常具有完整确定的实际意义。( (节点、顶点、节点、顶点、记录记录) )l数据项数据项(data item)(data item)：数据不可分割的最小标：数据不可分割的最小标识单位。一个数据元素可由若干数据项组成，识单位。

24、一个数据元素可由若干数据项组成，通常不具有完整确定的实际意义。通常不具有完整确定的实际意义。( (字段字段) )00010001刘建国刘建国男男1949100119491001工程师工程师00020002黄黄 红红女女1965050619650506助工助工00030003张张 华华女女1946111819461118高工高工.第 2626 页1.2 1.2 基本概念和术语基本概念和术语l数据结构数据结构(data structure)(data structure)：相互之间相互之间存在一种或多种特定关系的、具有相同存在一种或多种特定关系的、具有相同特征的数据元素的集合。特征的数据元素的集合

25、。数据结构：数据结构：带有带有结构结构和和操作操作的数据元素的数据元素集合。集合。 结构结构：数据元素之间的关系；：数据元素之间的关系； 操作操作：对数据的加工处理：对数据的加工处理 。.第 2727 页1.2 1.2 基本概念和术语基本概念和术语l每种结构讨论两方面问题：每种结构讨论两方面问题：1) 数据的数据的逻辑结构逻辑结构：从具体问题抽象出来：从具体问题抽象出来的数据模型，反映了事物的组成及事物之间的的数据模型，反映了事物的组成及事物之间的逻辑关系。逻辑关系。 2) 数据的数据的存储结构存储结构(也称为物理结构也称为物理结构)：解决：解决各种逻辑结构在计算机中的物理存储和表示。各种逻辑

26、结构在计算机中的物理存储和表示。 同一种逻辑结构可以采用不同的表示方式，同一种逻辑结构可以采用不同的表示方式，即采用不同的映射关系来建立数据的逻辑结构即采用不同的映射关系来建立数据的逻辑结构到存储结构的转换。到存储结构的转换。.第 2828 页1.2 1.2 基本概念和术语基本概念和术语：数据的逻辑结构：数据的逻辑结构l数据的逻辑结构：数据的逻辑结构：数据之间的结构关系，是具数据之间的结构关系，是具体关系的抽象。有四种体关系的抽象。有四种集合集合：数据元素间除：数据元素间除“同属于一个集合同属于一个集合”外，外，无其它关系无其它关系线性结构线性结构：一个对一个，如线性表：一个对一个，如线性表/

27、栈栈/队列队列树形结构树形结构：一个对多个，如树：一个对多个，如树图状结构图状结构：多个对多个，如图：多个对多个，如图.第 2929 页1.2 1.2 基本概念和术语基本概念和术语：数据的逻辑结构：数据的逻辑结构l线性结构线性结构学生基本情况登记表，记录了每个学生的学号、姓名学生基本情况登记表，记录了每个学生的学号、姓名、专业、政治面貌。按学生的学号顺序排列。、专业、政治面貌。按学生的学号顺序排列。 001001003003002002004004006006005005008008007007学生间学号顺序关系学生间学号顺序关系是一种线性结构关系是一种线性结构关系线性结构：线性结构：除第一个

28、元除第一个元素和最后一个元素外，素和最后一个元素外，其他元素都有且仅有一其他元素都有且仅有一个个直接前趋直接前趋，有且仅有，有且仅有一个一个直接后继直接后继。学号学号 姓名姓名 专业专业 政治面貌政治面貌001001王洪王洪 计算机计算机 党员党员002 002 孙文孙文 计算机计算机 团员团员003003谢军谢军 计算机计算机 团员团员004004李辉李辉 计算机计算机 团员团员005005沈祥福沈祥福 计算机计算机 党员党员006006余斌余斌 计算机计算机 团员团员007007巩力巩力 计算机计算机 团员团员008008孔令辉孔令辉 计算机计算机 团员团员.第 3030 页1.2 1.2

29、 基本概念和术语基本概念和术语：数据的逻辑结构：数据的逻辑结构l树形结构树形结构假设某家族有假设某家族有1010个成员个成员A A、B B、C C、D D、E E、F F、G G、H H、I I、J J，他们之间的血缘关系可以用图表，他们之间的血缘关系可以用图表示。示。J JI IA AC CB BD DH HG GF FE E树形结构：树形结构：每一个元素只有每一个元素只有一个一个直接直接前趋，有前趋，有0个个或或多个多个直接后继。直接后继。.第 3131 页1.2 1.2 基本概念和术语基本概念和术语：数据的逻辑结构：数据的逻辑结构l图形结构图形结构 工程进度图。工程进度图。图形结构：图形

30、结构：每一个元素可以有每一个元素可以有0个个或或多个多个直直接前趋，有接前趋，有0个个或或多个多个直接后继。直接后继。 V1V1 V0V0 V2V2 V3V3 V4V4 V5V5 V6V6.第 3232 页1.2 1.2 基本概念和术语基本概念和术语：数据的逻辑结构：数据的逻辑结构数据结构的表示数据结构的表示图示表示图示表示 图示表示是由顶点和边构成的图，其中顶图示表示是由顶点和边构成的图，其中顶点表示数据，边表示数据之间的结构关系。点表示数据，边表示数据之间的结构关系。二元组表示二元组表示 二元组表示是用一个二元组（二元组表示是用一个二元组（D D，S S）表示）表示数据结构，其中数据结构，

31、其中 D D 是数据元素集合，是数据元素集合，S S 是是 D D 上关系的集合。上关系的集合。.第 3333 页1.2 1.2 基本概念和术语基本概念和术语：数据的逻辑结构：数据的逻辑结构例：学生基本情况表的二元组表示（例：学生基本情况表的二元组表示（D，S） 001001003003002002004004006006005005008008007007D = 001D = 001，002002，003003，004004，005005，006006，007007，008 008 S = R S = R R = , , , R = , , , , , , , , , .第 3434 页1.2 1.2 基本概念和术语基本概念和术语：数据的逻辑结构：数据的逻辑结构例：家族树的二元组表示（例：家族树的二元组表示（D，S） D = A，B，C，D，E，F，G，H，I，J S = R R = , , , , , , , , J JI IA AC CB BD DH HG GF FE E.第 3535 页1.2 1.2 基本概念和术语基本概念和术语：数据的存储结构：数据的存储结构l数据的存储结构数据的存储结构逻辑结构逻辑结构：从操作对象抽象出来的数学模型。：从操作对象抽象出来的数学模型。存储结构存