有些解释内容为搬运，如有侵权，联系删除！！！

数据结构

线性表

顺序存储

优点：无须为表中元素之间的逻辑关系而增加额外的存储空间；可以快速的存取表中任一位置的元素。

缺点：插入和删除操作需要移动大量元素；当线性表长度较大时，难以确定存储空间的容量；造成存储空间的“碎片”。

#include <iostream>
#define MAXSIZE 20
using namespace std;
typedef int ElementType;//顺序表结构体
typedef struct {ElementType Data[MAXSIZE];int last;
}LNode , *List;//顺序表的初始化
List MakeEmpty() {List Ptrl;Ptrl = (List)malloc(sizeof( LNode));//开辟空间Ptrl->last = -1;//0代表有一个元素，-1代表表里没元素return Ptrl;
}//顺序表的查找
int Find(ElementType x, List Ptrl) {int i = 0;while (i <= Ptrl->last && Ptrl->Data[i] != x)//判断{i++;if (i > Ptrl->last) {//如果超过数组范围return -1;}else return i;//如果找到了返回储存位置}
}//顺序表的插入
void Insert(ElementType x, int i, List Ptrl) {int j;//判断表空间是否已满if (Ptrl->last = MAXSIZE - 1) {cout << "The Form is full"; << endl;return;}//检查插入位置的合法性if (i < 1 || Ptrl->last + 1) {cout << "The address is illegal" << endl;}//插入x元素for (j = Ptrl->last; j >= i - 1; j--) {Ptrl->Data[j + 1] = Ptrl->Data[j];Ptrl->Data[i - 1] = x;Ptrl->last++;//last仍然指向最后一个元素return;}
}//顺序表的删除
void Delete(int i, List Ptrl) {int j; //创建一个计时器if (i < 1 || Ptrl->last + 1) {cout << "The ElemType is not found!" << endl;return;}for (j = i; j <= Ptrl->last; j++) {Ptrl->Data[j - 1] = Ptrl->Data[j];Ptrl->last--;return;}
}

链式存储

​ 头指针

• 头指针是指链表指向的第一个节点的指针，若链表有头节点，则是指向头节点的指针

• 头指针有标志作用，一般用头指针冠以链表的名字。

• 不论链表是否为空，头指针均不为空。
  头节点

• 头节点是为了操作的方便而设立的，数据域一般无意义。

• 有了头节点，对在第一元素节点前插入节点和删除节点等操作就统一了。

• 头节点不一定是链表必须要素

• 1、头插法

  创建单链表的过程就是一个动态生成链表的过程，单链表头插法的思路是：
  \5. 声明一个节点p和计数变量i；
  \6. 初始化一空链表L；
  \7. 让L的头节点的指针指向null，建立一个带头结点的单链表。
  \8. 循环：
  ①生成一新结点赋值给P；
  ②随机生成艺术字赋值给p的数据域；
  ③将p插入到头节点与前一新结点之间。
  

  2、尾插法

  尾插法即我们在标为添加，我们设 r 为指向尾结点的变量，r 会随着循环不断的变化结点，而L我们定义为整个单链表，我们把原先的 r 的指针域存放新的尾结点的地址，然后我们最后让 r 拿到新的尾结点的地址，这样就完成了尾插法。
  

