1.堆分配存储表示（也是一种顺序表）
 

typedef struct{
	char *ch;
	int length;
}HString;

 2.串操作函数
 

 
 

//初始化一个串
void InitalStr(HString &T);
//生成一个其值等于串常量chars的串T.
void StrAssign(HString &T, char *chars);
//返回串的长度
int StrLength(HString &T);
//比较串大小，从第一个开始比较，若T>S返回>0，若S=T 返回0；若T<S返回<0
int StrCompare(HString &T, HString &S);
//将T清空为空串
int ClearString(HString &T);
//用T返回S1和S2连接的新串
void Concat(HString &T, HString &S1, HString &S2);
//用Sub返回串T的第Pos个字符，长度为len的子串
int SubString(HString &Sub, HString &T, int pos, int len);

 
 
3.函数实现
 

#include<stdio.h>
#include<stdlib.h>
#include"HStringOp.h"
//初始化一个串
void InitalStr(HString &T){
	T.ch = NULL;
	T.length = 0;
}

//生成一个其值等于串常量chars的串T.
void StrAssign(HString &T,char *chars){
	int i = 0,j=0;
	char *c;
	if (T.ch)free(T.ch);
	for (i = 0, c = chars; *c; ++i, ++c);
	if (!i)
	{
		T.ch = NULL;
		T.length = 0;
	}
	else
	{
		if (!(T.ch = (char *)malloc(i*sizeof(char))))exit;
		while (j<i)
		{
			T.ch[j] = chars[j];
			j++;
		}
		T.length = i;
	}
}
//返回串的长度
int StrLength(HString &T){
	return T.length;
}
//比较串大小，从第一个开始比较，若T>S返回>0，若S=T 返回0；若T<S返回<0
int StrCompare(HString &T, HString &S){
	int i = 0;
	for ( i = 0; i < T.length&&i<S.length; i++)
	{
		if (T.ch[i]!=S.ch[i])
		{
			return T.ch[i] - S.ch[i];
		}
	}
	return T.length - S.length;
}
//将T清空为空串
int ClearString(HString &T){
	if (T.length == 0)return 1;
	free(T.ch);
	T.ch = NULL;
	T.length = 0;
	return 1;
}

//用T返回S1和S2连接的新串

void Concat(HString &T,HString &S1,HString &S2){
	if (T.ch)free(T.ch);
	if (!(T.ch=(char *)malloc((S1.length+S2.length)*sizeof(char))))exit;
	for (int i = 0; i < S1.length; i++)
	{
		T.ch[i] = S1.ch[i];
	}
	for (int i = S1.length; i < S1.length+S2.length; i++)
	{
		T.ch[i] = S2.ch[i-S1.length];
	}
	T.length = S1.length + S2.length;
}

//用Sub返回串T的第Pos个字符，长度为len的子串
int SubString(HString &Sub,HString &T,int pos,int len){
	if (!T.length)return 0;
	if (pos > T.length)return 0;
	if (Sub.ch)free(Sub.ch);
	if (T.length<(pos+len-1))Sub.length = T.length - pos + 1;
	else  Sub.length = len;
	
	Sub.ch = (char *)malloc(Sub.length*sizeof(char));
	for (int i = 0; i < Sub.length; i++)
	{
		Sub.ch[i] = T.ch[i + pos-1];
	}
	return 1;
}

 

 
 
4.子串位置定位一般算法,返回第pos个字符后子串的位置
 

int pos_substr(HString &F,HString &S,int pos){
	int i = pos, j = 0;
	int Flength = StrLength(F);
	int Slength = StrLength(S);
	if (Slength+pos>Flength)
	{
		return 0;
	}
	while (i<Flength&&j<Slength)
	{
		if (F.ch[i]==S.ch[j])
		{
			++i; ++j;
		}else
		{
			i=i-j+1; j = 0;
		}
		
	}
	if (j >=Slength)return i+1 - Slength;
	else  return 0;
}

 

 
 
5.KMP算法
 
(1)求next函数
 

//next函数求值
void get_next(HString &S,int *p){
	int i = 0, j = 0;
	i = 0; *p = 0;
	while (i<S.length-1)                //书中T[0]存放的是字符串的长度，我们这里T[0]也属于字符串的内容
	{
		/*
		实际上求next算法也是一个匹配的过程
		当ch[i]==ch[j-1]时说明，主串第i+1个（我们这里字符串从0开始）之前有j个字符与子串匹配。则p[i+1]=j;同时继续比较ch[i+1]=ch[j]
		当ch[i]！=ch[j-1]时说明，主串第i个字符与子串第j-1个字符适配，这时候需要获取子串的第j-1个next个值，再与主串进行比较
		这里表示next值的指针也是从0标号开始，与书上不同。
		*/
		if (j==0||S.ch[i]==S.ch[j-1]){   
			i++; j++;
			p[i] = j;
		}
		else
		{
			j = p[j-1];
		}
	}
}
 

 
 
求next函数改进算法
 

//KMP模式匹配改进算法
void get_nextval(HString &S, int *p){
	int i = 0, j = 0;
	i = 0; *p = 0;
	while (i < S.length - 1)                //书中T[0]存放的是字符串的长度，我们这里T[0]也属于字符串的内容
	{
		if (j == 0 || S.ch[i] == S.ch[j - 1]){
			i++; j++;
			if (S.ch[i]!=S.ch[j-1])
			{
				p[i] = j;
			}
			else{
				p[i] = p[j-1];
			}
		}
		else
		{
			j = p[j - 1];
		}
	}
}

 (2)KMP实现定子串位置函数
 

//KMP模式匹配算法
int Index_KMP(HString T,HString S,int pos,int *p){
	int i = pos, j = 0;
	while (i<S.length&&j<T.length)
	{
		if (S.ch[i]==T.ch[j])
		{
			i++; j++;
		}
		else
		{
			j = p[j];
			if (j==0)
			{
				i++;
			}
			else
			{
				j--;
			}
		}
	}
	if (j>=T.length)
	{
		return i - T.length+1;
	}
	else
	{
		return 0;
	}
}

 

 
 

 

 

 

1、用链表表示线性表的优点是（便于插入和删除操作）
 
2、单链表中，增加头结点的目的是（方便运算的实现）
 
3、栈和队列的共同特点是（只允许在端点处插入和删除元素）
 
4、栈通常采用的两种存储结构是（线性存储结构和链表存储结构）
 
5、队列具有（先进先出）的特征，栈具有（后进先出）的特征。
 
6、链表（插入和删除不需要移动元素，但是无法随机访问任一元素）
 
7、循环链表的主要优点是（从表中任一结点出发都能访问到整个链表）
 
8、线性表（除了第一个和最后一个元素外，其余每个元素都有一个直接前驱和直接后继）
 
9、线性表的顺序存储结构和线性表的链式存储结构分别是（随机存取的存储结构、顺序存取的存储结构）
 
10、深度为5的满二叉树中，叶子结点的个数为（16）。其共有（31）个结点。
 
       设一棵完全二叉树共有699个结点。则该二叉树的叶子结点数为（350）个。 
 
             #完全二叉树总的结点数为N，若N为奇数，则叶子结点数为（N+1）/2；若N为偶数，则叶子结点数为N/2。
 
