数据结构（陈越，何钦铭） 第七讲 图（中）

7.1 Tree Traversals Again

#include <stdio.h>
#include <string.h> 
#include <stdlib.h>
#define MAXN 30


int post[MAXN];
int pre[MAXN];
int in[MAXN];

void solve(int preL,int inL,int postL,int n){
	if(n==0){
		return;
	}
	if(n==1){
		post[postL]=pre[preL];
		return;
	}
	int root,i;
	root=pre[preL];
	post[postL+n-1]=root;
	for(i=0;i<n;i++){
		if(pre[preL]==in[inL+i]){
			break;
		}
	}
	solve(preL+1,inL,postL,i);
	solve(preL+1+i, inL+i+1,postL+i,n-i-1);
}

typedef struct{
	int data[MAXN];
	int top;
}Stack;

void InitStack(Stack *stack){
	stack->top=-1;
}

void PushStack(Stack *stack,int value){
	if(stack->top==MAXN-1){
		printf("栈已满，无法入栈\n");
		return;
	}
	stack->data[++stack->top]=value;
}

int PopStack(Stack *stack){
	if(stack->top==-1){
		printf("栈已空，无法出栈");
		return -1;
	}
	return stack->data[stack->top--];
}

int main(){
	int N,i;
	int preidx=0;
	int inidx=0;
	char A[5];
	scanf("%d",&N);
	Stack *stack=(Stack*)malloc(sizeof(Stack));
	InitStack(stack);
	for(i=0;i<2*N;i++){
		scanf("%s",A);
		if(strcmp(A,"Push")==0){
			scanf("%d",&pre[preidx]);
			PushStack(stack,pre[preidx]);
			preidx++;
		}else{
			in[inidx]=PopStack(stack);
			inidx++;
		}
	}
	solve(0,0,0,N);
	printf("%d",post[0]);
	for(i=1;i<N;i++){
		printf(" %d",post[i]);
	}
	return 0;
} 

7.2 Complete Binary Search Tree

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXN 1000

int a[MAXN];
int T[MAXN];
int N;

int compare(const void*a,const void*b){
	return *(int*)a-*(int*)b;
}

int min(int a,int b){
	if(a<=b){
		return a;
	}
	return b;
}

int Getleftlength(int n){
	int H,x;
	H=(int)floor(log(n+1)/log(2));
	x=n+1-pow(2,H);
	x=min(x,pow(2,H-1));
	return pow(2,H-1)-1+x;
}

void solve(int aleft,int aright,int Troot){
	int n,L,leftroot,rightroot;
	n=aright-aleft+1;
	if(n==0){
		return;
	} 
	L=Getleftlength(n);
	T[Troot]=a[aleft+L];
	leftroot=2*Troot+1;
	rightroot=leftroot+1;
	solve(aleft,aleft+L-1,leftroot);
	solve(aleft+L+1,aright,rightroot);
}

int main(){
	int i;
	scanf("%d",&N);
	for(i=0;i<N;i++){
		scanf("%d",&a[i]);
	}
	qsort(a,N,sizeof(int),compare);
	solve(0,N-1,0);
	printf("%d",T[0]);
	for(i=1;i<N;i++){
		printf(" %d",T[i]);
	}
	return 0;
} 

7.3 Huffman Codes

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h> 
#define MAXNUM 64
#define MINDATA -1

typedef struct TreeNode *HuffmanTree;
struct TreeNode{
	int Weight;
	HuffmanTree Left,Right;
};


typedef struct HNode *Heap;
struct HNode{
	HuffmanTree *Data;
	int Size;
	int Capacity;
};
typedef Heap MinHeap;


MinHeap CreateHeap(int MaxSize){
	MinHeap H=(MinHeap)malloc(sizeof(struct HNode));
	H->Data=(HuffmanTree *)malloc((MaxSize+1)*sizeof(HuffmanTree));
	H->Size=0;
	H->Capacity=MaxSize;
	H->Data[0]=(HuffmanTree)malloc(sizeof(struct TreeNode)); 
	H->Data[0]->Weight=MINDATA;
	H->Data[0]->Left=NULL;
	H->Data[0]->Right=NULL;
	return H;
}

