数据结构讲义绪论严蔚敏c语言版

《数据结构讲义绪论严蔚敏c语言版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、柳青Email:liuqing@ynu.edu.cnSchoolofSoftware,YunnanUniversity数据结构(DataStructure)7/16/2021《数据结构》（C语言版）严蔚敏吴伟民清华大学出版社《数据结构题集》严蔚敏吴伟民清华大学出版社《数据结构习题与解析》（C语言篇）李春葆清华大学出版社数据结构教材及参考材料7/16/2021数据结构是计算机类本科专业的一门必修课程，同时也是很多非计算机类本科专业的主要选修课程，属于综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，具有很强的理

2、论性和实践性。数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统和其他系统程序和大型应用程序的重要基础。数据结构课程性质及特点7/16/2021第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求7/16/2021计算机的程序是对信息（数据）进行加工处理。信息的表示和处理直接关系到程序的效率。在大多数情况下，信息之间往往具有重要的结构关系，这就是数据结构的内容。例1、电话号码查

3、询系统：设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn),其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码。要求设计算法：（1）当给定任何一个人的名字时能够给出此人的电话号码；（2）加入一个新的人的名字和其相应的电话号码；（3）删除一个不需要的人的名字和其相应的电话号码。1.1什么是数据结构7/16/20211.1什么是数据结构算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据结构就是研究数据的逻辑结构和

4、物理结构以及它们之间相互关系，并对这种结构定义相应的运算。数据结构的三个方面：1逻辑结构—数据之间的逻辑关系2物理结构—数据在计算机中如何表示3运算问题逻辑结构（模型）物理结构（存储）运算（算法）7/16/2021数据(Data):是对客观事物的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。Eg.75,“软件”，08/08/2008。在计算机科学中，数据的含义极为广泛，包括数值型、非数值型、多媒体数据等。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理

5、。Eg.“图”中的圆圈。一个数据元素可由若干个数据项(DataItem)组成。数据项是数据的不可分割的最小单位。Eg.“书目”中的书名。数据对象(DataObject):是性质相同的数据元素的集合。是数据的一个子集。Eg.C={“A’’,“B”,···,“Z”}1.2基本概念和术语7/16/2021数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构。通常分为四类基本结构：1、集合数据元素除了同属于一种类型外，别无其它关系。2、线性结构数据元素之间存在一对一的关系。3、树形结构

6、数据元素之间存在一对多的关系。4、图状结构数据元素之间存在多对多的关系。1.2基本概念和术语集合线性结构树形结构图状结构7/16/2021数据结构的形式定义为：数据结构是一个二元组Data-Structure=(D，S)其中，D是数据元素的有限集，S是D上关系的有限集。例：复数的数据结构定义如下：Complex=(C，R)其中，C是含两个实数的集合﹛C1，C2﹜，R={P}，P是定义在集合C上的一种关系{〈C1，C2〉}，其中〈C1，C2〉表示复数的实部和虚部。1.2基本概念和术语7/16/2021数据结构在计算机中的表示称为数据的物理结构，又

7、称为存储结构。数据结构在计算机中有两种不同的表示方法：顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。1.2基本概念和术语7/16/2021数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。在程序设计语言中，用以刻画操作对象的特性。Eg.C语言的数据类型：基本类型和构造类型。基本类型：整型、浮点型、字符型。构造类型：数组、结构、联合、指针等。数据对象：是某种数据类型元素的集合。Eg.整数的数据对象是{…-2，-1，0

8、，1，2，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对象，它