11、具有3个结点的二叉树有（5）种形态。 #高度为2层的是：根-左-右。高度为3层的是：根-左-左、根-左-右、根-右-右、根-右-左。
 
12、一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（13）个。
 
      #叶子结点数n0与度为2的结点数n2的关系是：n0＝n2＋1，所以度为2的结点个数为3-1=2。所以总的结点数为 n=n0+n1+n2, 8+2+3=13.
 
13、已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（cedba）。#过程见文章：点击打开链接
 
14、已知二叉树的前序遍历序列是abdgcefh,中序遍历序列是dgbaechf,它的前序遍历序列是（gdbehfca）。
 
15、算法是指（解决方案的准确而完整的描述）。
 
16、算法由（顺序、选择、循环）控制结构组合而成。
 
17、算法的时间复杂度是指（算法执行过程中所需要的基本运算次数）。
 
18、算法的空间复杂度是指（执行过程中所需要的存储空间）。
 
19、算法分析的目的是（分析算法的效率以求改进）。
 
20、数据的存储结构是指（数据的逻辑结构在计算机中的表示）。
 
21、数据的逻辑结构是指（反映数据元素之间逻辑关系的数据结构）。
 
22、根据数据结构中各元素之间前后件关系的复杂程度，可将数据结构分为（线性结构和非线性结构）。
 
线性结构一般是首无前驱，尾无后继，中间元素有唯一的前驱和后继。主要有：列表、链表、队列、栈。
 
非线性结构主要有1、没有对应关系的 集合。2、一对多关系的 树。3、多对多关系的 图。
 
23、（队列，循环队列，顺序表）不具有记忆功能，（栈）具有记忆功能。
 
24、递归算法一般需要用（栈）来实现。
 
#在递归算法的运行过程中，需要利用栈来保存其运算结果、参数和返回地址等。
 
25、算法的五个基本特征是：可行性，确定性，和拥有足够的情报
 
有限性：算法在执行有限步后必须终止。
 
确定性：算法的每个步骤都需要精确地定义，严格地、无歧义的运行。
 
输入：算法在运行之前赋给它的量。
 
输出：算法运行结束时的结果。
 
可行性：算法原则上能够精准地运行，而且人们用纸和笔做有限次运算后即可完成。
 
26、由两个栈共享一个存储空间的好处是（节省存储空间，降低上溢发生的概率）。
 
为了不发生上溢错误，就必须给每个栈分配一个足够大的存储空间。但实际中，很难准确地估计，若每个栈都分配过大的存储空间，势必造成系统空间紧张；若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使它们的存储空间互补
 
27、需要打印机输出数据时，一般将打印作业放在一个（队列）中。
 
28、非空的循环单链表head的尾结点（由 p 所指向） ，满足（p->next=head ）。
 
29、与单链表相比，双向链表的优点是（更容易访问相邻结点）。
 
30、
 
31、N个顶点的连通图中边的条数至少为（N-1）条。#将所有顶点连成一条线即可
 
32、N个顶点的强连通图中边的条数至少为（N）条。#将所有顶点连成一条圈
 
33、对长度为n的线性表进行顺序查找，最坏情况下需要比较（N）次。
 
34、最简单的交换排序是（冒泡排序）。
 
35、对长度为n的线性表进行顺序冒泡排序，最坏情况下需要比较（n(n-1)/2）次。
 
        #一共比较n-1遍，第1遍需要比较n-1次，第1遍需要比较n-2次,........最后一遍需要比较1次。是一个等差序列，对其进行求和即可。
 
36、在序列基本有序的情况下，效率最高的方法是（A） #如果将插入排序换为冒泡排序，则选冒泡排序
 
         A．插入排序   B．选择排序   C．快速排序   D．堆排序
 
        插入排序通过数据元素的交换来逐步消除线性表中的逆序，所以比较的次数与初始排列次序有关，在待排序的元素序列基本有序的前提下，效率最高。而选择排序和堆排序的比较次数与初始排列次序无关。快速排序虽然与初始排列次序有关，但在待排序的元素序列基本有序的前提下，效率低于插入排序。
 
37、希尔排序属于（插入类排序），堆排序属于（选择类排序）。
 
38、在下列几种排序方法中，要求内存量最大的是（D）.
  
 
        A．插入排序  B．选择排序  C．快速排序  D．归并排序
 
        快速排序的基本思想是，通过一趟排序将待排序记录分割成独的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续进行排序，以达到整个序列有序；插入排序的基本操作是指将无序序列中的各元素依次插入到已经有序的线性表中，从而得到一个新的序列；选择排序的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面(这是它应有的位置)，然后对剩下的子表采用同样的方法，直到表空为止；归并排序是将两个或两个以上的有序表组成合成一个新的序列表。
 
39、已知数据表 A中每个元素距其最终位置不远，为节省时间， 应采用（直接插入排序）。
 
40、数据结构是指相互有关联的( 数据元素 )的集合。
 
41、数据元素之间的任何关系都可以用 (前驱和后继) 关系来描述。
 
42、顺序存储方法是把逻辑上相邻的结点存储在 (物理位置) 相邻的存储单元中。
 
43、栈的基本运算有三种：入栈、退栈与读栈顶元素。
 
44、队列主要有两种基本运算：入队和退队。
 
45、在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为 (可利用栈) .
 
46、栈和队列通常采用的存储结构分别是 链式存储和顺序存储。
 
47、当循环队列非空且队尾指针等于对头指针时， 说明循环队列已满，不能进行入队运算。这种情况称为 (上溢) 
 
48、当循环队列为空时， 不能进行退队运算， 这种情况称为 (下溢)。
 
49、在一个容量为 25 的循环队列中， 若头指针 front=16 ， 尾指针 rear=9 ， 则该循环队列中共有 18 个元素。        注： 当 rear<front 时， 元素个数＝总容量－（ front －rear ）； 当 rear>front 时，元素个数＝ rear －front 。
 
50、判断一个链表是否存在环：点击打开链接
 
        单链表中元素的反转：点击打开链接
 
        判断两个数组中是否有相同的数字：点击打开链接
 
        从一个子序列中找出其最大子序列的和：点击打开链接
 
        按单词反转字符串：点击打开链接
 
        删除数组中重复的元素：点击打开链接
 
 
 
1、数组和链表的区别
 
      数组不允许动态地定义其大小，只能够将其定义成足够大小，这样可能会造成空间的浪费。
 
      数组在内存中是顺序的存储，可以以O(1)时间查找元素，但是需要O(n)时间插入和删除元素（因为其后面的元素都需要跟着移动）。
 
      链表可以动态地定义其大小。其在内存中是链式的存储，访问元素是需要从头开始向后顺序访问，所以需要O(n)时间查找元素；如果在所需位置直接插入或删除元素，需要O(1)时间，如果在需要先找到所需位置再插入或删除元素，需要O(n)时间。
 
