英文译名：DATA STRU CTU RE THM 授课对象：计算机科学与技术本科生 课程网站：ftp:///.users///// 数据结构与算法 教学目的：（１）学会分析和研究计算机处理的数据对象的特性，掌握 常用数据结构内在的逻辑关系、在机内的存储表示，掌 握常用数据结构上的运算操作的动态性质和执行算法． （２）能够为实际应用选择适当的数据结构、存储结构和相 应算法； （３）初步掌握算法性能的分析方法。 考核要求：（１）考试：７０％；（２）作业：１０％； （３）实验：２０％；（４）缺勤：－１０％ 第1章绪论 1.1数据结构的研究对象 1.2数据结构的发展概况 1.3抽象数据型(ADT) 1.4逐步求精的程序设计方法 1.1数据结构的研究对象 1.1.1基本概念和术语 1.1.2四种基本的数据结构 1.1.3数据结构的研究对象 返回 1.1.1基本概念和术语一.客观世界与计算机世界的关系 客观世界 概念世界 机器世界 映象 抽象 映象 实现 (逻辑模型) 映象 模拟 客观世界与计算机的关系 计算机科学是研究信息表示和信息处理的科学。
信息 在计算机内是用数据表示的。用计算机解决实际问题的实 质可以用下图表示： 1.1.1基本概念和术语 二.基本概念和术语 1.数据: 数据是用于描述客观事物的数值、字符，以及一切可 以输入到计算机中的并由计算机程序加以处理的符号的集 合。其范围随着计算机技术的发展而不断发展。 2.数据元素 数据的基本单位是数据元素，在计算机程序中通常作 为一个整体进行考虑和处理。 3.数据项 是数据的不可分割的最小单位，一个数据元素可由若 干个数据项组成。 4.数据对象 性质相同的元素的集合叫做数据对象。 5.结点 数据元素在机内的位串表示，即数据元素在计算机内 的映象。 6.域/字段 当数据元素由若干个数据项组成时，位串中对应于各 个数据项的子串称为域/字段，是数据元素中数据项在计 算机中的映象。 7.信息表 计算机程序所作用的一组数据通常称为信息表，是数 据对象在计算机中的映象。 1.1.1基本概念和术语 二.基本概念和术语 8.数据结构 数据结构指的是数据元素之间的相互关系，这种关系 是抽象的，即并不涉及数据元素的具体内容。是数据元素 及其相互间的关系的数学描述。 9.逻辑结构和存储结构 (1)逻辑结构 数据结构中描述的是数据元素之间的抽象关系(逻辑 关系)，称为逻辑结构。
(2)存储结构/物理结构 数据结构在计算机中的表示（映象）称为存储结构/物 理结构。 1.1.1基本概念和术语 二.基本概念和术语 (3)数据元素之间的关系（逻辑结构）在计算机中有两种表示方法：顺序映象(表示)和非顺序映象(表示)，从而 导致两种不同的存储结构：顺序结构和链式结构。 顺序映象（表示）的特点是借助数据元素在存储器中 的相对位置来表示数据元素之间的逻辑关系。 非顺序映象（表示）的特点是借助指示数据元素存储 地址的指针来表示数据元素之间的逻辑关系。 1.1.1基本概念和术语 二.基本概念和术语 返回 1.1.2四种基本的逻辑结构 1.集合结构 结构中的数据元素之间除了属于同一个集合的关系 之外，别无其他关系。关系比较松散，可用其他结构来表 结构中的数据元素之间存在一个对一个的关系，即线性关系，每个元素至多有一个直接前导和后继。 2.线性结构 1.1.2四种基本的逻辑结构 3.树型结构 结构中的数据元素之间存在一个对多个的关系，即层 次关系，即每一层上的元素可能与下层的多个元素相关， 而至多与上层的一个元素相关。 结构中的数据元素之间存在多个对多个的关系，即任 意关系，任何元素之间都可能有关系。
。 4.网状/图型结构 返回 一般将逻辑结构分为线性结构（2）和非线性结构（1 ，3，4 ）两种。 结构中的数据元素之间存在多个对多个的关系，即任 意关系，任何元素之间都可能有关系。。 1.1.4数据结构的研究对象 数据结构的研究对象(研究内容) 1.数据对象的结构形式,各种数据结构的性质(逻辑结 2.数据对象和关系在计算机中的表示(物理结构/存储结构); 3.数据结构上定义的基本操作(算法); 4.算法的效率; 5.数据结构的应用,如数据分类,检索. 返回 1.2数据结构的发展概况1.程序设计方法学的发展极大地促进了数据结构的发展 2.数据结构在计算机科学中的地位 (1)计算机科学及其应用的发展时数据结构成为独立学科. (2)以数据为中心的程序设计方法推动了数据结构的发展. 面向过程的程序设计的特点是以程序为中心，侧重于建立程序，程序在简单的数据结构上进行复杂的运算，软件设计的 主要工作就是设计求解问题的过程。注重于程序设计技巧， 适合于数值计算。 结构化特别是面向对象的程序设计以数据结构为中心，系统采用复杂的数据结构来描述系统状态，程序围绕数据结构 进行加工。这种编程语言更适合于非数值计算。
(1)是计算机科学的一门专业基础和核心课程。 (2)是学习、设计和实现操作系统、编译系统、数据库系统和 其它应用系统的重要基础。 返回 1.3抽象数据型(ADT) 1.3.1抽象数据型的定义 1.3.2数据型,数据结构和ADT 1.3.3抽象数据型的规格描述 返回 1.3.4抽象数据型的实现 1.3.5多层次抽象技术 1.3.6多层次抽象技术 1.3.1抽象数据型的定义 一.抽象数据型的定义 1.定义: 是一个数学模型和在该模型上定义的操作集合的 总称。 ADT是程序设计语言中数据类型概念的进一步推广和进一步抽象。 ADT int=({x|xZ}，{+,-,*,/,%,,==}) 2.ADT的优点 使用者只要知道这些操作的用途就可以编程序了；至 于这些操作是怎样实现的，以及整型数在内存中是如何表 示的，并不影响使用者所编程序的编码形式。 1.3.1抽象数据型的定义 二.抽象数据型的实现 1.抽象型实现的含义 就是将ADT转换成程序设计语言的说明语句，加上对 应于该ADT中的每个操作的函数。换句话说，就是用适当 的数据结构来表示ADT中的数学模型,并用一组函数来实 现该模型上的各种操作。
2.注意事项 (1)同一数学模型上定义不同的操作集，则它们代表不 同的ADT; (2)把ADT的描述与用某中程序设计语言实现ADT加以 区别，这是大型程序设计中当前的发展趋势。如下图所示: 1.3.1抽象数据型的定义三.抽象数据型图示 ADT 规格 描述 ADT 实现 语法 描述 语义 描述 数据结构 (表示) 操作(算法)的 实现(函数) 抽象数据型(ADT)图示 返回 1.3.2数据型、数据结构和ADT 1.三个概念的各自含义及相互关系 (1)各自含义 数据型是该类型变量的存储格式和所有可能取值的集合; 数据结构则是抽象数据型中数学模型的表示; 抽象数据型是一个数学模型及在该模型上定义的操作集 的总称。 (2)相互关系 数据型是根据数据结构分类的，同类型的数据元素的数 据结构相同； 数据结构是ADT中数学模型的表示； ADT是数据类型的进一步推广和进一步抽象。 2.信息聚集的三种方式 数组、结构（体）和文件 返回 1.3.3抽象数据型的规格描述 一.ADT的规格描述 即ADT的形式化描述，包括语法规格和语义规格描述 规格描述必须具有: (1)完整性: 要能反映所定义的抽象数据型的全部特性 (2)统一性: 应是一个前后协调的整体，不应自相矛盾 (3)通用性: 所定义的抽象数据型应适用于尽量广泛的对象 (4)独立性: 应尽可能不依赖于程序语言 (1)是程序操作/算法实现的依据; (2)是作为与程序并存的文档,用于程序的调试和维护。
二.规格描述的作用 三.规格描述原则 1.3.3抽象数据型的规格描述 ADT的规格描述方法1.语法规格描述 就是给出所指定的操作的名称以及输入输出类型； 2.语义规格描述 给出符合语法规定的表达式的语义,即表达形式所起 的作用是什么或者效果是什么或者是让程序作什么(但不 涉及怎么做) 3.ADT规格描述方法 首先描述它的定义域; 然后描述各个操作及其作用(给予法和语义规格描述) ADT的规格描述方法4.规格描述举例（ADT栈） 语法规格描述部分： type Stack[]; ()Stack, PUSH(,Stack) Stack, POP(Stack)Stack{ NED} TOP(Stack){ NED} EMPTY(Stack); 语法部分给出所指定的操作的名称以及输入输出类型 首先，ADT栈是同类单元的集合; 然后，用语法和语义规格来描述各个操作及其作用， 并且体现ADT栈的后进先出LI FO的特征。 1.3.3抽象数据型规格描述 四.ADT的规格描述方法 4.规格描述举例（ADT栈） 语义规格描述部分： stk:Stack,elm:; POP()=, // NED POP(PUSH(elm,stk))=stk, TOP()= NED, TOP(PUSH(elm,stk))=elm, EMPTY()=TRUE, EMPTY(PUSH(elm,stk))=FALSE; 语义部分主要有一组等式组成，严格规定了各种操作的 功能及相互关系 1.3.3抽象数据型规格描述 四.ADT的规格描述方法 5.注意事项 (1)对于同一ADT，在同样语法定义之下可以有不同语 义定义; (2)不同的语义定义，将影响ADT的实现，因此要做到 语义定义和是实现的协调一致。
返回 1.3.4抽象数据型实现 一.ADT的实现原则 (1)应符合规格描述的定义； (2)应有尽可能好的通用性； (3)应尽可能具有良好的独立性，在结构上应成为独立 的模块；将内部细节屏蔽起来。 二.ADT的实现举例（ADT栈的带头结点的链式实现） 1)数据结构描述 {FALSE,TRUE}; node{ ; node next; };//结点的型 node stack;//栈的型 1.3.4抽象数据型的实现二.ADT的实现举例（ADT栈的带头结点的链式实现） 基本操作的实现stack () s=； /s=(node )((node));/ s->next=NULL； 基本操作的实现void PUSH(elm,stk) ;stack stk; s=; s->val=elm; s->next=stk->next; stk->next=s; next stk 1.3.4抽象数据型的实现二.ADT的实现举例（ADT栈的带头结点的链式实现） 基本操作的实现void POP(stk) stack stk; (stk->next){/stk->next!=NULL*/ s=stk->next; stk->next=s->next; stk 1.3.4抽象数据型的实现二.ADT的实现举例（ADT栈的带头结点的链式实现） 基本操作的实现(stk) stack stk; (stk->next) (stk->next->val)； else ; 1.3.4抽象数据型的实现二.ADT的实现举例（ADT栈的带头结点的链式实现） 基本操作的实现 EMPTY(stk) stack stk; (stk->next) FALSE; else TRUE; 1.3.4抽象数据型的实现二.ADT的实现举例（ADT栈的带头结点的链式实现） 返回 1.3.5多层次抽象技术 1.逐层抽象方法 对于较复杂的数据类型，先将较简单、较基本的数据 类型抽象出来,给出定义；再用已定义的数据类型去定义 更复杂的数据类型,完成对后者的抽象。
就是说，用已定 义的类型来表述正要定义的类型的定义域，并用前者的 操作来表述后者的操作这就是所谓逐层抽象的方法。 逐层抽象实质是用已知的简单数据类型定义更复杂的 数据类型。 2.优点 (1)由于在定义高层数据类型时不必考虑低层数据类型及其 操作的内部细节,因而对复杂数据类型进行抽象可以简化许多 琐事。 (2)多层次抽象化通常可以采用自底向上的方式进行，先抽 象出最基本的数据类型，然后利用它们定义上一层数据类型 ，如此逐层向上，直至到达最高层的数据类型为止,这样可以 防止低层次倒过来引用高层数据类型，保证整个系统的有序 层次结构。 多层次抽象化的最终目的是建立最高层的数据类型，因此 低层应该服从高层的要求。自底向上方式是底层的抽象带有 一定的盲目性，在抽象过程中，可能从高层返回低层作修正 ，也就是不得不穿插一些自顶向下的过程。 1.3.5多层次抽象技术 3.缺点 返回 1.3.6抽象数据型的优点 抽象数据型的优点 采用抽象数据型的方法进行软件（特别是大型软件） 系统的设计，具有许多明显的优点： 首先，它降低了软件设计的复杂性。 其次，抽象数据型可提高程序的可读性和可维护性。 第三，由于抽象数据型的使用降低了程序的复杂度， 使程序的各部分相对分离，因而程序的正确性容易得到 保证。
第四，有利于软件重用。 返回 1.4逐步求精的程序设计方法1.4.1如何求解一个问题 算法的定义1.计算 能由一个给定的计算模型机械地执行的规则(或步 骤)序列称为该计算模型的一个计算. 一个计算机程序是一个计算(计算模型是计算机);计算可能永远不停止—不是算法. 2.算法 是一个满足下列条件的一个计算： (1)有穷性/终止性：总是在执行有穷步后停止; (2)确定性：每一步必须有严格的定义和确定的动作; (3)能行性：每个动作都能被精确地机械执行; (4)输入：有0个和多个满足约束条件的输入; (5)输出：有一个或多个满足约束条件的结果. 1.4逐步求精的程序设计方法 1.4.1如何求解一个问题 算法的逐步求精就是对用自然语言等描述的算法逐步细致化、精确化和 形式化，追求的目标是把算法变成可以执行的程序。 1.4逐步求精的程序设计方法 1.4.1如何求解一个问题 二.求解问题的一般过程 1.模型化：对实际问题进行分析，选择适当的数学模 型来描述问题，即模型化; 2.确定算法：根据模型，找出解决问题的方法(算法); 3.逐步求精：就是对用自然语言等描述的算法逐步细 致化、精确化和形式化，这一阶段可能包括多步求精。
当逐步求精到某一步时，根据程序中所使用的数据形式数据结构与算法设计，定义若干ADT，并且用ADT中的操作代替对应的非形 式语句； 4.ADT的实现：对每个ADT数据结构与算法设计 DATASTRUTHMRETHMTHMTHMTHMTHM授课，选择适当的数据结构表 示数学模型，并用相应的函数实现每个操作。 1.4逐步求精的程序设计方法 1.4.2算法逐步求精 例1.4.2交叉路口的交通安全管理问题 问题描述： 一个具有多有多条通路的交叉路口,当允许 某些通路上的车辆在交叉路口拐弯时,必 须对其他一些通路上的车辆加以限制,不允 许同时在交叉路口拐弯,以免发生碰撞.所 有这些可能的拐弯组成一个集合. 图1.5一个交叉路口基本要求： 把这个集合分成尽可能少的组 ,使得每组中所有的拐弯都能 同时进行而不发生碰撞. 这样,每 组对应一个指挥灯,因而实现了 用尽可能少的指非灯完成交叉 路口的管理. 有5条组成的交叉路口,其中有2条 路是单行道,把从一条路到另一条 路的通路称为拐弯,有的拐弯 可以同时通过,有些拐弯不能同 时通过,共有13个拐弯.要求: (1)设置一组交通灯,实现安全管理 (2)使交通灯的数目最少. 10 1.4逐步求精的程序设计方法 1.4.2算法逐步求精 例1.4.2的求解过程 模型化： (1)用图作为交叉路口的数学模型;(2)每个拐弯对应图中的一个顶 点;(3)若两个拐弯不能同时进行,则用用一条边把这两个拐弯所 对应的两个结点连接起来，并且说这两个顶点是相邻的。
AB AC AD BA DC ED BC BD EA DA DB EB EC 一个交叉路口1.4逐步求精的程序设计方法 1.4.2算法逐步求精 确定算法： (1)穷举法;(2)试探法 (3)贪心法 贪心算法的思想是首先用 第一种颜色对图中尽可能多 的顶点着色(尽可能多表现 出贪心)然后用第二种颜 色对余下的顶点中尽可能多 的顶点着色如此等等，直 至所有的顶点都着完色。 AB AC AD BA DC ED BC BD EA DA DB EB EC 当用一种新颜色对余下的顶点着色时我们采取下列步骤: （1）选取某个未着色的顶点，并且用新颜色对它着色。 （2）扫描所有未着色的顶点集，对其中的每个顶点，确定它是否 与已着新颜色的任何顶点相邻。若不相邻，则用新颜色对它着色。 1.4逐步求精的程序设计方法 1.4.2算法逐步求精 用C语言描述的"贫心"算法如下: void (G,) GRAPH ; /类型GRAPH和SET有待具体说明/ /本程序把G中可以着同一色的顶点放入/ while(G中有未着色的顶点v) 其中，G是被着色的图，的初值为空，算法执行的结果形成可以着相同颜色的顶点的集合。
只要重复调用算法，直到图中 的所有顶点都被着色为止，即可求出问题的解。 1.4逐步求精的程序设计方法 1.4.2算法逐步求精 逐步求精：第一步求精： void (G,) GRAPH G;SET ; /类型GRAPH和SET有待具体说明/ ; while(G中有未着色的顶点v){(3.1) found=0;/found的初值为false/ (3.2) (中的每一个顶点w）(3.3) if(v与w相邻) (3.4) found=1; (3.5) if(found==0){ /v与中的任何顶点都不相邻/ 111.4逐步求精的程序设计方法 1.4.2算法逐步求精 逐步求精：第二步求精： void (GRAPH ) ; =%; v=G中第一个未着色的顶点； while /G中还有未着色的顶点v/found=0; w=中的第一个顶点； while(w!=0){ /中的顶点还没取尽/ if(v与w相邻) found=1; w=中的下个顶点； if(found==0){对v着色； 将v放入； 1.4逐步求精的程序设计方法1.4.2算法逐步求精 逐步求精：第三步求精： 由上一步求精的结果可见，算法中大部分操作都归结为对图和集合的操作 。
设G和S分别是抽象数据型GRAPH和SET的实例，我们在G上规定如下 操作： (1)(G)返回G中的第一个未加标记的（未着色的）元素；若 G中没有这样的元素存在，则返回NULL。 (2)EDGE(v,w,G)若v和w在G中相邻，则返回true，否则返回false。 (3)MARK(v,G)标记G中的元素v。 (4)ADDG(v,G)将元素v放入G中。 (5)NEXTG(G)返回G中下一个未标记得元素，若G中没有这样的元 素存在，则返回NUL。 在S上规定如下操作： (1)(S)将集合S置空。 (2)(S)返回S中的第一个元素；若S为空集，则返回NULL。 (3)NEXTS(S)返回S中的下一个元素；若S中没有下一个元素，则返 回NULL。 (4)ADDS(v,S)将v放入S中。 1.4逐步求精的程序设计方法 1.4.2算法逐步求精 逐步求精：第三步求精： void (G,) GRAPH G;SET ; /类型GRAPH和SET有待说明/ ; v,w;/可以自定义/ (); v=(G); while(v!=NULL){ found=0; w=(); while(w!=NULL){ if(EDGE(v,w,G)) found=1; w=NEXTS(); 1.4逐步求精的程序设计方法1.4.2算法逐步求精 ADT的实现： 按上述函数，最后一步工作就是给出类型的定义和实 现抽象数据型GRAPH及SET。
此后数据结构与算法设计，上述函数就是可执的程序了。 12 1.5本书采用的类语言描述 一、关于本书采用的类语言描述： 输入输出约定(cin new和 其他二、关于引用类型： 所谓的引用就是给变量对象起个别名．换句话说就是这 个别名和原来的变量对象共用一个地址． 无论对原变量对象或对其引用的修改其实都是对同一地 址内容进行修改因而变量和对它的引用总具有相同的值． Ｃ＋＋用引用运算符＆来定义一个引用类型．如 ｉｎｔｎｕｍ＝５０ ｉｎｔ＆ｒｅｆ＝ｎｕｍ／／类型名＆引用名＝同类型变量的值 ｎｕｍ＝ｎｕｍ＋３０／／ｎｕｍ、ｒｅｆ均为８０ ｒｅｆ＝ｒｅｆ＋１０／／ｎｕｍ、ｒｅｆ均为９０ 1.5本书采用的类语言描述 1.引用与函数参数----引用调用举例 ＃ｉｎｃｌｕｄｅ＜ｉｏｓｔｒｅａｍ．ｈ＞ ｖｏｉｄＳｗａｐｉｎｔ＆ａｉｎｔ＆ｂ／／ｉｎｔｉｎｔｉｎｔ＊ｉｎｔ＊ ｖｏｉｄｍａｉｎ ｉｎｔｘ５ｙ１０／／Ｃ＋＋的初始化形式＜＝＞ｘ＝５ｃｏｕｔ＜＜＂ｘ＝＂＜＜ｘ＜＜＂ｙ＝＂＜＜ｙ＜＜ｅｎｄｌ 1.5本书采用的类语言描述2.返回引用的函数 是可以使该函数出现在运算符的左边(其他情况一个函数不能 成为赋值表达式的左值). 函数返回一个引用的主要目的 返回引用的函数举例 # int a[]={2,4,6,8,10,12}; int &index(int () index(3)=16;//a[3]=
文章来源:https://www.docin.com/touch_new/preview_new.do?id=97698841