數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書

數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書太原理工大學(xué)2011年3月-PAGE19-實驗一線性表一、目的與要求熟悉線性表的基本操作在順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)，基本操作在實際問題中的應(yīng)用。仔細(xì)分析并調(diào)試運行下面給出的程序。二、實驗內(nèi)容某省福利彩票的單注號碼由1～35中的任意7個數(shù)組成，中獎號碼由7個基本號碼和1個特別號碼組成。用計算機(jī)模擬搖獎過程隨機(jī)產(chǎn)生8個號碼，前7個號碼為基本號碼，最后1個號碼為特別號碼。分析：參考電視中的搖獎過程，使用線性表sq1存儲35個號碼，sq2存儲抽獎結(jié)果。線性表sq2中，前7個元素是基本號碼，第8個元素是特別號碼。使用函數(shù)randomize()初始化隨機(jī)發(fā)生器，使用random(n)產(chǎn)生范圍在0～n-1之間的隨機(jī)數(shù)，模擬抽獎過程的隨機(jī)性。抽獎過程是：用random()產(chǎn)生一個隨機(jī)數(shù)k，將線性表sq1中的第k個元素刪除，插入線性表sq2的最后。如此重復(fù)8次，產(chǎn)生8個號碼。最后輸出抽獎結(jié)果。如：在線性表sq2中保存的抽獎號碼依次是：2613521227316則輸出結(jié)果是：2613052102270316C語言源程序如下：#defineN35#defineM8#defineSUCCESS1#defineFAILED-1#defineINIT_SIZE50#defineADDNODE10#include<stdlib.h>typedefintELEMENT;/*定義元素類型*/typedefstructslist_st/*定義順序表類型*/{ELEMENT*element;intsize;intlength;}SLIST;intInitSList(SLIST*list);/*函數(shù)聲明*/intGetSListLength(SLIST*list);intInsertElement(SLIST*list,intposition,ELEMENTelem);intDeleteElement(SLIST*list,intposition,ELEMENT*elem);intPrintSList(SLIST*list);main()/*主函數(shù)*/{inti,j,k;ELEMENTtmpelem;SLISTsq1,sq2;/*定義順序表*/InitSList(&sq1);/*初始化順序表sq1*/InitSList(&sq2);/*初始化順序表sq1*/for(i=1;i<=N;i++)/*將N()=35個號碼存儲在順序表sq1中*/InsertElement(&sq1,i,i);randomize();for(i=1;i<=M;i++){j=GetSListLength(&sq1);/*求順序表的長度*/k=random(j)+1;/*產(chǎn)生一個隨機(jī)數(shù)*/DeleteElement(&sq1,k,&tmpelem);/*刪除順序表sq1的第k個元素*/InsertElement(&sq2,i,tmpelem);/*插入到順序表sq2的最后*/}PrintSList(&sq2);/*輸出抽獎結(jié)果*/}intInitSList(SLIST*list)/*初始化順序表*/{if((list->element=(ELEMENT*)malloc(INIT_SIZE*sizeof(ELEMENT)))==NULL)returnFAILED;else{list->size=INIT_SIZE;list->length=0;returnSUCCESS;}}intGetSListLength(SLIST*list)/*求表長*/{if(list!=NULL)returnlist->length;elsereturnFAILED;}intInsertElement(SLIST*list,intposition,ELEMENTelem)/*插入*/{inti;ELEMENT*tmplist;if(position<1||position>list->length+1)returnFAILED;if(list->length==list->size){tmplist=(ELEMENT*)realloc(list->element,(list->size+ADDNODE)*sizeof(ELEMENT));if(tmplist==NULL)returnFAILED;list->element=tmplist;list->size+=ADDNODE;}for(i=list->length-1;i>=position-1;i--)list->element[i+1]=list->element[i];list->element[position-1]=elem;list->length++;returnSUCCESS;}intDeleteElement(SLIST*list,intposition,ELEMENT*elem)/*刪除*/{inti;if(position<1||position>list->length)returnFAILED;*elem=list->element[position-1];for(i=position;i<list->length;i++)list->element[i-1]=list->element[i];list->length--;returnSUCCESS;}intPrintSList(SLIST*list)/*輸出順序表中的元素*/{inti;if(list==NULL)returnFAILED;printf("\n");for(i=0;i<list->length;i++)printf("%02d",list->element[i]);printf("\n");}三、思考題1．設(shè)有n個人圍坐在一個圓桌周圍，現(xiàn)從第s個人從1開始報數(shù)，數(shù)到第m的人離開圓桌，然后從下一個人重新開始報數(shù)，數(shù)到m的人又離開圓桌，如此重復(fù)，直到所有的人離開圓桌。對任意給定的n,s,m，求n個人離開圓桌的次序。提示：用循環(huán)鏈表存儲n個人的信息（可以是姓名，也可以是編號），從鏈表的首結(jié)點開始計數(shù)，到s時，刪除該結(jié)點，插入到出列鏈表的(第二個鏈表)最后，接著刪除結(jié)點的下一個結(jié)點重新計數(shù)，直到該鏈表為空。第二個鏈表的結(jié)點數(shù)據(jù)就是離開圓桌的次序。2．多項式相加。用單鏈表ha存儲多項式A(x)=a0+a1x1+a2x2+…+anxn(其中ai是非0系數(shù))，用單鏈表hb存儲多項式B(x)=b0+b1x1+b2x2+…+bmxm(其中bj是非0系數(shù))，要求計算C(x)=A(x)+B(x)，結(jié)果存儲在單鏈表hc中。設(shè)：A(x)=9+7x1-5x2+3x3+x5B(x)=10+8x1-6x3+4x4+2x5

