数据结构复习笔记

绪论

数据结构讨论的范畴

Niklaus Wirth：
Programs = Algorithm + Data Structures
例：计算机对弈=对弈的规则和策略+棋盘及棋盘的格局

基本概念

• 数据：所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。
• 数据元素: 是数据（集合）中的一个“个体”，数据结构中讨论的基本单位。
• 数据项：是数据结构中讨论的最小单位，数据元素可以是数据项的集合
• 数据结构：带结构的数据元素的集合，是相互之间存在着某种逻辑关系的数据元素的集合
• 数据的逻辑结构：线性结构，树形结构，图状结构，集合结构
  -数据结构形式定义：Data structure=（D,S)
• 数据的存储结构 （逻辑结构在存储器中的映象）
• 映像方法：顺序映像（以相对的存储位置表示后继关系),链式映象(以附加信息(指针)表示后继关系),自定义
• 数据类型：值的集合 & 定义在此集合上的 一组操作
• 抽象数据类型（ADT) :一个数学模型以及定义在此数学模型上的一组操作。两个重要特性：数据抽象 & 数据封装
• 描述方法 （D，S，P），如下：
  ADT 抽象数据类型名 {
  数据对象：〈数据对象的定义〉
  数据关系：〈数据关系的定义〉
  基本操作：〈基本操作的定义〉
  } ADT 抽象数据类型名
  （这地方个人觉得不是很重要，没必要死记硬背，看懂就好）
• 抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。

算法和算法的衡量

• 算法是为了解决某类问题而规定的一个有限长的操作序列
• 算法的五个特性：有穷，确定，可行，有输入，有输出
• 算法设计的原则：正确，可读，健壮，高效率与低存储
• 衡量算法效率的方法：事后统计，事前分析估算
• 一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。
• 时间复杂度估算（计算语句频度）：从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。
• 空间复杂度估算：输入数据所占空间+辅助变量所占空间+程序本身所占空间
  （若输入数据所占空间只取决于问题本身，与算法无关，那么一般只考虑辅助变量所占空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。）
• 时间空间复杂度通常按最坏的情况来考虑

线性表（最简单的线性结构）

线性结构的基本特征：存在唯一的第一个元素和最后一个元素；除最后一个元素外，都有唯一后继；除第一个元素外，都有唯一前驱。

线性表类型定义

数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,…,n, n≥0 }
数据关系：R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,…,n }
基本操作：初始化，销毁，引用，加工
常见操作(时间复杂度，空间复杂度）

//数组逆置：O(n) O(c)
void reverse_arr(int *a,int n)
{
	int i,j,temp;
	for(i=0,j=n-1;i<j;i++,j--)
	{
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
}

//数组去重：无序：O(n^2) O（c) 有序：O(n) O(c)
int delrepeat(int *a,int n)
{
	int i,j;//计数器i用来在数组a中做遍历；计数器j用来在墙的左边做遍历，以判断a[i]是否为重复元素
	int k;//k表示墙的位置，初始值为1
	for(i=1,k=1;i<n;i++)//对数组中的元素，逐一做处理
	{
		for(j=0;j<i;j++)//在墙的左边做遍历，判断当前的数组元素a[i]是否是重复元素
		{
			if(a[i]==a[j])//如果是重复元素，提前退出循环
				break;
		}
		if(j>=i)//循环结束后，根据计数器j的取值即可判断循环是正常结束还是提前结束，如果正常结束即表示a[i]非重复元素
		{
			a[k]=a[i];//将a[i]移动到墙的位置
			k++;//同时墙的位置右移，表示墙左边新增一个非重复的元素
		}
	}
	return k;//返回墙最终的位置，即为数组中最后包含的实际元素个数

//////////////////////////////////有序数组去重/////////////////////////////////////////////////////////////
	/*int i,k;
	for(i=1,k=1;i<n;i++)
	{
		if(a[i]!=a[i-1])
		{
			a[k]=a[i];
			k++;
		}
	}
	return k;*/
}

//有序数组本地归并（O(m*n) O(c)），求交集(O(m+n) O(c))
int Merge1(int *a,int *b,int m,int n)
{
	int i,j,k;//计数器i,j分别在数组a和b中遍历，k表示当前数组a中有效元素个数，初始值为m
	int h;//做插入时，数组a中的相应元素逐个后移一位，用h做计数器
	for(i=0,j=0,k=m;i<k&&j<n;)//注意循环终止条件
	{
		if(a[i]<b[j])//当前a[i]小，b[j]不能插入
			i++;
		else if(a[i]==b[j])//二者相等，也不做插入
		{
			i++;
			j++;
		}
		else//在数组a的i这个位置上要插入b[j]
		{
			for(h=k-1;h>=i;h--)//从a中当前最后一个元素开始，到元素a[i]，
				a[h+1]=a[h];//逐个后移一位
			a[i]=b[j];//空出i这个位置，将b[j]插入
			i++;//当前i的位置是新插入的b[j]，所以将计数器i加1
			j++;//b[j]已经做完处理，因此j加1
			k++;//数组a中新增一个元素，墙的位置后移一位
		}
	}	
	while(j<n)//如果数组b中还有剩余的未做比较的元素，直接复制到数组a
	{
		a[k]=b[j];
		j++;
		k++;
	}
	return k;//返回数组a中实际包含的元素个数

///////////////////////////////////////有序数组本地求交集///////////////////////////////////////////////////
	/*int i,j,k;
	for(i=0,j=0,k=0;i<m&&j<n;)
	{
		if(a[i]<b[j])
			i++;
		else if(a[i]>b[j])
			j++;
		else
		{
			a[k]=a[i];
			k++;
			i++;
			j++;
		}
	}
	return k;*/
}

//有序数组异地求并集（O(m+n) O(m+n))交集（O(m+n),O(max(m,n)))
int Merge2(int *a,int *b,int *c,int m,int n)
{
	int i,j,k;
	for(i=0,j=0,k=0;i<m&&j<n;)
	{
		if(a[i]<b[j])
		{
			c[k]=a[i];
			i++;
			k++;
		}
		else if(a[i]>b[j])
		{
			c[k]=b[j];
			k++;
			j++;
		}
		else
		{
			c[k]=a[i];
			i++;
			j++;
			k++;
		}
	}
	while(i<m)
	{
		c[k]=a[i];
		i++;
		k++;
	}
	while(j<n)
	{
		c[k]=b[j];
		j++;
		k++;
	}
	return k;
	///////交集////////////
	/*
	int i,j,k;
	for(i=0,j=0,k=0;i<m && j<n;)
	{
		if(a[i]>b[j])
		{
			j++;
		}
		else if(a[i]<b[j])
		{
			i++; 
		} 
		else
		{
			c[k]=a[i];
			i++;
			j++
			k++;
	}
	return k;
	*/ 
}

顺序映像（数组）

定义:以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系<x,y>
常见做法：令x与y的位置相邻，用一组地址连续的存储单元依次存放线性表中的数据元素
存储位置计算：LOC(ai) = LOC(a1) + (i-1)×C LOC(ai):基地址 C：一个元素的存储量 或 LOC(ai) = LOC(a0) + i×C
常见操作移动元素计算：插入：E=1/(n+1)(0+1+…+n)=n/2
删除：E=1/n(0+1+…+n-1)=(n-1)/2

链式映像（链表）

定义： 用一组地址任意的存储单元存放线性表中的数据元素。以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的映象) 。以“结点的序列”表示线性表----链表
基本操作：

//插入链表（O(n),O(c))
void insdata(LI *A,int data)
{
	LI *p1,*p;//
	LI *q;//用q指向新生的节点空间
	p1=A;//
	p=p1->next;//
	while(p)//开始遍历链表A寻找合适的插入位置
	{
		if(p->data<data)//当前结点的数值比待插入数值要小的话，p与p1的指针要向后移动
		{
			p1=p;//
			p=p->next;//
		}
		else//当前结点的数值大于等于待插入数值，比较结束
			break;//
	}
	q=(LI *)malloc(sizeof(LI));//动态生成节点空间
	q->data=data;//给改新结点数值域赋值
	p1->next=q;//将该新结点插入到p1与p之间
	q->next=p;//
}
//创建有序链表（O(n^2) O(n))
void createlist(LI *A,int n)
{
////////////////////////////////////创建有序链表/////////////////////////////////////////////////////////////////
	int i,x;
	for(i=1;i<=n;i++)
	{
		x=rand()%43;//随机生成一个数
		insdata(A,x);//调用插入函数，将其插入到当前有序的链表中，并保持其有序性
	}
}
//创建无序链表（O(n) O(n))
void createlist(LI *A,int n)
{
	int i;
	LI *rear,*p;
	rear=A;//rear指向链表的最后一个节点，初始空链表，头结点也是尾节点
	for(i=1;i<=n;i++)
	{
		p=(LI *)malloc(sizeof(LI));//动态申请一个节点空间
		p->data=rand()%43;//该结点空间的数值域等于当前随机数
		rear->next=p;//将新生成的节点插入在链表的尾部
		rear=p;//当前新插入的节点是新的尾节点，因此更新尾节点指针的位置
	}
	rear->next=NULL;//所有结点生成结束后，令尾节点指向NULL，完成创建
}

//删除链表：O(n) O(c)
void dellist(LI *A)
{
	LI *p,*p2;
	p=A->next;
	A->next=NULL;
	while(p)
	{
		p2=p->next;
		free(p);
		p=p2;
	}
}

//单链表逆置：O(n) O(c)
void reverse_list(LI *A)
{
	LI *p,*p2;//p用来遍历链表，指向当前结点；p2是p的后继，因为在把p拆下来插入到头结点后，其next指针的指向发生变化，如果
	          //要对p之后的节点继续做处理，应该事先将其后继的位置保存下来
	if(A->next==NULL||A->next->next==NULL)//如果链表是空的或者只包含一个节点
		return;//此时不需要做逆置，直接返回结束
	p=A->next;//如果链表包含一个以上的节点，需要做逆置，那么初始p指向头结点后的第一个节点
	A->next=NULL;//将头结点拆下来，并置其next指向空，表示当前这个空链表就是最后我们要的逆置链表，原先链表中的节点会被逐一的
	             //插入到头结点的后边
	while(p)//只要p指向的是一个实际存在的节点
	{
		p2=p->next;//先把其后继的位置存储到p2中
		p->next=A->next;//将p指向的当前结点插入到头结点A的后边
		A->next=p;//将p指向的当前结点插入到头结点A的后边
		p=p2;//更新p的指向，使其指向原链表中的下一个待处理结点
	}
}

//无序链表去重:O(n^2) O(c)
//有序链表去重:O(n) O(c)
void delrepeat(LI *A)
{
//////////////////////////////////////无序链表去重/////////////////////////////////////////////////////////////
	/*LI *p,*p1;//p用来遍历链表，指向当前访问的节点，p1指向p的前驱
	LI *q;//结点p需要跟它之前所有的节点做比较判断其是否为重复结点，用q来对p之前的所有结点做遍历
	if(A->next==NULL||A->next->next==NULL)//如果链表为空或者只包含一个节点
		return;//不需要做去重，直接结束返回
	p1=A->next;//否则需要做去重，从第二个结点开始做判断，因此初始p1指向头结点后的第一个节点
	p=p1->next;//p指向p1的后继，即第二个结点
	while(p)//只要p指向的是一个实际存在的节点
	{
		for(q=A->next;q!=p;q=q->next)//指针q从第一个节点开始遍历，一直到指针p之前
		{
			if(p->data==q->data)//将p的数据与q指向的节点数据做比较，如果相等
				break;//退出当前比较的循环
		}
		if(q==p)//循环结束后，根据q的取值，如果它已经等于p，说明循环是正常结束的，p指向的节点是非重复结点
		{
			p1=p;//不做删除，将p和p1做更新，继续处理下一个节点
			p=p->next;//
		}
		else//否则循环是通过break提前结束的，说明p指向的节点是一个重复结点，要做删除
		{
			p1->next=p->next;//通过修改指针将p指向的节点从链表中拆下来
			free(p);//释放该结点，这才算真正删除
			p=p1->next;//释放后p没有指向了，要重新复制，它始终是p1的后继
		}
	}*/
//////////////////////////////////////有序链表做去重/////////////////////////////////////////////////////
	LI *p1,*p;
	if(A->next==NULL||A->next->next==NULL)
		return;
	p1=A->next;
	p=p1->next;
	while(p)
	{
		if(p->data==p1->data)
		{
			p1->next=p->next;
			free(p);
			p=p1->next;
		}
		else
		{
			p1=p;
			p=p->next;
		}
	}	
}

//有序链表并集：O(m+n) O(c)
//有序链表交集：O(m+n) O(c)
void Merge(LI *A,LI *B)
{
	LI *pa,*pa1;//pa用来在A中遍历，指向当前访问的节点，pa1指向pa的前驱，方便做插入
	LI *pb,*pb2;//pb用来在B中遍历，指向当前访问的节点，pb2是pb的后继，因为把若把pb插入到链表A中，pb的next域会发生变化，如果想要
	            //对pb的后续节点继续做处理，需要将其后继实现保存到pb2
	pa1=A;//给pa1赋初值
	pa=pa1->next;//给pa赋初值
	pb=B->next;//给pb赋初值
	B->next=NULL;//因为处理结束后，B的所有结点要么已经被插入到A中，要么被释放掉，因此应该是个空链表
	while(pa&&pb)//如果pa与pb同时为真
	{
		pb2=pb->next;//保存pb的后继（注意这个赋值要放在循环内，确保pb为真，它才会有后继next）
		if(pa->data<pb->data)//如果A中元素比较小，不做插入
		{
			pa1=pa;//向后移动
			pa=pa->next;//向后移动
		}
		else if(pa->data==pb->data)//如果A和B的元素相等，要把B中的节点释放掉，同时更新pa、pb及相应指针
		{
			pa1=pa;//向后移动
			pa=pa->next;//向后移动
			free(pb);//把B中的与A相同的节点释放掉
			pb=pb2;//重新给pb赋值
		}
		else//如果A的元素比B的大，此时要把B的节点插入在pa1与pa之间
		{
			pa1->next=pb;//将pb插入到pa1后边
			pb->next=pa;//此时pb成为pa的前驱了
			pa1=pb;//更新pa1的指向，使其确保在pa的前驱的位置上
			pb=pb2;//更新pb的指向
		}
	}
	if(pb)//比较结束后，如果在B中有剩余的未被比较的元素
		pa1->next=pb;//将这些剩余的节点直接链接在A的后边

///////////////////////////////////////求A=A and B ///////////////////////////////////////////////////////////////
	/*LI *pa,*pa1,*pb;
	pa1=A;pa=pa1->next;
	pb=B->next;
	while(pa&&pb)
	{
		if(pa->data<pb->data)
		{
			pa1->next=pa->next;
			free(pa);
			pa=pa1->next;
		}
		else if(pa->data>pb->data)
			pb=pb->next;
		else
		{
			pa1=pa;
			pa=pa->next;
			pb=pb->next;
		}
	}
	if(pa)
		pa1->next=NULL;
	while(pa)
	{
		pa1=pa->next;
		free(pa);
		pa=pa1;
	}*/
	
}

//异地归并：O(m+n) O(m+n)
LI *Merge2(LI *A,LI *B)
{
	LI *p2,*p;
	LI *q2,*q;
	LI *rear;
	LI *C=(LI *)malloc(sizeof(LI));
	p=A->next;
	q=B->next;
	rear=C;
	A->next=NULL;
	B->next=NULL;
	while(p&&q)
	{	
		q2=q->next;
		p2=p->next;
		if(p->data<q->data)
		{
			rear->next=p;
			rear=p;
			rear->next=NULL;
			p=p2;
			
		}
		else if(p->data>q->data)
		{
			rear->next=q;
			rear=q;
			rear->next=NULL;
			q=q2;
			
		}
		else
		{
			rear->next=p;
			rear=p;
			rear->next=NULL;
			p=p2;
			p2=p->next;
			free(q);
			q=q2;
		}
	}
	if(p) rear->next=p;
	if(q) rear->next=q;
	 return C;
}

其他类型的链表

1.双向链表
2.循环链表（可用于约瑟夫环问题）
创建函数返回的是尾节点；判断循环结束时的条件不是后继是否为空，而是后继节点是否为头节点

#include "stdlib.h"
#include "math.h"
#include "stdio.h"

typedef struct node
{
	int data;
	struct node *next;
}LI;


LI *createcyclist_p(int n);//创建包含有n个数的单向循环链表并返回尾节点指针
void showcyclist_p(LI *A);//按照从头到尾的顺序显示循环链表的内容
void joesph_p(LI *A,int m);//模拟实现约瑟夫问题。根据报数间隔m，依次将对应节点从链表中删除，输出删除的顺序（时间复杂度O(m*n) 空间复杂度O(c))
main()
{
	LI *A;
	int n,m;
	printf("please input the data of N and M:\n");
	scanf("%d%d", &n, &m);
	while (n > 0 && m > 0)
	{
		A = createcyclist_p(n);			
		printf("the original list is :\n");
		showcyclist_p(A);
		printf("the del order is:\n");
		joesph_p(A,m);		
		printf("please input the data of N and M:\n");
	    scanf("%d%d", &n, &m);	
	}
}

LI *createcyclist_p(int n)
{
	LI *head=(LI *)malloc(sizeof(LI));
	head->data=1;
	LI *rear=head,*p;
	int i;
	for(i=2;i<=n;i++)
	{
		p=(LI*)malloc(sizeof(LI));
		p->data=i;
		rear->next=p;
		rear=p;
	}
	rear->next=head;
	return rear;
	//返回尾指针 
}
void showcyclist_p(LI *A)
{
	LI *head=A->next;
	LI *p=head;
	int j=1;
	do
	{
		printf("%-4d",p->data);
		j++;
		if (j%15==0)
		printf("\n");
		p=p->next;
	 } while(p!=head);
	 printf("\n");
}//按照从头到尾的顺序显示循环链表的内容
void joesph_p(LI *A,int m)
{
	LI *p1=A,*p=p1->next;
	while(p1!=p)
	{
	int i=1;
	for (i=1;i<m;i++)
	{
		p1=p1->next;
		p=p1->next;
	}
	printf("%-4d",p->data);
	p1->next=p->next;
	free(p);
	p=p1->next;
	}
	printf("%-4d\n",p->data);
}//模拟实现约瑟夫问题。根据报数间隔m，依次将对应节点从链表中删除，输出删除的顺序

Tips

两个有序顺序表合并成一个有序顺序表所需比较次数
（n,n)->min=n;
(最好情况，一个顺序表内的元素都比另一个顺序表内的元素要小）
（m,n)->max=m+n-1
（最差情况：大小交叉）
2.对于链表来说：删除某一节点或插入某一节点，一定要知道它的前驱
3.如果一个链表常用操作为删除尾节点或插入一个节点，最好用双向循环链表。因为查找尾节点无论是单向还是双向的链表，都要遍历找到尾节点的前驱，时间复杂度为O（n），而双向循环链表初始化函数返回的就是尾指针，这样就不用遍历了

