数据结构与算法基础
数据
元素又称为元素、结点、记录是数据的基本单位
数据项是具有独立含义的最小标识单位
数据的逻辑结构
数据的逻辑结构有以下两大类：
线性结构：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。
线性表是一个典型的线性结构。栈、队列、串、数组等都是线性结构。
非线性结构：在该类结构中至少存在一个数据元素,它具有两个或者两个以上的前驱或后继.如树和二叉树
集合结构和多维数组、广义表、图、堆等数据结构都是非线性结构。
基本逻辑结构
集合结构：数据元素的有限集合。数据元素之间除了“属于同一个集合”的关系之外没有其他关系。
线性结构：数据元素的有序集合。数据元素之间形成一对一的关系。
树型结构：树是层次数据结构，树中数据元素之间存在一对多的关系。
图状结构：图中数据元素之间的关系是多对多的。
具体例子：
传统文本（例如书籍中的文章和计算机的文本文件）都是线性结构，阅读是需要注意顺序阅读，而超文本则是一个非线性结构。在制作文本时，可将写作素材按内部联系划分成不同关系的单元，然后用制作工具将其组成一个网型结构。阅读时，不必按线性方式顺序往下读，而是有选择的阅读自己感兴趣的部分。
算法
是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法是一系列将输入转换为输出的计算步骤。
算法的重要特性
输入：算法应该有零个或多个输入。
输出：算法应该有一个或多个输出。
有穷性：算法必须在执行有穷步骤之后正常结束。
确定性：算法中的每一条指令必须有确切的含义。
可行性：算法中的每一条指令必须是切实可执行的。
算法设计的要求
正确性：算法应能正确地实现预定功能和要求。
易读性：算法应易于阅读和理解，便于调试、修改和扩充。
健壮性：对正确的输入能得到正确的输出。当遇到非法输入时应能作适当的反应或处理，而不会产生不需要或不正确的结果。
高效性：解决同一问题的执行时间越短，算法的时间效率就越高。
低存储量：解决同一问题的占用存储空间越少，算法的空间效率就越高。
算法的时间复杂度
定义：设问题的规模为n，把一个算法的时间耗费T(n)称为该算法的时间复杂度，它是问题规模为n的函数。
常用的算法的时间复杂度的顺序：（比较时只看最高次幂）
for ( i = 1 , i < = 10 , i++ ) x=x+c； =>O(1)
for ( i = 1 , i < = n , i++ ) x=x+n； =>O(n)
多嵌套一个for，则为 =>O(n^2) 以此类推
真题难点：i = 1，while（i < = n)
i = i * 3；=>O(log3^n)
i = i * 2；=>O(log2^n) 以此类推
程序与算法的区别
程序可以不满足有穷性。
线性表（Linear List）
是具有相同数据类型的数据元素的一个有限序列。通常表示为：（a1，a2，… ai，ai+1… an）
线性表的顺序存储是指用一组地址连续的存储单元依次存放线性表的数据元素，这种存储形式的线性表称为顺序表。它的特点是线性表中相邻的元素在内存中的存储位置也是相邻的。由于线性表中的所有数据元素属于同一类型，所以每个元素在存储中所占的空间大小相同。
优点：顺序存储结构内存的存储密度高，可以节约存储空间，并可以随机或顺序地存取结点，但是插入和删除操作时往往需要移动大量的数据元素，并且要预先分配空间，并要按最大空间分配，因此存储空间得不到充分的利用，从而影响了运行效率。
线性表的链式存储结构，它能有效地克服顺序存储方式的不足，同时也能有效地实现线性表的扩充。
单链表和循环链表（循环链表是单链表的变形）
线性表的链式存储结构是用一组地址任意的存储单元存放线性表中的数据元素。除了存储其本身的值之外，还必须有一个指示该元素直接后继存储位置的信息，即指出后继元素的存储位置。这两部分信息组成数据元素ai的存储映像，称为结点（node）。每个结点包括两个域：一个域存储数据元素信息，称为数据域；另一个存储直接后继存储位置的域称为指针域。
指针域中存储的信息称做指针或链。N个结点链结成一个链表，由于此链表的每一个结点中包含一个指针域，故又称线性链表或单链表。
循环链表最后一个结点的next指针不为空，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。
循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。
双向链表
双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。
在双向链表结构中，每一个结点除了数据域外，还包括两个指针域，一个指针指向该结点的后继结点，另一个指针指向它的前趋结点。通常采用带表头结点的循环链表形式。
用指针实现表
用数组实现表时，利用了数组单元在物理位置上的邻接关系表示表元素之间的逻辑关系。
优点是：
无须为表示表元素之间的逻辑关系增加额外的存储空间。
可以方便地随机存取表中任一位置的元素。
缺点是：
插入和删除运算不方便，除表尾位置外，在表的其他位置上进行插入或删除操作都须移动大量元素，效率较低。
由于数组要求占用连续的存储空间，因此在分配数组空间时，只能预先估计表的大小再进行存储分配。当表长变化较大时，难以确定数组的合适的大小
顺序表与链表的比较
顺序表的存储空间可以是静态分配的，也可以是动态分配的。链表的存储空间是动态分配的。
顺序表可以随机或顺序存取。链表只能顺序存取。
顺序表进行插入/删除操作平均需要移动近一半元素。链表则修改指针不需要移动元素。
若插入/删除仅发生在表的两端，宜采用带尾指针的循环链表。
存储密度=结点数据本身所占的存储量/结点结构所占的存储总量。
顺序表的存储密度= 1，链表的存储密度< 1。
总结：顺序表是用数组实现的，链表是用指针实现的。用指针来实现的链表，结点空间是动态分配的，链表又按链接形式的不同，区分为单链表、双链表和循环链表。
栈(stack)
是限定仅在表尾进行插入或删除操作的线性表。栈是一种后进先出(Last In First Out)/先进后出的线性表，简称为LIFO表
用指针实现栈—链(式)栈链式栈
无栈满问题，空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
链栈的基本操作
1）进栈运算
进栈算法思想：
1）为待进栈元素x申请一个新结点，并把x赋给 该结点的值域。
2）将x结点的指针域指向栈顶结点。
3）栈顶指针指向x结点，即使x结点成为新的栈顶结点。
具体算法如下：
SNode *Push_L(SNode * top,ElemType x)
{
SNode *p;
p=(SNode*)malloc(sizeof(SNode));
p->data=x;
p->next=top;
top=p;
return top;
}
2）出栈运算
出栈算法思想如下：
1）检查栈是否为空，若为空，进行错误处理。
2）取栈顶指针的值，并将栈顶指针暂存。
3）删除栈顶结点。
SNode *POP_L(SNode * top,ElemType *y)
{SNode *p;
if(top==NULL) return 0;/*链栈已空*/
else{
p=top;
*y=p->data;
top=p->next; free(p);
return top;
}
3）取栈顶元素
具体算法如下：
void gettop(SNode *top)
{
if(top!=NULL)
return(top->data); /*若栈非空，则返回栈顶元素*/
else
return(NULL); /*否则，则返回NULL*/
}
队列（Queue）
是只允许在表的一端进行插入，而在另一端进行删除的运算受限的线性表。其所有的插入均限定在表的一端进行，该端称为队尾（Rear）；所有的删除则限定在表的另一端进行，该端则称为队头（Front）。如果元素按照a1，a2，a3....an的顺序进入队列，则出队列的顺序不变，也是a1，a2，a3....an。所以队列具有先进先出（First In First Out，简称FIFO）/后进后出特性。如车站排队买票，排在队头的处理完走掉，后来的则必须排在队尾等待。在程序设计中，比较典型的例子就是操作系统的作业排队。
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个数组来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针分别指示队头和队尾元素在队列中的位置。
循环队列是为了克服顺序队列中“假溢出”，通常将一维数组Sq.elem[0]到Sq.elem.[MaxSize-1]看成是一个首尾相接的圆环，即Sq.elem[0]与Sq.elem .[maxsize-1]相接在一起。这种形式的顺序队列称为循环队列。
用线性链表表示的队列称为链队列。链表的第一个节点存放队列的队首结点，链表的最后一个节点存放队列的队尾首结点，队尾结点的链接指针为空。另外还需要两个指针（头指针和尾指针）才能唯一确定，头指针指向队首结点，尾指针指向队尾结点
递归
定义：若一个函数部分地包含它自己或用它自己给自己定义,则称这个函数是递归的；若一个算法直接地或间接地调用自己,则称这个算法是递归的算法。
树
①结点的度：结点拥有子节点的个数
②树的度：该树中最大的度数
③叶子结点：度为零的结点
④分支结点：度不为零的结点
⑤内部结点：除根结点之外的分支结点
⑥开始结点：根结点又称为开始结点
结点的高度：该结点到各结点的最长路径的长度
森林：m（m≥0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；
反之，给m棵独立的树增加一个根结点，并把这m棵树作为该结点的子树，森林就变成一棵树。
2．结点的层数和树的深度
①结点的层数：根结点的层数为1，其余结点的层数等于其双亲结点的层数加1。
②堂兄弟：双亲在同一层的结点互为堂兄弟。
③树的深度：树中结点的最大层数称为树的深度。
注意：要弄清结点的度、树的度和树的深度的区别。
树中结点之间的逻辑关系是“一对多”的关系，树是一种非线性的结构
树的遍历
先序遍历：访问根结点——先序遍历根的左子树——先序遍历根的右子数
中序遍历：中序遍历左子树——访问根结点——中序遍历右子树
后序遍历：后序遍历左子树——后序遍历右子树——访问根结点
最优二叉树（哈夫曼树）：最小两结点数相加的值再与次小结点数合并。
已知一棵二叉树的前根序序列和中根序序列，构造该二叉树的过程如下：
1. 根据前根序序列的第一个元素建立根结点；
2. 在中根序序列中找到该元素，确定根结点的左右子树的中根序序列；
3. 在前根序序列中确定左右子树的前根序序列；
4. 由左子树的前根序序列和中根序序列建立左子树；
5. 由右子树的前根序序列和中根序序列建立右子树。
-已知一棵二叉树的后根序序列和中根序序列，构造该二叉树的过程如下：
1. 根据后根序序列的最后一个元素建立根结点；
2. 在中根序序列中找到该元素，确定根结点的左右子树的中根序序列；
3. 在后根序序列中确定左右子树的后根序序列；
4. 由左子树的后根序序列和中根序序列建立左子树；
5. 由右子树的后根序序列和中根序序列建立右子树。
图
G= ( V , E ) = ( 顶点，边）
无向完全图有n（n - 1）/ 2 个边 ，有向完全图有n（n - 1）个边 。n表结点。
边无向()，弧有向<>
迪杰斯特拉（Dijkstra）算法
是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
弗洛伊德（Floyd）算法<邻接矩阵求>
是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
普里姆(Prim)算法
普里姆算法的基本思想：
从连通网络N= {V,E}中的某一顶点u0出发,选择与它关联的具有最小权值的边(u0,v),将其顶点加入到生成树顶点集合S中。以后每一步从一个顶点在S中而另一个顶点不在S中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合S中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合S中为止。
克鲁斯卡尔(Kruskal)算法
克鲁斯卡尔算法的基本思想：
设有一个有n个顶点的连通网络N= {V,E},最初先构造一个只有n个顶点,没有边的非连通图T= {V,∅},图中每个顶点自成一个连通分支。当在E中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分支上，则将此边加入到T中;否则将此边舍去，重新选择一条权值最小的边。如此重复下去,直到所有顶点在同一个连通分支上为止。
排序
冒泡排序：比较相邻2数，大的数后移小的数前移选出max/min（反之亦可）
如：有 4 3 1 7 2 5，i = 1时：1 4 3 2 7 5（两两相比）
i = 2时：1 2 4 3 5 7
简单选择排序：首先在所有记录中选出排序码最小的记录，与第一个记录交换，然后在其余的记录中再选出排序码最小的记录与第二个记录交换，以此类推，直到所有的记录排好序为止。
如：有 3 2 4 1 ， i = 1时：1 2 4 3
i = 2时：1 2 3 4
快速排序：被广泛认为它是解决一般问题的最佳排序算法，它比较适合解决大规模数据的排序。
快速排序首先选取一个“基准数”，通过基准数将大于它和小于它的数无序地放在基准数的两边
如：有 4 3 1 7 2 5 ， i = 1时：3 1 2 4 5 7（以4为基准数）
i = 2时：1 2 3 4 5 7（以3为基准数）
插入排序： 略
排序小结
1、就平均时间性能而言，快速排序最佳。但在最坏情况下不如堆排序和归并排序。（归并排序对n较大时适用）
2、当序列中的记录“基本有序”或n值较小时，直接插入排序是最佳的方法，因此常将它与其他排序方法结合使用，如快速排序、归并排序等。
3、基数排序的时间复杂度也可写成O(d*n)，因此它最适用于n值很大而关键字较小的序列。
4、稳定的排序方法：简单排序。不稳定的排序方法：快速排序、堆排序。
一般来说，排序过程中的“比较”是在相邻的两个记录的关键字之间进行的排序方法是稳定的。
