数据结构基础

一、定义与目的
数据结构就是数据的组织形式，在应用中涉及各种各样的数据，为了存储它们，组织它们，需要讨论它们的归来及它们之间的关系，从而建立相应的数据结构，并以此实现要求的软件功能。

二、分类

1. 线性结构：也成为线性表，在这种结构中所有数据元素都按某种次序排列在一个序列中。根据对线性结构中数据元素存取方法的不同，又可分为直接存取结构、顺序存取结构和字典结构。对于直接存取结构，可以直接存取某一指定项而不须先访问其前驱，就像数组、文件，可以根据下标直接存取某一数组元素，可以按记录号直接检索记录集合或文件中的某一记录。对于顺序存取结构，只能从序列中第一个数据元素起，按序列组个访问直到指定的元素（如栈、队列、优先级队列等）。而字典结构就是通过关键码（Key）进行索引，例如我们要查询学生记录，可以设定学生的学号为关键码，用它来识别是哪一位学生的记录。
2. 非线性结构
   在非线性结构中的各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或多个其他数据元素发生关系。根据关系的不同可分为层次结构（如树形结构）和群结构（图结构、网络结构）。

三、意义
社会的发展，要求使用计算机解决更复杂的问题，而更复杂的问题需要更大的计算量，从而要求计算机程序的运算速度更快。选择不同数据结构可能会残生很大的差异：同样一个程序，选择某一种数据结构可能在几秒钟内运行完成，而选择另一种数据结构则可能需要几天时间才能运算完毕。

四、存储问题
数据结构的存储结构可以用以下4种存储方法得到：

1. 顺序存储：逻辑相连的元素，物理位置也相连；
2. 链接存储：逻辑相连，物理位置不一定相连，而是根据元素中的指针指示上一个或者下一个元素的位置；
3. 索引存储：该方法在存储元素信息的同时，还建立附加的索引表，索引表中每一项成为索引项，索引项的一般形式是：关键码+地址
4. 散列存储：该方法的处理方式是根据结点的关键码通过一个函数计算直接得到该结点的存储地址；