# 数据结构

**Repository Path**: stardustr/datastruct

## Basic Information

- **Project Name**: 数据结构
- **Description**: 考研数据结构自整理（结合王道教材）
- **Primary Language**: C
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2022-09-16
- **Last Updated**: 2024-12-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

数据结构重点摘要

### 一、数据结构及相关基本概念



1. $\color{orange} {数据结构} $是指所有元素以及元素之间的关系，可以看作是相互之间存在着某种特定关系的数据元素的集合
2. $\color{orange} {数据元素} $是数据的基本单位
3. $\color{orange} {数据项} $是描述客观事物的数和字符的集合
4. $\color{orange} {数据对象} $是指性质相同的数据元素的集合，他是数据的一个子集
--- 
1. 数据的$\color{orange} {逻辑结构} $：由数据之间的逻辑关系构成
    - 1.集合  2.线性结构（一对一） 3.树形结构（一对多） 4. 图形结构（多对多）    
2. 数据的$\color{orange} {存储结构} $： 数据元素及其关系在计算机存储器中的存储表示
    - 1.顺序存储 2.链式存储 3.索引存储（查找效率高，缺点是需要建立索引表，增加了空间开销） 4.哈希（散列）存储
3. 数据的$\color{orange} {运算} $：施加在该数据上的操作
---
1. 数据的$\color{orange} {抽象数据类型} $：指的是用户进行软件系统设计时问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构的运算，
                                        而不考虑计算机的具体存储结构和运算的具体实现算法
2. 一个抽象数据类型可用（D,S,P)三元组表示，D是数据对象，S是D上的关系集，P是D中的数据运算的基本运算集
3. 特点：数据抽象和数据封装
---
1. 数据的$\color{orange} {算法} $是对特定问题求解步骤的一种描述，他是指令的有限序列
2. 特点
    - 1.有穷性 2.确定性 3.可行性 4.有输入（0或n) 5.有输出（1或n）
3. 要求 
    - 1.正确性 2.健壮性 3.可读性 4.可使用性 5.高效率与低存储量的要求
---
1. 时间复杂度
    - O(1)＜O(log n)＜O(n)＜O(nlog n)＜O(n^2)＜O(n^3)＜O（2^n）＜O(n!)
    - 线性时间复杂度指的是原操作执行次数与问题规模n的增长呈线性增大关系
2. 空间复杂度
    - O（1）原地工作
### 二、线性表
1.  $\color{orange} {线性表} $是具有相同特性的数据元素的一个有限序列
####顺序存储和链式存储结构体
```sh
顺序存储
#define MaxSize 10 //定义最大长度
typedef struct{
ElemType data[MaxSize]; //用静态的“数组”存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义（静态分配方式）
```
```sh
链式存储
typedef struct LNode{ 
    ElemType data;          
  struct LNode *next;
}LNode,*LinkList;
```
#### 顺序表和链式表的比较
```sh
    逻辑结构都属于线性表都是线性结构
    存储结构
        1.顺序表    优点：支持随机存取，存储密度高    缺点：大片连续空间分配不方便，改变容量不方便
        2.链表      优点：离散的小空间分配方便，改变容量方便     缺点：不可随机存取，存储密度低
    一、基于空间的比较
        1.存储分配的方式:顺序表的存储空间是静态分配的，链表的存储空间是动态分配
        2.存储密度顺序表=1，链表<1（有指针域）
    二、 基于时间的比较
        1.存取方式：顺序表可随机存取，而链表仅能顺序存储
        2.插入/删除元素时移动元素个数·
        顺序表平均要移动近一半元素，链表无需移动元素，仅改变指针
    三、基于场合
        1.顺序表：信息少表长已知.较少需要插入和删除操作但经表中位置去访问元素.
        2.链表信息量大，表长未知，插入删除操作频繁的情况
        顺序存储可用于线性结构，图，树
    四、插入删除操作
        1.线性表操作删除第一个元素（指到头指针）
        2.删除最后一个指针（倒数第二个指针）
        3.在第一个元素之前插入新元素（头指针）
        4.在最后一个元素之后插入新元素（尾指针）
    五、头插法和尾插法
        1.头插法 s->next = L->next;L->next=s
        2.尾插法 r->next = s;r=s
```
### 三、栈和队列
#### 栈
- 栈是一种只能在一端进行插入或删除操作的线性表（后进先出） 
- n个不同元素进栈，出栈元素不同排列个数为（1/（n+1））Cn^2n
```c
#define MaxSize 100 //定义栈中元素的最大个数
typedef struct SqStack{
    int data[MaxSize]; //存放栈中的元素
    int top; //栈顶指针
}SqStack;
```
```c
typedef struct LinkNode{
    int data; //数据域
    struct LinkNode *next; //指针域
}*LiStack; //栈类型定义(不带头节点最方便)
```
#### 队列
1. 队列是只允许在一端进行插入，在另一端删除的线性表(先进先出)
2. 循环队列
```sh
        1.初始时 Q.front=Q.rear=0
        2.队首拨针进1:Q.front=(Q.front+1)%Maxsize
        3.队尾指针进1:Q.rear=(Q.rear+1)%Maxsize
        4.队列长度(Q.reart+Maxsize-Q.front)%Maxsize
        5.队满条件(Q.rear+1%Maxsize=Q.front(牺牲一个存储空间)
        6.队空条件仍为Q.front=Q.rear
        7.注意front，rear指向的位置.
```
```c
using namespace std;
#define MaxSize 10
typedef struct{
  ElemType data[MaxSize];
  int front rear;
}SqQueue;
void testQueue(){
    SqQueue Q;
}
```
#### 栈和队列的应用
1. 栈的应用
    1.递归（效率不高但精简）
    2.进制转换
    3.迷宫求解
    4.括号匹配
    5.处理函数过程调用
