7_8.txt

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

#include<stdio.h>
#include<stdlib.h>
#define intmax 32767
typedef struct node{
  int data;
  int w;
  struct node *next;
 }Node;
typedef struct adjnode{
  char ch[10];
  Node *firstarc;
 }Adjnode;
typedef struct f{
  int *p;
  }Path;
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],w[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);
    gets(w);
    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->w=atoi(w);
     p->next=(*adj)[j].firstarc;
     (*adj)[j].firstarc=p;
     }
     else
     printf("边的顶点输入不正确!\n");
   }
 }
minvetex(int dist[],int n,int visited[],int v)
 {
  int i=0,j;int vetex=-1;
  while(i<n && (visited[i]==1 || i==v))i++;
  if(i<n)vetex=i;
  for(j=i+1;j<n;j++)
    if(visited[i]!=1 && i!=v && dist[vetex]>dist[j])vetex=j;
  return vetex;
  }
  
minpath(Adjnode *adj,int n,int v)
 {
  int *dist,i,j,k,vetex;Path *path;Node *p; 
  int *visited;
  dist=(int *)malloc(sizeof(int)*(n-1));
  path=(Path *)malloc(sizeof(Path)*(n-1));
  visited=(int *)malloc(sizeof(int)*n);
  for(i=0;i<n;i++)
    visited[i]=0;
  for(i=0;i<n;i++)
   { dist[i]=intmax;
     path[i].p=(int *)malloc(sizeof(int)*(n+1));
     path[i].p[0]=0;
   }
   dist[v]=0;
   p=adj[v].firstarc;
   while(p){
    dist[p->data]=p->w;path[p->data].p[0]=2;
    path[p->data].p[1]=v;
    path[p->data].p[2]=p->data;
    p=p->next;
    }
   path[v].p[0]=2;
   path[v].p[1]=v;path[v].p[2]=v;
   for(i=1;i<n;i++)
   {
    vetex=minvetex(dist,n,visited,v);
    if(vetex>=0){
       visited[vetex]=1;
       for(j=0;j<n;j++)
        if(visited[j]!=1 && j!=v)
         {
          p=adj[vetex].firstarc;
          while(p ){
             if(p->data==j)break;
             p=p->next;
             }
           if(p && dist[j]>dist[vetex]+p->w)
            {
             dist[j]=dist[vetex]+p->w;
             path[j].p[0]=path[vetex].p[0]+1;
             for(k=1;k<=path[vetex].p[0];k++)
              path[j].p[k]=path[vetex].p[k];
              path[j].p[k]=j;
            } 
         }
      }/*if*/
     }/*for*/
   for(i=0;i<n;i++)
    {
    printf("the distance of %s-->%s=%d\n",adj[v].ch,adj[i].ch,dist[i]);
    printf("the path of  %s-->%s=",adj[v].ch,adj[i].ch);
    for(j=1;j<=path[i].p[0];j++)
     printf("%s ",adj[path[i].p[j]].ch);
    printf("\n");
    }
   
 }
main()
{
 int n,e,i;
 Adjnode *adj;char s[10];
 printf("输入无向图的顶点数和边数.\n");
 do
 scanf("%d%d",&n,&e);
 while(n<=0 || e<=0);
 getchar();
 adj=(Adjnode *)malloc(sizeof(Adjnode)*n);
 createadj(&adj,n,e);
 printf("请输入某个出发的顶点：\n");
 gets(s);
 i=locate(adj,n,s);
 if(i>=0 && i<n)
 minpath(adj,n,i);
  }