栈和队列

栈和队列是限定插入和删除只能在表的“端点”进行的线性表

栈的定义与常规操作

顺序栈

typedef struct{
	int stack[MAXSIZE];
	int top;
}Stack,*Stack_P;

void initstack(Stack_P);
void clearstack(Stack_P);
int gettop(Stack_P p);
int isfull(Stack_P p);
int isempty(Stack_P p);
int pop(Stack_P p);
void push(Stack_P p,int);
void showstack(Stack_P);
main()
{
	int i=0;
	Stack P;
	initstack(&P);
	for(i=0;i<10;i++)
	{
		push(&P,i);
	}
	showstack(&P);
	printf("pop out %d\n",pop(&P));
	showstack(&P);
	printf("pop out %d\n",pop(&P));
	showstack(&P);
	printf("empty?%d full?%d\n",isempty(&P),isfull(&P));
 } 
 void initstack(Stack_P p)
 {
 	p->top=-1;
 }
 void clearstack(Stack_P p)
 {
 	p->top=-1;
 }
 int isfull(Stack_P p)
 {
 	if (p->top==MAXSIZE-1)
 	{
 		printf("Stack is full\n");
 		return 1;
	 }
	 else return 0;
 }
 int isempty(Stack_P p)
 {
 	if (p->top==-1)
 	{
 		printf("Stack is empty\n");
 		return 1;
	 }
	 else return 0;
 }
 int gettop(Stack_P p)
 {
 	if (isempty(p))
 	{
 		printf("cant get top \n");
 		exit(1);
	 }
	 return p->stack[p->top];
 }
 int pop(Stack_P p)
 {
 	if (isempty(p))
	{
 		printf("cant pop out \n");
 		exit(1);
	 }
	 return p->stack[p->top--];
	  }
void push(Stack_P p,int x)
{
	if (isfull(p))
	{
 		printf("cant push \n");
 		exit(1);
	 }
	 p->stack[++(p->top)]= x;
}
void showstack(Stack_P p)
{
	int i;
	for(i=0;i<=p->top;i++)
	{
		printf("%d ",p->stack[i]);
	}
	printf("\n");
}

链栈

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

typedef struct node{
	int data;
	struct node* next;
}Node,*Node_P;

typedef struct{
	Node_P top;
}Linkstack;

void initstack(Linkstack *);
void clearstack(Linkstack *);
int isempty(Linkstack*);
void push(Linkstack *,int);
int pop(Linkstack *);
int gettop(Linkstack*);
void showstack(Linkstack *);

void main()
{
	Linkstack P;
	initstack(&P);
	int i=0;
	for(i=0;i<10;i++)
	{
		push(&P,i);
	}
	showstack(&P); 
	printf("%d\n",gettop(&P));
	printf("%d\n",pop(&P));
	showstack(&P); 
	clearstack(&P);
	showstack(&P);
	
}
void initstack(Linkstack *p)
{
	p->top=NULL; 
}
void clearstack(Linkstack *p)
{
	Node_P q=p->top,temp;
	while(q)
	{
		temp=q;
		q=q->next;
		free(temp);
	}
	p->top=NULL;
}
int isempty(Linkstack* p)
{
	if (p->top==NULL) return 1;
	else return 0;
}
void push(Linkstack *p,int x)
{
	Node_P head=p->top;
	Node_P temp=(Node_P)malloc(sizeof(Node));
	if (temp==NULL)
	{
		printf("fail to allocate memory");
		exit(1);
	}
	temp->data=x;
	temp->next=p->top;
	p->top=temp;
}
int pop(Linkstack *p)
{
	if (isempty(p))
	{
		printf("cant pop");
		exit(1);
	}
	Node_P q=p->top;
	int temp=p->top->data;
	p->top=p->top->next;
	free(q);
	return temp;
}
void showstack(Linkstack * p)
{
	Node_P q=p->top;
	if (q==NULL)
	{
		printf("empty \n");
		exit(1);
	}
	while(q!=NULL)
	{
		printf("%d ",q->data);
		q=q->next;
	}
}
int gettop(Linkstack* p)
{
	if (isempty(p))
	{
		printf("empty\n");
		exit(1);
	}
	return p->top->data;
}

应用举例

数制转换

#include<stdio.h>
int main()
{	//10进制转8进制 
	int stack[100];
	int top=-1;
	int input,output;
	scanf("%d",&input);
	while(input!=0)
	{
		stack[++top]=input%8;
		input/=8;
	}
	while(top>-1)	printf("%d",stack[top--]);
	return 0;
}

括号匹配

如遇到左括号则进栈；若遇到右括号：栈空则不匹配，栈非空则与栈顶元素比较；结束时栈非空则不匹配，反之则匹配，具体代码见课程设计的表达式求值，传送门：www.fornownothingtoshow.com

行编辑

遇到一般字符就push，遇到退行符则clear stack，遇到退格符就pop
每行用换行符来分割

int main()
{
	char stack[100];
	char ch;
	int top=-1;
	ch=getchar();
	while(ch!=EOF)
	{
		while(ch!=EOF&&ch!='\n')
		{
			switch (ch) 
			{
				case '#':top--;break;//退格符 
				case '@':top=-1;break;//退行符 
				default :stack[++top]=ch;break ;
			}
			ch=getchar();
		}
		for(int i=0;i<=top;i++) printf("%c",stack[i]);
		top=-1;
		ch=getchar();
	}
	return 0;
}

迷宫问题

算法思想：
若当前位置“可通”，则纳入路径，继续前进;
若当前位置“不可通”，则后退，换方向继续探索;
若四周“均无通路”，则将当前位置从路径中删除出去。
详情见课程设计中的迷宫问题最短路径的非递归算法求解：
传送门：www.fornownothingtoshow.com
以上想法在非递归算法中会比较体现的比较具体，在递归算法中实际上就是向所有可行的方向进行探索
(这个代码是老师写的递归例子代码，感觉很巧妙，有一种美感）

#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#define start_x 1
#define start_y 1
#define end_x 8
#define end_y 8
#define N 100
int sum=0;
int mg[10][10]={
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1},	
};//迷宫数据，0表示可行，1表示不可行

typedef struct
{
	int i,j;
}PA;//路径中的每个点都有相应的行列值，因此用PA表示路径中每个点的数据结构

