写在前面：这是我在学习王道计算机考研课程——“数据结构”的过程中，对照着视频，以及加入了个人思考，跟着敲了一遍代码，同时也为日后考研复习材料提供方便。 代码多为伪代码，而排序部分是当时初次学习”大话数据结构”之后，以及参考B站up主及各博客大佬，建立的排序专题，全部由代码实现，可以直接粘贴运行。 在此特推荐B站up主：正月点灯笼 的堆排序视频（以下为链接），真的讲的超级好，当时对堆排序的代码难以理解，看了大佬的视频，如醍醐灌顶，非常感谢！ https://www.bilibili.com/video/BV1Eb41147dK/?spm_id_from=333.337.search-card.all.click&vd_source=b64addc069fb830079345fe5d6f118f9

线性表#

&：需要带出#

#include <stdio.h>
void test1(int x)
{
	x=1024;
	printf("test1函数内部 x=%d\n",x);
}			

void test2(int & x)
{
	x=1024;
	printf("test2函数内部 x=%d\n",x);
}	

int main() 
{
	int x=1;
	printf("调用test前 x=%d\n",x);
	test1(x);
	printf("调用test1后 x=%d\n",x);
	test2(x);
	printf("调用test2后 x=%d\n",x);
	return 0; 
}

顺序表的实现- -静态分配#

#include <stdio.h>
#define MaxSize 10    //定义最大长度
typedef struct{
	int data[MaxSize];   //用静态的数组存放数据元素
	int length;        //顺序表的当前长度 
}SqList;

//基本操作 ---初始化一个顺序表
void InitList(SqList &L){
	
//	for(int i = 0; i < MaxSize; i++){
//		L.data[i] = 0;      //将所有数据元素置为0:清空脏数据 ,这一步可省略 
//	}                                       
	
	L.length = 0;          //顺序表初始长度为0 
} 

int main(){
	SqList L;          //声明一个顺序表 
	InitList(L);       //初始化顺序表 
	
	//未完待续...
	
	return 0; 
}

顺序表的实现—动态分配#

#include <stdio.h>
#include <stdlib.h> 

#define InitSize 10    //默认的最大长度 

typedef struct{    
	int *data;        //指示动态分配数组的指针 
	int MaxSize;      //顺序表的最大容量 
	int length;      //顺序表的当前长度 
}SeqList;

void InitList(SeqList &L){
  //用malloc函数申请一片连续的存储空间
 L.data = (int *)malloc(InitSize*sizeof(int));
 L.MaxSize = InitSize; 
 L.length = 0;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
	int *p = L.data;     //辅助指针p 
	L.data = (int*)malloc(sizeof(int)*(L.MaxSize + len));
	for(int i = 0; i < L.length; i++){
		L.data[i] = p[i];    //将数据复制到新区域 
	}
	L.MaxSize = L.MaxSize + len;    //顺序表最大长度增加len
	free(p);                     //释放原来的内存空间 
} 

int main()
{
	SeqList L;    //声明一个顺序表
	InitList(L);   //初始化顺序表
	//...往顺序表中随便插入几个元素...
	IncreaseSize(L,5);
	return 0;
}

顺序表的基本操作——插入#

#include <stdio.h>

#define MaxSize 10   //定义最大长度
typedef struct{
	int data[MaxSize];  //用静态的数组存放数据元素
	int length;         //顺序表的当前长度 
}SqList;                //顺序表的类型定义


bool ListInsert(SqList &L, int i, int e){
	if(i < 1||i > L.length + 1){
		return false;
	}
	if(L.length >= MaxSize){
		return false;
	}
	
	for(int j = L.length; j >= i; j--){    //将第i个元素及之后的元素后移   注意：从最后面开始移动 为前面空出位置 
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;         //在位置i处放入e，注意i是位序 
	L.length ++;               //长度加1
	
	return true;
}

int main(){
	SqList L;    //声明一个顺序表
	InitList(L);  //初始化顺序表
	//..此处省略一些代码，插入几个元素
	ListInsert(L,3,3);
	return 0; 
}       

顺序表的基本操作——删除#

#include <stdio.h>

bool ListDelete(SqList &L, int i, int &e){
	if(i < 1||i > L.length){         //健壮性 
		return false;
	}
	e = L.data[i - 1];      //将被删除的元素赋值给e
	for(int j = i; j < L.length; j++){
		L.data[j - 1] = L.data[j];    //将第i个位置后的元素前移  注意：先移动前面的元素，给后面的元素腾出前移的空间 
	} 
	L.length--;       //线性表长度减1
	return true; 
} 

int main(){
	SqList L;  //声明一个顺序表
	InitList(L);   //初始化顺序表
	//..此处省略一些代码，插入几个元素
	int e = -1;    //用变量e把删除的元素带回来
	
	if(ListDelete(SqList L, 3, e)){
		printf("已删除第3个元素，删除元素的值为%d\n", e);
	}
	else{
		printf("位序i不合法，删除失败\n");
	}
	return 0;	
}

顺序表的基本操作——查找#

#include <stdio.h>
#define MaxSize 10
#define InitSize 10 

typedef struct{          //静态分配 
	ElemType data[MaxSize];
	int length;
}SqList; 

typedef struct{          //动态分配 
	ElemType *data;
	int MaxSize;
	int length;
}SqList; 


//二者同样可用如下代码                  

// ***按位查找*** 
ElemType GetElem(SqList L, int i){
	//健壮性可以判断i的值是否合法 
	return L.data[i - 1];
}

 
 
//***按值查找*** 
int LocateElem(SqList L, ElemType e){
	for(i = 0; i < L.length; i++){
		if(L.data[i] == e){
			return i + 1;    //数组下标为i的元素值为e，返回其位序i+1 
		}
	}
	return 0;                //查找失败，返回0 
}

单链表的定义#

#include <stdio.h>

typedef struct LNode{            //结点 
	ElemType data;              //数据域 
	struct LNode *next;         //指针域 
}LNode, *LinkList;      //***注意：声明一个指向单链表第一个结点的指针可以用 LNode *L, 也可用 LinkList L,用后者代码可读性更强

//强调这是一个结点：用 LNode*
//强调这是一个单链表：用 LinkList 

LNode *p = (LNode*)malloc(sizeof(LNode));    //增加一个新的结点：在内存中申请一个结点所需空间，并用指针p指向这个结点 


//不带头结点的单链表
	//初始化一个空的单链表
bool InitList(LinkList &L){
	L = NULL;      //空表，暂时还没有任何结点 (防止脏数据) 
	return true; 
} 


//带头结点的单链表
	//初始化
bool InitList(LinkList &L){
	L = (LNode*)malloc(sizeof(LNode));   //分配一个头结点
	if(L == NULL){           //内存不足，分配失败 
		return false;
	} 
	L->next = NULL;          //头结点之后暂时还没有结点 
	return true; 
} 

//判断单链表是否为空（不带头结点） 
bool Empty(LinkList L){
	return(L == NULL);
} 
//判断单链表是否为空（带头结点） 
bool Empty(LinkList L){
	return((L->next) == NULL);
} 


void test(){
	LinkList L;    //声明一个指向单链表的指针
	//初始化一个空表
	InitList(L);
	//...后续代码... 
}

单链表的插入删除#

#include <stdio.h>

typedef struct LNode{      //前提准备条件 
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;

//1.按位序插入（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e) {
	if(i < 1){         //判断插入位置的合法性 
		return false;
	}
	LNode *p;         //指针p指向当前扫描到的结点（定义一个指向LNode的指针） 
	int j = 0;        //当前p指向的是第几个结点
	p = L;           //L指向头结点，头结点是第0个结点（不存数据）  注意：此时p和L都指向头结点 
	while (p != NULL && j < i - 1) {        //循环找到第i-1个结点 
		p = p->next;
		j++;
	}
	if(p == NULL){  //i值不合法 （此种情况是针对已经超出了末尾元素） 
		return false;
	}

	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;     //将结点s链接到p之后
	
	return true; 
}

//2.按位序插入（不带头结点）
bool ListInsert(LinkList &L, int i, ElemType e) {
	if(i < 1){
		return false;
	}
	if(i == 1){    //插入第一个结点的操作与其他结点操作不同 ，单独拿出来 
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;     //头指针指向新结点
		return true; 
	} 
	LNode *p;         //指针p指向当前扫描到的结点（定义一个指向LNode的指针） 
	int j = 1;        //当前p指向的是第几个结点
	p = L;           //p指向第一个结点，（注意：不是头结点） 
	while (p != NULL && j < i - 1) {        //循环找到第i-1个结点 
		p = p->next;
		j++;
	}
	if(p == NULL){  //i值不合法 
		return false;
	}

	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;     //将结点s链接到p之后
	return true; 
}


//3.后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e){
	if(p == NULL){
		return false;
	}
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL){   //内存分配失败 
	 	return false; 
	}
	s->data = e;
	s->next = p->next;
	p->next = s;     //将结点s链接到p之后
	return true; 
}


