数据结构实验报告-答案

数据结构实验报告---答案'.数据结构(C语言版)实验报告数据结构实验报告---答案全文共25页，当前为第1页。数据结构实验报告---答案全文共25页，当前为第1页。专业班级学号姓名实验1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。实验主要步骤：分析、理解给出的示例程序。调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。修改程序：增加插入结点的功能。将建立链表的方法改为头插入法。程序代码:#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();//函数，打印链表中的所有值数据结构实验报告---答案全文共25页，当前为第2页。数据结构实验报告---答案全文共25页，当前为第2页。ListNode*AddNode(); //修改程序：增加节点。用头插法，返回头指针//==========主函数==============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);//按值查找结点，返回结点指针 数据结构实验报告---答案全文共25页，当前为第3页。 if(pp==NULL){数据结构实验报告---答案全文共25页，当前为第3页。 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; } } else break; } returnhead;}数据结构实验报告---答案全文共25页，当前为第4页。//==数据结构实验报告---答案全文共25页，当前为第4页。ListNode*LocateNode(LinkListhead,char*key){ListNode*p=head->next;//从开始结点比较while(p!=NULL&&strcmp(p->data,key)!=0)//直到p为NULL或p->data为key止 p=p->next;//扫描下一个结点returnp;//若p=NULL则查找失败，否则p指向找到的值为key的结点}//==========修改程序：增加节点=======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的前结点数据结构实验报告---答案全文共25页，当前为第5页。 q=q-数据结构实验报告---答案全文共25页，当前为第5页。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:put数据结构实验报告---答案全文共25页，当前为第6页。position:数据结构实验报告---答案全文共25页，当前为第6页。mat,lat,jat,fat,eat,put,cat,bat,请按任意键继续...示意图：latlatjathatfateatcatbatmatNULLheadlatjathatfateatcatbatmatheadlatjatfateatputcatbatmatheadNULLNULL心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。数据结构实验报告---答案全文共25页，当前为第7页。

实验2数据结构实验报告---答案全文共25页，当前为第7页。实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。实验主要步骤：分析、理解程序。调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如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为叶子数//==========基于先序遍历算法创建二叉树==============//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========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);}数据结构实验报告---答案全文共25页，当前为第8页。}数据结构实验报告---答案全文共25页，当前为第8页。//========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)数据结构实验报告---答案全文共25页，当前为第9页。{数据结构实验报告---答案全文共25页，当前为第9页。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;//右子树入队 }}}//====数叶子节点个数==========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();//创建二叉树，返回根结点数据结构实验报告---答案全文共25页，当前为第10页。do{//从菜单中选择遍历方式，输入序号。数据结构实验报告---答案全文共25页，当前为第10页。 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=%dBinTreeNodenumber=%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************1:PreorderTraversal2:IorderTraversal3:Postordertraversal数据结构实验报告---答案全文共25页，当前为第11页。4:PostTreeDepth,Nodenumber,Leafnumber数据结构实验报告---答案全文共25页，当前为第11页。5:LevelDepth0:Exit*******************************1PrintBin_treePreorder:ABDCEF2PrintBin_TreeInorder:DBAECF3PrintBin_TreePostorder:DBEFCA4BinTreeDepth=3BinTreeNodenumber=6BinTreeLeafnumber=35LevePrintBin_Tree:ABCDEF0Pressanykeytocontinue二叉树示意图AABFEDC心得体会：这次实验加深了我对二叉树的印象，尤其是对二叉树的各种遍历操作有了一定的了解。同时认识到，在设计程序时辅以图形化的描述是非常有用处的。数据结构实验报告---答案全文共25页，当前为第12页。

