数据结构 徐虹 http:/jwc.cuit.edu.cn/jxgl/ HomePage/Default. asp 说明 据>总学时: 构 80(学时)=60(课时)+20(机时) 行课时间从第1周开始,每周4学时 上机安排待定 >考试时间:课程结束 第8、11、12章的内容为自学内容; 目录中标有*的内容不作要求
1 数据结构 徐 虹 http://jwc.cuit.edu.cn/Jxgl/ HomePage/Default.asp 数 据 结 构 之 绪 论 2 说明 ¾ 总学时： 80(学时)= 60（课时）+20（机时） ¾ 行课时间从第 1 周 开始，每周 4 学时 ¾ 上机安排待定 ¾ 考试时间：课程结束 ¾ 第8、11、12 章的内容为自学内容； ¾ 目录中标有 ** 的内容不作要求
教材与参考书 据>严蔚敏,《数据结构》,清华大学出版社 结 构> Clifford A. Shaffer,《数据结构与算法 分析》,电子工业出版社 > Sartaj Sahni,,《数据结构、算法与应用》 机械工业出版社 论>严蔚敏,《数据结构题集》,清华大学出 版社 目录 据 第一章:绪论 构 第二章:线性表 第三章:栈和队列 第四章:串 第五章:数组和广义表 绪 第六章:树和二叉树 第七章:图 第八章:查找 第九章:内部排序
2 数 据 结 构 之 绪 论 3 教材与参考书 ¾ 严蔚敏，《数据结构》，清华大学出版社 ¾ Clifford A. Shaffer, 《数据结构与算法 分析》，电子工业出版社 ¾ Sartaj Sahni, 《数据结构、算法与应用》, 机械工业出版社 ¾ 严蔚敏，《数据结构题集》，清华大学出 版社 数 据 结 构 之 绪 论 4 目录 第一章：绪论 第二章：线性表 第三章：栈和队列 第四章：串 第五章：数组和广义表 第六章：树和二叉树 第七章：图 第八章：查找 第九章：内部排序
第一章绪论 什么是数据结构 算法和算法分析 1.1什么是数据结构 数据结构的引论 据 例1图书馆的书目检索系统自动化问题 构 在书目自动检索系统中可以建立一张按等录顺序号 排列的书目文件和三张分别按书名、作者名和分类号 顺序排列的索引表,如下所示: 绪 001高等数学樊映川 002理论力学罗远祥L01 003高等数学华罗庚s0 004线形代数栾汝书sn2|…
3 第一章 绪论 什么是数据结构 算法和算法分析 数 据 结 构 之 绪 论 6 1. 1 什么是数据结构 ¾ 数据结构的引论 ¾ 例1 图书馆的书目检索系统自动化问题 在书目自动检索系统中可以建立一张按等录顺序号 排列的书目文件和三张分别按书名、作者名和分类号 顺序排列的索引表，如下所示： 001 002 003 004 ... ... ... ... 高等数学 理论力学 高等数学 线形代数 樊映川 罗远祥 华罗庚 栾汝书 S01 L01 S01 S02 . . . . . . .
按书名排列 按作者排列 据高等数学0010 樊映川 结 理论力学 华罗庚003,… 线形代数 004 栾汝书 按索引号排列 论 特点:计算机按某个特定的要 001,003·· 求进行奎询.处理对象之间存在 一种简单的线形关系,这类模型 可以称为简单的线形数据结构 >例2:计算机和人的对弈问题 对奕的过程是在一定的规则下随机进行的因此计算 据 机必须对对弈过程之中可能发生的情况以及相应 的对策都考虑周全这个关系不是线形的,从 构 棋盘可以派生出几个格局如下图 (a)棋盘格式示例 (b)并字棋对奔树的局部 树根”是对奕开始之前的棋盘格局而所有的“叶子”是可能出现 的结局对奕的过程就是从树根沿树叉到达某个叶子的过程
4 数 据 结 构 之 绪 论 7 高等数学 理论力学 线形代数 001,003, … 002, … 004, … ... . . . L S 002, 001, 003 ... ... . . . . . . 特点：计算机按某个特定的要 求进行查询.处理对象之间存在 一种简单的线形关系,这类模型 可以称为简单的线形数据结构. 按书名排列 樊映川 华罗庚 栾汝书 001, 003, 004, ... ... ... . . . . . . 按作者排列 按索引号排列 数 据 结 构 之 绪 论 8 ¾ 例2: 计算机和人的对弈问题 对奕的过程是在一定的规则下随机进行的,因此,计算 机必须对对弈过程之中可能发生的情况以及相应 的对策都考虑周全.这个关系不是线形的,从一个 棋盘可以派生出几个格局,如下图: “树根”是对奕开始之前的棋盘格局,而所有的“叶子”是可能出现 的结局,对奕的过程就是从树根沿树叉到达某个叶子的过程. * * * * * * * * * * * * * * * * * * (a) 棋盘格式示例 (b)井字棋对弈树的局部
据结构 例3:多叉路口交通灯的管理问题 以把这类交通道路的问题当作一种“图”的结构:一个顶点表 示一条通道而通道之间的矛盾的关系以两个顶点之间的连 线表示如下图所示 B (a)五叉路口 数据结构 结论:综合上面三个例子描述这类非数值计算性问 题的数学模型不再是数学方程而是诸如表、树和图之 类的数据结构. 数据结构定义: 数据结构是一门非数值计算的程序设计问题中计 绪 算机的操作对象以及它们之间的关系和操作等等的学 科
5 数 据 结 构 之 绪 论 9 ¾ 例3: 多叉路口交通灯的管理问题 可以把这类交通,道路的问题当作一种“图”的结构：一个顶点表 示一条通道,而通道之间的矛盾的关系以两个顶点之间的连 线表示.如下图所示: A E D C B (a) 五叉路口 数 据 结 构 之 绪 论 10 ¾ 结论：综合上面三个例子,描述这类非数值计算性问 题的数学模型不再是数学方程,而是诸如表、树和图之 类的数据结构. ¾ 数据结构定义: 数据结构是一门非数值计算的程序设计问题中计 算机的操作对象以及它们之间的关系和操作等等的学 科