内部排序之表插入排序（大二习题）

gladrain

<FONT size=3>《数据结构》习题（严蔚敏 吴伟民 编著  清华大学出版社 C语言版）P268


大二上学期写的，思路忘了（呵呵其实连什么叫“表插入排序”我都已经想不起来了）



/********************************************\
|                                表插入及导出重排             |
|                                  作者：吴志坚                             |
|                  2002-1-17                 |
\********************************************/
#include &lt;stdio.h&gt;
#define  TRUE 1
#define  FALSE 0
#define  NULL 0
#define  OVERFLOW -2
#define  OK    1
#define  ERROR 0
typedef int Status;
typedef int RcdType;

#define MAXINT 32767
#define SIZE 100
typedef struct{
        RcdType rc;
        int next;
}SLNode;
typedef struct{
        SLNode r[SIZE];
        int length;
}SLinkListType;

void PrintCurrentKEYFieldAndNEXTField(SLinkListType mySL)
{        
        int i;
        printf("\n");
        for(i=0;i&lt;mySL.length;i++)        printf("%5d",mySL.r.rc);
        printf("\n");
        for(i=0;i&lt;mySL.length;i++)  printf("%5d",mySL.r.next);
        printf("\n");
}


Status InitStaticLink(SLinkListType &amp;mySL)
{
        //int temArray[SIZE];//,*ptr
        //prt=&amp;temArray[0];
        int temp;
        printf("初始化静态链表(%d个以内整型数据,以\"32767\"结束输入):\n",SIZE);
        for(int i=1;i&lt;SIZE;i++) //0号元素放“MAXINT”
        {
                scanf("%d",&amp;temp);
                if(temp==MAXINT)
                        break;
                mySL.r.rc=temp;
                mySL.r.next=-1;
        }
        mySL.r[0].rc=MAXINT; mySL.r[0].next=1; mySL.r[1].next=0;//初始状态的要求
        mySL.length=i;
        //PrintCurrentKEYFieldAndNEXTField(mySL);
        return OK;
}


Status TableInsertSort(SLinkListType &amp;mySL)
{
        int i,sign1,sign2;//sign2是当前被比较数据的下标，sign1是前一个被比较数据的下标
        int current,compared;//当前数据 与 被比较数据
        for(i=2;i&lt;mySL.length;i++)
        {
                current=mySL.r.rc;
                sign1=0;sign2=0;
                while(1)
                {
                        sign1=sign2;
                        sign2=mySL.r[sign2].next;
                        compared=mySL.r[sign2].rc;
                        if(current&lt;compared)
                        {
                                mySL.r.next=mySL.r[sign1].next;//“交换”NEXT域
                                mySL.r[sign1].next=i;
                                break;
                        }
                }
                //printf("%d",i);
                //PrintCurrentKEYFieldAndNEXTField(mySL);
        }
        return OK;
}

Status InsertInOrder(SLinkListType mySL)
//仅输出排序结果，并不改变静态表结构
{
        int i,sign;
        int OrderArray[SIZE];
        //RcdType *ptr;
        //ptr=(RcdType *)malloc(mySL.length*sizeof(RcdType));
        sign=0;
        for(i=0;i&lt;mySL.length;i++)
        {
                sign=mySL.r[sign].next;
                OrderArray=mySL.r[sign].rc;
        }
        
        printf("经排序的数列为：\n");
        for(i=0;i&lt;mySL.length-1;i++)
        {
                printf("%5d",OrderArray);
        }
        printf("\n");
        return OK;
}

void main()
{
        SLinkListType mySL;
        InitStaticLink(mySL);
        TableInsertSort(mySL);
        printf("最终静态表的结构为");
        PrintCurrentKEYFieldAndNEXTField(mySL);
        InsertInOrder(mySL);        
}

测试数据，输入：
49
38
65
97
76
13
27
49
32767</FONT>