数据结构ds-1.ppt

数 据 结 构 说明 总学时： 48(学时)= 36（课时）+ 12（实验） 行课时间:第 1 ~9周 周学时:平均每周 4 学时 上机安排待定 考试时间：课程结束 第8、11、12 章的内容为自学内容； 目录中标有 ** 的内容(除递归外)不作要求。 上机安排 指导老师: 时间： 地点:计算机学院机房 教材与参考书 严蔚敏，《数据结构》，清华大学出版社 Clifford A. Shaffer, 《数据结构与算法分析》，电子工业出版社 Sartaj Sahni, 《数据结构、算法与应用》,机械工业出版社 严蔚敏，《数据结构题集》，清华大学出版社 2.《数据结构》课程的性质与地位 学生的考核资格按下述原则审查： 学生有以下情况之一者，不能参加课程成绩考核，该课程的考核成绩以零分处理。在确定学籍处理、授予学士学位时，该门课程以考核不及格门次参加统计。 全期旷课累计达该课程教学时数五分之一（含五分之一）以上者； 全期缺交该课程任课教师布置作业三分之一（含三分之一）以上者；或全期所交该课程作业，虽达到任课教师布置作业三分之二以上，但所交作业的准确度、整洁度有二分之一不合格者； 全期缺做该课程实习、实验或缺交实习、实验报告达三分之一（含三分之一）以上者；或全期参加该课程实习、实验，所交实习、实验报告都在三分之二以上，但有二分之一不合格者； 未经批准或未办理选课手续，擅自修读该门课程者。 目 录 第一章：绪论 第二章：线性表 第三章：栈和队列 第四章：串 第五章：数组和广义表 第六章：树和二叉树 第七章：图 第九章：查找 第十章：内部排序 第一章 绪论 1. 1 什么是数据结构 数据结构的引论 例1 图书馆的书目检索系统自动化问题 在书目自动检索系统中可以建立一张按等录顺序号排列的书目文件和三张分别按书名、作者名和分类号顺序排列的索引表，如下所示： 例2: 计算机和人的对弈问题 对奕的过程是在一定的规则下随机进行的,因此,计算机必须对对弈过程之中可能发生的情况以及相应的对策都考虑周全.这个关系不是线形的,从一个棋盘可以派生出几个格局,如下图: “树根”是对奕开始之前的棋盘格局,而所有的“叶子”是可能出现的结局,对奕的过程就是从树根沿树叉到达某个叶子的过程. 例3: 多叉路口交通灯的管理问题 可以把这类交通,道路的问题当作一种“图”的结构：一个顶点表示一条通道,而通道之间的矛盾的关系以两个顶点之间的连线表示.如下图所示: 结论：综合上面三个例子,描述这类非数值计算性问题的数学模型不再是数学方程,而是诸如表、树和图之类的数据结构. 数据结构定义: 数据结构是一门非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科. 数据结构的地位 《数据结构》是计算机科学中一门综合性的专业基础课。可以认为数据结构是介于数学、计算机硬件、计算机软件三者之间的一门核心课程。 1. 2 基本概念 数据（Data) 客观事物的符号表示，能输入到计算机中并被计算 机中程序处理的符号的总称。 数据元素 (Data element) 数据的基本单位，可由数据项组成。 数据类型 (Data Type) 是和数据结构密切相关的一个概念，在高级语言中，用以刻画（程序）操作对象的特性。是一个值的集合和定义在这个值集上的一组操作的总称。 数据对象 (Data Object) 性质相同的数据元素的集合，是数据的子集。 数据结构 (Data Structure) 相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的相互关系称为结构。有下列四种基本结构： （1）集合（2）线形结构（3）树形结构（4）图状结构(网状结构）。 数据结构类型 数据的逻辑结构 数据结构的形式定义： Data_Structure=[D,S,P] 其中： D是数据元素的有限集 S是上下关系的有限集 P是对数据对象的基本操作 数据的物理结构（存储结构），数据结构基本操作的实现； 数据的存储结构：位、元素和数据域 数据结构的存储形式有： 顺序存储 链式存储 数据类型综述 数据类型可以分为 原子类型——值不可以分解 结构类型——值由若干成分按某种结构组成。 抽象数据类型（ADT） ADT是一个值的集合和定义在这个值集上的一组操作的总称。包括：原子类型、固定聚合类