void showpath(PA *p,int n);//显示包含有n个点的路径


/////////////////////////////////////////////////////////////////////////////////////////////
//
//        maze是一个递归函数
//  x1,y1表示当前起始点的坐标；
//  x2,y2表示终止点的坐标；
//  p是存放路径中包含点的数组；
//  n表示当前路径中已经包含的点的个数；  
//
/////////////////////////////////////////////////////////////////////////////////////////////
void maze(int x1,int y1,int x2,int y2,PA *p,int n);
main()
{
	PA p[N];//定义用来存放路径的数组
	p[0].i=start_x;//
	p[0].j=start_y;//将给定的起始点坐标赋值给数组p中的第一个元素
	mg[start_x][start_y]=1;//将起始点设置成不可行状态（我们找的是简单路径，也就是一条路径中，某个
	                       //点只能走过一次，不能重复走。为了避免一个点在一条路径中重复出现，因此
	                       //一旦某个点被放入当前路径中后，将其设置成不可行状态）
	maze(start_x,start_y,end_x,end_y,p,1);//调用maze函数递归的寻找所有可行路径，初始情况下数组p中
	printf("sum=%d",sum);                               //只有一个点，即起始点
}

void showpath(PA *p,int n)
{
	int i,j;
	for(i=0,j=0;i<n;i++)
	{
		printf("(%d %d) ",p[i].i,p[i].j);
		j++;
		if(j%10==0)
			printf("\n");
	}
	printf("\n\n");
	sum++;
}
void maze(int x1,int y1,int x2,int y2,PA *p,int n)
{
	int i,j;//i,j两个变量用来表示当前点的行列号
	int	next;//对于每个当前的起始点，需要对其后继的4个方向进行穷举，next用来做穷举时的计数器
	if(x1==x2&&y1==y2)//若当前起始点坐标等于终止点坐标，说明当前的数组p中已经存放了一条从入口
		              //到出口的可行路径（这个就是该递归的出口，即基准情况）
		showpath(p,n);//输出该路径
	else//如果当前的x1,y1不是终止点，那么要继续找下一个可行的点
	{
		for(next=0;next<4;next++)//对前后左右4个方向进行穷举来寻找下一个可行的点
		{
			switch(next)
			{
			case 0:i=x1;j=y1+1;break;//向右
			case 1:i=x1+1;j=y1;break;//向下
			case 2:i=x1;j=y1-1;break;//向左
			case 3:i=x1-1;j=y1;break;//向上
			}
			if(mg[i][j]==0)//如果某个方向上，点可行
			{
				p[n].i=i;
				p[n].j=j;//将该点放入路径数组p中
				mg[i][j]=1;//为了避免该点在当前路径中重复出现，将其设置成不可行状态				
				maze(i,j,x2,y2,p,n+1);//以当前找到的该可行点作为新的起始点，继续调用maze函数，注意
				                      //参数的变化
				mg[i][j]=0;//当前的递归结束后，将该点复原（注意，一个点在一条路径中只能出现一次，但
				           //一个点允许出现在多条不同的路径中。因此为了确保可以找到所有可行的点，当
				           //前递归结束后，一定要将该点复原，确保找别的路径的时候该点是可行状态）
			}
		}
	}
}

表达式求值

详情见课程设计中的表达式求值：传送门：www.nothingtoshow.com

实现递归

当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。
从被调用函数返回调用函数之前，应该完成下列三项任务：保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数
多个函数嵌套调用的规则是：后调用先返回 ，此时的内存管理实行“栈式管理”
相关术语
递归工作栈：递归过程执行过程中占用的数据区。
递归工作记录：每一层的递归参数合成一个记录。
当前活动记录：栈顶记录指示当前层的执行情况。
当前环境指针：递归工作栈的栈顶指针。
经典例子：汉诺塔问题

//伪代码
void hanoi (int n, char x, char y, char z) 
{
	if (n==1)
   		move(x, 1, z);   
   	else {
    		hanoi(n-1, x, z, y); 
   			move(x, n, z);     
    		hanoi(n-1, y, x, z); 
  		}
}

理解p56,p57的过程与调用关系

队列的定义和常见操作

顺序队列

#include<stdio.h>
#include<stdlib.h>
#define N 50
typedef struct{
	int a[N];
	int front,rear;
}Queue; 
void initqueue(Queue*p);
void clear(Queue*p);
int gettop(Queue *p);
int isempty(Queue *p);
int isfull(Queue *p);
void inqueue(Queue *p,int x);
int outqueue(Queue *p);
void showqueue(Queue *p); 

int main()
{	Queue P;
	initqueue(&P);
	printf("%d\n",P.front);
	int i;
	for(i=0;i<6;i++)
	{
		inqueue(&P,i);
		printf("%d\n",P.front);
	}
	printf("%d\n",P.front);
	showqueue(&P);
	printf("%d\n",P.front);
	printf("front:%d top:%d out:%d\n",P.front,gettop(&P),outqueue(&P));
	showqueue(&P);
	clear(&P);
	showqueue(&P);
	return 0;
}
void initqueue(Queue*p)
{
	p->front=-1;
	p->rear=-1;
}
void clear(Queue*p)
{
	p->front=-1;
	p->rear=-1;
}
int gettop(Queue *p)
{
	if(p->front==p->rear)
	{
		printf("empty queue\n");
		exit(1);
	}
	return p->a[p->front+1];
}
int isempty(Queue *p)
{
	if (p->front==p->rear) return 1;
	else return 0;
}
int isfull(Queue *p)
{
	if (p->rear==N-1) return 1;
	else return 0;
}
void inqueue(Queue *p,int x)
{
	if(isfull(p))
	{
		printf("full queue\n");
		exit(1);
	}
	p->rear++;
	p->a[p->rear]=x;
}
int outqueue(Queue *p)
{
	if(p->front==p->rear)
	{
		printf("empty queue\n");
		exit(1);
	}
	p->front++;
	return p->a[p->front];
}
void showqueue(Queue *p)
{
	if(isempty(p))
	{
		printf("empty queue\n");
		return ;
	}
	int i;
	for(i=p->front+1;i<=p->rear;i++)
	{
		printf("%d ",p->a[i]);
	}
	printf("\n");
}

链式队列

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

typedef struct node{
	int data;
	struct node *next;
}Node;

typedef struct{
	Node *front;
	Node *rear;
}Queue; 

void initqueue(Queue*);
void clearqueue(Queue *);
int isempty(Queue *);
int gettop(Queue *);
int outqueue(Queue *);
void inqueue(Queue *,int);
void showqueue(Queue *);

int main()
{	Queue P;
	initqueue(&P);
	int i;
	for(i=0;i<6;i++)
	{
		inqueue(&P,i);
	}
	showqueue(&P);
	printf("out:%d \n",outqueue(&P));
	printf("top:%d\n",gettop(&P));
	showqueue(&P);
	clearqueue(&P);
	showqueue(&P);
	return 0;
}
void initqueue(Queue* p)
{
	p->front=NULL;
	p->rear=NULL;
}
void clearqueue(Queue* p)
{
	Node *q;
	while(p->front!=p->rear)
	{
		q=p->front;
		p->front=q->next;
		free(q);
	}
	free(p->front);
	p->front=NULL;
	p->rear=NULL; 
}
int isempty(Queue *q)
{
	if (q->front==NULL&&q->rear==NULL) return 1;
	else return 0;
}
int gettop(Queue *p)
{
	if (isempty(p))
	{
		printf("empty queue\n");
		exit(1);
	}
	return p->front->data;
}
int outqueue(Queue *p)
{	int temp;
	if (isempty(p))
	{
		printf("empty queue\n");
		exit(1);
	}
	if(p->front==p->rear)
	{   temp=p->front->data;
		p->front=NULL;
		p->rear=NULL;
		return temp;
		
	}
	else
	{
		temp=p->front->data;
		p->front=p->front->next;
		return temp;
	}
}
void inqueue(Queue *p,int x)
{
	Node *q=(Node*)malloc(sizeof(Node));
	q->data=x;
	if(p->front==NULL&&p->rear==NULL)
	{
		p->front=q;
		p->rear=q;
		q->next=NULL;
	}
	else
	{
		p->rear->next=q;
		q->next=NULL;
		p->rear=q;
	}
}
void showqueue(Queue *p)
{
	Node* q=p->front;
	if(isempty(p))
	{
		printf("empty queue\n");
		exit(1);
	}
	while(q!=NULL)
	{
		printf("%d",q->data);
		q=q->next;
	}
	printf("\n");
}

循环队列

#include<stdio.h>
#include<stdlib.h> 
const int MAXNUM=5;
typedef struct{
	int *data;
	int front;
	int rear;
}Cq,*Cqp;

void init(Cqp p);
int isempty(Cqp p);
int isfull(Cqp p);
void inque(Cqp p,int x);
int deque(Cqp p);
void showque(Cqp);

int main()
{
	Cqp p=(Cqp)malloc(sizeof(Cq)); 
	init(p);
	for(int i=0;i<MAXNUM;i++)
	{
		p->data[i]=0;
	}
	for(int i=0;i<3;i++)
	{
		inque(p,i+2);
	}
	showque(p);
	printf("\n");
	printf("%d\n",deque(p));
	inque(p,6);
	inque(p,98);
	showque(p);
	printf("\n%d",isfull(p));
	printf("rear=%d front=%d",p->rear,p->front);
	return 0;
	
}
void init(Cqp p)
{
	
	p->data=(int *)malloc(sizeof(int)*MAXNUM);
	p->front=0;
	p->rear=0;
}
int isempty(Cqp p)
{
	return p->front==p->rear;
}
int isfull(Cqp p){
	return (p->rear+1)%MAXNUM==p->front;
}
void inque(Cqp p,int x)
{
	if(isfull(p))
	{
		printf("full");
		exit(1);
	}
	p->data[p->rear]=x;
	p->rear=(p->rear+1)%MAXNUM;
}
int deque(Cqp p)
{
	if(isempty(p))
	{
		printf("empty");
		exit(0);
	}
	int temp=p->data[p->front];
	p->front=(p->front+1)%MAXNUM;
	return temp; 
}
void showque(Cqp p)
{
	for(int i=0;i<MAXNUM;i++)
	{
		printf("%d ",p->data[i]);
	}
}

Tips

顺序队列：
front指针所指元素无值
判断队列空：front==rear
判断队列满：rear?=N-1
链式队列：
front指针所指元素有值
判断队列空：front==rear==NULL;
判断队列满：队列不会满
入队：特殊处理队列空时的情况，将新的节点设为front和rear
出队：特殊处理队列空时的情况，front和rear设为NULL
循环队列：
front指针所指元素有值，rear所指元素无值
初始时front，rear都设为0
判断队列满：（rear+1）%MAX==front
判断队列空：front == rear
入队：先为rear所指位置赋值，

数组与广义表

数组的类型定义，顺序表示与实现

1.类型定义：

高维数组：

数据对象:
D = {aj1,j2,…ji…jn | 0≤i≤n, 0 ≤ji≤bi-1}
数据关系:
R = { R1,R2,…Rn }
Ri= {<aj1,j2,…ji…jn,aj1,j2,…ji+1…jn>| 0≤jk≤bk-1 k!=i, 0≤ji≤bi-2}

基本操作：

InitArray(&A, n, bound1, …, boundn)

DestroyArray(&A)

Value(A, &e, index1, …, indexn)

Assign(&A, e, index1, …, indexn)

二维数组：

数据对象:
D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1}
数据关系:
R = { ROW, COL }
ROW = {<ai,j,ai+1,j>| 0≤i≤b1-2, 0≤j≤b2-1}
COL = {<ai,j,ai,j+1>| 0≤i≤b1-1, 0≤ j≤b2-2}

基本操作同上

2.数组的顺序表示和实现

1）类型特点：

只有引用型操作，没有加工型操作

数组是多维的结构，而存储空间是**
一个一维的结构。**

2）有两种顺序映象的方式:
以行序为主序(低下标优先)；
以列序为主序(高下标优先)。

这里讨论以行序为主讨论地址计算：

二维数组：
数组的大小为mn：(i=0-m-1,j=0-n-1)
loc(i,j)=loc(0,0)+L(in+j)
n维数组：
数组大小为b1b2*…bn:(ji=0-bi-1)
loc(j1,j2…jn)=loc(0,0…0)+L(j1b2b3…bn+j2b3*…bn+…+jn-1bn+jn)

易见：数组元素的存储位置是其下标的线性函数。

稀疏矩阵的压缩存储

1.稀疏矩阵：σ=t/(mn) （非零元素个数/总数）稀疏因子小于0.05的矩阵为稀疏矩阵