實驗二棧和隊列一、目的與要求通過棧應(yīng)用的一個典型實例——迷宮求解，熟悉棧的操作特點和棧的使用方法。仔細(xì)分析并調(diào)試運行下面給出的程序。二、實驗內(nèi)容所謂迷宮求解就是要在迷宮中尋找一條從入口到出口的路徑。采用試探法——從入口出發(fā)，沿著某一方向向前搜索，如果有路就繼續(xù)前進(jìn)，否則沿原路退回一步，重新選擇新的方向，在繼續(xù)搜索。如此重復(fù)，直到到達(dá)出口或退回到入口(表明迷宮中無路徑)。為了保證在搜索路徑過程中能沿原路回退，需用一個后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)——棧，保存搜索過程中走過的路徑。000000000000000000000000000001101101000010100100001111110000100100000010111100001110011000000000000000000000在迷宮中，搜索從入口到出口路徑的算法思想是這樣的：從迷宮的入口出發(fā)，先將迷宮的入口位置入棧。取棧頂位置作為當(dāng)前位置，如果當(dāng)前位置就是出口位置，那么至此已經(jīng)找到一條路徑，算法結(jié)束。如果當(dāng)前位置還未被搜索過，則在當(dāng)前位置上置路徑標(biāo)志(ROAD_ID)，表示已經(jīng)位于搜索路徑上，并將其入棧。接著查看其它相鄰的位置(上下左右4個相鄰位置)，將所有的候選通路(具有PATH_ID標(biāo)志的位置)依次入棧，如此重復(fù)，直到找到出口。如果當(dāng)前位置為死路(上下左右4個相鄰位置要么都已搜索，要么都是墻)，則表明當(dāng)前位置必不在路徑上，需回退。如果棧中的前一位置尚未被搜索過，則從此位置開始搜索其它路徑。如果棧中的前一位置已經(jīng)搜索過，則說明該位置也是死路，需繼續(xù)回退。如果最后棧為空，則說明迷宮中沒有從入口到達(dá)出口的路徑。C語言源程序如下：#defineSUCCESS1#defineFAILED-1#defineTRUE1#defineFALSE0#defineROW_NUM8+2#defineCOL_NUM8+2#defineSTACK_SIZE50typedefstructposition_st{intx;inty;}POSITION;typedefstructstack_st{POSITIONdata[STACK_SIZE];inttop;}STACK;STACKmystack;#defineWALL_ID0#definePATH_ID1#defineROAD_ID2#defineDEAD_ID3intSearchMazePath(intmaze[][COL_NUM],POSITION*start,POSITION*end);voidInitStack(STACK*stack);intPushStack(STACK*stack,POSITION*elem);intPopStack(STACK*stack,POSITION*elem);intIsStackEmpty(STACK*stack);main(){inti,j;intmaze[ROW_NUM][COL_NUM]={{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,1,1,0,1,1,0,1,0,0},{0,0,1,0,1,0,0,1,0,0},{0,0,1,1,1,1,1,1,0,0},{0,0,1,0,0,1,0,0,0,0},{0,0,1,0,1,1,1,1,0,0},{0,0,1,1,1,0,0,1,1,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0}};POSITIONstart={2,1},end={7,8},pos;SearchMazePath(maze,&start,&end);for(i=0;i<ROW_NUM;i++){for(j=0;j<COL_NUM;j++)printf("%d",maze[i][j]);printf("\n");}printf("\n");}intSearchMazePath(intmaze[][COL_NUM],POSITION*start,POSITION*end){POSITIONposition,tmppos;InitStack(&mystack);PushStack(&mystack,start);while(IsStackEmpty(&mystack)!=TRUE){PopStack(&mystack,&position);if(maze[position.x][position.y]==WALL_ID){maze[position.x][position.y]=DEAD_ID;continue;}elseif(maze[position.x][position.y]==PATH_ID){PushStack(&mystack,&position);maze[position.x][position.y]=ROAD_ID;}if(position.x==end->x&&position.y==end->y)returnSUCCESS;if(maze[position.x+1][position.y]!=PATH_ID&&maze[position.x][position.y+1]!=PATH_ID&&maze[position.x-1][position.y]!=PATH_ID&&maze[position.x][position.y-1]!=PATH_ID)maze[position.x][position.y]=DEAD_ID;else{if(maze[position.x][position.y-1]==PATH_ID){tmppos.x=position.x;tmppos.y=position.y-1;PushStack(&mystack,&tmppos);}if(maze[position.x-1][position.y]==PATH_ID){tmppos.x=position.x-1;tmppos.y=position.y;PushStack(&mystack,&tmppos);}if(maze[position.x][position.y+1]==PATH_ID){tmppos.x=position.x;tmppos.y=position.y+1;PushStack(&mystack,&tmppos);}if(maze[position.x+1][position.y]==PATH_ID){tmppos.x=position.x+1;tmppos.y=position.y;PushStack(&mystack,&tmppos);}}}}voidInitStack(STACK*stack){stack->top=-1;}intPushStack(STACK*stack,POSITION*elem){if(stack->top>=STACK_SIZE)returnFAILED;stack->top++;stack->data[stack->top].x=elem->x;stack->data[stack->top].y=elem->y;returnSUCCESS;}intPopStack(STACK*stack,POSITION*elem){if(stack->top<0)returnFAILED;elem->x=stack->data[stack->top].x;elem->y=stack->data[stack->top].y;stack->top--;returnSUCCESS;}intIsStackEmpty(STACK*stack){if(stack->top<0)returnTRUE;elsereturnFALSE;}三、思考題1．請列舉日常生活中棧的應(yīng)用。2．請列舉日常生活中隊列的應(yīng)用。

