数据结构与算法笔记

准备把常用的数据结构与算法都手撸一遍，程序都经过调试并且可运行，代码中也有过程注释便于理解。之后会把各种数据结构的应用补上，比如基于栈的二进制转换，计算器，基于链表的一元多项式求和等。

数据结构

顺序表

#include <stdio.h>
#include <stdlib.h>
#define MAXLEN 100
typedef int DataType;	//定义数据类型 
//用结构体来完成顺序表 
typedef struct{
	//DataType data[MAXLEN];	//存储顺序表数据的数组 
	DataType *data;				//采用动态初始化数组的方法 
	int length;					//顺序表的长度 
}SeqList;

// 对顺序表操作的一些函数
//1.初始化顺序表操作 
void initSeqList(SeqList *seqList){
	seqList->data=(DataType*)malloc(sizeof(DataType)*MAXLEN);//数组动态初始化 
	seqList->length = 0;	//初始化一个空的顺序表，顺序表长度为0 
}

//2.建立顺序表,n为建立顺序表的元素数目 
void createSeqList(SeqList *seqList,int n){
	if(n>MAXLEN){
		printf("超过最大存储长度！\n");
		return;
	}
	if(n<1){
		printf("未添加元素！\n");
		return;
	}
		
	printf("请输入%d个元素：",n);
	int i;
	for(i=0;i<n;i++){
		scanf("%d",&seqList->data[i]);
	} 
	seqList->length=i;
	getchar();
}

//3.查取顺序表中第几位的内容 ,i为位置，returnData是返回的数据 
int getItemByLocation(SeqList *seqList,int index,DataType *returnData){
	if(index > seqList->length || index<1){
		return 0;	
	}else{
		*returnData = seqList->data[index-1];
		return 1;	
	} 
} 
//4.根据内容查询其在顺序表中的位置
int getItemByContent(SeqList *seqList,DataType context) {
	int i;
	for(i=0;i<seqList->length;i++){
		if(seqList->data[i] == context){
			return i+1;
		}
	}
	return 0;
}
//5.插入操作
int insertItem(SeqList *seqList,DataType context,int i){
	if(seqList->length >= MAXLEN || i<1 || i>seqList->length+1){
		//当前顺序表长度已经满了或者i的值非法
		printf("操作错误！");
		return 0; 
	}
	if(i == seqList->length+1){
		//插入的位置为最后一个位置则直接放入 
		seqList->data[i-1] = context; 
	}
	int j;
	for(j = seqList->length-1;j>=i-1;j--){
		seqList->data[j+1] = seqList->data[j];	//元素后移 
	}
	seqList->data[i-1] = context;//插入新元素 
	seqList->length++;
	return 1;
} 
//6.删除操作
int  deleteItem(SeqList *seqList,int i,DataType *returnData){
	if(seqList->length == 0){
		//表为空则无法删除 
		printf("顺序表为空");
		return 0;
	}
	if(i>seqList->length||i<1){
		printf("超出范围");
		return 0;
	}
	*returnData = seqList->data[i-1];//删除元素 
	int j;
	for(j=i;j<seqList->length;j++){
		//元素前移 
		seqList->data[j-1] = seqList->data[j];
	}
	seqList->length--; //长度减一
	return 1; 
} 
//7.显示顺序表中的所有数据 
void showAll(SeqList *seqList){
	int i;
	for(i=0;i<seqList->length;i++){
		printf("%d  ",seqList->data[i]);
	}
}

//8.菜单显示
void menu(){
  
  printf("\n顺序表的各种操作");
  printf("\n========================================");
  printf("\n|          1--建立顺序表               |");
  printf("\n|          2--插入元素                 |");
  printf("\n|          3--删除元素                 |");
  printf("\n|          4--按位置查找元素           |");
  printf("\n|          5--按元素值查找其在表中位置 |");
  printf("\n|          6--求顺序表的长度           |");
  printf("\n|          7--显示顺序表内容           |");
  printf("\n|          8--销毁顺序表               |");
  printf("\n|          0--返回                     |");
  printf("\n========================================");
  printf("\n请输入菜单号(0-8)：");
} 

//9.补充操作
//9.1销毁 
void destroySeqList(SeqList *seqList){
	if(seqList->data){
		free(seqList->data);
		seqList->length=0;
	}
}
//9.2
main(){
	SeqList seqList; 
	DataType dataType;
	int context;
	int n,i,loc,x;
	char ch1,ch2,a;
	ch1='y';
	while(ch1=='y'||ch1=='Y'){
		menu();
		scanf("%c",&ch2);
		getchar();
		switch(ch2)
		{
			case '1':
				initSeqList(&seqList);
				printf("请输入建立线性表的个数：");
				scanf("%d",&n);
				createSeqList(&seqList,n);
				printf("建立的线性表为：");
				showAll(&seqList);
				break;
	  		case '2':
				printf("请输入要插入的位置：");
				scanf("%d",&i);
				getchar();
				printf("请输入要插入的元素值：");
				scanf("%d",&context);
				getchar();
				if(insertItem(&seqList,context,i)){
					printf ("已成功在第%d的位置上插入%2d,插入后的线性表为: \n",i,context);
					showAll(&seqList);
					break;
				}else{
					printf("输入插入的参数错误!\n");
					break;
				}
			case '3':
				printf("请输入要删除元素的位置: ");
				scanf("%d",&i);
				if(deleteItem(&seqList,i,&x)){
					printf ("已成功在第%d的位置上删除%d,删除后的线性表为: \n",i,x);
					showAll(&seqList);
				}else
					printf ("\n输入删除的参数错误!");
				break;
			case '4':
				printf("请输入要查看表中元素位置(从1开始): ");
				scanf ("%d",&i);
				if (getItemByLocation(&seqList,i, &x))
					printf("当前线性表第%d个元素的值为: %d",i,x);
				else
					printf ("输入的位置错误!");
				break;
			case '5':
				printf("请输入要查找的元素值为: ") ;
				scanf("%d",&context) ;
				loc = getItemByContent(&seqList, context);
				if(loc)
					printf("查找元素值为%d的位置为: %d",context, loc);
				else
					printf ("该表中无此元素!");
				break;
			case '6':
				printf("当前线性表的长度为: %d",seqList.length);
				break;
			case '7':
				showAll(&seqList); 
				break;
			case '8':
				destroySeqList(&seqList);
				break;
			case '0' :
				ch1='n';
				break;
			default:
				printf("输入有误，请输入0~6进行选择!");
			}
		printf("\n");	
		system("pause");		
	}
}

单链表

结构体版本链表-动态链表，由于每次插入需要动态分配空间，效率太低，适合工程开发时使用

数组模拟链表-静态链表，速度快，适合于算法题

动态链表

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct linknode{
	DataType data;
	struct linknode *next;
} LinkList;

//初始化一个单链表
void *initList(){
	LinkList *head;
	head = (LinkList*)malloc(sizeof(LinkList));	//动态的分配一个头指针 
	head->next= NULL;
	return head;
} 

//增-头插法,n插入的元素 
void createListH(LinkList *head,int n){
	LinkList *node;
	int i;
	printf("请输入%d个元素:",n);
	for(i=0;i<n;i++){
		node = (LinkList*)malloc(sizeof(LinkList));	//动态分配一个新节点 
		scanf("%d",&node->data);
		
		//将新节点的next指针指向上一个添加的节点(头节点)
		node->next = head->next; 
		//更新头节点
		head->next = node; 
	}
	printf("通过头插法成功建立链表！");
} 

//增-尾插法，n插入的元素 
void createListL(LinkList *head,int n){
	
	LinkList *node,*last;
	last = head;		//设置头为最后一个节点 
	int i;
	printf("请输入%d个元素：",n);
	for(i=0;i<n;i++){
		node = (LinkList*)malloc(sizeof(LinkList));//动态生成新节点 
		scanf("%d",&node->data);					
		last->next=node;							//设置新节点为最后节点 
		node->next=NULL;							//设置最后一个节点的next为空 
		last = node;								//将last指向s 
	}
	printf("通过尾插法成功建立链表!"); 
} 

//查询链表长度
int lengthList(LinkList *head){
	LinkList *node;
	int count = 0;
	node = head->next;
	while(node!=NULL){
		//不为尾节点则进入循环 
		count++;
		node=node->next;
	}
	return count;	
} 

//按值查数据
int queryDataByContent(LinkList *head,DataType x){
	LinkList *node;
	node = head->next;
	int j=1;
	while(node != NULL && node->data != x){
		node = node->next;
		j++;
	}
	if(node != NULL){
		printf("在表的%d位找到了元素%d",j,node->data);
		return j;
	}else{
		printf("未查询到该元素");
		return 0;
	}
} 

//按序号查询,i为索引，data为查询到的数据为null则未查到 
 int queryDataByIndex(LinkList *head,int i,DataType *data){
 	LinkList *node;
 	int j=1;
 	node = head->next;
	 if(i<1 || i>lengthList(head)){
 		//位置错误 
 		printf("位置错误!"); 
 		return 0;
	}
	while(node!=NULL && j<i){
		node = node->next;
		j++;
	}
	if(j==i){
		printf("第%d位元素为：%d",i,node->data);
		data = &node->data;
		return 1;
	}
 } 
 
 //插入
 int insertItem(LinkList *head,DataType data,int i){
 	LinkList *node,*newNode;
 	node = head;
 	if(i<1 || i>lengthList(head)+1){
 		//位置错误 
 		printf("位置错误!"); 
 		return 0;
	}
	int j = 0;
 	while(node->next != NULL && j<i-1){
 		node = node->next;
 		j++;
	}
	if(j==i-1){
		newNode = (LinkList*)malloc(sizeof(LinkList));
		newNode->data = data;
		newNode->next = node->next;
		node->next = newNode;
		return 1;
	}
	return 0;
 } 
 
 //删除