2、链表的基本操作：反转，是否存在环，循环链表点击打开链接和双向链表点击打开链接的查找、插入、删除操作。
 
3、栈的入栈和出栈：点击打开链接，队列的入队和出队：点击打开链接
 
4、二叉树的基础知识：点击打开链接及其三种遍历（递归和非递归实现）：点击打开链接
 
5、图的基础知识：点击打开链接
 
6、常用散列函数和冲突消解机制：点击打开链接
 
 
 
7、排序算法中基本的冒泡排序、选择排序、插入排序需要很快地用代码实现。堆排序、归并排序、快速排序需要掌握其主要思想，并熟悉常用排序算法的时间和空间复杂度，及其应用范围：
 
    (1) 当数据规模较小时，直接采用直接插入排序或直接选择排序。
 
    (2) 当数据已经基本有序时，可以用直接插入排序或冒泡排序。
 
    (3) 当数据规模较大时，可以用快速排序。当记录随机分布时，快速排序的平均时间最短。当最坏情况时，其时间复杂度为O(n2)，空间复杂度为O(n)。
 
     (4) 堆排序所需的辅助空间比快排少，但这两种方法都不稳定。
 
     (5) 归并排序既可以用于内部排序，也可以用于外部排序，是一种稳定的算法。
 
8、能熟练写出二分查找的程序。
 
9、熟悉算法的思想：贪心算法，动态规划，分治算法。
 
 
 
 
 
参考：https://www.cnblogs.com/houjun/p/4896268.html

概论
 
 
 
 
名词解释:
 
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合,是计算机存储和组织数据的方式,它分为三个方面,即数据的逻辑结构,数据的物理结构,数据的操作.
 
数据项:是数据不可分割的最小单位,用它可以识别一个或一组数据,一个数据元素可由若干数据项组成.
 
数据元素(记录):是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理,一个数据元素可由若干数据项组成.
 
数据对象:是性质相同的数据元素的集合,是数据的一个子集.
 
数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称,是计算机化的信息.
 
数据类型:是一个值的集合以及定义在这个值集上的一组操作,可分为原子类型和结构类型.
 
抽象数据类型:是基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作.
 
逻辑结构:是数据元素之间逻辑关系的描述.
 
物理结构(存储结构):是指数据的逻辑结构在计算机中的映像(又称表示),即数据结构在计算机中的存储方法.
 
算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作.
 
时间复杂度:算法执行所需时间的量度.
 
空间复杂度:算法执行所需存储空间的量度.
 
存储密度:指结点数据本身所占存储量和整个结构所占存储量之比.
 
填空题:
 
程序设计的一些基本原则:分解.抽象和信息隐蔽.
 
根据数据元素之间关系的不同特性,有四类基本的数据结构:集合结构,线性结构,树型结构,图形结构(网状结构).
 
数据的存储结构有:顺序存储结构.链式(链接)存储结构.索引存储结构,散列存储结构.常用的两种存储结构:顺序存储结构和链式存储结构.
 
算法的五个特性:确定性.有穷性.可行性.输入和输出.(可以有零个或多个数据输入,但必须至少有一个输出数据)
 
算法设计的要求:正确性,可读性,稳健性,高效率低存储量.
 
沃思公式:程序=算法+数据结构.
 
(算法分析)衡量算法的两个标准:时间复杂度和空间复杂度.
 
一个算法的设计取决于所选的逻辑结构.
 
一个算法的实现取决于所选的存储结构.
 
结构化程序设计思想的要求:自顶向下.逐步细化.模块化设计.结构化编程.
 
简答题:
 
顺序存储结构的特点?(顺序存储和链式存储的优缺点)
 
1.结点中只存放数据元素本身的信息,无附加内容.
 
2.可直接存取数据元素.
 
3.存取操作速度较快.
 
4.插入.删除数据元素时,由于需要保持数据元素之间的逻辑关系,必须大量移动元素,因此实现起来较慢.
 
5.顺序存储是一种静态结构,存储密度大,空间利用率低,预分配空间大小难以确定.
 
链式存储结构的特点?(顺序存储和链式存储的优缺点)
 
1.结点中除存放数据元素本身的信息外,还需存放附加的指针.
 
2.不能直接存取数据元素,需顺链查找,存取速度较慢.
 
3.插入.删除元素时不必移动其他元素,速度较快.
 
4.链式存储是一种动态存储结构,空间利用率高,存储密度小,不存在预分配空间问题.
 
线性结构与非线性结构的特点(或差异)?
 
线性结构的特点是:除第一个元素和最后一个元素外,每个数据元素都有唯一的前驱和唯一的后继,第一个元素没有前驱,最后一个元素没有后继,关系是一对一的.
 
非线性结构的特点是:表示结点间关系的前驱后继不具有唯一性,结点间是一对多或多对多的关系.
 
逻辑结构与物理结构的区别和联系?
 
1.数据的物理结构也称为存储结构.
 
2.数据的逻辑结构仅考虑数据之间的逻辑关系.
 
3.数据的物理结构是数据的逻辑结构在计算机中的映像.
 
4.数据的逻辑结构独立于数据的存储介质.
 
数据结构与数据类型的区别和联系?
 
数据结构是相互之间存在一种或多种特定关系的数据元素的集合,是计算机存储和组织数据的方式,它分为三个方面,即数据的逻辑结构,数据的物理结构,数据的操作.它偏向于逻辑方面,而数据类型是一个值的集合以及定义在这个值集上的一组操作,可分为原子类型和结构类型.它偏向于物理方面.
 
线性表
 
 
名词解释:
 
线性表:是最常用,最简单的一种数据结构,一个线性表是n个数据元素的有限序列,除首尾元素外,每个元素有唯一的前驱和唯一的后继.
 
顺序表:采用顺序存储结构的线性表通常称为顺序表.
 
链表:采用链式存储结构的线性表通常称为链表.
 
结点:由数据元素和指示其后继结点地址的信息组成的存储映像称为结点.
 
表长:表中元素的个数称为表的表长.
 
循环链表:是另一种形式的链式存储结构,它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环.
 
双链表:采用链式存储结构的线性表,每个结点除一个数据域外,还有两个指针域,其一指向直接前驱,另一指向直接后继.
 
静态单链表:是利用一块连续的空间,按链表的存储方式组织数据,按顺序存储结构分配空间,所构成的一种链表.
 
头指针:是指向链表表头结点的指针,只要链表存在,该指针始终不会改变,单链表由头指针唯一确定,因此单链表可以用头指针的名字来命名.
 
头结点:在链表的开始结点之前附加的一个结点,是链表的表头,当链表不空时,其内的指针指向链表的第一个结点,当链表是空链表是,该指针为空指针.
 
填空题:
 
线性表的两种基本的存储结构:顺序存储结构和链式存储结构.
 
从实现角度看,链表可分为静态链表和动态链表.
 
从链接方式的角度看,链表可分为单链表,循环链表,双链表.
 
添加哨兵可以保持首指针的稳定性,方便表示空表.
 
一元多项式的表示和相加可以使用链表实现.
 
简答题:
 
顺序表的优缺点?
 