2. 队列的应用
    1.页面替换算法
    2.缓冲（打印机）
3.  中后缀表达式
    1.用栈实现中缀表达式转后缀：初始化一个栈用于保存暂时不能确定的运算顺序的运算符
    2.用栈实现后缀表达式的计算：栈用于存放操作数
    3.用栈实现中缀表达式计算：两个栈 一个操作数一个运算符
### 四、串
1. 串是由零个或多个字符组成的有限序列
2. 串中任意多个连续的字符组成的子序列称为该串的子串，包括子串的串称为主串
3. 基本操作
```sh
    1.StrAssign(&T, chars): 赋值操作，把串T赋值为chars；
    2.StrCopy(&T, S): 复制操作，把串S复制得到串T
    3.StrEmpty(S): 判空操作，若S为空串，则返回TRUE，否则返回False；
    4.StrLength(S): 求串长，返回串S的元素个数；
    5.ClearString(&S): 清空操作，将S清为空串；
    6.DestroyString(&S): 销毁串，将串S销毁——回收存储空间；
    7.Concat(&T, S1, S2): 串联联接，用T返回由S1和S2联接而成的新串———可能会导致存储空间的扩展；
    8.SubString(&Sub, S, pos, len): 求子串，用Sub返回串S的第pos个字符起长度为len的子串；
    9.Index(S, T): 定位操作，若主串S中存在与串T值相同的子串，则返回它再主串S中第一次出现的位置，否则函数值为0；
    10.StrCompare(S, T): 串的比较操作，参照英文词典排序方式；若S > T,返回值>0; S = T,返回值=0 (需要两个串完全相同) ; S < T,返回值<0;
```
4.结构体定义
```c
#define MAXLEN 255   //预定义最大串长为255
typedef struct{
    char ch[MAXLEN];   //静态数组实现（定长顺序存储）
                       //每个分量存储一个字符
                       //每个char字符占1B
    int length;        //串的实际长度
}SString;
typedef struct StringNode{
    char ch;           //每个结点存1个字符
    struct StringNode *next;
}StringNode, * String;
``` 
5.模式匹配
- 最坏时间复杂度为O(mn)
- O((n-m+1)m)
```c
int Index(SString S, SString T){
    int i=1;                //扫描主串S
    int j=1;                //扫描模式串T
    while(i<=S.length && j<=T.length){
        if(S.ch[i] == T.ch[j]){ //如果当前相同，则指示都后移
            ++i;
            ++j;             //继续比较后继字符
        }
        else{       
            i = i-j+2;   //i-j表示指向了当前匹配串的起始位置的前一个，+2表示下一个串的起始位置（+1是当前被匹配串的起始位置）
            j=1;             //指针后退重新开始匹配
        }
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0;
}
```
### 五、数组
1. 数组是由n个相同类型的数据元素构成的有限序列。
2. 数组一旦被定义，其维数和维界就不会再改变。
3. 数组只会有存取元素和修改元素的操作
####特殊矩阵的存储
1. 对称矩阵三角矩阵三对角矩阵(计算时要注意一维数组和二维数组的下标从0还是从1开始，对称矩阵注意ij的大小注意换算)
- 例如
![avatar](图片/数组k计算.png)
2. 稀疏矩阵
    - 顺序存储---三元组<行，列，值>
    - 链式存储---十字链表法
