//本程序适合在turbo c++ 运行，内部的许多注释是本人在调试使用的，以跟踪错误所在并未去掉
/*静态连表插入排序*/
#define SIZE 100
#define KeyType int
#define MAXINT  30000
#include<stdio.h>
#include<stdlib.h>
#include"iostream.h"
int safe=0;
typedef struct{
  KeyType key;
  int next;
}SNode;
typedef struct {
 SNode r[SIZE];
 int length;
}SLink;
void outputkey(SLink* sl);
void outputnext(SLink* sl);
void Soutput(SLink * sl);
void Arrange(SLink *);
void main(){
 SLink SL;
 int index,pre_index;
  int i;
 printf("Now bigin to input the list :nFirst input the length:");
 scanf("%d",&SL.length);
 printf("please input %d elementsn",SL.length  );
 for(i=1;i<=SL.length;i++)
   {scanf("%d",&(SL.r[i].key));
   } 
   printf("Review the array: ");
   outputkey(&SL);
     SL.r[0].key=MAXINT;
  SL.r[0].next=1;
  SL.r[1].next=0;
  for(i=2;i<=SL.length;i++){
 pre_index=0;
    index=SL.r[pre_index].next;
    do{
  //   cout<<"i:"<<i<< "index:"<<index<<endl;
    if(SL.r[i].key<=SL.r[index].key)
       {SL.r[pre_index].next=i;
       SL.r[i].next=index;
       break;
       }
 else{
  pre_index=index;
  index=SL.r[index].next;
 }

      safe++;
     if(safe>15){cout<<"Error occured!n"<<endl; exit(0);}
     }while(index<i);

  }    /*end for*/
 cout<<"final check:";
 outputkey(&SL);
 Soutput(&SL);
 cout<<"Final array:";
 Arrange(&SL);
 outputnext(&SL);
}//end main

void outputkey(SLink* sl){
  int i;
  for(i=0;i<=sl->length;i++){
    printf("%d ",sl->r[i].next);
   }
printf("n");