數據結構實驗報告-答案

數據結構 (C語言版)實驗報告專業(yè) 班級 學號 姓名實驗 1實驗題目：單鏈表的插入和刪除實驗目的：了解和掌握線性表的邏輯結構和鏈式存儲結構， 掌握單鏈表的基本算法及相關的時間性能分析。實驗要求：建立一個數據域定義為字符串的單鏈表， 在鏈表中不允許有重復的字符串； 根據輸入的字符串，先找到相應的結點，后刪除之。實驗主要步驟：1、分析、理解給出的示例程序。2、調試程序，并設計輸入數據（如：bat，cat，eat，fat，hat，jat，lat，mat，#），測試程序的如下功能：不允許重復字符串的插入；根據輸入的字符串，找到相應的結點并刪除。3、修改程序：1）增加插入結點的功能。2）將建立鏈表的方法改為頭插入法。程序代碼:#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedefstructnode{

//定義結點chardata[10];

//結點的數據域為字符串structnode*next;

//結點的指針域}ListNode;typedefListNode*LinkList;

// 自定義

LinkList

單鏈表類型LinkListCreatListR1();

//函數，用尾插入法建立帶頭結點的單鏈表LinkListCreatList(void);

//函數，用頭插入法建立帶頭結點的單鏈表ListNode*LocateNode();

//函數，按值查找結點voidDeleteList();

//函數，刪除指定值的結點voidprintlist();

//函數，打印鏈表中的所有值voidDeleteAll();

//函數，刪除所有結點，釋放內存ListNode*AddNode(); //修改程序：增加節(jié)點。用頭插法，返回頭指針//========== 主函數==============voidmain(){charch[10],num[5];LinkListhead;head=CreatList(); //用頭插入法建立單鏈表，返回頭指針printlist(head); //遍歷鏈表輸出其值printf("Deletenode(y/n):"); //輸入"y"或"n"去選擇是否刪除結點scanf("%s",num);if(strcmp(num,"y")==0||strcmp(num,"Y")==0){printf("PleaseinputDelete_data:");scanf("%s",ch); //輸入要刪除的字符串DeleteList(head,ch);printlist(head);}printf("Addnode?(y/n):");//輸入"y"或"n"去選擇是否增加結點scanf("%s",num);if(strcmp(num,"y")==0||strcmp(num,"Y")==0){head=AddNode(head);}printlist(head);DeleteAll(head); //刪除所有結點，釋放內存}//========== 用尾插入法建立帶頭結點的單鏈表 ===========LinkListCreatListR1(void){charch[10];LinkListhead=(LinkList)malloc(sizeof(ListNode));// 生成頭結點ListNode*s,*r,*pp;r=head;r->next=NULL;printf("Input#toend "); //輸入"#"代表輸入結束printf("\nPleaseinputNode_data:");scanf("%s",ch); //輸入各結點的字符串while(strcmp(ch,"#")!=0){pp=LocateNode(head,ch); //按值查找結點，返回結點指針if(pp==NULL){ //沒有重復的字符串，插入到鏈表中s=(ListNode*)malloc(sizeof(ListNode));strcpy(s->data,ch);r->next=s;r=s;r->next=NULL;}printf("Input#toend ");printf("PleaseinputNode_data:");scanf("%s",ch);}returnhead; //返回頭指針}//========== 用頭插入法建立帶頭結點的單鏈表 ===========LinkListCreatList(void){charch[100];LinkListhead,p;head=(LinkList)malloc(sizeof(ListNode));head->next=NULL;while(1){printf("Input#toend ");printf("PleaseinputNode_data:");scanf("%s",ch);if(strcmp(ch,"#")){if(LocateNode(head,ch)==NULL){strcpy(head->data,ch);p=(LinkList)malloc(sizeof(ListNode));p->next=head;head=p;}}elsebreak;}returnhead;}//========== 按值查找結點，找到則返回該結點的位置，否則返回 NULL==========ListNode*LocateNode(LinkListhead,char*key){ListNode*p=head->next;// 從開始結點比較while(p!=NULL&&strcmp(p->data,key)!=0)p=p->next; //掃描下一個結點returnp; //若p=NULL 則查找失敗，否則