优点:    1.无需为表示结点间的逻辑关系而增加额外的存储空间,存储密度大.
 
            2.可随机存取表中的任一元素,查找方便.
 
缺点:    1.插入,删除运算不方便,须移动大量元素,效率较低.
 
            2.存在预分配空间问题.
 
链表的优缺点?
 
优点:    1.插入,删除操作很方便.
 
            2.空间利用率高.
 
缺点:    1.查找不方便,需顺链查找
 
            2.存储密度小.
 
顺序表和链表的区别和联系及适用范围?
 
顺序表:    内存中地址连续
 
               长度一般不可变更
 
               支持随机查找,可在O(1)内查找元素
 
               适用于需要大量访问元素的,而少量增删元素的程序.
 
链表:        内存中地址连续或非连续都可以
 
                长度可实时变化
 
                不支持随机查找,查找元素的时间复杂度为O(n)
 
                适用于需要大量增删元素,而对访问元素几乎无要求的程序.
 
头指针和头结点的作用?
 
1.头指针是指向链表表头结点的指针,只要链表存在,该指针就不会变化,已知该指针便已知该链表.
 
2.头结点是在链表的开始结点之前夫妇家的一个结点,当链表是空链表时,该指针为空指针,因此空表和非空表的处理也就统一了.
 
简述在单循环链表上尾指针取代头指针的作用?
 
在用头指针表示的单循环链表中,找开始结点a1的时间是O(1),然而要找终端结点an则需要从头指针开始遍历整个链表,其时间是O(n) ,在很多实际问题中,表的操作常常是在表尾进行的,此时头指针表示的单循环链表就显得不够方便,如果改用尾指针来表示单循环链表,则查找开始结点a1和终端结点an都很方便,查找时间都是O(1).
 
栈和队列
 
 
 
 
名词解释:
 
 
 
栈:也叫后进先出表,是限定仅在表尾进行插入和删除操作的线性表,表尾端称为栈顶,表头端称为栈底,不含元素的空表称为空栈,
 
顺序栈:采用顺序存储结构的栈称为顺序栈.
 
链栈:采用链式存储结构的栈称为链栈.
 
队列:是一种先进先出的线性表,它只允许在表的一段进行插入,而另一端删除元素,允许插入的一端叫做队尾,允许删除的一端称为队首.
 
链队列:用链表示的队列,需要两个指针分别指示队头和队尾,为了操作方便,也给链队列添加一个哨兵结点.
 
循环队列:队列是"先进先出表",随着入队出队的进行,会使整个队列整体向后移动,当队尾指针移到最后,若再有元素入队就会出现"假溢出",因为此时队头部分还有空间可用,循环队列是将队列的数据区看成头尾相接的循环结构,可解决"假溢出"现象.
 
双端队列:是限定插入,删除在表的两端进行的线性表,这两端分别称为端点.
 
填空题:
 
栈的两种存储方式:顺序存储和链式存储.
 
栈满的判断条件:s.top==stack.size.
 
栈空的判断条件:s.top==0.
 
栈满入栈栈上溢,栈空出栈栈下溢.
 
链栈使用多栈共享技术时,可使用静态链表结构实现.
 
队列的两种存储方式:顺序存储和链式存储.
 
循环队列采用少用一个元素存储空间的办法下,判断队列满的条件:front==(rear+1)%size.
 
循环队列判断队列满的方法有:少用一个元素存储空间,增设一个标志量,使用计数器.
 
队列的应用:杨辉三角.
 
栈的应用:数制转换,括号匹配,表达式求值,汉诺塔(递归用栈实现).
 
简答题:
 
什么是多栈共享技术?
 
在一个程序中经常会同时使用多个栈,使用顺序存储结构的栈,空间大小难以估计,这样使得有的栈已出,有的栈还有空闲空间,可以让多个栈共享一个足够大的连续向量空间(数组),通过利用栈的动态特性來使其存储空间互相补充,这就是多栈的共享技术,两个栈共享空间,主要利用了"栈底位置不变,栈顶位置动态变化"的特性.
 
与顺序队列相比,循环队列有哪些优点?
 
可解决假溢出现象(内容自行拓展).
 
简述线性表,栈,队列的区别和联系?
 
相同点:    都是线性结构,都是逻辑结构的概念,都可以用顺序存储或链式存储,栈和队列是两种特殊的线性表,即受限的线性表,只对插入和删除运算加以限制.
 
不同点:    1.运算规则不同,线性表为随机存取,而栈只允许在一端进行插入,删除运算,因而是后进先出表,队列只允许在一端进行插入,另一端删除运算,因而是先进先出表.
 
                2.用途不同,堆栈用于子程调用和保护现场,队列用于多道作业处理,指令寄存及其他运算等.
 
串
 
 
名词解释:
 
串:是由零个或多个字符组成的有限序列.
 
子串:串中任意个连续的字符组成的子序列称作该串的子串.
 
主串:包含子串的串相应的称为主串.
 
子串在主串中的位置:子串的第一个字符在主串中的位置表示.
 
空串:长度为零的串称为空串.
 
空格串:串中元素均为空格的串称为空格串.
 
串相等:长度相等且对应位置字符都相等.
 
填空题:
 
在程序中,串分为串常量和串变量.
 
串的存储结构:顺序存储结构,链式存储结构,堆存储结构.
 
串的应用:文本编辑.
 
简答题:
 
串和线性表的区别?
 
串的逻辑结构与线性表极为相似,区别仅在于串的数据对象约束为字符集,然而串的操作与线性表有很大的差别,在线性表基本操作中,大多以单个元素作为操作对象;而在串的基本操作中通常以"串的整体"作为操作对象.
 
简述静态分配的顺序串与动态分配的顺序串的区别?
 
程序运行前被分配以一个给定大小的数组空间的顺序串称为静态顺序串,在程序运行过程中,动态分配空间能以链表形式存在的顺序串称为动态顺序串,静态串在内存一片连续的数据区中,动态串在内存堆中.
 
串的链式存储与串的顺序存储相比,在哪些操作上效率更高?
 
插入,删除,因为无需移动其他元素(内容自行扩充).
 
数组与广义表
 
 
 
名词解释:
 
广义表:是由零个或多个单元素或子表所构成的有限序列,是线性表的推广,也有人称其为列表.
 
数组:类型一致的有限个数据元素按顺序连续存储.
 
矩阵的压缩存储:有的矩阵中有许多值相同元素或者是零元素,为了节省存储空间对这类矩阵采用多个值相同的元素只分配一个存储空间,有时零元素不存储的存储策略,称为矩阵的压缩存储.
 
特殊矩阵:值相同的元素或者零元素在矩阵中的分布有一定规律的矩阵称为特殊矩阵.
 
稀疏矩阵:非零的数据元素个数很少的矩阵称为稀疏矩阵.
 
对称矩阵:一个n阶方阵,若满足aij=aji,则称该矩阵为对称矩阵.
 
三角矩阵:主对角线上方和下方的元素(不包括对角线)均为常数或零元素的矩阵.
 