int deleteNode(LinkList *head,int i,DataType *returnData){
	LinkList *node;
	node = head;
	int j=0;
	
	if(i<1 || i>lengthList(head)){
 		//位置错误 
 		printf("位置错误!"); 
 		return 0;
	}
	
	while(node->next != NULL && j<i-1){
		node = node->next;
		j++;
	}
	if(node->next != NULL && j==i-1){
		LinkList *deleteNode = node->next;
		node->next = node->next->next;
		*returnData = deleteNode->data;
		free(deleteNode);
		return 1;
	}
	return 0;
}

void showAll(LinkList *head){
	LinkList *node;
	node = head->next;
	while(node != NULL){
		
		printf("%d",node->data);
		
		if(node->next != NULL){
			printf("->");
		}
		node = node->next;
	}	
		
} 

void menu(){
  
  printf("\n顺序表的各种操作");
  printf("\n========================================");
  printf("\n|          1--建立链表(头插法)         |");
  printf("\n|          2--建立链表(尾插法)         |");
  printf("\n|          3--插入元素                 |");
  printf("\n|          4--删除元素                 |");
  printf("\n|          5--按位置查找元素           |");
  printf("\n|          6--按元素值查找其在表中位置 |");
  printf("\n|          7--求顺序表的长度           |");
  printf("\n|          8--显示顺序表内容           |");
  printf("\n|          0--返回                     |");
  printf("\n========================================");
  printf("\n请输入菜单号(0-8)：");
} 

main(){
	LinkList *head; 
	DataType context,returnData;
	int n,i,loc;
	char ch1,ch2,a;
	ch1='y';
	while(ch1=='y'||ch1=='Y'){
		menu();
		scanf("%c",&ch2);
		getchar();
		switch(ch2)
		{
			case '1':
				head = initList();
				printf("请输入建立线性表的个数：");
				scanf("%d",&n);
				createListH(head,n);
				printf("建立的线性表为：");
				showAll(head);
				break;
			case '2':
				head = initList();
				printf("请输入建立线性表的个数：");
				scanf("%d",&n);
				createListL(head,n);
				printf("建立的线性表为：");
				showAll(head);
				break;
	  		case '3':
				printf("请输入要插入的位置：");
				scanf("%d",&i);
				printf("请输入要插入的值：");
				scanf("%d",&context);
				
				if(insertItem(head,context,i)){
					printf ("已成功在第%d的位置上插入%2d,插入后的线性表为: \n",i,context);
					showAll(head);
					break;
				}else{
					printf("输入插入的参数错误!\n");
					break;
				}
			case '4':
				printf("请输入要删除元素的位置: ");
				scanf("%d",&i);
				if(deleteNode(head,i,&returnData)){
					printf ("已成功在第%d的位置上删除%d,删除后的线性表为: \n",i,returnData);
					showAll(head);
				}else{
					printf ("\n输入删除的参数错误!");
				}	
				break;
			case '5':
				printf("请输入要查看表中元素位置(从1开始): ");
				scanf ("%d",&i);
				if (queryDataByIndex(head,i, &returnData))
					printf("当前线性表第%d个元素的值为: %d",i,returnData);
				else
					printf ("输入的位置错误!");
				break;
			case '6':
				printf("请输入要查找的元素值为: ") ;
				scanf("%d",&context) ;
				loc = queryDataByContent(head, context);
				if(loc)
					printf("查找元素值为%d的位置为: %d",context, loc);
				else
					printf ("该表中无此元素!");
				break;
			case '7':
				printf("当前线性表的长度为: %d",lengthList(head));
				break;
			case '8':
				showAll(head); 
				break;
			case '0' :
				ch1='n';
				break;
			default:
				printf("输入有误，请输入0~6进行选择!");
			}
			
		printf("\n");	
		system("pause");		
	}
}

静态链表

参考题目：链表操作

#include <iostream>
using namespace std;
const int MAX = 100005; //静态链表，最大可存储的节点大小
//结构体版本链表-动态链表，由于每次插入需要动态分配空间，效率太低，适合工程开发时使用
//数组模拟链表-静态链表，速度快，适合于算法题
//用数组某一块空间存储内容，数组下标看作这一块空间的指针
//例如：head-头指针存储第一节点的值；e[i]存储节点的值ne[i]存储该节点下一节点地址，i下标作为该节点的地址，idx表明当前已经有多少个节点
int head,e[MAX],ne[MAX],idx;
//初始化链表，头指针为-1，idx为0
void init(){
    head = -1;
    idx = 0;
}
//头插法插入节点
void insert_head(int v){
    //idx表明现在有多少个节点，在进行插入时类似于动态链表分配空间所返回的地址
    //假设：这时idx = 2,那么e[0]ne[0]是第一个节点,e[1]ne[1]是第二个节点，idx=3指向的e[3]ne[3]这时为空
    //这就类比于动态链表动态赋值后所返回的节点地址
    e[idx] = v;             //初始化新节点的值
    ne[idx] = head;         //初始化新节点指向的下一节点地址(头插法)
    head = idx;             //更新头指针指向新节点
    idx++;                  //节点数加1
}
//删除k节点后面的一个节点
void delet(int k){
    ne[k] = ne[ne[k]];      //将k个节点的next指针指向它的下一节点的下一节点
}
//在k个节点后插入一个节点
void insert(int k,int v){
    e[idx] = v;             //首先要开辟这个节点(idx为新节点指针,前面解释过)
    ne[idx] = ne[k];        //新节点的下一节点指向k节点的下一节点
    ne[k] = idx;            //将k节点的下一节点更新为新节点
    idx++;                  //总节点数加1
}
int main(){
    int n;
    cin>>n;
    init();
    while(n--){
        char c;
        cin>>c;
        if(c == 'H'){
            int a;
            cin>>a;
            insert_head(a);
        }
        if(c == 'D'){
            int k;
            cin>>k;
            if(k == 0) head = ne[head];
            else delet(k-1);
        }
        if(c == 'I'){
            int k,v;
            cin>>k>>v;
            insert(k-1,v);
        }
    }
    //从头节点开始遍历，指针指向第一个节点，只要当前节点值不为-1(-1表示结束)则打印该节点值之后更新指针i指向当前节点的下一节点
    for(int i = head;i != -1;i = ne[i]){
        printf("%d ",e[i]);
    }
    return 0;
}

栈

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

const int MAX = 20;	//定义栈的最大存储量 
typedef int DataType;	//定义存储的数据类型 
typedef struct{
	DataType data[MAX];
	int top;			//栈顶的序号 
}SeqStack; 
//初始化栈 
SeqStack *initStack(){
	SeqStack *seqStack = (SeqStack*)malloc(sizeof(SeqStack));
	seqStack->top = -1;
}
//判断栈空
int emptyStack(SeqStack *seqStack){
	if(seqStack -> top == -1){
		return 1;
	}
	return 0;
}
//判断栈满 
int fullSeqStack(SeqStack *seqStack){
	if(seqStack->top == MAX - 1){
		return 1;
	}
	return 0;
}
//入栈
int push(SeqStack *seqStack,DataType data){
	
	if(fullSeqStack(seqStack)){
		printf("栈满,无法添加元素");
		return 0;
	}
	
	seqStack->data[++seqStack->top] = data;
	return 1;
}

//出栈
int pop(SeqStack *seqStack,DataType *data){
	if(emptyStack(seqStack)){
		printf("栈为空");
		return 0;
	}
	*data = seqStack->data[seqStack->top--];
	return 1;
} 
//获取栈顶元素
int getTop(SeqStack *seqStack,DataType *data){
	if(emptyStack(seqStack)){
		printf("栈为空");
		return 0;
	}
	*data = seqStack->data[seqStack->top];
	return 1;
} 
void menu(){
  
  printf("\n栈的各种操作:");
  printf("\n====================================");
  printf("\n|          1--建立栈               |");
  printf("\n|          2--入栈                 |");
  printf("\n|          3--出栈                 |");
  printf("\n|          4--获取栈顶             |");
  printf("\n|          0--返回                 |");
  printf("\n====================================");
  printf("\n请输入菜单号(0-4)：");
} 
int main(){
	char ch1,ch2;
	ch1='y';
	SeqStack *seqStack;
	int context;
	
	while(ch1=='y'||ch1=='Y'){
		menu();
		scanf("%c",&ch2);
		getchar();
		switch(ch2)
		{
			case '1':
				seqStack = initStack(); 
				printf("初始化成功!");
				break;
	  		case '2':
	  			if(seqStack == NULL) {
	  				printf("请先初始化！\n");
	  				break; 
				  }
				printf("请输入入栈元素:");
				scanf("%d",&context);
				getchar();
				if(push(seqStack,context))
					printf("入栈成功\n");
				break;
			case '3':
				if(pop(seqStack,&context)){
					printf ("%d出栈成功 \n",context);
				}
				break;
			case '4':
				if(getTop(seqStack,&context)){
					printf ("栈顶元素为%d \n",context);
				}
				break; 
			case '0' :
				ch1='n';
				break;
			default:
				printf("输入有误，请输入0~6进行选择!");
			}
			
		printf("\n");	
		system("pause");
	}
	return 0;
}

队列

#include<stdio.h>
#include<stdlib.h> 
#define MAX 5
using namespace std;
typedef int DataType;
typedef struct{
	DataType *base;	//base数组，之后动态赋值 
	int front;		//队头 
	int rear;		//队尾 
}SqQueue;