//直到 p為NULLp指向找到的值為

或p->datakey的結點

為

key

止}//========== 修改程序：增加節(jié)點 =======ListNode*AddNode(LinkListhead){charch[10];ListNode*s,*pp;printf("\nPleaseinputaNewNode_data:");scanf("%s",ch); //輸入各結點的字符串pp=LocateNode(head,ch);printf("ok2\n");

//按值查找結點，返回結點指針if(pp==NULL){ //沒有重復的字符串，插入到鏈表中s=(ListNode*)malloc(sizeof(ListNode));strcpy(s->data,ch);printf("ok3\n");s->next=head->next;head->next=s;}returnhead;}//==========刪除帶頭結點的單鏈表中的指定結點voidDeleteList(LinkListhead,char*key){

=======ListNode*p,*r,*q=head;p=LocateNode(head,key);

//按

key

值查找結點的if(p==NULL){

//若沒有找到結點，退出printf("positionerror");exit(0);}while(q->next!=p)

//p

為要刪除的結點，

q為

p的前結點q=q->next;r=q->next;q->next=r->next;free(r);

//釋放結點}//=========== 打印鏈表voidprintlist(LinkListhead){

=======ListNode*p=head->next;while(p){printf("%s, ",p->data);p=p->next;

//從開始結點打印}printf("\n");}//========== 刪除所有結點，釋放空間

===========voidDeleteAll(LinkListhead){ListNode*p=head,*r;while(p->next){r=p->next;free(p);p=r;}free(p);}實驗結果：Input#toendPleaseinputNode_data:batInput#toendPleaseinputNode_data:catInput#toendPleaseinputNode_data:eatInput#toendPleaseinputNode_data:fatInput#toendPleaseinputNode_data:hatInput#toendPleaseinputNode_data:jatInput#toendPleaseinputNode_data:latInput#toendPleaseinputNode_data:matInput#toendPleaseinputNode_data:#mat, lat, jat, hat, fat, eat, cat, bat,Deletenode(y/n):yPleaseinputDelete_data:hatmat, lat, jat, fat, eat, cat, bat,Insertnode(y/n):yPleaseinputInsert_data:putposition:5mat, lat, jat, fat, eat, put, cat, bat,請按任意鍵繼續(xù) ...示意圖：headmat lat jat hat fat eat cat batNULLheadmat lat jat fat eat cat batNULLhatheadmat lat jat fat eat cat batNULLput心得體會：本次實驗使我們對鏈表的實質了解更加明確了， 對鏈表的一些基本操作也更加熟練了。 另外實驗指導書上給出的代碼是有一些問題的， 這使我們認識到實驗過程中不能想當然的直接編譯執(zhí)行，應當在閱讀并完全理解代碼的基礎上再執(zhí)行，這才是實驗的意義所在。實驗 2實驗題目：二叉樹操作設計和實現實驗目的：掌握二叉樹的定義、性質及存儲方式，各種遍歷算法。實驗要求：采用二叉樹鏈表作為存儲結構， 完成二叉樹的建立， 先序、中序和后序以及按層次遍歷的操作，求所有葉子及結點總數的操作。實驗主要步驟：1、分析、理解程序。2、調試程序， 設計一棵二叉樹， 輸入完全二叉樹的先序序列， 用#代表虛結點（空指針），如ABD###CE##F##，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結點總數。實驗代碼#include"stdio.h"#include"stdlib.h"#include"string.h"#defineMax20 //結點的最大個數typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode; //自定義二叉樹的結點類型typedefBinTNode*BinTree; //定義二叉樹的指針intNodeNum,leaf; //NodeNum 為結點數， leaf為葉子數//========== 基于先序遍歷算法創(chuàng)建二叉樹 ==============//=====要求輸入先序序列，其中加入虛結點

"#"

以示空指針的位置

==========BinTreeCreatBinTree(void){BinTreeT;charch;if((ch=getchar())=='#')return(NULL); //讀入#，返回空指針else{T=(BinTNode*)malloc(sizeof(BinTNode));// 生成結點T->data=ch;T->lchild=CreatBinTree(); //構造左子樹T->rchild=CreatBinTree(); //構造右子樹return(T);}}//========NLR 先序遍歷 =============voidPreorder(BinTreeT){if(T){printf("%c",T->data);

//訪問結點Preorder(T->lchild);

//先序遍歷左子樹Preorder(T->rchild);

//先序遍歷右子樹}}//========LNR 中序遍歷 ===============voidInorder(BinTreeT){if(T){Inorder(T->lchild);printf("%c",T->data);

//中序遍歷左子樹//訪問結點Inorder(T->rchild);

//中序遍歷右子樹}}//==========LRN 后序遍歷 ============voidPostorder(BinTreeT){if(T){Postorder(T->lchild);

//后序遍歷左子樹Postorder(T->rchild);

//后序遍歷右子樹printf("%c",T->data);

//訪問結點}}//=====采用后序遍歷求二叉樹的深度、結點數及葉子數的遞歸算法 ========intTreeDepth(BinTreeT){inthl,hr,max;if(T){hl=TreeDepth(T->lchild);

//求左深度hr=TreeDepth(T->rchild);

//求右深度max=hl>hr?hl:hr;

//取左右深度的最大值NodeNum=NodeNum+1;

//求結點數if(hl==0&&hr==0)leaf=leaf+1;

//若左右深度為

0，即為葉子。return(max+1);}elsereturn(0);}//====利用"先進先出 "（FIFO

）隊列，按層次遍歷二叉樹

==========voidLevelorder(BinTreeT){intfront=0,rear=1;BinTNode*cq[Max],*p; //定義結點的指針數組 cqcq[1]=T; //根入隊while(front!=rear){front=(front+1)%NodeNum;p=cq[front];printf("%c",p->data);

//出隊//出隊，輸出結點的值if(p->lchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->lchild;

//左子樹入隊}if(p->rchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->rchild;

//右子樹入隊}}}//====數葉子節(jié)點個數 ==========intcountleaf(BinTreeT){inthl,hr;if(T){hl=countleaf(T->lchild);hr=countleaf(T->rchild);if(hl==0&&hr==0) //若左右深度為 0，即為葉子。return(1);elsereturnhl+hr;}elsereturn0;}//========== 主函數=================voidmain(){BinTreeroot;chari;intdepth;printf("\n");printf("CreatBin_Tree ； Inputpreorder:");// 輸入完全二叉樹的先序序列，// 用

#代表虛結點，如

ABD###CE##F##root=CreatBinTree();

//創(chuàng)建二叉樹，返回根結點do{

//從菜單中選擇遍歷方式，輸入序號。printf("\t**********select************\n");printf("\t1:PreorderTraversal\n");printf("\t2:IorderTraversal\n");printf("\t3:Postordertraversal\n");printf("\t4:PostTreeDepth,Nodenumber,Leafnumber\n");printf("\t5:LevelDepth\n");// 按層次遍歷之前，先選擇 4，求出該樹的結點數。printf("\t0:Exit\n");printf("\t*******************************\n");fflush(stdin);scanf("%c",&i); //輸入菜單序號（ 0-5）switch(i-'0'){case1:printf("PrintBin_treePreorder:");Preorder(root); //先序遍歷break;case2:printf("PrintBin_TreeInorder:");Inorder(root); //中序遍歷break;case3:printf("PrintBin_TreePostorder:");Postorder(root);

//后序遍歷break;case4:depth=TreeDepth(root); //求樹的深度及葉子數printf("BinTreeDepth=%d BinTreeNodenumber=%d",depth,NodeNum);printf(" BinTreeLeafnumber=%d",countleaf(root));break;case5:printf("LevePrintBin_Tree:");Levelorder(root); //按層次遍歷break;default:exit(1);}printf("\n");}while(i!=0);}實驗結果：CreatBin_Tree ； Inputpreorder:ABD###CE##F##**********select************PreorderTraversalIorderTraversalPostordertraversalPostTreeDepth,Nodenumber,LeafnumberLevelDepthExit*******************************1PrintBin_treePreorder:ABDCEF2PrintBin_TreeInorder:DBAECF3PrintBin_TreePostorder:DBEFCA4BinTreeDepth=3BinTreeNodenumber=6BinTreeLeafnumber=35LevePrintBin_Tree:ABCDEF0Pressanykeytocontinue二叉樹示意圖AB CD E F心得體會：這次實驗加深了我對二叉樹的印象， 尤其是對二叉樹的各種遍歷操作有了一定的了解。 同時認識到，在設計程序時輔以圖形化的描述是非常有用處的。實驗 3實驗題目：圖的遍歷操作實驗目的：掌握有向圖和無向圖的概念； 掌握鄰接矩陣和鄰接鏈表建立圖的存儲結構； 掌握 DFS及BFS對圖的遍歷操作；了解圖結構在人工智能、工程等領域的廣泛應用。實驗要求：采用鄰接矩陣和鄰接鏈表作為圖的存儲結構，完成有向圖和無向圖的 DFS和BFS操作。實驗主要步驟：設計一個有向圖和一個無向圖，任選一種存儲結構，完成有向圖和無向圖的 DFS（深度優(yōu)先遍歷）和 BFS（廣度優(yōu)先遍歷）的操作。1． 鄰接矩陣作為存儲結構#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100 // 定義最大頂點數typedefstruct{charvexs[MaxVertexNum]; // 頂點表intedges[MaxVertexNum][MaxVertexNum]; //intn,e; // 圖中的頂點數 n和邊數}MGraph; // 用鄰接矩陣表示的圖的類型//========= 建立鄰接矩陣 =======

e

鄰接矩陣，可看作邊表voidCreatMGraph(MGraph*G){inti,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);//輸入頂點數和邊數scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G->n;i++){scanf("%c",&a);G->vexs[i]=a;

//

讀入頂點信息，建立頂點表}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0; // 初始化鄰接矩陣printf("Inputedges,CreatAdjacencyMatrix\n");for(k=0;k<G->e;k++){ // 讀入 e條邊，建立鄰接矩陣scanf("%d%d",&i,&j); // 輸入邊（ Vi，Vj）的頂點序號G->edges[i][j]=1;G->edges[j][i]=1;// 若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句}}//========= 定義標志向量，為全局變量typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS ：深度優(yōu)先遍歷的遞歸算法voidDFSM(MGraph*G,inti){// 以Vi為出發(fā)點對鄰接矩陣表示的圖intj;printf("%c",G->vexs[i]); //visited[i]=TRUE; //for(j=0;j<G->n;j++) //if(G->edges[i][j]==1&&!visited[j])DFSM(G,j); //

=============G進行DFS搜索，鄰接矩陣是 0，1訪問頂點 Vi置已訪問標志依次搜索 Vi的鄰接點（Vi，Vj）∈E，且 Vj未訪問過，故

矩陣Vj為新出發(fā)點}voidDFS(MGraph*G){inti;for(i=0;i<G->n;i++)visited[i]=FALSE;

//

標志向量初始化for(i=0;i<G->n;i++)if(!visited[i])DFSM(G,i);

//Vi//

以

未訪問過Vi為源點開始

DFS搜索}//===========BFS ：廣度優(yōu)先遍歷 =======voidBFS(MGraph*G,intk){ // 以Vk為源點對用鄰接矩陣表示的圖 G進行廣度優(yōu)先搜索inti,j,f=0,r=0;intcq[MaxVertexNum]; // 定義隊列for(i=0;i<G->n;i++)visited[i]=FALSE; // 標志向量初始化for(i=0;i<G->n;i++)cq[i]=-1; // 隊列初始化printf("%c",G->vexs[k]); // 訪問源點 Vkvisited[k]=TRUE;cq[r]=k; //Vk 已訪問，將其入隊。注意，實際上是將其序號入隊while(cq[f]!=-1){ // 隊非空則執(zhí)行i=cq[f];f=f+1; //Vf 出隊for(j=0;j<G->n;j++) // 依次Vi的鄰接點 Vjif(G->edges[i][j]==1&&!visited[j]){//Vj 未訪問printf("%c",G->vexs[j]); // 訪問 Vjvisited[j]=TRUE;r=r+1;cq[r]=j; // 訪問過 Vj入隊}}}//==========main=====voidmain(){inti;MGraph*G;G=(MGraph*)malloc(sizeof(MGraph)); // 為圖 G申請內存空間CreatMGraph(G); // 建立鄰接矩陣printf("PrintGraphDFS:");DFS(G); // 深度優(yōu)先遍歷printf("\n");printf("PrintGraphBFS:");BFS(G,3); // 以序號為 3的頂點開始廣度優(yōu)先遍歷printf("\n");}2． 鄰接鏈表作為存儲結構#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum50 // 定義最大頂點數typedefstructnode{ // 邊表結點intadjvex; // 鄰接點域structnode*next; // 鏈域}EdgeNode;typedefstructvnode{ // 頂點表結點charvertex; // 頂點域EdgeNode*firstedge; // 邊表頭指針}VertexNode;typedefVertexNodeAdjList[MaxVertexNum]; //AdjListtypedefstruct{AdjListadjlist; // 鄰接表intn,e; // 圖中當前頂點數和邊數}ALGraph; // 圖類型