1.单链表

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LNode * List;
struct LNode {ElemType Data;List next;
};//求链表的长度
int Length(List Ptrl) {List p = Ptrl;//让p指向第一个节点int j = 0;while (p){p = p->next;j++;//当前p就会指向第j个节点}return j;
}//链表的查找（按序号查找）
List FindKth(int K, List Ptrl) {List p = Ptrl;int i = 1;//p指向第一个元素while (i < K && p != NULL){p = p->next;i++;}if (i == K) {return p;}else return NULL;
}//链表的查找（按值查找）
List FindValue(ElemType x, List Ptrl) {List p = Ptrl;while (p != NULL && p->Data != x) {p = p->next;}return p;
}//链表的插入
List Insert(ElemType x, int i, List Ptrl) {List p , s;if (i == 1) {//入过要插入在头节点前面s = (List)malloc(sizeof(struct LNode));s->Data = x;s->next = Ptrl;//next指向头节点return s;}p = FindKth(i - 1, Ptrl);if (p == NULL) {cout << "Error!" << endl;return NULL;}else{s = (List)malloc(sizeof(struct LNode));//申请，填装节点s->Data = x;s->next = p->next;p->next = s;return Ptrl;}
}//链表的删除
List Delete(int i, List Ptrl) {List p , s;if (i == 1) {//如果删除的是头节点s = Ptrl;if (Ptrl != NULL) Ptrl = Ptrl->next;else return NULL;free(s);return Ptrl;}p = FindKth(i - 1, Ptrl);//查找第i-1个节点if (p == NULL) {cout << "The Ptrl not Found!" << endl;return NULL;}else if (p->next == NULL) {cout << "The next Ptrl not Found!" << endl;}else {s = p->next;//s指向被删除节点p->next = s->next;free(s);return Ptrl;}
}

2.双链表

/*双向链表存储结构*/
typedef struct DulNodse{ElemType data;struct DulNode *prior;	//直接前驱指针struct DulNode *next;	//直接后继指针
} DulNode, *DuLinkList;//插入操作
//第一步：把p赋值给s的前驱
s->prior = p;
//第二步：把p->next赋值给s的后继
p->next = p->next
//第三步：把s赋值给p->next的前驱
p->next->prior = s;
//第四步：把s赋值给p的后继
p->next = s;//删除操作
//第一步
p->next = q->next;
//第二步
q->next->prior = p;
free(q);

3.循环链表

将单链表中终端节点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。
循环链表带有头结点的空链表如下图所示：

对于非空的循环链表则如下图所示：

只设尾节点的循环列表

上述仅设头指针的循环链表有一个弊端，我们可以用O(1)的时间访问第一个节点，但对于最后一个节点，却需要O(n)的时间，于是就有了仅设尾指针的循环链表。

如下图所示：

从上图可以看到，终端节点用尾指针rear指示，则查找终端节点是O(1)，而开始节点，其实就是rear->next->next，其时间复杂度也是O(1)。

举个程序的例子，要将两个循环链表合成一个表时，有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别是rearA和rearB。

要想把它们合并，只需要如下操作即可：

//第一步：保存A的头结点
p = rearA->next;	
//第二步：将本是指向B表的第一个节点（不是头结点）赋值给rearA->next
rearA->next = rearB->next->next;
//第三步：将原A表的头结点赋值给rearB->next
rearB->next=p;
//释放p
free(p);

4.静态链表

静态链表，使用数组连描述指针，首先我们让数组的元素都是由两个数据域组成，data和cur。数据域data，用来存放数据元素；游标cur相当于单链表的next指针，存放该元素的后继在数组中的下标。

/*** 将一维数组space中各分量链成一备用链表* space[0].cur为头指针。“0”表示空指针
*/
Status InitList(Component *space){int i;for(i=0; i<MAXSIZE; i++){space[i].cur = i+1;}space[MAXSIZE-1].cur = 0; //目前静态链表为空，最后一个元素的cur为0return OK;
}/*** 申请下一个分量的资源，返回下标
*/
int Malloc_SLL(StaticLinkList space){int i = space[0].cur;   //当前数组第一个元素的cur存的值，就是要返回的第一个备用空间的下标if(space[0].cur){space[0].cur = space[i].cur;    //把下一个分量用来做备用}return i/*** 申请下一个分量的资源，返回下标
*/
int Malloc_SLL(StaticLinkList space){int i = space[0].cur;   //当前数组第一个元素的cur存的值，就是要返回的第一个备用空间的下标if(space[0].cur){space[0].cur = space[i].cur;    //把下一个分量用来做备用}return i;/*** 得到静态列表的长度* 初始条件：静态列表L已存在。操作结果：返回L中数据元素的个数
*/
int ListLength(StaticLinkList L){int j = 0;int i = L[MAXSIZE-1].cur;while(i){i = L[i].cur;j++;}return j;
}/*** 在L中第i个元素之前插入新的元素e
*/
Status ListInsert(Component *L, int i, ElemType e){int j,k,l;k = MAXSIZE - 1;    //注意k首先是最后一个元素的下标if(i<1 || i>ListLength(L) + 1){return ERROR;}j = Malloc_SLL(L);if(j){L[j].data = e;  //将数据赋值给此分量的datafor(l=1; l<= i-1; l++){ k = L[k].cur;   //找到第i个元素之前的位置}L[j].cur = L[k].cur;    //把第i个元素之前的cur赋值给新元素的curL[k].cur = j;   //把新元素的下标赋值给第i个元素之前元素的curreturn OK;}return ERROR;/*** 删除在L中第i个数据元素e
*/
Status ListDelete(Component *L, int i){int j,k;if(i<1 || i>ListLength(L)+1){return ERROR;}k = MAXSIZE - 1;for(j=1; j<=i-1; j++){k = L[k].cur;   //找到第i个元素之前的位置}j = L[k].cur;L[k].cur = L[j].cur;OUTPUT(L);Free_SSL(&L, j);return OK;
}

堆栈

堆栈（Stack）是一组相同数据类型的组合，具有“后进先出”的特性，所有的操作均在顶端进行。

1. 堆栈的简介

   “后进先出”可以看做是往米缸里放米，先放进去的后吃，后放进去的在顶端先吃。堆栈是一种抽象数据结构（ADT，Abstract Data Type），具有下列特性：

   • 只能从堆栈的顶端存取数据
   • 数据的存取符合后进先出的原则

//创建堆栈
Stack CreateStack(int MaxSize)
{Stack S=(Stack)malloc(sizeof(struct SNode));//申请空间S->Data=(ElementType*)malloc(MaxSize * sizeof(ElementType));S->Top=-1;//栈顶初始化为-1S->MaxSize=MaxSize;return S;
}

顺序存储

#include <iostream>
#define MAXSIZE 20
using namespace std;
typedef int ElemType;
typedef struct {ElemType Data[MAXSIZE];int Top;
}SNode , *Stack;//初始化
void Init(Stack Ptrl) {Ptrl->Top = -1;
}
//入栈
void Push(Stack PtrS, ElemType item) {if (PtrS->Top == MAXSIZE - 1) {cout << "The Stack is full" << endl;}else {PtrS->Data[++(PtrS->Top)] = item;//等价于 (PtrS->Top)++//        PtrS->Data[PtrS->Top] = item}
}//出栈
int Pop(Stack PtrS) {if (PtrS->Top == -1) {cout << "The Stack is empty" << endl;return -1;}else {return(PtrS->Data[(PtrS->Top)--]);}
}

2. 数组储存两个栈

#include <iostream>
#define MAXSIZE 20
using namespace std;
typedef int ElemType;
struct DStack {ElemType Data[MAXSIZE];int Top1;int Top2;
}S;//判空条件为S.Top1 = -1; S.Top2 = MAXSIZE;
void Init(struct DStack* Ptrl) {Ptrl->Top1 = -1;Ptrl->Top2 = MAXSIZE;
}//入栈
void Push(struct DStack* Ptrl, ElemType item, int Tag) {if (Ptrl->Top2 - Ptrl->Top1 == 1) {cout << "The Stack is full" << endl;}if (Tag == 1) {//Tag = 1 对第一个堆栈操作Ptrl->Data[++(Ptrl->Top1)] = item;}else {//Tag = 2 对第二个堆栈操作Ptrl->Data[--(Ptrl->Top2)] = item;}
}//出栈
int Pop(struct DStack* PtrS, int Tag) {if (Tag == 1) {if (PtrS->Top1 == -1) {cout << "The Stack1 is empty" << endl;return NULL;}else return PtrS->Data[(PtrS->Top1)--];}else {if (PtrS->Top2 == MAXSIZE) {cout << "The Stack2 is empty" << endl;return NULL;}else return PtrS->Data[(PtrS->Top2)++];}
}int main() {DStack s;Init(&s);Push(&s, 6, 1);cout<<Pop(&s, 1);}

链式存储

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct SNode {ElemType Data;SNode* Next;
}SNode , *Stack;//构建头节点
Stack CreateStack() {Stack S;S = (Stack)malloc(sizeof(SNode));S->Next = NULL;return S;
}//判断是否为空
int IsEmpty(Stack S) {return(S->Next == NULL);//若为空则返回1，否则返回0
}//入栈
void Push(ElemType item, Stack S) {SNode* TemCell;TemCell = (SNode*)malloc(sizeof(SNode));TemCell->Data = item;TemCell->Next = S->Next; S->Next = TemCell;
}//出栈
int Pop(Stack S) {SNode* FirstCell;ElemType TopElem;if (IsEmpty(S)) {cout << "The Stack is empty" << endl;return NULL;}else {FirstCell = S->Next;//因为空间需要释放，所以让被删元素赋给变量S->Next = FirstCell->Next;TopElem = FirstCell->Data;free(FirstCell);return TopElem;}
}

队列

顺序存储

#include <iostream>
#define MAXSIZE 20
using namespace std;dad
typedef int ElemType;
typedef struct QNode {ElemType Data[MAXSIZE];int rear;int front;
}QNode , *Queue;//初始化
void Init(Queue PtrQ) {PtrQ->rear = -1;PtrQ->front = -1;
}//入队
void AddQ(Queue PtrQ, ElemType item) {if ((PtrQ->rear + 1) % MAXSIZE == PtrQ->front) {cout << "The Queue is full" << endl;}PtrQ->rear = (PtrQ->rear + 1) % MAXSIZE;PtrQ->Data[PtrQ->rear] = item;
}//出队
int DeleteQ(Queue PtrQ) {if (PtrQ->front == PtrQ->rear) {cout << "The Queue is empty" << endl;return -1;}else {PtrQ->front = (PtrQ->front + 1) % MAXSIZE;return PtrQ->Data[PtrQ->front];}
}

但这样存储会浪费空间，所以我们设置一个Tag，Tag = 1时，定义为插入，Tag = 2时，定义为删除

//定义Tag,判断队列是否已满
void IsEmpty(Queue PtrQ , int Tag) {//Tag的值需要从删除和插入操作进行赋值if (PtrQ->rear == PtrQ->front && Tag == 1) {cout << "The Queue is full" << endl;}if(PtrQ->rear == PtrQ->front && Tag == 2) {cout << "The Queue is empty" << endl;}
}

链式存储

使用链表实现堆栈

用链表实现堆栈的优点是随时可以动态改变链表长度，能有效利用内存资源，缺点是算法较为复杂

使用链表表示堆栈就需要指定一个属性next，链表方向为从上到下

top	顶端数据
↓	next指向下一个
new_data	下一个数据
↓	next指向下一个
new_data	下一个数据

#include <iostream>
using namespace std;
typedef int ElemType;
struct Node {ElemType Data;struct Node* Next;
};typedef struct QNode {Node* rear;Node* front;
}QNode , *Queue;//出队
int DeleteQ(Queue PtrQ) {Node* FrontCell;ElemType FrontElem;if (PtrQ->front == NULL) {cout << "The Queue is empty" << endl;return -1;}FrontCell = PtrQ->front;if (PtrQ->front == PtrQ->rear)PtrQ->front = PtrQ->rear = NULL;elsePtrQ->front = PtrQ->front->Next;FrontElem = FrontCell->Data;free(FrontCell);return FrontElem;
}//入队
void AddQ(Queue PtrQ , ElemType item) {Node* TemCell;TemCell = (Node*)malloc(sizeof(Node));TemCell->Data = item;PtrQ->rear->Next = TemCell;PtrQ->rear = TemCell;
}

树（⭐⭐）

二叉树

存储结构

1. 二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i ii的结点元素存储在一维数组下标为i − 1 i-1i−1的分量中。

2. 既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

typedef Position BinTree;
typedef struct TNode {ElemType Data;BinTree Left;BinTree Right;
}TNode , *Position;

遍历

//先序遍历二叉树
void PreOrderTraversal(BinTree BT) {if (BT) {cout << BT->Data << endl;PreOrderTraversal(BT->Left);PreOrderTraversal(BT->Right);}
}//中序遍历
void PreOrderTraversal(BinTree BT) {if (BT) {PreOrderTraversal(BT->Left);cout << BT->Data << endl; PreOrderTraversal(BT->Right);}
}//后序遍历
void PreOrderTraversal(BinTree BT) {if (BT) {cout << BT->Data << endl;PreOrderTraversal(BT->Left);PreOrderTraversal(BT->Right);}
}//非递归实现中序遍历
void InOrderTraversal(BinTree BT) {BinTree T = BT;Stack S = CreatStack(MaxSize);while (T || !is_empty(S)) {while (T) {Push(S, T);T = T->Left;}if (!IsEmpty(S)) {T = Pop(S);cout << T->Data;T = T->Right;}}
}//层序遍历
void LevelOrderTraversal(BinTree BT) {Queue Q;BinTree T;if (!BT) return;Q = CreatQueue(MaxSize);AddQ(Q, BT);//将根节点放入while (!IsEmpty(Q)) {T = DeleteQ(Q);//抛出第一个元素cout << T->Data << endl;if (T->Left)  AddQ(Q, T->Left);//左右儿子放进去if (T->Right) AddQ(Q, T->Right);}
}

应用

输出叶子节点

void PreOrderPrintLeaves(BinTree BT){if(BT){if(!BT->Left && !BT->Right){cout<<BT->Data<<endl;}PreOrderPrintLeaves(BT->Left);PreOrderPrintLeaves(BT->Right);}
}

求二叉树的高度

int PostOrderGetHeight(BinTree BT){int HL , HR , MaxH;if(BT){HL = PostOrderGetHeight(BT->Left);//求左子树的深度HR = PostOrderGetHeight(BT->Right);//求右子树的深度MaxH = (HL > HR) ? HL:HR;//比较return (MaxH + 1);}else return 0;//空树的深度为0
}

二叉搜索树

查找

二叉搜索树的查找有可以用递归函数来实现

//查找操作(尾递归）
Position Find(ElemType x, BinTree BST) {if (!BST) {return NULL;  //查找失败}if (x > BST->Data) {return Find(x, BST->Right);  //在右子树继续查找}else if (x < BST->Data) {return Find(x, BST->Left);  //在左子树继续查找}else return BST;
}

但是递归算法往往执行效率不高，所以我们用迭代函数

//迭代查找操作
Position IterFind(ElemType x, BinTree BST) {while (BST) {if (x > BST->Data)BST = BST->Right;else if (x < BST->Data)BST = BST->Left;else return BST;}return NULL;
}

//查找最小元素递归函数
Position FindMin(BinTree BST) {if (!BST) return NULL;else if (!BST->Left)return BST;else return FindMin(BST->Left);
}//查找最大元素递归函数
Position FindMax(BinTree BST) {if (BST) {//判断树空不空while (BST->Right) {BST = BST->Right;}return BST;}
}

插入

//插入
BinTree Insert(ElemType x, BinTree BST) {if (!BST) {//若原树为空，生成并返回一个结点的二叉搜索树BST = malloc(sizeof(TNode));BST->Data = x;BST->Left = BST->Right = NULL;}else if(x < BST->Data)//开始找要插入元素的位置{BST->Left = Insert(x, BST->Left);//递归插入左子树}else if (x > BST->Data) {BST->Right = Insert(x, BST->Right);//递归插入右子树}return BST;
}

删除

//删除
BinTree Delete(ElemType x, BinTree BST) {Position Tmp;if (!BST) cout << "The x is not found" << endl;else if (x < BST->Data){BST->Left = Delete(x, BST->Left);//左子树递归删除}else if (x > BST->Data) {BST->Right = Delete(x, BST->Right);//右子树递归删除}else if (BST->Left && BST->Right) {//被删除的结点有两个子结点Tmp = FindMin(BST->Right);//在右子树中找最小的元素填充删除结点BST->Data = Tmp->Data;BST->Right = Delete(BST->Data, BST->Right);//在删除结点的右子树中删除最小元素}else {//被删除的结点有一个或无子结点Tmp = BST;if (!BST->Left) {//有右孩子或无子结点BST = BST->Right;//若无左节点有右节点则根节点指向将右结点，//若无子结点则指向NULL}else if (!BST->Right) {//有左孩子或无子结点BST = BST->Left;}free(Tmp);}return BST;
}

平衡二叉树

AVL树的构建（⭐）

//typedef struct AVLNode *Position; 
typedef Position AVLTree; /* AVL树类型 */
typedef struct AVLNode{     ElementType Data; /* 结点数据 */    AVLTree Left;     /* 指向左子树 */    AVLTree Right;    /* 指向右子树 */    int Height;       /* 树高 */
}AVLNode , *Position;int Max ( int a, int b )
{    return a > b ? a : b; 
}AVLTree SingleLeftRotation ( AVLTree A ) 
{ /* 注意：A必须有一个左子结点B */  /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */        AVLTree B = A->Left;    A->Left = B->Right;    B->Right = A;   A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;   B->Height = Max( GetHeight(B->Left), A->Height ) + 1;     return B; 
}AVLTree DoubleLeftRightRotation ( AVLTree A ) 
{ /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */  /* 将A、B与C做两次单旋，返回新的根结点C */       /* 将B与C做右单旋，C被返回 */   A->Left = SingleRightRotation(A->Left);  /* 将A与C做左单旋，C被返回 */    return SingleLeftRotation(A);
}/*************************************/ 
/* 对称的右单旋与右-左双旋请自己实现 */
/*************************************/ AVLTree Insert( AVLTree T, ElementType X ) 
{ /* 将X插入AVL树T中，并且返回调整后的AVL树 */  if ( !T ) { /* 若插入空树，则新建包含一个结点的树 */         T = (AVLTree)malloc(sizeof(struct AVLNode));    T->Data = X;      T->Height = 0;      T->Left = T->Right = NULL;   }/* if (插入空树) 结束 */else if ( X < T->Data ) {      /* 插入T的左子树 */     T->Left = Insert( T->Left, X);   /* 如果需要左旋 */     if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )             if ( X < T->Left->Data )                 T = SingleLeftRotation(T);   }/* 左单旋 */          else        {        T = DoubleLeftRightRotation(T); /* 左-右双旋 */    } /* else if (插入左子树) 结束 */else if ( X > T->Data ) {       /* 插入T的右子树 */      T->Right = Insert( T->Right, X );      /* 如果需要右旋 */      if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )             if ( X > T->Right->Data )                 T = SingleRightRotation(T);   }/* 右单旋 */      else              {T = DoubleRightLeftRotation(T);/* 右-左双旋 */   } /* else if (插入右子树) 结束 */  /* else X == T->Data，无须插入 */   /* 别忘了更新树高 */   T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;  
}

线索二叉树

#include <iostream>
#include <cmath>
#include <time.h>
using namespace std;#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 100typedef int Status;
typedef char TElemType;typedef enum {Link, Thread
}PointerTag;typedef struct BiThrNode {TElemType data;struct BiThrNode* lchild, * rchild;PointerTag LTag;PointerTag RTag; // 左右标志
}BiThrNode , *BiThrTree;TElemType Nil = '#';  //字符型以空格符为主Status visit(TElemType e) {cout << e << endl;return OK;
}// 按前序输入二叉线索树中结点的值，构造二叉线索树
// 0（整形）/空格（字符型）表示空结点
Status CreateBiThrTree(BiThrTree *T) {TElemType h;cin >> h;if (h == Nil)*T = NULL;else{*T = (BiThrTree)malloc(sizeof(BiThrNode));if (!*T)exit(OVERFLOW);(*T)->data = h;// 生成根节点CreateBiThrTree(&(*T)->lchild); //递归构造左子树if ((*T)->lchild)//有左孩子(*T)->LTag = Link;CreateBiThrTree(&(*T)->rchild); //递归构造右子树if ((*T)->rchild)//有右孩子(*T)->RTag = Link;}return OK;
}BiThrTree pre; //全局变量，始终指向刚刚访问过的结点
//中序遍历进行中序线索化
void InThreading(BiThrTree p) {if (p) {InThreading(p->lchild);// 递归左子树线索化if (!p->lchild) {//没有左孩子p->LTag = Thread;//前驱线索p->lchild = pre;//左孩子指针指向前驱}if (!pre->rchild) {//前驱没有右孩子pre->RTag = Thread;//后继线索pre->rchild = p;//前驱右孩子指针指向后继（当前结点p）}pre = p;//保持pre指向p的前驱InThreading(p->rchild);//递归右子树线索化}
}/* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree* Thrt, BiThrTree T)
{*Thrt = (BiThrTree)malloc(sizeof(BiThrNode));if (!*Thrt)exit(OVERFLOW);(*Thrt)->LTag = Link; /* 建头结点 */(*Thrt)->RTag = Thread;(*Thrt)->rchild = (*Thrt); /* 右指针回指 */if (!T) /* 若二叉树空,则左指针回指 */(*Thrt)->lchild = *Thrt;else{(*Thrt)->lchild = T;pre = (*Thrt);InThreading(T); /* 中序遍历进行中序线索化 */pre->rchild = *Thrt;pre->RTag = Thread; /* 最后一个结点线索化 */(*Thrt)->rchild = pre;}return OK;
}/* 中序遍历二叉线索树T(头结点)的非递归算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{BiThrTree p;p = T->lchild; /* p指向根结点 */while (p != T){ /* 空树或遍历结束时,p==T */while (p->LTag == Link)p = p->lchild;if (!visit(p->data)) /* 访问其左子树为空的结点 */return ERROR;while (p->RTag == Thread && p->rchild != T){p = p->rchild;visit(p->data); /* 访问后继结点 */}p = p->rchild;}return OK;
}int main()
{BiThrTree H, T;printf("请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')\n");CreateBiThrTree(&T); /* 按前序产生二叉树 */InOrderThreading(&H, T); /* 中序遍历,并中序线索化二叉树 */printf("中序遍历(输出)二叉线索树:\n");InOrderTraverse_Thr(H); /* 中序遍历(输出)二叉线索树 */printf("\n");return 0;
}

堆

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<=K2i+2 ，则称为小堆(或大堆)。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

1. 堆中某个节点的值总是不大于或不小于其父节点的值;
2. 堆总是一棵完全二叉树。

（1）向下调整算法

堆的向下调整:
(以小堆为例）

1. 先设定根节点为当前节点(通过下标获取，标记为cur)，比较左右子树的值，找出更小的值，用child来标记。
2. 比较child和cur的值，如果child比cur小，则不满足小堆的规则，需要进行交换。
3. 如果child比cur大，满足小堆的规则，不需要交换，调整结束。
4. 处理完一个节点之后，从当前的child出发，循环之前的过程。

向下调整（小堆）示例：
向下调整（大堆）示例：

（2）向上调整算法(堆的创建)

下面我们给出两个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。

根节点左右子树不是堆，我们怎么调整呢？

这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

堆的向上调整:
(以小堆为例）

1. 先设定倒数的第一个叶子节点为当前节点(通过下标获取，标记为cur)，找出他的父亲节点，用parent来标记。
2. 比较parent和cur的值，如果cur比parent小，则不满足小堆的规则，需要进行交换。
3. 如果cur比parent大，满足小堆的规则，不需要交换，调整结束。
4. 处理完一个节点之后，从当前的parent出发，循环之前的过程。

int a[] =    {9,7,8,10,3,6}
1

向上调整（小堆）示例：

int a[] =    {1,5,3,8,7,6}
1

向上调整（大堆）示例：

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct HNode {ElemType* Data;int Size;int Capacity;
}HNode , *Heap;typedef Heap MaxHeap;//最大堆
typedef Heap MinHeap;//最小堆#define MAXDATA 1000 //岗哨，防止插入元素比最后的根大//构建堆
MaxHeap CreatHeap(int MaxSize) {MaxHeap H = (MaxHeap)malloc(sizeof(HNode)); H->Data = (ElemType*)malloc((MaxSize + 1) * sizeof(ElemType));H->Size = 0;H->Capacity = MaxSize;H->Data[0] = MAXDATA;//定义哨兵为大于堆所有元素的值return H;
}//判满操作
bool IsFull(MaxHeap H) {return(H->Size == H->Capacity);
}//插入操作
bool Insert(MaxHeap H, ElemType x) {int i;if (IsFull(H)) {cout << "最大堆已满！" << endl;return false;}i = ++H->Size;//i指向插入后堆中的最后一个元素位置for (; H->Data[i / 2] < x; i /= 2) {H->Data[i] = H->Data[i / 2];//上滤x}H->Data[i] = x;return true;
}#define ERROR - 1
bool IsEmpty(MaxHeap H) {return (H->Size == 0);
}//删除操作
int DeleteMax(MaxHeap H) {//从最大堆H中取出最大元素，并删除一个结点int Parent, Child;ElemType MaxItem, temp;if (IsEmpty(H)) {cout << "最大堆已空！" << endl;return ERROR;}MaxItem = H->Data[1];//保存要删除的结点temp = H->Data[H->Size];//最后一个结点H->Size--;for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {Child = Parent * 2;if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1])) {Child++;//保证有右儿子 ， 左儿子小于右儿子}if (temp >= H->Data[Child]) break;else{H->Data[Parent] = H->Data[Child];}}H->Data[Parent] = temp;return MaxItem;
}//堆的建立
void PercDown(MaxHeap H, int p)
{ /* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */int Parent, Child;ElemType X;X = H->Data[p]; /* 取出根结点存放的值 */for (Parent = p; Parent * 2 <= H->Size; Parent = Child) {Child = Parent * 2;if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))Child++;  /* Child指向左右子结点的较大者 */if (X >= H->Data[Child]) break; /* 找到了合适位置 */else  /* 下滤X */H->Data[Parent] = H->Data[Child];}H->Data[Parent] = X;
}void BuildHeap(MaxHeap H)
{ /* 调整H->Data[]中的元素，使满足最大堆的有序性  *//* 这里假设所有H->Size个元素已经存在H->Data[]中 */int i;/* 从最后一个结点的父节点开始，到根结点1 */for (i = H->Size / 2; i > 0; i--)PercDown(H, i);
}

哈夫曼树（待修改）（⭐）

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct TreeNode * HuffmanTree;
typedef struct TreeNode {int weight;HuffmanTree left, right;
};//定义堆
typedef struct HNode {ElemType* Data;int Size;int Capacity;
}HNode, * Heap;typedef Heap MaxHeap;//最大堆
typedef Heap MinHeap;//最小堆#define ERROR - 1
bool IsEmpty(MaxHeap H) {return (H->Size == 0);
}//删除操作
int DeleteMin(MaxHeap H) {//从最大堆H中取出最大元素，并删除一个结点int Parent, Child;ElemType MinItem, temp;if (IsEmpty(H)) {cout << "最大堆已空！" << endl;return ERROR;}MinItem = H->Data[1];//保存要删除的结点temp = H->Data[H->Size];//最后一个结点H->Size--;for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {Child = Parent * 2;if ((Child != H->Size) && (H->Data[Child] > H->Data[Child + 1])) {Child++;//保证有右儿子 ， 左儿子大于右儿子}if (temp <= H->Data[Child]) break;else{H->Data[Parent] = H->Data[Child];}}H->Data[Parent] = temp;return MinItem;
}//判满操作
bool IsFull(MaxHeap H) {return(H->Size == H->Capacity);
}//插入操作
bool Insert(MaxHeap H, ElemType x) {int i;if (IsFull(H)) {cout << "最大堆已满！" << endl;return false;}i = ++H->Size;//i指向插入后堆中的最后一个元素位置for (; H->Data[i / 2] < x; i /= 2) {H->Data[i] = H->Data[i / 2];//上滤x}H->Data[i] = x;return true;
}void PercDown(MinHeap H, int p)
{ /* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */int Parent, Child;ElemType X;X = H->Data[p]; /* 取出根结点存放的值 */for (Parent = p; Parent * 2 <= H->Size; Parent = Child) {Child = Parent * 2;if ((Child != H->Size) && (H->Data[Child] > H->Data[Child + 1]))Child++;  /* Child指向左右子结点的较小者 */if (X <= H->Data[Child]) break; /* 找到了合适位置 */else  /* 下滤X */H->Data[Parent] = H->Data[Child];}H->Data[Parent] = X;
}void BuildMinHeap(MaxHeap H)
{ /* 调整H->Data[]中的元素，使满足最大堆的有序性  *//* 这里假设所有H->Size个元素已经存在H->Data[]中 */int i;/* 从最后一个结点的父节点开始，到根结点1 */for (i = H->Size / 2; i > 0; i--)PercDown(H, i);
}//哈夫曼树的构造
HuffmanTree Huffman(MinHeap H)
{ /* 假设H->Size个权值已经存在H->Elements[]->Weight里 */int i; HuffmanTree T;BuildMinHeap(H); /*将H->Elements[]按权值调整为最小堆*/for (i = 1; i < H->Size; i++) { /*做H->Size-1次合并*/T =(HuffmanTree) malloc(sizeof(struct TreeNode)); /*建立新结点*/T->left = DeleteMin(H);/*从最小堆中删除一个结点，作为新T的左子结点*/T->right = DeleteMin(H);/*从最小堆中删除一个结点，作为新T的右子结点*/T->weight = T->left->Weight + T->right->Weight;/*计算新权值*/Insert(H, T); /*将新T插入最小堆*/}T = DeleteMin(H);return T;
}

代码不完善，待修改

#include <iostream>
using namespace std;
typedef struct {int weight;int parent, lchild, rchild;
}HTNode , *HuffmanTree;void CreateHuffmanTree(HuffmanTree& HT, int n) {if (n < 1) return;int m = 2 * n - 1;int s1, s2;HT = new HTNode[m + 1];for (int i = 0; i < m; i++){HT[i].parent = 0;HT[i].lchild = 0;HT[i].rchild = 0;}for (int i = 0; i < n; i++){cin >> HT[i].weight;}/*===================初始化结束，开始创建哈夫曼树========================*/for (int i = n - 1; i <= m; i++){Select(HT, i - 1, &s1, &s2);HT[s1].parent = i;HT[s2].parent = i;HT[i].lchild = s1;HT[i].rchild = s2;HT[i].weight = HT[s1].weight + HT[s2].weight;}
}int Select(HuffmanTree HT, int top, int* s1, int* s2)
{int min = INT_MAX;for (int i = 1; i <= top; ++i)  // 选择没有双亲的节点中，权重最小的节点 {if (HT[i].weight < min && HT[i].parent == 0){min = HT[i].weight;*s1 = i;}}min = INT_MAX;for (int i = 1; i <= top; ++i)  // 选择没有双亲的节点中，权重次小的节点 {if (HT[i].weight < min && i != *s1 && HT[i].parent == 0){min = HT[i].weight;*s2 = i;}}return 1;
}

主函数需要以下几个类

int main(int argc, char** argv) {char data[MaxSize];  NumCount Cntarray;ReadData(data);  // 读入数据 WordCount(data,&Cntarray);  // 统计次数 
//	Show(&Cntarray); //可以查看每个单词出现的对应次数 HuffmanTree tree;CreateHuffmanTree(tree,Cntarray.length,Cntarray);  // 建树 HuffmanCode code;  CreateHuffmanCode(tree,code,Cntarray.length);  // 创建编码 Encode(data,code,Cntarray.length);  // 生成编码文件 Decode(tree,Cntarray.length);  // 解码 cout<<"Please view the generated TXT file to check the result"<<endl; return 0;
}

需要以下几种结构

typedef struct wordcnt{  // 统计字符和对应的次数 char ch;int cnt = 0;
}Count;typedef struct NumCount{  // 统计次数的外部封装 Count count[MaxSize];int length = 0;
}NumCount;typedef struct HTree{  // 哈夫曼树结构 char data; int weight;int parent,lchild,rchild;
}HTNode,*HuffmanTree; typedef struct HCode{ // 编码结构 char data;char* str; 
}*HuffmanCode;

读取函数如下

int ReadData(char *source)
{//打开文件读入数据 ifstream infile;infile.open("in.txt");cout<<"Reading..."<<endl;cout<<"the input file is:"<<endl;infile.getline(source,MaxSize);cout<<source<<endl;infile.close();cout<<endl;return OK;
}

统计次数

int WordCount(char *data,NumCount *paraCnt)
{int flag;// 标识是否已经记录 int len = strlen(data);for(int i = 0;i < len;++i){flag = 0;for(int j = 0;j < paraCnt->length;++j){if(paraCnt->count[j].ch == data[i]) // 若已有记录，直接++ {++paraCnt->count[j].cnt;flag = 1;break;}}if(!flag) // 没有记录，则新增 {paraCnt->count[paraCnt->length].ch = data[i];++paraCnt->count[paraCnt->length].cnt;++paraCnt->length;}}return OK;
}

建树的方法

int CreateHuffmanTree(HuffmanTree &HT,int length,NumCount cntarray)
{if(length <= 1) return ERROR;int s1,s2;int m = length*2-1;  // 没有度为1的节点，则总结点是2*叶子节点数-1个 HT = new HTNode[m+1];for(int i = 1;i <= m;++i)  // 初始化 {HT[i].parent = 0;HT[i].lchild = 0;HT[i].rchild = 0;}for(int i = 1;i <= length;++i) {HT[i].data = cntarray.count[i-1].ch;HT[i].weight = cntarray.count[i-1].cnt;}for(int i = length + 1;i <= m;++i){select(HT,i-1,&s1,&s2);  // 从前面的范围里选择权重最小的两个节点 HT[s1].parent = i;HT[s2].parent = i;HT[i].lchild = s1;HT[i].rchild = s2;HT[i].weight = HT[s1].weight + HT[s2].weight;  // 得到一个新节点 }return OK;
}

打印

int Decode(HuffmanTree HT,int length)
{char codetxt[MaxSize*length];ifstream infile;infile.open("code.txt");infile.getline(codetxt,MaxSize*length);infile.close();ofstream outfile;outfile.open("out.txt");int root = 2*length-1;  // 从根节点开始遍历 for(int i = 0;i < strlen(codetxt);++i){if(codetxt[i] == '0') root = HT[root].lchild;  //为0表示向左遍历 else if(codetxt[i] == '1') root = HT[root].rchild; //为1表示向右遍历 if(HT[root].lchild == 0 && HT[root].rchild == 0)  // 如果已经是叶子节点，输出到输出文件中，然后重新回到根节点 {outfile<<HT[root].data;root = 2*length-1;}}outfile.close();cout<<"the output txt has been written"<<endl;cout<<endl;return OK;
}

哈夫曼编码（⭐）

编码

int CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int length)
{HC = new HCode[length+1];char *cd = new char[length];  // 存储编码的临时空间 cd[length-1] = '\0';  // 方便之后调用strcpy函数 int c,f,start;for(int i = 1;i <= length;++i){start = length-1;  // start表示编码在临时空间内的起始下标，由于是从叶子节点回溯，所以是从最后开始 c = i;f = HT[c].parent;while(f != 0){--start;  // 由于是回溯，所以从临时空间的最后往回计 if(HT[f].lchild == c)cd[start] = '0';else cd[start] = '1';c = f;f = HT[c].parent;}HC[i].str = new char[length-start];  // 最后，实际使用的编码空间大小是length-start HC[i].data = HT[i].data;strcpy(HC[i].str,&cd[start]);  // 从实际起始地址开始，拷贝到编码结构中 }delete cd;
}

输入编码文件

int Status Encode(char *data,HuffmanCode HC,int length)
{ofstream outfile;outfile.open("code.txt");for(int i = 0;i < strlen(data);++i)  // 依次读入数据，查找对应的编码，写入编码文件 {for(int j = 1;j <= length;++j){if(data[i] == HC[j].data){outfile<<HC[j].str;}}}outfile.close();cout<<"the code txt has been written"<<endl;cout<<endl;return OK;
}

解码

int Decode(HuffmanTree HT,int length)
{char codetxt[MaxSize*length];ifstream infile;infile.open("code.txt");infile.getline(codetxt,MaxSize*length);infile.close();ofstream outfile;outfile.open("out.txt");int root = 2*length-1;  // 从根节点开始遍历 for(int i = 0;i < strlen(codetxt);++i){if(codetxt[i] == '0') root = HT[root].lchild;  //为0表示向左遍历 else if(codetxt[i] == '1') root = HT[root].rchild; //为1表示向右遍历 if(HT[root].lchild == 0 && HT[root].rchild == 0)  // 如果已经是叶子节点，输出到输出文件中，然后重新回到根节点 {outfile<<HT[root].data;root = 2*length-1;}}outfile.close();cout<<"the output txt has been written"<<endl;cout<<endl;return OK;
}

集合

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct {ElemType Data;int Parent;
}SetType;int MaxSize;
//查找
int Find(SetType s[], ElemType x) {//在数组中查找值为x的元素所属集合//MaxSize是全局变量，为数组s的最大长度int i;for (i = 0; i < MaxSize && s[i].Data != x; i++);if (i >= MaxSize) return -1;for (; s[i].Parent >= 0; i = s[i].Parent);return i;}

图（⭐⭐⭐）

**图(Graph)是由顶点的有穷非空集合**V ( G ) V(G)V(G)**和顶点之间边的集合**E ( G ) E(G)E(G)**组成，通常表示为: *G = ( V , E ) G=(V,E)G=(V,E)*，其中，**G GG**表示个图，**V VV**是图**G GG**中顶点的集合，**E EE**是图**G GG**中边的集合。若*V = { v 1 , v 2 , . . . , v n } V= {v_1, v_2,…,v_n}V={v1,v2,…,vn}*，则用**∣ V ∣ |V|∣V∣**表示图**G GG**中顶点的个数，也称图**G GG**的阶，*E = { ( u , v ) ∣ u ∈ V , v ∈ V } E= {(u, v) |u∈V, v∈V}E={(u,v)∣u∈V,v∈V}*，用**∣ E ∣ |E|∣E∣**表示图*G GG*中边的条数。

注意:线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边

图的表示（邻接矩阵）

图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设图G GG有n nn个顶点，则邻接矩阵A AA是一个n ∗ n n*nn∗n的方阵，定义为:

下图是一个无向图和它的邻接矩阵：

可以看出:

1. 无向图的邻接矩阵一定是一个对称矩阵(即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的)。 因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。
2. 对于无向图，邻接矩阵的第i ii行(或第i ii列)非零元素(或非∞ ∞∞元素)的个数正好是第i ii个顶点的度T D ( v i ) TD(v_i)TD(vi)。比如顶点v 1 v_1v1的度就是1 + 0 + 1 + 0 = 2 1+0+1+0=21+0+1+0=2。
3. 求顶点v i v_ivi的所有邻接点就是将矩阵中第i行元素扫描一遍， A [ i ] [ j ] A[i][j]A[i][j]为 1就是邻接点。

typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100
#define INFINITY 65535
typedef struct{VertexType vexs[MAXVEX];EdgeType arc[MAXVEX][MAXVEX];int numNodes , numEdges;
}MGraph;/*建立无向网图的邻接矩阵表示*/
void CreateMGraph(MGraph *G){int i , j , k , w;cout<<"please input vertex and side:"<<endl;cin>>G->numNodes>>G->numEdges;for(i = 0 ; i < G->numNodes ; ++i)  //读入顶点表cin>>G->vexs[i];for(i = 0 ; i < G->numNodes ; ++i){for(j = 0 ; j < G->numNodes ; ++j){G->arc[i][j] = INFINITY;}}for(k = 0 ; k < G->numEdges ; ++k){//读入边，建立邻接矩阵cout<<"输入边(vi,vj)上的下标i，下标j和权w："<<endl;cin>>i>>j>>w;G->arc[i][j] = w;G->arc[j][i] = G->arc[i][j];  //无向图，矩阵对称
}
}

图的表示（邻接表）

当一个图为稀疏图时（边数相对顶点较少），使用邻接矩阵法显然要浪费大量的存储空间，如下图所示：

而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。
所谓邻接表，是指对图G GG中的每个顶点v i v_ivi建立一个单链表，第i ii个单链表中的结点表示依附于顶点v i v_ivi 的边(对于有向图则是以顶点v i v_ivi为尾的弧)，这个单链表就称为顶点v i v_ivi的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)，所以在邻接表中存在两种结点:顶点表结点和边表结点，如下图所示。

顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc) 构成，边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc) 构成。
无向图的邻接表的实例如下图所示。

有向图的邻接表的实例如下图所示。

此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。

#include <iostream>
using namespace std;
#define MaxVertexNum 100 //最大顶点数为100typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
typedef int WeightType;        /* 边的权值设为整型 */
typedef char DataType;        /* 顶点存储的数据类型设为字符型 *//* 边的定义 */
typedef struct ENode* PtrToENode;
struct ENode {Vertex V1, V2;      /* 有向边<V1, V2> */WeightType Weight;  /* 权重 */
};
typedef PtrToENode Edge;//邻接点的定义
typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode {Vertex AdjV;  //邻接点下标WeightType Weight;  //边的权重PtrToAdjVNode Next;  //指向下一个邻接点的指针
};//顶点表头结点的定义
typedef struct Vnode {PtrToAdjVNode FirstEdge;  //边表头指针DataType Data;;  //存顶点的数据//注意：很多情况下，顶点无数据，此时Data可以不用出现
}AdjList[MaxVertexNum];//图结点的定义
typedef struct GNode* PtrToGNode;
struct GNode {int Nv; //顶点数int Ne; //边数AdjList G; //邻接表
};
typedef PtrToGNode LGraph; //以邻接表方式存储的图类型LGraph CreateGraph(int VertexNum) {//初始化一个有VertexNum个顶点但没有边的图Vertex V;LGraph Graph;Graph = (LGraph)malloc(sizeof(GNode)); //建立图，请求空间Graph->Nv = VertexNum;Graph->Ne = 0;//初始化邻接表头指针//注意：这里默认顶点编号从0开始，到(Graph->Nv - 1)for (V = 0; V < Graph->Nv; V++) {Graph->G[V].FirstEdge = NULL;}return Graph;
}void InsertEdge(LGraph Graph, Edge E) {PtrToAdjVNode NewNode;//插入边<V1 , V2>//为V2建立新的邻接点NewNode = (PtrToAdjVNode)malloc(sizeof(AdjVNode));NewNode->AdjV = E->V2;NewNode->Weight = E->Weight;//将V2插入V1的表头NewNode->Next = Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge = NewNode;
}LGraph BuildGraph() {LGraph Graph;Edge E;Vertex V;int Nv, i;cin >> Nv;//读入顶点个数Graph = CreateGraph(Nv);//初始化有Nv个顶点但没有边的图cin >> Graph->Ne;if (Graph->Ne != 0) {E = (Edge)malloc(sizeof(ENode));//读入边，格式为“起点 终点 权重”插入邻接矩阵for (int i = 0; i < Graph->Ne; ++i) {cin >> E->V1 >> E->V2 >> E->Weight;//注意：如果权重不是整数，weight的读入格式要改InsertEdge(Graph, E);}}//如果顶点有数据的话，读入数据for (int V = 0; V < Graph->Nv; V++) {cin >> Graph->G[V].Data;}return Graph;
}

十字链表

十字链表是有向图的一种链式存储结构。
对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢?答案是肯定的，就是把它们整合在一起。这就是我们现在要介绍的有向图的一种存储方法：十字链表(Orthogonal List)。
我们重新定义顶点表结点结构如下表所示。

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout 表示出边表头指针，指向该顶点的出边表中的第一个结点。
重新定义的边表结点结构如下表所示。

其中tailvex 是指弧起点在顶点表的下标，headvex 是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。

接下来通过一个例子详细介绍十字链表的结构。
如下图所示，顶点依然是存入一个一维数组{ V 0 , V 1 , V 2 , V 3 } {V_0,V_1,V_2,V_3}{V0​,V1​,V2​,V3​}，实线箭头指针的图示完全与的邻接表的结构相同。就以顶点V 0 V_0V0​来说，firstout 指向的是出边表中的第一个结点V 3 V_3V3​。所以V 0 V_0V0​边表结点的h e a d v e x = 3 headvex=3headvex=3，而tailvex就是当前顶点V 0 V_0V0​的下标0，由于V 0 V_0V0​只有一个出边顶点，所以headlink和taillink都是空。

我们重点需要来解释虚线箭头的含义，它其实就是此图的逆邻接表的表示。对于V 0 V_0V0​来说，它有两个顶点V 1 V_1V1​和V 2 V_2V2​的入边。因此V 0 V_0V0​的firstin指向顶点V 1 V_1V1​的边表结点中headvex为0的结点，如上图右图中的①。接着由入边结点的headlink指向下一个入边顶点V 2 V_2V2​，如图中的②。对于顶点V 1 V_1V1​,它有一个入边顶点V 2 V_2V2​，所以它的firstin指向顶点V 2 V_2V2​的边表结点中headvex为1的结点，如图中的③。顶点V 2 V_2V2​和V 3 V_3V3​也是同样有一个入边顶点，如图中④和⑤。

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起， 这样既容易找到以V 1 V_1V1为尾的弧，也容易找到以V 1 V_1V1为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中，十字链表是非常好的数据结构模型。

#define MaxVertexTypeNum 100
typedef char VertexType;
typedef int EdgeType;typedef struct ArcNode{  //边表结点int tailvex , headvex;  //尾域和头域struct ArcNode *hlink , *think; //出单链表和入单链表//InfoType info   权值
}AceNode;typedef struct VNode{				//顶点表节点 VertexType data;				//顶点的数据 ArcNode *firstin,*firstout;		//入单链表的头指针和入单链表的头指针 
}VNode;	// 邻接表类型 typedef struct{						//十字链表 VNode xlist[MaxVertexTypeNum];	//所有结点的数据 int vexnum,arcnum;				//节点数和边数 
}ALGraph;				

临界多重表

与十字链表一样，邻接多重表是由顶点集合和边集合构成的。但又与十字链表不同的是，邻接多重表是无向图的存储结构吗，而十字链表是针对有向图的。因为不考虑边的方向，所以和十字链表相比较，顶点结点只需要一个指针域指向所连接的边结点即可。

边集数组

说明：边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息。这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成。

图的遍历

深度优先遍历

深度优先遍历有点像死磕，从第一个点开始细化查找到底，然后开始接下来的点。

邻接矩阵

void DFS(MGraph G , int i){int j;visited[i] = true;cout<<G.vexs[i]<<" ";for(j = 0 ; j < G.numVertexes ; ++j){if(G.arc[i][j] == 1 && !visited[j])DFS(G , i);}
}void DFSTraverse(MGraph G){int i;for(int i = 0 ; i < G.numVertexes ; ++i){visited[i] = false;}for(int i = 0 ; i < G.numVertexes ; ++i){if(!visited[i])  DFS(G , i);}
}

邻接表

void DFS(GraphAdjList GL , int i){EdgeNode *p;visited[i] = true;cout<<GL->adjList[i].data<<" ";p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL , p->adjvex);p = p->next;}
}void DFSTraverse(GraphAdjList GL){int i;for(int i = 0 ; i < GL->numVertexes ; ++i){visited[i] = false;}for(i = 0 ; i < GL->numVertexes ; ++i){if(!visited[i]) DFS(GL , i);}
}

广度优先遍历

广度优先遍历的重点是广，先大致走一遍，然后慢慢扩大范围。

邻接矩阵

/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G)
{int i, j;Queue Q;for(i = 0; i < G.numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);		/* 初始化一辅助用的队列 */for(i = 0; i < G.numVertexes; i++)  /* 对每一个顶点做循环 */{if (!visited[i])	/* 若是未访问过就处理 */{visited[i]=TRUE;		/* 设置当前顶点访问过 */printf("%c ", G.vexs[i]);/* 打印顶点，也可以其它操作 */EnQueue(&Q,i);		/* 将此顶点入队列 */while(!QueueEmpty(Q))	/* 若当前队列不为空 */{DeQueue(&Q,&i);	/* 将队对元素出队列，赋值给i */for(j=0;j<G.numVertexes;j++) { /* 判断其它顶点若与当前顶点存在边且未访问过  */if(G.arc[i][j] == 1 && !visited[j]) { visited[j]=TRUE;		/* 将找到的此顶点标记为已访问 */printf("%c ", G.vexs[j]);	/* 打印顶点 */EnQueue(&Q,j);				/* 将找到的此顶点入队列  */} } }}}
}

邻接表

void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印顶点,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge;/* 找到当前顶点的边表链表头指针*/while(p){if(!visited[p->adjvex])	/* 若此顶点未被访问 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex);	/* 将此顶点入队列 */}p = p->next;	/* 指针指向下一个邻接点 */}}}}
}

