數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、!-實(shí)驗(yàn)一：約瑟夫問(wèn)題1、實(shí)驗(yàn)?zāi)康?)2)2、實(shí)驗(yàn)環(huán)境(硬/軟件要求):掌握用VC6.0上機(jī)調(diào)試線性表的基本方法，掌握線性表的基本操作，如插入、刪除、檢索等在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的運(yùn)算。Win dows XP + VC6.03、實(shí)驗(yàn)內(nèi)容約瑟夫問(wèn)題的一種描述是：編號(hào)為1, 2,n的n個(gè)人按順時(shí)針?lè)较驀?圈，先從某個(gè)人從1開始報(bào)數(shù)，報(bào)到m的人出列，接著從出列的下一個(gè)人開始 重新從1報(bào)數(shù)，數(shù)到m的人又出列，如此下去，直到所有人全部都出列為止。 試設(shè)計(jì)一個(gè)程序，求出出列順序。4、實(shí)驗(yàn)設(shè)計(jì)思想在實(shí)踐約瑟夫問(wèn)題時(shí)的關(guān)鍵是用兩個(gè)指針把一個(gè)移動(dòng)的，一個(gè)指向要?jiǎng)h除的節(jié) 點(diǎn)，另外要注意保留頭指針。第一步是建立一個(gè)循

2、環(huán)的單向鏈表。第二步是運(yùn)用 指針遍歷鏈表同時(shí)計(jì)數(shù)到第m個(gè)時(shí)將其刪除。此時(shí)指針指向不變。其格式如下：out put(struct Jose ph *head)輸出出列情況int i,j=1;struct Jose ph *p 1,* p2;p1= p2=head;/p1、p2都指向頭指針for(i=1;i<m;i+)p1= p1->next;從第M個(gè)人開始報(bào)數(shù)，所以p1指針依次后移，指向第 m個(gè)人while( n>0)for(i=1;i<s;i+)p2=p1；開始報(bào)數(shù) 報(bào)到s前p1 p2依次后移p1=p1->n ext; printf("第%d 個(gè)出列的人

3、是：dn",j,p1->num);p2->n ext=p1->n ext;p1= p2->next; 此人出列，將p1->next賦給p2->next,將p1所指向的結(jié)點(diǎn)刪掉 n-;/人數(shù)減少1j+;/出列人數(shù)加15、程序清單/ 定義 joseph/* 運(yùn)行環(huán)境 VC*/ #include <stdio.h> #include<stdlib.h> #include <malloc.h> #define LEN sizeof(struct Joseph) struct Joseph int num; struct

4、Joseph *next; int n,s,m; print(struct Joseph *head) /打印鏈對(duì)中的信息 struct Joseph *p; /p 指針 p=head; / 將 p 指向頭指針 printf("%d 個(gè)人的代號(hào)如下 :n",n);do printf("%d ",p->num); p=p->next;while(p!=head);/依次輸入每個(gè)人的代號(hào)printf("n");/p1 p2 都指向頭指針 output(struct Joseph *head) /輸/ 出出列情況 int i,j

5、=1; struct Joseph *p1,*p2; p1=p2=head;for(i=1;i<m;i+)p1= p1->next;從第M個(gè)人開始報(bào)數(shù)，所以p1指針依次后移，指向第 m個(gè)人while(n>0) for(i=1;i<s;i+) p2=p1;/開始報(bào)數(shù)，報(bào)到 s 前 p1、p2 依次后移p1=p1->next;printf("第%d 個(gè)出列的人是：dn",j,p1->num); p2->next=p1->next;p1= p2->next; 此人出列，將p1->next賦給p2->next,將p1

6、所指向的結(jié)點(diǎn)刪掉 n-;/人數(shù)減少 1j+;/ 出列人數(shù)加 1 struct Joseph *create() /建/ 立鏈隊(duì)列 int i;struct Joseph *head;struct Joseph *p1,*p2;printf("請(qǐng)輸入總?cè)藬?shù)(輸入0退出程序):n"); scanf("%d",&n);if(n=0)exit(0);/ 退出for(i=1;i<=n;i+) p1=(struct Joseph*)malloc(LEN); p1->num=i;if(i=1)head=p1;else p2->next=p1;

7、p2=p1;p2->next=head; /將整個(gè)鏈隊(duì)構(gòu)成一個(gè)環(huán)形 print(head);printf(" 請(qǐng)輸入從第幾個(gè)人開始報(bào)數(shù) :n"); scanf("%d",&m);printf(" 數(shù)到第幾個(gè)人出列 :n"); scanf("%d",&s);return head;main() struct Joseph *head;while(1)head=create(); output(head); system("pause"); system("cls&q

8、uot;);6、實(shí)驗(yàn)心得在約瑟夫問(wèn)題中， 著重訓(xùn)練的是鏈表的應(yīng)用， 尤其是鏈表中結(jié)點(diǎn)的刪除、 檢 索等。由于單向鏈表等線性表的操作基本思想是一致的， 因此通過(guò)對(duì)單向鏈表的 練習(xí)來(lái)加深對(duì)線性表的理解。在本實(shí)驗(yàn)中， 需要解決的問(wèn)題的重點(diǎn)是怎樣找到要?jiǎng)h除的結(jié)點(diǎn)。 因此，我首 先考慮解決這個(gè)問(wèn)題，即應(yīng)用循環(huán)語(yǔ)句來(lái)找到滿足條件的結(jié)點(diǎn)，我選用了 if 循 環(huán)語(yǔ)句。然后應(yīng)用指針實(shí)現(xiàn)查找過(guò)程。 在弄清出這些之后， 在建立一個(gè)單向鏈表 即形成程序。 在經(jīng)過(guò)調(diào)試改正一些細(xì)節(jié)即可。 在編輯的過(guò)程中， 將所學(xué)的知識(shí)充 分應(yīng)用于實(shí)踐， 雖然遇到了一些問(wèn)題， 比如說(shuō)不知從何下手， 不過(guò)通過(guò)仔細(xì)考慮 找出問(wèn)題的關(guān)鍵和參考資

