图的演示.cpp

这是一个小小的程序

#include<stdio.h>
#include<stdlib.h>
#define MAX  20
#include <malloc.h>
#include "string.h"
#define M 30
#define INFINITE 100

#define MAX_WEIGHT 1000
int visited[MAX];
#define MAXNode 1024 
#include<iostream.h>
#define MAXSIZE 1024
int w;

typedef int   DataType; 
typedef int VexType;
typedef struct BiNode{
	DataType data;
	 struct BiNode *lchild;
     struct BiNode *rchild;
}BiNode,*BiTree;

typedef struct HaffmanTreeNode { 
 char ch; 
 int weight; 
 int parent, lchild, rchild; 
} HTNode, *HaTree; 

typedef struct { 
 HTNode arr[MAXNode]; 
 int total; 
} HTree; 

typedef struct arcnode
{
 int adjvex;//该弧指向的顶点的位置
 struct arcnode *next;//弧尾相同的下一条弧
}arcnode;

typedef struct vexnode
{
 VexType data;//结点信息
 arcnode *firstarc;//指想第一条依附该结点的弧的指针
}vexnode;
typedef struct
{
 vexnode g[MAX];
 int vexnum,arcnum;
}Graph;

typedef struct
{
 int vexnum,arcnum;
 int arcs[MAXNode][MAXNode];
}MGraph;//用邻接矩阵存储


typedef struct Qnode
{
int data;
 struct Qnode *next;
}QNode,*Qptr;

typedef struct
{
 Qptr front;
 Qptr rear;
}Queue;

typedef struct{
	BiTree data[MAXSIZE];
	int top;
}stack;


void InitStack(stack &S){
//初始化栈
  S.top=0;
}//SqstackInit()


void Push(stack &S,BiTree p){
// 把元素x压入栈，使其成为新的栈顶元素 
	if(S.top> MAXSIZE )
		printf("栈已满!");
	S.data[S.top++]=p;  
}//SqstackPush


int StackEmpty(stack S){
	//判断栈是否为空,若是空返回1;
	if(S.top==0)
	return 1;
	return 0;
}//SqstackEmpty


BiTree GetTop(stack S)
{	
	if(S.top)
		return S.data[S.top-1];
	else 
		return NULL;
}
		

BiTree Pop(stack &S)
 {		//把栈顶元素弹出
	if(S.top!=0)
		return S.data[--S.top];
	else 
		return  NULL;
}//SqstackPop


 void CreatBitree(BiTree &T){
	//按先序输入结点，建立链表表示的二叉树T
	//输入0时结束
	DataType ch;
	printf("输入结点值：");
	scanf("%d",&ch);
	if(ch){
		T=(BiTree)malloc(sizeof(BiNode));
		T->data=ch;
	CreatBitree(T->lchild);
	CreatBitree(T->rchild);
	}//while	
	else T=NULL;
}//CreatBiTree




void PreOrderTraverse(BiTree T)
{//利用二叉树的链表结构实现二叉树的非递归先序遍历

	stack s; BiTree p;
	InitStack(s);
	p=T;
	while(p||!StackEmpty(s))
	{
		while(p)
		{
		printf("%d--",p->data);
		Push(s,p);
		p=p->lchild;
		}
	p=Pop(s);
	p=p->rchild;
	}
		printf("结束!\n");

}//PreOrderTraverse

void InOrderTraverse(BiTree T)
{                                          //中序遍历二叉树的非递归算法
	stack s;
	InitStack(s);                              //初始化辅助栈
    BiTree p=T;
	while(p||!StackEmpty(s))
	{                                      //p指向为空并且辅助栈为空的时候循环停止
		if(p)
		{                                  //p指向不是空时
		Push(s,p);                     //p进栈
            p=p->lchild;                   //p指向左子树
		}//if
		else
		{                                  //p指向为空的时候
		p=Pop(s);                      //出栈
			printf("%d--",p->data);           //输出p
			p=p->rchild;                   //p指向栈顶元素的右子树
		}//else
	}//while
		printf("结束!\n");
}


	
void PostOrderTraverse(BiTree T)
{//利用二叉树的链表结构实现二叉树的非递归后序遍历
            		
	stack s; BiTree p=T,pre=NULL;
	InitStack(s);
	while(p||!StackEmpty(s))
	 {
		while(p)
		{
			Push(s,p);
			p=p->lchild;
		}
		p=GetTop(s);
		if(p->rchild==NULL||p->rchild==pre)
		{
			printf("%d--",p->data);
			pre=Pop(s);		//pre指向刚刚访问的结点
			p=NULL;
		}
		else
			p=p->rchild;
	 }//while
	printf("结束!\n");
}//PostOrderTraverse




