struct ElemType{
  char name[10];
  int mark;
};

void InsertSort(ElemType A[],int n)  //straight insertion sorting
{
  ElemType x;
  int i,j;
  for(i=1;i<n;i++){
    x=A[i];
    for(j=i-1;j>=0;j--)
      if(x.mark>A[j].mark)
        A[j+1]=A[j];
      else
        break;
    A[j+1]=x;
  }
}

void ShellSort(ElemType A[],int n)
{
  ElemType x;
  int i,j,d;
  for(d=n/2;d>=1;d/=2){
    for(i=d;i<n;i++){
      x=A[i];
      for(j=i-d;j>=0;j-=d){
        if(x.mark>A[j].mark)
          A[j+d]=A[j];
        else
          break;
      }
      A[j+d]=x;
    }
  }
}

void SelectSort(ElemType A[],int n)
{
  ElemType x;
  int i,j,k;
  for(i=1;i<=n-1;i++){
    k=i-1;
    for(j=i;j<=n-1;j++)
      if(A[j].mark>A[k].mark)
        k=j;
    if(k!=i-1){
      x=A[i-1];
      A[i-1]=A[k];
      A[k]=x;
    }
  }
}

void PrintSortResultByMark(ElemType A[],int n)
{
  int i,rank;
  cout<<"Name  Mark  Rank"<<endl;
  for(i=0;i<n;i++){
    rank=i+1;
    if(i>0&&A[i].mark==A[i-1].mark)
      rank--;
    cout<<A[i].name<<"     "<<A[i].mark<<"     "<<rank<<endl;
  }
}

void PrintSortResultByOrder(ElemType A[],int n)
{
  int i,rank;
  cout<<"Rank  Name  Mark"<<endl;
  for(i=0;i<n;i++){
    rank=i+1;
    if(i>0&&A[i].mark==A[i-1].mark)
      rank--;
    cout<<rank<<"     "<<A[i].name<<"     "<<A[i].mark<<endl;
  }
}

typedef struct
{
  char key[20];
}ElemType;
typedef struct Node
{
  ElemType data;
  struct Node *next;
}LNode;
typedef LNode *LinkHashList[HashMaxSize];

int Hash(char *K,int m)
{
  int len=strlen(K);
  unsigned int h=0;
  for(int i=0;i<len;i++){
    h<<=3;
    h+=K[i];
  }
  return h%m;
}

void InitHashList(LinkHashList HT)
{
  for(int i=0;i<HashMaxSize;i++)
    HT[i]=NULL;
}

bool Insert(LinkHashList HT,int m,ElemType item)
{
  int d=Hash(item.key,m);
  LNode *p=new LNode;
  if(p==NULL)
    return false;
  p->data=item;
  p->next=HT[d];
  HT[d]=p;
  return true;
}

ElemType *Search(LinkHashList HT,int m,ElemType item)
{
  int d=Hash(item.key,m);
  LNode *p=HT[d];
  while(p!=NULL){
    if(strcmp(p->data.key,item.key)==0)
      return &(p->data);
    else
      p=p->next;
  }
  return NULL;
}

bool Delete(LinkHashList HT,int m,ElemType item)
{
  int d=Hash(item.key,m);
  LNode *p=HT[d],*q;
  if(p==NULL)
    return false;
  if(strcmp(p->data.key,item.key)==0){
    HT[d]=p->next;
    delete p;
    return true;
  }
  q=p->next;
  while(q!=NULL){
    if(strcmp(q->data.key,item.key)==0){
      p->next=q->next;
      delete q;
      return true;
    }
    else{
      p=q;
      q=q->next;
    }
  }
  return false;
}

void PrintHashList(LinkHashList HT,int m)  //按散列地址依次输出散列表的所有元素
{
  int i;
  for(i=0;i<m;i++){
    LNode *p=HT[i];
    while(p!=NULL){
      cout<<p->data.key<<" ";
      p=p->next;
    }
  }
  cout<<endl;
}

typedef struct{
  int key;   //职工号，作为关键字域
  char depart[13];  //部门名称，作为索引值域
  int next;   //链接同一部门的职工记录
}ElemType;
typedef char IndexKeyType[13];
struct IndexItem{
  IndexKeyType index;
  int start;
  int length;
};
typedef IndexItem indexlist[ILMaxSize];
typedef ElemType mainlist[MaxSize];

void CreateIndexList(mainlist A, int n, indexlist B, int m)
{
  int i,j;
  for(j=0;j<m;j++){
    B[j].start=-1;
    B[j].length=0;
  }
  for(i=0;i<n;i++)
    for(j=0;j<m;j++)
      if(strcmp(A[i].depart,B[j].index)==0){
        if(B[j].start==-1)
          B[j].start=i;
        B[j].length++;
      }
  int t;
  for(j=0;j<m;j++){
    t=B[j].start;
    for(i=0;i<n;i++){
      if(i==B[j].start)
        continue;
      if(strcmp(A[i].depart,B[j].index)==0){
        A[t].next=i;
        t=i;
      }
    }
  }
  cout<<"now print the mainlist after sort :"<<endl;
  for(j=0;j<m;j++){
    i=B[j].start;
    while(i!=-1){
      cout<<A[i].key<<" "<<A[i].depart<<" -> ";
      i=A[i].next;
    }
    cout<<endl;
  }
}