### 六、树和二叉树
#### 树的性质
```sh
1.树的结点数等于所有结点的度数之和加1
2.区分度为m的树，m叉树
度为m的树：各结点的度最大值为m，但是其他结点的度不一定是m
m叉树：每个结点最多只能有m个孩子的树
3. 度为m的树第i层至多有mi-1 个结点（i≥1）
4. m叉树第i层至多有mi-1个结点（i≥1）
4. 高度为h的m叉树至多有 (mh-1) /(m-1)个结点:m0+m1…+mn
5. 高度为h的m叉树至少有h个结点
6. 高度为h，度为m的树至少有h+m-1个结点
7. 具有h个结点的m叉树的最小高度为[logm(n(m-1)+1)]
```
![2](图片/m叉树.png)
#### 二叉树的性质
1. n0=n2+1
2. 非空二叉树上第k层最多有2^(k-1)个结点
3. 高度为h的二叉树至多有2^h-1个结点
4. 具有n个结点的完全二叉树的高度为[log~2~（n+1）]（向上取整）或[log~2~n]+1（向下取整）
#### 满m叉树的性质
1. 结点i的第一个子女ì=(ì-1)×m+1+1
2. 结点i的双亲(i-2)/m+1
3. 结点i的第k个子女(i-1)m+k+1
4. 结点i有兄弟的条件i<=[(i+m-2)/m]*m
- 顺序存储
```c
#define MaxSize 100
struct TreNode{
   ElemType value; //结点中的数据元素
   bool isEmpty;//结点是否为空
};
TreeNode t[MaxSize];
```
- 链式存储
```c
typedef struct BiTNood{
   ElemType value; //结点中的数据元素
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
```
5. 含有n个结点的二叉链表中，含有n+个空链域
#### 二叉树的遍历
- 先序遍历
```c
typedef struct BiTNood{
   ElemType value; //结点中的数据元素
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void InOrder(BiTree T){
  if(T!=NULL){
   visit(T);
    InOrder(T->lchild);
    InOrder(T->rchild);
  }
}
```
- 中序遍历
```c
  if(T!=NULL){
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
  }
```
- 后序遍历
```c
  if(T!=NULL){
    InOrder(T->lchild);
    InOrder(T->rchild);
    visit(T);
  }
```
- 层次遍历
```c
void levelorder(BiTree T){
    initquete(Q);
    BiTree p;
    enqueue(Q,T);
    while(!isEmpty(Q)){
        dequeue(Q,p);
        visit(p);
        if(p->lchild!=NULL)
        enqueue(Q,p->lchild);
        if(p->rchild!=NULL)
        enqueue(Q,p_<rchild);
    }
}
```
#### 线索二叉树
1. 先序线索化容易爱的魔力转圈圈
2. 后续线索化需要栈的支持可以找到祖先但不能有效的找到后续后继
#### 树
1. 双亲表示法，孩子表示法，孩子兄弟表示法（常用）
![1](图片/遍历树.png)
#### 哈夫曼树
1. 哈夫曼树不唯一，因此哈夫曼编码不唯一。
2. 哈夫曼编码可用于数据压缩。
```sh
（1）结点的权：有某种现实含有的数值（如：表示结点的重要性等）
（2）结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积。
（3）树的带权路径长度：树中所有叶结点的带权路径长度之和wpl
（4）在含有n个带权也结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也称最优二叉树。
```
### 七、图
####邻接表存储结构
```sh
typedef struct ANode
{     int adjvex;			//该边的终点编号
      struct ANode *nextarc;	//指向下一条边的指针
      InfoType info;		//该边的权值等信息
}  ArcNode;

typedef struct Vnode
{    Vertex data;			//顶点信息
     ArcNode *firstarc;		//指向第一条边
}  VNode;

typedef struct 
{     VNode adjlist[MAXV] ;	//邻接表
       int n，e;			//图中顶点数n和边数e
} AdjGraph;
```
#### DFS
```sh
void  DFS1(AdjGraph *G)
{　int i;
     for (i=0;i<G->n;i++)     //遍历所有未访问过的顶点
          if (visited[i]==0) 
               DFS(G，i);
}
void DFS(AdjGraph *G，int v)  
{      ArcNode *p; int w;
       visited[v]=1; 		//置已访问标记
       printf("%d  "，v); 		//输出被访问顶点的编号
       p=G->adjlist[v].firstarc;     	//p指向顶点v的第一条边的边头结点
       while (p!=NULL) 
       {      w=p->adjvex;
	if (visited[w]==0) 
	       DFS(G，w);   	//若w顶点未访问，递归访问它
	p=p->nextarc; 　	//p指向顶点v的下一条边的边头结点
      }
}
```
#### BFS
```sh
void  BFS1(AdjGraph *G)
{      int i;
        for (i=0;i<G->n;i++)     //遍历所有未访问过的顶点
             if (visited[i]==0) 
                  BFS(G，i);
}
void BFS(AdjGraph *G，int v)
{        int w， i;
         ArcNode *p;
         SqQueue *qu;		//定义环形队列指针
         InitQueue(qu);		//初始化队列
         int visited[MAXV];            	//定义顶点访问标记数组
         for (i=0;i<G->n;i++) 
	  visited[i]=0;	  	//访问标记数组初始化
         printf("%2d"，v); 		//输出被访问顶点的编号
         visited[v]=1;              	//置已访问标记
         enQueue(qu，v);
    while (!QueueEmpty(qu))       	//队不空循环
       {	deQueue(qu，w);			//出队一个顶点w
	p=G->adjlist[w].firstarc; 	//指向w的第一个邻接点
	while (p!=NULL)		//查找w的所有邻接点
	{     if (visited[p->adjvex]==0) 	//若当前邻接点未被访问
	       {	printf("%2d"，p->adjvex);  //访问该邻接点
		visited[p->adjvex]=1;	//置已访问标记
		enQueue(qu，p->adjvex);	//该顶点进队
           	       }
           	       p=p->nextarc;              	//找下一个邻接点
	}
       }
       printf("\n");
}

```
#### 最短路径
```sh
//不带权无向连通图G中距离顶点v最远的一个顶点
int Maxdist(ALGraph *G，int v)
{      ArcNode *p;
        int Qu[MAXV]，front=0，rear=0;	//队列及队头、尾指针
        int visited[MAXV]，i，j，k;
        for (i=0;i<G->n;i++)			//初始化访问标志数组
	visited[i]=0;
        rear++;Qu[rear]=v;			//顶点v进队
        visited[v]=1;			//标记v已访问
      while (rear!=front)
      {	front=(front+1)%MAXV;
	k=Qu[front];			//顶点出队
	p=G->adjlist[k].firstarc;		//找第一个邻接点
	while (p!=NULL)		//所有未访问过的邻接点进队
	{      j=p->adjvex;
	       if (visited[j]==0)		//若j未访问过
	       {	visited[j]=1;		//将顶点j进队
		rear=(rear+1)%MAXV;Qu[rear]=j; 
	       }
	       p=p->nextarc;		//找下一个邻接点
	}
        }
        return k;
}、
```
#### 图的应用
1. 最小生成树
    1. prim算法（以点为基础，时间复杂度O（|V^2|）,适用于求边稠密的图）
    2. kruskal算法（以边为基础选取边权值最小，时间复杂度O（Elog2e），适用于边稀疏点较多的图） 