9、料并逐步編輯出程序。 從而注意到了一些細(xì)節(jié)問(wèn)題， 例 如：頭指針的問(wèn)題、 *p1,*p2 之間在不同的函數(shù)中不同的關(guān)系的區(qū)分以及函數(shù)位 置的前后和聲明的關(guān)系等等。 這些只有在真的去實(shí)踐時(shí)才能意識(shí)到的小問(wèn)題給我 帶來(lái)了很大的困惑。這次的實(shí)驗(yàn)讓我重新熟悉了 C+的編輯環(huán)境，為以后的實(shí)驗(yàn)奠定了基礎(chǔ)。實(shí)驗(yàn)?zāi)康?掌握隊(duì)列的定義； 掌握隊(duì)列基本操作的實(shí)現(xiàn)，并能用于解決實(shí)際問(wèn)題。實(shí)驗(yàn)內(nèi)容編寫一個(gè)程序 ,反映病人到醫(yī)院看病排隊(duì)等醫(yī)生的過(guò)程 .在病人排除過(guò)程中 ,主要病人看病模擬程序1、1)2)2、 重復(fù)兩件事 :A:病人到達(dá)診室，將病歷本交給護(hù)士，排到等待隊(duì)列中候診.B:護(hù)士從等待隊(duì)列中取出下一位病人的病歷，

10、該病人進(jìn)入診室就診 要求模擬病人等待就診這一過(guò)程 ,程序采用菜單方式 ,其選項(xiàng)及功能說(shuō)明如下 :(a) 排隊(duì)：輸入排隊(duì)病人的病歷號(hào)，加入病人排隊(duì)隊(duì)列中(b) 就診：病人排隊(duì)隊(duì)列中最前面的病人就診，并將其從隊(duì)列中刪除(C)查看排隊(duì):從隊(duì)首到隊(duì)尾列出所有的排隊(duì)病人的病歷號(hào)(d)下班：退出運(yùn)行3、實(shí)驗(yàn)環(huán)境MiCrosoft Visual C+ 6.04、實(shí)驗(yàn)設(shè)計(jì)思想病人看病， 需要進(jìn)行插入和出隊(duì)程序。 這與隊(duì)列的操作順序完全相同， 具有先進(jìn) 先出的順序， 只在對(duì)頭進(jìn)進(jìn)行輸出在對(duì)尾進(jìn)行插入操作， 故此問(wèn)題可以用隊(duì)列這 種特殊的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。 在具體的實(shí)現(xiàn)過(guò)程中需要進(jìn)行數(shù)據(jù)的插入即病人入隊(duì)操 作。在程序