//4.指定结点的前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){
	if(p == NULL){
		return false;
	}
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL){   //内存分配失败 
	 	return false; 
	}
	s->next = p->next;
	p->next = s;       //新节点s连接到p之后 
	s->data = p->data; //将p中元素复制到s中 
	p->data = e;       //p中元素覆盖为e        （此招偷梁换柱，时间复杂度为O（1）） 
	return true; 
}

//5.按位删除（带头结点）
bool ListDelete(LinkList &L, int i, ElemType &e) {
	if(i < 1){
		return false;
	}
	LNode *p;         //指针p指向当前扫描到的结点
	int j = 0;        //当前p指向的是第几个结点
	p = L;           //L指向头结点，头结点是第0个结点（不存数据）  注意：此时p和L都指向头结点 
	while (p != NULL && j < i - 1) {        //循环找到第i-1个结点 
		p = p->next;
		j++;
	}
	if(p == NULL){  //i值不合法 
		return false;
	}
	if(p->next == NULL){ //第i-1个结点之后已无其他结点 
		return false; 
	} 

	LNode *q = p->next;    //令q指向被删除结点 
	e = q->data;          //用e返回元素的值 
	p->next = q->next;    //将*q结点从链中"断开" 
	free(q);             //释放结点的存储空间 
	return true; 
}

//6.删除指定节点p
bool DeleteNode(LNode *p){
	if( p == NULL){
		return false;
	}
	LNode *q = p->next;    //令q指向被删除结点 
	p->data = p->next->data;     //和后继结点交换数据域 
	p->next = q->next;    //将*q结点从链中"断开" 
	free(q);             //释放后继结点的存储空间        （把它后面那个结点与之交换，再删除后面那个结点） 
	return true; 
} 

单链表的查找#

#include <stdio.h>

/**
 * 按位查找，返回第i个元素（带头结点）
 */
 
LNode * GetElem(LinkList L, int i){
	if(i < 0){
		return NULL;   //注意：返回的是空指针，查找失败 
	}
	LNode *p;      //指针p指向LNode(当前扫描到的结点) 
	int j = 0;     //当前p指向的是第几个结点 
	p = L;         //L和p均指向头结点
	while(p != NULL && j < i){      //循环找到第i个结点 
	    p = p->next;
	    j++;
	}
	return p;  //这里当i=0的时候，返回的也是p指向的结点即头结点 
//当i已经超出表尾元素，p最终仍然指向NULL，返回的是空指针，即查找失败 
}




/**
 * 按值查找，找到数据域==e的结点 
 */

LNode * LocateElem(LinkList L, ElemType e){
	LNode *p = L->next;  //从第一个结点开始遍历查找数据域为e的结点
	while(p != NULL && p->data != e){
		p = p->next;
	} 
	return p;         //找到后返回该结点指针，否则返回NULL，这里当到最后也没找到数据域为e的结点时，p指针指向NULL 
}



/**
 * 求表长 
 */
int Length(LinkList L){
	int len = 0;   //统计表长
	LNode *p = L;
	while(p->next != NULL){
		p = p->next;
		len++;
	} 
	return len;
}

单链表建立（头插和尾插）#

#include <stdio.h>

/**
 * 尾插法建立单链表 
 */
 
LinkList List_TailInsert(LinkList &L){
	int x;
	L = (LinkList)malloc(sizeof(LNode));   //建立头结点
	LNode *s,*r = L;    //r为表尾指针
	scanf("%d", &x);
	while(x != 9999){           //输入9999表示结束 
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;      //尾结点指针置空
	return L; 
} 


/**
 * 头插法建立单链表 
 */
 
LinkList List_HeadInsert(LinkList &L){
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));   //建立头结点
	L->next = NULL;
	scanf("%d", &x);
	while(x != 9999){           //输入9999表示结束 
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;           //将新结点插入表中,L为头指针 
		scanf("%d", &x);
	}
	return L; 
} 

双链表#

#include <stdio.h>
#include <stdlib.h>

/**
 *双链表定义 
 */ 
typedef struct DNode{
	ElemType data;
	struct DNode *prior, *next;
}DNode, *DLinkList; 


/**
 *双链表初始化（带头结点） 
 */ 
bool InitDLinkList(DLinkList &L){
	L = (DNode * )malloc(sizeof(DNode));
	if(L == NULL){
		return false;
	}
	L->prior = NULL;
	L->next = NULL;
	return true;
}


/**
 *判断双链表是否为空（带头结点） 
 */ 
bool Empty(DLinkList L){
	if(L->next == NULL){
		return true;
	}
	else{
		return false;
	}
} 



/**
 *双链表的插入（带头结点） 
 */ 

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
	if(p == NULL || s == NULL){   //非法参数 
		return false; 
	}
	s->next = p->next;    //将结点s插入到结点p之后
	if(p->next != NULL){     //如果p结点有后继结点 
		p->next->prior = s;	
	}
	s->prior = p;
	p->next = s; 
}


/**
 *双链表的删除（带头结点） 
 */ 
 
//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
	if( p == NULL){
		return false;
	}
	DNode *q = p->next;     //找到p的后继节点q
	if(q == NULL){         //p没有后继 
		return false;
	}
	p->next = q->next; 
	if(q->next != NULL){     //q结点不是最后一个结点 
		q->next->prior = p; 
} 
	free(q);
	return true;
} 



/**
 *双链表的销毁 
 */

void DestroyList(DLinkList &L){
	while(L->next != NULL){
		DeleteNextDNode(L);
	}
	free(L);       //释放头结点
	L = NULL;      //头指针指向NULL 
}



/**
 *双链表的遍历 
 */