2. 最短路径
    1. dijkstra算法求单源最短路径问题（带权图，无权图）
        1. 时间复杂度O（|V^2|）
        2. 不适合带负权值的
        3. 也可以用于求各顶点最短路径之间的问题O(|V^3|)
    2. flody算法求个顶点之间最短路径之间的问题
        1. 时间复杂度O(|V^3|)---空间复杂度O(|V^2|)
        2. 可以用于解决带负权值的但不能解决带负权回路的
3. 有向无环图(DAG图)
    1. 把各个操作数不重复的排成一排
    2. 标出各个运算符的生效顺序（有点出入无所谓）
    3. 按顺序加入运算符注意分层
    4. 从底向上逐层检查同层的运算是否可以合体
4. 拓扑排序
5. 逆拓扑排序（在顶点退栈前输出）
6. 关键路径
#### 知识点汇总
1. floyd算法求两个顶点的最短路径时path（k-1）一定是path的子集（F）
2. 一个有向图的顶点不能排在一个拓扑序列中--->有环图--->含有顶点数大于1的强连通分量（T）
3. 有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1（F）
4. 若有向图具有有序的拓扑排序序列则他的邻接矩阵必为三角（T）
5. 一个连通分量可以是自己本身（单一个顶点）
### 八、查找
#### 顺序查找（顺序存储链式存储）
##### 基础表
1. 查找成功长度（n+1）/2；失败n+1
2. 时间复杂度O（n）
```c
//结构体
typedef struct 
{       ElemType *elem; 	  	//KeyType为关键字的数据类型
        int tablelen;  		//其他数据项
}SStable;			//查找顺序表元素类型
```
```c
int search_seq(SStable ST,ElemType key){
    int i;
    for(i=0;i<ST.tablelen&&ST.elem[i]!=key;i++);
        return i==St.tablelen ? -1:i;
}
```
##### 有序表
1. 若当前关键字大于（小于）目标关键字时，可以提前判断查找失败
2. 优点：查找失败时ASL更少
3. 查找失败情况有n+1种情况，
![](图片/sequence.png)
#### 折半查找
1. 树高（不包含失败结点）h = ⌈log2(n + 1)⌉向上取整，查找成功和查找失败的ASL ≤ h 
2. 故折半查找的时间复杂度 = O(log2n)
```c
//查找表的数据结构——顺序表
typedef struct{
	ElemType *elem;		//动态数组的基址
	int TableLen;		//表的长度	
}SSTable;
//折半查找——增序序列（成功返回数组下标，失败返回-1）
int Binary_Search(SSTable L, ElemType key)
{	//准备指针（下标）
	int low = 0;
	int high = L.TableLen - 1;
	int mid;
	while(low<=high)
	{mid = (low + high)/2;
		if(key == L.elem[mid])
		{return mid;}
		else if(key < L.elem[mid])
		{high = mid - 1;}
		else		
		{low = mid + 1;}
		return -1;
	}
}
```
#### 分块查找（索引顺序查找）
1. 块内无序，块间有序
![](图片/分块查找.png)
#### 二叉排序树
1. 非空二叉排序树
    1. 删叶结点再加入与原来相同
    2. 删非叶结点再加入与原来不同
