7_7.txt

C语言数据结构知识原代码 C语言数据结构知识原代码C语言数据结构知识原代码

#include<stdio.h>
#define maxsize 100
typedef struct node{
  int data;
  struct node *next;
 }Node;
typedef struct adjnode{
  char ch[10];
  Node *firstarc;
 }Adjnode;
typedef struct stack{
  int data[maxsize];
  int top;
 }Stack;
locate(Adjnode *adj,int n,char *s)
 {
  int i;
  for(i=0;i<n;i++)
   if(strcmp(adj[i].ch,s)==0)return i;
  return -1;
 }
createadj(Adjnode **adj,int n,int e)
 {char s[10],t[10]; int i,j,k;
  Node *p,*q;
  printf("输入各顶点的字符串.\n");
  for(i=0;i<n;i++)
   { gets(s);
    strcpy((*adj)[i].ch,s);
    (*adj)[i].firstarc=NULL;
   }
    printf("请输入各条边.\n");  /*如v1回车v2回车表明有v1到v2的边*/
   for(i=1;i<=e;i++)
   {
    gets(s);
    gets(t);
    j=locate(*adj,n,s);
    k=locate(*adj,n,t);   
    if(k>=0 && j>=0 && j!=k){
     p=(Node *)malloc(sizeof(Node));
     p->data=k;
     p->next=(*adj)[j].firstarc;
     (*adj)[j].firstarc=p;
     }
     else
     printf("边的顶点输入不正确!\n");
   }
 }
topsort(Adjnode *adj,int n)
 {
  Stack s;int *indegree,i,v,count=1;Node *p;
  indegree=(int *)malloc(sizeof(int)*n);
  for(i=0;i<n;i++)
    indegree[i]=0;
   s.top=-1;
  for(i=0;i<n;i++)
    {
     p=adj[i].firstarc;
     while(p){
      indegree[p->data]++;
      p=p->next;
      }
     }
  for(i=0;i<n;i++)
   if(indegree[i]==0){
    s.top++;
    s.data[s.top]=i;
   }
  while(s.top>-1){
   v=s.data[s.top];
   printf("%d.%s ",count++,adj[v].ch);
   s.top--;
   p=adj[v].firstarc;
   while(p){
     indegree[p->data]--;
     if(indegree[p->data]==0){
         s.top++;
         s.data[s.top]=p->data;
         }
      p=p->next;
      }
  }
 }
main()
{
 int n,e,i;
 Adjnode *adj;
 printf("输入无向图的顶点数和边数.\n");
 do
 scanf("%d%d",&n,&e);
 while(n<=0 || e<=0);
 getchar();
 adj=(Adjnode *)malloc(sizeof(Adjnode)*n);
 createadj(&adj,n,e);
 topsort(adj,n);
  }