查找排序?qū)嶒?yàn)報(bào)告

1、編程實(shí)訓(xùn)實(shí)驗(yàn)報(bào)告書專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)：151班 學(xué) 號(hào)： 姓 名： 指導(dǎo)教師： 日 期：2016年6月30日 目錄一、需求分析31.任務(wù)要求32.軟件功能分析33.數(shù)據(jù)準(zhǔn)備3二、概要設(shè)計(jì)31.功能模塊圖42.模塊間調(diào)用關(guān)系43.主程序模塊54.抽象數(shù)據(jù)類型描述5三、詳細(xì)設(shè)計(jì)61.存儲(chǔ)結(jié)構(gòu)定義62.各功能模塊的詳細(xì)設(shè)計(jì)7四、實(shí)現(xiàn)和調(diào)試71.主要的算法72.主要問題及解決83.測(cè)試執(zhí)行及結(jié)果8五、改進(jìn)9六、附錄91.查找源程序92.排序源程序9 目錄1 需求分析   1.1 任務(wù)要求 對(duì)于從鍵盤隨機(jī)輸入的一個(gè)序列的數(shù)據(jù)，存入

2、計(jì)算機(jī)內(nèi)，給出各種查找算法的實(shí)現(xiàn)；以及各種排序算法的實(shí)現(xiàn)。1.2 軟件功能分析任意輸入n個(gè)正整數(shù)，該程序可以實(shí)現(xiàn)各類查找及排序的功能并將結(jié)果輸出。1.3 數(shù)據(jù)準(zhǔn)備任意輸入了5個(gè)正整數(shù)如下：12 23 45 56 782 概要設(shè)計(jì)（如果2，3合并可以省略2.4）   2.1 功能模塊圖（注：含功能說明）2.2 模塊間調(diào)用關(guān)系   2.3 主程序模塊 2.4 抽象數(shù)據(jù)類型描述存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（也稱映像）叫做物理結(jié)構(gòu)。又稱為存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)類型（

3、data type）是一個(gè)“值”的集合和定義在此集合上的一組操作的總稱。3 詳細(xì)設(shè)計(jì)3.1 存儲(chǔ)結(jié)構(gòu)定義查找：typedef int ElemType ;/順序存儲(chǔ)結(jié)構(gòu)typedef structElemType *elem; /數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)按實(shí)際長(zhǎng)度分配，號(hào)單元留空int length; /表的長(zhǎng)度SSTable;排序：typedef struct /定義記錄類型int key; /關(guān)鍵字項(xiàng)RecType;typedef RecType SeqListMax+1; /SeqList為順序表，表中第0個(gè)元素作為哨兵3.2 各功能模塊的詳細(xì)設(shè)計(jì)查找：

4、void Create(SSTable *table, int length);/ 構(gòu)建順序表void FillTable(SSTable *table) / 無序表的輸入int Search_Seq(SSTable *table, ElemType key);/哨兵查找算法void Sort(SSTable *table ) / 排序算法int Search_Bin(SSTable *table, ElemType key) / 二分法查找（非遞歸）排序：void InsertSort(SeqList R) /對(duì)順序表R中的記錄R1n按遞增序進(jìn)行插入排序void BubbleSort(Seq

5、List R) /自下向上掃描對(duì)R做冒泡排序int Partition(SeqList R,int i,int j)/對(duì)Rij做一次劃分，并返回基準(zhǔn)記錄的位置void QuickSort(SeqList R,int low,int high) /Rlow.high快速排序void SelectSort(SeqList R) /直接選擇排序void Heapify(SeqList R,int low,int high) /大根堆調(diào)整函數(shù)void MergePass(SeqList R,int length) /歸并排序4 實(shí)現(xiàn)和調(diào)試4.1 主要的算法查找：建立順序存儲(chǔ)結(jié)構(gòu)，構(gòu)