最小生成树

Prim算法

除了Kruskal算法以外，普里姆算法（Prim算法）也是常用的最小生成树算法。虽然在效率上差不多。但是贪心的方式和Kruskal完全不同。

prim算法的核心信仰是：从已知扩散寻找最小。它的实现方式和Dijkstra算法相似但稍微有所区别，Dijkstra是求单源最短路径，而每计算一个点需要对这个点重新更新距离，而prim不用更新距离。直接找已知点的邻边最小加入即可！prim和kruskal算法都是从边入手处理。

对于具体算法具体步骤，大致为：

寻找图中任意点，以它为起点，它的所有边V加入集合(优先队列)q1,设置一个boolean数组bool[]标记该位置(边有两个点，每次加入没有被标记那个点的所有边)。
从集合q1找到距离最小的那个边v1并 判断边是否存在未被标记的一点p ，如果p不存在说明已经确定过那么跳过当前边处理，如果未被标(访问)记那么标记该点p,并且与p相连的未知点(未被标记)构成的边加入集合q1， 边v1(可以进行计算距离之类，该边构成最小生成树) .
重复1，2直到q1为空，构成最小生成树 ！

/* Prim算法生成最小生成树  */
void MiniSpanTree_Prim(MGraph G)
{int min, i, j, k;int adjvex[MAXVEX];		/* 保存相关顶点下标 */int lowcost[MAXVEX];	/* 保存相关顶点间边的权值 */lowcost[0] = 0;/* 初始化第一个权值为0，即v0加入生成树 *//* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */adjvex[0] = 0;			/* 初始化第一个顶点下标为0 */for(i = 1; i < G.numVertexes; i++)	/* 循环除下标为0外的全部顶点 */{lowcost[i] = G.arc[0][i];	/* 将v0顶点与之有边的权值存入数组 */adjvex[i] = 0;					/* 初始化都为v0的下标 */}for(i = 1; i < G.numVertexes; i++){min = GRAPH_INFINITY;	/* 初始化最小权值为∞， *//* 通常设置为不可能的大数字如32767、65535等 */j = 1;k = 0;while(j < G.numVertexes)	/* 循环全部顶点 */{if(lowcost[j]!=0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */{	min = lowcost[j];	/* 则让当前权值成为最小值 */k = j;			/* 将当前最小值的下标存入k */}j++;}printf("(%d, %d)\n", adjvex[k], k);/* 打印当前顶点边中权值最小的边 */lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */for(j = 1; j < G.numVertexes; j++)	/* 循环所有顶点 */{if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j]) {/* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */lowcost[j] = G.arc[k][j];/* 将较小的权值存入lowcost相应位置 */adjvex[j] = k;				/* 将下标为k的顶点存入adjvex */}}}
}