行表:记录稀疏矩阵中每行非零元素在三元组表中的起始位置的表.
 
三元组表:若线性表顺序存储的每一个结点均是三元组,则该线性表的存储结构称为三元组表.
 
带状矩阵:所有非零元素均集中在以主对角线为中心的带状区域的矩阵.
 
填空题:
 
数组的两种存储方式:顺序存储和链式存储.
 
数组的顺序存储有两种方式:按行存储和按列存储.
 
稀疏矩阵可以采用三元组表和十字链表来存储.
 
简答题:
 
广义表和线性表的区别?
 
1.广义表是线性表的推广,是由零个或多个单元素或子表所构成的有限序列.
 
2.线性表的成分都是结构上不可分割的单个数据元素,而广义表的成分既可以是单元素,也可以是有结构的表,其定义是递归的定义.
 
树和二叉树
 
 
 
名词解释:
 
树:是n个结点的有限集合,n≥0,有且只有一个称为根的结点,根结点无前驱.
 
森林:m(m≥1)棵互不相交的树的集合.
 
有序树:树中结点的各子树看成是从左至右依次有序的,且不能交换.
 
二叉树:是一种树型的结构,它的特点是每个结点之多有两棵子树,且有左右之分,不可任意颠倒.
 
完全二叉树:深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时.
 
满二叉树:是一棵深度为k的,且有(2^k)-1个结点的二叉树.
 
遍历二叉树:是按照某种搜索路径巡访二叉树中的每个结点,使得这些结点均被访问一次.
 
线索二叉树:由每个结点中包含左指针,左标志位,数据域,右标志位,右指针五部分组成的二叉链表,叫做线索链表,指向前驱或后继的指针叫做线索,以二叉树某一种遍历顺序给空指针加线索的过程叫做线索化,线索化了的二叉树称为线索二叉树.
 
哈夫曼树:又称最优二叉树,是一类带权路径长度最短的树.
 
哈夫曼编码:在哈夫曼树中,约定左分支代表0,右分支代表1,把叶子结点到根结点的路径上的左右分支代表的码从下至上一次连接起来,组成的字符串称为该叶子结点的哈夫曼编码,这就是哈夫曼编码.
 
二叉排序树:或者是空树,或者是符合以下性质的二叉树.
 
                    1.若它的左子树不空,则左子树上所有结点均小于它的根结点值.
 
                    2.若它的右子树不空,则右子树上所有结点均大于它的根结点值.
 
平衡二叉排序树(AVL树):或者是空树,或者是符合一下性质的二叉排序树.
 
                    1.左子树和右子树的高度之差的绝对值小于等于1.
 
                    2.左子树和右子树也是平衡二叉排序树.
 
B-树(B树):略,看书.
 
填空题:
 
在二叉树中,第i层结点最多为2^k-1个.
 
深度为k的二叉树中,结点总数最多为(2^k)-1个.
 
二叉树中,n0=n2+1,n2=n0-1(n0为二叉树中度为0的结点的个数,n2为二叉树中度为2的结点的个数).
 
有n个结点的完全二叉树,深度为k,则k=⌊log2n⌋+1.(log以2为底,括号是向下取整,不是方括号)
 
k层的完全二叉树至少有2^k-2个叶子结点.
 
二叉树的两种存储结构:顺序存储结构和链式存储结构.
 
树的三种常用的存储方法:孩子表示法,双亲表示法和孩子兄弟表示法.
 
树的遍历方法:先根遍历和后根遍历.
 
简答题:
 
非线性结构的特点?
 
表示结点间关系的前驱后继不具有唯一性,结点间是一对多或多对多的关系.
 
二叉树的五种基本形态?
 
(1)空二叉树——如图(a)；
 
(2)只有一个根结点的二叉树——如图(b)；
 
(3)只有左子树——如图(c)；
 
(4)只有右子树——如图(d)；
 
(5)完全二叉树——如图(e)。
 
 
只有三个结点的二叉树的五种形式?
 
因为二叉树是有序树,所有有左右之分,这是五棵不同的二叉树,但若下列五棵是树,不是二叉树,则后面四种为同一棵树.
 
 
 
 
图
 
 
名词解释:
 
图:图G由两个集合V和E组成,记为G=(V,E),其中V是顶点的有穷非空集合,E是由V中顶点的序偶组成的有穷集,这些序偶称为边或弧.
 
顶点:图中的数据元素称为顶点.
 
完全图:边数恰好等于n(n-1)/2的n个顶点的无向图称为完全图(无向图中任意两个顶点之间都有一条边相连,称该图为完全图).
 
有向完全图:有n(n-1)条边的有向图称为有向完全图(图中每个顶点和其余n-1个顶点都有弧相连).
 
入度:以顶点V为头的弧的数目称为V的入度.
 
出度:以顶点V为尾的弧的数目称为V的出度.
 
连通图:在无向图中,任意两个顶点之间都有路径相通.
 
强连通图:在有向图中,任意两个顶点之间都有来回路径相通.
 
生成树:生成树是无向连通图的一个极小连通子图,它含有图中的全部顶点和使任意顶点都连通的最少的边.
 
邻接矩阵:表示图中结点之间关系的矩阵称为邻接矩阵.
 
邻接表:由顶点数据表和表示数据关系的边(弧)构成的表.
 
十字链表:可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种存储形式.
 
图的遍历:从某一顶点出发按序访问图中所有结点,且使每个结点仅被访问一次.
 
最小生成树:无向网中边上权值之和为最小的生成树.
 
DAG:有向无环网.
 
拓扑排序:由某个集合上的一个偏序得到该集合上一个全序的操作称为拓扑排序.
 
关键路径:在AOE网中,从源点到汇点的最长路径称为关键路径.
 
AOE网:用顶点表示事件,用弧表示活动,弧的权值表示活动所需的时间,构造的有向网称为AOE网.
 
简单路径:一条路径上除了开始顶点和结束顶点外,其余顶点均不相同.
 
弧头:边的终点称为弧头.
 
弧尾:边的始点称为弧尾.
 
填空题:
 
边很少的图称为稀疏图,反之称为稠密图.
 
有向图中,所有顶点的入度与出度的和等于边个数的2倍.
 
图的存储方法:邻接矩阵,邻接表,邻接多重表,十字链表和边集数组.
 
图的深度优先搜索类似于树的先根遍历.
 
图的广度优先搜索类似于树的层次遍历.
 
连通图→深度优先搜索遍历→深度搜索生成树
 
连通图→广度优先搜索遍历→广度搜索生成树
 
简答题:
 
邻接矩阵表示法的特点?
 
1.对于无向图而言,它的邻接矩阵是对称矩阵,因此可以采用特殊矩阵的压缩存储法,但对于有向图而言,其中的弧是由方向的,因此有向图的邻接矩阵不一定是对称矩阵,对于有向图的邻接矩阵的存储则需要n*n个存储空间.
 
2.采用邻接矩阵表示法,便于判断图中任意两个顶点之间是否有边相连,即根据邻接矩阵中的信息来判断,另外还便于求得各个顶点的度,对于无向图而言,其邻接矩阵第i行元素之和就是图中第i个顶点的度.
 