2. 非空平衡二叉树
    1. 删叶节点再加入与原来可能不同
    2. 删非叶节点再加入与原来可能相同
    3. LL平衡旋转，LR平衡旋转，RR平衡旋转，RL平衡旋转
#### B树
#### 散列表
1. 散列表（Hash Table），又称为哈希表，是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关。
2. 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr(这里的地址可以是数组下标、索引或内存地址等)。
3. 散列函数可能会把两个或两个以上的不同关键字映射到同一地址上，这种情况就称为哈希冲突。这些发生碰撞的不同关键字称为同义词。
4. 装填因子（0.6-0.9）
    1. 装填因子：表中记录数/散列表的长度
    2. 装填因子越小，说明空缺越大，会影响效率。
5. 构造散列函数方法
    1. 直接定址法
        - H(key)=key 或H(key)=a*key+b
        - 适用于：数据分布均匀的情况
    2. 除留余数法
        - 假设散列表长为m，取一个不大于m但最接近或等于m的质数p，利用公式：H(key)=key%p；选择地址p，可以让数据分布均匀，尽量没有空位置，则实现减少冲突。
    3. 数字分析法
        - 选择数码分布较为均匀的若干位，作为散列地址。
    4. 平均取中法
        - 去关键字的平方值的中间几位作为散列地址。这种方法得到的散列地址与关键字的每位都有关系，因此散列地址分布比较均匀。
6. 处理冲突方法
    1. 拉链法
        1. 查找失败不包括空指针判定（根据考纲参考目录要求）
    2. 开放定址法
        1. 线性探测法
            - 线性探测法很容易造成同义词、⾮同义词的“聚集（堆积）”现象，严重影响查找效率，产⽣原因——冲突后再探测⼀定是放在某个连续的位置
        2. 平方探测法
        3. 伪随机序列法
        4. 再散列法
        5. 查找失败包括数组中第一个空的比较
#### 查找知识点汇总
1. 散列函数k取不大于表长的最大素数优点
    1. 简单，计算速度快
    2. 分布均匀
    3. 散列表填充因子（装填密度） x<=n/m
    4. 浪费空间少，空间效率高
### 九、内部排序
#### 插入排序
##### 直接插入排序
```c
typedef struct
{  int key;
   float info;
}JD;
void straisort(JD r[],int n)
{  int i,j;
   for(i=2;i<=n;i++)
   {  r[0]=r[i];
      j=i-1;
      while(r[0].key<r[j].key)
      {  r[j+1]=r[j];
         j--;    }
      r[j+1]=r[0];
   }    } 
```
##### 折半插入排序
```c
void binsort(JD r[],int n)
{  int i,j,x,s,m,k;
   for(i=2;i<=n;i++)
   {  r[0]=r[i];
      x=r[i].key;
      s=1; j=i-1;
      while(s<=j)
      {  m=(s+j)/2;
      if(x<r[m].key)  j=m-1;
         else s=m+1;
      }
      for(k=i-1;k>=s;k--)
         r[k+1]=r[k];
      r[s]=r[0];
   }
}
```
##### 希尔排序(缩小增量法)
```c
void shellsort(JD r[],int n,int d[T])
{  int i,j,k;
   JD x;
   k=0;
   while(k<T)
   {  for(i=d[k]+1;i<=n;i++)
      {  x=r[i];
         j=i-d[k];       
         while((j>0)&&(x.key<r[j].key))
         {  r[j+d[k]]=r[j];
            j=j-d[k];
         }
         r[j+d[k]]=x;
       }
       k++;
    }
}
  
```
#### 交换排序
##### 冒泡排序
```c
void BubbleSort(ElemType A[],int n ){
    for(i=0;i<n-1;i++){
        flag=flase;
        for(j=n-1;j>i;j--){
            if(A[j-1]>A[j]);
            flag=true;
        }
    }
    if(flag==flase)
        return;
}
```
##### 快速排序
1. 一次划分可以确定一个元素的最终位置，而一趟排序也许可以确定多个元素的最终位置
2. 快速排序算法的性能关键在于划分操作的好坏
3. 判断是否是快速排序第n躺的结果，可以排除原序列看几个元素在其最终位置
```c
void QucikSort(ElemType A[],int low,int high){
    if(low<high){
        int pivotpos = Partition(A,low,high);
        QucikSort(A,low,pivotpos-1);
        QucikSort(A,pivotpos+1,high);
    }
}
int Partition(ElemType A[],int low,int high){
    ElemType pivot = A[low];
    while(low<high){
        while(low<high && A[high]=pivot)
            --high;
            A[low]=A[high];
        while(low<high && A[low]=pivot)
            ++low;
        }
        A[low]=pivot;
        return low;
    }
}
```
#### 选择排序
##### 简单选择排序
1. 移动次数不会超过3（n-1）最少O（n）
```c
void smp_selesort(JD r[],int n)
{  int i,j,k;
   JD x;
   for(i=1;i<n;i++)
   {  k=i;
      for(j=i+1;j<=n;j++)
         if(r[j].key<r[k].key)  k=j;
      if(i!=k)
      {  x=r[i];
         r[i]=r[k];
         r[k]=x;     }   }
}
```
##### 堆排序
1. 建立堆时间复杂度O（n），调整堆时间复杂度O（log2n）或者说移动和比较次数的数量基
2. 每一趟将对顶元素加入有序子序列，与待排序序列中最后一个元素进行交换
3. 
    - 基于大根堆的堆排序是递增序列
    - 基于小根堆的堆排序是递减序列