Kruskal算法

Kruskal算法是一种用来查找最小生成树（M S T MSTMST）的算法，由Joseph Kruskal在1956年发表。求最小生成树的算法常用有两种：Kruskal算法和Prim算法。这里指路一篇Prim算法的详解blog：https://blog.csdn.net/hzf0701/article/details/107927858。与Prim算法不同的是，该算法的核心思想是归并边，而Prim算法的核心思想是归并点。这里我们会在后面的实现过程中看到。

假设连通网N = ( V , E ) N=(V,E)N=(V,E)，将N NN中的边按权值从小到大的顺序排列。
①初始状态为只有n nn个顶点而无边的非连通图T = ( V , { } ) T=(V,{})T=(V,{})，图中每个顶点自成一个连通分量。
②在E EE中选择权值最小的边，若该边依附的顶点落在T TT中不同的连通分量上（即不形成回路），则将此边将入到T TT中，否则舍去此边而选择下一条权值最小的边。
③重复②，直到T TT中所有的顶点都在同一连通分量上为止。

这个算法的构造过程十分简洁明了，那么为什么这样的构造过程能否形成最小生成树呢？我们来看第二个步骤，因为我们选取的边的顶点是不同的连通分量，且边权值是最小的，所以我们保证加入的边都不使得T TT有回路，且权值也最小。这样最后当所有的连通分量都相同时，即所有的顶点都在生成树中被连接成功了，我们构造成的树也就是最小生成树了。