是鄰接表類型//========= 建立圖的鄰接表 =======voidCreatALGraph(ALGraph*G){inti,j,k;chara;EdgeNode*s; // 定義邊表結點printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e); //

讀入頂點數和邊數scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G->n;i++) //{

建立邊表scanf("%c",&a);G->adjlist[i].vertex=a; //G->adjlist[i].firstedge=NULL;//

讀入頂點信息邊表置為空表}printf("Inputedges,CreatAdjacencyList\n");for(k=0;k<G->e;k++){ //

建立邊表scanf("%d%d",&i,&j); //

讀入邊（

Vi

，

Vj

）的頂點對序號s=(EdgeNode*)malloc(sizeof(EdgeNode));

//

生成邊表結點s->adjvex=j; //

鄰接點序號為

js->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s; //

將新結點

*S

插入頂點

Vi

的邊表頭部s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=i; //

鄰接點序號為

is->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s; //

將新結點

*S

插入頂點

Vj

的邊表頭部}}//========= 定義標志向量，為全局變量typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS ：深度優(yōu)先遍歷的遞歸算法voidDFSM(ALGraph*G,inti){ // 以ViEdgeNode*p;printf("%c",G->adjlist[i].vertex); //visited[i]=TRUE; //p=G->adjlist[i].firstedge; //while(p){ //if(!visited[p->adjvex]) //DFSM(G,p->adjvex); //p=p->next; //