11、中實(shí)現(xiàn)數(shù)據(jù)的輸出處理即病人就診過(guò)程。 其中還需設(shè)置一個(gè)實(shí)現(xiàn)對(duì)隊(duì) 列中數(shù)據(jù)的遍歷操作函數(shù)以及一個(gè)退出函數(shù)即查看和下班。在設(shè)計(jì)時(shí)，首先應(yīng)對(duì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的對(duì)頭指針進(jìn)行定義， 其具體格式 為:typedef struCt qnode int data;struCt qnode *next;/鏈隊(duì)結(jié)點(diǎn)類型 qnode;typedef struCtqnode *front,*rear;/鏈隊(duì)類型 qutype;再次，通過(guò)四個(gè)函數(shù)實(shí)現(xiàn)具體的操作，其定義格式如下: paidu(qutype *q );jiuzhen(qutype *q);Chakan(qutype *q); xiaban(qutyp

12、e *q);5、程序源代碼及解釋#include <iostream.h>#include <stdli> #include <malloc.h> #define null 0typedef struct node int data;struct node *next; /連隊(duì)節(jié)點(diǎn)定義Qnode, *Queuepre;typedef struct Qnode *front,*rearLQueue;/將對(duì)頭指針和隊(duì)尾指針定義為一個(gè)結(jié)構(gòu)體void paidui(LQueue *Q) / 實(shí)現(xiàn)數(shù)據(jù)節(jié)點(diǎn)的插入函數(shù) Qnode *p;int num,m;cout<

13、;<" 輸入看病總?cè)藬?shù)： " cin>>m;for(int i=0;i<m;i+) /用循環(huán)語(yǔ)句實(shí)現(xiàn)一次插入多個(gè)節(jié)點(diǎn) cout<<" 輸入病例號(hào) :"cin>>num;p=(Queue pre)malloc(sizeof(Q node);/malloc(函 數(shù)生成一個(gè)新節(jié)點(diǎn) p->data=num;p->next=null;/Q->rear- >n ext=p;Q->rear二 p;/將節(jié)點(diǎn)插入到隊(duì)列中void jiuzhe n(LQueue & Q)/ 出隊(duì)函數(shù)的實(shí)現(xiàn)

14、 Queuepre q;int m;q=Q.fro nt-> next;/取出對(duì)頭節(jié)點(diǎn)的值m=q->data;if(q=Q->rear)/判斷隊(duì)列中是否已經(jīng)只有一個(gè)節(jié)點(diǎn)剩余coutvvmvv"號(hào)病人就診，已沒(méi)有病人就診!"else /若還有多個(gè)節(jié)點(diǎn)直接輸出數(shù)據(jù)元素coutvvmvv"號(hào)病人就診"<<endl;Q->front->next=q->next;free(q);void chakan(LQueue *Q) Queuepre p;H.coutvv"還未看病的病人：p=Q->front-

15、>next;coutvv p->datavv't'/輸出對(duì)頭元素 dop=p->next;coutvvp->datavv't'while(p->next!=null);/ 判斷隊(duì)列中的節(jié)點(diǎn)個(gè)數(shù)并實(shí)現(xiàn)指針的后移以逐個(gè)輸出其 值void xiaban(LQueue *Q)while(Q->front)Q->rear=Q->front->next;free(Q->front);Q->front=Q->rear;/ 摧毀整個(gè)隊(duì)列即下班操作的實(shí)現(xiàn)void main()int sel,flag=1; /

16、定義一個(gè)選擇字符和一個(gè)標(biāo)志符LQueue *qu;Queuepre p; qu=(LQueue *)malloc(sizeof(LQueue); p=(Queuepre)malloc(sizeof(Qnode); /* 創(chuàng)建空隊(duì) */ qu->front=qu->rear=p;p->next=null;free(p);while(flag=1) /實(shí)現(xiàn)入隊(duì)，出隊(duì)，查看的多次操作coutvv"1.排隊(duì)2.就診 3.查看排隊(duì) 4.下班n"printf("Please select:");cin>>sel;switch(sel)c

17、ase 1: paidui(qu); break;case 2:jiuzhen(qu); break;case 3: chakan(qu);break;case 4: xiaban(qu);flag=0; break; /執(zhí)行此語(yǔ)句是改變標(biāo)志符，一跳出本循環(huán) 6、實(shí)驗(yàn)心得本實(shí)驗(yàn)中應(yīng)用的主要是隊(duì)列的知識(shí)， 重點(diǎn)是結(jié)點(diǎn)的插入。 在主函數(shù)中創(chuàng)建一 個(gè)菜單，使得進(jìn)行操作的選擇運(yùn)用 switch 語(yǔ)句，此為復(fù)習(xí)上學(xué)期所學(xué)內(nèi)容。在實(shí)踐本實(shí)驗(yàn)的過(guò)程中， 我沒(méi)有遇到太大的問(wèn)題， 這得益于第一個(gè)實(shí)驗(yàn)。 本 實(shí)驗(yàn)與第一個(gè)實(shí)驗(yàn)的基本思想是一致的， 不同的是表達(dá)方式。 在進(jìn)行隊(duì)列的遍歷， 即查看排隊(duì)時(shí)，我開始并不是很

18、明白它的意圖， 但經(jīng)過(guò)參考資料， 終于發(fā)現(xiàn)原來(lái) 是要清點(diǎn)人數(shù)，判斷隊(duì)列是否為空。通過(guò)本實(shí)驗(yàn)的學(xué)習(xí)，使我進(jìn)一步認(rèn)識(shí)到了棧與隊(duì)列的區(qū)別， 棧是“先進(jìn)后出”， 隊(duì)列是“先進(jìn)先出”，根據(jù)病人看病的特點(diǎn)，只能選擇運(yùn)用隊(duì)列而不能運(yùn)用棧。 在編輯程序時(shí)，運(yùn)用了建立空對(duì)、隊(duì)列初始化、入隊(duì)和出隊(duì)等隊(duì)列的基本知識(shí)， 使得我在課堂上所學(xué)得到了充分的應(yīng)用， 并進(jìn)一步熟悉了隊(duì)列的基礎(chǔ)知識(shí)。 同時(shí)， 也使我發(fā)現(xiàn)要認(rèn)真觀察， 只有充分理解了現(xiàn)實(shí)生活中的遇到的事情才能透徹的分 析問(wèn)題，提出解決問(wèn)題的辦法。叉樹的建立與遍歷1、實(shí)驗(yàn)?zāi)康?：1)2)3)掌握二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)； 掌握利用二叉樹的先序遍歷方法創(chuàng)建一個(gè)二叉樹；