void SearchIndexList(mainlist A, int n, indexlist B, int m, ElemType worker)
{
  int i,j;
  for(i=0;i<m;i++)
    if(strcmp(worker.depart,B[i].index)==0)
      break;
  if(i==m)
    exit(1);
  j=B[i].start;
  while(j!=-1)
    if(worker.key==A[j].key){
      cout<<"found the record matched in "<<j<<" position."<<endl;
      break;
    }
    else
      j=A[j].next;
  if(j==-1)
    cout<<"Not found."<<endl;
}

void InsertIndexList(mainlist A, int n, indexlist B, int m, ElemType worker)
{
  int i,j;
  for(i=0;i<n;i++){
    j=i;
    if(strcmp(worker.depart,A[j].depart)==0){
      while(A[j].next!=-1)
        j=A[j].next;
      A[j].next=n;
      strcpy(A[n].depart,worker.depart);
      A[n].key=worker.key;
      A[n].next=-1;
    }
  }
  for(j=0;j<m;j++)
    if(strcmp(worker.depart,B[j].index)==0){
      B[j].length++;
      break;
    }
}

void  InitAdjoin(adjlist G)
{
  for(int i=0;i<MaxVertexNum;i++)
    G[i]=NULL;
}

void CreateAdjoin(adjlist G, int n)
{
  char *s=new char[100];
  cerr<<"please input the adjmatrix :"<<endl;
  cin>>s;
  istrstream sin(s);
  char c1,c2,c3;
  int i,j;
  Edgenode *p;
  sin>>c1;
  do{
    sin>>c1>>i>>c2>>j>>c3;
    p=new Edgenode;
    p->adjvex=j;
    p->next=G[i];
    G[i]=p;
    sin>>c1;
    if(c1=='}')
      break;
  }while(1);
}

void  PrintAdjoin (adjlist G, int n)
{
  int i,j;
  Edgenode *p;
  cout<<"V={";
  for(i=0;i<n-1;i++)
    cout<<i<<',';
  cout<<n-1<<'}'<<endl;
  cout<<"E={";
  for(i=0;i<n;i++){
    p=G[i];
    while(p){
      j=p->adjvex;
      cout<<'<'<<i<<','<<j<<'>'<<',';
      p=p->next;
    }
  }
  cout<<'}'<<endl;
}

#include<iostream.h>
#include<stdlib.h>
#include<strstrea.h>
typedef int VertexType;
typedef int WeightType;
const int MaxVertexNum=10;
const WeightType MaxValue=20000;
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];
struct edgenode
{
    int adjvex;
    edgenode *next;
};
typedef edgenode *adjlist[MaxVertexNum];
#include"Graph2.h"

void PATH(adjlist path,int m,int j)
{
  edgenode *p,*q,*s;
  p=path[j];
  while(p!=NULL)
  {
    path[j]=p->next;
    delete p;
    p=path[j];
  }
  p=path[m];
  while(p!=NULL)
  {
    q=new edgenode;
    q->adjvex=p->adjvex ;
    if(path[j]==NULL)
    {
      path[j]=q;
    }
    else    
      s->next=q;
    s=q;
    p=p->next;
  }
  q=new edgenode;
  q->adjvex=j;
  q->next=NULL;
  s->next=q;
}

void Dijkstra(adjmatrix GA,int dist[],adjlist path,int i,int n)
{
  int *s=new int[MaxVertexNum];
  for(int j=0;j<n;j++)
  {
    if(j==i)
      s[j]=1;
    else
      s[j]=0;
    dist[j]=GA[i][j];
    if((dist[j]<MaxValue)&&(j!=i))
    {
      edgenode *p1=new edgenode;
      edgenode *p2=new edgenode;
      p1->adjvex=i;
      p2->adjvex =j;
      p2->next =NULL;
      p1->next=p2;
      path[j]=p1;
    }
    else
      path[j]=NULL;
  }
  int w;
  int m;
  for(int k=1;k<=n-2;k++){
    w=MaxValue;
    m=i;
    for(j=1;j<n;j++)
      if(s[j]==0&&dist[j]<w){
        w=dist[j];
        m=j;
      }
      if(m!=i)
        s[m]=1;
      else
        break;
      for(j=0;j<n;j++)
        if(s[j]==0&&dist[m]+GA[m][j]<dist[j]){
          dist[j]=dist[m]+GA[m][j];
          PATH(path,m,j);
        }
  }
}

void PrintPath(int dist[], edgenode *path[], int n)
{
  int i,t;
  for(i=1;i<n;i++){
    edgenode *p=path[i];
    cout<<"V={";
    while(p!=NULL){
      cout<<p->adjvex<<',';
      p=p->next;
    }
    cout<<"}"<<"    length: "<<dist[i]<<endl;
  }
}

void main()
{
    adjmatrix GA;
  int n;
  cout<<"input the points of the graph: ";
  cin>>n;
  InitMatrix(GA);
  CreateMatrix(GA,n);
  PrintMatrix(GA,n);
  cout<<endl;
  cout<<"now print the path and length from v0 to others :"<<endl;
    adjlist path;
    int *dist=new int[MaxVertexNum];
    Dijkstra(GA,dist,path,0,n);
  PrintPath(dist,path,n);
}