=============為出發(fā)點對鄰接鏈表表示的圖 G進行 DFS搜索訪問頂點 Vi標記 Vi已訪問取Vi邊表的頭指針依次搜索 Vi的鄰接點 Vj，這里 j=p->adjvex若Vj尚未被訪問則以 Vj為出發(fā)點向縱深搜索找Vi的下一個鄰接點}}voidDFS(ALGraph*G){inti;for(i=0;i<G->n;i++)visited[i]=FALSE;

//

標志向量初始化for(i=0;i<G->n;i++)if(!visited[i])

//Vi

未訪問過DFSM(G,i);

//

以

Vi

為源點開始

DFS搜索}//==========BFS ：廣度優(yōu)先遍歷

=========voidBFS(ALGraph*G,intk){ //

以

Vk

為源點對用鄰接鏈表表示的圖

G進行廣度優(yōu)先搜索inti,f=0,r=0;EdgeNode*p;intcq[MaxVertexNum]; // 定義 FIFO隊列for(i=0;i<G->n;i++)visited[i]=FALSE; // 標志向量初始化for(i=0;i<=G->n;i++)cq[i]=-1; // 初始化標志向量printf("%c",G->adjlist[k].vertex);// 訪問源點 Vkvisited[k]=TRUE;cq[r]=k; //Vk 已訪問，將其入隊。注意，實際上是將其序號入隊while(cq[f]!=-1){ 隊列非空則執(zhí)行i=cq[f];f=f+1; //Vi 出隊p=G->adjlist[i].firstedge; // 取Vi的邊表頭指針while(p){ // 依次搜索 Vi的鄰接點 Vj（令 p->adjvex=jif(!visited[p->adjvex]){ // 若Vj未訪問過printf("%c",G->adjlist[p->adjvex].vertex); // 訪問 Vjvisited[p->adjvex]=TRUE;r=r+1;cq[r]=p->adjvex; // 訪問過的 Vj入隊

）}p=p->next;