19、掌握二叉樹的先序、中序、后序遍歷的遞歸實(shí)現(xiàn)方法；2、實(shí)驗(yàn)環(huán)境(硬 /軟件要求)：Windows XP + VC6.03、實(shí)驗(yàn)內(nèi)容：按先序次序輸入二叉樹中結(jié)點(diǎn)的值， (用 *'表示空)，構(gòu)造一棵二叉樹；以遞 歸算法實(shí)現(xiàn)二叉樹的先序、中序、后序遍歷。 注：采用二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)。4、實(shí)驗(yàn)要求：1)2)ino rder, preorder, postorde。5、實(shí)驗(yàn)設(shè)計(jì)思想編寫創(chuàng)建二叉樹的函數(shù)，函數(shù)名 : createbitree。 編寫遞歸實(shí)現(xiàn)二叉樹的中序、先序和后序遍歷算法。函數(shù)名分別為：在本實(shí)驗(yàn)中需要建立一個(gè)二叉樹和三個(gè)遍歷函數(shù)， 其中遍歷函數(shù)需要用遞歸的算 法，三個(gè)遍歷函

20、數(shù)基本一致。其格式為：void Preorder(BiTree T)/先序遍歷函數(shù)if(T)printf("%c",T->data);Preorder(T->lchild);Preorder(T->rchild); /遞歸在建立二叉樹時(shí)，要注意用二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)。其格式為：typedef struct createbitreechar data;struct createbitree *lchild,*rchild; createbitree,*BiTree;6、實(shí)驗(yàn)清單#include <stdio.h>#include <