實驗三樹一、目的與要求熟悉樹和二叉樹的表示方法和遍歷方式，掌握有關(guān)算法的實現(xiàn)，了解樹在計算機(jī)科學(xué)及其它工程技術(shù)中的應(yīng)用。仔細(xì)分析并調(diào)試運行下面給出的程序。二、實驗內(nèi)容1．任意給定一棵二叉樹。試設(shè)計一個程序，建立二叉樹并對其進(jìn)行遍歷。假設(shè)有如下的二叉樹：二叉樹的結(jié)點若無子樹，則將其子樹看作“.”，按照前序序列的順序輸入二叉樹的結(jié)點內(nèi)容。對上圖所示的二叉樹，其輸入序列為：ABD..EH...CF.I..G..對建立的二叉樹進(jìn)行后序遍歷，若為空二叉樹，則輸出：Thisisaemptybinarytree。若二叉樹不空，則輸出遍歷序列。對上圖所示的二叉樹，輸出結(jié)果為：DHEBIFGCA二叉樹采用二叉鏈表存儲。采用遞歸方法建立和遍歷二叉樹。二叉樹的建立過程是：首先建立二叉樹的根結(jié)點，然后建立其左右子樹，直到空子樹為止。C語言源程序如下：#include<stdio.h>typedefstructnode{chardata;structnode*left,*right;}NODE;/*建立二叉樹*/voidcreatbit(NODE**tree){charx;x=getchar();if(x!='.'){(*tree)=(NODE*)malloc(sizeof(NODE));(*tree)->data=x;creatbit(&((*tree)->left));creatbit(&((*tree)->right));}else(*tree)=NULL;}/*后根遍歷二叉樹*/voidPostOrderTraverse(NODE*t){if(t!=NULL){PostOrderTraverse(t->left);PostOrderTraverse(t->right);printf("%c",t->data);}}main(){NODE*tree;printf("Pleaseinputtree:");creatbit(&tree);printf("\n");if(tree==NULL)printf("Thisisaemptybinarytree.\n");PostOrderTraverse(tree);printf("\n");}2．假設(shè)通訊中電文由a,b,c,d,e,f,g,h等8個字符組成，其出現(xiàn)的頻率分別為：12，23，9，2，27，6，15，5。請設(shè)計程序，給出這8個字符的赫夫曼編碼。分析：m個權(quán)值的赫夫曼樹由2m-1個結(jié)點，采用數(shù)組存儲赫夫曼樹中的結(jié)點，樹中的每個結(jié)點結(jié)構(gòu)為：wparentleftright其中：w為結(jié)點的權(quán)，parent是結(jié)點的雙親在數(shù)組中的下標(biāo)，left和right分別是結(jié)點的左右孩子在結(jié)點數(shù)組中的下標(biāo)。另外，與每個葉子結(jié)點對應(yīng)字符的編碼被存放在一個字符數(shù)組中，因為編碼是不等長的，即每個編碼所占用的空間不等，應(yīng)此存儲編碼串的空間需動態(tài)分配。C語言源程序如下：#defineSUCCESS1#defineFAILED-1#defineCODE_NUM8#defineMAX_WEIGHT32767#include<stdio.h>#include<string.h>typedefstructnode_st{/*定義樹結(jié)點類型*/intw;intparent,left,right;}NODE;typedefstructchar_code_st{/*定義字符、編碼類型*/charch;intweight;char*huffmancode;}HCODE;char*tmpcode;intCreatHuffmanCode(HCODE*node,intnodenum);intGetTwoNode(NODE*huffmantree,intn,int*s1,int*s2);main(){inti,nodenum;/*字符個數(shù)*/HCODEnode[CODE_NUM]={{'a',12},{'b',23},{'c',9},{'d',2},{'e',27},{'f',6},{'g',15},{'h',5}};nodenum=CODE_NUM;CreatHuffmanCode(node,nodenum);/*求赫夫曼編碼*/for(i=0;i<nodenum;i++)/*輸出字符及其編碼*/printf("%c%s\n",node[i].ch,node[i].huffmancode);}/*定義求赫夫曼編碼函數(shù)*/intCreatHuffmanCode(HCODE*node,intnodenum){inti,m,s1,s2;intcurrent,preid,tmpid;NODE*huffmantree;if(nodenum<1)returnFAILED;/*字符數(shù)不對,返回失敗標(biāo)志*/if(nodenum==1)returnSUCCESS;/*只有一個字符，無需編碼*/m=2*nodenum-1;/*赫夫曼樹的結(jié)點數(shù)*/huffmantree=(NODE*)malloc(m*sizeof(NODE));for(i=0;i<nodenum;i++){/*初始化葉子結(jié)點*/huffmantree[i].w=node[i].weight;huffmantree[i].parent=0;huffmantree[i].left=0;huffmantree[i].right=0;}for(i=nodenum;i<m;i++){/*初始化非葉子結(jié)點*/huffmantree[i].w=0;huffmantree[i].parent=0;huffmantree[i].left=0;huffmantree[i].right=0;}for(i=nodenum;i<m;i++){/*構(gòu)造赫夫曼樹*/GetTwoNode(huffmantree,i,&s1,&s2);huffmantree[s1].parent=i;huffmantree[s2].parent=i;huffmantree[i].left=s1;huffmantree[i].right=s2;huffmantree[i].w=huffmantree[s1].w+huffmantree[s2].w;}tmpcode=(char*)malloc(nodenum*sizeof(char));tmpcode[nodenum-1]='\0';for(i=0;i<nodenum;i++){/*求赫夫曼編碼*/current=nodenum-1;/*存放當(dāng)前編碼的位置*/for(preid=i,tmpid=huffmantree[i].parent;tmpid!=0;preid=tmpid,tmpid=huffmantree[tmpid].parent)if(huffmantree[tmpid].left==preid)tmpcode[--current]='0';elsetmpcode[--current]='1';node[i].huffmancode=(char*)malloc((nodenum-current)*sizeof(char));strcpy(node[i].huffmancode,&tmpcode[current]);}returnSUCCESS;}/*找權(quán)值最小的兩棵子樹*/intGetTwoNode(NODE*huffmantree,intn,int*t1,int*t2){inttmp1,tmp2,i;tmp1=tmp2=MAX_WEIGHT;*t1=*t2=0;for(i=0;i<n;i++)if(huffmantree[i].parent==0)if(huffmantree[i].w<tmp1){*t2=*t1;tmp2=tmp1;*t1=i;tmp1=huffmantree[i].w;}elseif(huffmantree[i].w<tmp2){*t2=i;tmp2=huffmantree[i].w;}}