//初始化队列 
SqQueue *initQueue(){
	
	SqQueue *queue = (SqQueue*)malloc(sizeof(SqQueue));	
	queue->base = (DataType*)malloc(MAX*sizeof(SqQueue));	//动态声明数组空间 
	queue->front = 0;				//初始化时对头与对尾指向同一位置 
	queue->rear = 0;
}
//判断队列是否为空 
int isEmpty(SqQueue *queue){
	//如果队头与队尾相同则表明为空 
	if(queue->front == queue->rear) return 1;
	return 0;
}
//判断队列是否满 
int isFull(SqQueue *queue){
	//牺牲一个空间不存储，用于判断队满 
	if((queue->rear+1)%MAX == queue->front) return 1;
	return 0;
}
//入队操作 
int push(SqQueue *queue,DataType data){
	//先判断是否队满 
	if(!isFull(queue)){
		queue->base[queue->rear] = data;
		queue->rear = (queue->rear+1)%MAX;	//更新尾指针，通过取模运算来构建循环队列，解决假溢出情况 
		return 1;
	}
	return 0; 
}
//出队操作 
int pop(SqQueue *queue,DataType *data){
	//先判断是否队空 
	if(!isEmpty(queue)){
		*data = queue->base[queue->front];
		queue->front = (queue->front+1)%MAX;//更新头指针，通过取模运算来构建循环队列，解决假溢出情况
		return 1;
	}
	return 0; 
}
//返回队首元素 
int front(SqQueue *queue,DataType *data){
	//先判断是否队空 
	if(!isEmpty(queue)){
		*data = queue->base[queue->front];
		return 1;
	}
	return 0; 
}
//返回队尾元素 
int rear(SqQueue *queue,DataType *data){
	//先判断是否队空 
	if(!isEmpty(queue)){
		*data = queue->base[(queue->rear-1<0?MAX-1:queue->rear-1)];	//特殊判断一下当尾指针在下标0的情况 
		return 1;
	}
	return 0; 
}
//获取栈的长度
int getLength(SqQueue *queue) {
	return (queue->rear-queue->front+MAX)%MAX;
}
void menu(){
  
  printf("\n队列的各种操作:");
  printf("\n====================================");
  printf("\n|          1--建立队列             |");
  printf("\n|          2--入队                 |");
  printf("\n|          3--出队                 |");
  printf("\n|          4--获取队首元素         |");
  printf("\n|          5--获取队尾元素         |"); 
  printf("\n|          6--获取队长度           |"); 
  printf("\n|          0--返回                 |");
  printf("\n====================================");
  printf("\n请输入菜单号(0-6)：");
} 
int main(){
	char ch1,ch2;
	ch1='y';
	SqQueue *queue = NULL; 
	DataType context;
	
	while(ch1=='y'||ch1=='Y'){
		menu();
		scanf("%c",&ch2);
		getchar();
		switch(ch2)
		{
			case '1':
				queue = initQueue(); 
				printf("初始化成功!");
				break;
	  		case '2':
	  			//如果未初始化就不继续执行 
	  			if(queue == NULL) {
	  				printf("请先初始化！\n");
	  				break; 
				}
				printf("请输入入队元素:");
				scanf("%d",&context);
				getchar();
				if(push(queue,context))
					printf("入队成功\n");
				else 
					printf("队满"); 
				break;
			case '3':
				if(pop(queue,&context)){
					printf ("%d出队成功 \n",context);
				}else 
					printf("队空");
				break;
			case '4':
				if(front(queue,&context)){
					printf ("队首元素为%d \n",context);
				}else 
					printf("队空");
				break; 
			case '5':
				if(rear(queue,&context)){
					printf ("队尾元素为%d \n",context);
				} else 
					printf("队空");
					break;
			case '6':
				printf ("队长为%d \n",getLength(queue));
				break; 
			case '0' :
				ch1='n';
				break;
			default:
				printf("输入有误，请输入0~6进行选择!");
			}
			
		printf("\n");	
		system("pause");
	}
	return 0;
}

HashTable

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 20
#define OK 1
#define FALSE 0

//定义存储个人信息的结构体 
typedef struct{
	char name[20];	//姓名 
	char phone[20];	//电话 
	char location[30];	//地址 
}Person;

//定义散列表HashTable
typedef struct{
	Person* array[MAXSIZE];	//存储联系人的动态数组 
	int count;		//当前表中元素总个数 
}HashTable; 

//将电话号码处理为key 
int GetKey(char phone[]){
	//将电话号码的每一位数字加起来即为key
	int key=0;
	int i=0;
	while(phone[i] != '\0') {
		key += phone[i]-'0';
		i++;
	}
//	printf("key = %d\n",key);
	return key;
} 
//散列函数 传入key返回存储的位置l=Hash(key) 
int Hash(int key){
	return key%19;	//采用除留余数法,由于表长为20,除数一般为小于或等于表长的最大质数，所以这里为19 
} 

//初始化散列表
HashTable* InitHashTable(){
	HashTable *hashTable = NULL;
	hashTable = (HashTable*)malloc(sizeof(HashTable));
	hashTable->count = 0;	//初始化时hash表中没有元素 
	int i;
	for(i=0;i<MAXSIZE;i++){
		hashTable->array[i] = NULL; //为每个位置的电话初始化为-1
	}
} 
//int Save()
//int HandleCollision(HashTable *hashTable,Person person,int loc){
//	
//}
//插入数据
int Insert(HashTable *hashTable,Person *person){
	int key = GetKey(person->phone);
	int loc = Hash(key);//获取在hash表中的位置
	 
	if(hashTable->array[loc] == NULL){
		//如果该位置为空，就将联系人存储到此处
		hashTable->array[loc] =  person;
		hashTable->count++;
		return OK;
	}else{
		//如果该位置不为空，则出现散列表冲突，采用二次探测再散列方式处理
		int j=1;
		int k=0;
		while(1){
			int newLoc = -1;
			if(k%2 == 0){
				newLoc = loc + j*j;
				k++;
			}else{
				newLoc = loc - j*j;
				j++;
				k++;
				if(newLoc < 0){
					//相减时要考虑负数，负数无法取模 
					continue;
				}
			}
			if(newLoc>MAXSIZE){
				//数组越界
				return FALSE; 
			}
			if(hashTable->array[newLoc] == NULL){
				//如果该位置为空，就将联系人存储到此处
				hashTable->array[newLoc] =  person;
				hashTable->count++;
				return OK;
			}
		}
	}	
} 

//查找数据
Person* Find(HashTable *hashTable,char phone[]){
	int loc = Hash(GetKey(phone));//获取在hash表中的位置
	if(hashTable->array[loc] == NULL){
		return NULL;
	} 
	if(!strcmp(hashTable->array[loc]->phone,phone)){
		//如果该位置的值等于查询的值，就将联系人返回 
		return hashTable->array[loc]; 
	}else{
		//出现散列表冲突，采用二次探测再散列方式处理
		int j=1;
		int k=0;
		while(1){
			int newLoc = -1;
			if(k%2 == 0){
				newLoc = loc + j*j;
				k++;
			}else{
				newLoc = loc - j*j;
				j++;
				k++;
				if(newLoc < 0){
					//相减时要考虑负数，负数无法取模 
					continue;
				}
			}
			if(newLoc>MAXSIZE || hashTable->array[newLoc] == NULL){
				//未找到联系人 
				return NULL;
			}
			
			if(!strcmp(hashTable->array[newLoc]->phone,phone)){
				//如果该位置的值等于查询的值，就将联系人返回 
				return hashTable->array[newLoc]; 
			}
		}
	}
}

//展示所有联系人,由于数组写死，所以最大存储为MAXSIZE，可自行升级为动态数组 
void ShowAll(HashTable *hashTable){
	if(hashTable){
		int i;
		printf("一共有%d条记录:\n",hashTable->count);
		for(i=0;i<MAXSIZE;i++){
			if(hashTable->array[i] != NULL){
				printf("姓名：%s\t电话：%s\t地址：%s\t\n",hashTable->array[i]->name,hashTable->array[i]->phone,hashTable->array[i]->location);
			}
		}
		printf("加载完毕！");
		system("pause");
	}else{
		printf("请先建立联系簙！");
		system("pause"); 
	}
}

void menu(){
  
  printf("\n请选择操作");
  printf("\n========================================");
  printf("\n|          1--建立联系簙               |");
  printf("\n|          2--添加联系人               |");
  printf("\n|          3--查找联系人               |");
  printf("\n|          4--显示所以联系人           |");
  printf("\n|          0--退出                     |");
  printf("\n========================================");
  printf("\n请输入菜单号(0-4)：");
} 

void main(){
	HashTable *hashTable = NULL;
	while(1){ 
		menu(); 
		int i; 
		scanf("%d",&i);
		if(i == 1){
			hashTable = InitHashTable();
			printf("建立成功！");
			system("pause");
		}else if(i == 2){
			if(hashTable == NULL){
				printf("请先建立联系簙！");
				system("pause"); 
				continue;
			}
			Person *p = NULL;
			p = (Person*)malloc(sizeof(Person));
			printf("输入电话号码："); 
			scanf("%s",p->phone);
			printf("输入姓名：");
			scanf("%s",p->name);
			printf("输入地址：");
			scanf("%s",p->location);
			
			Insert(hashTable,p);
			printf("添加成功!\n");
			printf("姓名：%s\t电话：%s\t地址：%s\t\n",p->name,p->phone,p->location);
			system("pause"); 
		} else if(i == 3){
			if(hashTable == NULL){
				printf("请先建立联系簙！");
				system("pause"); 
				continue;
			}
			char phone[20];
			printf("输入待查找号码：");
			scanf("%s",phone); 
			Person *findPerson = Find(hashTable,phone); 
			if(findPerson){
				printf("查询成功:\n"); 
				printf("姓名：%s\t电话：%s\t地址：%s\t\n",findPerson->name,findPerson->phone,findPerson->location);
				system("pause");
			}else{
				printf("未查询到该联系人！");
				system("pause");
			}
		  	
		}else if(i == 4){
			ShowAll(hashTable);
		}else if(i == 0){ 
		  	printf("成功退出系统！"); 
		  	break; 
		} else{
		   printf("指令错误！");
		   system("pause");
		}
	}
	return;
}

串

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 200

typedef struct {
	char ch[MAXSIZE + 1]; //永远预留一个'\0'的位置
	int len;			//串的长度 
}String;

//更新串的长度,并返回 
int updateLen(String *s){
	int i = 0;
	while(s->ch[i] != '\0') i++;
	s->len = i;
	return (s->len);
} 

//创建串
String* creatStr(){
	String *s = (String*)malloc(sizeof(String));
	gets(s->ch);
	updateLen(s); 
	return s;
} 