实验3数据结构实验报告---答案全文共25页，当前为第12页。实验题目：图的遍历操作实验目的：掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。实验要求：采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。实验主要步骤：设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。邻接矩阵作为存储结构#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100//定义最大顶点数typedefstruct{charvexs[MaxVertexNum];//顶点表intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表intn,e;//图中的顶点数n和边数e}MGraph;//用邻接矩阵表示的图的类型//=========建立邻接矩阵=======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条边，建立邻接矩阵数据结构实验报告---答案全文共25页，当前为第13页。 scanf("%d%d",&i,&j);//输入边（Vi，Vj）的顶点序号数据结构实验报告---答案全文共25页，当前为第13页。 G->edges[i][j]=1; G->edges[j][i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句}}//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voidDFSM(MGraph*G,inti){//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵intj;printf("%c",G->vexs[i]);//访问顶点Vivisited[i]=TRUE;//置已访问标志for(j=0;j<G->n;j++)//依次搜索Vi的邻接点 if(G->edges[i][j]==1&&!visited[j]) DFSM(G,j);//（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点}voidDFS(MGraph*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：广度优先遍历=======voidBFS(MGraph*G,intk){//以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索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){//队非空则执行 i=cq[f];f=f+1;//Vf出队 for(j=0;j<G->n;j++)//依次Vi的邻接点Vj if(G->edges[i][j]==1&&!visited[j]){//Vj未访问 printf("%c",G->vexs[j]);//访问Vj数据结构实验报告---答案全文共25页，当前为第14页。 visited[j]=TRUE;

r=r+1;cq[r]=j;//访问过Vj入队数据结构实验报告---答案全文共25页，当前为第14页。 }}}//==========main=====voidmain(){inti;MGraph*G;G=(MGraph*)malloc(sizeof(MGraph));//为图G申请内存空间CreatMGraph(G);//建立邻接矩阵printf("PrintGraphDFS:");DFS(G);//深度优先遍历printf("\n");printf("PrintGraphBFS:");BFS(G,3);//以序号为3的顶点开始广度优先遍历printf("\n");}邻接链表作为存储结构#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum50//定义最大顶点数typedefstructnode{//边表结点intadjvex;//邻接点域structnode*next;//链域}EdgeNode;typedefstructvnode{//顶点表结点charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中当前顶点数和边数}ALGraph;//图类型//=========建立图的邻接表=======voidCreatALGraph(ALGraph*G){inti,j,k;chara;EdgeNode*s;//定义边表结点printf("InputVertexNum(n)andEdgesNum(e):");数据结构实验报告---答案全文共25页，当前为第15页。scanf("%d,%d",&G->n,&G->e);//读入顶点数和边数数据结构实验报告---答案全文共25页，当前为第15页。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;//邻接点序号为j s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s;//将新结点*S插入顶点Vi的边表头部 s=(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex=i;//邻接点序号为i s->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=s;//将新结点*S插入顶点Vj的边表头部}}//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voidDFSM(ALGraph*G,inti){//以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode*p;printf("%c",G->adjlist[i].vertex);//访问顶点Vivisited[i]=TRUE;//标记Vi已访问p=G->adjlist[i].firstedge;//取Vi边表的头指针while(p){//依次搜索Vi的邻接点Vj，这里j=p->adjvex if(!visited[p->adjvex])//若Vj尚未被访问 DFSM(G,p->adjvex);//则以Vj为出发点向纵深搜索 p=p->next;//找Vi的下一个邻接点}}voidDFS(ALGraph*G){inti;for(i=0;i<G->n;i++) visited[i]=FALSE;//标志向量初始化for(i=0;i<G->n;i++)数据结构实验报告---答案全文共25页，当前为第16页。 if(!visited[i])//Vi未访问过

DFSM(G,i);//以Vi为源点开始DFS搜索

}

//==========BFS：广度优先遍历=========数据结构实验报告---答案全文共25页，当前为第16页。voidBFS(ALGraph*G,intk)

