《数据结构与算法设计》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(inti=0;isize;i+)If(strcmp(dictionaryi,target)=0)returngetDocumentsbyWord(i);,第8页,关键词只有属于同一词典的关系（集合关系）查找不命中时，需要遍历所有关键词,1.1什么是数据结构,排序的办法char*dictionary=(char*)maolloc();char*target=;sort(dictionary);for(inti=0;isize;i+)intret=strcmp(dictionaryi,target);If(ret=0)returngetDocumentsbyWord(i);elseif(ret0)returnNULL;,第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=lenwidthdepth设计求解问题的方法编程main()intlen,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=lenwide用方程或函数表示*数据存储：可用程序设计语言中的实型变量存储数据*问题求解方法：某种数值计算方法求解,非数值问题*对象：课程用课程名表示*对象之间的关系：课程间有“冲突”关系*数据存储：要保存数据及数据之间的关系*问题求解方法,不能用数值表示,课程之间的这种关系不能用方程或函数表示,第21页,1.1什么是数据结构,1968年美国D.E.Knuth教授出版：TheArtofComputerProgramming计算机程序设计技巧开创了数据结构的最初体系。计划共写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)：客观对象的符号表示。数据元素(dataelement)：数据的基本单位，在计算机程序中作为一个整体考虑和处理，通常具有完整确定的实际意义。(节点、顶点、记录)数据项(dataitem)：数据不可分割的最小标识单位。一个数据元素可由若干数据项组成，通常不具有完整确定的实际意义。(字段),第26页,1.2基本概念和术语,数据结构(datastructure)：相互之间存在一种或多种特定关系的、具有相同特征的数据元素的集合。数据结构：带有结构和操作的数据元素集合。结构：数据元素之间的关系；操作：对数据的加工处理。,第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，008S=RR=,第34页,1.2基本概念和术语：数据的逻辑结构,例：家族树的二元组表示（D，S）,D=A，B，C，D，E，F，G，H，I，JS=RR=,第35页,1.2基本概念和术语：数据的存储结构,数据的存储结构逻辑结构：从操作对象抽象出来的数学模型。存储结构：逻辑结构在计算机中的表示,包含“数据元素”的映象和“关系”的映象。实质是内存分配，具体实现依赖于计算机语言。数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。一种数据的逻辑结构可以用多种存储结构来存储；而采用不同的存储结构，其数据处理的效率往往是不同的。,第36页,1.2基本概念和术语：数据的存储结构,常见的存储结构顺序存储方式链式存储方式散列方式索引方式。顺序存储方式：借助元素在存储器中的相对位置来表示数