6、建一個(gè)順序表，實(shí)現(xiàn)順序查找算法。 typedef struct ElemType *elem; /數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)按實(shí)際長(zhǎng)度分配，號(hào)單元留空 int length; /表的長(zhǎng)度 SSTable; 對(duì)順序表先排序后，實(shí)現(xiàn)行二分法查找相關(guān)操作。 定義二叉樹節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)的值進(jìn)行查找，并且實(shí)現(xiàn)節(jié)點(diǎn)的插入，刪除等操作。 typedef struct BiTnode /定義二叉樹節(jié)點(diǎn) int data; /節(jié)點(diǎn)的值 struct BiTnode *lchild,*rchild; BiTnode,*BiTree; 定義哈希表以及要查找的節(jié)點(diǎn)元素，創(chuàng)建哈希表，實(shí)現(xiàn)其相關(guān)查找操作。 typedef

7、 struct int num; Elemtype; /定義查找的結(jié)點(diǎn)元素 typedef struct Elemtype *elem; /數(shù)據(jù)元素存儲(chǔ)基址 int count; /數(shù)據(jù)元素個(gè)數(shù) int sizeindex; HashTable;/定義哈希表排序：2. 排序相關(guān)實(shí)驗(yàn)內(nèi)容及步驟。 定義記錄類型。 typedef struct int key; /關(guān)鍵字項(xiàng) RecType; 實(shí)現(xiàn)直接插入排序：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已排序好的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。 實(shí)現(xiàn)冒泡排序：設(shè)想被排序的記錄數(shù)組R1n垂直排序。根據(jù)輕氣泡不能在重氣泡之下的原則，從

8、下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上“漂浮”（交換），如此反復(fù)進(jìn)行，直到最后任意兩個(gè)氣泡都是輕者在上，重者在下為止。 實(shí)現(xiàn)快速排序：在待排序的n個(gè)記錄中任取一個(gè)記錄（通常取第一個(gè)記錄），把該記錄作為支點(diǎn)（又稱基準(zhǔn)記錄）（pivot），將所有關(guān)鍵字比它小的記錄放置在它的位置之前，將所有關(guān)鍵字比它大的記錄放置在它的位置之后(稱之為一次劃分過程)。之后對(duì)所分的兩部分分別重復(fù)上述過程，直到每部分只有一個(gè)記錄為止。 實(shí)現(xiàn)直接選擇排序：第i趟排序開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為R1i-1和Rin（1in-1），該趟排序則是從當(dāng)前無序區(qū)中選擇出關(guān)鍵字最小的記錄Rk，將它與無序區(qū)的的第一個(gè)

9、記錄Ri交換，有序區(qū)增加一個(gè)記錄，使R1i,和Ri+1n分別為新的有序區(qū)和新的無序區(qū)。如此反復(fù)進(jìn)行，直到排序完畢。 實(shí)現(xiàn)堆排序：它是一種樹型選擇排序，特點(diǎn)是：在排序的過程中，將R1n看成是一個(gè)完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大（或最小）的記錄。即：把待排序文件的關(guān)鍵字存放在數(shù)組R1n子中，將R看成是一棵二叉樹，每個(gè)結(jié)點(diǎn)表示一個(gè)記錄，源文件的第一個(gè)記錄R1作為二叉樹的根，以下各記錄R2n依次逐層從左到右排列，構(gòu)成一棵完全二叉樹，任意結(jié)點(diǎn)Ri的左孩子是R2i，右孩子是R2i+1，雙親是Ri/2。 實(shí)現(xiàn)二路歸并排序：假設(shè)初始序列n