邻接表表示法的特点?
 
1.n个顶点,e条边的无向图,若采取邻接表作为存储结构,需要n个顶点数据和2e个表示边的结点,显然在边很稀疏的情况下,用邻接表存储所需的空间比邻接矩阵所需的空间少.
 
2.无向图的度,在无向图的邻接表中,顶点Vi的度恰好就是第i个边链表上结点的个数.
 
3.有向图的度,在有向图中,第i个边链表上结点的个数就是顶点Vi的出度,只需通过表头向量表中找到第i个顶点的边链表的头指针,实现顺链查找计数即可.
 
DFS(深度优先搜索遍历)的基本思路?
 
假设初始状态是图中所有顶点均未被访问过,则深度优先搜索可从某个顶点V出发,首先访问此顶点(称此顶点为初始点),然后依次从V的任一个未被访问的邻接点出发进行深度优先搜索遍历,直到图中所有与V有路径相通的顶点都被访问到,若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作为初始点,重复上述步骤,直到图中所有顶点都被访问过为止.
 
BFS(广度优先搜索遍历)的基本思路?
 
1.从图中某个顶点V0出发,首先访问V0,依次访问V0的各个未被访问的邻接点.
 
2.分别从这些邻接点(端结点)出发,依次访问各个未被访问的邻接点,访问时应保证:如果Vi和Vk为当前结点,且Vi在Vk之前被访问,则Vi的所有未被访问的邻接点应在Vk的所有未被访问的邻接点之前访问.
 
3.重复步骤2,直到所有结点均没有未被访问的邻接点.
 
4.若此时还有顶点未被访问,则选一个未被访问的顶点作为起始点,重复上述过程,直至所有顶点均被访问过为止.
 
查找
 
 
 
 
名词解释:
 
关键字:是数据元素中某个数据项的值,用它可以识别一个或一组数据元素.
 
查找:根据给定的关键字的值,检索某个与该值相等的数据元素是否在查找表中,找到为查找成功,找不到为查找失败.
 
查找表:是由同一类型的数据元素或记录构成的集合.
 
静态查找表:查询某个特定的数据元素是否在查找表中,检索某个特定的数据元素的各种属性.
 
动态查找表:在查找过程中同时插入查找不存在的数据元素,或者从查找表中删除已存在的某个数据元素.
 
平均查找长度(ASL):为确定数据元素在查找表中的位置,需和给定值进行比较的关键字个数的期望值,称为查找算法在查找成功时的平均查找长度.
 
冲突:两个不同的关键字,其散列函数值相同,因而被映射到同一表位置的现象称为冲突.
 
填空题:
 
哈希函数的构造方法:直接定址法,数字分析法,平方取中法,折叠法,除留余数法和随机数法.
 
哈希函数处理冲突的方法:开放地址法,再哈希法,链地址法和建立一个公共溢出区.
 
简答题:
 
各查找方法的基本思想,平均查找长度?
 
顺序查找的基本思路:对于给定的关键字k,从线性表的第一个元素开始依次向后与记录的关键字域相比较,如果某个记录的关键字等于k,则查找成功,否则查找失败.平均查找长度ASL=3(n+1)/4.
 
折半(二分)查找的基本思路:先取表的中间位置的记录关键字和所给关键字进行比较,若相等,则查找成功,如果给定关键字比该记录的关键字小,则说明所要查找的记录只可能在表的前半部分,反之,则在后半部分,重复步骤,每一次比较就可以将查找范围缩小一半,直到找到给定的关键字的记录,查找成功,找不到为查找失败.平均查找长度ASL=log2(n+1)-1.
 
分块查找(索引顺序表查找)的基本思路:先确定待查记录所在的块(子表),然后在块中顺序查找.平均查找长度ASL=1/2[(n/s)+1]+s/2.
 
哈希查找(散列查找)的基本思路:在进行查找时,在记录的存储位置与它的关键字之间建立一个确定的对应关系h,以线性表中每个元素的关键字k为自变量,通过函数h(k)计算出该元素的存储位置,我们将h函数称为散列函数或哈希函数,这种查找方法称为散列查找或哈希查找.
 
排序
 
 
 
 
名词解释:
 
排序:就是按关键字值的递增或递减的次序,把文件中的各记录一次排列起来,可使一个无序文件变成有序文件的一种操作.
 
排序算法的稳定性:相同元素排序前后的相对位置没有发生变化,则为稳定,反之为不稳定.
 
内部排序:在排序过程中,所有待排序记录都放在内存中进行的排序称为内部排序.
 
外部排序:当待排序的记录很多,排序时不仅要使用内存,而且还要使用外部存储器的排序方法称为外部排序.
 
简答题:
 
各排序方法的基本思想,时间复杂度,空间复杂度及稳定性?
 
 
 
直接插入排序的基本思想:直接插入排序是一种最简单的排序方法,基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的,记录数量增一的有序表.时间复杂度O(n^2).空间复杂度O(1).直接插入排序是稳定的.
 
希尔排序的基本思想:先将整个待排元素序列分割成若干子序列分别进行直接插入排序,然后依次缩减增量再进行排序,使整个序列中的元素基本有序时,再对全体元素进行一次直接插入排序,实质就是分组直接插入排序.时间复杂度O(n^2).空间复杂度O(1).希尔排序是不稳定的.
 
冒泡排序的基本思想:先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个记录交换,然后比较第二个记录和第三个记录的关键字,以此类推,直至第n-1个记录和第n个记录的关键字进行过比较为止.时间复杂度O(n^2).空间复杂度O(1).冒泡排序是稳定的.
 
快速排序的基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据进行快速排序,整个排序过程可以递归进行,以达到整个序列有序.时间复杂度O(nlog2n).空间复杂度O(nlog2n).快速排序是不稳定的.
 
直接选择排序的基本思想:对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录与第一个记录的位置交换,接着对不包括第一个记录以外的其他记录进行第二轮比较,得到最小的记录并与第二个记录的位置交换,重复该过程,直到进行比较的记录只有一个时为止.时间复杂度O(n^2).空间复杂度O(1).直接选择排序是不稳定的.
 
堆排序的基本思想:堆排序是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种,可以利用数组的特点快速定位索引的元素,堆分为大根堆和小根堆,是完全二叉树.时间复杂度O(nlog2n).空间复杂度O(1).堆排序是不稳定的.
 
归并排序的基本思想:将待排序序列看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序表再次归并,得到n/4个长度为4的有序序列;如此重复进行下去,最后得到一个长度为n的有序序列.时间复杂度O(nlog2n).空间复杂度O(n).归并排序是稳定的.
 
基数排序的基本思想:是借助"分配"和"收集"两种操作对单逻辑关键字进行排序的一种内排序方法.时间复杂度O(d*n).空间复杂度O(n+r).基数排序是稳定的.
 
作图题
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
附加内容:
 
文件:是由大量性质相同的记录组成的集合,可按其记录的类型不同而分成两类:操作系统文件和数据库文件.
 