{//以Vk为源点对用邻接链表表示的图G进行广度优先搜索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){队列非空则执行 i=cq[f];f=f+1;//Vi出队 p=G->adjlist[i].firstedge;//取Vi的边表头指针 while(p){//依次搜索Vi的邻接点Vj（令p->adjvex=j） if(!visited[p->adjvex]){//若Vj未访问过 printf("%c",G->adjlist[p->adjvex].vertex);//访问Vj visited[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");}数据结构实验报告---答案全文共25页，当前为第17页。数据结构实验报告---答案全文共25页，当前为第17页。实验结果：邻接矩阵作为存储结构执行顺序：V6V4V5V6V4V5V7V2V3V1V0VoInputVertexstring:01234567Inputedges,CreatAdjacencyMatrix010213142526374756PrintGraphDFS:01374256PrintGraphBFS:31704256邻接链表作为存储结构执行顺序：InputVertexNum(n)andEdgesNum(e):8，9InputVertexstring:01234567V6V4V5V7V6V4V5V7V2V3V1V0Vo010213142526374756PrintGraphDFS:02651473PrintGraphBFS:37140265心得体会：这次实验较以前的实验难度加大，必须先理解深度优先和广度优先两种遍历思路，和数据结构中队列的基本操作，才能看懂理解代码。同时图这种数据结构对抽象的能力要求非常高，代码不容易看懂，排错也比较麻烦，应该多加练习，才能掌握。数据结构实验报告---答案全文共25页，当前为第18页。

实验4数据结构实验报告---答案全文共25页，当前为第18页。实验题目：排序实验目的：掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。实验要求：实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。实验主要步骤：实验代码#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大于等于有序区中所有的keys，则R[i]留在原位 R[0]=R[i];j=i-1;//R[0]是R[i]的副本 do {//从右向左在有序区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}数据结构实验报告---答案全文共25页，当前为第19页。//==========冒泡排序=======数据结构实验报告---答案全文共25页，当前为第19页。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--)//对当前无序区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;//发生了交换，故将交换标志置为真 } if(!exchange)//本趟排序未发生交换，提前终止算法 return;}// endfor（为循环）}//1.========一次划分函数=====intPartition(SeqListR,inti,intj){//对R[i‥j]做一次划分，并返回基准记录的位置RecTypepivot=R[i];//用第一个记录作为基准while(i<j){//从区间两端交替向中间扫描，直到i=j while(i<j&&R[j].key>=pivot.key)//基准记录pivot相当与在位置i上 j--;//从右向左扫描，查找第一个关键字小于pivot.key的记录R[j] if(i<j)//若找到的R[j].key<pivot.key，则 R[i++]=R[j];//交换R[i]和R[j]，交换后i指针加1 while(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){//仅当区间长度大于1时才排序 pivotpos=Partition(R,low,high);//对R[low..high]做一次划分，得到基准记录的位置数据结构实验报告---答案全文共25页，当前为第20页。 QuickSort(R,low,pivotpos-1);//对左区间递归排序数据结构实验报告---答案全文共25页，当前为第20页。 QuickSort(R,pivotpos+1,high);//对右区间递归排序}}//======直接选择排序========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++)//在当前无序区R[i‥n]中选key最小的记录R[k] if(R[j].key<R[k].key) k=j;//k记下目前找到的最小关键字所在的位置 if(k!=i){////交换R[i]和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;数据结构实验报告---答案全文共25页，当前为第21页。for(i=n/2;i>0;i--)数据结构实验报告---答案全文共25页，当前为第21页。 Heapify(R,i,n);//将R[i..n]调整为大根堆}//==========堆排序===========voidHeapSort(SeqListR){//对R[1..n]进行堆排序，不妨用R[0]做暂存单元inti;BuildHeap(R);//将R[1..n]构造为初始大根堆for(i=n;i>1;i--){//对当前无序区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]上 R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];while(i<=m)//若第一个子序列非空，则复制剩余记录到R1 R1[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)//尚有一个子序列，其中后一个长度小于length Merge(R,i,i+length-1,n);//归并最后两个子序列//注意：若i≤n且i+length-1≥n时，则剩余一个子序列轮空，无须归并}//==========自底向上对R[1..n]做二路归并排序===============voidMergeSort(SeqListR){intlength;数据结构实验报告---答案全文共25页，当前为第22页。for(length=1;length<n;length*=2)//做[lgn]趟排序数据结构实验报告---答案全文共25页，当前为第22页。 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);//输入整数1-7，选择排序方式switch(i){ case1:InsertSort(R);break;//值为1，直接插入排序 case2:BubbleSort(R);break;//值为2，冒泡法排序 case3:QuickSort(R,1,n);break;//值为3，快速排序 case4:SelectSort(R);break;//值为4，直接选择排序 case5:HeapSort(R);break;//值为5，堆排序 case6:MergeSort(R);break;//值为6，归并排序 case7:exit(0);//值为7，结束程序数据结构实验报告---答案全文共25页，当前为第23页。}数据结构实验报告---答案全文共25页，当前为第23页。printf("Sortreult:");output_int(R);}实验结果：Pleaseinputnum(int):10Plaseinput10integer:26530175112993786374269476438********Select**********1:InsertSort