bool IsFull(MinHeap H){
	return (H->Size==H->Capacity);
}

bool IsEmpty(MinHeap H){
	return (H->Size==0);
}

void Insert(MinHeap H,HuffmanTree X){
	int i;
	if(IsFull(H)){
		printf("最小堆已满");
	}
	i=++H->Size;
	for(;H->Data[i/2]->Weight>X->Weight;i/=2){
		H->Data[i]=H->Data[i/2];
	}
	H->Data[i]=X;
}

HuffmanTree DeleteMin(MinHeap H){
	int Parent,Child;
	HuffmanTree MinItem,X;
	if(IsEmpty(H)){
		printf("最小堆已空");
		return NULL;
	}
	MinItem=H->Data[1];
	X=H->Data[H->Size--];
	for(Parent=1;Parent*2<=H->Size;Parent=Child){
		Child=Parent*2;
		if((Child!=H->Size)&&(H->Data[Child]->Weight>H->Data[Child+1]->Weight)){
			Child++;
		}
		if(X->Weight<=H->Data[Child]->Weight){
			break;
		}else{
		H->Data[Parent]=H->Data[Child]; 
		}
	} 
	H->Data[Parent]=X;
	return MinItem;
}

void PercDown(MinHeap H,int p){
	int Parent,Child;
	HuffmanTree X;
	X=H->Data[p];
	for(Parent=p;Parent*2<=H->Size;Parent=Child){
		Child=Parent*2;
		if((Child!=H->Size)&&(H->Data[Child]->Weight>H->Data[Child+1]->Weight)){
			Child++;
		}
		if(X->Weight<=H->Data[Child]->Weight){
			break;
		}else{
			H->Data[Parent]=H->Data[Child];	
		}
	}
	H->Data[Parent]=X;
}

void BuildMinHeap(MinHeap H){
	int i;
	for(i=H->Size/2;i>0;i--){
		PercDown(H,i); 
	}
}
 

HuffmanTree Huffman(MinHeap H,int N){
	int i;
	HuffmanTree T;
	BuildMinHeap(H);
	for(i=0;i<N-1;i++){
		T=(HuffmanTree)malloc(sizeof(struct TreeNode));
		T->Left=DeleteMin(H);
		T->Right=DeleteMin(H);
		T->Weight=T->Left->Weight+T->Right->Weight;
		Insert(H,T); 
	} 
	T=DeleteMin(H);
	return T;
}



int WPL(HuffmanTree T,int Depth){
	if(!T->Left&&!T->Right){
		return (Depth*T->Weight);
	}
	return (WPL(T->Left,Depth+1)+WPL(T->Right,Depth+1));
} 

typedef struct TrieNode{
	struct TrieNode *right;
	struct TrieNode *left;
	int isEnd; 
}TrieNode; 

TrieNode* CreateTrieNode(){
	TrieNode* newnode=(TrieNode*)malloc(sizeof(TrieNode));
	newnode->isEnd=0;
	newnode->left=newnode->right=NULL;
	return newnode; 
}

bool InsertTrie(TrieNode* root,char *code){
	TrieNode* current=root;
	int len=strlen(code);
	int i;
	for(i=0;i<len;i++){
		if(current->isEnd){
			return false;
		}
		if(code[i]=='0'){
			if(!current->left){
				current->left=CreateTrieNode();
			}
			current=current->left;
		}else{
			if(!current->right){
				current->right=CreateTrieNode();
			}
			current=current->right;
		}
	}
	if(current->isEnd||current->left||current->right){
		return false;
	}
	current->isEnd=1;
	return true;
} 

void freeTrie(TrieNode* root){
	if(!root){
		return;
	}
	freeTrie(root->left);
	freeTrie(root->right);
	free(root);
}