//后向遍历 
	while(p != NULL){
		//对结点p作相应处理，如打印
		p = p->next; 
	}
	
//前向遍历 
	while(p->prior != NULL){
		//对结点p作相应处理，如打印
		p = p->prior; 
	}

 
 
 
//测试 
void testDLinkList(){
	DLinkList L;
	InitDLinkList(L);  
}

int main(){
	testDLinkList();
	return 0;
}

静态链表#

/**
 *定义静态链表 
 */ 
#define MaxSize 10    //静态链表最大长度
struct Node{          //静态链表结构类型的定义 
	ElemType data;
	int next;        //下一个元素的数组下表 
}; 

void testSLinkList(){
	struct Node a[MaxSize];
} 


/**
 *也可以这样定义静态链表 
 */ 
#define MaxSize 10    //静态链表最大长度
typedef struct{          //静态链表结构类型的定义 
	ElemType data;
	int next;        //下一个元素的数组下表 
}SLinkList[MaxSize]; 

void testSLinkList(){
	SLinkList a;
} 

循环链表#

/**
 *1.循环单链表初始化 
 */

bool InitList(LinkList &L){
	L = (LNode *)malloc(sizeof(LNode));
	if(L == NULL){
		return false;
	}
	L->next = L;      //头结点next指向头结点
	return true; 
} 

/**
 *2.判断循环单链表是否为空 
 */
bool Empty(LinkList L){
	if(L->next == L){
		return true;
	}
	else{
		return false;
	}
}


/**
 *3.判断结点p是否为循环单链表的表尾结点 
 */
bool isTail(LinkList L, LNode *p){
	if(p->next == L){
		return true;
	}
	else{
		return false;
	}
}


/**
 *4.循环双链表初始化 
 */
 bool InitDList(DLinkList &L){
	L = (DNode *)malloc(sizeof(DNode));
	if(L == NULL){
		return false;
	}
	L->next = L;      //头结点next指向头结点
	L->prior = L;
	return true; 
} 

/**
 *5.判断循环双链表是否为空 
 */
bool Empty(DLinkList L){
	if(L->next == L){
		return true;
	}
	else{
		return false;
	}
}

/**
 *6.判断结点p是否为循环双链表的表尾结点 
 */
bool isTail(DLinkList L, DNode *p){
	if(p->next == L){
		return true;
	}
	else{
		return false;
	}
}


/**
 *7.循环双链表的插入 
 */
bool InsertNextDNode(DNode *p, DNode *s){
	s->next = p->next;    //将结点*s插入到结点*p之后
	p->next->prior = s;
	s->prior = p;
	p->next = s; 
}

/**
 *8.循环双链表的删除 
 */

//删除p的后继结点q
	p->next = q->next;
	q->next->prior = p;
	free(q);

栈、队列和串#

栈的顺序存储结构#

/**
 *顺序栈定义 
 */
 
#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];      //静态数组存放栈中元素
	int top;                   //栈顶指针 （记录数组的下标） 
}SqStack; 


/**
 *初始化栈 
 */
void InitStack(SqStack &S){
	S.top = -1;     //初始化栈顶指针 
}


/**
 *判断栈空 
 */
bool StackEmpty(SqStack S){
	if(S.top == -1){   //栈空 
		return true; 
	} 
	else{
		return false;
	}
}
 

/**
 *进栈操作 
 */
bool Push(SqStack &S, ElemType e){
	if(S.top == MaxSize - 1){    //栈满，报错
		return false; 
	} 
	S.top = S.top + 1;    //指针先加1
	S.data[S.top] = e;    //新元素再入栈
	return true; 
}
 
 
/**
 *出栈操作 
 */
bool pop(SqStack &S, ElemType &e){
	if(S.top == -1){    //栈空，报错
		return false; 
	} 
	e = S.data[S.top];    //栈顶元素先出栈 
	S.top = S.top - 1;    //指针先减1 
	return true;
}

/**
 *出栈操作 
 */
bool Pop(SqStack &S, ElemType &e){
	if(S.top == -1){    //栈空，报错
		return false; 
	} 
	e = S.data[S.top];    //栈顶元素先出栈 
	S.top = S.top - 1;    //指针先减1 
	return true;
}


/**
 *读栈顶元素 
 */
bool GetTop(SqStack &S, ElemType &e){
	if(S.top == -1){    //栈空，报错
		return false; 
	} 
	e = S.data[S.top];    //e记录栈顶元素  
	return true;
}


/**
 *共享栈 
 */
#define MaxSize = 10
typedef struct{
	ElemType data[MaxSize];   //静态数组存放栈中元素
	int top0;     //0号栈栈顶指针
	int top1;     //1号栈栈顶指针 
}ShStack;
//初始化栈
void InitStack(ShStack &S){
	S.top0 = -1;
	S.top1 = MaxSize;
} 
//判断栈满的条件
top0 + 1 == top1; 




//测试函数 
void testStack(){
	SqStack S;        //声明一个顺序栈，分配空间 
	InitStack(S)
}

栈的链式存储结构#

/**
 *链栈的定义 
 */
typedef struct Linknode{
	ElemType data;
	struct Linknode *next;
}*LiStack;     //和单链表类似 

//带头结点/不带头结点 创增删查判空判满 参考单链表 

栈在括号匹配中的运用#

#include <stdio.h>

#define MaxSize 10
typedef struct{
	char data;
	int top;
}SqStack; 

bool brackCheck(char str[], int length){
	Sqstack S;
	InitStack S;    //初始化一个栈 
	for(int i = 0; i < length; i++){
		if(str[i] == '(' || str[i] =='[' || str[i] =='{'){
			Push(S, str[i]);        //扫描到左括号，入栈 
		}
		else{
			if(StackEmpty(S)){        //扫描到有括号，但当前栈空
				return false;         //匹配失败 
			} 
			char topElem;
			Pop(S, topElem);          //栈顶元素出栈
			if(str[i] == ')' && topElem != '('){
				return false;
			} 
			if(str[i] == ')' && topElem != '('){
				return false;
			}
			if(str[i] == '}' && topElem != '{'){
				return false;
			} 
		}
	} 
	return StackEmpty(S);     //检索完全部括号后，如果栈空则说明匹配成功 
}

//初始化栈
void InitStack(SqStack &S)
//判断栈是否为空
bool StackEmpty(SqStack S)
//新元素入栈
bool Push(SqStack &S, char x) 
//栈顶元素出栈，用x返回
bool Pop(SqStack &S, char &x) 

队列的顺序存储结构#

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];   //用静态数组存放队列元素
	int front, rear;          //队头指针和队尾指针 
}SqQueue; 

 
void testQueue(){
 	SqQueue Q;    //声明一个队列（顺序存储） 
	//...后续操作... 
 } 


/**
 *判断队列是否为空 
 */
bool QueueEmpty(SqQueue Q){
	if(Q.front == Q.rear){
		return true;
	}
	else{
		return false;
	}
} 