//

找

Vi

的下一個鄰接點}}//endwhile}//========== 主函數 ===========voidmain(){inti;ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));CreatALGraph(G);printf("PrintGraphDFS:");DFS(G);printf("\n");printf("PrintGraphBFS:");BFS(G,3);printf("\n");}實驗結果：1.鄰接矩陣作為存儲結構執(zhí)行順序：InputVertexNum(n)andEdgesNum(e):8，9V0InputVertexstring:01234567Inputedges,CreatAdjacencyMatrixV1V201V302V4V5V613142526V7374756PrintGraphDFS:01374256PrintGraphBFS:317042562.鄰接鏈表作為存儲結構執(zhí)行順序：InputVertexNum(n)andEdgesNum(e):8，9InputVertexstring:01234567Inputedges,CreatAdjacencyList01V002V1V21314V325V4V5V6263747V756PrintGraphDFS:02651473PrintGraphBFS:37140265心得體會：這次實驗較以前的實驗難度加大， 必須先理解深度優(yōu)先和廣度優(yōu)先兩種遍歷思路， 和數據結構中隊列的基本操作，才能看懂理解代碼。同時圖這種數據結構對抽象的能力要求非常高，代碼不容易看懂，排錯也比較麻煩，應該多加練習，才能掌握。實驗 4實驗題目：排序實驗目的：掌握各種排序方法的基本思想、排序過程、算法實現，能進行時間和空間性能的分析，根據實際問題的特點和要求選擇合適的排序方法。實驗要求：實現直接排序、 冒泡、直接選擇、 快速、堆、歸并排序算法。 比較各種算法的運行速度。實驗主要步驟：實驗代碼#include"stdio.h"#include"stdlib.h"#defineMax100 // 假設文件長度typedefstruct{ // 定義記錄類型intkey; // 關鍵字項}RecType;typedefRecTypeSeqList[Max+1];//SeqList 為順序表，表中第 0個元素作為哨兵intn; // 順序表實際的長度//========== 直接插入排序法 ======voidInsertSort(SeqListR){ // 對順序表 R中的記錄 R[1‥n]按遞增序進行插入排序inti,j;for(i=2;i<=n;i++) // 依次插入 R[2]，??， R[n]if(R[i].key<R[i-1].key){// 若R[i].key 大于等于有序區(qū)中所有的 keys，則R[i]留在原位R[0]=R[i];j=i-1; //R[0] 是R[i] 的副本do{ // 從右向左在有序區(qū) R[1‥i-1] 中查找 R[i] 的位置R[j+1]=R[j]; // 將關鍵字大于 R[i].key 的記錄后移j--;}while(R[0].key<R[j].key); // 當R[i].key ≥R[j].key 是終止R[j+1]=R[0]; //R[i] 插入到正確的位置上}//endif}//========== 冒泡排序 =======typedefenum{FALSE,TRUE}Boolean;//FALSE 為0，TRUE為1voidBubbleSort(SeqListR){ // 自下向上掃描對 R做冒泡排序inti,j; Booleanexchange; // 交換標志for(i=1;i<n;i++){ // 最多做 n-1趟排序exchange=FALSE; // 本趟排序開始前，交換標志應為假for(j=n-1;j>=i;j--) // 對當前無序區(qū) R[i‥n] 自下向上掃描if(R[j+1].key<R[j].key){ // 兩兩比較，滿足條件交換記錄R[0]=R[j+1]; //R[0] 不是哨兵，僅做暫存單元R[j+1]=R[j];R[j]=R[0];exchange=TRUE; // 發(fā)生了交換，故將交換標志置為真}if(!exchange)