int judge(char num[][MAXNUM],int N){
	TrieNode *root=CreateTrieNode();
	int i;
	for(i=0;i<N;i++){
		if(!InsertTrie(root,num[i])){
			freeTrie(root);
			return 0;
		}
	}
	freeTrie(root);
	return 1;
}



int main(){
	int N,i,M,huffmannum,j;
	char names[MAXNUM];
	int weights[MAXNUM];
	scanf("%d",&N);
	for(i=0;i<N;i++){
		scanf(" %c %d",&names[i],&weights[i]);
	} 
	MinHeap H=CreateHeap(N);
	HuffmanTree T;
	for(i=1;i<=N;i++){
		HuffmanTree node=(HuffmanTree)malloc(sizeof(struct TreeNode));
		node->Weight=weights[i-1];
		node->Left=node->Right=NULL;
		H->Data[i]=node;
		H->Size++; 
	}
	T=Huffman(H,N); 
	huffmannum=WPL(T,0);
	scanf("%d",&M); 
	char tmp; 
	int len; 
	char num[MAXNUM][MAXNUM]; 
	for(i=0;i<M;i++){
		len=0;
		for(j=0;j<N;j++){
			scanf(" %c %s",&tmp,&num[j]);
			len+=strlen(num[j])*weights[j]; 
		} 
		if(len==huffmannum){
			if(judge(num,N)){
				printf("Yes\n");
			}else{
				printf("No\n"); 
			}
		}else{
			printf("No\n");
		} 
	} 
	return 0; 
}

7.4 最短路径问题

7.4.1 概述

7.4.2 无权图的单源最短路

void Unweighted(LGraph Graph,int dist[],int path[],Vertex S){
	Queue Q;
	Vertex V;
	PtrToAdjVNode W;
	Q=CreateQueue(Graph->Nv);
	dist[S]=0;
	AddQ(Q,S);
	while(!IsEmpty(Q)){
		V=DeleteQ(Q);
		for(W=Graph->G[V].FirstEdge;W;W=W->Next){
			if(dist[W->AdjV]==-1){
				dist[W->AdjV]=dist[V]+1;
				path[W->AdjV]=V;
				AddQ(Q,W->AdjV);
			}
		}
	}
}

7.4.3 无权图的单源最短路径示例

7.4.4 有权图的单源最短路

Vertex FindMinDist(MGrph Graph,int dist[],int collected[]){
	Vertex MinV,V;
	int MinDist=INFINITY;
	for(V=0;V<Graph->Nv;V++){
		if(collected[V]=false&&dist[V]<MinDist){
			MinDist=dist[V];
			Min=V;
		}
	}
	if(MinDist<INFINTY){
		return MinV;
	}else{
		return ERROR;
	}
} 

bool Dijkstra(MGraph Graph,int dist[],int path[],Vertex S){
	int collected[MaxVertexNum];
	Vertex V,W;
	for(V=0;V<Graph->Nv;V++){
		dist[V]=Graph->G[S][V];
		if(dist[V]<INFINITY){
			path[V]=S;
		}else{
			path[V]=-1;
		}
		collected[V]=false;
	} 
	dist[S]=0;
	collected[S]=true;
	while(1){
		V=FindMinDist(Graph,dist,collected);
		if(V=ERROR){
			break;
		}
		collected[V]=true;
		for(W=0;W<Graph->Nv;W++){
			if(collected[W]==false&&Graph->G[V][W]<INFINITY){
				if(Graph->G[V][W]<0){
					return false;
				} 
				if(dist[V]+Graph->G[V][W]<dist[W]){
					dist[W]=dist[V]+Graph->G[V][W];
					path[W]=V;
				} 
			}
		}
	}
	return true;
}

7.4.5 有权图的单源最短路示例

7.4.7 多源最短路算法

