數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)（青島大學(xué)-王卓）
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
typedef int KeyType; // 設(shè)置關(guān)鍵字類型
typedef struct{
? KeyType key; // 關(guān)鍵字
}SListType;
typedef struct{
? List item[MAXSIZE+1]; // 哨兵類型
? int length;
}Slist;
// 初始化數(shù)據(jù)
void initSList(Slist *L,int length){
? L->item[0].key = 0;
? L->length = length;
? for(int i=1;i<=L->length;i++){
? ? printf("SList[%d]=%d\n",i,L->item[i].key=rand());
? }
}
// 直接插入排序
void insertSort(Slist *L){
? int i=2,j=0;
? for(i=2;i<=L->length;i++){
? ? // 當(dāng)前大于等于前一個(gè)直接跳出循環(huán)
? ? if(L->item[i].key >= L->item[i-1].key) continue;
? ? // 把當(dāng)前值賦值到哨兵位置
? ? L->item[0].key = L->item[i].key;
? ? // 當(dāng)前小于前一個(gè)，把當(dāng)前位置的值替換成前一個(gè)值
? ? for(j=i-1;L->item[j].key>L->item[0].key;j--){
? ? ? L->item[j+1].key = L->item[j].key;
? ? }
? ? // 終止判斷時(shí)，已經(jīng)往前移了一位，所以才要+1
? ? L->item[j+1].key = L->item[0].key;
? }
}
// 遍歷取出數(shù)據(jù)
void printfSList(Slist* L){
? for(int i=1;i<=L->length;i++){
? ? printf("orderSlist[%d]=%d\n",i,L->item[i].key);
? }
}
int main(){
? Slist La;
? initSList(&La,10);
? insertSort(&La);
? printfSList(&La);
? system("pause");
? return 0;
}