21、string.h>#define NULL 0typedef struct createbitree char data;struct createbitree *lchild,*rchild; createbitree,*BiTree;BiTree Create(BiTree T) /樹的建立函數(shù) char ch;ch=getchar(); if(ch='*') T=NULL;/輸入 * 則為空elseif(!(T=( createbitree *)malloc(sizeof(createbitree) printf("Error!");T->

22、data=ch; /生成根結(jié)點(diǎn) T->lchild=Create(T->lchild); /生成左子樹 T->rchild=Create(T->rchild); /生成右子樹 return T;/遞歸void Preorder(BiTree T) /先序遍歷函數(shù) if(T) printf("%c",T->data); Preorder(T->lchild); Preorder(T->rchild); void inorder(BiTree T) /中序遍歷函數(shù) if(T) inorder(T->lchild); printf(

23、"%c",T->data);inorder(T->rchild); /遞歸 void postorder(BiTree T) /后序遍歷函數(shù) if(T) postorder(T->lchild);postorder(T->rchild); /遞歸 printf("%c",T->data); main()/主函數(shù)BiTree T; T=Create(T); Preorder(T); printf("n"); inorder(T); printf("n"); postorder(T);7、

24、實(shí)驗(yàn)心得本實(shí)驗(yàn)是這四個(gè)實(shí)驗(yàn)中最簡(jiǎn)單的一個(gè)實(shí)驗(yàn)， 包含的內(nèi)容并不多， 主要就是二 叉樹的建立及三種遍歷方式， 而三種遍歷方式基本一致因此比較簡(jiǎn)單。 我所不熟 悉的是怎樣用二叉鏈來(lái)作為二叉樹的存儲(chǔ)結(jié)構(gòu)。 經(jīng)過(guò)翻看老師的課件， 終于將順 序存儲(chǔ)結(jié)構(gòu)、二叉鏈存儲(chǔ)結(jié)構(gòu)和三叉鏈表存儲(chǔ)結(jié)構(gòu)之間的不同弄清楚， 不再混淆。 雖然思考起來(lái)內(nèi)容不多，但是由于能力水平有限， 有些東西還是不能很好的實(shí)現(xiàn)。通過(guò)本實(shí)驗(yàn)的練習(xí)，能夠?qū)Χ鏄涞闹饕獌?nèi)容作一個(gè)比較深入的理解和記 憶，同時(shí)掌握樹中非常重要的一中樹型結(jié)構(gòu)。 二叉樹中最重要的為三種遍歷， 而 且運(yùn)用的遞歸比較多。 遞歸的使用時(shí)要注意，初始時(shí)的狀態(tài)以及如何使用遞歸， 注

25、意普遍性，思考時(shí)可以從普通的開始。數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)要達(dá)到的目的方法是有很多種的， 只有深入才會(huì)發(fā)現(xiàn)有很多 的寫法和其他程序達(dá)到的目的是一樣的， 一個(gè)實(shí)驗(yàn)肯定會(huì)經(jīng)過(guò)多次運(yùn)行， 多次糾 正錯(cuò)誤，只有不斷的改正才能真正的體會(huì)出它的意義。 對(duì)于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)多半 靠在實(shí)踐中摸索。內(nèi)部排序?qū)嶒?yàn)?zāi)康模荷羁汤斫馀判虻亩x和各種排序方法的特點(diǎn)、并能靈活應(yīng)用。 掌握常用的排序方法，并掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法。 了解各種方法的排序過(guò)程及依據(jù)的原則，掌握各種排序方法的性能1、1)2)4、的分3) 析方法。2 、實(shí)驗(yàn)環(huán)境(硬 /軟件要求) ： Windows XP +VC+6.03 、實(shí)驗(yàn)內(nèi)容：1、對(duì)于給定的某