//

本趟排序未發(fā)生交換，提前終止算法return;}//endfor

（為循環(huán)）}//1.======== 一次劃分函數 =====intPartition(SeqListR,inti,intj){//對R[i‥j]做一次劃分，并返回基準記錄的位置RecTypepivot=R[i]; // 用第一個記錄作為基準while(i<j){ // 從區(qū)間兩端交替向中間掃描，直到while(i<j&&R[j].key>=pivot.key) // 基準記錄 pivotj--; // 從右向左掃描，查找第一個關鍵字小于if(i<j) // 若找到的 R[j].key<pivot.key ，則

i=j相當與在位置 ipivot.key 的記錄

上R[j]R[i++]=R[j];//

交換

R[i]

和

R[j]

，交換后

i

指針加

1while(i<j&&R[i].key<=pivot.key)

//

基準記錄

pivot

相當與在位置

j上i++;

//

從左向右掃描，查找第一個關鍵字小于

pivot.key

的記錄R[i]if(i<j)

//

若找到的

R[i].key>pivot.key

，則R[j--]=R[i];//

交換

R[i]

和

R[j]

，交換后

j指針減

1}R[i]=pivot;

//

此時，

i=j

，基準記錄已被最后定位returni;

//

返回基準記錄的位置}//2.===== 快速排序 ===========voidQuickSort(SeqListR,intlow,inthigh){ //R[low..high]