2.分类：

1）特殊矩阵（分布有规则）：三角矩阵，对角矩阵

2）随机稀疏矩阵

在三元组顺序表中的压缩存储的下标变换公式;

对称矩阵压缩存储公式：

1<=i,j<=n k=0~(n+1)n/2-1

k=i(i-1)/2+j-1 (i>j)
k=j(j-1)/2+i-1 (i<=j)

下三角矩阵：

1<=i,j<=n k=0~(n+1)n/2-1

k=i(i-1)/2+j-1 (i>j)

上三角矩阵：

1<=i,j<=n k=0~(n+1)n/2-1

k=（2n+2-i)(i-1)/2+j-i

反下三角矩阵

1<=i,j<=n k=0~(n+1)n/2-1

k=(i-1)i/2+j-(n-i)-1

快速转置算法

typedef struct mytripple//定义三元组
{
	int i,j,data;
}TR;

typedef struct mymatrix//定义稀疏矩阵的数据结构
{
	TR T[N];//三元组数组
	int mu,nu,tu;//mu表示行数,nu表示列数,tu表示非零元的个数
}MA;
MA reversema(MA *A)//快速转置：时间复杂度O(nu+tu) 
{
	MA B;B.mu=A->nu;B.nu=A->mu;B.tu=A->tu;//行数，列数，非零元个数 
	int *Cpot=(int*)malloc(sizeof(int)*(A->nu+1));//每列第一个元素在新的三元顺序表中的位置 
	int *num=(int*)malloc(sizeof(int)*(A->nu+1));//每列与非零元素的个数 
	memset(num,0,sizeof(int)*(A->nu+1));
	int i,tempind;
	Cpot[1]=1;
	for(i=1;i<=A->tu;i++) num[A->T[i].j]++;
	for(i=2;i<=A->nu;i++) Cpot[i]=Cpot[i-1]+num[i-1];
	for(i=1;i<=A->tu;i++) 
	{	
		tempind=Cpot[A->T[i].j]++;
		B.T[tempind].i=A->T[i].j;
		B.T[tempind].j=A->T[i].i;
		B.T[tempind].data=A->T[i].data;
	}
	return B;
}

行逻辑链接

和上述快速转置算法中的cpot类似，添加存储每行行第一个元素所在位置的rpos数组。方便访问每行的元素，而不必从头开始遍历

访问矩阵元素
ElemType value(RLSMatrix M, int r, int c) {
  p = M.rpos[r];
  while (M.data[p].i==r &&M.data[p].j < c) 
      p++;
  if (M.data[p].i==r && M.data[p].j==c)
     return M.data[p].e;
  else return 0;
} // value

矩阵乘法：经典算法时间复杂度为O(m1*n2*n1)
    改进算法时间复杂度O(m1*n2)
typedef struct mytripple//定义三元组
{
	int i,j,data;
}TR;

typedef struct mymatrix//定义稀疏矩阵的数据结构
{
	TR T[N];//三元组数组
	int rpos[N];//每行第一个非零元所在序号 
	int mu,nu,tu;//mu表示行数,nu表示列数,tu表示非零元的个数
}MA;
MA multiply(MA *A,MA *B)//稀疏矩阵相乘
{
	MA C;C.mu=A->mu;C.nu=B->nu;C.tu=0;
	if (A->nu!=B->mu) exit(1);
	if (A->tu*B->tu==0)
	return C;
	int r1,c1,r2,c2,i,j,k;
	int e1,e2;
	int ctemp[N];
	for(r1=1;r1<=A->mu;r1++)
	{	
		C.rpos[r1]=C.tu+1;
		memset(ctemp,0,sizeof(int)*N);
		if(r1<A->mu) e1=A->rpos[r1+1];
		else e1=A->tu+1;
		for(i=A->rpos[r1];i<e1;i++)
		{
			r2=A->T[i].j;
			if(r2<B->mu) e2=B->rpos[r2+1];
			else e2=B->tu+1;
			for(j=B->rpos[r2];j<e2;j++)
			{
				c1=B->T[j].j;
				ctemp[c1]+=A->T[i].data*B->T[j].data;
			}
		}
		for(k=1;k<=B->nu;k++)
		{
			if(ctemp[k])
			{
				C.tu++;
				C.T[C.tu].i=r1;
				C.T[C.tu].j=k;
				C.T[C.tu].data=ctemp[k];
			}
		}
	}
	return C;
	 
}

广义线性表的表示

1.结构特点：

1. 广义表中的数据元素有相对次序；

2）广义表的长度定义为最外层包含元素个数

3. 广义表的深度定义为所含括弧的重数；“原子”的深度为 0 “空表”的深度为 1

4）广义表可以共享

5）广义表可以是一个递归的表。递归表的深度是无穷值，长度是有限值。

LS = ( a1, a2, a3, …an )
其中：ai 或为原子 或为广义表

6)任何一个非空广义表 LS = ( a1, a2, …, an)均可分解为
表头 Head(LS) = a1 和
表尾 Tail(LS) = ( a2, …,an) 两部分。

2.表示方法：

通常采用头、尾指针的链表结构：

表节点：tag=1，hp,hp

原子节点：tag=0,atom_data

存储表示：

typedef enum {ATOM,LIST} Elemtag;
typedef struct{
	Elemtag tag;
	union{
	AtomType atom;
	struct{
		struct GLnode *hp,*hp
		}ptr;
	}
};

树与二叉树

树的定义与结构特点

1.树的定义（root,F），基本术语，相关概念（有向树，有序树，无序树，森林）(具体见树)

2.结构特点：只有一个根节点；有若干叶子节点；根节点无前驱，其余有若干个前驱；叶子节点无后继，其余有若干个后继

3.二叉树的五个结构特性及证明：
（1） 第k层最多节点个数：2^(k-1)（归纳法易得）
（2）至第k层的累计节点数：2^k-1（利用（1）等比求和即可）
（3）n0=n2+1（边与节点数的关系：n0+n1+n2=n && n-1=n1+2n2）
（掌握完全二叉树与满二叉树的定义）
（4）完全二叉树的层数公式：[logn]+1（利用（2）:2^(k-1)<=n<2k）
（5）完全双亲节点与左右孩子节点的对应层次序号:序号为i，左孩子2i，右孩子2i+1，父亲节点：[i/2]（归纳易得）

二叉树的存储结构

顺序结构

树序号为i的节点存储在一维数组下标为i-1的分量中（适用于完全二叉树，不浪费空间）

链式结构

1）二叉链表（左右孩子指针）
2）三叉链表（左右孩子指针，双亲指针，方便直接找双亲节点）
3）双亲链表（方便直接找双亲节点）
4）线索链表（有效利用空指针域，若经常需要遍历链表查找前驱和后继，则比较适合使用线索链表）

二叉树的遍历

代码实现

typedef struct node
{
	char data;
	struct node *left,*right,*pa;
}BT;//定义二叉树的节点结构

void preorder(BT *T)//先序遍历二叉树（递归）
{	
	if(T)
	{
		printf("%c ",T->data);
		preorder(T->left);
		preorder(T->right);
	}
}
void inorder(BT *T)//中序遍历二叉树（递归）
{
 if(T)
	{
		inorder(T->left);
		printf("%c ",T->data);
		inorder(T->right);
	}
} 
void postorder(BT *T)//后序遍历二叉树（递归）
 {
 if(T)
	{
		postorder(T->left);
		postorder(T->right);
		printf("%c ",T->data);
	}
} 

void inorder2(BT *T)//中序遍历二叉树 （非递归）
{
	BT *t[N],*p=T;//定义栈，指针数组，可以存放指向结点的指针，指针p用来做遍历，p初始指向根节点
	int top=-1;//栈顶，初始栈为空
	while(top>=0||p)//只要栈非空或者指针p为真
	{
		while(p)//只要p为真
		{
			top++;//
			t[top]=p;//将p指向的节点压栈
			p=p->left;//继续向左走
		}
		p=t[top];//
		top--;//弹栈
		printf("%c ",p->data);//输出弹出的节点数值
		p=p->right;//指针p指向当前弹出节点的右，如果有右，继续按照如上的步骤找到最左，然后弹栈
		          //输出....;如果没有右，则继续弹栈
	}
	printf("\n");
} 

void postorder2(BT *T)//后续遍历二叉树（非递归） 
{
	BT *t[N];//定义栈，指针数组，可以存放指向结点的指针
	BT *p=T,*b;//指针p用来做遍历，初始指向根节点；指针b用来存放刚刚访问过的节点
	int top=-1;//初始栈为空
	do//注意循环的样式
	{
		while(p)//只要指针p为真
		{
			top++;//
			t[top]=p;//将指针p指向的节点压栈
			p=p->left;//继续向左走
		}
		b=NULL;//给b赋起始值
		while(top>=0)//如果当前栈非空
		{
			p=t[top];//观察栈顶，判断栈顶元素的右孩子有没有被访问过
			if(p->right==b)//如果刚访问过的节点就是栈顶的右
			{
				p=t[top];//说明当前的栈顶元素可以弹出（弹出意味着可以访问）
				top--;//
				printf("%c ",p->data);//输出该结点数值
				b=p;//将刚刚访问的节点指向赋值给b
			}
			else//如果刚访问过的节点不是栈顶的右
			{
				p=p->right;//不能弹栈，要进入栈顶的右分支，
				break;//并从当前的循环中退出，回到第一层的循环体内，继续上述的操作
			}
		}

	}while(top>=0);//只要栈非空
	printf("\n");
}
void layer(BT *T)//层次遍历（非递归）
{
	BT *t[N],*p;
	int top=-1,rear=-1;//初始化空队列 
	if(T) t[++rear]=T;//根节点入队 
	while(top!=rear)//当队列非空时 
	{
		p=t[top+1];//根节点开始向下遍历 
		printf("%c ",p->data);//输出根节点 
		if(p->left) t[++rear]=p->left;//左孩子入队 
		if(p->right) t[++rear]=p->right;//右孩子入队 
		top++;//根节点出队，进行其右侧相邻兄弟节点或下一个层次的最左侧节点的遍历 
	}
	printf("\n");
 } 
 //以上都是从左至右的遍历，可以根据要求改为从右至左，不要太死板

应用举例

统计叶子节点数目

 void countleaf(BT *T,int &count)//统计叶子节点的个数(先序遍历） 
 {
 	if(T)
 	{
 		if(!(T->left||T->right)) count++;
 		countleaf(T->left,count);
 		countleaf(T->right,count);
	 }
  } 

统计树的层数

int countlayer(BT *T)//统计树的层数 (后序遍历） 
  {
  	if (!T) return 0;
	else return 1+(countlayer(T->left)>countlayer(T->right)?countlayer(T->left):countlayer(T->right));
  } 

复制树

BT *gettreenode(char data,BT *left,BT *right,BT *pa)//得到一个树的节点
{
  	BT *node=(BT*)malloc(sizeof(BT));
  	node->data=data;
  	node->left=left;
  	node->right=right;
  	node->pa=pa;
  	return node;
} 
BT *copytree(BT *T)//复制树(后序遍历） 
{	BT *L,*R;
	if(!T) return NULL;
	else
	{
		L=copytree(T->left);
		R=copytree(T->right);
	} 
	return gettreenode(T->data,L,R,T->pa);	//获得左右子树再与根节点链接 
}

建立二叉树的存储结构

含空格的字符串建树

 BT *createbt(char *pre,int *k)
 //这里用int*是为了保证进行递归时先序数组会一直向下读取，当左子节点完成初始化后读取的是右子节点 
 {	BT *A;
 	//注意：两种情况都要有返回值 （k对应的值所在节点的指针） 
 	if (pre[*k]!=' ')//根节点非空 ，表示该根节点存在 
 	{
 		A=(BT *)malloc(sizeof(BT));//分配空间 
 		A->data=pre[*k];//赋值 
 		(*k)++;//读取左子节点 
 		A->left=createbt(pre,k);//以左子节点作为新的根初始化 
		(*k)++;//读取右子节点 
		A->right=createbt(pre,k); //以右子节点作为新的根初始化 
		return A; 
	}
	else return NULL;
 }

根据先序序列和中序序列建树

只有先序序列的话无法确定根节点左右子树的根节点位置，这时就需要中序序列求出左右子树的节点个数，并将其应用到先序序列中得到右子树根节点位置。

