一、数据结构绪论

数据结构是一门研究非数值计算的程序设计问题中，计算机的操作对象以及它们之间的关系和操作的学科。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据结构包含三个方面的含义：          

逻辑结构：

物理结构：数据的逻辑结构在计算机中的表示，称此为物理结构，或称存储结构。

数据类型：一个值的集合以及定义在这个值集上的一组操作的总称。

抽象数据类型：通常由用户定义，用以表示应用问题的数据模型以及定义在该模型上的一组操作。                                                                                                     

算法是描述计算机解决给定问题的操作过程，即为决解某一特定问题而由若干条指令组成的有穷序列。

算法的效率分析：

http://univasity.iteye.com/blog/1164707

事后统计法：收集该算法实际的执行时间和实际占用空间的统计资料。

事前分析估算法：在算法运行之前分析该算法的时间复杂度和空间复杂度，来判断算法的效率。

时间复杂度分析：

、

常见函数的时间复杂度按数量递增排列及增长率：                                                                                                                  

二、线性表

线性表的类型定义

线性表是n(n>0)个相同类型数据元素构成的有限序列，其中n为线性表的长度。

线性表的基本操作：    

线性表的顺序表示和实现

线性表的顺序存储结构：用一组地址连续的存储单元依次存储线性表的元素。

线性表的顺序存储，也成为向量存储，又可以说是一维数组存储。线性表中结点存放的物理顺序与逻辑顺序完全一致，它叫向量存储。

线性表顺序存储结构在插入或删除数据元素时比较繁琐，但是它比较适合存取数据元素。

线性表的插入操作：在第i个元素之前插入一个元素时，需将第n至第i（共n-i+1）个元素向后移动一个位置。  

线性表的删除操作：删除第i个元素时需将从第i+1至第n（共n-i）个元素一次向前移动一个位置                                                                                                 

线性表的链式表示和实现

用一组任意的存储单元（可能不连续）存储线性表的数据元素。

在链式存储结构中，每个存储结点不仅包含数据元素本身的信息，还必须包含每个元素之间逻辑关系的信息，即包含直接后继结点的地址信息（指针域）。

逻辑顺序与物理顺序有可能不一致；属顺序存取的存储结构，即存取每个元素必须从第一个元素开始遍历，直到找到需要访问的元素，所以所花时间不一定相等。                  

                                                                                               

链表的创建方式：                                                                                                

结点类的定义：                                                                                                 

单链表的基本操作

插入方式——头插法：                                                                                        

插入方式——尾插法：                                                                                            

查找运算——按序号查找：在链表中，即使知道被访问结点的序号i，也不能像顺序表中那么直接按序号i访问结点，而只能从链表的头指针除法，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。链表不是随机存取结构，只能顺序存取。                                                                                                              

查找运算——按数值查找：                                                                                     

删除结点：将被删除结点的前驱指针连接被删除结点的后继指针

循环链表

表中尾结点的指针域指向头结点，形成一个环。从表中任意一个点出发都可以找到表中其他的结点。                                       

循环链表的操作和线性链表的操作基本一致，但循环链表中没有NULL指针，故遍历操作时，终止条件不再是判断p或p.next是否为空，而是判断他们是否等于某一指定指针，如头指针或尾指针。

双向链表

双向链表是在单链表的每个结点里再增加一个指向其直接前驱的指针域prior。这样就形成了链表中有两个方向不同的链，故称为双向链表。

双线链表——头插法：                                                                                        

双向链表——尾插法：                                                                                          

插入操作

删除操作