4. 被删除元素用堆底元素替代，然后让元素不断下坠，直至无法下坠
5. 关键字对比
    - 下方有两个孩子 则下坠一层对比2次
    - 一个孩子，对比一次
```c
//建立大根堆
void BuildMaxHeap(ElemType A[],int len){
    for(int i= len/2;i>0;i*=2){
        HeadAdjust(A,i,len);
    }
}
void HeadAdjust(ElemType A[],int k,int len){
    A[0]=A[k];
    if(i<len&&A[i]<i[i+1])
        i++;
    if(A[0]>=A[i])
        break;
    else{
        A[k]=A[i];
        k=i;
    }
    A[k]=A[0];
}
void heapsort(ElemType A[],int len){
    BuildMaxHeap(A,len);
    for(i=len;i>1;i--){
        swap(A[i],A[1]);
        HeadAdjust(A,1,i-1);
    }
}
```
#### 归并排序
1. 归并数量基O（log2n）
2. 每趟移动比较次数O（n）
```sh
void merge(int arr[], int start, int mid, int end) {
	int result[ArrLen];
	int k = 0;
	int i = start;
	int j = mid + 1;
	while (i <= mid && j <= end) {
		if (arr[i] < arr[j]){
			result[k++] = arr[i++];
        }
		else{
			result[k++] = arr[j++];
        }
	}
	if (i == mid + 1) {
		while(j <= end)
			result[k++] = arr[j++];
	}
	if (j == end + 1) {
		while (i <= mid)
			result[k++] = arr[i++];
	}
	for (j = 0, i = start ; j < k; i++, j++) {
		arr[i] = result[j];
	}
}
 
void mergeSort(int arr[], int start, int end) {
	if (start >= end)
		return;
	int mid = ( start + end ) / 2;
	mergeSort(arr, start, mid);
	mergeSort(arr, mid + 1, end);
	merge(arr, start, mid, end);
```
#### 基数排序
1. 不是基于比较的算法
![](图片/排序比较.png)
#### 排序总结
1. 直接选择排序与关键字比较的次数和记录初始排序顺序无关
### 代码
#### 线性表 
##### 数组A[m+n] mn元素互换
```c
void reverse(int A[],int left,int right,int arraysize){
    if(left>=right||right>=arraysize)
        return;
    int mid=(left+right)/2;
    for(int i=0;i<=mid-left;i++){
        int temp = A[left+i];
        A[left+i]=A[right-i];
        A[right-i]=temp;
    }
}
void exchange(int A[],int m,int n,int arraysize){
    reverse(A,0,m+n-1,arraysize);
    reverse(A,0,n-1,arraysize);
    reverse(A,n,m+n-1,arraysize);
}
```
#### 树
##### 求树的深度
```c
int deeptree(BiTree *t)
{    int l,r;
    if(t==NULL) return 0;
    else 
    {
        l=deeptree(t->lchhild);
        r=deeptree(t->rchild);
        if(l<r)  
            return r+1;
        else 
            return l+1;
    }
}
```
##### 求叶子节点个数