// 统计字符出现的频率 
void statistic_char(char *text, HTree *t)
{ 
	int i, j; 
	int text_len = strlen(text); 
	t->total = 0; 
	for (i=0; i<text_len; i++)
	{ //对每个元素
		for (j=0; j<t->total; j++) 
			if (t->arr[j].ch == text[i])
			{ 
				t->arr[j].weight ++; 
				break;
			} 
			
			
			if (j==t->total) 
			{ 
				t->arr[t->total].ch = text[i]; 
				t->arr[t->total].weight = 1; 
				t->total++; 
			} 
	} 
	
} //statistic_char



void Create_htree(HTree *t) 
{ 
	int i; 
	int total_node = t->total * 2 - 1; 
	int min1, min2; // 权最小的两个结点  
	int min1_i, min2_i; // 权最小结点对应的编号  
	for (i=0; i<t->total; i++)
	{ 
		t->arr[i].parent = -1; 
		t->arr[i].rchild = -1; 
		t->arr[i].lchild = -1; 
	} //for
	
	while (t->total < total_node) 
	{ 
		min1 = min2 = MAX_WEIGHT; 
		for (i=0; i<t->total; i++) 
		{ // 对每一个结点  
			if (t->arr[i].parent == -1 // 结点没有被合并  
				&& t->arr[i].weight < min2)
			{ // 结点的权比最小权小  
				if (t->arr[i].weight < min1) 
				{ // 如果它比最小的结点还小  
					min2_i = min1_i; min2 = min1; 
					min1_i = i; min1 = t->arr[i].weight; 
				} 
				else 
				{ 
					min2_i = i; min2 = t->arr[i].weight; 
				} 
			} 
		}//for
		
		t->arr[t->total].weight = min1 + min2; 
		t->arr[t->total].parent = -1; 
		t->arr[t->total].lchild = min1_i; 
		t->arr[t->total].rchild = min2_i; 
		t->arr[min1_i].parent = t->total; 
		t->arr[min2_i].parent = t->total; 
		t->arr[t->total].ch = ' '; 
		t->total ++; 
	} //while
} //Create_htree


// 对哈夫曼树进行编码 
void Coding(HTree *t, int head_i, char *code) 
{ 
	if (t->arr[head_i].lchild == -1 && t->arr[head_i].rchild == -1)
		printf("%c,%s\n",t->arr[head_i].ch,code); 
	
	else
	{ 
		int len = strlen(code); 
		strcat(code, "0"); 
		Coding(t, t->arr[head_i].lchild, code); 
		code[len] = '1'; 
		Coding(t, t->arr[head_i].rchild, code); 
		code[len] = '\0'; 
	} 
} 



void haffman(HTree &t) 
{ 
	char text[100]; 
	char code[100] = " "; 
	printf("请输入需要编码的字符串：\n"); 
	cin>>text; 
	statistic_char(text, &t); 
	Create_htree(&t); 
	printf("编码对应关系：\n"); 
	Coding(&t, t.total-1, code); 
	
}  






int LocateVex(Graph G,VexType v){
	int i=0;
	while(i<G.vexnum&&G.g[i].data!=v)
		i++;
	return i;
	}