實驗四查找一、目的與要求熟悉查找的概念和查找方法，設(shè)計相關(guān)的查找程序。本實驗給出了順序查找、二分查找和二叉排序查找的程序，請仔細(xì)閱讀并調(diào)試運行。二、實驗內(nèi)容隨機(jī)產(chǎn)生20個整數(shù)，組成一個順序表（或有序表，或二叉排序樹）。從鍵盤輸入一個整數(shù)x，進(jìn)行順序查找、二分法查找和二叉排序樹查找。C語言源程序如下：#include<stdlib.h>#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))#defineMAXSIZE20#defineSUCCESS1#defineFAILED-1typedefintKeyType;typedefstruct{KeyTypekey;}RcdType;/*元素類型*/typedefstruct{RcdTyper[MAXSIZE+1];intlength;}SqList;/*順序表類型*/typedefstructnode_st{RcdTypedata;structnode_st*left,*right;}NODE;/*二叉排序樹結(jié)點類型*/intSearch(SqList*L,KeyTypekey);intBinarySearch(SqList*L,KeyTypekey);voidInitList(SqList*L);voidWriteList(SqList*L);voidInsertSort(SqList*L);NODE*FindNode(NODE*tree,KeyTypekey);NODE*FindNodeWithInsert(NODE**tree,KeyTypekey);voidCreatBinarySortTree(NODE**tree,SqList*L);main(){inti,x;SqListL;NODE*tree,*found;InitList(&L);CreatBinarySortTree(&tree,&L);printf("\n數(shù)據(jù)序列:\n");WriteList(&L);printf("輸入一個整數(shù)：");scanf("%d",&x);i=Search(&L,x);printf("順序查找結(jié)果：");if(i==FAILED)printf("查找的數(shù)%d不存在!\n",x);elseprintf("查找的數(shù)%d是第%d個數(shù)!\n",x,i);printf("\n\n有序表序列:\n");InsertSort(&L);WriteList(&L);printf("輸入一個整數(shù)：");scanf("%d",&x);i=BinarySearch(&L,x);printf("二分查找結(jié)果：");if(i==FAILED)printf("查找的數(shù)%d不存在!\n",x);elseprintf("查找的數(shù)%d是第%d個數(shù)!\n",x,i);found=FindNode(tree,x);printf("\n二叉排序樹查找結(jié)果：");if(found==NULL)printf("查找的數(shù)%d不存在!\n",x);elseprintf("查找的數(shù)%d存在，其地址是%x\n",x,found);getch();}intSearch(SqList*L,KeyTypekey)/*順序查找*/{inti;for(i=1;i<=L->length;i++)if(L->r[i].key==key)returni;returnFAILED;}intBinarySearch(SqList*L,KeyTypekey)/*二分查找*/{intlow,high,mid;low=1;high=L->length;while(low<=high){mid=(low+high)/2;if(L->r[mid].key==key)returnmid;if(L->r[mid].key<key)low=mid+1;elsehigh=mid-1;}returnFAILED;}NODE*FindNode(NODE*tree,KeyTypekey){NODE*tmp=tree;while(tmp!=NULL){if(tmp->data.key==key)returntmp;if(tmp->data.key>key)tmp=tmp->left;elsetmp=tmp->right;}returnNULL;}NODE*FindNodeWithInsert(NODE**tree,KeyTypekey)/*二叉排序樹查找并插入*/{NODE*tmp,*pre;tmp=pre=*tree;while(tmp!=NULL){if(tmp->data.key==key)returntmp;pre=tmp;if(tmp->data.key>key)tmp=tmp->left;elsetmp=tmp->right;}tmp=(NODE*)malloc(sizeof(NODE));tmp->data.key=key;tmp->left=tmp->right=NULL;if(*tree==NULL)*tree=tmp;elseif(pre->data.key>key)pre->left=tmp;elsepre->right=tmp;returnNULL;}voidCreatBinarySortTree(NODE**tree,SqList*L)/*建立二叉排序樹*/{inti;*tree=NULL;for(i=1;i<=L->length;i++)FindNodeWithInsert(tree,L->r[i].key);}voidInitList(SqList*L)/*初始化*L*/{inti;randomize();for(i=1;i<=MAXSIZE;++i)L->r[i].key=(KeyType)random(100);L->length=MAXSIZE;}voidWriteList(SqList*L)/*輸出順序表*L*/{inti;for(i=1;i<=L->length;++i)printf("%3d",L->r[i].key);printf("\n");}voidInsertSort(SqList*L)/*直接插入排序*/{inti,j;for(i=2;i<=(*L).length;++i)if(LT((*L).r[i].key,(*L).r[i-1].key)){(*L).r[0]=(*L).r[i];for(j=i-1;LT((*L).r[0].key,(*L).r[j].key);--j)(*L).r[j+1]=(*L).r[j];(*L).r[j+1]=(*L).r[0];}}三、思考題1．分析二分查找的查找過程。2．畫出程序運行時20個隨機(jī)數(shù)組成的二叉排序樹。3．設(shè)計算法，對本實驗中的二叉排序樹進(jìn)行中序遍歷。