BT *createbt2(char *pre,char *in,int k)//根据先序,中序创建二叉树
 //pre指向根节点，in为中序遍历得到的列表，k为中序序列当前根节点左/右侧的点个数 
 {	
 	BT *T;
 	int i,j;
 	if (k<=0) //如果该点下一层左或右侧没有子节点，则将该节点的子节点赋为NULL 
		return NULL;
 	else
 	{	
	 	T=(BT *)malloc(sizeof(BT));
 		T->data=pre[0];
 		for(i=0;in[i]!=pre[0];i++);
 		//每次递归传入新的根节点值在先序表里面的指针，新的搜索起点，集合元素个数 
 		T->left=createbt2(pre+1,in,i);
		T->right=createbt2(pre+i+1,in+i+1,k-i-1);
 		return T;
	}
 }

注意二叉树与表达式的关系

以操作符为根节点和分支节点，操作数为叶子节点建树。先序遍历就是前缀表达式，中序遍历就是中缀表达式，后序遍历就是后缀表达式

//先缀表达式建树如下
//中缀表达式建树放在课设里面了
BT *createtree(char *expression,int *k)
{
	
	if(isoperator(expression[*k]))
	{
		BT *T=(BT*)malloc(sizeof(BT));
		T->data=expression[*k];
		(*k)++;
		T->left=createtree(expression,k);
		(*k)++;
		T->right=createtree(expression,k);
		return T;
	}
	else
	{	
		BT *T=(BT*)malloc(sizeof(BT));
		T->data=expression[*k];
		T->left=NULL;
		T->right=NULL;
		return T;
	}
}

int isoperator(char c)
{
	if(c==43||c==45||c==42||c==47) return 1;
	else return 0;
}

线索二叉树

（1）理解二叉树线索化的实质：建立结点与其在相应序列中的前驱或后继之间的直接联系
（2）线索化的过程实际上就是修改节点的空指针使其指向相应遍历序列里面的前驱和后继，相关的算法描述个人没办法直观看一眼就明白其操作含义，最好还是画图依照算法的步骤执行几步，看看能不能理解每每步究竟在干嘛。中序遍历的线索化过程的算法描述如下：

先看inorderthreading函数，传进去的参数是thrt（头节点），T（树的根节点）：首先为头节点分配空间，thrt的左标志域设为link，即thrt的左指针指向节点，thrt的右标志域为thread，即thrt的右指针指向遍历序列里面的节点，然后将其右指针指向自己（意义不明，不影响后面的理解），如果根节点不是空树，那么就将头节点左指针指向根节点，pre（刚刚访问过的节点，是一个全局变量，由两个函数共享），头节点的初始化完成后，接下来看重头戏–>inthreading（T),要记得这个线索化是给予中序遍历的线索化，因此要先对根节点的左子树进行操作，然后是根节点，最后是右子树。利用递归思想：首先对左子树进行线索化，（要记得我们是想将中序遍历所得的序列给予前驱后继关系，将整个序列链接起来。）然后看目前的节点p有没有前驱，如果他有左孩子的话，那么按照中序遍历的规则，他的左孩子就是他的前驱，如果他没有左孩子，那么就以刚刚访问的节点pre作为他的前驱。如果刚刚访问的节点pre没有后继，那么就将该点p作为pre的后继（实际上pre就是他的作为叶节点的左孩子。接下来将pre=p（因为接下来访问的是右子树，右子树根节点的前驱就是p），再将其右子树线索化。多说无益，看图（thrt的0和1画反了，最后一张才改过来）：
———————————————

thrt的指向实际上是为了方便正向和反向遍历，遍历算法考试好像没什么要求，理解掌握了了线索化即可。

对于中序线索化，对于每个节点来说，要知道如何找前驱和后继：前驱，如果一个节点的Ltag为link，那么就找他左子树最后访问的节点，即左子树右下角，如果是thread,那么直接就是thread指向的内容；后继，如果一个节点的Rtag为link，那么就找他右子树第一个访问的节点，即右子树左下角，如果是thread,那么直接就是thread指向的内容；
———————————————

树与森林

树的存储结构

双亲表示法

孩子链表表示法

树的二叉链表（孩子兄弟表示）

掌握树与二叉树 森林与二叉树的转换规则

树与森林的遍历

对应关系：

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

这里主要关注树的遍历：

void preorder(TR *T)
{
	if(T)
	{
		printf("%c ",T->data);
		preorder(T->fir);
		preorder(T->sib);
	}
	
	
}

void postorder(TR *T)//树的后序遍历就是对应二叉树的中序遍历 
{
	TR *t[N],*p=T;
	int top=-1;
	while(top>=0||p)
	{
		while(p)
		{
			top++;
			t[top]=p;
			p=p->fir;
		}
		p=t[top];
		top--;
		printf("%c ",p->data);
		p=p->sib;
	}
	/*if(T)
	{
		postorder(T->fir);
		printf("%c ",T->data);
		postorder(T->sib);
	}*/
	
	
}
void layer(TR *T)//层次遍历 
{
	TR *p=T;
	int front=-1,rear=-1;
	TR *t[N];
	t[++rear]=T;
	printf("%c ",p->data);
	while(rear!=front)
	{	
		p=t[front+1]->fir;
		while(p)
		{	
			t[++rear]=p;
			printf("%c ",p->data);
			p=p->sib;
		}
		front++;
		
	}
	printf("\n");
}

遍历算法的应用

求树的深度

int height(TR *T)
{	
	int h1,h2;
	if(T)
	{	//一棵树的高度是这棵树的子树高度加1与兄弟节点树高度中的最大值 
		h1=1+height(T->fir);
		h2=height(T->sib);
		return h1>h2?h1:h2;
	}
	else return 0;
}

输出树中所有从根到叶子的路径

void allpath(TR *T,char *route,int top)
{	TR *p;
	if(T)
	{	route[++top]=T->data;
		if(!T->fir)
		{
			int i;
			for(i=0;i<=top;i++)
			printf("%c ",route[i]);
			printf("\n");
		}
		else
		{	
			p=T->fir;
			while(p)
			{
				allpath(p,route,top);
				p=p->sib; 
			}	
		}
	}
}

建立树的输出结构

见课设选修家谱设计

Huffman树与Huffman编码

最优树

树的带权路径长度：

叶子节点值与根节点到叶子节点路径长度乘积的求和

最优树：使得上述带权路径长度最小的树

huffman算法（构建最优树）

据给定的 n 个权值 {w1, w2, …, wn}，构造 n 棵二叉树的集合F = {T1, T2, … , Tn}，其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树。在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；从F中删去这两棵树，同时加入刚生成的新树。一直这样构造下去直到只剩一颗树。

正确性理解：
对于有限个叶子节点(w1<=w2<=…<=wn)，其组合出的树一定是有限个 ，那么最优树一定存在。对于最优树T而言，欲证明从根节点到叶子节点的所有路中，最长的那一条的最后一个分支节点的两片叶子一定是w1,w2（没有度为1的点）：如果不是w1,w2的话，将w1,或w2与任意一个其他分支的叶子节点互换，显然权值乘路长的总和都不会减少，只能不变或增加，得证。将w1,w2收缩，对于新树T’,w(T’)+w1+w2=w(T),那么T’是（w’,w3,—wn)的最优树（如果不是最优树，假设有新的最优树T’’,那么将T’‘的w’展开为w1,w2，得到的新树T’’’,w(T’’’)=w(T’’)+w1+w2<w(T’)+w1+w2=w(T),与T为最优树矛盾）。因此对于T’而言，最小权值的两个叶子节点一定也是同分支的，这样一直进行下去。可以发现，这正是Huffman树的构造算法。

huffman编码

对于编码而言，如果一个字符的编码是另一个字符编码的前几个时，在解码时便不知道读到哪里才算一个字符。但根据二叉树来定义的编码就没有这一缺点，这就是前缀编码（一个字符的编码不是是另一个字符编码的前缀），编码的长度便为根到叶子节点的长度。在确定编码方式后，想要让总的编码长度最短，就是对于每个字符，出现次数乘编码长度最短，这正是huffma树的所具有的特点。

示例

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JZq6t7sI-1590853395383)(C:\Users\l\AppData\Roaming\Typora\typora-user-images\image-20200530162918370.png)]

具体程序见课设

图

抽象数据类型表示和存储表示

抽象数据类型表示：

图是由一个顶点集 V 和一个弧集 R构成的数据结构Graph = (V , R )其中，VR＝{<v,w>| v,w∈V 且 P(v,w)}
<v,w>表示从 v 到 w 的一条弧，并称 w 为弧头，v 为弧尾。谓词 P(v,w) 定义了弧 <v,w>的意义或信息

了解概念：

有向图，无向图，网、子图 ，完全图、稀疏图、稠密图、邻接点、度、入度、出度、路径、路径长度、简单路径、简单回路、连通图、连通分量、
强连通图、强连通分量、生成树、生成森林

存储表示：

邻接矩阵，邻接表，逆邻接表

抽象数据类型：(其实也不抽象…)

typedef struct arc
{
int index;//邻接点的编号
int weight;//边的权值
struct arc *next;//指向下一个邻接点
}AR;//弧

typedef struct mygragh
{
int arcnum;//图中边的数量
int vexnum;//图中顶点数量
int type;//图的类型（比如，1表示有向图（网），0表示无向图（网））
AR *N;//为邻接表的表头定义动态数组
char **vexname;//存储顶点名的动态数组
int **A;//邻接矩阵动态数组
}GH;//

图的遍历

深度优先搜索(DFS)

时间复杂度：O(arcnum+vexnum)

void DFSvisit(GH *G)
{
	int i,*visit;
	visit=(int *)malloc(G->vexnum*sizeof(int));
	memset(visit,0,G->vexnum*sizeof(int));
	for(i=0;i<G->vexnum;i++)
	{
		if(!visit[i])
			DFS(G,visit,i);
	}
	printf("\n");
	free(visit);
}

void DFS(GH *G,int *visit,int index)
{	
	AR *p;
	printf("%s ",G->vexname[index]);
	visit[index]=1;
	p=G->N[index].next;
	while(p)
	{
		if(visit[p->index]==0)
			DFS(G,visit,p->index);
		p=p->next;
	}
////////////////////////////////////////////////////////////////
	/*int i;
	printf("%s ",G->vexname[index]);
	visit[index]=1;
	for(i=0;i<G->vexnum;i++)
	{
		if(G->A[index][i]&&visit[i]==0)
			DFS(G,visit,i);
	}*/
}

广度优先搜索（BFS)

时间复杂度：O(arcnum+vexnum)

void BFSvisit(GH *G)
{
	int i,*visit;
	visit=(int *)malloc(G->vexnum*sizeof(int));
	memset(visit,0,G->vexnum*sizeof(int));
	for(i=0;i<G->vexnum;i++)
	{
		if(!visit[i])
			BFS(G,visit,i);
	}
	printf("\n");
	free(visit);
}

void BFS(GH *G,int *visit,int index)
{
	int *q,front=0,rear=0,i;
	AR *p;
	q=(int *)malloc(G->vexnum*sizeof(int));
	q[rear]=index;
	rear++;
	visit[index]=1;
	while(front!=rear)
	{
		i=q[front];
		front++;
		printf("%s ",G->vexname[i]);
		p=G->N[i].next;
		while(p)
		{
			if(visit[p->index]==0)
			{
				q[rear]=p->index;
				rear++;
				visit[p->index]=1;
			}
			p=p->next;
		}
	}
	free(q);
}

搜索算法的应用

无向图中的最短路径

typedef struct node
{
	int index,pa;
}QU;

void findmin(GH *G,char *start,char *end)
{
	QU *q=(QU *)malloc(sizeof(QU)*G->vexnum);
	int *path=(int *)malloc(sizeof(int)*G->vexnum);
	int *visit=(int *)malloc(sizeof(int)*G->vexnum);
	memset(visit,0,sizeof(int)*G->vexnum);
	AR *p;
	int rear=-1,front=-1;
	q[++rear].index=findvex(G,start);
	q[rear].pa=front;
	while(front!=rear)
	{
		p=G->N[q[front+1].index].next;
		while(p)
		{
			if(visit[p->index]==0)
			{
				q[++rear].index=p->index;
				q[rear].pa=front+1;
				visit[p->index]=1;
				if(strcmp(G->vexname[p->index],end)==0)
				break;
			}
			p=p->next;
		}
		if(!p) front++;
		else break;
	}
	front=-1;
	int k=q[rear].pa;
	path[++front]=q[rear].index;
	while(k!=-1)
	{
		path[++front]=q[k].index;
		k=q[k].pa;
	}
	for(k=front;k>=0;k--)
	{
		printf("%s ",G->vexname[path[k]]);
	}
	printf("\n");
}

寻找无向图中举例给定节点举例最远的点

