第1章绪论1.1什么是数据结构（定义）2.数据元素（DataElement）数据元素是组成数据的基本单位。3.数据对象（DataObject）数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对象。由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。综上1~3所述，再分析数据概念：4.数据结构（DataStructure）数据结构是指相互之间存在一种或多种特定关系的数据元素集合。图1.3交通流量图5.数据类型(DataType)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型是高级语言中允许的变量种类，是程序语言中已经实现的数据结构（即程序中允许出现的数据形式）。在高级语言中，整型类型可能的取值范围是-32768~+32767，可用的运算符集合为加、减、乘、除、乘方、取模（如C语言中+，-，*，/，%）。6.数据抽象与抽象数据类型２）抽象数据类型(AbstractDataType)抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。在高级语言中，给出高一级的数据抽象，出现了数据类型，如整型、实型、字符型等。到抽象数据类型出现，可以进一步定义更高级的数据类别，设计新的数据类别就是创造新的抽象数据类型。抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一些最基本的原则：分解、抽象和信息隐藏。一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。数学模型→抽象数据类型→数据结构，恰好反应了信息结构转换的三个重要阶段，而在这个转换过程中，数据结构是基础，抽象数据类型是中枢。一个线性表的抽象数据类型的描述如下：ADTLinear-list数据元素所有ai属于同一数据对象，i=1，2，…，n,n≥0；逻辑结构所有数据元素ai（i=1，2，…，n-1）存在次序关系<ai，ai+1>，ai无前趋，an无后继；操作设L为Linear-list:Initial(L):初始化空线性表;Length(L):求线性表的表长;Get(L,i):取线性表的第i个元素；Insert(L,i,b):在线性表的第i个位置插入元素b；Delete(L,i):删除线性表的第i个元素。３）抽象数据类型实现４）ADT的表示与实现ADT的定义ADT的定义格式不唯一,我们采用下述格式定义一个ADT:ADT<ADT名>{数据对象:<数据对象的定义>结构关系:<结构关系的定义>基本操作:<基本操作的定义>}ADT<ADT名>其中数据对象和结构关系的定义采用数学符号和自然语言描述,而基本操作的定义格式为:<操作名称>(参数表)操作前提:<操作前提描述>操作结果:<操作结果描述>用标准C语言表示和实现ADT描述时，主要包括以下两个方面:(1)通过结构体将int、float等固有类型组合到一起,构成一个结构类型,再用typedef为该类型或该类型指针重新起一个名字。(2)用C语言函数实现各操作。基本操作主要有以下几种：(1)插入：在数据结构中的指定位置上增添新的数据元素；(2)删除：删去数据结构中某个指定数据元素；(3)更新：改变数据结构中某个元素的值，在概念上等价于删除和插入操作的组合；(4)查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值)；(5)排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。1.2数据结构的内容(1)集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。(2)线性结构：结构中的数据元素之间存在着一对一的线性关系。(3)树形结构：结构中的数据元素之间存在着一对多的层次关系。(4)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。2.存储结构存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。形式化描述：D要存入机器中，建立一从D的数据元素到存储空间M单元的映象S，D→M，即对于每一个d，d∈D,都有唯一的z∈M，使S（D）=Z,同时这个映象必须明显或隐含地体现关系R。逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是