26、無(wú)序序列，分別用直接插入排序、快速排序、希爾排序、簡(jiǎn)單 選擇排序、等方法進(jìn)行排序，并輸出每種排序下的各趟排序結(jié)果。4 、實(shí)驗(yàn)要求：1 、輸入的無(wú)序序列為： 26 5 37 1 6111 59 15 48 192、出要求：對(duì)每種算法均需輸出原始數(shù)據(jù)序列、每趟排序的中間結(jié)果序列和最 后排好序的有序序列。3、實(shí)驗(yàn)中要求應(yīng)用四種方法進(jìn)行排序， 其中包括直接插入排序、 簡(jiǎn)單選擇排序、 快速排序和希爾排序。 能靈活應(yīng)用幾種不同的方法進(jìn)行計(jì)算機(jī)內(nèi)部排序， 了解其 中的排序原理，并能根據(jù)具體情況選擇最優(yōu)的方法排序。宏定義 用LS (a,b)、LL (a,b)替換a與b之間的 /比較，以簡(jiǎn)化代碼/自定義數(shù)據(jù)結(jié)構(gòu)

27、5 、程序源代碼及解釋 #include <iostream.h> #define LS(a,b) (a)<(b) #define LL(a,b) (a)>(b) #define MAXSIZE 50 typedef int KeyType; typedef struct int key; RedType; typedef struct RedType rMAXSIZE+1;/定義一個(gè) RedType類型多大數(shù)組int length;SqList;typedef SqList HeapType;int change=0;/用以記錄在具體的排列中交換的次數(shù)* 建立排序數(shù)組