/**
 *入队操作 
 */
 bool EnQueue(SqQueue &Q, ElemType e){
 	if((Q.rear + 1) % MaxSize == Q.front){         //队满  //看rear的后一个位置是否与front重合
	                                              //（牺牲了一个空间,所以rear+1才是front 防止front与rear重合（此时与队空条件相同出现歧义） 
 		return false;
	 } 
	 Q.data[Q.rear] = e;
	 Q.rear = (Q.rear + 1) % MaxSize;   //队尾指针加1取模 
	 return true; 
 } 
 
 
 /**
 *查找操作（获得队头元素的值） 
 */
 bool GetHead(SqQueue &Q, ElemType &e){
 	if(Q.rear == Q.front){         //队空 
 		return false;
	 } 
	 e = Q.data[Q.front];
	 return true; 
 } 
 

队列的链式存储结构#

/**
 * 队列的链式实现 
 */
typedef struct LinkNode{  //链式队列结点 
	ElemType data;
	struct LinkNode *next;
}LinkNode; 

typedef struct{          //链式队列 
	LinkNode *front, *rear;     //队列的队头和队尾指针 ,相比单链表多了一个尾指针 
}LinkQueue; 


/**
 * 队列的初始化（带头结点） 
 */
void InitQueue(LinkQueue &Q){
	//初始时front和rear都指向头结点 ,注意：front指向的是头结点，不是第一个元素 
	Q.front = Q.rear = (LinkNode* )malloc(sizeof(LinkNode));
	Q.front->next = NULL;
} 

/**
 * 判空 (带头结点） 
 */
bool IsEmpty(LinkQueue Q){
	if(Q.front == Q.rear){
		return true;
	}
	return false;
}


/**
 * 队列的初始化（不带头结点） 
 */
void InitQueue(LinkQueue &Q){
	//初始时front和rear都指向NULL
	Q.front = NULL;
	Q.rear = NULL;
} 

/**
 * 判空 (不带头结点） 
 */
bool IsEmpty(LinkQueue Q){
	if(Q.front == NULL){
		return true;
	}
	return false;
}

/**
 * 队尾元素入队（带头结点） 
 */
void EnQueue(LinkQueue &Q, ElemType e){
	LinkNode *s = (LinkNode*)malloc(sizeoe(LinkNode));
	s->data = e;
	s->next = NULL;
	Q.rear->next = s;
	Q.rear = s;       //表尾指针后移 
} 

/**
 * 队尾元素入队（不带头结点） 
 */
void EnQueue(LinkQueue &Q, ElemType e){
	LinkNode *s = (LinkNode*)malloc(sizeoe(LinkNode));
	s->data = e;
	s->next = NULL;
	if(Q.front == NULL){      //队列为空时区别对待 
		Q.front = s;
		Q.rear = s;
	} 
	else{
	Q.rear->next = s;
	Q.rear = s;       //表尾指针后移 
	}
} 


/**
 * 队头元素出队（带头结点） 
 */
bool DeQueue(LinkQueue &Q, ElemType &e){
	if(Q.front == Q.rear){
		return false;
	}
	LinkNode *p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;     //修改指针，若不是最后一个结点出队，直接free（p）即可，否则要特殊处理 
	if(Q.rear == p){       //最后一个结点出队 
		Q.rear = Q.front;    //修改rear指针，让其指向头结点 
	}
	free(p);              //释放结点空间,除了上述最后一个结点出队时的特殊处理，我们修改完指针之后直接free掉p即可 
	return true; 
} 


/**
 * 队头元素出队（不带头结点） 
 */
bool DeQueue(LinkQueue &Q, ElemType &e){
	if(Q.front == NULL){
		return false;
	}
	LinkNode *p = Q.front;
	e = p->data;
	Q.front = p->next;     //修改指针，若不是最后一个结点出队，直接free（p）即可，否则要特殊处理 
	if(Q.rear == p){       //最后一个结点出队 
		Q.front = NULL;    
		Q.rear = NULL;    //修改front和NULL指针让其置空 
	}
	free(p);              //释放结点空间,除了上述最后一个结点出队时的特殊处理，我们修改完指针之后直接free掉p即可 
	return true; 
} 

串的存储结构#

/**
 * 串的顺序存储结构（静态数组实现） 
 */ 
#define MAXLEN 255       //预定义最大串长为255
typedef struct{
	char ch[MAXLEN];
	int length;
}SString;

 
 
/**
 * 串的顺序存储结构（动态数组实现/堆分配存储） 
 */
 #define MAXLEN 255 
typedef struct{ 
	char *ch[MAXLEN];      //指向串的基地址 
	int length;
}HString;

HString S;
S.ch = (char *)malloc(sizeof(char)*MAXLEN);
S.length = 0;    
//用完需要free

 
 
/**
 * 串的链式存储结构 
 */
typedef struct StringNode{
	char ch;     //每个结点存1个字符
	struct StringNode * next; 
}StringNode, *String;            //但是这种方法存储密度低（一个ch存1个字节，而一个指针4个字节，所以可采用如下方式增加存储密度） 

typedef struct StringNode{
	char ch[4];     //每个结点存多个字符
	struct StringNode * next; 
}StringNode, *String; 

 
 /**
 * 基本操作之求子串 (用Sub返回串S的第pos个字符起长度为len的子串） 
 */
bool SubString(SString &Sub, SString S, int pos, int len){
	//子串范围越界
	if(pos + len - 1 > S.length){
		return false;
	}
	for(int i = pos; i < pos + len; i++){
		Sub.ch[i - pos + 1] = S.ch[i];
	}
	Sub.length = len;
	return true;
} 


/**
 * 基本操作之比较两串大小 (若S>T,返回值>0，=则返回0，S<T则返回值<0） 
 */
int StrCompare(SString S, SString T){
	for(int i = 1; i <= S.length && i <= T.length; i++){
		if(S.ch[i] != T.ch[i]){
			return S.ch[i] - T.ch[i];
		}
	}
	//扫描过的所有字符都相同，则长度长的串更大
	return S.length - T.length;     //长度相等返回0也符合 
} 


/**
 * 基本操作之定位操作 （若主串S中存在与串T值相同的字符串，则返回它在主串S中第一次出现的位置，否则函数值为0） 
 */
int Index(SString S, SSting T){
	int pos = 1, n =StrLength(S), m = StrLength(T);
	SString sub;     //用于暂存子串
	while(pos < n - m + 1){
		SubString(sub , S, pos, m);
		if(StrCompare(Sub, T) != 0){
			++pos;
		}
		else{
			return pos;       //返回子串在主串中的位置 
		}
	}
	return 0;    //S中不存在与T相等的子串 
} 

模式匹配算法（朴素（暴力）匹配和KMP）#

/**
 * 朴素模式匹配算法（使用到了基本操作） 
 */
 
int Index(SString S, SSting T){
	int pos = 1, n =StrLength(S), m = StrLength(T);
	SString sub;     //用于暂存子串
	while(pos < n - m + 1){             //最多对比n-m+1个子串    比如n=5, m=2,那么最多要匹配5-2+1=4个长度为2的子串 
		SubString(sub , S, pos, m);
		if(StrCompare(Sub, T) != 0){
			++pos;
		}
		else{
			return pos;       //返回子串在主串中的位置 
		}
	}
	return 0;    //S中不存在与T相等的子串 
} 


/**
 * 朴素模式匹配算法（不使用基本操作） 思想：设立一个主串指针i，一个模式串指针j，
	若当前子串匹配失败，则主串指针i指向下一个子串的第一个位置 ※（i=i-j+2）※，模式串指针j回到模式串的第一个位置（j=1） 
	（这里难理解 见王道4.2_1 10分钟左右） 
	若j超出了模式串长度，则匹配成功，返回当前子串第一个字符的位置：i-T.length 
 */
 