快速排序intpivotpos; //

劃分后基準記錄的位置if(low<high){//pivotpos=Partition(R,low,high);//

僅當區(qū)間長度大于 1時才排序對R[low..high] 做一次劃分，

得到基準記錄的位置QuickSort(R,low,pivotpos-1); // 對左區(qū)間遞歸排序QuickSort(R,pivotpos+1,high); // 對右區(qū)間遞歸排序}}//======直接選擇排序voidSelectSort(SeqListR){

========inti,j,k;for(i=1;i<n;i++){

//

做第

i

趟排序（

1≤i

≤n-1

）k=i;for(j=i+1;j<=n;j++)//if(R[j].key<R[k].key)k=j; //kif(k!=i){// //

在當前無序區(qū) R[i‥n]中選 key最小的記錄記下目前找到的最小關鍵字所在的位置交換 R[i] 和R[k]

R[k]R[0]=R[i];R[i]=R[k];R[k]=R[0];}//endif}//endfor}//========== 大根堆調整函數 =======voidHeapify(SeqListR,intlow,inthigh){ // 將R[low..high] 調整為大根堆，除 R[low] 外，其余結點均滿足堆性質intlarge; //large 指向調整結點的左、右孩子結點中關鍵字較大者RecTypetemp=R[low];// 暫存調整結點for(large=2*low;large<=high;large*=2){//R[low] 是當前調整結點//

若

large>high,

則表示

R[low]

是葉子，調整結束；否則先令

large

指向

R[low]

的左孩子if(large<high&&R[large].key<R[large+1].key)large++; // 若R[low] 的右孩子存在且關鍵字大于左兄弟，則令

large

指向它//

現在

R[large]

是調整結點

R[low]

的左右孩子結點中關鍵字較大者if(temp.key>=R[large].key)//temp

始終對應

R[low]break;//

當前調整結點不小于其孩子結點的關鍵字，結束調整R[low]=R[large];//

相當于交換了

R[low]

和

R[large]low=large;//

令

low

指向新的調整結點，相當于

temp

已篩下到

large

的位置}R[low]=temp; // 將被調整結點放入最終位置上}//========== 構造大根堆 ==========voidBuildHeap(SeqListR){ // 將初始文件 R[1..n] 構造為堆inti;for(i=n/2;i>0;i--)Heapify(R,i,n); // 將R[i..n] 調整為大根堆}//========== 堆排序 ===========voidHeapSort(SeqListR){ // 對R[1..n] 進行堆排序，不妨用