//求子串
int subStr(String *s,String *sub,int index,int len){
	//判断位置和长度是否符合要求
	if(index < 0 || index > s->len - 1 || len > s->len || len > s->len - index){
		printf("位置或长度错误"); 
		return 0; //返回0则操作失败 
	}	
	for(int i = 0; i < len; i++){
		sub->ch[i] = s->ch[i+index];
	}
	sub->ch[len] = '\0';		//求得子串后将下一位赋值为'\0' 
	sub->len = len;
	return 1; //操作成功 
} 

//重要操作1：删除子串
int deleteStr(String *s, int index, int len){
	//判断下标和长度是否符合要求
	if(index < 0 || index > s->len - 1|| len > s->len || len > s->len - index){
		printf("位置或长度错误"); 
		return 0; //返回0则操作失败 
	}
	
	for(int i = index + len; i< s->len; i++){
		s->ch[i-len] = s->ch[i];
	}
	s->len = s->len - len;		//更新串长度 
	s->ch[s->len] = '\0';		//标上串结束字符 
	return 1;
} 

//重要操作2：添加子串
int insertStr(String *s, String *addStr,int index){
	if(index < 0||index > (s->len - 1)){
		printf("位置错误"); 
		return 0;
	}
	if(s->len + addStr->len > MAXSIZE){
		printf("超过最大存储长度");
		return 0;
	} 
	
	//1.为待加入的串挪出空位
	for(int i = s->len - 1; i>= index; i--){
		s->ch[i+addStr->len] = s->ch[i];
	}
	//2.将串加入主串 
	for(int k = 0; k < addStr->len;k++){
		s->ch[k+index] = addStr->ch[k];
	} 
	//3.更新串信息
	s->ch[s->len+addStr->len] = '\0';
	s->len =  s->len+addStr->len;
	return 1;
} 

//重要操作3：从某一位置开始进行子串匹配,返回查询到的第一个子串的首字符下标，未找到返回-1 
int  indexStr(String *s, String *cmpStr,int index){
	if(index < 0||index > (s->len - 1)){
		printf("位置错误"); 
		return -1;
	}
	int i = index,j = 0;
	while(i< s->len&& j< cmpStr->len){
		if(s->ch[i] == cmpStr->ch[j]){
			i++;
			j++;
		}else{
			i = i-j+1;
			j = 0;
		}
	}
	//查询到子串时j == cmpStr-> len 
	if(j>= cmpStr->len){
		return i-cmpStr->len;
	}
	
	//未查询到 
	return -1;
} 

//替换子串,返回成功替换的个数 
int replaceStr(String *s,String *repStr,String *aimStr){
	int p = 0,count = 0;
	//串中可能包含多个待替换子串所以用循环 
	do{
		//1.查询待替换子串下标
		int index = indexStr(s,repStr,p);
		if(index != -1){
			//可能目标子串替换后长度超过最大长度，所以进行判断 
			if(s->len-repStr->len+aimStr->len>MAXSIZE){
				return count;
			}
			//2.删除该子串
			deleteStr(s,index,repStr->len);
			//3.插入目标串 
			insertStr(s,aimStr,index);
			//4.更新p 
			p = index;
			p+=aimStr->len;
			//5.更新主串长度
			count++;
		}
		//如果剩余的子串长度足够进行替换则继续进行匹配 
	}while(s->len - p >= aimStr->len);
	return count; 
}
//连接两串 
int catStr(String *s,String *t){
	//两串长度和小于等于最大值则可以完全连接
	if(s->len + t->len <= MAXSIZE){
		for(int i = 0;i<t->len;i++){
			s->ch[i+s->len] = t->ch[i];
		}
		s->ch[s->len+t->len] = '\0'; //更新结束标志
		s->len += t->len; 
	} else{
		//两串长度和大于最大值
		for(int i = s->len;i<MAXSIZE;i++){
			s->ch[i] = t->ch[i-s->len];
		} 
		
		s->ch[MAXSIZE] = '\0'; //更新结束标志
		s->len = MAXSIZE;
	}
	return 1;
}

//比较两串是否相等，长度不相等返回长度差，长度相等返回第一次不相等字符的ascll码差值
int cmpStr(String *s,String *cmp){
	if(s->len != cmp->len){
		return s->len - cmp->len;
	}else{
		int i = 0;
		while(i<s->len || i<cmp->len){
			if(s->ch[i] != cmp->ch[i]){
				return s->ch[i] - cmp->ch[i];
			}
			i++;
		}
	}
	return 0;
} 

//显示串 
void showStr(String *s){
	int i = 0;
	while(s->ch[i] != '\0') printf("%c",s->ch[i++]);
	printf(",串长为%d\n",s->len);
}

//kmp算法
void getNext(String *t,int *next){
	int i = 0,k = -1;
	next[i] = k;
	while(i<t->len){
		if(k == -1 || t->ch[k] == t->ch[i]){
			k++;
			i++;
			next[i] = k;
		}else{
			k = next[k];
		}
	}
	for(int l = 0;l<t->len;l++){
		printf("%d ",next[l]);
	}
} 

int kmp(String *s,String *p,int index){
	int i = index,j = 0;
	int next[MAXSIZE];
	getNext(p,next);
	while(i<s->len && j<p->len){
		if( j==-1 || s->ch[i] == p->ch[j]){
			i++;
			j++;
		}else{
			j = next[j];
		}
	}
	if(j >= p->len){
		return i-p->len;
	}
	return -1;
	
}

//菜单
 void menu(){
  
  printf("\n顺序表的各种操作");
  printf("\n========================================");
  printf("\n|          1--创建串                   |");
  printf("\n|          2--求子串                   |");
  printf("\n|          3--删除子串                 |");
  printf("\n|          4--添加子串                 |");
  printf("\n|          5--子串定位                 |");
  printf("\n|          6--替换子串                 |");
  printf("\n|          7--串的连接                 |");
  printf("\n|          8--串的比较                 |");
  printf("\n|          9--显示主串                 |");
  printf("\n|          0--返回                     |");
  printf("\n========================================");
  printf("\n请输入菜单号(0-8)：");
} 
 
int main(){
	char ch1,ch2;
	String tempString;		//默认空串 
	tempString.ch[0] = '\0';
	String *s = &tempString;
	ch1='y';
	int context;
	
	while(ch1=='y'||ch1=='Y'){
		menu();
		scanf("%c",&ch2);
		getchar();
		switch(ch2)
		{
			case '1':
				{
					printf("请输入要存储的字符串："); 
					s = creatStr();
					printf("创建字符串成功!\n");
					showStr(s);
				}
				break;
	  		case '2':
	  			{
	  				printf("主串为：");
	  				showStr(s);
	  				String *sub = (String*)malloc(sizeof(String));
					printf("\n请输入从第几个字符求子串(下标从0开始):");
					int index;
					scanf("%d",&index);
					getchar();
					printf("请输入求取的长度：");
					int len;
					scanf("%d",&len);
					getchar();
	  				int sign = subStr(s,sub,index,len);
	  				if(sign){
	  					printf("操作成功!,子串为：");
						showStr(sub);	
					}
	  				
				}
				break;
			case '3':
				{
					printf("主串为：");
	  				showStr(s);
					printf("\n请输入从第几个字符删除(下标从0开始):");
					int index;
					scanf("%d",&index);
					getchar();
					printf("请输入删除的长度：");
					int len;
					scanf("%d",&len);
					getchar();
	  				int sign = deleteStr(s,index,len);
	  				if(sign){
	  					printf("操作成功!,主串为：");
						showStr(s);	
					}
				}
				break;
				case '4':
				{
					printf("主串为：");
	  				showStr(s);
	  				printf("\n请输入插入的子串:");
	  				String *addStr = creatStr();
					printf("\n请输入插入的位置(下标从0开始):");
					int index;
					scanf("%d",&index);
					getchar();
	  				int sign = insertStr(s,addStr,index);
	  				if(sign){
	  					printf("操作成功!,主串为：");
						showStr(s);	
					}
				}
				break;
				case '5':
				{
					printf("主串为：");
	  				showStr(s);
	  				printf("\n请输入要查询的子串:");
	  				String *cmpStr = creatStr();
					printf("\n请输入从第几个字符开始查找(下标从0开始):");
					int index;
					scanf("%d",&index);
					getchar();
	  				//int sign = indexStr(s,cmpStr,index);
	  				int sign = kmp(s,cmpStr,index);
	  				if(sign != -1){
	  					printf("子串在%d第一次出现.",sign);
					}else{
						printf("未找到.");
					}
				}
				break;
				case '6':
				{
					printf("主串为：");
	  				showStr(s);
	  				printf("\n请输入要替换的子串:");
	  				String *repStr = creatStr();
					printf("\n请输入要替换为目标子串:");
	  				String *aimStr = creatStr();
	  				int count = replaceStr(s,repStr,aimStr);
	  				printf("替换后的主串为："); 
	  				showStr(s);
	  				printf("***成功替换%d个子串***",count);
				}
				break;
				case '7':
				{
					printf("主串为：");
	  				showStr(s);
	  				printf("\n请输入要连接的串:");
	  				String *str = creatStr();
	  				catStr(s,str);
	  				printf("连接后的串为：");
	  				showStr(s);
				}
				break;
				case '8':
				{
					printf("主串为：");
	  				showStr(s);
	  				printf("\n请输入要比较的子串:");
	  				String *str = creatStr();
	  				int sign = cmpStr(s,str);
	  				if(sign == 0){
	  					printf("两串相等");
					}else{
						printf("两串不相等");
					}
				}
				break;
				case '9':
				{
					printf("主串为：");
	  				showStr(s);
				}
				break;
			case '0' :
				ch1='n';
				break;
			default:
				printf("输入有误，请输入0~8进行选择!");
			}
			
	}
	return 0;
}

树

二叉树

#include <stdio.h>
#include <stdlib.h> 
//二叉树
typedef struct Tree{
	char data;
	struct Tree *lchild;		//左孩子
	struct Tree *rchild;		//右孩子 
}BT; 