void CreateAdjList(Graph &G)
{   
	int i,m,n;
	VexType v1,v2; 
	arcnode *p,*q;
	printf("输入图中结点个数v（0<v<100）：\n");
	scanf("%d",&G.vexnum);
	printf("输入图中弧个数arc(0<arc<100)：\n");
	scanf("%d",&G.arcnum);
	
	for(i=0;i<G.vexnum;)
	{
		printf("请输入第%d个结点值：\n",i+1);
		scanf("%d",&G.g[i].data);
		G.g[i++].firstarc=NULL;
	}
	
	for(i=0;i<G.arcnum;i++)
	{//对每一条边
		printf("请输入第%d条边的两个结点值：\n",i+1);
		scanf("%d %d",&v1,&v2);
		m=LocateVex(G,v1);
		n=LocateVex(G,v2);
		p=(arcnode *)malloc(sizeof(arcnode));
		p->adjvex=n;
		p->next=G.g[m].firstarc;
		G.g[m].firstarc=p;
		q=(arcnode *)malloc(sizeof(arcnode));
		q->adjvex=m;
		q->next=G.g[n].firstarc;
		G.g[n].firstarc=q;
	}//for
	for(i=0;i<G.vexnum;i++)
	{ 
		printf("\n位置为%d的结点值为：v%d\n",i,G.g[i].data);
		p=G.g[i].firstarc; 
		if(p)
			printf("该点邻接点的位置：");
		while(p){
			printf("%d\t",p->adjvex);
			p=p->next;
		}
	}//for
}//CreateAdjList


int FirstAdjvex(Graph G,VexType v)
//返回依附顶点V的第一个点
//即以V为尾的第一个结点
{ 
	int m;  
	arcnode *p;
	m=LocateVex(G,v);
	p=G.g[m].firstarc;
	if(p)
		return p->adjvex;
	else
		return MAX;
}

int NextAdjvex(Graph G,VexType v,int w)//返回依附顶点V的相对于W的下一个顶点
{
	arcnode *p;
	int m;     
	m=LocateVex(G,v);
	p=G.g[m].firstarc;
	while(p)
	{
		if(p->adjvex!=w)
			p=p->next;
		if(p->adjvex==w&&p->next!=NULL)
			return p->next->adjvex;
		else return MAX;
	}
	return MAX;
}


void InitQueue(Queue &Q)//初始化队列
{
	Q.rear=(Qptr)malloc(sizeof(QNode));
	Q.front=Q.rear;
	if(!Q.front)
		printf("分配失败！！！");
	Q.front->next=NULL;
}

void EnQueue(Queue &Q,int e)//入队
{
	
	Qptr p;
	p=(Qptr)malloc(sizeof(QNode));
	if(!p)
		printf("分配失败！！！");
	
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
}


void DeQueue(Queue &Q,int &e)//出队
{
	Qptr p;
	if(Q.front==Q.rear)
		printf("栈空！！");
	
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
		Q.rear=Q.front;
	free(p);
}



int QueueEmpty(Queue Q)//判断队为空
{
	if(Q.front==Q.rear)
		return 1;
	else return 0;
}


void BFSTra(Graph G)//广度优先遍历
{
	int i,e;
	Queue Q;
	InitQueue(Q);
	for(i=0;i<G.vexnum;i++)
		visited[i]=0;
	
	for(i=0;i<G.vexnum;i++)//对每一个结点
		if(!visited[i])
		{
			visited[i]=1;
			printf("\n%d\t",G.g[i].data);
			EnQueue(Q,i);
			while(!QueueEmpty(Q))
			{
				DeQueue(Q,e);
				for(w=FirstAdjvex(G,G.g[e].data);w>=0,w<MAX;w=NextAdjvex(G,G.g[e].data,w))
					if(!visited[w])
					{
						visited[w]=1;
						printf("%d\t",G.g[w].data);
						EnQueue(Q,w);
					}
			}
		}
}

void DFS(Graph G,int i)
{
	visited[i]=1;
	printf("%d\t",G.g[i].data);
	for(w=FirstAdjvex(G,G.g[i].data);w>=0,w<MAX;w=NextAdjvex(G,G.g[i].data,w))
		if(!visited[w])
			DFS(G,w);
		
}

void DFSTra(Graph G)//深度优先遍历
{
	int i;
	for(i=0;i<G.vexnum;i++)
		visited[i]=0;
	for(i=0;i<G.vexnum;i++)
		if(!visited[i])
			DFS(G,i); 
}


void CreateMGraph(MGraph *p)
{
  int i,j,n,m;
  int v1,v2,w;
  printf("请输入顶点个数:");