int Index(SString S, SSting T){
	int i = 1, j = 1;
	while(i < S.length  && j < T.length){             //最多对比n-m+1个子串    比如n=5, m=2,那么最多要匹配5-2+1=4个长度为2的子串 
		if(S.ch[i] == T.ch[j]){
			++i; ++j;         //i,j都后移继续匹配下一个字符 
		}
		else{
			i = i - j + 2; 
			j = 1;
		}
	}
	if(j > T.length){
		return i - T.length;    //匹配成功，返回第一个字符的位置 
	}
	else{
		return 0;    //匹配失败 
	}
} 


/**
 * KMP
 */
int Index_KMP(SString S, SSting T, int next[]){
	int i = 1, j = 1;
	while(i < S.length  && j < T.length){ 
		if(j == 0 || S.ch[i] == T.ch[j]){
			++i; ++j;         //i,j都后移继续匹配下一个字符 
		}
		else{
			j = next[j];    //模式串向右移动 
		}
	}
	if(j > T.length){
		return i - T.length;    //匹配成功，返回第一个字符的位置 
	}
	else{
		return 0;    //匹配失败 
	}
} 


/**
 * 优化的KMP
 */
//在KMP的基础上优化next数组为nextval数组,减少不必要的回溯 
void get_nextval(SSting T, int nextval[]){
	int i = 1, j = 0;
	nextval[1] = 0;   //普适性
	while(i < T.length){
		if(j == 0 || T.ch[i] == T.ch[j]){
			++i; ++j;
			if(T.ch[i] != T.ch[j]){
				nextval[i] = j;
			}
			else{
				nextval[i] = nextval[j];
			}
			else{
				j = nextval[j];
			}
		}
	} 

//或者是先算出next数组之后，采用如下算法把next数组优化为nextval    //序号j   1 2 3 4 5 6 
nextval[1] = 0;    //普适性                               //模式串T.ch[j]    a b a b a a
for(j = 2; j < T.length; j++){                                   //next[j]   0 1 1 2 3 4
 	if(T.ch[next[j]] == T.ch[j]){                               //nextval[j] 0 1 0 1 0 4 
		nextval[j] = nextval[next[j]];
	}
	else{
		nextval[j] = next[j];
	}
}

树与二叉树#

二叉树的存储结构#

/**
 * 二叉树的顺序存储（不常用） 浪费存储单元，只适合存储完全二叉树 
 */

#define MaxSize 100
struct TreeNode{
	ElemType value;   //结点中的数据元素 
	bool isEmpty;     //结点是否为空 
};

TreeNode t[MaxSize];
for(int i = 0; i < MaxSize; i++){
	t[i].isEmpty = true;        //初始化所有结点标记为空 
}

/**
 * 二叉树的链式存储
 */
struct ElemType{
	int value;       //假设每个ElemType只包含一个int型变量 
}; 

typedef struct BiTNode{
	ElemType data;                     //数据域 
	struct BiTNode *lchild, *rchild;   //左、右孩子指针 
}BiTNode, *BiTree;

//定义一棵空树
BiTree root = NULL;

//插入根结点
root = (BiTree)malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;

//插入新结点
BiTree p = (BiTNode *)malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;      //作为根结点的左孩子

/**
 * 二叉树的链式存储（如果经常要查父节点） 
 */
 typedef struct BiTNode{   //三叉链表 
	ElemType data;                     //数据域 
	struct BiTNode *lchild, *rchild;   //左、右孩子指针 
	struct BiTNode *parent;            //父结点指针 
}BiTNode, *BiTree;

树的链式存储例子#

#include <stdio.h> 
#include <stdlib.h>

typedef struct ElemType{
	int value1;       //假设每个ElemType只包含一个int型变量 
	double value2;
	char value3;
}ElemType; 

typedef struct BiTNode{
	ElemType data;                     //数据域 
	struct BiTNode *lchild, *rchild;   //左、右孩子指针 
}BiTNode, *BiTree;

int main(){
	BiTree root = NULL;
	root = (BiTree)malloc(sizeof(BiTNode));
	root->data.value1 = 1;
	root->data.value2 = 1.1;
	root->data.value3 = 'a';
	root->lchild = NULL;
	root->rchild = NULL;

	BiTree p = (BiTNode *)malloc(sizeof(BiTNode));
	p->data.value1 = 2;
	p->data.value2 = 2.2;
	p->data.value3 = 'b';
	p->lchild = NULL;
	p->rchild = NULL;
	root->lchild = p;      //作为根结点的左孩子	
	
	printf("%d\n%f\n%c\n",root->data.value1,root->data.value2,root->data.value3);
	printf("%d\n%f\n%c\n",root->lchild->data.value1,root->lchild->data.value2,root->lchild->data.value3);
	return 0;
}

二叉树的先中后序遍历（递归）#

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

//先序遍历
void PreOrder(BiTree T){
	if(T != NULL){
		visit(T);    //访问根节点
		PreOrder(T->lchild); 
		PreOrder(T->rchild);
	}
} 

//中序遍历
void PreOrder(BiTree T){
	if(T != NULL){
		PreOrder(T->lchild);
		visit(T);    //访问根节点
		PreOrder(T->rchild);
	}
} 

//后序遍历
void PreOrder(BiTree T){
	if(T != NULL){
		PreOrder(T->lchild); 
		PreOrder(T->rchild);
		visit(T);    //访问根节点
	}
} 

//求树的深度（应用）
int treeDepth(BiTree T){
	if(T == NULL){
		return 0;
	}
	else{
		int l = treeDepth(T->lchild);
		int r = treeDepth(T->rchild); 
		//树的深度=Max（左子树深度，右子树深度）+1
		return l > r ? l + 1, r + 1;  
	}
}

二叉树的层序遍历#

/**
 * 层序遍历 
 */ 
void LevelOrder(BiTree T){
	InitQueue(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);  //右子树不空，则右子树根节点入队 
		}
	} 
}
 
/**
 *前提声明 
 */ 

