数据结构C语言版 表插入排序.doc

《数据结构C语言版 表插入排序.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构C语言版表插入排序.txt两个人吵架，先说对不起的人，并不是认输了，并不是原谅了。他只是比对方更珍惜这份感情。/*数据结构C语言版表插入排序算法10.3P267-P270编译环境：Dev-C++4.9.9.2日期：2011年2月13日*/#include#include//静态链表类型#defineSIZE100//静态链表容量typedefintKeyType;//定义关键字类型为整型typedefintInfoType;//定义其他信息的类型typedefstruct{KeyTypekey;/

2、/关键字项InfoTypeotherinfo;//其它数据项，具体类型在主程中定义}RedType;//记录类型typedefstruct{RedTyperc;//记录项intnext;//指针项}SLNode;//表结点类型typedefstruct{SLNoder[SIZE];//0号单元为表头结点intlength;//链表当前长度}SLinkListType;//静态链表类型//由数组D建立n个元素的表插入排序的静态链表SLvoidTableInsert(SLinkListType*SL,RedTypeD[],intn){inti,p

3、,q;//表头结点记录的关键字取最大整数(非降序链表的表尾)(*SL).r[0].rc.key=INT_MAX;(*SL).r[0].next=0;//next域为0表示表尾(现为空表，初始化)for(i=0;i

4、当前记录插入静态链表(*SL).r[q].next=i+1;}(*SL).length=n;}//算法10.3P270//根据静态链表SL中各结点的指针值调整记录位置，使得SL中记录按关键字//非递减有序顺序排列voidArrange(SLinkListType*SL){inti,p,q;SLNodet;p=(*SL).r[0].next;//p指示第一个记录的当前位置for(i=1;i<(*SL).length;++i){//(*SL).r[1..i-1]中记录已按关键字有序排列,第i个记录在SL中的//当前位置应不小于iwhile(p

5、)//找到第i个记录，并用p指示其在SL中当前位置p=(*SL).r[p].next;q=(*SL).r[p].next;//q指示尚未调整的表尾if(p!=i){t=(*SL).r[p];//交换记录，使第i个记录到位(*SL).r[p]=(*SL).r[i];(*SL).r[i]=t;//指向被移走的记录，使得以后可由while循环找回(*SL).r[i].next=p;}p=q;//p指示尚未调整的表尾，为找第i+1个记录作准备}}//求得adr[1..L.length]，adr[i]为静态链表L的第i个最小记录的序号voidSort(

6、SLinkListTypeL,intadr[]){inti=1,p=L.r[0].next;while(p){adr[i++]=p;p=L.r[p].next;}}//算法10.18(L的类型有变)P290//adr给出静态链表L的有序次序，即L.r[adr[i]]是第i小的记录。//本算法按adr重排L.r，使其有序。voidRearrange(SLinkListType*L,intadr[]){inti,j,k;for(i=1;i<(*L).length;++i)if(adr[i]!=i){j=i;(*L).r[0]=(*L).r[i];

7、//暂存记录(*L).r[i]while(adr[j]!=i){//调整(*L).r[adr[j]]的记录到位直到adr[j]=i为止k=adr[j];(*L).r[j]=(*L).r[k];adr[j]=j;j=k;//记录按序到位}(*L).r[j]=(*L).r[0];adr[j]=j;}}voidprint(SLinkListTypeL){inti;for(i=1;i<=L.length;i++)printf("key=%dord=%dnext=%d",L.r[i].rc.key,L.r[i].rc.otherinfo,L.r[i

8、].next);}#defineN8intmain(){RedTyped[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6}