int findfar(GH *G,char *start)
{
	int *t=(int *)malloc(sizeof(int)*G->vexnum);
	int *visit=(int*)malloc(sizeof(int)*G->vexnum);
	memset(visit,0,sizeof(int)*G->vexnum);
	int front=-1,rear=-1;
	t[++rear]=findvex(G,start);
	visit[rear]=1;
	AR p,*q;
	while(front!=rear)
	{
		p=G->N[t[front+1]];
		q=p.next;
		while(q)
		{	
			if(!visit[q->index])
			{	
				t[++rear]=q->index;
				visit[q->index]=1;
			}
			q=q->next;
		}
		front++;
	 } 
	 return t[rear];
}

寻找两点间的所有路径

void findpath(GH *G,char *start,char *end)
{
	int i,j;
	int *path;//存路径结点的序号 
	int *visit;//标志状态 
	i=findvex(start,G);
	j=findvex(end,G);
	path=(int *)malloc(G->vexnum*sizeof(int));
	path[0]=i;//第一个结点加入路径 
	visit=(int *)malloc(G->vexnum*sizeof(int));
	memset(visit,0,G->vexnum*sizeof(int));
	visit[i]=1;//将起点标位不可行 
	allpath(G,i,j,path,1,visit,0); 
}
void allpath(GH *G,int i,int j,int *path,int n,int *visit,int sum)
{
	int k;
	AR *p;
	if(i==j) 
	{
		for(k=0;k<n;k++)
		{
			printf("%s  ",G->vexname[path[k]]);
		}
		printf("路径长度为：%d",sum);
		printf("\n");
	}
	else
	{	
		p=G->N[i].next;//找到下一个可行点 
		while(p)//对所有邻接点尝试访问 
		{
			if(visit[p->index]==0)//如果该点未访问过 
			{
				path[n]=p->index;//将该点的序号加入路径
				visit[p->index]=1;//加入路径以后该点被访问过 
				allpath(G,p->index,j,path,n+1,visit,sum+p->weight);
				visit[p->index]=0;
			}
			p=p->next;//尝试下一个邻接点 
		}
	}
}

寻找所有回路

void findcycle(GH *G,char *start) 
{	//找回路，深度优先搜索，起点的visit始终设为0，每次递归完成后都会把1的visit还原为0以找到所有通路 
	int top=-1,sum=0;
	int *path=(int *)malloc(sizeof(int)*G->vexnum);
	int stid=findvex(start,G);
	int *visit=(int *)malloc(sizeof(int)*G->vexnum);
	path[++top]=stid;
	memset(visit,0,sizeof(int)*G->vexnum);
	circle(G,stid,path,top,visit,&sum);
	if(!sum)
		printf("没有回路\n");

}
void circle(GH *G,int start,int *path,int top,int *visit,int *sum)
{	
	int i;
	
	if(start==path[top]&&top>2)
	{
		(*sum)++;
		
		for(i=0;i<=top;i++)
		    printf("%s ",G->vexname[path[i]]);
		printf("\n");
	}
	else
	{	
		AR *q=G->N[path[top]].next;
		while(q)
		{	
			if(visit[q->index]==0)
			{
				path[top+1]=q->index;
				visit[q->index]=1;
				circle(G,start,path,top+1,visit,sum);
				visit[q->index]=0;
			}
			q=q->next;
		}
	}
}

判断是否联通

int isconnect(GH *G)
{
	int i;
	int ans=0;//连通分支
	int *visit=(int *)malloc(sizeof(int)*G->vexnum);
	memset(visit,0,sizeof(int)*G->vexnum);
	for(i=1;i<G->vexnum;i++)
	{
		if(!visit[i])
		{
			DFS(G,visit,i);
			ans++;
		}
	}
	free(visit);
	if(ans==1)
		return 1;
	else if(ans>1)
		return 0;
	
}

判断是有环

int iscycle(GH *G)
{
	int i;
	int ans=0;//连通分支
	int *visit=(int *)malloc(sizeof(int)*G->vexnum);
	memset(visit,0,sizeof(int)*G->vexnum);
	for(i=1;i<G->vexnum;i++)
	{
		if(!visit[i])
		{
			DFS(G,visit,i);
			ans++;
		}
	}
	free(visit);
	if(G->arcnum+ans>G->vexnum)
	//边数加联通分支数大于点的个数则有环
		return 1;
	else
		return 0;

}

最小生成树

Prim算法

算法描述：
图中顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边

时间复杂度：

O(n^2) 适用于稠密图

要求会手动实现：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oaFGkMFu-1590853395386)(…/…/…/AppData/Roaming/Typora/typora-user-images/image-20200530213304729.png)]

Kruskal算法

算法描述：
先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止

时间复杂度：

O(eloge) 适用于稀疏图

手动实现：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AsD3JGU3-1590853395388)(…/…/…/AppData/Roaming/Typora/typora-user-images/image-20200530213519200.png)]

拓扑排序

拓扑有序序列：

在有向图中找到一个没有入度的节点，删掉该点与之相邻的弧，然后继续找没有入度的节点，删掉该点与之相邻的弧，一直做下去，直至图点的个数为0。显然如果有向图中含有回路，则不存在拓扑序列

int tuopu(GH *G,int *t)
{	//拓扑排序：t用来存储拓扑序列 
	int *st,top=-1,count=0,i,*du;
	AR *p;
	st=(int *)malloc(G->vexnum*sizeof(int));//入度为0的点的zhai 
	du=(int *)malloc(G->vexnum*sizeof(int));//每个点的入度 
	memset(du,0,G->vexnum*sizeof(int));
	for(i=0;i<G->vexnum;i++)
	{
		p=G->N[i].next;
		while(p)
		{
			du[p->index]++;
			p=p->next;
		}
	}
	for(i=0;i<G->vexnum;i++)
	{
		if(du[i]==0)
		{
			top++;
			st[top]=i;
		}
	}
	while(top>=0)
	{
		i=st[top];
		top--;
		t[count]=i;
		count++;
		p=G->N[i].next;
		while(p)
		{
			du[p->index]--;
			if(du[p->index]==0)
			{
				top++;
				st[top]=p->index;
			}
			p=p->next;
		}
	}
	free(st);
	free(du);
	if(count==G->vexnum)
		return 1;
	else
		return 0;
	
}

关键路径：见课设

两点间最短距离

源点到其余各点的最短路径（DIJKSTRA)

算法描述：

依最短路径的长度递增的次序求得各条路径。在这条路径上，必定只含一条弧，并且这条弧的权值最小（v0-v1)。

下一条路径长度次短的最短路径的特点：它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成) （可先去掉v1，那么v0向外最短的一条弧就是最短路线，再短的只有可能出现在添加v1后经过v1再到它的路线,）。再下一条路径长度次短的最短路径的特点：它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。其余最短路径的特点：它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。

正确性理解:

归纳法证明：假设对于每次进入永久标号集合S的点ui，依照它的前驱形成的都是最短路。第一个入S的点为起点u1，它的前驱就是u1，显然u1到u1的最短路就是u1->u1，长度为0.假设第n个入队的点满足假设，那么对于第n+1个入队的点v来说，利用反证法，如果d[u1,v]不是u1到v的最短路径，存在另一条更短的路径，那么记该路径最后一个属于S的点为x，x经过若干个点最后到达v，记y是x的后继，那么d[u1,v]<=d[u1,y],(若d[u1,v]>d[u1,y],那么这次入S的便是y而不是v),所以d[u1,y]+d[y,v]>=d[u1,v]，矛盾。

手动实现：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mxEPC4qP-1590853395389)(…/…/…/AppData/Roaming/Typora/typora-user-images/image-20200530223104566.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CX1HYug4-1590853395390)(…/…/…/AppData/Roaming/Typora/typora-user-images/image-20200530223131836.png)]

代码实现：

void dijkstra(GH *G,int start)
{	
	int k;
	int *dis=(int *)malloc(sizeof(int)*G->vexnum); 
	int *path=(int *)malloc(sizeof(int)*G->vexnum);
	int *flag=(int *)malloc(sizeof(int)*G->vexnum);
	memset(flag,0,sizeof(int)*G->vexnum);
	//初始化
	for(int i=0;i<G->vexnum;i++)
	{
		dis[i]=G->A[start][i];
		if(dis[i]<MAX) path[i]=start;
		else path[i]=-1;
	}
	flag[start]=1;
	
	for(int i=0;i<G->vexnum-1;i++)
	{
		k=findmin(G->vexnum,flag,dis);
		if(k>0)
		{
			flag[k]=1;
			for(int h=0;h<G->vexnum;h++)
			{
				if(flag[h]==0 && dis[h]>dis[k]+G->A[k][h])
				{	
					dis[h]=dis[k]+G->A[k][h];
					path[h]=k;
				}
			 } 
		}
	}
	showpath1(G->vexnum,flag,path,dis,start);
	free(dis);
	free(path);
	free(flag);
} 

任意两点间的最短距离（FLOYD)

算法思想：

自己看书

手动实现：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eHdF4j4r-1590853395393)(…/…/…/AppData/Roaming/Typora/typora-user-images/image-20200530223431198.png)]

代码实现：

void floyd(GH *G)
{
	int **P=(int **)malloc(sizeof(int *)*G->vexnum); 
	int **D=(int **)malloc(sizeof(int *)*G->vexnum);
	for(int i=0;i<G->vexnum;i++)
	{
		P[i]=(int *)malloc(sizeof(int)*G->vexnum);
		D[i]=(int *)malloc(sizeof(int)*G->vexnum);
		for(int j=0;j<G->vexnum;j++)
		{
			D[i][j]=G->A[i][j];
			if(D[i][j]<MAX) P[i][j]=i;
			else P[i][j]=-1;
		}
	 } 
	 for(int k=0;k<G->vexnum;k++)
	 {
	 	for(int i=0;i<G->vexnum;i++)
	 	{
	 		for(int j=0;j<G->vexnum;j++)
	 		{
	 			if(D[i][j]>D[i][k]+D[k][j])
	 			{
	 				D[i][j]=D[i][k]+D[k][j];
	 				P[i][j]=k;
				 }
			 }
		 }
	 }
	 printf("WAY :\n");
	 for(int i=0;i<G->vexnum;i++)
	 {
	 	for(int j=0;j<G->vexnum;j++)
	 	{	
		 	if(P[i][j]!=-1&&i!=j)
	 		{
			 printf("len:%d :",D[i][j]);
			 printf("v[%d] ",i);
			 showpath3(G->vexnum,D,P,i,j);
	 		 printf("\n");
			} 
			else if(P[i][j]==-1 && i!=j)
			{
				printf("no path:v[%d]->v[%d]\n",i,j);
			}
		 }
		 
	 }
	 free(P);
	 free(D);
} 
void showpath3(int n,int **D,int **P,int st,int ed)
{
	if(st==P[st][ed])
	printf("->v[%d]",ed);
	else
	{
		showpath3(n,D,P,st,P[st][ed]);
		showpath3(n,D,P,P[st][ed],ed);
	}
}

floyd算法应用

1.输出有向图的根节点：

在最后的D矩阵中，如果某一行的所有dis均小于max，即该点到所有点都有路线，则该点即为根节点

2.建立一家医院，使得所有村庄的总体交通代价最小：

在已经求得D，P矩阵后，对于每个点，求得该点到其余所有点和的距离s1，其余点到该点的距离和s2，将s1+s2作为总体交通代价，寻找总体交通代价最小的点即可

3.注意最短路径树与最小生成树的区别

查找

因为画图实在太多，这一部分就拿记的课上笔记来代替了（字丑见谅）

文字笔记和画图

相关代码实现

//静态查找
#include<stdio.h>
#include<stdlib.h>//随机数 

int ordersearch(int *,int,int);//顺序查找
int halforder(int *,int ,int);//折半查找
void sort(int *,int);//排序 
int question1(int *,int n);//例题
 