//二叉树的结点（链式存储）
typedef struct BiTNode{
	char data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree; 

//链式队列结点
typedef struct LinkNode{
	BiTNode *data;        //注意，因为结点入队的时候，如层序遍历中左孩子入队保存的是结点的指针，而不是本身 
	struct LinkNode* next;
}LinkNode; 

typedef struct{
	LinkNode *front, *rear;
}LinkQueue;

二叉树的先中后序遍历（非递归）#

/*非递归遍历二叉树*/
//中序遍历
void InOrder2(BiTree T){
	InitStack(S);    //初始化栈
	BiTree p = T;    //p是遍历指针
	while(p || !IsEmpty(S)){    //栈不空或p不空时循环 
		if(p){                  //一路向左 
			Push(S,p);      //当前结点入栈
			p = p->lchild;    //左孩子不空，一直向左走 
		}
		else{              //出栈，并转向出栈结点的右子树 
			Pop(S,p); visit(p);    //栈顶元素出栈，访问出栈结点
			p = p->rchild;      //向右子树走，p赋值为当前结点的右孩子 
		}                      //返回while循环继续进入if-else语句 
	}  
}  


//先序遍历
void PreOrder2(BiTree T){
	InitStack(S);    //初始化栈
	BiTree p = T;    //p是遍历指针
	while(p || !IsEmpty(S)){    //栈不空或p不空时循环 
		if(p){ 
			visit(p);Push(S,p);    //访问当前结点，并入栈 
			p = p->lchild;    //左孩子不空，一直向左走 
		}
		else{              //出栈，并转向出栈结点的右子树 
			Pop(S,p);     //栈顶元素出栈
			p = p->rchild;      //向右子树走，p赋值为当前结点的右孩子 
		}                      //返回while循环继续进入if-else语句 
	}  
}  
  
//后序遍历（最难） 
void PostOrder2(BiTree T){
	InitStack(S);    //初始化栈
	p = T;    //p是遍历指针
	r = NUll; 
	while(p || !IsEmpty(S)){        //栈不空或p不空时循环 
		if(p){ 
			Push(S,p);              //访问当前结点，并入栈 
			p = p->lchild;          //左孩子不空，一直向左走 
		}
		else{
			GetTop(S,p);                          //读栈顶元素，非出栈
			if(p->rchild && p->child != r){       //若右子树存在，且未被访问过
				p = p->rchild;           //转向右 
			}
			else{             //否则，弹出结点并访问 
				Pop(S,p);    //弹出
				visit(p->data);   //访问
				r = p;        //记录最近访问过的结点
				p = NULL;      //结点访问完后，重置p指针 
			} 
		}//else
	}//while
} 
  
//习题：层次遍历求二叉树高度（非递归）
int BTdepth(BiTree T){
    if(T==NULL){
		return 0;          //空树，高度为0;
	}
    int front = -1,rear = -1;
    int last = 0;  //last指向当前层最后结点 
    int level =0;
	BiTree Q[MaxSize];   //设置队列Q，元素是二叉树结点指针且容量足够 
	Q[++rear] = T;      //将根结点入队；
    BiTree p; 
    while(front <rear){    //队不空，则循环 
       		p = Q[++front];    //队列元素出队，即正在访问的结点 
        if(P->lchild){
            Q[++rear] = p->lchild;    //左孩子入队 
        }
        if(P->rchild){
            Q[++rear] = p->rchild;    //右孩子入队 
        }
        
        if(front == last){    //当前层最后结点；
            level++;         //层数增1 
            last = rear;     //last指向下层 
        }
    }
    return level;
}

线索二叉树的存储结构与二叉树的线索化#

/**
* 线索二叉树的存储结构 
*/ 

//二叉树的结点（链式存储）
typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree; 

//线索二叉树结点 
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild, *rchild;
	int ltag, rtag;        //左右线索标志 （tag位为1时，表示指针是线索；tag位为0时，表示指针指向孩子） 
}ThreadNode, *ThreadTree; 

/**
*  
*/ 

//辅助全局变量 
BiTNode *p;      //p指向目标结点 
BiTNode *pre;    //指向当前访问结点的前驱 
BiTNode *final;  //用于记录最终结果 

//中序遍历 
void Inorder(BiTree T){
	if(T != NULL){
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}

//访问结点q
void visit(BiTNode *q){
	if(q == p){       //当前访问的结点刚好是p 
		final = pre   //找到p的前驱 
	}
	else{
		pre = q;     //pre指向当前访问的结点 
	} 
} 

/**
* 中序线索化 
*/ 

//全局变量pre,指向当前访问结点的前驱
ThreadNode *pre = NULL;  

//线索二叉树结点 
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild, *rchild;
	int ltag, rtag;        //左右线索标志 （tag位为1时，表示指针是线索；tag位为0时，表示指针指向孩子） 
}ThreadNode, *ThreadTree; 

//中序线索化二叉树 
void CreateInThread(ThreadTree T){
	pre = NULL;     //pre初始为NULL 
	if(T != NULL){      //非空二叉树才能线索化 
		InThread(T);    //中序线索化二叉树
		if(pre -> rchild == NULL){
			pre->rtag = 1;      //注意：最后还要检查pre的child是否为NULL，如果是，则令rtag=1.
			                    //处理遍历的最后一个结点  
 		} 
	}
}

//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T){
	if(T != NULL){
		InThread(T->lchild);
		visit(T);
		Inthread(T->rchild);	
	}

} 

void visit(ThreadNode *q){
	if(q->lchild == NULL){     //左子树为空，建立前驱线索 
		q->lchild = pre;
		q->ltag = 1;
	}
	if(pre != NULL && pre->rchild == NULL){
		pre->rchild = q;       //建立前驱结点的后继线索 
		pre->rtag  = 1;
	}
	pre = q; 
} 

/**
 * 先序线索化（注意，在执行PreThread(T->lchild)之前已经把左孩子指针指向了前驱
   这时如果有左子树，再访问左子树的话就会将q结点再次指回pre结点，
   出现死循环（原地打转）） 
 */ 
//修改部分：
void PreThread(ThreadTree T){
	if(T != NULL){
		visit(T);    //先处理根节点
		if(T->ltag == 0){   //lchild不是前驱线索 注意：这里作出了修改，防止出现死循环 
			PreThread(T->lchild);
		}
		PreThread(T->rchild);
	}
}

/**
 * 后序线索化
 */ 
//不会出现先序死循环的问题，只需要将中序的代码修改遍历顺序即可 

//大话数据结构中采用(考研可忽略)
typedef enum {Link, Thread} PointerTag;

树的存储结构#

//双亲表示法（顺序存储） 
#define MAX_TREE_SIZE 100  //树中最多结点数
typedef struct{            //树的结点定义 
	ElemType data;         //数据元素 
	int parent;            //双亲位置域 
}PTNode; 

typedef struct{                   //树的类型定义 
	PTNode nodes[MAX_TREE_SIZE];  //双亲表示 
	int n;                        //结点数 
}; 

//孩子表示法（顺序+链式存储）
struct CTNode{
	int child;     //孩子结点在数组中的位置
	struct CTNode *next;    //下一个孩子 
}; 
typedef struct{
	ElemType data;
	struct CTNode *firstChild;   //第一个孩子 
}CTBox;

typedef struct{
	CTBox nodes[MAX_TREE_SIZE];
	int n, r;   //节点数和根的位置 
}CTree; 

//孩子兄弟表示法（链式存储）（重点）  实现树和二叉树的转化 
typedef struct CSNode{
	ElemType data;
	struct CSNode *firstchild, *nextsibling   //第一个孩子和右兄弟指针 
}CSNode, CSTree; 

树和森林的遍历#

//树的先根遍历
void PreOrder(TreeNode *R){
	if(R != NULL){
		visit(R); //访问根节点
		while(R还有下一个子树T){
			PreOrder(T);     // 先根遍历下一棵子树
		} 
	}
}

//树的后根遍历
void PostOrder(TreeNode *R){
	if(R != NULL){
		while(R还有下一个子树T){
			PostOrder(T);     // 先根遍历下一棵子树
		} 
		visit(R); //访问根节点
	}
}

并查集及优化#

#define SIZE 13
int UFSets[Size];   //集合元素数组

//初始化并查集
void Initial(int S[]){
	for(int i = 0; i < SIZE; i++){
		S[i] = -1;   //注意，后续优化的时候，将其变为树的高度的负数，以便取绝对值得到树的高度 
	}
} 