定长纪录文件:文件中每个记录含有的信息长度相同,则称这类记录为定长记录,由这类记录组成的文件称为定长纪录文件.
 
不定长记录文件:文件中每个记录含有的信息长度不相同,则称这类记录为不定长记录,由这类记录组成的文件称为不定长纪录文件.
 
文件的操作有两类:检索和修改.
 
文件的检索有三种方式:顺序存取,直接存取,按关键字存取.
 
文件的修改包括插入一个记录,删除一个记录和更新一个记录三种操作.
 
顺序文件:物理记录的顺序与逻辑记录的顺序是一致的.
 
连续文件:若次序相继的两个物理记录在存储介质上的存储位置是相邻的,则称连续文件.
 
串联文件:物理记录之间的次序由指针相链表示,则称串联文件.
 
索引文件:包含文件数据区和索引表两大部分的文件称作索引文件.
 
索引项:索引表中的每一项称为索引项.
 
索引顺序文件:数据区中记录也按关键字顺序排列,则称索引顺序文件,反之为索引非顺序文件.

码字不易，喜欢请点赞！！！
 1.数据结构基础
 2.线性表(顺序存储、链式存储)
 
元素之间是有顺序的：第一个元素无前驱，最后一个元素无后继，其他元素都有前驱和后继
顺序存储结构：用一段地址连续的存储单元一次存储线性表的数据元素(存取时间复杂度为O(1)，插入或删除时间复杂度为O(N)，适合数据量不大并且存取操作多的数据)
优缺点：
 
链式结构：元素信息+后继元素的地址(读取、插入、删除：时间复杂度O(N))
头指针：链表第一个结点的存储位置；
尾结点：后继不存在，即最后一个结点的指针为空；
头结点：第一个结点前设一个结点，可以不存储任何信息，也可以存储长度等附加信息
 
优缺点：
 
 
3.栈
 
4.队列、循环队列
 
5.串
 
 子串查找：KMP算法
 
6.树
 
 
节点的度：节点的分支数目
 
 
树的度：树内各个节点的度的最大值
 
 
叶节点、终端节点：度为0的点
 
 
树的深度：树中节点的最大层次
 
 
 
二叉树：n个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根节点和两颗互不相交、分别称为根节点的左子树和右子树的二叉树组成。
 
 
二叉树的5种形态：
 
 
 
满二叉树：
 
 
 
完全二叉树
 
 
 
二叉树的性质
 
 
 二叉树的第i层，最多有$2^{i-1}$结点
 
 
 深度为k的二叉树，最多有$2^k-1$个节点
 
 
 具有n个结点的完全二叉树的深度为$[lo{g}_2^n]+1$（[x]表示对x下取整）
 
 
 二叉树T，叶子节点数为$n_0$，度为2的节点数为$n_2$，则$n_0$ = $n_2$ + 1
 因为节点数n = $n_0$ + $n_1$ + $n_2$ = 2$n_2$ + $n_1$ + 1
 所以：$n_0$ = $n_2$ + 1
 
 
 
 对于完全二叉树的节点i：
 
 
 
二叉树的存储
 
 
 一维数组存储：使用一维数组按照顺序存储，对于不存在的节点使用空来占位
 
 
 二叉链表：lchild+data+rchild形式
 
 
 
二叉树的遍历：前序遍历、中序遍历、后序遍历、层序遍历(逐层遍历)
 
 
 已知前序和中序，可以确定一颗二叉树
 
 
 已知后序和中序，可以确定一颗二叉树
 
 
 已知前序和后序，不可以确定一颗二叉树
 
 
树、森林、二叉树的转换
 
 
 树转换成二叉树
 
 
1.加线：兄弟节点之间加一条线
2.去线：对每个节点只保留第一个子节点的连线，删除其他子节点的连线
3.层次调整：第一个子节点为左孩子，兄弟节点转成第一个子节点的右孩子
 
eg：
 
 
 森林转成二叉树
 
#森林由多棵树组成，将森林中每一颗树都视为兄弟，按照兄弟的办法来处理
1.将每棵树转成二叉树
2.将后面的树的根节点作为前面的树的根节点的右孩子
 
eg：
 
 
 二叉树转成树
 
#树转成二叉树的逆过程
1.加线：左孩子的所有右孩子，与左孩子的父节点连接起来。
2.去线：删除原二叉树中的所有右孩子连线。
3.层次调整：旋转
 
eg：
 
 
 二叉树转成森林
 
#如果根节点有右孩子，则是森林，没有孩子，则是一棵树
1.先将根节点的右孩子线删除，拆成多颗二叉树
2.然后对每个二叉树执行拆分成树的操作
 
eg：
 
 
 
树与森林的遍历
 
 
 树的遍历：先根遍历、后根遍历
 
 
 
 
 森林的遍历：前序遍历、后续遍历
 
 前序遍历结果：ABCDEFGHJI
 后序遍历结果：BCDAFEJHIG
 
 
 
哈夫曼树
 
 
 简介
 
 
 
1.节点的带权路径：节点到根之间的路径长度与节点权值的乘积
2.树的带权路径：树中所有节点的带权路径之和
3.哈夫曼树：带权路径长度WPL最小的二叉树，称为哈夫曼树，也叫最优二叉树
 
二叉树a的WPL=51+152+403+304+104=315
 二叉树b的WPL=53+153+402+302+102=220
 这个结果意味着，如果有10000个学生需要计算，那么二叉树a的判断方法需要计算31500次，而二叉树b的方法需要计算22000次。
 
 哈夫曼树构造
 
 
 
 
7.图
 
 
定义
 
 
 
无向边：顶点之间没有方向，称这条边为无向边，用无序偶对$(v_i,v_j)$来表示
 
 
有向边：顶点之间有方向，称这条边为有向边，也称为弧，用有序偶对$<v_i,v_j>$来表示，如果图中任意两个顶点的边都是有向边，则称该图为有向图，要区分开弧尾$v_j$和弧头$v_i$
 
 
无向图:如果任意两个顶点之间都存在边，则称该图为无向完全图，含有n个顶点的无向完全图有$n(n-1)/2$条边。
 
 
有向图:如果任意两个顶点间都存在方向互为相反的两条弧，则称为有向完全图。含有n个顶点的有向完全图有$n(n-1)$条边。
 
 
连通图：无向图中，如果两个顶点之间有路径，说明两顶点是连通的，如果对于图中任意两个顶点都是连通的，则称该无向图是连通图。
 
 
极大连通子图称为连通分量：需要是1.子图；2.子图是连通的；3.连通子图含有极大顶点数；4.具有极大顶点数的连通子图包含依附这些顶点的所有边。
 
 
度：无向图顶点的边数叫度，有向图的顶点分为出度和入度。
 
 
生成树、森林：无向图中连通且n个顶点有n-1条边叫生成树；有向图中一个顶点入度为0，其余顶点入度为1称为有向树；一个有向图由若干个有向树构成生成森林。
 
 
图的存储结构
 由于图的结构比较复杂，任意两点之间都可能存在联系，因此不能用简单的顺序存储结构来表示。
 
 
 邻接矩阵
 
 