10、個(gè)記錄，則可看成是n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為2或1的有序子序列；再兩兩歸并，如此重復(fù)，直到一個(gè)長(zhǎng)度為n的有序序列為止。4.2 主要問題及解決在實(shí)驗(yàn)前對(duì)于各種查找和排序的算法不是很熟悉，所以花了一些時(shí)間去復(fù)習(xí)。有些代碼反復(fù)測(cè)試還是找不出錯(cuò)誤，最后也是翻閱了書本并仔細(xì)思考才改進(jìn)了算法并成功測(cè)試出了結(jié)果。這次試驗(yàn)大大提升了我對(duì)排序算法及查找算法的熟練程度。4.3 測(cè)試執(zhí)行及結(jié)果查找算法：任意輸入若干正整數(shù)并測(cè)試如下：排序算法：任意輸入數(shù)字并測(cè)試如下：5 改進(jìn)根據(jù)提示的代碼，經(jīng)過一系列調(diào)試后最終出了結(jié)果。在一開始運(yùn)行時(shí)總是出錯(cuò)

11、，特別是二叉樹的測(cè)試，代碼有些小錯(cuò)誤導(dǎo)致測(cè)試的時(shí)候程序總是出錯(cuò)。最后改動(dòng)了一下提高了程序的穩(wěn)定性并成功運(yùn)行出了結(jié)果。6 附錄【附錄1-查找源程序】#include"iostream"#include"stdlib.h"#include"stdio.h"#include "malloc.h"#define MAX 11 using namespace std;typedef int ElemType ;/順序存儲(chǔ)結(jié)構(gòu)typedef structElemType *elem; /數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)按實(shí)際長(zhǎng)度分