//递归构建二叉树(先序序列构建二叉树)
//递归理解：将整个构树过程分为四步
//1.构建根节点
//2.构建左子树(递归建树) 
//3.构建右子树(递归建树) 
//4.返回根节点 
//递归结束条件为：没有左或右孩子(输入'0') 
BT *creatBT(){
	BT *bt;
	//没有左或右孩子(输入'0')，输入0则树节点为NULL 
	char ch = '0'; 
	scanf("%c",&ch);
	getchar();
	//递归结束条件 
	if(ch == '0'){
		bt = NULL;
	} else{
		//第一步构建根节点
		bt = (BT*)malloc(sizeof(BT));
		bt->data = ch;
		//第二步构建左子树(递归建树) 
		printf("请输入%c节点的左孩子节点(无节点输入0):",bt->data); 
		bt->lchild = creatBT();
		//第三步构建右子树(递归建树)  
		printf("请输入%c节点的右孩子节点(无节点输入0):",bt->data); 
		bt->rchild = creatBT();
	}
	//第四步返回所创建的根节点 
	return bt;
} 
//递归先序遍历 (先序遍历时第一个元素肯定是根节点)
//递归理解：将整个遍历树过程分为三步
//1.输出根节点 
//2.遍历左子树(递归遍历) 
//3.遍历右子树(递归遍历) 
//递归结束条件为：没有左或右孩子
void preOrderShowBT(BT *bt){
	if(bt == NULL){
		return;
	} 
	//第一步输出根节点 
	printf("%c ",bt->data);
	//第二步遍历左子树(递归遍历)  
	preOrderShowBT(bt->lchild); 
	//第三步遍历右子树(递归遍历) 
	preOrderShowBT(bt->rchild); 
}
//递归中序遍历 
//递归理解：将整个遍历树过程分为三步
//1.遍历左子树(递归遍历) 
//2.输出根节点 
//3.遍历右子树(递归遍历) 
//递归结束条件为：没有左或右孩子
void midOrderShowBT(BT *bt){
	if(bt == NULL){
		return;
	} 
	//第一步遍历左子树(递归遍历)
	midOrderShowBT(bt->lchild); 
	//第二步输出根节点  
	printf("%c ",bt->data);
	//第三步遍历右子树(递归遍历)
	midOrderShowBT(bt->rchild); 
}
//递归后序遍历(后序遍历时最后一个元素肯定是根节点)
//递归理解：将整个遍历树过程分为三步
//1.遍历左子树(递归遍历)  
//2.遍历右子树(递归遍历) 
//3.输出根节点
//递归结束条件为：没有左或右孩子
void postOrderShowBT(BT *bt){
	if(bt == NULL){
		return;
	} 
	//第一步遍历左子树(递归遍历)
	postOrderShowBT(bt->lchild); 
	//第二步遍历右子树(递归遍历) 
	postOrderShowBT(bt->rchild); 
	//第三步输出根节点
	printf("%c ",bt->data);
}
//树的层次遍历
//算法实现：需要用到一个队列(这里使用循环队列，所以对树的层数有限制)，首先把根节点加入队列中 然后循环出队，
//每出队一个元素就将它的左孩子和右孩子入队，为空则不入队，直到队列为空 
//如果最大可遍历树的层数为4那么数组大小应该设置为2^(k-1)+1,加一是给循环队列用于处理队满的情况 
void levelOrderShowBT(BT *bt){
	const int MAX = 9;
	BT *btQueue[MAX],*tempBt = NULL;		//队列数组，临时节点 
	int front,rear;						//队首指针与队尾指针
	btQueue[0] = bt;					//将根节点入队
	front = 0,rear = 1;					//更新指针
	
	while(front != rear) {
		tempBt = btQueue[front];		//将队首出队
		front = (front + 1)%MAX;
			
		printf("%c ",tempBt->data);
		
		if(tempBt->lchild != NULL){
			btQueue[rear] = tempBt->lchild;	//如果不为空则将左孩子加入队列 
			rear = (rear + 1 ) % MAX;
		}
		if(tempBt->rchild != NULL){
			btQueue[rear] = tempBt->rchild;	//如果不为空则将右孩子加入队列 
			rear = (rear + 1 ) % MAX;
		}	
	}
}
//树的重建(前序+中序)
//算法实现：(首先要知道前序遍历所得到的数组首元素肯定为待建树的根节点)
//我们先判断当前待建树的节点是否为0，没有节点肯定无法建树，有节点先建立树的根节点，将前序数组的首元素存入根节点中
//然后遍历中序数组，查找到该根元素(前序数组首元素)所在位置(下标i)，根据中序遍历的性质可以知道，元素左方是左子树，右方是右子树
//下标i即为左子树长度，比如前序为a,b,c =中序为b,a,c.可知根元素是a，然后遍历中序数组，找到a,下标为1，左子树长度也为1.
//接下来则递归建树，构建左子树(buidBT(左子树所在前序数组,左子树所在中序数组,根节点左孩子,左子树节点数))，构建右子树(buidBT(右子树所在前序数组,右子树所在中序数组,根节点右孩子右子树节点数))
//总之递归算法就是三步：
//1.构建根节点
//2.递归构建左子树 
//3.递归构建右子树
//递归退出条件为待构建树长度为0 
void buildBT(char *pre,char *mid,BT **bt,int len){	//pre前序数组，mid中序数组，bt建树节点指针的指针，len待建树节点 
	//待构建树的长度为0则结束递归 
	if(len == 0){
		*bt = NULL;	//没有子节点则赋值NULL 
		return;
	}
	//第一步，构建根节点 
	int i;
	*bt = (BT*)malloc(sizeof(BT));
	//printf("%c",*pre);
	(*bt)->data=*pre;	//*pre，pre是数组首地址，*pre即取其值类似于pre[0] 
	for(i=0;i<len;i++){
		//在中序数组中循环遍历根的位置 
		if(mid[i] == *pre){
			//找到则break，这时i即为根在中序数组中的位置 
			break;
		}
	}
	//第二步，构建左子树 
	//pre+1，表明左子树所在先序遍历数组的首地址，他和最后一个参数i可以确定左子树的前序数组 
	//mid，左子树所在中序遍历数组的首地址，他和参数i可以确定左子树的中序数组
	//i子树长度 
	buildBT(pre+1,mid,&((*bt)->lchild),i);				
	//第三步，构建右子树 
	//pre+1+i，表明右子树所在先序遍历数组的首地址，他和最后一个参数len-i-1可以确定右子树的前序数组 
	//mid+i+1，右子树所在中序遍历数组的首地址，他和参数len-i-1可以确定左子树的中序数组
	//len-i-1,子树长度
	buildBT(pre+i+1,mid+i+1,&((*bt)->rchild),len-i-1);
	
	//自行举例..... 
} 
//后序加中序 
void postMidBuildBT(char *post,char *mid,BT **bt,int len) {
	if(len == 0){
		*bt = NULL;
		return;
	}
	
	*bt = (BT*)malloc(sizeof(BT));
	(*bt)-> data = post[len-1];
	int i;
	for(i = 0; i < len; i++){
		if(post[len-1] == mid[i]){
			break;
		}
	}
	postMidBuildBT(post,mid,&((*bt)->lchild),i);
	postMidBuildBT(post+i,mid+i+1,&((*bt)->rchild),len-i-1);
}

//求节点总数
int getAllNodeCount(BT *bt){
	int count = 0;
	//结束条件，左或右子树节点数量为0 
	if(bt == NULL){
		return 0; 
	}
	//递归获取左子树的数量
	int l = getAllNodeCount(bt->lchild);
	//递归获取右子树的数量
	int r = getAllNodeCount(bt->rchild);
	count = l+r+1;		//总数为左子树数量加右子树数量加一个根节点 
	return count;
}
//求树深度 
int getDepth(BT *bt){
	//结束条件，左或右子树节点数量为0
	if(bt == NULL){
		return 0;
	}
	//求左子树深度 
	int l = getDepth(bt->lchild);
	//求右子树深度 
	int r = getDepth(bt->rchild);
	int depth = 0;
	//取最大的子树深度 
	if(l >= r){
		depth+=l;
	} else{
		depth+=r;
	}
	//最后深度加1则为最终树的深度 
	return ++depth;
} 
void menu(){
  
  printf("\n树的各种操作");
  printf("\n========================================");
  printf("\n|          1--建立二叉树               |");
  printf("\n|          2--重建二叉树(前序+中序)    |");
  printf("\n|          3--重建二叉树(后序+中序)    |");
  printf("\n|          4--先序遍历                 |");
  printf("\n|          5--中序遍历                 |");
  printf("\n|          6--后序遍历                 |");
  printf("\n|          7--层次遍历                 |");
  printf("\n|          8--求树总节点数             |");
  printf("\n|          9--求树深度                 |");
  printf("\n|          0--返回                     |");
  printf("\n========================================");
  printf("\n请输入菜单号(0-9)：");
} 
int main(){ 
	BT *bt = NULL;
	int context;
	int n,i,loc,x;
	char ch1,ch2,a;
	ch1='y';
	while(ch1=='y'||ch1=='Y'){
		menu();
		scanf("%c",&ch2);
		getchar();
		switch(ch2)
		{
			case '1':{
				printf("请输入根节点:");
				bt = creatBT(); 
				preOrderShowBT(bt);
				break;
			}
	  		case '2':{
	  			BT *newBt = NULL;
	  			char pre[100],mid[100]; 
	  			printf("请输入先序数组：");
				scanf("%s",pre);
				getchar();
				printf("请输入中序数组：");
				scanf("%s",&mid);
				getchar();
				int i = 0,j = 0;
				for(;pre[i]!='\0'&&mid[j]!='\0';i++,j++){}
				if(pre[i] == mid[j]){
					//printf("%d\n",i);
					buildBT(pre,mid,&newBt,i);
					//建树成功输出其后序遍历 
					postOrderShowBT(newBt);
					//printf("mdfk\n"); 
				}else{
					printf("先序数组与后序数组长度不一致!\n");
				}
				break;
			}
			case '3':{
	  			BT *newBt = NULL;
	  			char post[100],mid[100]; 
	  			printf("请输入后序数组：");
				scanf("%s",post);
				getchar();
				printf("请输入中序数组：");
				scanf("%s",mid);
				getchar();
				int i = 0,j = 0;
				for(;post[i]!='\0'&&mid[j]!='\0';i++,j++){}
				if(post[i] == mid[j]){
					postMidBuildBT(post,mid,&newBt,i);
					//建树成功输出其先序遍历
					preOrderShowBT(newBt);
				}else{
					printf("后序数组与后序数组长度不一致!\n");
				}
				break;
			}
			case '4':
				if(bt){
					preOrderShowBT(bt);
				} else {
					printf("请先建一颗树吧！");
				}	
				break;
			case '5':
				if(bt){
					midOrderShowBT(bt);
				} else {
					printf("请先建一颗树吧！");
				}
				break;
			case '6':
				if(bt){
					postOrderShowBT(bt);
				} else {
					printf("请先建一颗树吧！");
				}
				break;
			case '7':
				if(bt){
					levelOrderShowBT(bt);
				} else {
					printf("请先建一颗树吧！");
				}
				break;
			case '8':
				if(bt){
					printf("树一共有%d个节点",getAllNodeCount(bt));
				} else {
					printf("请先建一颗树吧！");
				}
				break;
			case '9':
				if(bt){
					printf("树的深度为:%d",getDepth(bt));
				} else {
					printf("请先建一颗树吧！");
				}
				break;
			case '0' :
				ch1='n';
				break;
			default:
				printf("输入有误，请输入0~6进行选择!");
			}
		printf("\n");
		system("pause");	
	}
	return 0;
}