bool Floyd(MGraph Graph,WeightType D[][MaxVertexNum],Vertex path[][MaxVertexNum]){
	Vertex i,j,k;
	for(i=0;i<Graph->Nv;i++){
		for(j=0;j<Graph->Nv;j++){
			D[i][j]=Graph->G[i][j];
			path[i][j]=-1;
		}
	}
	for(k=0;k<Graph->Nv;k++){
		for(i=0;i<Graph->Nv;i++){
			for(j=0;j<Graph->Nv;j++){
				if(D[i][k]+D[k][j]<D[i][j]){
					D[i][j]=D[i][k]+D[k][j];
					if(i==j&&D[i][j]<0){
						return false;
					}
					path[i][j]=k;
				}
			}
		}
	}
	return true;
}

7.5 哈利·波特的考试

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MaxVertexNum 100
#define INFINITY 65535 

typedef int WeightType; 
typedef int Vertex; 

typedef struct ENode *PtrToENode;
struct ENode{
	Vertex v1,v2;
	WeightType Weight;
}; 
typedef PtrToENode Edge;

typedef struct GNode *PtrToGNode;
struct GNode{
	int Nv;
	int Ne;
	WeightType D[MaxVertexNum][MaxVertexNum]; 
};
typedef PtrToGNode MGraph;

MGraph CreateGraph(int VertexNum){
	MGraph graph=(MGraph)malloc(sizeof(struct GNode));
	graph->Ne=0;
	graph->Nv=VertexNum;
	Vertex v,w;
	for(v=0;v<graph->Nv;v++){
		for(w=0;w<graph->Nv;w++){
			graph->D[v][w]=INFINITY;
		}
	}
	return graph; 
}

void InsertGraph(MGraph graph,Edge E){
	graph->D[E->v1][E->v2]=E->Weight;
	graph->D[E->v2][E->v1]=E->Weight;
}

MGraph BuildGraph(){
	MGraph graph;
	int n,i;
	scanf("%d",&n);
	graph=CreateGraph(n);
	scanf("%d",&graph->Ne); 
	if(graph->Ne!=0){
		Edge E=(Edge)malloc(sizeof(struct ENode));
		for(i=0;i<graph->Ne;i++){
			scanf(" %d %d %d",&E->v1,&E->v2,&E->Weight);
			E->v1--;
			E->v2--; 
			InsertGraph(graph,E); 
		} 
	}
	return graph; 
}


WeightType FindMaxDist(WeightType G[][MaxVertexNum],Vertex i,int N){
	WeightType MaxDist;
	Vertex j;
	MaxDist=0;
	for(j=0;j<N;j++){
		if(G[i][j]>MaxDist&&i!=j){
			MaxDist=G[i][j];
		}
	}
	return MaxDist;
}

bool Floyd(MGraph graph,WeightType G[][MaxVertexNum]){
	Vertex i,j,k;
	for(i=0;i<graph->Nv;i++){
		for(j=0;j<graph->Nv;j++){
			G[i][j]=graph->D[i][j];
		}
	}
	for(k=0;k<graph->Nv;k++){
		for(i=0;i<graph->Nv;i++){
			for(j=0;j<graph->Nv;j++){
				if(G[i][k]+G[k][j]<G[i][j]){
					G[i][j]=G[i][k]+G[k][j];
					if(i==j&&G[i][j]<0){
						return false;
					}
				}
			}
		}
	}
	return true;
}

void FindAnimal(MGraph graph){
	WeightType G[MaxVertexNum][MaxVertexNum];
	WeightType MaxDist,MinDist;
	Vertex Animal,i;
	Floyd(graph,G);
	MinDist=INFINITY;
	for(i=0;i<graph->Nv;i++){
		MaxDist=FindMaxDist(G,i,graph->Nv);
		if(MaxDist==INFINITY){
			printf("0\n");
			return;
		}
		if(MaxDist<MinDist){
			MinDist=MaxDist;
			Animal=i+1;
		}
	}
	printf("%d %d\n",Animal,MinDist);
}

int main(){
	MGraph G=BuildGraph();
	FindAnimal(G);
	return 0; 
}