数据结构是计算机存储、组织数据的方式。
现在计算机主要用于非数值计算，处理字符、表格和图像等具有一定结构的数据。数据结构研究如何组织数据，高效地处理数据。数据结构主要研究非数值计算的问题。
计算机用于数值计算时，一般要经过的步骤，首先从具体问题抽象出数学模型，然后设计出来一个解此数学模型的算法。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，建立相应的数学方程。
问题一、学生学籍管理系统（数学模型为“线性”的数据结构）
每个学生的基本信息记录按顺序号排列，形成了学生基本信息记录的线性序列，是一种线性关系。诸如此类的线性表结构还有图书馆的书目管理系统，库存管理系统等。在这类问题中，计算机处理的对象是各种表，元素之间存在简单的一对一的线性关系，这类问题的数学模型就是各种线性表，施加于对象上的操作有查找、插入和删除等。这
问题二、人机对弈问题（数学模型为“树”的数据结构）
对弈的过程就是一颗倒长着的树，这棵树从初始状态（根）到最终格局（叶子）的一条路径，就是一次具体的对弈过程。数学模型是如何用树结构表示棋盘和棋子，算法是博弈分规则和策略。诸如此类树结构还有计算机的文件系统，一个单位的组织结构等。计算机处理的对象是树结构，元素之间是一对多的层次关系，对象上的操作有查找、插入和删除等。
问题三、最短路径问题（数学模型为“图”的数据结构）
从城市A到城市B有多条路径，但每条线路的交通费用不同，如何选择一条线路，使得从城市A到城市B的费用最少。解决方法是，把这类问题抽象成图的最短路径问题。用点代表城市，有向边代表城市之间的通路，边上的权值代表两个城市之间的交通费用。诸如此类的图结构还有网络工程图和网络通信图等，这类问题中，元素之间是多对多的网状关系，对象上的操作有查找、插入和删除等。
非数值计算问题的数学模型是诸如线性表、树和图的数据结构，数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系的操作的学科。
基本概念和术语
数据（data）:能被计算机处理的符号，如整数、实数、字符串、图形图像（特殊编码定义后的数据）等
数据元素（data element）:数据的基本单位，用于完整的描述一个数据对象，如一名学生记录、图的一个顶点。
数据项（data Item）:组成数据元素的不可分割的最小单位。如学生的学号姓名等。
数据对象（data object）:性质相同的数据元素的集合。如整数数据对象，N={0,1,2,}，字母字符数据对象是集合C={‘A’，‘B’，‘C’}，学生的基本信息表。只要集合内元素的性质相同，都可成为一个数据对象。
数据结构（包括逻辑结构和存储结构）
数据结构（data structure）:是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带“结构”的数据元素的集合，“结构”是指数据元素之间存在的关系。
1.逻辑结构（从具体问题抽象出来的数学模型）
数据的逻辑结构有两个要素：数据元素和关系。关系是数据元素之间的逻辑关系，通常有四类基本结构，分别是：集合结构、线性结构、树结构、图结构。
（1）集合结构：数据元素之间除了“属于同一集合”的关系外，别无其他关系。如确定一名学生是否为班级成员，班级就是一个集合结构。
（2）线性结构：数据元素之间存在一对一的关系。如学生信息数据顺序排列，组成一个线性结构。
（3）树结构：数据元素之间存在一队多的关系。如在班级管理体系中，班长管理多个组长，没个组长管理多名组员，形成树形结构。
（4）图结构：数据元素之间存在多对多的关系。如多位同学之间的朋友关系，从而构成图或网状结构。
集合结构、树结构和图结构属非线性结构。线性结构包括，①栈和队列②字符串（数据元素仅有一个字符组成）③数组（是线性表的推广，数组元素是一个线性表）④广义表（线性表的推广，数据元素是一个线性表，可不同构可以是单元素或线性表）。非线性结构包括树和二叉树，有向图和无向图。
2.存储结构（顺序存储结构和链式存储结构）
把数据对象存储到计算机时，要求既要存储个数据元素的数据，又要存储数据元素之间的逻辑关系。数据元素在计算机内用一个节点来表示。
（1）顺序存储结构：用存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助数组来描述。需要一片连续的存储空间。
（2）链式存储结构：需要给每个节点附加一个指针字段，用于存放后继元素的存储地址，链式存储结构通常需要借助指针类型来描述。
3.数据的运算：
插入、删除、修改、查找、排序
数据类型和抽象数据类型：
抽象数据类型（Abstract Data Type，ADT）是由用户定义的表示应用问题的数学模型。包括，数据对象、数据对象上关系的集合、数据对象基本操作的集合。
数据结构的表示（存储结构）用类型定义（typedef）描述，数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。
完整数据类型的定义、表示和实现：
（1）定义：ADT name{数据对象、数据关系、基本操作}
（2）表示部分：typedef struct{数据项}ADTname
（3）实现部分：插入、删除等函数
网友评论