数据结构 主讲人：张敏.pptVIP

数据结构主讲人：张敏 考核方法 考核要求： 平时成绩：30分 = 书面作业与考勤10 + 期中考试5 + 上机15； 期末考试：70分 网上答疑 作业在布置后的一周内交，抄袭不作为成绩记载 绪论 为什么要学习数据结构？ 什么是程序、软件？ N.沃思（Niklaus Wirth)教授提出： 程序=算法+数据结构 以上公式说明了如下两个问题： （1）数据上的算法决定如何构造和组织数据（算法→数据结构）。 （2）算法的选择依赖于作为基础的数据结构（数据结构→算法）。 软件=程序+文档（软件工程的观点） 电子计算机的主要用途： ?早期： 主要用于数值计算。 ?后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。 数值计算解决问题的一般步骤： 数学模型→选择计算机语言→编出程序→测试→最终解答。 数值计算的关键是：如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 非数值计算问题： 数据元素之间的相互关系一般无法用数学方程加以描述 数据结构与问题求解 1. 在计算机中建立一个与实际问题有比较密切对应关系的模型； 2. 计算机内部的数据 表示了需要被处理的实际对象，包括其内在的性质和关系； 3. 处理这些数据的程序 则模拟对象领域中的实际过程； 4. 将计算机程序的运行结果 在实际领域中给予解释，便得到实际问题的解。 例1、图书馆的书目检索系统自动化问题(p1) 例3 多叉路口交通灯管理问题 例4: 田径赛的时间安排问题（无向图的着色问题） ： 设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。 （1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 100米 200米 A B C D E F （2）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不能同时比赛）。 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？ 因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 数据结构课程的形成和发展： 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。 《数据结构课程》所处的地位： 什么是数据结构 《DS》主要研究内容： 数据的各种逻辑结构和物理结构，以及它们之间的相应关系； 对每种结构定义相适应的各种运算； 设计出相应的算法； 分析算法的效率。 数据结构的三个研究方面 数据的逻辑结构（算法设计的基础） 数据的存储结构（算法实现的基础） 数据的操作算法 基本术语 数据 计算机化的信息。如数字、文字、图像、声音等 数据元素（元素、结点、记录、文件） 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 信息处理的基本单位。如书本、学生等 数据项（域、属性） 不可再分的数据单元。如书号、书名等 数据对象 是性质相同的数据元素的集合。是数据的一个子集。 如书库等 数据结构 相互之间存在一种或多种特定关系的数据元素的集会。 基本术语 数据的逻辑结构 数据元素集合及元素间的相互关系 按元素间的关系分类 逻辑结构的形式定义 D_S = (D, S)，即由元素集D和关系集S组成的二元组 集合：元素间相互独立 基本术语 例如 复数 Complex = (D, S) D = {d1, d2} //实部，虚部 S = {d1, d2} 研究小组 Group(D, S) D = {T, G1, …, Gn, S11, … , Snm} S = {S1, S2} S1 = {T,Gi | 1=i=n} S2 = {Gi, Sij | 1=i=n, 1=j=m } 基本术语 线性结构：元素间一对一关系 例：线性表、队列、堆栈 非线性结构： 树形结构：元素间一对多关系 数据的逻辑结构 从逻辑关系上描述数据，与数据的存储无关； 从具体问题抽象出来的数据模型； 与数据元素本身的形式、内容无关； 与数据元素的相对位置无关。 基本术语 数据的存储结构（物理结构） 数据的逻辑结构在计算