图

#include <iostream>
#include <stdlib.h>
#include <limits.h>
using namespace std;
const int MAX = 100;	//最大存储节点
typedef char DataType;	//节点的数据类型 
typedef int EdgeType;	//边类的数据类型 
bool v[MAX];	//图搜索记录数组

//MyEdgesGraph-邻接矩阵表示图 
typedef struct{
	int nodeNum,edgeNum;	//节点总数量，边总数量 
	DataType vexs[MAX];		//存储所有节点的数组 
	int edges[MAX][MAX];	//邻接矩阵	 
}MyEdgesGraph; 

typedef struct ArcNode{
	int vertexIndex;			//节点下标 
	int arcData;				//权重 
	struct ArcNode *nextArc;	//下邻接点 
}ArcNode;//存储边关系的节点

typedef struct VertexNode{
	DataType data;				//头节点信息 
	ArcNode *first;				//表头指针,指向它的边 
}VertexNode;//存储顶点的节点
	 
//AdjList-邻接表表示图 
typedef struct{
	int nodeNum,edgeNum;		//邻接表的节点数，边数 
	VertexNode vertexNode[MAX]; //邻接表数组 
}AdjList; 

MyEdgesGraph *createEdgesGraph(){
	//判断是有向图输入还是无向图输入 
	printf("请确认是无向图还是有向图？(1.无向，2.有向):");
	int choose;
	scanf("%d",&choose);
	getchar();
	if(choose != 1 && choose != 2) return NULL;	//如果输入不为1或者2，直接退出方法 
	
	MyEdgesGraph *graph = (MyEdgesGraph*)malloc(sizeof(MyEdgesGraph));	//动态申请一块空间用于邻接矩阵存储图 
	printf("请输入有多少个节点:");
	scanf("%d",&graph->nodeNum);	//存储节点数 
	getchar();						//getchar()用于读取缓存区的回车，防止后续读取字符出错 
	printf("请输入有多少条边:");
	scanf("%d",&graph->edgeNum);	//存储边数 
	getchar();
	
	printf("请输入每个节点信息:");
	char c;
	int i=1; 
	while(1){						//存储节点信息 
		c = getchar();
		graph->vexs[i++] = c;
		if(i>graph->nodeNum) break;
	}
	getchar();	
	
	if(choose == 1){
		//无向图 
		printf("请输入边(节点编号,节点编号):");
		int x,y;	//临时存储节点编号 
		for(int i = 1; i<=graph->edgeNum; i++){
			scanf("%d,%d",&x,&y);
			getchar();
			graph->edges[x][y] = 1;		//将边标记 
			graph->edges[y][x] = 1;		//无向图,矩阵具有对称性 
		}  
			
	} else if(choose == 2){
		//有向图
		//先将矩阵初始化为最大值 
		for(int i = 1;i<=graph->nodeNum;i++){
			for(int j = 1;j<=graph->nodeNum;j++){
				graph->edges[i][j] = INT_MAX;
			}
		} 
		printf("请输入边(节点编号,节点编号,权重):");
		int x,y,w;	//临时存储节点编号与权重 
		for(int i = 1; i<=graph->edgeNum; i++){
			scanf("%d,%d,%d",&x,&y,&w);
			getchar();
			graph->edges[x][y] = w;	//将边标记为权重 
		}  
	}
	printf("创建成功!");
	return graph;
}
void showEdges(MyEdgesGraph *graph){
	printf("该图的邻接矩阵为：\n");
	printf("  ");
	for(int i = 1;i<=graph->nodeNum;i++)
		printf("%c   ",graph->vexs[i]);
	printf("\n");
	for(int i = 1;i<=graph->nodeNum;i++){
		printf("%c ",graph->vexs[i]);
		for(int j = 1;j<=graph->nodeNum;j++){
			if(graph->edges[i][j] == INT_MAX){
				printf("∞  ");
			}else
				printf("%d   ",graph->edges[i][j]);
		}
		cout<<endl;
	}
	printf("节点数:%d",graph->nodeNum);
	printf("\n边数:%d",graph->edgeNum);
}
AdjList *createAdjList(){
	//判断是有向图输入还是无向图输入 
	printf("请确认是无向图还是有向图？(1.无向，2.有向):");
	int choose;
	scanf("%d",&choose);
	getchar();
	if(choose != 1 && choose != 2) return NULL;			//如果输入不为1或者2，直接退出方法
	
	AdjList *graph = (AdjList*)malloc(sizeof(AdjList));	//动态声明一块空间存储邻接表 
	printf("请输入有多少个节点:");
	scanf("%d",&graph->nodeNum);						//存储节点数 
	getchar();
	printf("请输入有多少条边:");						
	scanf("%d",&graph->edgeNum);						//存储边数 
	getchar();
	
	printf("请输入每个节点信息:");
	char c;
	int i=1; 
	while(1){											//存储边信息 
		c = getchar();
		graph->vertexNode[i].first = NULL;
		graph->vertexNode[i++].data = c;
		if(i>graph->nodeNum) break;
	}
	getchar();
	
	if(choose == 1){
		//无向边 
		printf("请输入边(节点编号,节点编号,权重):");
		int x,y,z;		//节点编号,节点编号,权重
		for(int i = 1; i<=graph->edgeNum; i++){
			scanf("%d,%d,%d",&x,&y,&z);
			getchar();
			ArcNode *node = (ArcNode*)malloc(sizeof(ArcNode));		//动态声明一块空间存储边关系 
			//先存储该边信息 
			node->vertexIndex = y;									//边相连的另一边 
			node->arcData = z;										//存储权重 
			//采用头插法，将头节点与边相连接 
			node->nextArc = graph->vertexNode[x].first;				 
			graph->vertexNode[x].first = node;
			//无向图所以可以x->y和y->x
			ArcNode *node1 = (ArcNode*)malloc(sizeof(ArcNode));
			node1->vertexIndex = x;
			node1->arcData = z;
			node1->nextArc = graph->vertexNode[y].first;
			graph->vertexNode[y].first = node1;
		}  
			
	} else if(choose == 2){
		printf("请输入边(节点编号,节点编号,权重):");
		int x,y,z;
		for(int i = 1; i<=graph->edgeNum; i++){
			scanf("%d,%d,%d",&x,&y,&z);
			getchar();
			ArcNode *node = (ArcNode*)malloc(sizeof(ArcNode));
			
			node->vertexIndex = y;
			node->arcData = z;
			node->nextArc = graph->vertexNode[x].first;
			graph->vertexNode[x].first = node;
			
		}  
	}
	printf("创建成功!");
	return graph;
	
}
void showAdjList(AdjList *graph){
	for(int i = 1;i<=graph->nodeNum;i++){
		printf("下标:%d 节点:%c 边:",i,graph->vertexNode[i].data);
		ArcNode *node = graph->vertexNode[i].first;
		while(node != NULL){
			printf(" (%d,%d)",node->vertexIndex,node->arcData);
			node = node->nextArc;
		}
		printf("\n");
	}
}

