tuopupaixu.cpp

这是数据结构基础算发知识的VC实现 如二叉树遍历、拓扑排序、哈夫曼树等

#include<stdlib.h>
#include<conio.h>
#include <string.h>
#include<iostream>
#include<queue>
#include<stack>
#define MAX_NUM 100
#define MAXM    1000
#define SIZE 100
typedef char Vertype;
typedef struct acnode
{
    int adjvex;
    acnode *nextarc;
}acnode;
typedef struct bxnode
{
    Vertype vex;
    acnode *firstarc;
}bxnode,AdjList[MAX_NUM];
typedef struct 
{
    int vexnum,arcnum;
    AdjList verices;
}ALGraph;
typedef struct degree
{
    int adjvex;
    int deg;
}Degree[MAX_NUM];
int LocateVex(ALGraph G,Vertype v);
void finddegree(ALGraph G,Degree de);
void CreatDN(ALGraph &G)
{
    int i,j,k,vexnum,arcnum;
	char tp,Y,N;
    Vertype v1,v2;
    acnode *p;
    printf("请输入 vexnum 和arcnums :");
    scanf("%d%d",&vexnum,&arcnum);
	vexnum=vexnum*2;
    G.vexnum=vexnum;G.arcnum=arcnum;
    fflush(stdin);
	printf("请输入各个结点：\n");
    for(i=0;i<vexnum;i++){
        G.verices[i].vex=getchar();
        G.verices[i].firstarc=NULL;
    }
    fflush(stdin);
    for(i=0;i<vexnum;i++){
        printf("%c\n",G.verices[i].vex);
    }

    for(i=0;i<arcnum;i++){
        printf("\n请输入第%d个有向关系的两个顶点元素:",i+1);
        v1=getche();printf("----->");
        v2=getche();
        j=LocateVex(G,v1);
        k=LocateVex(G,v2);
        if(j==-1||k==-1)
		{
            printf("the v1 or v2 is not in the vertexs!!");	
			printf("你是否要重新输入数据，重新输入按Y，否则按N。");	
			if(tp==Y)
			{
		        printf("\n请输入第%d个有向关系的两个顶点元素:",i+1);
                v1=getche();printf("----->");
                v2=getche();
                j=LocateVex(G,v1);
                k=LocateVex(G,v2);
               if(j==-1||k==-1)
			   {
                printf("the v1 or v2 is not in the vertexs!!");
		    	printf("你是否要重新输入数据，重新输入按Y，否则按N。");
			   }
			   else if(tp==N)
			   {
			     exit(0);
			   }
			}
		}
        p=(acnode *)malloc(sizeof(acnode));
        p->adjvex=k;p->nextarc=G.verices[j].firstarc;
        G.verices[j].firstarc=p;
    }
}
int LocateVex(ALGraph G,Vertype v)
{
    
    int i;
    for(i=0;i<G.vexnum;i++)
        if(G.verices[i].vex==v) return i;
    return -1;
}
void finddegree(ALGraph G,Degree de)
{
    int i;
    acnode *p;
    for(i=0;i<G.vexnum;i++)
        de[i].deg=0;
    for(i=0;i<G.vexnum;i++)
        for(p=G.verices[i].firstarc;p!=NULL;p=p->nextarc)
            de[p->adjvex].deg++;
}
void topscort(ALGraph G,Degree &de)
{
    int i,top,k,count=0;
    Vertype tops[MAX_NUM];
    acnode *p;
    finddegree(G,de);
    top=-1;
    for(i=0;i<G.vexnum;i++)
        if(de[i].deg==0){
            de[i].adjvex=top;top=i;
        }
    printf("\n\n\n");
    i=0;
    while(top!=-1){
        tops[i++]=G.verices[top].vex;
        k=top;top=de[top].adjvex;
        for(p=G.verices[k].firstarc;p!=NULL;p=p->nextarc){
            de[p->adjvex].deg--;
            if(de[p->adjvex].deg==0){
                de[p->adjvex].adjvex=top;top=p->adjvex;
            }
        }
    }
    if(i!=G.vexnum)
	{ 
		printf("图中有环\n");
	    printf("请按3重新进入本程序。");
	}
    else{
        printf("拓扑排序的结果为:\n\t\t\t");
        for(i=0;i<G.vexnum;i++)
            printf("%c  ",tops[i]);
    }
	printf("\n");
}
void main()
{
	    ALGraph G;
       Degree de;
       CreatDN(G);
       topscort(G,de);
}