/* 查找连线顶点的尾部下标 */
int Find(int *parent, int f)
{while ( parent[f] > 0){f = parent[f];}return f;
}/* 生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G)
{int i, j, n, m;int k = 0;int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 *//* 用来构建边集数组并排序********************* */for ( i = 0; i < G.numVertexes-1; i++){for (j = i + 1; j < G.numVertexes; j++){if (G.arc[i][j]<GRAPH_INFINITY){edges[k].begin = i;edges[k].end = j;edges[k].weight = G.arc[i][j];k++;}}}sort(edges, &G);/* ******************************************* */for (i = 0; i < G.numVertexes; i++)parent[i] = 0;	/* 初始化数组值为0 */printf("打印最小生成树：\n");for (i = 0; i < G.numEdges; i++)	/* 循环每一条边 */{n = Find(parent,edges[i].begin);m = Find(parent,edges[i].end);if (n != m) /* 假如n与m不等，说明此边没有与现有的生成树形成环路 */{parent[n] = m;	/* 将此边的结尾顶点放入下标为起点的parent中。 *//* 表示此顶点已经在生成树集合中 */printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);}}
}

最短路径

Dijkstra 算法

Dijkstra算法思想是基于贪心算法思想的。所谓贪心算法即始终保持当前迭代解为当前最优解。*意思就是在已知的条件下或是当前拥有的全部条件下保证最优解，若在此后的迭代中由于加入了新的条件使得产生了更优解则替代此前的最优解。通过不断的迭代不断保证每次迭代的结果都是当前*最优解，那么当迭代到最后一轮时得到的就会是全局最优解**。 由于下一轮迭代会参考上一轮的最优解，因此每一轮的迭代的工作量基本一致，降低了整体工作的复杂性。

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535typedef struct{int vexs[MAXVEX];int arc[MAXVEX][MAXVEX];int numVertexes , numEdges;
}MGraph;typedef int Patharc[MAXVEX];//用于存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX];//用于存储各点最短路径的权值和

算法代码

void ShortestPath_Dijkstra(MGraph G , int v0 , Patharc *P , ShortPathTable *D){int v , w , k , min;int final[MAXVEX];for(v = 0 ; v < G.numVertexes ; ++v){final[v] = 0;(*D)[v] = G.arc[v0][v];(*P)[v] = -1;}(*D)[v0] = 0;final[v0] = 1;// 开始主循环，每次求得v0到某个顶点v的最短路径for(v = 1 ; v < G.numVertexes ; ++v){min = INFINITY;for(w = 0 ; w < G.numVertexes ; ++W){//寻找距离v0最近的顶点if(!final[w] && (*D)[w] < win){k = w;min = (*D)[w];//w顶点离v0顶点更近}}final[k] = 1; //将目前找的最近的顶点置为1for(w = 0 ; w < G.numVertexes ; ++W){if(!final[w] && (min + G.arc[k][w] < (*D)[w])){(*D)[w] = min + G.arc[k][w]; //计算路径长度(*P)[w] = k;  //记录路径点}}}
}

Floyd 算法

1. 在主函数中创建一个矩阵，存储输入的两点间的距离。
   2.在Floyd函数中，初始化记录最短距离的矩阵和记录中介点的矩阵。初始化之后将主函数的矩阵复制给记录最短距离的矩阵。
   3.用三层循环不断更新最短距离。

优点：比较容易容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。
缺点：时间复杂度比较高(n3)，不适合计算大量数据，当数据稍微大点儿的时候就可以选择其他的算法来解决问题了，不然也会是超时。

Floyd算法与Dijkstra算法的不同

1. Floyd算法是求任意两点之间的距离，是多源最短路，而Dijkstra(迪杰斯特拉)算法是求一个顶点到其他所有顶点的最短路径，是单源最短路。

2. Floyd算法属于动态规划，我们在写核心代码时候就是相当于推dp状态方程，Dijkstra(迪杰斯特拉)算法属于贪心算法。

3. Dijkstra(迪杰斯特拉)算法时间复杂度一般是o(n^{2),Floyd算法时间复杂度是o(n}3),Dijkstra(迪杰斯特拉)算法比Floyd算法块。

4. Floyd算法可以算带负权的，而Dijkstra(迪杰斯特拉)算法是不可以算带负权的。并且Floyd算法不能算负权回路。

typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];//Floyd算法，求网图G中顶点v到其余顶点w的最短路径
void ShortestPath_Floyd(MGraph G , Patharc *p , ShortPathTable *D){int v , w , k;for(v = 0 ; v < G.numVertexes ; ++v){for(w = 0 ; w < G.numVertexes ; ++w){(*D)[v][w] = G.arc[v][w]; //D[v][w]值即为对应点间的权值(*P)[v][w] = w; //初始化p}}for(k = 0 ; k < G.numVertexes ; ++k){for(v = 0 ; v < G.numVertexes ; ++v){for(w = 0 ; w < G.numVertexes ; ++W){if((*D)[v][w] > (*D)[v][k] + [k][w]){//如果经过下标为k的路径比原来两点距离小(*D)[v][w] = (*D)[v][k] + (*D)[k][w];//将当前两点间权值设为更小一个(*P)[v][w] = (*P)[v][k];//路径设置为经过下标为k的顶点}}}}
}

求最短路径的显示代码

printf("各顶点间最短路径如下:\n");    for(v=0; v<G.numVertexes; ++v)   {        for(w=v+1; w<G.numVertexes; w++)  {printf("v%d-v%d weight: %d ",v,w,D[v][w]);k=P[v][w];				/* 获得第一个路径顶点下标 */printf(" path: %d",v);	/* 打印源点 */while(k!=w)				/* 如果路径顶点下标不是终点 */{printf(" -> %d",k);	/* 打印路径顶点 */k=P[k][w];			/* 获得下一个路径顶点下标 */}printf(" -> %d\n",w);	/* 打印终点 */}printf("\n");}

拓扑排序

拓扑序：如果图中从v到w有一条有向路径，则v一定排在w之前。满足此条件的顶点序列称为一个拓扑序。

数据结构

typedef struct EdgeNode{       //边表结点int adjvex;  //邻接点域，存储该顶点对应下标int weight;  //用于存储权值，对于非网图可以不需要struct EdgeNode *next;  //链域，指向下一个邻接点
}EdgeNode;typedef struct VertexNode{ //顶点表结点int in;  //顶点入度int data;  //顶点域，存储顶点信息EdgeNode *firstedge;  //边表头指针
}VertexNode , AdjList[MAXVEX];typedef struct{AdjList adjList;int numVertexes , numEdges;  //图中当前的顶点数和边数
}graphAdjList , *GraphAdjList;

// 拓扑排序，若GL无回路，则输出拓扑排序序列并返回1，若有回路返回0。
int TopologicalSort(GraphAdjList GL){EdgeNode *e;int i , k , gettop;int top = 0;       //用于栈指针下标int count = 0;     //用于统计输出顶点的个数int *stack;        //建栈将入度为0的顶点入栈stack = (int *)malloc(GL->numVertexes * sizeof(int));for(i = 0 ; i < GL->adjList[gettop].data ; i++)if(GL->numVertexes.in == 0)  //度数为0的入栈stack[++top] = i;while(top != 0){gettop = stack[top--];  //出栈cout<<GL->adjList[gettop].data<<" -> "<<endl;  //打印出栈顶点count++; //计数器加一for(e = GL->adjList[gettop].firstedge ; e ; e = e->next){ //对此顶点弧表遍历k = e->adjvex;if(!(--GL->adjList[k].in))  //将k号顶点入度减一stack[++top] = k;  //若为0则入栈，便于下次遍历}  }if(count < GL->numVertexes) //count小于顶点数，说明存在环return 0;elsereturn 1;
}

关键路径

这时我们引入AOE和AOV这两个概念。

AOV（Activity On Vertex）：活动在顶点上，边没有权重
AOE（Activity On Edge）：活动在边上，边有权重

其中这两者的区别也显而易见，AOV网是顶点表示活动的网，它只描述活动之间的制约关系，而AOE网是用边表示活动的网，边上的权值表示活动持续的时间。AOE是建立在AOV之上的。

首先，我们引入几个全局变量吧，

int *etv; //事件最早发生时间
int *ltv; //事件最迟发生时间
int *stack2; //用于存储拓扑序列的栈
int top2; //用于stack2的指针

其中stack2用于存储拓扑序列，以便后边关键路径使用。

下面是拓扑排序，多了个weight

int TopologicalSort(GraphAdjList GL){//若GL无回路，则输出拓扑排序序列并返回1EdgeNode *e;int i , k , gettop;int top = 0; //栈指针下标int count = 0; //用于统计输出顶点的个数int *stack;stack = (int *)malloc(GL->numVertexes * sizeof(int));for(i = 0 ; i < GL->numVertexes ; ++i)if(GL->numVertexes.in == 0) //将度数为0的顶点入栈stack[++top] = i;top2 = 0; //初始化    /***/etv = (int *)malloc(GL->numVertexes * sizeof(int));  /***/for(i = 0 ; i < GL->numVertexes ; ++i)   /***/etv[i] = 0; //初始化                   /***/stack2 = (int *)malloc(GL->numVertexes * sizeof(int)); //初始化拓扑序列栈  /***/while(top != 0){gettop = stack[top--];count++; //输出i顶点，并计数stack2[++top2] = gettop; //将弹出的顶点序号压入拓扑序列的栈   /***/for(e = GL->adjList[gettop].firstedge ; e ; e = e->next){k = e->weight;if(!(--GL->adjList[k].in))stack[++top] = k;if((etv[gettop] + e->weight) > etv[k])    /***///求最早时间发生的etv值etv[k] = etv[gettop] + e->weight;     /***/}}if(count < GL-> numVertexes)return 0;elsereturn 1;}

加/***/的表示相比拓扑排序新加入的代码。

关键路径的伪代码

/* 求关键路径,GL为有向网，输出G的各项关键活动 */
void CriticalPath(GraphAdjList GL) 
{    EdgeNode *e;    int i,gettop,k,j;    int ete,lte;  /* 声明活动最早发生时间和最迟发生时间变量 */        TopologicalSort(GL);   /* 求拓扑序列，计算数组etv和stack2的值 */ ltv=(int *)malloc(GL->numVertexes*sizeof(int));/* 事件最早发生时间数组 */   for(i=0; i<GL->numVertexes; i++)        ltv[i]=etv[GL->numVertexes-1];    /* 初始化 */        printf("etv:\t");   for(i=0; i<GL->numVertexes; i++)        printf("%d -> ",etv[i]);    printf("\n"); while(top2!=0)    /* 出栈是求ltv */    {        gettop=stack2[top2--];        for(e = GL->adjList[gettop].firstedge; e; e = e->next)      /* 求各顶点事件的最迟发生时间ltv值 */        {            k=e->adjvex;            if(ltv[k] - e->weight < ltv[gettop])               ltv[gettop] = ltv[k] - e->weight;        }   }    printf("ltv:\t");   for(i=0; i<GL->numVertexes; i++)        printf("%d -> ",ltv[i]);    printf("\n"); for(j=0; j<GL->numVertexes; j++)        /* 求ete,lte和关键活动 */        {            for(e = GL->adjList[j].firstedge; e; e = e->next)            {                k=e->adjvex;                ete = etv[j];        /* 活动最早发生时间 */                lte = ltv[k] - e->weight; /* 活动最迟发生时间 */               if(ete == lte)    /* 两者相等即在关键路径上 */                    printf("<v%d - v%d> length: %d \n",GL->adjList[j].data,GL->adjList[k].data,e->weight);}        }
}

查找

顺序表查找

1、顺序查找（sequential search）是一种最简单的查找方法，一般用于数组。他从顺序表的一端开始依次将每个元素值同给定的值进行比较，若找到则返回该元素所在的下标；否则返回特定值，表示查找失败。时间复杂度O（n)。

int Sequential_Search(int *a , int n , int key){for(int i = 1 ; i <= n ; ++i){if(a[i] == key)return i;}return 0;
}

顺序表查找的优化

因为每次都要判断i<=n，所以设置一个哨兵，并赋予a[0]

int Sequential_Search(int *a , int n , int key){int i;a[0] = key;i = n;while(a[i] != key){i--;}return i;
}

有序表的查找

这里的表就变成了有序表，一个线性表有序时，查找效率一定时提高的。

折半查找

折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找，时间复杂度为logn。

int Binary_Search(int *a , int n , int key){int low , high , mid;low = 1;high = n;while(low <= high){mid = (low + high) / 2;if(key < a[mid])high = mid - 1;else if(key > a[mid])low = mid + 1;else return mid;}return 0;
}

插值查找

插值查找是对于折半查找的优化，他将mid = （low + high）/ 2变为了下面这个式子，

Mid = low + ((key - data[low]) / (data[high] - data[low])) * (high - low)。

int Binary_Search(int *a , int n , int key){int low , high , mid;low = 1;high = n;while(low <= high){mid = low + ((key - a[low]) / (a[high] - a[low])) * (high - low);if(key < a[mid])high = mid - 1;else if(key > a[mid])low = mid + 1;else return mid;}return 0;
}

斐波那契查找

斐波那契搜索(Fibonacci search) ，又称斐波那契查找，是区间中单峰函数的搜索技术。斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。（mid的关系式不同）

F(n)=F(n−1)+F(n−2)(n≥2,n∈N∗)

F[k]-1是待搜索的数组中数组的长度，之所以使F[k]-1为数组的长度目的是满足以下关系式：

F(n)−1=F(n−1)−1+F(n−2)−1(n≥2,n∈N∗)

以实现mid将一个数组分为两个数组

正是上面这样的区间分割想法，使斐波那契数列和数组联系到了一起。这种分割思想亦是斐波那契查找算法的基础。

斐波那契查找算法相对于二分查找和插值查找的基本思路是一致的，其中最重要的区别就是它们的查找点（或称中间值）的确定。斐波那契查找算法的查找点的计算公式如下：

mid=left+F(n−1)−1

/* 斐波那契查找 */
int Fibonacci_Search(int *a,int n,int key)
{int low,high,mid,i,k=0;low=1;						/* 定义最低下标为记录首位 */high=n;						/* 定义最高下标为记录末位 */while(n>F[k]-1)k++;                   //计算n位斐波那契数列的位置for (i=n;i<F[k]-1;i++)a[i]=a[n];            //将不满的数据补全while(low<=high){mid=low+F[k-1]-1;if (key<a[mid]){high=mid-1;		k=k-1;}else if (key>a[mid]){low=mid+1;		k=k-2;}else{if (mid<=n)return mid;		/* 若相等则说明mid即为查找到的位置 */else return n;}}return 0;
}

线性索引查找

稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。如图1-1所示。

图1-1

对于稠密索引这个索引表来说，索引项一定是按照关键字有序的排列。
索引项有序也就意味着，我们要查找关键字时，可以用到折半，插值，裴波纳契等有序查找算大，大大提高了效率。
比如在图1-1中，我们要查找关键字是18的记录。如果直接中右侧的数据表中查找，那么就只能顺序查找，我们需要查找6次才可以查到结果，而如果我们是从左侧的索引表中查找，只需要两次折半查找就可以得到18对应的指针，最终查找到结果。
这就是稠密索引的优点，但是如果数据集非常的大，比如几百万，那也就意味着索引也得同样的数据集长度规模，对与内存有限的计算机来说，可能就是需要反复去访问磁盘，查找性能反而就下降了。

分块索引

稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大，。为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后对每一个块建立一个索引项，从而减少索引项的个数。
分块有序就是把数据集的记录分成了若干块，并且这些块小需要满足两个条件：

1. 块内无序：每一个块内的记录不要求有序。当然你如果能够让块内有序查找来说更理想。不过这就要付出大量时间和空间的代价。因此通常我们不要求块内有序。
2. 块间有序：例如，要求第二块所有记录的关键字均要岛屿第一块中所有记录的关键字，第三块的所有记录的关键字要大于第二块的所有记录的关键字，因为只有块间有序，才有可能在查找时带来效率。

对于分块有序的数据集，将每块对应一个索引项。这种索引方法叫做分块索引。
如图1-2所示，我们定义的分块索引的索引项结构分三个数据项。

• 最大关键码：它存储每一个块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大。
• 存储了块中的记录个数，以便于循环使用。
• 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。

图1-2

在分块索引表中查找，就是分两部分进行：

1. 在分块索引中表汇查找要查关键字的所在的块。由于分块索引表是块间有序的，因此很容易使用折半，插值等算法得到结果。
2. 根据块的首指针找到对应的块。并在快中顺序查找关键码。因为块中是无序的，因此只能顺序查找。

step1 先选取各块中的最大关键字构成一个索引表； 时间复杂度 log2(m)
step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；在已确定的块中用顺序法进行查找。 时间复杂度 n/m

总复杂度 log2(m) + n/m
当 m = 1时，即为顺序查找
当 m = n时，即为索引查找，
否则 时间复杂度介于二者之间

倒排索引

倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted file)。

优缺点：倒排索引的优点是速度快，缺点就是记录不等长，维护比较困难，插入和删除都要做相应的处理。比如删除某个文章，就可能要对所有的单词都进行考察。

二叉排序树

二叉排序树（Binary Sort Tree， BST），也称二叉查找树。
二叉排序树或者是一棵空树，或者是一棵具有下列特性的非空二叉树：
1） 若左子树非空，则左子树上所有结点关键字均小于根结点的关键字值；
2） 若右子树非空，则右子树上所有结点关键字均大于根结点的关键字值；
3） 左、右子树本身也分别是一棵二叉排序树。

由定义可知，二叉排序树是一个递归的数据结构，可以方便的使用递归算法对二叉排序树进行各种运算。
根据二叉树的定义，可得左子树结点值 ＜ 根结点值 ＜ 右子树结点值。
所以，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

二叉排序树的查找

先提供一个二叉树的结构

typedef struct BiTNode{int data;struct BiTNode *lchild , *rchild;
}BiTNode , *BiTree;

查找算法

int SearchBST(BiTree T , int key , BiTree f , BiTree *p){//递归查找排序树中是否存在keyif(!T){  //若查找不成功，则p指向查找路径上访问的最后一个结点并返回false*p = f;return false;}else if(key == T->data){  //若查找成功，则p指向该元素结点*p = T;return true;}else if(key < T->data)return SearchBST(T->lchild , key , T , p);elsereturn SearchBST(T->rchild , key , T , p);
}

二叉排序树的插入

所谓的二叉排序树的插入，其实也就是将关键字放到树中合适的位置罢了

int InsertBST(BiTree *T , int key){BiTree p , s;if(!SearchBST(*T , key , NULL , &p)){ //查找不成功s = (BiTree)malloc(sizeof(BiTree));s->data = key;s->lchild = s->rchild = NULL;if(!p)*T = s;  //插入s为新的根节点else if(key < p->data)p->lchild = s;  //插入s为左孩子elsep->rchild = s;  //插入s为右孩子return true;}elsereturn false;  //树中已有与关键字相同的结点，不再插入
}

二叉排序树的删除

​ 对于二叉树的插入和查找，删除操作要麻烦的多，如果一个删除结点有两个庞大的左右子树，那么对他们的再排序是十分麻烦的事情，但是否能找到一个能代替删除结点的结点呢？答案是肯定的，那就是删除结点的直接前驱和直接后继，也就是中序遍历后删除结点前后的结点。

根据我们对删除结点三种情况的分析：

· 叶子结点

· 仅有左或右子树的结点

· 左右子树都有的结点

我们来看代码，下面这个算法是递归方式对二叉排序树T查找key，查找到时删除

int DeleteBST(BiTree *T , int key){if(!*T) //不存在keyreturn false;else{if(key == (*T)->data)return Delete(T);else if(key < (*T)->data)return DeleteBST(&(*T)->lchild , key);elsereturn DeleteBST(&(*T)->rchild , key);}
}

上面这段代码和前面的二叉排序树查找几乎完全相同，唯一的区别就在于第8行，此时执行的时Delete方法，对当前结点进行删除操作，我们来看Delete的代码

/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
Status Delete(BiTree *p)
{BiTree q,s;if((*p)->rchild==NULL)/* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */{q=*p; *p=(*p)->lchild; free(q);}else if((*p)->lchild==NULL) /* 只需重接它的右子树 */{q=*p; *p=(*p)->rchild; free(q);}else /* 左右子树均不空 */{q=*p; s=(*p)->lchild;while(s->rchild) /* 转左，然后向右到尽头（找待删结点的前驱） */{q=s;s=s->rchild;}(*p)->data=s->data; /*  s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */if(q!=*p)q->rchild=s->lchild; /*  重接q的右子树 */ elseq->lchild=s->lchild; /*  重接q的左子树 */free(s);}return TRUE;
}

平衡二叉树

定义：左子树和右子树高度差

计算：左子树高度 - 右子树高度的值

别名：简称 BF（Balance Factor 而不是 Boy Friend）

一般来说 BF 的绝对值大于 1，,平衡树二叉树就失衡，需要「旋转」纠正

「旋转」纠正只需要纠正「最小不平衡子树」即可

判断「平衡二叉树」的 2 个条件：

• 1. 是「二叉排序树」
• 2. 任何一个节点的左子树或者右子树都是「平衡二叉树」（左右高度差小于等于 1）

/* 二叉树的二叉链表结点结构定义 */
typedef  struct BiTNode	/* 结点结构 */
{int data;	/* 结点数据 */int bf; /*  结点的平衡因子 */ struct BiTNode *lchild, *rchild;	/* 左右孩子指针 */
} BiTNode, *BiTree;

对于右旋操作

/* 对以p为根的二叉排序树作右旋处理， */
/* 处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */
void R_Rotate(BiTree *P)
{ BiTree L;L=(*P)->lchild; /*  L指向P的左子树根结点 */ (*P)->lchild=L->rchild; /*  L的右子树挂接为P的左子树 */ L->rchild=(*P);*P=L; /*  P指向新的根结点 */ 
}

对于左旋操作

/* 对以P为根的二叉排序树作左旋处理， */
/* 处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0  */
void L_Rotate(BiTree *P)
{ BiTree R;R=(*P)->rchild; /*  R指向P的右子树根结点 */ (*P)->rchild=R->lchild; /* R的左子树挂接为P的右子树 */ R->lchild=(*P);*P=R; /*  P指向新的根结点 */ 
}

左平衡旋转

#define LH +1 /*  左高 */ 
#define EH 0  /*  等高 */ 
#define RH -1 /*  右高 */ /*  对以指针T所指结点为根的二叉树作左平衡旋转处理 */
/*  本算法结束时，指针T指向新的根结点 */
void LeftBalance(BiTree *T)
{ BiTree L,Lr;L=(*T)->lchild; /*  L指向T的左子树根结点 */ switch(L->bf){ /*  检查T的左子树的平衡度，并作相应平衡处理 */ case LH: /*  新结点插入在T的左孩子的左子树上，要作单右旋处理 */ (*T)->bf=L->bf=EH;R_Rotate(T);break;case RH: /*  新结点插入在T的左孩子的右子树上，要作双旋处理 */ Lr=L->rchild; /*  Lr指向T的左孩子的右子树根 */ switch(Lr->bf){ /*  修改T及其左孩子的平衡因子 */ case LH: (*T)->bf=RH;L->bf=EH;break;case EH: (*T)->bf=L->bf=EH;break;case RH: (*T)->bf=EH;L->bf=LH;break;}Lr->bf=EH;L_Rotate(&(*T)->lchild); /*  对T的左子树作左旋平衡处理 */ R_Rotate(T); /*  对T作右旋平衡处理 */ }
}

右平衡旋转

/*  对以指针T所指结点为根的二叉树作右平衡旋转处理， */ 
/*  本算法结束时，指针T指向新的根结点 */ 
void RightBalance(BiTree *T)
{ BiTree R,Rl;R=(*T)->rchild; /*  R指向T的右子树根结点 */ switch(R->bf){ /*  检查T的右子树的平衡度，并作相应平衡处理 */ case RH: /*  新结点插入在T的右孩子的右子树上，要作单左旋处理 */ (*T)->bf=R->bf=EH;L_Rotate(T);break;case LH: /*  新结点插入在T的右孩子的左子树上，要作双旋处理 */ Rl=R->lchild; 			/*  Rl指向T的右孩子的左子树根 */ switch(Rl->bf){ 						/*  修改T及其右孩子的平衡因子 */ case RH: (*T)->bf=LH;R->bf=EH;break;case EH: (*T)->bf=R->bf=EH;break;case LH: (*T)->bf=EH;R->bf=RH;break;}Rl->bf=EH;R_Rotate(&(*T)->rchild); /*  对T的右子树作右旋平衡处理 */ L_Rotate(T); /*  对T作左旋平衡处理 */ }
}

主函数

/*  若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */ 
/*  数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */ 
/*  失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。 */
Status InsertAVL(BiTree *T,int e,Status *taller)
{  if(!*T){ /*  插入新结点，树“长高”，置taller为TRUE */ *T=(BiTree)malloc(sizeof(BiTNode));(*T)->data=e; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=EH;*taller=TRUE;}else{if (e==(*T)->data){ /*  树中已存在和e有相同关键字的结点则不再插入 */ *taller=FALSE; return FALSE;}if (e<(*T)->data){ /*  应继续在T的左子树中进行搜索 */ if(!InsertAVL(&(*T)->lchild,e,taller)) /*  未插入 */ return FALSE;if(*taller) /*   已插入到T的左子树中且左子树“长高” */ switch((*T)->bf) /*  检查T的平衡度 */ {case LH: /*  原本左子树比右子树高，需要作左平衡处理 */ LeftBalance(T);	*taller=FALSE; break;case EH: /*  原本左、右子树等高，现因左子树增高而使树增高 */ (*T)->bf=LH; *taller=TRUE; break;case RH: /*  原本右子树比左子树高，现左、右子树等高 */  (*T)->bf=EH; *taller=FALSE; break;}}else{ /*  应继续在T的右子树中进行搜索 */ if(!InsertAVL(&(*T)->rchild,e,taller)) /*  未插入 */ return FALSE;if(*taller) /*  已插入到T的右子树且右子树“长高” */ switch((*T)->bf) /*  检查T的平衡度 */ {case LH: /*  原本左子树比右子树高，现左、右子树等高 */ (*T)->bf=EH; *taller=FALSE;	break;case EH: /*  原本左、右子树等高，现因右子树增高而使树增高  */(*T)->bf=RH; *taller=TRUE; break;case RH: /*  原本右子树比左子树高，需要作右平衡处理 */ RightBalance(T); *taller=FALSE; break;}}}return TRUE;
}

多路查找树（B树）

2-3树

具有如下特点

• 2-3 树的所有叶子节点都在同一层(只要是 B 树都满足这个条件)
• 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。
• 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点。
• 2-3 树是由二节点和三节点构成的树。

插入规则

1. 2-3 树的所有叶子节点都在同一层(只要是 B 树都满足这个条件)。
2. 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。
3. 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点。
4. 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面 3 个条件。
5. 对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则。

B树

1. B-tree 树即 B 树，B 即 Balanced，平衡的意思。有人把 B-tree 翻译成 B-树，容易让人产生误解。会以为 B-树是一种树，而 B 树又是另一种树。实际上，B-tree 就是指的 B 树。
2. 前面已经介绍了 2-3 树和 2-3-4 树，他们就是 B 树(英语：B-tree 也写成 B-树)，这里我们再做一个说明，我们在学习 Mysql 时，经常听到说某种类型的索引是基于 B 树或者 B+树的。

B+树

B+ 树是 B 树的变体，也是一种多路搜索树。

对上图的说明

1. B+树的搜索与 B 树也基本相同，区别是 B+树只有达到叶子结点才命中（B 树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找
2. 所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的。
3. 不可能在非叶子结点命中
4. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
5. 更适合文件索引系统
6. B 树和 B+树各有自己的应用场景，不能说 B+树完全比 B 树好，反之亦然。

B*树

1. B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为 2/3，而 B+树的块的最低使用率为的1/2。
2. 从第 1 个特点我们可以看出，B*树分配新结点的概率比 B+树要低，空间使用率更高

散列表查找（哈希表）

散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”。
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

• key：键或者关键字。
• 散列函数（或“Hash 函数”“哈希函数”）：把key值转化为数组下标的映射方法。
• 散列函数计算得到的值就叫作散列值（或“Hash 值”“哈希值”）

散列函数设计的基本要求：

• 散列函数计算得到的散列值是一个非负整数；
• 如果 key1 = key2，那 hash(key1) == hash(key2)；
• 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。（往往这个条件很难办到，key不同可能出现相同的散列值，于是出现散列冲突）

散列函数的构造方法

基本要求

1. 计算简单
2. 散列地址分布均匀

1. 直接定址法

取某个线性函数值为散列地址

这样的散列函数有点时简单，均匀，也不会产生冲突，但问题时需要事先知道关键字的分布情况，适合查找表小且连续的情况。

2. 数字分析法

抽取出部分数字并进行反转，右环位移，左环位移，叠加，以提供一个散列函数，能够将关键字分配到散列表的各位置

适合关键字位数较多的情况，如果事先知道关键字的分布且关键字的若干分布比较均匀，可以考虑这个方法

3. 平方取中法

这个方法计算简单，假设关键字是1234，那么它的平法就是1522756，再抽取中间的三位就是227，用做散列地址。再比如关键字是4321，那么它的平方是18671041，抽取中间三位就可以是671，也可以是710，用作散列地址。

4. 除留余数法

这种方法不仅可以对关键字直接取模，也可以在折叠平方后取模，当然这就对于关键字要求很高，选不好就会出现同义词，比如对2取模。

根据前辈的经验，若散列表长度为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。

5. 随机数法

选择一个随机数，取关键字的随机函数为它的散列地址。

处理散列冲突的方法

既然冲突很难避免，那该怎么办呢？

试想一下，当你观望很久很久，终于看上一套房子准备买了，人家告诉你，这房子已经卖出去了。

那就找别的房子呗，这就是其中的一种方法----开放地址法

开放地址法

1. 线性探测法

开放地址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入

hash =( hash(key) + F(i)) % mod(表长)（F(i) = 1,2,3~~~m-1)

2. 平方探测法

所谓的平方探测法，就是在上面的基本公式中，以F（i) = 1²,-1²,2²,-2²的形式后移。也就是说，如果发生冲突的话，他是在当前下标(即key % tableSize)的基础上加上F(i)。

