Timmy's Blog

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{
  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;
}