int main()
{	
	int n,target;
	printf("数组大小"); 
	scanf("%d",&n); 
	int *a=(int *)malloc(sizeof(int)*(n+1));
	printf("显示数组\n"); 
	for(int i=1;i<=n;i++) 
	{
		a[i]=rand()%100;
		printf("%d ",a[i]);
		if(i%20==0) printf("\n");
	}
	printf("查找目标"); 
	scanf("%d",&target);
	printf("顺序查找:");
	printf("%d\n",ordersearch(a,target,n));
	sort(a,n);
	for(int i=1;i<=n;i++)  printf("%d ",a[i]);
	printf("折半查找:");
	printf("%d\n",halforder(a,target,n));
	printf("a[i]==i?:");
	if (question1(a,n)>=0)
	printf("a[%d]==%d",question1(a,n),question1(a,n)); 
	else printf("no such thing");
	return 0;
	
 } 
 int ordersearch(int *a,int target,int n)
 {
 	a[0]=target;//目标放在0位置作为哨兵
	for(int i=n;;i--)
	{
		if(target==a[i])//最后一定有返回值 
		return i;
	 } 
 }
 void sort(int *a,int n)
 {	int i,j,temp;
 	for(i=1;i<=n-1;i++)
 	{
 		for(j=i+1;j<=n;j++)
 		{
 			if(a[j]<a[i])
 			{
 				temp=a[i];
 				a[i]=a[j];
 				a[j]=temp;
			 }
		 }
 	
	 }
 }
 int halforder(int *a,int target,int n)
 {	//逐步缩小查找区间 
 	int low=1,high=n,mid;
 	while(low<=high)
 	{	
	 	mid=(low+high)/2;
 		if(a[mid]==target) return mid;
 		else if(a[mid]<target) low=mid+1;
		else high=mid-1;
	}
	return -1;
 }
 int question1(int *a,int n)
 {
 	//检查是否含有使得a[i]=i的i存在
	int low=1,high=n,mid;
 	while(low<=high)
 	{	
	 	mid=(low+high)/2;
 		if(a[mid]==mid) return mid;
 		else if(a[mid]<mid) low=mid+1;
		else high=mid-1;
	}
	return -1;//无 
 } 

//动态查找（BST)
#include "stdio.h"
#include "stdlib.h"
#define N 100
typedef struct node
{
	int data;//关键字 
	int ban;//0 平衡 -1；左高 1右高 
	struct node *left,*right;
}BST;//二叉链 

BST *createbst(int n);
BST *insnode(BST *T,int data);
void showbst(BST *T);
BST *delnode(BST *T,int data);
BST *delbst(BST *T);
BST *findnode(BST *T,int data);

main()
{
	BST *T=NULL;
	int n,x,i;
	printf("请输入数据规模:\n");
	scanf("%d",&n);
	while(n>0)
	{
		T=createbst(n);
		printf("二叉排序树：\n");
		showbst(T);		
		printf("输入要删除的节点：");
		scanf("%d",&x);
		T=delnode(T,x);
		printf("删除后BST");
		showbst(T); 
		T=delbst(T);
		printf("\n请输入数据规模:\n");
	    scanf("%d",&n);
	}
}

BST *createbst(int n)
{
	int i,x;
	BST *T=NULL;
	for(i=0;i<n;i++)
	{
		x=rand()%N;
		T=insnode(T,x);
	}
	return T;
}
BST *insnode(BST *T,int data)
{	//非递归 
	BST *pa=NULL,*p=T;
	while(p)
	{
		if(p->data==data) break;
		else if(p->data>data) 
		{
			pa=p;
			p=pa->left;
		}
		else
		{
			pa=p;
			p=pa->right;
		}
	}
	if(p) return T;//该点已经在树中存在 
	else
	{
		p=(BST *)malloc(sizeof(BST));
		p->data=data;
		p->left=p->right=NULL;
		if(!pa) return p;//空树 
		else
		{
			if(pa->data>p->data) pa->left=p;
			else pa->right=p;
		 } 
	}
	return T;
	//递归 
	/*if(!T)
	{
		BST *p=(BST *)malloc(sizeof(BST));
		p->data=data;
		p->right=p->left=NULL;
		return p; 
	}
	else if(T->data==data) return T;
	else if(T->data>data) T->left=insnode(T->left,data);
	else T->right=insnode(T->right,data);
	return T;*/ 
}
void showbst(BST *T)
{
	if(T)
	{
		printf("%d",T->data);
		if(T->left||T->right)
		{
			printf("(");
			showbst(T->left);
			printf(",");
			showbst(T->right);
			printf(")");
		}
	}
}
BST *delnode(BST *T,int data)
{
	BST *p=T,*pa=NULL,*q;
	while(p)
	{
		if(p->data<data)//查找目标 
		{
			pa=p;
			p=pa->right;
		}
		else if(p->data>data)//查找目标 
		{
			pa=p;
			p=pa->left;
		}
		else
		{	
			if(!p->left)//左子树空 
			{
				q=p;
				p=p->right;
				if(!pa)
				{
					free(q);
					rerturn p; 
				} 
				else if(pa->data>q->data) pa->left=p;
				else pa->right=p;
				free(q);
			}
			else if(!p->right)//右子树空 
			{
				q=p;
				p=p->left;
				if(!pa)
				{
					free(q);
					rerturn p; 
				} 
				if(pa->data>q->data) pa->left=p;
				else pa->right=p;
				free(q);
			}
			else//左右子树均非空 
			{	BST *s; 
				q=p;//针对p->left=s已经是最右下的时候 
				s=p->left;//在左子树中 
				while(s->right)//找到最右下元素 
				{	
					q=s;
					s=q->right;
				}
				printf("【%d】",s->data);
				p->data=s->data;//替换目标节点的值 
				if(p!=q) q->right=s->left;
				else q->left=s->left;
				free(s);	
			} 
			break;
		}
	}
	return T;
}
BST *delbst(BST *T)
{
	if(!T)
		return NULL;
	else
	{
		T->left=delbst(T->left);
		T->right=delbst(T->right);
		free(T);
		return NULL;
	}
}
BST *findnode(BST *T,int data)
{	
	//递归 
	/*
	if(!T) return NULL;
	else if(T->data==data) return T;
	else if(T->data>data) return findnode(T->left,data);
	else return findnode(T->right,data); */
	//非递归
	while(T)
	{
		if(T->data==data) return T;
		else if(T->data>data) T=T->left;
		else T=T->right;	
			
	 } 
	 return NULL; 
}

排序

基本术语

1.稳定的排序算法：相同关键字的记录在排序前后记录的相对位置不变
一般来说：若比较是在两个相邻的关键字之间进行的，则一般是稳定的
2.分类：内部排序（待排序列存储在内存中） 外排序列（待排序列存储在外部存储器中） 这一章只考虑内排
3.内排是一个逐步扩大有序序列长度的过程
4.常见内排：
简单排序：插入类，交换类，选择类
改进排序：希尔排序，快速排序，堆排序
归并排序，基数排序
5.内排的评价标准:时间复杂度，空间复杂度，稳定性，对数字的敏感程度（最好最坏情况下比较，移动的次数）

插入类排序

直接插入

算法描述

将一个记录插入到已有的有序序列中，从而使得有序序列的长度加一。将第一个元素看为有序的，从第二个元素开始，将它的值存在哨兵位，然后向左寻找插入位置（最后一个大于它的数的左侧，即第一个小于它的数的右侧），将这个位置之后的数向后移动一位，再将哨兵位存储的值放入该位置。
手动实现如下：

性能分析

数据敏感性：
最好的情况下（有序）：比较n-1次，移动0次
最坏的情况下（逆序）：比较2+3+…+n=(n+2)*(n-1)/2次 ，移动（1+1+1）+（1+1+2）+…+(1+1+n-1)=(n+4)(n-1)/2 （1+1+x)代表一次移入哨兵位一次移出哨兵位，和插入引起的数据移动。
可以看出对数据是敏感的
时间复杂度：O(n^2)
空间复杂度：O©
稳定性：稳定（相邻元素比较）

代码实现

void insertsort(int *p,int n)
{
	int comp=0,move=0,i,j,k;
	int *data=(int *)malloc(sizeof(int)*(1+n));
	memcpy(data,p,sizeof(int)*(1+n));
	for(i=2;i<=n;i++)
	{
		comp++;
		if(data[i]<data[i-1])
		{
			data[0]=data[i];
			move++;
			for(j=i-1;;j--)
			{	
				comp++;
				if(data[j]<=data[0])
				break;
			}
			for(k=i-1;k>=j+1;k--)
			{
				data[k+1]=data[k];
				move++;
			}
			data[j+1]=data[0];
			move++; 
		}
	} 
	printf("insertsort:\n");
	showdata(data,n);
	printf("move: %d\n",move);
	printf("comp: %d\n",comp);
}

改进版本

算法描述

在寻找插入位置时，由于已有序列的有序的，可以使用折半查找。
如果找到了a[mid]==a[0]，那么原有序序列中就存在哨兵位的值，这样第一个小于等于哨兵位的位置就是mid，把哨兵位插在mid前即可。若没有找到与哨兵位相等的a[mid],那么就将哨兵位的值插入到low之前。因此在找到mid时将low等于mid，最后插入到mid前即可。

性能分析

只改变了比较次数，未改变移动次数，时间复杂度仍为O(n^2),空间复杂度为O©,对数据依然敏感，但不再稳定

代码实现

void insertsort_half(int *p,int n)
 {
	int comp=0,move=0,i,k,low,high,mid;
	int *data=(int *)malloc(sizeof(int)*(1+n));
	memcpy(data,p,sizeof(int)*(1+n));
	for(i=2;i<=n;i++)
	{
		comp++;
		if(data[i]<data[i-1])
		{
			data[0]=data[i];
			move++;
			low=1;
			high=i-1;
			while(low<=high)
			{	
				mid=(low+high)/2;
				comp++;
				if(data[0]==data[mid])
				{
					low=mid;
					 break;
				}
				else if(data[0]<data[mid]) high=mid-1;
				else low=mid+1;
			}
			for(k=i-1;k>=low;k--)
			{
				data[k+1]=data[k];
				move++;
			}
			data[low]=data[0];
			move++;
		}
	} 
	printf("insertsort（halfsort_version):\n");
	showdata(data,n);
	printf("move: %d\n",move);
	printf("comp: %d\n",comp);
}

希尔排序

算法描述

当数据大致有序时，直接插入的排序效率较高；当数据量较少时，直接插入的排序效率也很高，基于以上两点，希尔排序做出了改进：先将数据处理成大致有序的情况，再进行直接插入排序。

将序列分为若干（d个)子序列，然后对每个子序列进行插入排序

a[1] a[1+d] a[1+2d] …a[1+kd]

a[2] a[2+d] a[2+2d] …a[2+kd]

…

a[d] a[d+d] a[d+2d] …a[d+kd]

逐渐减小d直至1，做最后一次插入排序

性能分析

时间复杂度：与增量序列的取值有关，一般达到的较好情况为O(n^1.5)

空间复杂度：本地实现O©

稳定性：不稳定（涉及非相邻元素的比较）

数据敏感性：对数据敏感

代码实现

void shellsort(int *p,int n)
{
	int comp=0,move=0,i,t;
	int *data=(int *)malloc(sizeof(int)*(1+n));
	memcpy(data,p,sizeof(int)*(1+n));
	for(i=1;pow(2,i)<=n;i++);
	for(i=i-1;i>=1;i--)
	{
		t=pow(2,i)-1;
		shellinsert(data,n,t,&comp,&move);
	}
	printf("shellsort:\n");
	showdata(data,n);
	printf("move: %d\n",move);
	printf("comp: %d\n",comp);
	
}
void shellinsert(int *p,int n,int t,int *comp,int *move)
{
	int i,j,k;
	for(i=t+1;i<=n;i++)
	{
		(*comp)++;
		if(p[i-t]>p[i])
		{
			p[0]=p[i];
			(*move)++;
			for(k=i-t;k>=1;k=k-t)
			{
				(*comp)++;
				if(p[k]>p[0])
				{
					p[k+t]=p[k];
					(*move)++;
				}
				else break;
			}
			p[k+t]=p[0];
			(*move)++; 
		}
	}
}

交换类排序

通过交换无序序列中的记录从而得到关键字最大或最小的记录，将其加入有序子序列中，由此增加有序子序列的长度

冒泡排序

经典算法

算法思想

不再赘述

性能分析

时间复杂度：O(n^2)
比较次数：1+…+(n-1)=n(n-1)/2
移动次数：最差情况下为3n(n-1)/2
空间复杂度：O©
稳定性：是稳定的（相邻元素比较）
代码

void bubble_classic(int *a,int n)
{
	int *b=(int *)malloc(sizeof(int)*(n+1));
	memcpy(b,a,sizeof(int)*(n+1));
	int i,j,temp,move=0,comp=0;
	for(i=1;i<=n-1;i++)
	{
		for(j=1;j<=n-i;j++)
		{	comp++;
			if(b[j+1]<b[j])
			{	
				temp=b[j];
				b[j]=b[j+1];
				b[j+1]=temp;
				move+=3;
			}
		 } 
		
	} 
	showdata(b,n);
	free(b);
	printf("move: %d\n",move);
	printf("comp: %d\n",comp);
} 

改进版本

算法思想

当元素已经比较有序时，进行几次冒泡即可，在已经有序后不必进行多余的冒泡。因此每轮冒泡后检查是否已经有序，若已经有序则不必再冒泡。为了达到这样的目的，记录最后一次交换的序号lastind，即a[lastind] 与a[lastind+1]交换，根据冒泡排序的特性，每轮冒泡最后一次交换后a[lastind]至a[n]已经有序，若lastind==1，则序列整体就是有序的。

