文档介绍：数
据结构
演讲稿
严蔚敏,吴伟民,数据结构(C语言版),清华大学出版社,2003年7月再版;
中国计算机学会教育委员会,全国高等院校计算机教育研究会,计算机学科教学计划2000,内部资料;
傅清祥,王晓东,算法与数据结构,电子工业出版社,2001;
吴文虎,王建德,实用算法的分析与程序设计,电子工业出版社,1998;
William F.,William T.,Data Structures with C++,Prentice Hall,Inc.,1996;
Clifford .,Data Structures and Algorithm Analysis,Prentice Hall,Inc.,1997。
教学安排:
总学时数:72学时
主要参考资料:
教学对象:
计算机科学与工程专业的学生;
计算机软件专业的学生;
计算机辅修专业的学生;
电类联合班的学生;
网络教育学院计算机专业的学生;
各类成人教育及自学考试人员;
工程技术人员。
课程内容:
第一章 绪论
第二章 线性表
第三章 栈和队列
第四章 串
第五章 数组和广义表
第六章 树和二叉树
第七章 图
第八章 动态存储管理
第九章 查找
第十章 内部排序
第十一章 外部排序
第十二章 文件
第一章绪论
￡ 背景
自第一台计算机1946年在美国问世以来,计算机的应用范围大大地扩展,已深入到人类社会的各个领域。与此相应的,计算机加工处理的对象也从纯粹的数值发展到字符、图像、声音等各种具有一定结构的复杂的数据。例如,从数值计算到卫星发射等等。因此要设计出一个好的程序(程序执行时间最短,占内存空间最小),必须研究数据的特性以及数据之间存在的关系。这就形成了《数据结构与算法》这门课程。
“数据结构与算法”作为一门独立的课程,在国外是从1968年开始,而国内是在80年代初才开始。它不仅是计算机科学中的一门专业基础课,而且也是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。在计算机专业的教学计划中,它是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。
值得注意的是,“数据结构与算法”的发展并未终结,一方面,面向各专门领域中特殊问题的数据结构得到研究和发展,如多维图形数据结构等;另一方面,从抽象数据类型的观点来讨论数据结构,已成为一种新的趋势,越来越被人们所重视。
￡ 什么是数据结构
在图书馆内有各种名目的卡片:有按书名编排的,有按作者编排的,还有按分类编排的,等等。若利用计算机实现自动检索,则计算机处理的对象便是这些目录卡片上的书目信息。列在一张卡片上的一本书的书目信息可由登录号、书名、作者名、分类号、出版单位和出版时间等若干项组成,每一本书都有唯一的一个登录号,但不同的书目之间可能有相同的书名,或者有相同的作者,或者有相同的分类号。由此,在书目自动检索系统中可以建立一张按登录顺序排列的书目文件和3张分别按书名、作者名和分类号顺序排列的索引表,如下图所示。
例一:图书馆的书目检索系统自动化问题。
001
高等数学
樊映川
S01
…
002
理论力学
罗远祥
L01
…
003
高等数学
华罗庚
S01
…
004
线性代数
栾汝书
S02
…
…
…
…
…
…
高等数学
001,003, …
理论力学
002, …
线性代数
004, …
…
樊映川
001, …
华罗庚
003, …
栾汝书
004, …
…
L
002, …
S
001,003, …
…
数学模型—线性表
例二:计算机和人对弈问题。数学模型-树。(课本P2)
例三:多叉路口交通灯的管理问题。数学模型-图。(课本P3)
由上述例子可见,描述这类非数值计算问题的数学模型不再是数学方程,而是诸如表、树和图之类的数据结构。因此,简单来说,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。
￡ 基本概念和术语
1)数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
例如,整数、实数、字符串、图像和声音等。
2)数据项:是数据不可分割的最小单位。
3)数据元素:是数据的基本单位。有时,一个数据元素可由若干个数据项组成。
例如,例一中一本书的书目信息为一个数据元素,而书目信息中的每一项(如书名、作者名等)为一个数据项。
4)数据对象:是性质相同的数据元素的集合,是数据的一个子集。
例如,字母字符数据对象集合C={‘A’, ‘B’, …,’Z’}。
5)数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。