数据结构

1.1   为什么学习数据结构？

是一门专业基础课程，为后续的专业课程学习提供知识和技能准备。

1.2   什么是数据结构？

数据结构涉及数据之间的逻辑关系，数据在计算机中的存储方式和在这种结构上的一组能行的操作运算。即：数据的逻辑结构，数据的存储结构和数据的运算。

1.2.1          数据的逻辑结构

数据的逻辑结构是从具体问题抽象出来的数学模型，由数据节点和连结两点的连结边组成。一个逻辑结构可以用一组数据节点K和一个关系集合R表示：（K,R）。

1．  结点的类型（5种）

# 整数类型，1-4字节来存储整数。

#实数类型，4-8字节来存储浮点数。

#布尔类型，取值为真或假。

#字符类型，用单个字节表示字符。

#指针类型，用于表示机器内存地址，即表示指向某一内存单元的地址，用4-8个字节来表示。

2．  结构的分类（3种）

#线性结构，也称前后关系或大小关系。满足全序性和单索性。全部的节点都可以比较前后，每个节点存在唯一的一个直接后续节点。

#树形结构，也称树结构或层次结构。每个节点可以都多于一个的直接下级，但只能有唯一的直接上级。

#图结构，也称网络结构。

区别：树形结构和图结构：每个结点是否仅仅从属一个直接上级。线性结构和树形结构：每个结点是否仅仅有一个直接后继。

1.2.2          数据的存储结构

计算机的主存储器的特性简述：其存储空间提供了一种具有非负整数地址编码的，在存储空间上相邻的单元集合，其基本的存储单元式字节。

为了表达逻辑关系r,可以将它映射到存储结构的地址关系上，利用存储地址的顺序相邻关系或者地址指针的指向关系来表达关系r。

可以用数学上的映射来表示存储结构。数据的存储结构是建立一种由逻辑结构到存储空间的映射。4种映射方法。

1．  顺序的方法。（顺序存储结构或紧凑数据结构）

用一块无空隙的存储区域存储结点数据成为顺序存储。顺序存储把一组结点存放在按地址相邻的存储单元里，结点间的逻辑关系用存储单元的自然顺序关系来表达。

2．  链接的方法。（链接法）

利用指针在结点的存储结构中附加指针字段的方法成为链接法。两个结点的逻辑后续关系用指针的指向来表达。做法是将数据结点分为两部分，一部分存放结点本身的数据（数据字段），一部分存放指针（指针字段）。

3．  索引的方法

使用一个索引表存储一串指针。直接用途是可以把大小不等的数据结点顺序存储，并且仍然可以使用整数下标来间接访问数据结点位置。

4．  散列的方法

利用散列函数进行索引值的计算，然后通过索引求出结点的指针地址。