//"查"操作，找x所属集合（返回x所属根节点）
int Find(int S[], int x){
	while(S[x] >= 0){     //循环寻找x的根 
		x = S[x]; 
	}
	return x;        //根的S[]小于0 
} 

//"并"操作，将两个集合合并为一个 
void Union(int S[], int Root1, int Root2) {
	//要求Root1和Root2是不同的集合
	if(Root1 == Root2){
		return;
	} 
	//将根Root2连接到另一根Root1的下面
	S[Root2] = Root1;  //Root2的父节点指向Root1 
	return;
}

//注意：如果给定的两个元素不是根节点，那么只需要先执行find找到根节点在执行union即可合并

//Union操作优化（查的复杂度为O（n），并的复杂度为O（1） ，树越高效率越低。所以尽量减少树的高度 
//Union"并"操作，小树合并到大树（该方法构造的树高不超过（log2（以2为底）n）向下取整+1） 所以复杂度为O（log2（以2为底）n ） 
void Union(int S[], int Root1, int Root2) {
	if(Root1 == Root2){
		return;
	} 
	if(S[Root2] > S[root1]){    //Root2节点数更少 (因为这里是负值） 
		S[Root1] += S[root2];  //累加节点总数  (总和赋值给更大的树)
		S[Root2] = Root1;      //小树合并到大树 
	} 
	else{
		S[Root2] += S[root1];  //累加节点总数
		S[Root1] = Root2;      //小树合并到大树 
	} 
}  

//Find "查"优化，先找到根结点，在进行压缩路径（将查找路径上的所有结点都挂在根节点下）
int Find(int S[], int x){
	int root = x; 
	while(S[root] >= 0){     
		root = S[root];   //循环找到根 
	}
	while(x != root){    //压缩路径 
		int t = S[x];    //t指向x的父节点
		S[x] = root;    //x直接挂到根节点下
		x = t; 
	} 
	return root;     //返回根结点编号 
} 

//总结：无论是find还是union优化，核心思想都是把树变矮 

二叉排序树#

/**二叉排序树的查找 **/
//二叉排序树结点
typedef struct BSTNode{
	int key;
	struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree; 

//在二叉排序树中查找值为key的结点（非递归）                                             //最坏时间复杂度O（1） 
BSTNode *BST_Search(BSTree T, int key){
	while(T != NULL && key != T->key){  //如果树不空且根结点值不等于key，则循环 
		if(key < T->key){
			T = T.lchild;   //key小于结点值，则进入左子树 
		} 
		else{
			T = T.rchild;   //key大于结点值，则进入右子树 
		} 
	}
	return T;   //这里如果查找失败了仍然会返回NULL 
} 

//在二叉排序树中查找值为key的结点（递归）                                            //最坏时间复杂度O（h） 
BSTNode *BSTSearch(BSTree T, int key){
	if(T == NULL){
		return NULL;     //查找失败 
	}
	if(key == T->key){
		return T;   //查找成功 
	} 
	else if(key < T->key){
		return BSTSearch(T->lchild, key);   //在左子树中查找 
	}
	else{
		return BSTSearch(T->rchild, key);   //在右子树中查找 
	}
} 

//在二叉排序树中插入关键字为k的新结点（递归实现）                       //最坏时间复杂度O（h）
int BST_Insert(BSTree &T, int k){
	if(T ==NULL){       //原树为空，新插入的结点为根结点 
		T = (BSTree)malloc(sizeof(BSTNode));
		T->key = k;
		T->lchild = T->rchild = NULL;
		return true;              //插入成功 
	}
	else if(k == T.key){      //树中存在与关键字相同的结点，插入失败 
		 return 0; 
	}
	else if(k < T->key){
		return BST_Insert(T->lchild, k);      //插入到左子树 
	} 
	else{
		return BST_Insert(T->rchild, k);     //插入到右子树 
	}
} 

//非递归效率低，自己练手

//二叉排序树的构造（按照str[]中的关键字序列建立二叉排序树
void Create_BST(BSTree &T, int str[], int n){
	T = NULL;       //初始时T为空树
	int i = 0;
	while(i < n){
		BST_Insert(T, str[i]);
		i++;
	} 
} 

//二叉排序树的删除 

图#

图的存储方式#

//邻接矩阵法（一维数组+二维数组） 
#define MaxVertexNum 100   //顶点数目的最大值 
typedef struct{
	char Vex[MaxVerNum];     //顶点表 
	bool Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵，边表
	int vexnum, arcnum;      //图的当前顶点数和边数，弧数 
}MGraph; 

//邻接矩阵法存储带权图（网）
#define MaxVertexNum 100   //顶点数目的最大值 
#define INFINITY 最大的int值   //宏定义常量"无穷" 
typedef char VertexType;    //顶点的数据类型 
typedef int EdgeType;    //带权图中边上权值的数据类型 
typedef struct{
	VertexType Vex[MaxVertexNum];     //顶点
	EdgeType Edge[MaxVertexNum][MaxVertexNum];   //边的权 
	int vexnum, arcnum;      //图的当前顶点数和弧数 
}MGraph; 

//邻接表法（顺序存储+链式存储） 
//顶点
typedef struct VNode{
	VertexType daya;   //顶点信息
	ArcNode *first;    //第一条边/弧 
}VNode, AdjList[MaxVertexNum]; 
//"边/弧" 
typedef struct ArcNode{
	int adjvex;    //边/弧指向哪个结点
	struct ArcNode *next;   //指向下一条弧的指针
	//InfoType info;    //边权值 
ArcNode}; 

//十字链表和邻接多重表考研很少考手写代码 
 

图的基本操作#

/*知识总览
 图的基本操作：
●Adjacent(G,x,y): 判断图G是否存在边<x, y>或(x, y)。
●Neighbors(G,x): 列出图G中与结点x邻接的边。  
●InsertVertex(G,x): 在图G中插入顶点x。
●DeleteVertex(G,x): 从图G中删除顶点x。
●AddEdge(G,x,y): 若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。
●RemoveEdge(G,x,y): 若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。
●(考研重要)FirstNeighbor(G,x): 求图G中顶点x的第-一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
●(考研重要)NextNeighbor(G,x,y): 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后-一个邻接点，则返回-1。
●Get_ edge_ value(G,x,y): 获取图G中边(x, y)或<x, y>对应的权值。
●Set_ edge_ _value(G,x,y,v): 设置图G中边(x, y)或<x, y>对应的权值为v。
上述考研重要，在图的遍历算法中用得到，包括深度优先遍历和广度优先遍历 
*/ 

BFS广度优先遍历#

bool visited[MAX_VERTEX_NUM];   //访问标记数组,初始都为false 

void BFSTraverse(Graph G){    //对图G进行广度优先遍历 
	for(i = 0; i < G.vexnum; ++i){
		visited[i] = false;         //访问标记数组初始化 
	} 
	InitQueue(Q);         //初始化辅助队列Q
	for(i = 0; i < G.vexnum; ++i){    //从0号顶点开始遍历 
		if(!visited[i]){  //对每个连通分量调用一次BFS
			BFS(G, i);     //vi未访问过，从vi开始BFS 
		}
	} 
	 
} 

//广度优先遍历BFS
void BFS(Graph G, int v){    //从顶点v出发，广度优先遍历图G
	visit(v);         //访问初始顶点v
	visited[v] = true;     //对v做已访问标记
	Enqueue(Q, v);        //顶点v入队列Q
	while(!isEmpty(Q)){
		Dequeue(Q, v);      //顶点v出队列
		for(w = FirstNeighbor(G, v)); w >= 0; w = NextNeighbor(G, v, w)){
			//检测v所有邻接点
			if(!visited[w]){    //w为V的尚未访问的临接顶点
				visit(w);      //刚问顶点w
				visited[w] = true;   //对w做已访问标记
				Enqueue(Q, w)      //顶点w入队列 
			}//if 
		}//for
	}//while
}
 //但是如果是非连通图，则无法遍历完所有的节点 ，所以要在BFS之前添加一段代码 