實驗五排序一、目的與要求熟悉排序的概念和常用排序方法，設(shè)計相關(guān)的排序程序。本實驗給出了直接插入排序、希爾排序、快速排序、堆排序、歸并排序程序，請仔細(xì)閱讀并調(diào)試運行。二、實驗內(nèi)容隨機(jī)產(chǎn)生20個整數(shù)，組成一個順序表，對其進(jìn)行直接插入排序、希爾排序、快速排序、堆排序、歸并排序。C語言源程序如下：#include<stdlib.h>#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))#defineMAXINT32767#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;}RcdType;/*定義記錄類型*/typedefstruct{RcdTyper[MAXSIZE+1];intlength;}SqList;/*定義順序表類型*/voidInitList(SqList*L)/*初始化順序表*L*/{inti;randomize();for(i=1;i<=MAXSIZE;++i)L->r[i].key=(KeyType)random(100);L->length=MAXSIZE;}voidWriteList(SqList*L)/*輸出順序表*L*/{inti;for(i=1;i<=L->length;++i)printf("%3d",L->r[i].key);printf("\n");}voidInsertSort(SqList*L)/*直接插入排序*/{inti,j;for(i=2;i<=(*L).length;++i)if(LT((*L).r[i].key,(*L).r[i-1].key)){(*L).r[0]=(*L).r[i];for(j=i-1;LT((*L).r[0].key,(*L).r[j].key);--j) (*L).r[j+1]=(*L).r[j];(*L).r[j+1]=(*L).r[0];}}voidShellInsert(SqList*L,intdk)/*希爾排序*/{/*對順序表*L作一趟希爾排序*/inti,j;for(i=dk+1;i<=(*L).length;++i)if(LT((*L).r[i].key,(*L).r[i-dk].key)){(*L).r[0]=(*L).r[i];for(j=i-dk;j>0&<((*L).r[0].key,(*L).r[j].key);j-=dk) (*L).r[j+dk]=(*L).r[j];(*L).r[j+dk]=(*L).r[0];}}voidShellSort(SqList*L,intdlta[],intt){/*按增量序列dlta[0..t-1]對*L作希爾排序*/intk;for(k=0;k<t;++k)ShellInsert(L,dlta[k]);}intPartition(SqList*L,intlow,inthigh)/*快速排序*/{/*對*L[low..high]作一趟快速排序,返回樞軸位置*/KeyTypepivotkey;L->r[0]=L->r[low];pivotkey=L->r[low].key;while(low<high){while(low<high&&LQ(pivotkey,L->r[high].key))--high;L->r[low]=L->r[high];while(low<high&&LQ(L->r[low].key,pivotkey))++low;L->r[high]=L->r[low];}L->r[low]=L->r[0];returnlow;}voidQSort(SqList*L,intlow,inthigh){/*對*L[low..high]快速排序*/intpivotloc;if(low<high){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}voidQuickSort(SqList*L){/*對*L作快速排序*/QSort(L,1,L->length);}void