性能分析

最好情况下（原数组有序）：比较次数为 n-1,移动次数为 0
最坏情况下（原数组逆向有序）：比较次数为 n(n-1)/2,移动次数为 3n(n-1)/2
改进了算法的执行效率，但没有改变时间复杂度O(n^2)
空间复杂度 O©
稳定性：是稳定的（相邻元素比较）

代码实现

void bubble_pro(int *a,int n)
{
	int *b=(int *)malloc(sizeof(int)*(n+1));
	memcpy(b,a,sizeof(int)*(n+1));
	int i,j,temp,move=0,comp=0,lastind;
	i=n;
	while(i>1)
	{
		lastind=1;
		for(j=1;j<i;j++)
		{	
			comp++; 
			if(b[j]>b[j+1])
			{
				temp=b[j];
				b[j]=b[j+1];
				b[j+1]=temp;
				lastind=j;
				move+=3;
			}	
		}
		i=lastind;
	 } 
	 showdata(b,n);
	free(b);
	printf("move: %d\n",move);
	printf("comp: %d\n",comp);
} 

与插入算法的比较

冒泡排序每次冒泡过程都能至少确定一个值在序列中的最终位置
但插入排序只有在完全结束后才能确定每个元素的所在位置
因此如果是想查找第k大的元素，冒泡排序可能会快于插入排序

快速排序（快排）

算法思想

采用分而治之的思想，每次将序列的第一个数值作为标志位，将序列排为以下形式：确定标志位对应数值所在位置，左面的元素都比它小，右面的元素都比它大。之后再对左子列和有子列采取相同的操作，递归地进行下去，这样就得到了有序序列。针对上述找位置的过程，选择序列的第一个元素作为标志位，即哨兵位。初始low=1，high=n，a[0]=a[low]，从high开始向前找第一个小于a[0]的元素，将它的值放在a[low],因为a[low]的值已经存在a[0]了，所以没有丢失a[low]的值。在从a【low】开始向后找第一个大于a[0]的值，将它的值赋给a[high],这样a[high]原来小于a[0]的值就被替换成了大于a[0]的值，接下来再从a[high]向前找一个小于a[0]的值。注意到，a【low】左侧的值都小于a【low】，a【high】右侧的值都大于a【high】，且上述的这些值中都不含有a【0】。如此进行下去，直至low==high，再将a[0]的值赋给a[low]，这样a【low】左侧的元素就都小于a【low】，右侧的元素都大于a【low】，起始标志位对应的值在数组中的位置就被确定了，接下来再递归地对左侧和右侧的数组执行同样的操作，最终就得到了有序数组。如果标志位开始选的是a[n]，那么起始搜索时应从low开始向后搜索。
手动实现：

性能分析

对数据较敏感
时间复杂度：
最坏的情况下：即原序列有序，第一次从a[high]向前找将会比较n-1次，之后对除第一个元素外的序列操作，同样这个序列也是有序的，需要比较n-2次，一直这样进行下去，那么将退化为冒泡排序，比较n(n-1)/2次，移动n-1次。平均情况下时间复杂度为O(nlogn)
空间复杂度：
虽然是本地实现的，但递归是需要用到zhai的，存在隐含的空间复杂度。相当于求点的个数一定的二叉树的深度。最好的情况便是完全二叉树，zhai的最大深度为【logn】+1，最坏的情况为原序列有序，zhai的深度为n。
如果每次快排后先对长度较短的子序列坐快排，那么最大深度可降为logn。这样是因为短的区间在排几次之后就会变得有序，不会有很多元素入zhai，对zhai的需求较低，如果先做长的区间的话，首先原来的短区间还在zhai里，其次如果每次都先做长区间，那么就会有短去见一直积累在zhai中等待处理，只有长区间处理完毕才会去处理那些短区间，因此对zhai的需求就特别大。
稳定性：不稳定（涉及到非相邻元素的比较与移动）

代码实现

void quick(int *a,int n)
{
	int *b=(int *)malloc(sizeof(int)*(n+1));
	memcpy(b,a,sizeof(int)*(n+1));
	int move=0,comp=0;
	quicksort(b,1,n,move,comp);
	showdata(b,n);
	printf("move: %d\n",move);
	printf("comp: %d\n",comp);
	free(b);
} 
void quicksort(int *b,int low,int high,int &move,int &comp)
{
	int pos;
	if(low<high)
	{
		pos=pivot(b,low,high,move,comp);
		quicksort(b,low,pos-1,move,comp);
		quicksort(b,pos+1,high,move,comp);
	}
}
int pivot(int *b,int low,int high,int &move,int &comp)
{
	b[0]=b[low];
	move++;
	while(low<high)
	{
		while(low<high && b[high]>=b[0])
		{	
			comp++;
			high--;
		}
		b[low]=b[high];
		while(low<high && b[low]<=b[0])
		{	
			comp++;
			low++;
		}
		b[high]=b[low];
		move++;
	}
	b[low]=b[0];
	move++;
	return low;
}

选择排序

从记录的无序子序列中选择关键字最大或最小的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列长度。

经典算法

算法描述

不再赘述

性能分析

时间复杂度：O(n^2)
比较次数：n-1+n-2+…+1=n(n-1)/2
移动次数：min(有序):0 -> max(例如51234）: 3(n-1)
空间复杂度：O(1)
稳定性：不稳定（涉及非相邻元素的比较和移动）
对数据不敏感

堆排序

算法描述

堆（二叉树，优先队列) {r1,r2,r3…rn}
其中 ri<=r2i ri<=r2i+1 (小顶堆）ri>=r2i ri>=r2i+1(大顶堆）
给一个数列要会判断是否为堆（当作先序遍历结果写成完全二叉树的形式）
算法思想：比如我们已经有了一个大顶堆，那么排序的话只需要先输出对应二叉树的根节点（最大值），再将剩余的节点调整成一个大顶堆，再输出根节点（次最大值），再调整，如此进行下去直至树空为止，则得到了一个有序序列
那么问题就在于如何（1）建立一个堆和（2）去掉堆的根节点后如何调整。
先看问题2
删除根节点：将堆尾节点的值与根节点的值互换，断开尾节点与树的连接（将根节点的值从树中去除），然后由根节点开始进行自上而下的”筛选“，拿建立大顶堆举例，在根节点的两个子节点中选择较大的一个与根节点的值互换，这样被互换的那个子节点作为根节点的子树就不是大顶堆了，再对这颗子树的根节点进行相同操作，直至到达叶子节点，调整结束，手动实现如下：

再看问题1：
对于一个随机序列{r1,r2,r3…rn}，从a[m]（m=[n/2]，这样选是为了排除所有的叶子节点，因为叶子节点不必进行调整，调整的对象是所有的根节点）开始向前直至a[0]（从下至上是因为符合问题2中前提，要求对一个根节点进行调整时，左右子树都是堆），对每一个节点进行筛选即可得到相应的堆。手动实现如下：
建立小顶堆

性能分析

时间复杂度：
运行时间主要集中在构建初始堆和删除根节点后的筛选上了。每进行一次筛选的时间复杂度为O(logn)(因为完全二叉树的最大深度为[logn]+1)，因此所有的筛选和建堆操作的时间复杂度为O(nlogn)
空间复杂度：O©
稳定性：不稳定
对数据不敏感

代码实现

void heapsort(int *a,int n)
{
	int i,j,*b=(int *)malloc(sizeof(int)*(n+1));
	int move=0,comp=0;
	memcpy(b,a,sizeof(int)*(n+1)); 
	for(i=n/2;i>=1;i--)
		heapadjust(b,n,i,&move,&comp);
	for(int i=1;i<n;i++)
	{
		b[0]=b[1];
		b[1]=b[n+1-i];
		b[n+1-i]=b[0];
		heapadjust(b,n-i,1,&move,&comp);
	}
	showdata(b,n);
	free(b);
	printf("move: %d\n",move);
	printf("comp: %d\n",comp);
} 
void heapadjust(int *a,int n,int index,int *move,int *comp)
{
	int i=index,j=2*index;
	a[0]=a[i];
	(*move)++;
	while(j<=n)
	{
		if((j+1)<=n && a[j+1]>a[j])
		{
			j++;
			(*comp)++;
		}
		(*comp)++;
		if(a[j]>a[0])
		{
			a[i]=a[j];
			(*move)++;
			a[j]=a[0];
			(*move)++;
			i=j;
			j=2*i;
		}
		else
		break;
	}
}

归并排序（异地）

算法描述

将两个有序序列归并为一个有序序列，手动实现如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fnqgSZK1-1590853395395)(C:\Users\l\Desktop\7592CB675C383875EB16191D76081D5C.jpg)]

性能分析

时间复杂度：进行归并的趟数为[logn]+1,由于每次归并都是异地的，因此每次的移动次数都是n，时间复杂度为O(nlogn).

空间复杂度：O(n) (非递归) 递归的话至少O(n)

稳定性：稳定

数据敏感性：最好（有序）最坏（逆序）情况下的移动次数都是相等的，比较次数在最好的情况下可能会少一点

代码实现

void Mergesort(int *a,int n)
{
	int *b=(int *)malloc(sizeof(int)*(n+1));//原数组 
	int *c=(int *)malloc(sizeof(int)*(n+1));//辅助数组 
	memcpy(b,a,sizeof(int)*(n+1));
	int i,j,k,low,top,mid,len=1,move=0,comp=0;
	while(len<n)
	{
		for(j=1;j<=(n-2*len+1);j+=2*len)
			Merge(b,c,j,j+len-1,j+2*len-1,&move,&comp);
		if((n+1-j)>len)
			Merge(b,c,j,j+len-1,n,&move,&comp);
		else
			for(k=j;k<=n;k++) 
				c[k]=b[k];
		//辅助数组每趟归并后要复制到原数组 
		memcpy(b,c,sizeof(int)*(n+1));
		len*=2;
	}
	showdata(b,n);
	printf("move: %d\n",move);
	printf("comp: %d\n",comp);
	free(b);
	free(c);
} 
void Merge(int *b,int *c,int low,int mid,int high,int *move,int *comp)
{
	int i=low,j=mid+1,k=low;
	while(i<=mid && j<=high)
	{	
		(*comp)++;
		if(b[i]<=b[j])
			c[k++]=b[i++];
		else 
			c[k++]=b[j++];
		(*move)++;
	}
	while(i<=mid)
	{
		c[k++]=b[i++];
		(*move)++;
	 } 
	while(j<=high)
	{
		c[k++]=b[j++];
		(*move)++;
	 } 
}

基类排序（桶排序）

算法思想

序列：{R1,R2,R3…Rn-1,Rn}

序列中每个元素的属性：(K1,K2,…Kd)

K1称为最主位关键字，K2称为次主位关键字…

排序方法：

1.最高位优先（MSD)：先按关键字Ki排列成不同的子列，在对每一个子列按关键字Ki+1排序，i=1~d-1

​ 必须逐层分为若干子列

2.最低位优先（LSD):先对最次位关键字Kd进行排序，再对Kd-1进行排序，一直进行下去最终得到有序序列

​ 不必逐层分为若干子列，对每个关键字都是整个序列进行排序

​ 将单关键字分割成多关键字，并对多关键字进行分配和收集来实现对单关键字的排序

但是事先要知道每个关键字的范围以确定桶的数目，将关键字相同的记录放入同一个桶中

因此LSD的缺点也很明显：

1.排序记录只限于整数和字符串

2.范围可能未知，或者范围特别大，实际记录数量却特别少，空间牺牲太大

解决这种空间牺牲大的问题，可以分割属性，例如将一个两位数范围10，分解为1和0

举例：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-N6M6Lp2D-1590853395396)(C:\Users\l\AppData\Roaming\Typora\typora-user-images\image-20200529175747778.png)]

LSD正确性的理解：在对高位进行排序，高位相同时，低位是稳定的，这样看来，在按百位排序完成后，百位大的一定大，百位相同的其十位的大小关系也是递增且稳定的，十位大的一定大，十位相同的其个位的大小关系也是递增且稳定的。因此整个序列就是递增且稳定的。

性能分析

时间复杂度：每次分配为O(n),每次收集为O(n)，共分配&收集d次，故时间复杂度为O(nd)

空间复杂度：O©(在d一定的情况下)

稳定性：稳定

对数据的敏感性：不敏感

总结

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d3G9jYjC-1590853395396)(C:\Users\l\AppData\Roaming\Typora\typora-user-images\image-20200529193320145.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RX8wT69q-1590853395397)(C:\Users\l\AppData\Roaming\Typora\typora-user-images\image-20200529193338198.png)]

BY ZKF