void dfs_adjList(AdjList *graph,int index){
	printf("%c ",graph->vertexNode[index].data);			//打印当前节点信息 
	v[index] = true;										//设置当前节点已经访问 
	ArcNode *node = graph->vertexNode[index].first;			//获取与该点相连的边 
	while(node != NULL){									//如果有边则将边相连的另一节点递归遍历 
		if(!v[node->vertexIndex])							//但是，与边相连的另一节点要没有遍历过才递归调用 
			dfs_adjList(graph,node->vertexIndex);
		node = node->nextArc;								//更新当前节点的边 
	}
}
void dfs_edges(MyEdgesGraph *graph,int index){
	printf("%c ",graph->vexs[index]);						//打印当前节点信息 
	v[index] = true;										//设置当前节点已经访问 
	for(int i = 1;i<=graph->nodeNum;i++){					//循环遍历矩阵 
		if(graph->edges[index][i] != 0 && !v[i] && graph->edges[index][i] != INT_MAX){//如果有边则将边相连的另一节点递归遍历 
			if(!v[i])										//但是，与边相连的另一节点要没有遍历过才递归调用 
				dfs_edges(graph,i);//递归 
		}
	}
}
void bfs_adjList(AdjList *graph,int index){

	int q[MAX],front = 0,rear = 0;	//循环队列 
	int nowNode,nextNode;			//当前节点与下一节点
	q[rear++] = index;				//将index入队 
	v[index] = true;				//设置当前节点已经访问 
	while(front != rear){			//队列不为空 (队首与队尾指针相同时队列为空) 
		
		nowNode = q[front];			//将队首出队赋值给当前节点 
		front = (front+1) % MAX; 	//出队后更新队头指针
		printf("%c ",graph->vertexNode[nowNode].data);		//打印 
		
		ArcNode* arcNode = graph->vertexNode[nowNode].first;		//取出与当前节点相连的第一条边 
		while(arcNode != NULL){					//如果不存在边则无节点入队 
			nextNode = arcNode->vertexIndex;	//下一节点	 
			if(!v[nextNode]){	//如果下一节点没有访问 
				v[nextNode] = true;		//标记下一节点已经访问
				q[rear] = nextNode;		//入队 
				rear = (rear+1)%MAX;	//更新尾指针 
			}
			arcNode = arcNode->nextArc;	//取出与当前节点相连的下一条边
		}
	}
}
void bfs_edges(MyEdgesGraph *graph,int index){
	int q[MAX],front = 0,rear = 0;	//循环队列 
	int nowNode,nextNode;	//当前节点与下一节点 
	q[rear++] = index;		//将index入队 
	v[index] = true;	//设置当前节点已经访问 
	while(rear != front){	//当队列不为空(队首与队尾指针相同时队列为空) 
		
		nowNode = q[front];		//将队首出队
		front = (front+1)%MAX;	//更新队头指针 
		printf("%c ",graph->vexs[nowNode]);	//打印节点信息 
		
		for(int i = 1;i<=graph->nodeNum;i++){	//将与该节点有边相连的节点入队 
			if(graph->edges[nowNode][i] != 0 && graph->edges[nowNode][i] != INT_MAX){	//权重不为0或者不为最大值表明有边 
				nextNode = i;
				if(!v[nextNode]){				//如果下一节点没有访问，则入队 
					q[rear] = nextNode;			//入队 
					rear = (rear+1)%MAX;		//更新尾指针 
					v[nextNode] = true;	//设置当前节点已经访问 
				}
			}
		}
	}
	
}
void menu(){
  
  printf("\n图的各种操作");
  printf("\n========================================");
  printf("\n|          1--建立邻接矩阵             |");
  printf("\n|          2--显示邻接矩阵             |");
  printf("\n|          3--建立邻接表               |");
  printf("\n|          4--显示邻接表               |");
  printf("\n|          5--图的DFS-邻接矩阵         |");
  printf("\n|          6--图的DFS-邻接表           |");
  printf("\n|          7--图的BFS-邻接矩阵         |");
  printf("\n|          8--图的BFS-邻接表           |");
  printf("\n|          0--返回                     |");
  printf("\n========================================");
  printf("\n请输入菜单号(0-8)：");
} 
int main(){
	char ch1,ch2;
	MyEdgesGraph *edgesGraph = NULL;
	AdjList *adjList = NULL;
	ch1='y';
	
	
	while(ch1=='y'||ch1=='Y'){
		menu();
		scanf("%c",&ch2);
		getchar();
		switch(ch2)
		{
			case '1':
				{
					edgesGraph = createEdgesGraph();
					
				}
				break;
	  		case '2':
	  			{
	  				if(edgesGraph != NULL)
	  					showEdges(edgesGraph);
	  				else
	  					printf("请先创建邻接矩阵!");
	  				
				}
				break;
			case '3':
				{
					adjList = createAdjList();
					
				}
				break;
			case '4':
				{
					if(adjList != NULL)
	  					showAdjList(adjList);
	  				else
	  					printf("请先创建邻接表!");
	  					
				}
				break;
			case '5':
				{
					if(edgesGraph != NULL){
						for(int i =1;i<=edgesGraph->nodeNum;i++){
							if(!v[i]) dfs_edges(edgesGraph,i);
						} 
						//搜索后将访问数组恢复初始状态，便于下次搜索 
						for(int i =1;i<=edgesGraph->nodeNum;i++){
							v[i] = false;
						} 
					}else
	  					printf("请先创建邻接矩阵!");
				}
				break;
			case '6':
				{
					if(adjList != NULL){
						for(int i =1;i<=adjList->nodeNum;i++){
							if(!v[i]) dfs_adjList(adjList,i);
						 } 
						 //搜索后将访问数组恢复初始状态，便于下次搜索 
						for(int i =1;i<=adjList->nodeNum;i++){
							v[i] = false;
						} 	
					}else
	  					printf("请先创建邻接表!");
				}
				break;
			case '7':
				{
					if(edgesGraph != NULL){
						for(int i =1;i<=edgesGraph->nodeNum;i++){
							if(!v[i]) bfs_edges(edgesGraph,i);
						 } 
						 //搜索后将访问数组恢复初始状态，便于下次搜索 
						for(int i =1;i<=edgesGraph->nodeNum;i++){
							v[i] = false;
						} 	
					}else
	  					printf("请先创建邻接矩阵!");
				}
				break;
			case '8':
				{
					if(adjList != NULL){
						for(int i =1;i<=adjList->nodeNum;i++){
							if(!v[i]) bfs_adjList(adjList,i);
						 }
						 //搜索后将访问数组恢复初始状态，便于下次搜索  
						for(int i =1;i<=adjList->nodeNum;i++){
							v[i] = false;
						} 	
					}else
	  					printf("请先创建邻接表!");
				}
				break;
			case '0' :
				ch1='n';
				break;
			default:
				printf("输入有误，请输入0~8进行选择!");
		}
		printf("\n");
		system("pause");	
	}
	return 0;
}

未完待续……

算法

最短路径

朴素版Dijkstra算法

参考题目:acwing-最短路径