邻接矩阵的存储方式：两个数组来表示图;
一个一维数组存储图中顶点的信息;
一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
 

 
 
 
 邻接表
 
临近矩阵的问题：对边数相对顶点数较少的图，这种结构是对存储空间的极大浪费，太稀疏。
 
 
邻接表：将数组与链表结合起来
 
无向图：
 
 有向图：
 
 带权有向图：
 
 
 十字链表
 
在有向图中，邻接表是有缺陷的，关心了出度问题，要想知道入度，就必须遍历整个图；
反之逆邻接表解决了入度却不能解决出度；
那能否将邻接表与逆邻接表结合起来呢？
答案是肯定的，于是就有了一种新的有向图的存储方法：十字链表法。
 
 
 
 邻接多重表
 
 
 边集数组
 边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素有一条边的起点下标(begin)、终点下标(end)和权(weight)组成。
 
 
 
图的遍历：深度优先搜索、广度优先搜素
 
 
 深度优先搜索：
 
 
 广度优先遍历：类似于树的层序遍历
 
 
 深度优先更适合目标比较明确，以找到目标为主的情况，广度优先更适合在不断扩大遍历访问时找到最优解的情况。
 
 
最小生成树
 
 
 定义：给定一个无向图，如果他的某个子图中，任意两个顶点都能互相连通并且是一棵树，那么这棵树就叫做生成树，如果边上有权值，那么使得边权和最小的生成树叫做最小生成树。即构成连通网的最小代价生成树称为最小生成树。
 
 
 实际问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？
 
 
 普里姆算法—Prim算法：适合稠密图
 【算法思想】：Prime算法是一种贪心算法，它最初将无向连通图G中所有顶点V分成两个顶点集合VA和VB。在计算过程中VA中的点为已经选好连接入生成树的点，否则属于VB。最开始的时候VA只包含任意选取的图G中的一个点u，其余的点属于VB，每次添加一个VB中的点到VA，该点是集合VB到集合VA中距离最小的一个点。直到V个顶点全部属于VA，算法结束。显然出发点不同，最小生成树的形态就不同，但边权和的最小值是唯一的。
 eg:
 下面我们对下面这幅图求其最小生成树：
 
 假设我们从顶点v1开始，所以我们可以发现（v1,v3）边的权重最小，所以第一个输出的边就是：v1—v3=1:
 
 然后，我们要从v1和v3作为起点的边中寻找权重最小的边，首先了（v1,v3）已经访问过了，所以我们从其他边中寻找，发现(v3,v6)这条边最小，所以输出边就是：v3—-v6=4
 
 然后，我们要从v1、v3、v6这三个点相关联的边中寻找一条权重最小的边，我们可以发现边(v6,v4)权重最小，所以输出边就是：v6—-v4=2.
 
 然后，我们就从v1、v3、v6、v4这四个顶点相关联的边中寻找权重最小的边，发现边（v3，v2）的权重最小，所以输出边：v3—–v2=5
 
 然后，我们就从v1、v3、v6、v4，v2这2五个顶点相关联的边中寻找权重最小的边，发现边（v2，v5）的权重最小，所以输出边：v2—–v5=3
 
 最后，我们发现六个点都已经加入到集合U了，我们的最小生成树建立完成。
 【算法步骤】
 选定图中的任意一个顶点v0，从v0开始生成最小生成树。
 （1）初始化dist[v0]=0，其他点的距离值dist[i]=∞。其中dist[i]表示集合VB中的点到VA中的点的距离值。
 （2）经过N次如下步骤操作，最后得到一棵含N个顶点，N-1条边的最小生成树：
 ①选择一个未标记的点k，并且dist[k]的值是最小的
 ②标记点k进入集合VA
 ③以k为中间点，修改未标记点j，即VB中的点到VA的距离值
 （3）得到最小生成树T。
 
 
 克鲁斯卡算法—Kruskal算法：适合稀疏图
 【算法思想】：Kruskal算法也是一种贪心算法，它是将边按权值排序，每次从剩下的边集中选择权值最小且两个端点不在同一集合的边加入生成树中，反复操作，直到加入了n-1条边。
 【算法步骤】：
 （1）将G中的边按权值从小到大快排。
 （2）按照权值从小到大依次选边。若当前选取的边加入后使生成树T形成环，则舍弃当前边，否则标记当前边并计数。
 （3）重复（2）的操作，直到生成树T中包含n-1条边，否则当遍历完所有边后，选取不到n-1条边，表示最小生成树不存在。
 【算法实现】：Kruskal算法
 算法的关键在于如何判定新加入的边会不会使图G’产生环，在这里用并查集，如果新加入的边的两个端点在并查集的同一集合中，说明存在环，需要舍弃这条边，否则保留当前边，并合涉及的两个集合。
 
 
最短路径
 
 
 迪杰斯特拉算法(Dijkstra)：单源最短路径
 【算法思想】：首先将图中的顶点分成两组，第一组S中包括已经确定最短路径的顶点（初始情况包含源点）;第二组V-S中包括还未确定最短路径的顶点。然后按照路径长度递增的顺序计算源点到各顶点的最短路径，逐个将第二组中的数据加入到第一组中，直到S = V。
 
 【算法实现】：Dijkstra
 【动态演示】
 
 
 
 弗洛伊德算法(Floyd)：任意两个点对最短路径
 【算法思想】：用简单的语言来解释，就是对于点Vi到Vj的距离，如果存在点Vk，使得点Vi到点Vk的距离加上点Vj到点Vk的距离之和小于点Vi到Vj的距离，那么就用点Vi到点Vk的距离加上点Vj到点Vk的距离之和去替代点Vi到Vj的距离。
 【算法实现】：Floyd
 【结果展示】
 
 
 
8.查找和排序算法
 
 顺序查找
 二分查找(折半查找)
 Hash查找
 二叉排序树：左子树小于根节点，右子树大于根节点
 冒泡排序
 短冒泡排序
 选择排序
 插入排序
 希尔排序
 归并排序
 快速排序
 堆排序：大根堆(每个节点的值都大于其左右子节点的值)；小根堆(每个节点的值都小于其左右子节点的值)
 
 
参考链接：
 https://blog.csdn.net/Asher117/article/details/89306091
 https://blog.csdn.net/Asher117/article/details/89351068
 https://blog.csdn.net/Asher117/article/details/93647879
 https://mp.weixin.qq.com/s/GjqKMEwLHq16FaXdoHy8xA
 https://blog.csdn.net/jiaoyangwm/article/details/80808235
 https://blog.csdn.net/dengpei187/article/details/51899550
 https://mp.weixin.qq.com/s/Oyk7_vR3KtIBXf5AnhmWNQ
 https://blog.csdn.net/qq_39826163/article/details/81660819
 https://mp.weixin.qq.com/s/LCs2wmfCGw9oc3d1hkJn2w
 https://mp.weixin.qq.com/s/Iul7pHHiAsun80Dad9jqkw
 https://blog.csdn.net/qq_38499859/article/details/79122634
 https://blog.csdn.net/Asher117/article/details/89500637