R[0]

做暫存單元inti;BuildHeap(R);//for(i=n;i>1;i--){

//

將

R[1..n]

構造為初始大根堆對當前無序區(qū) R[1..i]

進行堆排序，共做

n-1

趟。R[0]=R[1];R[1]=R[i];R[i]=R[0];Heapify(R,1,i-1); //

//

將

R[1..i-1]

將堆頂和堆中最后一個記錄交換重新調整為堆，僅有 R[1]可能違反堆性質。}}//===== 將兩個有序的子序列 R[low..m]

和

R[m+1..high]

歸并成有序的序列

R[low..high]==voidMerge(SeqListR,intlow,intm,inthigh){inti=low,j=m+1,p=0;// 置初始值RecType*R1; //R1 為局部量R1=(RecType*)malloc((high-low+1)*sizeof(RecType));// 申請空間while(i<=m&&j<=high) // 兩個子序列非空時取其小者輸出到R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];

R1[p]

上while(i<=m)

//

若第一個子序列非空，則復制剩余記錄到

R1R1[p++]=R[i++];while(j<=high)

//

若第二個子序列非空，則復制剩余記錄到

R1中R1[p++]=R[j++];for(p=0,i=low;i<=high;p++,i++)R[i]=R1[p]; // 歸并完成后將結果復制回 R[low..high]}//========= 對R[1..n] 做一趟歸并排序voidMergePass(SeqListR,intlength){

========inti;for(i=1;i+2*length-1<=n;i=i+2*length)Merge(R,i,i+length-1,i+2*length-1);//

歸并長度為

length

的兩個相鄰的子序列if(i+length-1<n) // 尚有一個子序列，其中后一個長度小于 lengthMerge(R,i,i+length-1,n);// 歸并最后兩個子序列// 注意：若 i≤n且i+length-1 ≥n時，則剩余一個子序列輪空，無須歸并}//========== 自底向上對 R[1..n] 做二路歸并排序 ===============voidMergeSort(SeqListR){intlength;for(length=1;length<n;length*=2) // 做[lgn] 趟排序MergePass(R,length); // 有序長度≥ n時終止}//========== 輸入順序表 ========voidinput_int(SeqListR){inti;printf("Pleaseinputnum(int):");scanf("%d",&n);printf("Plaseinput%dinteger:",n);for(i=1;i<=n;i++)scanf("%d",&R[i].key);}//========== 輸出順序表 ========voidoutput_int(SeqListR){inti;for(i=1;i<=n;i++)printf("%4d",R[i].key);}//========== 主函數 ======voidmain(){inti;SeqListR;input_int(R);printf("\t********Select**********\n");printf("\t1:InsertSort\n");printf("\t2:BubbleSort\n");printf("\t3:QuickSort\n");printf("\t4:StraightSelectionSort\n");printf("\t5:HeapSort\n");printf("\t6:MergeSort\n");printf("\t7:Exit\n");printf("\t***************************\n");scanf("%d",&i); // 輸入整數switch(i){case1:InsertSort(R);break; //case2:BubbleSort(R);break;case3:QuickSort(R,1,n);break; //case4:SelectSort(R);break;case5:HeapSort(R);break; //case6:MergeSort(R);break;case7:exit(0); //

1-7//////

，選擇排序方式值為 1，直接插入排序值為2，冒泡法排序值為 3，快速排序值為4，直接選擇排序值為 5，堆排序值為6，歸并排序值為 7，結束程序}printf("Sortreult:");output_int(R);}實驗結果：Pleaseinputnum(int):10Plaseinput10integer:26530175112993786374269476438********Select**********InsertSortBubbleSortQ