12、配，號(hào)單元留空int length; /表的長(zhǎng)度SSTable; void Create(SSTable *table, int length);void Destroy(SSTable *table);int Search_Seq(SSTable *table, ElemType key);void Traverse(SSTable *table, void (*visit)(ElemType elem);void Create(SSTable *table, int length) / 構(gòu)建順序表 SSTable *t = (SSTable*) malloc(sizeof(SSTable)

13、;/分配空間t->elem=(ElemType*)malloc(sizeof(ElemType)*(length+1);t->length=length;*table=t;void FillTable(SSTable *table) / 無序表的輸入ElemType *t=table->elem; for(int i=0; i<table->length; i+) /for循環(huán)，輸入各個(gè)元素t+;scanf("%d", t); /輸入元素getchar();void Destroy(SSTable *table) / 銷毀表 free(tabl

14、e->elem);/釋放元素空間free(table);/釋放表的空間void PrintTable(SSTable *table) / 打印查找表 int i; /定義變量ElemType *t=table->elem;for(i=0; i<table->length; i+) /進(jìn)入循環(huán)，依次打印表中元素 t+;printf("%d ", *t); /打印輸出printf("n");int Search_Seq(SSTable *table, ElemType key) /哨兵查找算法table->elem0=key;

15、/設(shè)置哨兵int result=0; / 找不到時(shí)，返回int i;for (i=table->length; i>=1;i-) if (table->elemi=key) result=i;break;return result; /返回結(jié)果void printSeq()SSTable *table; /先設(shè)置幾個(gè)變量int r;intn;ElemType key;printf("請(qǐng)輸入元素個(gè)數(shù):"); scanf("%d",&n); /輸入元素個(gè)數(shù)Create(&table, n); /建立表printf("

16、;請(qǐng)輸入");cout<<n;printf("個(gè)值：");FillTable(table); /輸入無序表的值printf("您輸入的%d 個(gè)值是：n",n);PrintTable(table); /打印無序表printf("請(qǐng)輸入關(guān)鍵字的值:");scanf("%d",&key);printf("n");printf("順序查找法運(yùn)行結(jié)果如下：nn ");Search_Seq(table,key); /哨兵查找算法r=Search_Seq(ta

17、ble,key);if(r>0)printf(" 關(guān)鍵字%d 在表中的位置是：%dn",key, r);/打印關(guān)鍵字在表中的位置printf("n");else /查找失敗printf ("查找失敗，表中無此數(shù)據(jù)。nn");void Sort(SSTable *table ) / 排序算法 int i, j;ElemType temp; for (i=table->length; i>=1 ;i-) / 從前往后找 for (j=1; j<i; j+)if(table->elemj>table-&g

18、t;elemj+1)temp=table->elemj;table->elemj=table->elemj+1;table->elemj+1=temp; int Search_Bin(SSTable *table, ElemType key) / 二分法查找（非遞歸）int low=1;int high=table->length;int result=0; / 找不到時(shí)，返回while(low <= high) /low不大于high時(shí)int mid=(low+high)/2;if(table->elemmid=key) /如果找到result=mi

19、d;break;else if(key<table->elemmid) /如果關(guān)鍵字小于mid對(duì)應(yīng)的值high=mid-1;else low=mid+1;return result; /返回結(jié)果void printBin()SSTable *table; /聲明變量int r;intn;ElemType key;printf("請(qǐng)輸入元素個(gè)數(shù):");scanf("%d",&n);Create(&table, n); /建立表printf("請(qǐng)輸入");cout<<n;printf("個(gè)

20、值：");FillTable(table); /輸入無序表的值printf("您輸入的%d 個(gè)值是：n",n);PrintTable(table); /打印無序表printf("請(qǐng)輸入關(guān)鍵字的值:");scanf("%d",&key);printf("n");Sort(table); /對(duì)無序表進(jìn)行排序printf("數(shù)據(jù)排序后的順序如下：nn ");PrintTable(table); /打印有序表printf("n");printf("二分查找

21、法的運(yùn)行結(jié)果如下：nn ");r=Search_Bin(table,key); /二分（非遞歸）查找算法if( r>0)printf("關(guān)鍵字%d 在表中的位置是：%dn",key, r);else printf ("查找失敗，表中無此數(shù)據(jù)。nn");/二叉排序樹typedef struct BiTnode /定義二叉樹節(jié)點(diǎn)int data; /節(jié)點(diǎn)的值struct BiTnode *lchild,*rchild; /節(jié)點(diǎn)的左孩子，節(jié)點(diǎn)的右孩子BiTnode,*BiTree;/查找（根據(jù)節(jié)點(diǎn)的值查找）返回節(jié)點(diǎn)指針BiTree search

22、_tree(BiTree T,int keyword,BiTree *father)BiTree p; / 臨時(shí)指針變量*father = NULL; /先設(shè)其父親節(jié)點(diǎn)指向空p = T; /p賦值為根節(jié)點(diǎn)（從根節(jié)點(diǎn)開始查找）while (p && p->data!=keyword) /如果不是p不指向空且未找到相同值的節(jié)點(diǎn)*father = p;/先將父親指向自己（注意：這里傳過來的father是二級(jí)指針）if (keyword < p->data) /如果要找的值小于自己的值p = p->lchild; / 就向自己的左孩子開始找elsep = p-&

23、gt;rchild; /否則向自己的右孩子開始查找return p; /如果找到了則返回節(jié)點(diǎn)指針BiTree creat_tree(int count)BiTree T,p; /設(shè)置兩個(gè)臨時(shí)變量T,pint i = 1;while (i <= count)if (i = 1) /如果i=1，說明還是空樹p = (BiTnode *)malloc(sizeof(BiTree);/使p指向新分配的節(jié)點(diǎn)if (!p)/分配未成功return NULL;T = p;/分配成功,T=p( 這里實(shí)際上T就是根節(jié)點(diǎn))scanf("%d",&p->data);/輸入p指

24、向節(jié)點(diǎn)的值p->lchild = p->rchild = NULL;/p的左孩子和右孩子都指向空i+;elseint temp;/ 如果不是空樹scanf("%d",&temp);/輸入節(jié)點(diǎn)的值search_tree(T,temp,&p);/查找節(jié)點(diǎn)要插入的位置。（T是根節(jié)點(diǎn)，插入的節(jié)點(diǎn)的值，父親節(jié)點(diǎn)的地址）if (temp < p->data)/如果插入的值小于父親節(jié)點(diǎn)的值p->lchild = (BiTnode *)malloc(sizeof(BiTnode);/那么就為父親節(jié)點(diǎn)的左孩子分配一個(gè)節(jié)點(diǎn)空間，并指向這個(gè)空間if

25、(!p->lchild)return NULL;p = p->lchild;/分配成功，p指向自己的左孩子else/ 如果插入的值大于父親節(jié)點(diǎn)的值p->rchild = (BiTnode *)malloc(sizeof(BiTnode);if (!p->rchild)return NULL;/分配不成功，退出p = p->rchild;/p指向自己的右孩子p -> data = temp;/新分配的節(jié)點(diǎn)的值賦值為插入的值p -> lchild = p->rchild = NULL;/使其左右節(jié)點(diǎn)均為NULLi+;return T;/返回根節(jié)點(diǎn)vo

26、id InOrder(BiTree T)if(T)InOrder(T->lchild);printf("%d ",T->data);InOrder(T->rchild);int insert_tree(BiTree *T,int elem)/插入（根節(jié)點(diǎn)，插入的值）返回-1和,-1代表插入失敗，代表成功BiTree s,p,father;s = (BiTnode *)malloc(sizeof(BiTnode);/s指向新開辟一個(gè)節(jié)點(diǎn)if (!s)/為開辟成功return -1;/ 返回值-1s->data = elem;/新節(jié)點(diǎn)的值賦值為插入的值s

27、->lchild = s->rchild = NULL;/其左右孩子為空p = search_tree(*T,elem,&father);/p賦值為要插入的節(jié)點(diǎn)if (!p)return -1;/未開辟成功，返回-1if (father = NULL)/如果父親節(jié)點(diǎn)指向空，說明是空樹*T = s;/讓根節(jié)點(diǎn)指向selse if (elem < father->data)/否則如果插入的值小于父親的值father->lchild = s;/父親的左孩子賦值為selsefather->rchild = s;/否則父親的右孩子賦值為sreturn 0;/返

28、回int delete_tree(BiTree *T,int elem) /刪除樹結(jié)點(diǎn)的操作BiTree s,p,q,father;/聲明變量p = search_tree(*T,elem,&father);/查找if(!p)return -1;if(!p->lchild)/如果p的左孩子為空if (father = NULL)*T = p->rchild;/T指向左孩子free(p);/釋放preturn 0;if (p = father->lchild)/如果p和father的左孩子相等father->lchild = p->rchild; /將p的左

29、孩子的值賦給father的左孩子elsefather->rchild = p->rchild;/將p的左孩子的值賦給father的右孩子free(p);/釋放preturn 0;elseif(!p->rchild)if (father = NULL)/如果father為空*T = p->lchild;/將p的左孩子賦給Tfree(p);/釋放preturn 0;if (p = father->lchild)/如果p等于father的左孩子的值father->lchild = p->lchild; /將p的左孩子的值賦給father的左孩子elsefat

30、her->rchild = p->lchild; /將p的左孩子的值賦給father的右孩子free(p);return 0;elseq = p;s = p->lchild;/將p的左孩子賦給swhile (s->rchild)q = s;s = s->rchild;p->data = s->data;/將s的值賦給pif (q != p)/如果q不等于pq->rchild = s->lchild; /將s的左孩子值賦給p的右孩子elseq->lchild = s->lchild; /將s的左孩子值賦給p的右孩子free(s);

31、/釋放sreturn 0;void print1() /定義print1（）以便調(diào)用printf("t*n");printf("t1,輸出中序遍歷n");printf("t2,插入一個(gè)結(jié)點(diǎn)n");printf("t3,刪除一個(gè)結(jié)點(diǎn)n");printf("t4,查找一個(gè)結(jié)點(diǎn)n");printf("t5,返回主菜單n");printf("t*n");void printTree()BiTree T,p; /聲明變量T=NULL;inti,n;ElemType

32、key;printf("請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù)：n");scanf("%d",&n);/輸入值printf("請(qǐng)輸入");cout<<n;printf("個(gè)值：");T=creat_tree(n);/建立樹print1();scanf("%d",&i);/輸入各個(gè)值while(i!=5)/i不等于5時(shí)switch(i)case 1:printf("中序遍歷二叉樹結(jié)果如下：n");InOrder(T);/中序遍歷break;case 2:printf(&qu

33、ot;請(qǐng)輸入要插入的結(jié)點(diǎn)值：");scanf("%d",&key);/輸入要查找的關(guān)鍵字if(insert_tree(&T,key)/如果插入成功printf("插入成功！");elseprintf("已存在此元素！");break;case 3:printf("請(qǐng)輸入要?jiǎng)h除的結(jié)點(diǎn)值：");scanf("%d",&key); /輸入要?jiǎng)h除的關(guān)鍵字if(!(delete_tree(&T,key)/如果刪除成功printf("刪除成功！"

34、);elseprintf("不存在此元素！");break;case 4:printf("請(qǐng)輸入要查找的結(jié)點(diǎn)值：");scanf("%d",&key); /輸入要查找的關(guān)鍵字if(search_tree(T,key,&p)/如果查找成功printf("查找成功！");elseprintf("不存在此元素！");break;default:printf("按鍵錯(cuò)誤！");printf("n");print1();scanf("%d&

35、quot;,&i);/哈希表typedef struct int num; Elemtype;/定義查找的結(jié)點(diǎn)元素typedef struct Elemtype *elem; /數(shù)據(jù)元素存儲(chǔ)基址int count; /數(shù)據(jù)元素個(gè)數(shù)int sizeindex; HashTable;/定義哈希表int Hash(int num) int p; p=num%11; return p; /定義哈希函數(shù)/沖突處理函數(shù)，采用二次探測(cè)再散列法解決沖突int collision(int p,int &c)int i,q;i=c/2+1;while(i<MAX)if(c%2=0)c+;q=

36、(p+i*i)%MAX;if(q>=0) return q;else i=c/2+1;elseq=(p-i*i)%MAX;c+;if(q>=0)return q;elsei=c/2+1;return 0;void InitHash(HashTable *H)/創(chuàng)建哈希表 int i; H->elem=(Elemtype *)malloc(MAX*sizeof(Elemtype); H->count=0; H->sizeindex=MAX; for(i=0;i<MAX;i+) H->elemi.num=0;/初始化，使SearHash函數(shù)能判斷到底有沒有

37、元素在里面 int SearHash(HashTable H,int key,int *p)/查找函數(shù) *p=Hash(key); while(H.elem*p.num!=key&&H.elem*p.num!=0) *p=*p+1; if(H.elem*p.num=key) return 1; else return 0; void InsertHash(HashTable *H,Elemtype e) /如果查找不到就插入元素int p; SearHash(*H,e.num,&p); /查找H->elemp=e; +H->count; void print

38、Hash()/調(diào)用哈希表 HashTable H; int p,key,i,n; Elemtype e; InitHash(&H);printf("輸入數(shù)據(jù)個(gè)數(shù)(<11 ):");scanf("%d",&n);printf("請(qǐng)輸入各個(gè)值：");for(i=0;i<n;i+) /輸入n個(gè)元素scanf("%d",&e.num);/輸入數(shù)字if(!SearHash(H,e.num ,&p) InsertHash(&H,e );/插入元素 else printf(&q

39、uot;已經(jīng)存在n");/否則就表示元素的數(shù)字已經(jīng)存在 printf("輸入查找的數(shù)字:"); scanf("%d",&key);/輸入要查找的數(shù)字if(SearHash(H,key,&p)/能查找成功 printf("查找成功！");/輸出位置 else printf(" 不存在此元素！"); void print()printf("t*n");printf("t1,順序查找n");printf("t2,二分查找n");prin

40、tf("t3,二叉排序樹n");printf("t4,哈希查找n");printf("t5,退出n");printf("t*n");printf("請(qǐng)選擇查找方式：n");/ 主函數(shù)int main(int argc, char* argv)int i;/定義變量print();scanf("%d",&i);/輸入要數(shù)字選擇要使用的查找方法while(i!=5)/i不等于5時(shí)switch(i) case 1:/i=1時(shí)printf("順序查找法：n"

41、;);printSeq();/順序查找法break;/跳出循環(huán)case 2:printf("二分查找法：n");printBin();/二分查找法break; /跳出循環(huán)case 3:printf("二叉排序樹：n");printTree();/二叉排序樹break; /跳出循環(huán)case 4:printf("哈希查找法：n");printHash();/哈希查找法break; /跳出循環(huán)default:printf("按鍵錯(cuò)誤！");printf("n");print();/調(diào)用函數(shù)print(

42、)scanf("%d",&i);return 0;/返回0【附錄2-排序源程序】#include <stdio.h>#include <stdlib.h>#include <string.h>#define Max 100 typedef struct /定義記錄類型int key; /關(guān)鍵字項(xiàng)RecType;typedef RecType SeqListMax+1; /SeqList為順序表，表中第0個(gè)元素作為哨兵int n; /順序表實(shí)際的長(zhǎng)度/1、 直接插入排序的基本思想：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已排

43、序好的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。/=直接插入排序法=void InsertSort(SeqList R) /對(duì)順序表R中的記錄R1n按遞增序進(jìn)行插入排序 int i,j;for(i=2;i<=n;i+) /依次插入R2，Rnif(Ri.key<Ri-1.key) /若Ri.key大于等于有序區(qū)中所有的keys，則Ri留在原位 R0=Ri;j=i-1; /R0是Ri的副本 do /從右向左在有序區(qū)R1i-1中查找Ri 的位置 Rj+1=Rj; /將關(guān)鍵字大于Ri.key的記錄后移 j-; while(R0.key<Rj.key); /當(dāng)Ri.keyRj.ke

44、y 是終止Rj+1=R0; /Ri插入到正確的位置上/2、 冒泡排序的基本思想：設(shè)想被排序的記錄數(shù)組R1n垂直排序。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"（交換），如此反復(fù)進(jìn)行，直到最后任意兩個(gè)氣泡都是輕者在上，重者在下為止。/=冒泡排序=typedef enumFALSE,TRUE Boolean; /FALSE為0，TRUE為1void BubbleSort(SeqList R) /自下向上掃描對(duì)R做冒泡排序int i,j; Boolean exchange; /交換標(biāo)志 for(i=1;i<n;i+)

45、 /最多做n-1趟排序exchange=FALSE; /本趟排序開始前，交換標(biāo)志應(yīng)為假for(j=n-1;j>=i;j-) /對(duì)當(dāng)前無序區(qū)Rin 自下向上掃描if(Rj+1.key<Rj.key) /兩兩比較，滿足條件交換記錄R0=Rj+1; /R0不是哨兵，僅做暫存單元Rj+1=Rj;Rj=R0;exchange=TRUE; /發(fā)生了交換，故將交換標(biāo)志置為真if(! exchange) /本趟排序未發(fā)生交換，提前終止算法return; /3、 快速排序的基本思想：在待排序的n個(gè)記錄中任取一個(gè)記錄（通常取第一個(gè)記錄），把該記錄作為支點(diǎn)（又稱基準(zhǔn)記錄）（pivot），將所有關(guān)鍵字比它

46、小的記錄放置在它的位置之前，將所有關(guān)鍵字比它大的記錄放置在它的位置之后(稱之為一次劃分過程)。之后對(duì)所分的兩部分分別重復(fù)上述過程，直到每部分只有一個(gè)記錄為止。/1.=一次劃分函數(shù)=int Partition(SeqList R,int i,int j) /對(duì)Rij做一次劃分，并返回基準(zhǔn)記錄的位置 RecType pivot=Ri; /用第一個(gè)記錄作為基準(zhǔn)while(i<j) /從區(qū)間兩端交替向中間掃描，直到i=jwhile(i<j &&Rj.key>=pivot.key) /基準(zhǔn)記錄pivot相當(dāng)與在位置i上j-; /從右向左掃描，查找第一個(gè)關(guān)鍵字小于pivot.key的記錄Rjif(i<j) /