```c
int addTnode(Bitree *t)
{
    if(t=NULL) return 0;
    else 
        if(t->rchild==NULL&&t->lchild==NULL)
          n++;
    addTnode(t->rchild);
    addTnode(t->lchild);
    return n;
} 
```
##### 统计二叉树度为1，2，0的个数（不定义全局变量）
```c
//度为2
int double(Bitree T){
    if(T==NULL)
    return 0;
    else if(T->lchild!=NULL&&T->rchild!=NULL)
        return double(T->lchild)+double(T->rchild)+1;
    else
         return double(T->lchild)+double(T->rchild);
}
//度为1
    else if(T->lchild!=NULL||T->rchild!=NULL)
//度为0
    else if(T->lchild==NULL&&T->rchild==NULL)
```
##### 复制二叉树
```c
void copytree(BiTree t1,BiTree t2)
{    if(t1==NULL)
       t2=NULL;
     else {
       t2=new BiTNode;
       t2->data=t1->data;
       t2->lchild=NULL;
       t2->rchild=NULL;
       copytree(t1->rchild,t2->rchild);
       copytree(t1->lchild,t2->lchild);
     }
    
}
```
##### 非递归后续遍历
```c
void preorder(Bitree T){
    initstack(S);
    p=T;
    r=NULL;
    while(p||isEmpty(S)){
        if(p){
            push(S,p);
            p=p->lchild;
        }
        else{
            gettop(s,p);
            if(p->rchild&&p->rchild!=t)
                p=p->rchild;
            else
            pop(S,p);
            visit(p);
            r=p;
            p=NULL;
        }
    }
}
```
##### 非递归先序遍历
```c
void preorder(Bitree T){
    initstack(S);
    p=T;
    r=NULL;
    while(p||isEmpty(S)){
        if(p){
            visit(p);
            push(S,p);
            p=p->lchild;
        }
        else{
            pop(S,p);
            p=p->rchild;
        }
    }
}
```
##### 非递归中序遍历
```c
void preorder(Bitree T){
    initstack(S);
    p=T;
    r=NULL;
    while(p||isEmpty(S)){
        if(p){
            push(S,p);
            p=p->lchild;
        }
        else{
            pop(S,p);
            visit(p);
            p=p->rchild;
        }
    }
}
```
#### 图
##### 零阶矩阵的深度优先遍历
```sh
int visited[MAXV];	  //全局变量，所有元素置初值0
void MDFS(MGraph g，int v)
{      int w;
        printf("%d  "，v);	  //访问顶点v
        visited[v]=1;		  //置访问标记
        for (w=0;w<g.n;w++)	  //找顶点v的所有相邻点
	if (g.edges[v][w]!=0 && g.edges[v][w]!=INF && visited[w]==0)
	        MDFS(g，w);  //找顶点v的未访问过的相邻点w
}
```
##### 判断图是否为一棵树
```sh
int visited[MaxSize];
void DFS2(ALGraph *G，int v，int &vn，int &en)
{      ArcNode *p;
       visited[v]=1;   vn++;		//遍历过的顶点数增1
       p=G->adjlist[v].firstarc;
       while (p!=NULL) 
       {      en++;			//试探过的边数增1
	if (visited[p->adjvex]==0)
	      DFS2(G，p->adjvex，vn，en);
	p=p->nextarc;
       }
}
bool GIsTree(ALGraph *G)      //判断无向图G是否是一棵树
{      int vn=0，en=0，i;
       for (i=0; i<MaxSize; i++)
	visited[i]=0;
       DFS2(G，0，vn，en);
       if (en==2*(vn-1))
	return true;  
       else
	return false;
}
```
##### 判断其中是否存在回路
```sh
void Cycle(ALGraph *G，int v，bool  &has)
{      //调用时has置初值false
        ArcNode *p;	int w;
        visited[v]=1;			//置已访问标记
        p=G->adjlist[v].firstarc;	//p指向顶点v的第一个邻接点
        while (p!=NULL)
        {	w=p->adjvex;
	if (visited[w]==0)		//若顶点w未访问，递归访问它
	        Cycle(G，w，has);
	else			//又找到了已访问过的顶点说明有回路
	        has=true;
	p=p->nextarc;		//找下一个邻接点
       }
}
bool HasCycle(ALGraph *G)       //判断有向图G中是否有回路
{ 
        bool has=false;
        for (int i=0;i<G->n;i++)
        {
                Cycle(G，i，has);
	if (has) return true;
        }
        return false;
}
```
### 知识点总结
1. DFS与拓排序都可以判图是否有环
2. 折半插入和直接插入的不同之处只有无素间的比较级
3. 有序表逻辑结构线性表，队列，栈都是逻辑结构
4. 链式存储中多不同结点的存储空间可以不断续但结点内的存储单元地址必须连续
5. 算法是指问题求解步骤的描述
6. 算法原地工作是指所需的辅助空间为常量.同一算法，实现语言级别越高，执行效率越低
7. 可以准确计算总运行时间
8. 数据结构的抽象操作的定义与具体实现无关
9. 在顺序存储结构中，不可以存储数据结构中元素间的关系
10. 散列表可以较快的插入删除但不能反映数据间的逻辑关系.
11. 二叉树线索化后，不能有效解决后续后继问题（后序线索二叉树）
12. B树不支持顺序查找
13. 头指针头结点和表头结点的区别
    在链表中，头指针是管理链表的基础，它指向链表的第一个结点链表中的第一个元素结点称为关结头。
    表头结点是头结点之前添加的一个结点.其数据.成一般无意义，也可以存放便于算法实现的辅助数据采用带表头结点的链表可使得头指针永不为空指针，
    这就可将在头结头之前插入新结点以及删除头结点的操作，与其它位置的插入和删除元素的操作的代码统一起来
