一、数据结构内容概述

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由哪部分构成，以什么方式构成，以及数据元素之间呈现的结构。数据结构常用的逻辑结构有四种：集合结构(数据元素之间没有关系)、线性结构(数据元素之间存在一对一的关系)、树形结构(数据元素之间存在一对多的关系)、图形形结构(数据元素之间存在多对多的关系)。数据结构常用的存储结构：顺序存储(使用任意一段连续存储空间存储数据)、链式存储(使用任意的空间存储数据)、索引存储(采用索引表和数据文件共同实现的索引查找方法)、散列存储(简称为哈希表，借助于散列函数，以及数组形式创建的哈希表共同实现的查找算法)。

二、线性表的顺序存储

对与顺序存储来说，顺序存储是借助于数组实现的，使用下标查找十分迅速，但计算机内存有限，故数组的长度有限，数组初始化就需要声明数组的长度。实际应用当中的数据往往十分庞大；无序数组的查找最坏情况需要遍历整个数组；后来人们提出了二分查找，二分查找要求数组的构造一定有序，二分法查找解决了普通数组查找复杂度过高的问题。任何一种数组无法解决的问题就是插入、删除操作比较复杂（插入、删除需根据数组下标来操作），原因是因为顺序表的插入和删除需要移动大量元素，所耗费时间复杂度是O(n), 因此，在一个增删查改比较频繁的数据结构中，数组不会被优先考虑。所以顺序存储常用来实现按下标实现查找的修改操作。

2.1 顺序表插入

线性表的插入运算是指在表的第i (1≤i≤n+1)个位置，插入一个新元素x，使长度为n的线性表变成长度为n+1的线性表，用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此我们必须将原表中位置n-1，n-2，…，i-1上的结点，依次后移到位置n，n-1，…，i上，空出第i-1个位置，然后在该位置上插入新结点x。当i=n+1时，是指在线性表的末尾插入结点，所以无需移动结点，直接将x插入表的末尾即可。最好的情况：当i=n+1时（插入尾元素），移动次数为0；最坏的情况：当i=1时（插入第一个元素），移动次数为n；平均情况：在位置i插入新元素x，需要将ai～an的元素均后移一次，移动次数为n-i+1。假设在等概率下pi（pi=1/(n+1)），移动元素的平均次数为：n/2,插入算法的主要时间花费在元素移动上，所以算法平均时间复杂度为O(n)。

2.2 顺序表删除

线性表的删除运算是指从表中删除第i(1<=i<=n)个元素，删除后使原表长n的线性表(a1,a2…..ai-1.ai.ai+1,…an)变为n-1的线性表(a1,a2…..ai-1.ai+1,…an)，数据元素ai-1,ai+1之间逻辑关系发生变化。和插入运算类似，为了在存储结构上反应这种逻辑结构上的变化，也必须移动元素的位置，当i=n，由于删除的最后一个元素，不需要移动元素，一般情况下，若删除第i个元素，将需要将第i+1至第n个元素依次向前移动一个位置到i,i+1…n-1上，平均时间复杂度是O(n)，删除过程如下：

2.3 顺序表按值查找

线性表安置查找是指在线性表中查找与给定值x相等的数据元素，可以从第一个元素a1一次和x比较，如果找到第一个和x相等的元素，则返回在线性表中的序号，表示查找成功；如果查边整个线性表都没有和x相等的元素，则返回0，表示查找失败。

三、线性表的链式存储

由于顺序存储在操作数据时不适用于插入和删除，以及数组的局限只能适用于数据量较小的情况，那么为了解决这个问题，则使用链式存储解决提前预估存储空间，并且插入和删除不需要移动大量元素，但是普通链表由于它的结构特点被证明根本不适合进行查找和修改数据。链表的操作形式有很多，比如单向链表、单向循环链表、双向链表、双向循环链表。常借助于约瑟夫环的思想实现循环播