#include <iostream>
#include <cstring>
using namespace std;
//稠密图使用朴素版dijkstra,时间复杂度为o(n*n)
const int MAX = 510;    //最大节点数
int g[MAX][MAX];        //邻接矩阵
bool v[MAX];            //已经访问了的到起点的距离最短的点
int pre[MAX];           //并查集,用于记录最短路径
int dijkstra(int n,int m){
    int dist[MAX];  //存储每个点到起点的最短距离
    for(int i = 0;i<=n;i++){
        pre[i] = i; //初始化每个点都以自己为一个集合
    }
    memset(dist,0x3f,sizeof dist);  //初始化设为无穷大
    dist[1] = 0;                    //本题起点是1,起点到起点的距离设为0
    //1号节点对dist进行更新会导致一直为无穷大
    for(int i = 0;i<n;i++){ //最多n次迭代
        int k = -1; //还未找到最小值时k为-1
        for(int j = 1;j<= n;j++){   //遍历dist数组，找到距离起点的最小距离，赋值给k
            if(!v[j] && (k == -1 || dist[j] < dist[k])) //当然，如果该点已经求得到原点的距离最小则不用在比较
                k = j;
        }
        
        v[k] = true;    //将到起点的距离最小的点标记
        if(k == n) break;   //如果该点正好是要求的终点则直接退出迭代
        
        for(int j = 1;j<=n;j++){    //更新dist数组
            if(!v[j]&&dist[j] > dist[k] + g[k][j]){  //如果该点还未被标记，且从原点到k加上k到该点j的距离，比曾经原点到j距离更近，则更新原点到该点的距离
                dist[j] = dist[k] + g[k][j];
                pre[j] = k;     //更新该节点从起始位置经过k到达j距离最近，也就是说j节点的父节点为k
            }
        }
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;    //如果起点到终点最短距离为无穷大则表明图未联通
    int hh = n; //从终点开始逆推到起点
    while(hh != pre[hh]){   //起点满足自己的上一节点是自己
        printf("%d->",hh);   //打印该节点
        hh = pre[hh];       //继续查找自己的上一节点是不是起点
    }
    printf("1");
    return dist[n];
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    
    memset(g,0x3f,sizeof g);
    
    for(int i = 0;i<m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        g[u][v] = min(g[u][v],w);
    }
    int res = dijkstra(n,m);
    printf("\n%d",res);
    return 0;
}

堆优化版Dijkstra算法

参考题目：Dijkstra求最短路 II

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;  //(离起始点最短距离，节点编号)
const int MAX = 200005;
//数组模拟邻接表，head[]数组是链表头，e[]数组存储的是节点编号，ne[]数组存储的是下一节点指针
//idx开辟新空间指针，w[]数组存储的是该节点的权重
int head[MAX],e[MAX],w[MAX],ne[MAX],idx;
bool v[MAX];    //记录节点是否被选出
void init(int n){
    //邻接表初始化
    for(int i = 0;i<=n;i++) head[i] = -1;   //将每个节点表头设为-1
    idx = 0;
}
//插入边关系 a->b,c为权重
void insert_head(int a,int b,int c){
    e[idx] = b; //存储与head[a]相连边的节点编号
    w[idx] = c; //存储边权重
    ne[idx] = head[a];  //头插法
    head[a] = idx;
    idx++;  //指针加1
}
int dijkstra(int n,int m){
    int dist[MAX];  //存储各节点到起点的距离
    memset(dist,0x3f,sizeof dist);  //初始化距离为无穷大
    dist[1] = 0;    //起点到起点距离为1
    priority_queue<PII,vector<PII>,greater<PII>> q; //优先队列，按照升序排序
    q.push({0,1});  //将节点1入队
    while(q.size()){
        //只要队不为空则进行循环
        PII x = q.top();    //取出队首元素，取出的元素总是到原点的最小距离，这步骤就是朴素版的查询dist[]数组的最小值
        q.pop();            //将其出队
        int now = x.second,weight = x.first;    //now表示现在这个节点的编号，weight表示权重
        if(v[now]) continue;    //如果该边已经被选中了，则continue
        v[now] = true;          //反之将该节点标记为已经选中
        
        //用选中的节点更新dist[]数组
        for(int i = head[now];i!=-1;i = ne[i]){//链表查询，查询与被选中节点连通的节点，更新其到起点的最短距离
            int node = e[i];    //与被选节点相连接的节点编号
            if(!v[node] && dist[node] > weight+w[i]){   //如果该节点未选中过且原来到原点的距离比通过被选节点到原点距离远则更新距离
                dist[node] = w[i] + weight;
                q.push({dist[node],node});  //更新后入队
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;    //如果距离出现无穷大说明图未联通
    return dist[n];
    
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    init(n);
    for(int i = 0;i<m;i++){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        insert_head(x,y,z);
    }
    int ans = dijkstra(n,m);
    printf("%d",ans);
    return 0;  
}

最小生成树

prim算法

参考题目:acwing-最小生成树

#include <iostream>
#include <limits.h>
using namespace std;
const int MAX = 510;	//邻接矩阵节点数最大值 
int graph[MAX][MAX];	//邻接矩阵 
//prim算法，获取最小生成树与其权重和 
int prim(int nodes,int edges){
	int pre[MAX],dist[MAX],ans = 0;	//pre数组记录最小生成树的连接关系pre[3] = 2,表示到节点3的最短距离是节点2
							//dist数组代表距离已经添加到最小生成树的节点集合的最小距离 
	bool v[MAX];			//记录已经添加进最小生成树集合的元素
	for(int i = 1;i<=nodes;i++){
		dist[i] = INT_MAX;	//初始化距离数组为最大值 
		pre[i] = -1;
		v[i] = false;
	} 
	for(int i = 0;i<nodes;i++){	//最小生成树连接了所有节点，所以是nodes次迭代，每次连接一个节点 
		int min = -1;		//用于记录dist数组的最小值 
		for(int j = 1;j<=nodes;j++){	//枚举每一个没有被加入最小生成树的节点，找出dist数组中距离最小生成树集合最近的节点 
			if(!v[j] && (min == -1 || dist[j] < dist[min])){	//这里如果min == -1 表示第一次寻找，特殊处理一下 
				min = j;
			}
		}
		if(i && dist[min] == INT_MAX) return INT_MAX;	//除了第一次节点选择会出现到最小生成树集合最小距离为无穷大情况，如果其他时候出现了表明，该图未联通        
		v[min] = true;	//找到最小值后，将其加入最小生成树集合 
		if(i) ans+=dist[min];	//加上权重,排除第一次选择节点时，由于初始化的dist为无穷大 
		//之后更新dist数组,因为最小生成树集合新加了元素，所以更新下dist数组(各节点到最小生成树集合的距离最小值) 
		for(int j = 1;j<=nodes;j++){
			if(!v[j] && dist[j]>graph[j][min]){
				dist[j] = graph[j][min];
				pre[j] = min;
			} 
		}  
	}
	for(int i = 1;i<=nodes;i++) printf("%d->%d ",pre[i],i);
	return ans;
}
int main(){
	int nodes,edges; //节点总数，边数
	int u,v,w;		//节点编号u,v 权重w 
	scanf("%d %d",&nodes,&edges);	//获取到节点数与边数 
	for(int i = 0;i<=nodes;i++){	//初始化邻接矩阵 
		for(int j = 0;j<=nodes;j++){
			if(i == j) graph[i][j] = 0; 
			else graph[i][j] = INT_MAX;
		}
	}
	for(int i = 1;i<=edges;i++){
	    scanf("%d %d %d",&u,&v,&w);	//读取边信息 
	    graph[u][v] = graph[v][u] = graph[u][v]>w?w:graph[u][v];
	} 
	int res = prim(nodes,edges);
	if(res != INT_MAX) printf("%d",res);
	else printf("impossible");
	return 0;
}

kruskal算法

参考题目:Kruskal算法求最小生成树

#include <iostream>
using namespace std;
const int MAX = 100005;
//结构体用于存储边 
typedef struct{
	int a,b,w;	//端点a,b,权重w 
}Edge;
int p[MAX];	//并查集数组，并查集数据结构可以快速的合并集合，查询某元素属于哪个集合等操作 
void quick_sort(Edge q[],int l,int r){  //用快速排序算法，文中有具体算法解释，也可以用库函数中的sort()
	if(l>=r) return;
	int i = l-1,j = r+1;
	Edge x = q[l+r>>1];
	while(i<j){
		do i++; while(q[i].w < x.w);
		do j--; while(q[j].w > x.w);
		if(i<j) swap(q[i],q[j]);
	}
	quick_sort(q,l,j);
	quick_sort(q,j+1,r);
}
int find(int x){    //查询某一元素输入哪个集合(查询根节点),并进行路径压缩
	if(p[x] != x) p[x] = find(p[x]);    //如果某元素x的父节点不是自己，则查询其父亲节点是否是根节点
	return p[x];    //如果是，返回父亲节点，并赋值给子节点，也就是说将所有子节点的父亲都设为根节点，这样有利于以后查询
}
int kruskal(Edge edges[],int nodes,int m){
	quick_sort(edges,0,m-1);        //先对边进行排序
	int res = 0,cnt = 0;
	for(int i = 0;i<m;i++){         //只要两节点没有连接，则进行连接
		int a = edges[i].a,b = edges[i].b,w = edges[i].w;
		a = find(a),b = find(b);    //查询两节点属于哪个集合
		if(a != b){                 //如果不属于同集合，表明两点未连接
			p[a] = b;               //更新某节点的父亲，也就是合并两集合
			res+=w;                 //更新权重
			cnt++;                  //连接的节点数加1
		}
	}
	if(cnt < nodes-1) return 0x3f;  //如果图是连通的那么其连接的节点数一定是n-1(由于计数是从0开始，每次连接的是两节点，当第一次连接的时候cnt只累加了一次)
	return res;
}
int main(){
	int nodes,m;	//节点数和边数 
	Edge edges[2 * MAX];	//存储边的数组 
	scanf("%d %d",&nodes,&m);
	for(int i = 1;i<=nodes;i++) p[i] = i;	//初始化并查集数组，每个元素都是一个集合
	for(int i = 0;i<m;i++){
		int a,b,w;
		scanf("%d %d %d",&a,&b,&w);
		edges[i] = {a,b,w};					//读入边信息 
	} 
	int res = kruskal(edges,nodes,m);
	if(res == 0x3f) printf("impossible");   //图未联通
	else printf("%d",res);                  
	return 0;
}

排序

插入排序

#include <iostream>
using namespace std;
int num[100];
//插入排序
//区间0-n可分为两个区间，0 - a为已经排序后的区间，a+1 - n为未排序区间
//算法思路：
//两个指针，指针i指向未排序区间第一个元素作为待插入元素，指针j指向排序后区间的最后一个元素 
//先将i指针指向的元素取出存储到temp中，随后temp与排序的区间进行比较，从j指向的元素开始查找到他本该在的位置
//即temp与num[j]进行比较 ：
//	1.(升序)如果temp大于等于j指定的元素那么待插入元素的位置就在当前位置 
//  2.小于，则表明在j指向的前方，所以把j元素移动到j+1位置，为插入temp腾出位置，随后j--,继续进行比较直到找到合适的位置 
int main(){
	int n;
	cin>>n;
	for(int i = 0;i<n;i++) cin>>num[i];
	for(int i = 1;i<n;i++){
		//从先将待插入元素取出，存到temp中
		//定义j指针，指向排序后区间的最后一个元素
		int temp = num[i],j = i-1;
		//循环判断待插入元素与j指向的元素的大小关系 
		while(j >= 0 && temp<num[j]){
			//如果小于则位置在j之前，先将j指向的元素移向j+1为temp腾位置 
			num[j+1] = num[j];
			j--;	//指针减一，继续判断 
		}
		num[j+1] = temp;	//查询到了合适位置后，插入到j元素后方 
	}
	for(int i = 0;i<n;i++) cout<<num[i]<<" ";
}

快速排序

参考题目：快速排序

#include <iostream>
using namespace std;
const int MAX = 100005;
int num[MAX];
void quick_sort(int q[],int l,int r){
    if(l>=r) return;        //递归结束条件
    //定义两个指针i,j 
    int i = l-1,j = r+1,k = q[l+r>>1];  //k可取任意值,但是该模板取中间值最快  
    while(i<j){
        //左指针先循环查找到大于k的值,随后右指针循环查找到小于k的值
        do{
            i++;
        }while(q[i]<k);
        do{
            j--;
        }while(q[j]>k);
        //如果左指针小于右指针则将左指针与右指针的内容进行交换
        if(i<j) swap(q[i],q[j]);
    }
    
    quick_sort(q,l,j);  //递归处理数组左边
    quick_sort(q,j+1,r);    //递归处理数组右边
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i<n;i++) scanf("%d",&num[i]);
    quick_sort(num,0,n-1);
    for(int i = 0;i<n;i++) printf("%d ",num[i]);
}

归并排序

参考题目:归并排序

#include <iostream>
using namespace std;
const int MAX = 100005;
int m[MAX],temp[MAX];
void merge_sort(int p[],int l,int r){
    if(l>=r) return;    //如果没有元素可以排序则直接return
    int mid = l+r>>1;   //将数组一分为二
    merge_sort(p,l,mid);    //左边数组进行排序
    merge_sort(p,mid+1,r);  //右边数组进行排序
    //将已经排好序的左右数组归并
    int i = l,j = mid+1,k = 0;  //i指向左边第一个元素，j指向右边第一个元素
    while(i<=mid && j<=r){  
        //如果左边元素小于等于右边元素，则将其放入临时数组，左指针加1，反之
        if(p[i]<=p[j]) temp[k++] = p[i++];
        else temp[k++] = p[j++];
    }
    //如果左或者右指针还有元素未存到临时数组中，则将其直接放在临时数组中
    while(i<=mid) temp[k++] = p[i++];
    while(j<=r) temp[k++] = p[j++];
    //最后将临时数组的值放回原数组
    for(i = l,j = 0; i <= r;i++,j++) p[i] = temp[j];
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i<n;i++) scanf("%d",&m[i]);
    merge_sort(m,0,n-1);
    for(int i = 0;i<n;i++) printf("%d ",m[i]);
    return 0;
}