14. 冒泡排序从前向后与从后向前排序趟数不一定同
15. AOV网中的领先关系是一种拟序关系它具有传递性和反自反性.
16. 希尔排序增量最后一个值一定是1增量序列中的值无除1之外公因子.
17. 对二叉树前序中序后序遍历其叶结点的相对次序不会改变.
18. 度为m的哈夫曼树中叶结点个数为n则非叶结点个数为「m=1]
19. 一个递归算法必须包含终止条件和递归部分
20. 队列链式最好的设计只设表尾指针无头结点的单循环链表.
21. 按广度优先遍历的次产生的最短路径是迪斯特拉算法基求思想
22. 普通稀疏矩阵压缩存储后,将失去随机存取功能
23. 树形结构常用递归方式定义因此被称为递归数据结构
24. 一棵左右子树均不空的二叉树在先序线索化后，其空指针是1个
25. 优先权队列的创建即一个一个插入调整
26. 伪随机法与二次探查法都可可以消除基本聚集
27. 数组一旦定义维数与维界不可再次修改
28. 极小连通子图是指添加一边就会有环，极大连通子图是不能再纳入顶点的图
29. 某二叉树的的前序序列和后序序列正好相反，则该二叉树一定是高度等子其结点数的二叉树或（只有一个叶结点）
30. 采用邻接存储的图按浑度优先搜索方法进行遍历的算法类似于二买树的先序遍历
31. 设F是个森林,B是由变换得到的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有n+l
32. 将森林F转换为对应的二叉树T,F中叶结点的个数等于T中左孩子指针为空的结点个数
33. 若一个具有N个结点,K条边的无向图是一个森林,则森林中必有N-K棵树解抑P59,2
34. 考度为m的哈夫曼树中其叶结点个数为n则非叶结点的个数为(n-1)/(m—1)
35. 给N个不同树值的关键建字,则其构造生成的哈夫曼树共有结点数为2N-1个
36. DAG图比有向图更一般,因为有向树不允许出现入度大于1的结点而在DAG图中则可以，另外DAG图不允许出现坏或回路,因此又是一种特殊的图
    - 有向树：一个顶点的入度为0,其余顶点的入度均为1的有向图
37. 如果有个顶点的图是一个环则它有n个生成树
38. 找出个数字的中位数至需要O(n)的时间(利用快排的过程而不是程,快排)
39. 在一个带权图G中权值最小的也一定包含在的某棵最小成树中（不是必在一颗树中）
40. 求关键路径是以拓扑排为基础的
41. 按广度优先遍历的次产生的最短路径是迪斯特拉算法基求思想
42. 分块查找（较快的查找，动态适应变化要求）；链式存储方式（较快地插入和删除，反映数据元素之间的逻辑关系）；顺序有序表（查找存取速度快，插入和删除速度慢）
43. 对于n个互不相月的串则其子串（不包括本身但含空串）的个数是n（n+1）/2；注意单字符重复例'database
43. 排序总结
    1. 按排序过程中依据不同原则读内部排序方法进行分类则可分为插入排序，交换排存，选择排序，归并排序，基数排序
    2. 如果按内排序过程中所需要工作量分则分为3类简单的排序方法0(n^2)先进的排疗方法o(nlog2n)基数排序方法度O(d*n)
    3. 记录数量多，可能出现正序逆序情况，并且要求排序方法稳定的时候选择归并排序
    4. 若只想得到序列的前k小元素的顺序排序最适合
        - 冒泡排序
        - 堆排序
        - 简单选择排序
    5. 堆用来排序在查找是无序，一般用于求第n大元素，相较于其他数据结构，堆的查找效率低
    6. 待排序列有序情况下，直按插入排序效率最高
    7. 以比较为基础的排序算法，在最坏情况下计算时间复杂度下届为O(nlog2n)
    8. 交换效率
        - 插入排序（O（n^2））
        - 快速排序（O（n^2））
        - 希尔排序（O（n^2））
        - 堆排序O(nlog2n)
44. 
    - 时间复杂度O（1）含义是执行时间与问题规模无关
    - （O（n^2））代表执行时间与n^2成正比；问题规模单指n
45. 树的结点数比边数多1，森林有15条边25个结点则有10棵树
46. 在树转换为对应的二叉树后，书中每一个非叶节点的所有子节点中的最右子节点在对应的二叉树中无右孩子，根节点也无右孩子
    - 对应的二叉树无右孩子的节点个数=树中非叶节点个数+1
47. 顺序存储结构可以是动态也可以是静态，链式存储结构属于动态结构