DFS深度优先遍历#

bool visited[MAX_VERTEX_NUM];   //访问标记数组

void DFSTraverse(Graph G){   //对图G进行深度优先遍历,从第一个visited=false的顶点开始进行DFS 
	for(v = 0, v < G.vernum; ++v){
		visited[v] = false;   //初始化已访问标记数据 
	} 
	for(v = 0, v < G.vernum; ++v){     //从v=0开始遍历 
		if(!visited[v]){
			DFS(G,v);
		} 
	} 
} 

//DFS深度优先遍历 
void DFS(Graph G, int v){   //从顶点v出发，深度优先遍历图G
	visit(v);     //访问节点v
	visited[v] = true;   //设已访问标记
	for(w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w)){
		if(!visited[w]){       //w为v的尚未访问的邻接节点 
			DFS(G,w);
		}//if 
	}//for
}

//注意，同BFS一样，如果是非连通图，则无法遍历完所有节点，所以在DFS之前再加一段代码 

BFS求单源最短路径#

//BFS算法求单源最短路径问题

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u){
	//d[i]表示从u到i节点的最短路径
	for(i = 0; i < G.vexnum; ++i){
		d[i] = ∞;   //初始化路径长度
		path[i] = -1;   //最短路径从哪个顶点过来  
	} 
	d[u] = 0;    //自己到自己是0 
	visited[u] = true;
	Enqueue(Q,u);
	
	while(!isEmpty(Q)){      //BFS算法主过程 
		Dequeue(Q, v);      //队头元素u出队列
		for(w = FirstNeighbor(G, u)); w >= 0; w = NextNeighbor(G, u, w)){
			if(!visited[w]){    //w为u的尚未访问的邻接顶点
				d[w] = d[u] + 1;      //路径长度加一 
				path[w] = u;      //最短路径应从u到w 
				visited[w] = true;   //对w做已访问标记
				Enqueue(Q, w)      //顶点w入队列 
			}//if 
		}//for
	}//while
} 

Floyd算法求最短路径（纸老虎：代码实现简单）#

//Floyd算法求最短路径
///...准备工作，根据图的信息初始化矩阵A和path
for(int k = 0; k < n; k++){    //考虑以Vk作为中转点
	for(int i = 0; i < n; i++){   //遍历整个矩阵，i为行号，j为列号
		for(int j = 0; j < n; j++){
			if(A[i][j] > A[i][k] + A[k][j]){     //以Vk为中转点的路径更短 
				A[i][j] = A[i][k] + A[k][j];     //更新最短路径长度
				path[i][j] = k;       //中转点 
			}
		} 
	} 
	
} 

拓扑排序#

//拓扑排序 
#define MaxVertexNum 100   //图中顶点数目的最大值
typedef struct ArcNode{    //边表节点 
	int Adjvex;     //该弧所指向的顶点的位置 
	struct ArcNode *nextarc;    //指向下一条弧的指针
	//InfoType info;     //权值 
}ArcNode; 

typedef struct VNode{    //顶点表节点
	VertexType data;   //顶点信息
	ArcNode *firstarc;   //指向第一条依附该顶点的弧的指针 
}VNode, AdjList[MaxVertexNum];

typedef struct{
	AdjList vertices;    //邻接表
	int vexnum, arcnum;    //图的顶点数和弧数 
}Graph;       //Graph是以邻接表存储的图类型

bool TopologicalSort(Graph G){
	InitStack(S);    //初始化栈，存储入度为0的顶点
	for(int i = 0; i < G.vexnum; i++){
		if(indegree[i] == 0){
			Push(S,i);         //将所有入度为0的顶点进栈 
		}
		int count= 0;    //计数，记录当前已经输出的顶点数
		while(!IsEmpty(S)){     //栈不空，则存在入度为0的顶点 
			Pop(S,i);     //栈顶元素出栈
			print[count++] = i;    //输出顶点i
			for(p = G.vertices[i].firstarc; p ; p = p->nextarc){
				//将所有i指向的顶点的入度-1，并且将入度减为0的顶点压入栈S
				v = p->adjvex;
				if(!(--degree[v])){
					Push(S,v);   //入度为0，则入栈 
				} 
			} //for 
		} //while 
		if(count < G.vexnum){
			return false;      //排序失败，有向图中有回路 
		} 
		else{
			return true;     //拓扑排序成功 
		} 
	} //for 
} 

//逆拓扑排序（DFS实现）
void DFSTraverse(Graph G){   //对图G进行深度优先遍历 
	for(v = 0; v < G.vexnum; ++v){
		visited[v] = false;    //初始化已访问标记数据 
	} 
	for(v = 0; v < G.vexnum; ++v){   //从0开始遍历 
		if(!visited[v]){
		DFS(G,v); 
	} 
}

void DFS(Graph G, int v){    //从顶点v出发，深度优先遍历图G 
	visited[v] = true;    //设已访问标记
	for(w = FirstNeighbor(G,v); w >= 0; W = NextNeibor(G,v,w)){
		if(!visited[w]){     //w为u的尚未访问的邻接顶点
			DFS(G,w); 
		}//if 
	} 
	print(v);    //输出顶点 
}

查找#

顺序查找#

typedef struct{   //查找表的数据结构（顺序表）
	ElemType *elem;  //动态数组基址
	int TableLen;    ///表的长度 
}SSTable;
 
//顺序查找
int Search_Seq(SSTable ST, ElemType key){
	int i;
	for(i = 0; i < ST.TableLen && ST.elem[i] != key; ++i){
		//查找成功，则返回元素下标；查找失败，返回-1
		return i == ST.TableLen ? -1 : i; 
	}
}

//顺序查找（哨兵）
int Search_Seq(SSTable ST, ElemType key){
	ST.elem[0] = key;    //哨兵 
	int i;
	for(i = TableLen; ST.elem[i] != key; --i){  //从后往前找 
		//查找成功，则返回元素下标；查找失败，返回0 
		return i; 
	}
}

折半查找#

typedef struct{   //查找表的数据结构（顺序表）
	ElemType *elem;  //动态数组基址
	int TableLen;    ///表的长度 
}SSTable;

int Binary_Search(SSTable L, ElemType key){
	int low = 0, high = L.TableLen - 1, mid;
	while(low <= high){
		mid = (low + high) / 2;   //取中间
		if(L.elem[mid] == key){
			return mid;     //查找成功 
		} 
		else if(L.elem[mid] > key){
			high = mid - 1;     //从左边找 
		} 
		else{
			low = mid + 1;   //从右边找 
		} 
	}
	return -1;      //查找失败 
}