3. 随机探测法

就是把F(i)换成随机数。

再散列函数法

这里的在散列函数的基础是有多个散列函数，当散列地址冲突的适合，就可以换一个散列函数去计算。

链地址法

所谓的分离链接法，就是采用数组+链表的形式,定义一个数组，并且每一个下标对应的都是一个链表的链表头。如果发生冲突的时候，并且这个新元素已经在哈希表中对应的链表中出现过了，那么就不执行任何的操作，反之，如果没有出现过，那么就将新的关键字插入到对应地址的链表头或者链表尾。如下图所示:

所以在采用分离链接法的时候，我们需要做的准备工作:
1、定义一个节点结构体Node，用于构建一个链表
2、定义一个结构体，表示哈希表HashTable，其中，这个结构体的成员变量主要有一个Node类型指针的数组，以及一个整形变量，表示这个哈希表的大小。

对应的代码

#include<stdio.h>
#include<stdlib.h>
typedef struct NODE *Node;
typedef Node * List;
typedef struct HASHTABLE HashTable;struct NODE{int data;Node next;
};
struct HASHTABLE{int size;//表示哈希表的大小List arr;
};
//初始化哈希表
void init(HashTable &H,int size){H.size = size;//初始化哈希表的大小H.arr = (List)malloc(sizeof(Node) * size);//给哈希表中的指针数组分配空间if(H.arr == NULL){printf("指针数组分配空间失败!!!\n");exit(0);}int i;for(i = 0; i < size; i++){H.arr[i] = (Node)malloc(sizeof(struct NODE));//给每一个节点分配空间if(H.arr[i] == NULL){printf("节点分配失败!!!\n");exit(0);}//每一个下标对应一条链表，并且这条链表是一个带有假节点的链表H.arr[i]->next = NULL;}
}
int hash(HashTable &H,int key){return key % H.size;//利用除留取余法，从而获取key在哈希表中的地址
}
/*
在哈希表中查找关键字key:
1、首先需要利用除留取余法获得key在哈希表中所处的链表位置
2、找到所处的链表之后，遍历链表，判断是否能找到值尾key的节点，如果能找到，
就将这个节点返回，否则返回null
*/
Node find(HashTable &H,int key){int pos;Node L,cur;pos = hash(H,key);//获取key在哈希表中的位置L = H.arr[pos];//获取key所在地址的链表cur = L->next;//由于L是一个带有假节点的链表，那么L->next才是链表真正的头结点while(cur != NULL && cur->data != key){//如果当前的节点不为空，并且当前节点的值不是要找的关键字，那么继续遍历链表cur = cur->next;}return cur;
}
/*
在哈希表中插入关键字
判断关键字是否已经存在哈希表中了，如果存在了，那么不进行任何操作，否则就将其
插入到对应的链表的链表头处
*/
void insert(HashTable &H,int key){Node L,p;p = find(H,key);if(p == NULL){//如果p为空，说明哈希表中并不存在这个这个关键字的节点，那么就将这个新节点插入到对应的链表头的位置L = H.arr[key % H.size];//获取关键字所处的链表p = (Node)malloc(sizeof(struct NODE));p->next = L->next;p->data = key;L->next = p;printf("插入成功!!!\n");}else{printf("关键字%d已经在哈希表中存在，所处的链表下标为%d\n",key,key % H.size);}
}
void deleteElement(HashTable &H,int key){Node L,p,tmp;p = find(H,key);if(p != NULL){//如果p不为空，说明哈希表中不存在这个这个关键字的节点L = H.arr[key % H.size];//获取关键字所处的链表p = L;while(p->next != NULL && p->next->data != key){//找到删除节点的前一个节点p = p->next;}tmp = p->next;//找到了删除的节点p->next = p->next->next;free(tmp);//释放待删除的节点printf("删除成功!!!\n");}else{printf("关键字%d在哈希表中不存在\n",key);}
}
void display(HashTable &H){int i;Node L;for(i = 0; i < H.size; i++){L = H.arr[i]->next;if(L == NULL){printf("NULL\n");}else{while(L != NULL){printf("%5d",L->data);L = L->next;}printf("\n");}}
}
int main(){HashTable h;int n,i,key;printf("请输入哈希表的大小:");scanf("%d",&n);init(h,n);printf("请输入元素的个数:");scanf("%d",&n);printf("请输入各个关键字:");for(i = 0; i < n; i++){scanf("%d",&key);insert(h,key);}while(1){printf("请输入选项: 1、插入 2、查找 3、删除 4、遍历哈希表 0、退出\n");scanf("%d",&n);switch(n){case 1:printf("请输入待插入数字:");scanf("%d",&key);insert(h,key);break;case 2:printf("请输入待查找数字:");scanf("%d",&key);if(find(h,key)){printf("找到了，所处的链表下标为%d\n",key % h.size);}else{printf("哈希表中无法找到%d\n",key);}break;case 3:printf("请输入待删除数字:");scanf("%d",&key);deleteElement(h,key);break;case 4:display(h);break;case 0:printf("退出系统");exit(0);}}return 0;
}

公共溢出区法

在查找时，对给定值通过散列函数计算出散列地址后，先于基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出区去进行顺序查找。如果相对于基本表而言，有冲突数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

散列表查找的实现

首先需要定义一个散列表的结构以及一些相关的常数。其中HashTable就是散列表结构。结构中的elem为一个动态数组。

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 /* 定义散列表长为数组的长度 */
#define NULLKEY -32768 typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef struct
{int *elem; /* 数据元素存储基址，动态分配数组 */int count; /*  当前数据元素个数 */
}HashTable;int m=0; /* 散列表表长，全局变量 */

对于散列表进行初始化

/* 初始化散列表 */
Status InitHashTable(HashTable *H)
{int i;m=HASHSIZE;H->count=m;H->elem=(int *)malloc(m*sizeof(int));for(i=0;i<m;i++)H->elem[i]=NULLKEY; return OK;
}

为了插入时计算地址，我们需要定义散列函数，散列函数可以根据不同的情况改变算法

/* 散列函数 */
int Hash(int key)
{return key % m; /* 除留余数法 */
}

初始化完成后，可以对散列表进行插入操作。

/* 插入关键字进散列表 */
void InsertHash(HashTable *H,int key)
{int addr = Hash(key); /* 求散列地址 */while (H->elem[addr] != NULLKEY) /* 如果不为空，则冲突 */{addr = (addr+1) % m; /* 开放定址法的线性探测 */}H->elem[addr] = key; /* 直到有空位后插入关键字 */
}

代码中插入关键字时，首先算出散列地址，如果当前地址不为空关键字，则说明有冲突。此时我们应用开放地址法的线性探测进行重新寻址，此处也可以用其他方法。

散列表存在后，我们需要时就可以通过散列表查找需要的记录

/* 散列表查找关键字 */
Status SearchHash(HashTable H,int key,int *addr)
{*addr = Hash(key);  /* 求散列地址 */while(H.elem[*addr] != key) /* 如果不为空，则冲突 */{*addr = (*addr+1) % m; /* 开放定址法的线性探测 */if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) /* 如果循环回到原点 */return UNSUCCESS;	/* 则说明关键字不存在 */}return SUCCESS;
}

排序

冒泡排序

****冒泡排序的原理是：从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。****

以从小到大排序为例，第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。

hvoid BubbleSort0(SqList *L){int i , j;for(i = 1 ; i < L->length ; i++){//重复的次数for(j = L->length - 1 ; j <= i ; j--){if(L->r[j] > L->r[j + 1])swap(L , j , j + 1);}}
}

但是这样效率还是不高，算法每次比较的次数都不变，这就会一直增加无效的比较次数，毕竟一部分以及排好序了，再比较就不礼貌了。

void BubbleSort2(SqList *L){int flag = true;for(int i = 1 ; i < L->length && flag ; i++){//若未进行数据交换则推出循环falg = true;for(int j = l->length - 1 ; j >= i ; j--){if(L->r[j] > L->r[j + 1]){swap(L , j , j + 1);flag = false;}}}
}

选择排序

选择排序就是通过n-i次关键字间的比较，从n-i+1个记录中选择出最小的关键字并和第一个数交换位置

void SelectSort(SqList *L){int i , j , min;for(i = 1 ; i < L->length ; i++){min = i;for(j = i + 1 ; j <= L->length ; j++){if(L->r[min] > L->r[j])min = j;}if(i != min){swap(L , i , min);}}
}

插入排序

直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表。

void InsertSort(SqList *L){inti , j;for(i = 2 ; i <= L->length ; i++){if(L->r[i] < L->r[i - 1]){L->r[0] = L->[i];//如果i比i-1小，则i设为哨兵，也就是放在0位置for(j = i - 1 ; L->r[j] > L->r[0] ; j--){//移动的数要大于哨兵L->r[j + 1] = L->r[j];}L->r[j + 1] = L->r[0];}}
}

希尔排序

希尔排序，先将待排序列进行预排序，使待排序列接近有序，然后再对该序列进行一次插入排序，此时插入排序的时间复杂度为O(N)

void ShellSort(SqList *L){int i , j , k = 0;int increment = L->length;do{increment = increment / 3 + 1;for(i = increment + 1 ; i <= L->length ; i++){if(L->r[i] < L->r[i - increment]){L->r[0] = L->r[i];for(j = i - increment ; j > 0 && L->r[0] < L->r[j] ; j -= increment){L->[j + increment] = L->r[0];}L->r[j + increment] = L->r[0];}}}while(increment > 1)
}

堆排序

1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端

2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1

3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

注意:升序用大根堆，降序就用小根堆(默认为升序)

/* 已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义， */
/* 本函数调整L->r[s]的关键字,使L->r[s..m]成为一个大顶堆 */
void HeapAdjust(SqList *L,int s,int m)
{ int temp,j;temp=L->r[s];for(j=2*s;j<=m;j*=2) /* 沿关键字较大的孩子结点向下筛选 */{if(j<m && L->r[j]<L->r[j+1])++j; /* j为关键字中较大的记录的下标 */if(temp>=L->r[j])break; /* rc应插入在位置s上 */L->r[s]=L->r[j];s=j;}L->r[s]=temp; /* 插入 */
}/*  对顺序表L进行堆排序 */
void HeapSort(SqList *L)
{int i;for(i=L->length/2;i>0;i--) /*  把L中的r构建成一个大顶堆 */HeapAdjust(L,i,L->length);for(i=L->length;i>1;i--){ swap(L,1,i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */HeapAdjust(L,1,i-1); /*  将L->r[1..i-1]重新调整为大顶堆 */}
}

归并排序

归并排序(Merge Sort)是建立在归并操作上的一种既有效又稳定的排序算法，该算法是采用

分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的

序列。即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二

路归并。

分离： 将已有数列不断分离成两段长度基本相同（当已有数列长度是奇数时，则一半长一半短），直到分离成长度为 1 的 n 个数列（其实就是 n 个数）。

合并： 将数列两两合并，每次合并时进行比较和排序，直到完成排序。

/* 归并排序********************************** *//* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[],int TR[],int i,int m,int n)
{int j,k,l;for(j=m+1,k=i;i<=m && j<=n;k++)	/* 将SR中记录由小到大地并入TR */{if (SR[i]<SR[j])TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m){for(l=0;l<=m-i;l++)TR[k+l]=SR[i+l];		/* 将剩余的SR[i..m]复制到TR */}if(j<=n){for(l=0;l<=n-j;l++)TR[k+l]=SR[j+l];		/* 将剩余的SR[j..n]复制到TR */}
}

/* 递归法 */
/* 将SR[s..t]归并排序为TR1[s..t] */
void MSort(int SR[],int TR1[],int s, int t)
{int m;int TR2[MAXSIZE+1];if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;				/* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */MSort(SR,TR2,s,m);		/* 递归地将SR[s..m]归并为有序的TR2[s..m] */MSort(SR,TR2,m+1,t);	/* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */Merge(TR2,TR1,s,m,t);	/* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */}
}/* 对顺序表L作归并排序 */
void MergeSort(SqList *L)
{ MSort(L->r,L->r,1,L->length);
}

非递归法

/* 非递归法 */
/* 将SR[]中相邻长度为s的子序列两两归并到TR[] */
void MergePass(int SR[],int TR[],int s,int n)
{int i=1;int j;while(i <= n-2*s+1){/* 两两归并 */Merge(SR,TR,i,i+s-1,i+2*s-1);i=i+2*s;        }if(i<n-s+1) /* 归并最后两个序列 */Merge(SR,TR,i,i+s-1,n);else /* 若最后只剩下单个子序列 */for(j =i;j <= n;j++)TR[j] = SR[j];
}/* 对顺序表L作归并非递归排序 */
void MergeSort2(SqList *L)
{int* TR=(int*)malloc(L->length * sizeof(int));/* 申请额外空间 */int k=1;while(k<L->length){MergePass(L->r,TR,k,L->length);k=2*k;/* 子序列长度加倍 */MergePass(TR,L->r,k,L->length);k=2*k;/* 子序列长度加倍 */       }
}

快速排序

快速排序的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行继续排序，以达到整个序列有序的目的。

/* 快速排序******************************** *//* 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
int Partition(SqList *L,int low,int high)
{ int pivotkey;pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */while(low<high) /*  从表的两端交替地向中间扫描 */{ while(low<high&&L->r[high]>=pivotkey)high--;swap(L,low,high);/* 将比枢轴记录小的记录交换到低端 */while(low<high&&L->r[low]<=pivotkey)low++;swap(L,low,high);/* 将比枢轴记录大的记录交换到高端 */}return low; /* 返回枢轴所在位置 */
}/* 对顺序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{ int pivot;if(low<high){pivot=Partition(L,low,high); /*  将L->r[low..high]一分为二，算出枢轴值pivot */QSort(L,low,pivot-1);		/*  对低子表递归排序 */QSort(L,pivot+1,high);		/*  对高子表递归排序 */}
}/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{ QSort(L,1,L->length);
}

对于快速排序的优化，那就是选取枢轴的优化

1. 三数取中，就是取第一个和中间的和最后一个，然后取中间的数。

/* 快速排序优化算法 */
int Partition1(SqList *L,int low,int high)
{ int pivotkey;int m = low + (high - low) / 2; /* 计算数组中间的元素的下标 */  if (L->r[low]>L->r[high])			swap(L,low,high);	/* 交换左端与右端数据，保证左端较小 */if (L->r[m]>L->r[high])swap(L,high,m);		/* 交换中间与右端数据，保证中间较小 */if (L->r[m]>L->r[low])swap(L,m,low);		/* 交换中间与左端数据，保证左端较小 */pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */L->r[0]=pivotkey;  /* 将枢轴关键字备份到L->r[0] */while(low<high) /*  从表的两端交替地向中间扫描 */{ while(low<high&&L->r[high]>=pivotkey)high--;L->r[low]=L->r[high];while(low<high&&L->r[low]<=pivotkey)low++;L->r[high]=L->r[low];}L->r[low]=L->r[0];return low; /* 返回枢轴所在位置 */
}void QSort1(SqList *L,int low,int high)
{ int pivot;if((high-low)>MAX_LENGTH_INSERT_SORT){pivot=Partition1(L,low,high); /*  将L->r[low..high]一分为二，算出枢轴值pivot */QSort1(L,low,pivot-1);		/*  对低子表递归排序 */QSort1(L,pivot+1,high);		/*  对高子表递归排序 */}elseInsertSort(L);
}/* 对顺序表L作快速排序 */
void QuickSort1(SqList *L)
{ QSort1(L,1,L->length);
}/* 尾递归 */
void QSort2(SqList *L,int low,int high)
{ int pivot;if((high-low)>MAX_LENGTH_INSERT_SORT){while(low<high){pivot=Partition1(L,low,high); /*  将L->r[low..high]一分为二，算出枢轴值pivot */QSort2(L,low,pivot-1);		/*  对低子表递归排序 */low=pivot+1;	/* 尾递归 */}}elseInsertSort(L);
}/* 对顺序表L作快速排序(尾递归) */
void QuickSort2(SqList *L)
{ QSort2(L,1,L->length);
}