霍夫曼编码.txt

动态对文件和字符串统计个字符出现的次数作为其权值

/* 拓扑排序 */
#include <stdio.h>
#include <stdio.h>
#define MAX_VERTEX_NUM 50
#define STACK_SIZE 50
typedef struct ArcNode{
       int adjvex; /* 顶点在数组中的位置  */
       struct ArcNode *nextarc; /* 下一条弧的指针  */
       }ArcNode;/* 邻接表结点 */
typedef struct VNode{
       int data; /* 顶点信息  */
       ArcNode *firstarc;/* 第一条依附该定点的弧  */
       }VNode,AdjList[MAX_VERTEX_NUM];/* 头结点  */
typedef struct {
       AdjList vertices;
       int vexnum,arcnum;
       }ALGraph;/* 邻接图的信息 */
typedef struct {
       int *base;
       int *top;
       int stacksize;/* 堆栈大小  */
       }SqStack;/* 堆栈结构体 */
/* *****************初始化堆栈********************** */
void InitStack(SqStack *S)
  {
       S->base=(int *)malloc(STACK_SIZE*sizeof(int));
         if(!S->base)
              exit(1);
       S->top=S->base;
       S->stacksize=STACK_SIZE;
  }
 /* *****************入栈************************* */
 void Push(SqStack *S,int e)
   {
            if(S->top-S->base>=S->stacksize)
                  exit(1);
            *(S->top++)=e;
   }     
 /* *****************出栈************************ */
void Pop(SqStack *S,int *e)
    {
           if(S->top==S->base)
                 exit(1);
            *e=*(--S->top);
    }
/* ****************判断栈空************************ */
int StackEmpty(SqStack *S)
    {
            if(S->base==S->top)
                return 1;
            else
                return 0;
    }                                                                 
 /* ***********************建立图****************** */
 void CreatGraph(ALGraph *G)
      {
              int i,n,m; 
              ArcNode *p; 
              printf("please input the vexnum and arcnum:");
              scanf("%d %d",&G->vexnum,&G->arcnum);
              for(i=1;i<=G->vexnum;i++)/* 初始图的表头结点  */
                   {
                        G->vertices[i].data=i;
                        G->vertices[i].firstarc=NULL;
                   }
              for(i=1;i<=G->arcnum;i++)
                   { /* 把弧存入邻接表  */
                          printf("\nplease input edge vertex and vertex:");
                          scanf("%d %d",&n,&m)   ;
                          while(n<0||n>G->vexnum||m<0||m>G->vexnum)
                                {
                                      printf("\nERROR!please input again:");                                                                          
                                      scanf("%d %d",&n,&m);/* 满足条件的顶点 ,n,m之间有边  */
                                }
                          p=(ArcNode *)malloc(sizeof(ArcNode));/* 为邻接表结点申请空间  */
                          if(!p)
                             exit(1);
                          p->adjvex=m;
                         p->nextarc = G->vertices[n].firstarc;/* 链表的操作  */
                          G->vertices[n].firstarc=p;
                   }
               printf("The Adjacency List :\n");
               for(i=1;i<=G->vexnum;i++)/* 输出此邻接表  */
                    { 
                             printf("%d",G->vertices[i].data);/* 头结点  */
                             for(p=G->vertices[i].firstarc;p;p=p->nextarc)
                                   printf("%3d",p->adjvex);/* 表结点  */
                              printf("\n");
                    }
     }
  /* *******************求入度*************************** */
  void FindInDegree(ALGraph G,int indegree[])
        {
               int i;
               for(i=1;i<=G.vexnum;i++)
                    indegree[i]=0;/* 初始为0  */
               for(i=1;i<=G.vexnum;i++)
                    { /* 遍历邻接表，求入度  */
                           while(G.vertices[i].firstarc)
                                {
                                       indegree[G.vertices[i].firstarc->adjvex]++; /* 弧头元素入度加一  */
                                       G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;
                                }
                    }
        }
 /* **********************拓扑排序*************************** */
 void TopologicalSort(ALGraph G)
     {
             int indegree[MAX_VERTEX_NUM];
             int i,k,n;
             int count=0;
             ArcNode *p;
             SqStack S;
        FindInDegree(G,indegree);/* 用数组名 。  */
        InitStack(&S);
        for(i=1;i<=G.vexnum;i++)
            {
                     if(!indegree[i])/* 入度为0，进栈  */
                          Push(&S,i);
            }
        printf("Topological Sort is \n");
        while(!StackEmpty(&S)) /* 栈不空，出栈并输出结果  */
              {
                     Pop(&S,&n);
                     printf("%d ",G.vertices[n].data);
                     count++;/* 输出i号顶点并计数  */
                     for(p=G.vertices[n].firstarc;p!=NULL;p=p->nextarc)
                       
                          k=p->adjvex;/*对i号定点的每个邻接点的入度减一*/
                                        if(!(--indegree[k]))
                                           Push(&S,k);/* 入度为0，进栈  */
                           }
              }
        if(count<G.vexnum)
              printf("Error!\n");
        else
              printf("\nSort Success !");
     }    
   /* *********************主函数**********************                     */
 int main()
   {
               ALGraph G;
               CreatGraph(&G);
               TopologicalSort(G);
               getch();
               return 0;
   }                                                                                          
                  




























  #include <stdio.h>
#include <string.h>
 # define  m    6     
typedef struct arcnode
{int adjvex;
 struct arcnode *nextarc;
}arcnode,*anode;
typedef struct vexnode
{int  data;
 int  indegree;
 struct arcnode *firstarc;
}vexnode;
vexnode L2[m];
anode L1;
main()
{int r,n,i,j,count=0,k;

printf("输入图解点数目/n");
scanf("%d",&n);
 
for(i=1;i<=n;i++)
{L2[i].data=i;
L2[i].indegree=0;
L2[i].firstarc=0;
}
 printf("input the edge:i,j\n");
scanf("%d,%d",&i,&j);
 while(i!=0)
    { L1=(anode*)malloc(sizeof(arcnode));
      L1->adjvex=j;
      L1->nextarc=L2[i].firstarc;
      L2[i].firstarc=L1;
      L2[j].indegree++;

      scanf("%d,%d",&i,&j);

 }
 for(i=1;i<=n;i++)
  printf("%d,%d\n",L2[i].data,L2[i].indegree);
  getch();
  for(j=1;j<=n-count;j++)
   for(i=1;i<=n;i++)
   while(L2[i].indegree==0)
{ L2[i].indegree=-1;
  printf("\nafter the topsort\n:");

    printf("%d\n",L2[i].data);count++;
    for(L1=L2[i].firstarc;L1;L1=L1->nextarc)
      {k=L1->adjvex;
     --L2[k].indegree;}
   }getch();
 }