1.0数据结构简介

1、数据结构是组织与存储数据，数据组织的好，存取速度快。
2、数据结构是研究非数值计算的数学模型，如：学生信息表、菜单树、课程关系图等之类的有结构的数据，将数据归纳为某一种类型进行相应的运算，完成数据处理过程。

1.1数据结构的基本概念、术语分析

1.数据（Data）：是一种计算机符号的表示形式。是对客观信息的符号化描述，是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号。

2.数据元素（Data Element）：是数据的基本单位。如每一个学生的记录就是一个数据元素。

3.数据项（data item）：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。例：学生记录中的姓名、学号等。

4.数据类型：在一种程序设计语言中，变量所具有的数据种类。整型、浮点型、字符型等等

5.逻辑结构：数据之间的相互关系。

6.数据对象（data object）：性质相同的数据元素的集合，是数据的一个子集，如大写字母字符数据对象是集合C = {‘A’,’B’,’C’,……，’Z’}，整数数据对象是集合{0,±1,±2, … }。

7.数据结构（data structure）：是指互相之间存在着一种或多种关系的数据元素的集合。数据元素之间的关系称为结构。

8.数据类型（Data Type）：数据类型是一个值的集合和定义在这个值集上的一组操作。

基本数据类型的每一个数据元素都是单一的无法再分割的整体。构造数据类型可以由不同成分的内置数据类型或子结构类型按照一定的规则组成。

           数据类型中定义了两个集合：
                1.数据取值范围
                2.数据允许使用的一组运算。

9.抽象数据类型ADT：抽象的本质就是抽取反映问题本质的东西，忽略非本质的细节。另外，抽象数据类型把使用与实现分离，实现封装与信息隐蔽。一般的，抽象数据类型由用户定义，是用于表示应用问题的数据模型。

     抽象数据类型=数据结构+操作
                 =数据对象+数据关系+操作

10.数据的逻辑结构：数据结构是存在关系的数据元素集，其中“关系”是描述数据元素之间的逻辑关系，称为逻辑结构。

11.物理结构：数据的物理结构又称为数据的存储结构，是指数据的逻辑结构在计算机中的映像，即数据结构在计算机中的存储。

         数据结构（逻辑结构） =数据集合+数据关系
         物理结构（存储结构） =数据映像+关系映像

12.顺序存储结构的特点是借助元素在连续空间的存储器中的相对位置来表示数据元素之间的逻辑关系。

13.非顺序映像是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

1.集合：结构中的数据元素除了同属于一种类型外，别无其它关系。
2.线性结构：数据元素之间一对一的关系
3.树形结构：数据元素之间一对多的关系
4.图状结构或网状结构：结构中的数据元素之间存在多对多的关系

   Data-Structure = (D,S)
   D：数据元素的有限集；
   S：D上关系的有限集。

例：在计算机科学中，复数可取如下定义：
复数是一种数据结构

           Complex=（C，R）

其中，C是含两个实数集合{c1，c2}；R={P}，P是定义在集合C上的一种关系{<c1，c2>}，其中有序偶<c1，c2>表示c1是复数的实部，c2是复数的虚部。

 ADT＜ADT名＞
   { 数据对象：＜数据对象的定义＞
     结构关系；＜结构关系的定义＞
      基本操作：＜基本操作的定义＞
   }ADT＜ADT名＞

数据对象和结构关系的定义采用数学符号和自然语言描述。
基本操作的定义格式为C语言基本函数

  函数类型   函数名（[参数列表]）
 [类型定义列表]
{
函数体
}

⑴ 结点中除存放数据元素+指针。
⑵ 要存取第i个结点的信息，必须从第1个结点开始查找，存取速度较慢。
⑶ 链式存储结构的优点是插入、删除元素时不必移动其他元素。
⑷ 链式存储是一种动态存储结构，申请空间，释放空间方便，也不用预分配空间。

（1）逻辑相邻的数据物理也相邻，顺序存储结构是指逻辑上相邻的数据元素，其结点的物理位置也相邻
（2）顺序表的存储空间需要预先分配。

1）顺序存储结构利于随机存取元素，链式只能顺序存取。
2）主要操作速度；执行的主要操作是插入、删除，则最好用链式存储结构，否则应该用顺序存储结构；
3）若预先可以估计出元素的个数，则可以采用顺序存储结构，否则宜用链式存储结构。