28、 * int Create_Sq(SqList &L) int i,k,n;coutvv"請(qǐng)輸所需排序的個(gè)數(shù)："； cin>>k;L.length=k; for(i=1;i<=k;+i)/次循環(huán)用以數(shù)組中數(shù)據(jù)元素的輸入coutvv"請(qǐng)輸入第"vvivv"個(gè)數(shù)：" cin>>n;L.ri.key=n;return 1;* 直接插入排序 *void InsertSort(SqList &L) int i,j; coutvvendl;for(i=2;iv=L.length;+i)if(LS(L.

29、ri.key,L.ri-1.key) /第i個(gè)與第i-1個(gè)數(shù)進(jìn)行比較若后面的一個(gè)比/前面的一個(gè)小 則進(jìn)行一下操作/記錄調(diào)換的次數(shù)/哨兵記錄的 i 個(gè)數(shù)并與前面一個(gè)輸調(diào)換+change;L.r0=L.ri;L.ri=L.ri-1;for(j=i-2;LS(L.r0.key,L.rj.key);-j)/第 i 個(gè)數(shù)與前面 I -2 個(gè)數(shù)比/較并調(diào)換L.rj+1=L.rj;L.rj+1=L.r0;H.coutvv"經(jīng)"vvcha ngevv"次調(diào)換以后的序列為:/輸出中間調(diào)換的過(guò)程for(j=1;jv=L.length;j+) coutvv" "vv

30、L.rj.key;coutvvendl;coutvv"最終結(jié)果："<<e ndl;for(i=1;i<=L.length;i+)coutvv" "vvL.ri.key;coutvvendl;change=0;/ 簡(jiǎn)單選擇排序 / void SelectSort(SqList &L)int l,i,j;coutvvendl;for(i=1;i<L.length;+i)L.r0=L.ri;j=i+1;for(j;jv=L.length;+j)前面i-1個(gè)已經(jīng)有序地i個(gè)與后面的比較找/出其中最小的與地 i 個(gè)交換if(LL(L.

31、r0.key,L.rj.key) /第 i 個(gè)比地 j 個(gè)大需調(diào)換 l=j;L.r0=L.rj; if(l!=i)/ 若 i 不是后面書中最小的需調(diào)換+change;L.rl=L.ri;L.ri=L.r0;coutvv"經(jīng)"<<cha ngew"次調(diào)換以后的序列為：" for(j=1;j<=L.length;j+) coutvv" "vvL.rj.key; coutvvendl;/ 輸出中間過(guò)程coutvv"最終結(jié)果："<<e ndl;for(i=1;i<=L.length;i+

32、) cout<<" "<<L.ri.key;cout<<endl;change=0;* 快速排序 *int Partition(SqList &L,int low,int high)交換順序表L中子表Llow -igh的記錄使樞軸記錄到位，并返回其所在位置/此時(shí)它之前(后)的記錄均不小 ( 大)與它int pivotkey;L.r0=L.rlow; pivotkey=L.rlow.key;while(low<high)/用第一個(gè)作為樞軸記錄/從表的兩邊交替的向中間掃描while(low<high&&L.

33、rhigh.key>=pivotkey)-high;+change;L.rlow=L.rhigh;/ 將比樞軸小的交換到低端coutvv"經(jīng)第"vvcha ngew"次調(diào)換以后的序列為：for(int j=1;j<=L.length;j+)cout<<" "<<L.rj.key;cout<<endl;while(low<high&&L.rlow.key<=pivotkey)H.+low;+change;L.rhigh=L.rlow;/將比樞軸大的交換到高端coutvv&

34、quot;經(jīng)第"vvchangew"次調(diào)換以后的序列為："for(j=1;j<=L.length;j+)coutvv" "vvL.rj.key;coutvvendl;L.rlow=L.r0; return low;/ 返回樞軸的位置void QSort(SqList &L,int low,int high) int pivotloc;if(low<high)pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);/將 Llow-high 一分為二/ 對(duì)低端表遞歸排序， p

35、ivotloc 是樞軸的位置QSort(L,pivotloc+1,high);/ 對(duì)高端表進(jìn)行遞歸排序 / 希爾排序 / void ShellInsert(SqList &L,int dk) /對(duì)順序表進(jìn)行一次希爾排序 增量為 dk int i;int j;for(i=dk+1;iv=L.length;+i)if(LS(L.ri.key,L.ri-dk.key)/ 需將 L.rI 插入到有序增量子表L.r0=L.ri;/ 暫存入到 Lrifor(j=i-dk;j>0&&LS(L.r0.key,L.rj.key);j-=dk)+change;/ 記錄后移 查找插入的

36、位置L.rj+dk=L.rj;L.rj+dk=L.r0;/插入Hcoutvv"依次調(diào)換以后的序列: for(j=1;j<=L.length;j+) cout<<" "<<L.rj.key; cout<<endl;void ShellSort(SqList &L,int dlta)增量序列為dkoj-1對(duì)序列L作希爾排序int k,j=L.length/2,t=0;while(j>=0)+t;/計(jì)算dlta中應(yīng)出入的數(shù)的個(gè)數(shù)j-=2；j=L.length/2; for(k=0;k<t;+k) if(j=0

37、)j=1；/最后一趟排序的增量dltak=j;j-=2;for(k=0;k<t;+k)ShellInsert(L,dltak);coutvv"最終結(jié)果："<<e ndl;for(k=1;k<=L.length;k+) coutvv" "vvL.rk.key;coutvvendl;change=0;void main()int i;int dltaMAXSIZE;SqList L;Create_Sq(L);cout<<" 待排序序列為 "<<endl;for(i=1;i<=L.length;i+) cout<<" "<<L.ri.key; cout<<endl;"<<endl;cout<<"1. 直接插入排序 SqList L1=L;InsertSort(L1);"<<endl;cout<<"2. 簡(jiǎn)單選擇排序 SqList L2=L; SelectSort(L2);"<<endl;cout<<"3. 快速排序SqList L3=L;QuickSo