数据结构实验报告答案

1、数据结构（C语言版）实验报告专业班级学号姓名实验1实验题目：单链表的插入和删除实验目的：了解和掌握线性式的逻辑结构和链式存储结构，掌握单链式的基本算法及相关的时间性能分析。实验要求：建立个数据域定义为字符串的单链表，在链表中不允许有重复的字符串：根据输入的字符串,先找到相应的结点，后删除之。实验主要步骤：1、分析、理解给出的示例程序。2、调试程序，并设计输入数据(如：battcat,eat,fht,hat,jat,lat»mat,#),测试程序的如下功能：不允许重复字符串的插入：根据输入的字符串，找到相应的结点并删除。3、修改程序：(1)增加插入结点的功能。(2)将建立链表的方法改为

2、头插入法。程序代码:#includestdio.h#includestriiig.h#includestdlib.h定义结点#inchidectype.htypedefstructnodechardata10;structnode*next;ListNode;结点的数据域为字符串结点的指针域npedef ListNode * LiiikList;LinkList CreatListRl();LinkList CreatList(void);ListNode *LocateNode();void DeleteList();void printlist();void DeleteAll();/:/

3、自定义LmkList单链表类型函数，用尾插入法建立带头结点的单链衣函数，用头插入法建立带头结点的单链表函数，按值查找结点函数，删除指定值的结点函数，打印链表中的所有值函数，删除所有结点，释放内存ListNode*AddNode():修改程序：增加节点。用头插法，返回头指针主函数,voidmain。charch10,num5;LiiikListhead:head=CreatList();用头插入法建立单链表，返回头指针prmtEst(head);遍历链及输出其值printsDeletenode(y/n):);/输入祜或混去选择是否删除结点scanf(%s,num);if(sticmp(num,y

4、)=O|strcmp(num,Y)=0)pnntf(PleaseinputDelete-data:);scanf(%s.ch);输入要删除的字符串DeleteList(head.ch);pnntlist(head);)prmtf(Addnode?(y/n):);输入祜或混去选择是否增加结点scanf(%s,num);if(strcixq)(num,y)=O|strcmp(num,Y)=O)(head=AddNode(head);)prmtlist(head);DeleteAll(head);删除所有结点，释放内存)=用尾插入法建立带头结点的单链表=LinkListCreatListRl(voi

5、d)(charch10;LinkListhead=(LinkList)malloc(sizeof(ListNode);生成头结点ListNode*s,*r.*pp:r=head;r->next=NULL;printf(Input#toend);输入?代表输入结束printf(PleaseinputNode_data:);scanf(%s,ch);输入各结点的字符串while(strcmp(ch,#)!=O)pp=LocateNode(head.ch)；按值查找结点，返回结点指针if(pp=NULL)没有重复的字符串，插入到链表中s=(ListNode*)malloc(sizeof(Lis

6、tNode);strcpy(s->data,ch):r->next=s;r=s;r->next=NULL;)printf(Inpiit#toend);pnntf(PleaseinputNode_data:);scanf(%sxh);returnhead;返回头指针)=用头插入法建立带头结点的单链表=LmkListCreatList(void)charch100;LiiikListhead,p;head=(LinkList)malloc(sizeof(ListNode);head->next=NULL;while(l)(printf(Input#toend);printf

7、(PleaseinputNode_data:);scanf(%sxh);if(strcmp(ch,#)if(LocateNode(liead,ch)=NULL)(strcpy(head->data,ch);p=(LmkList)malloc(sizeof(ListNode);p->next=head:head=p;)elsebreak;)returnhead:)/：按值查找结点，找到则返回该结点的位置，否则返回NULLListNode*LocateNode(LinkLi$thead,char*key)ListNode*p=head->next：从开始结点比较while(p!=

8、NULL&&strcmp(p->data,key)!=O)直至Up为NULL或p->data为keyll：p=p->next;扫描下一个结点returnp;若p=NULL则查找失败，否则p指向找到的值为key的结点)修改程序：增加节点=ListNode*AddNode(LinkListhead)charch10;ListNode*s.*pp:printf(PleaseinputaNewNode_data:);scanf(%s,ch);输入各结点的字符串pp=LocateNode(head.ch):按值查找结点，返回结点指针prmtf(ok2n);if(pp=N

9、ULL)没有重复的字符串，插入到链表中s=(ListNode*)malloc(sizeof(ListNode);strcpy(s->data、ch)：pnntf(okS'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)若没有找到结点，退出pnntf(positionerror);ex

10、it(O);)/p为要删除的结点，q为p的前结点lvhile(q->next!=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();)=删除所有结点，释放空间=voidDeleteAll(LiiikListhead)(ListNode*p=liead,*r;,vhile(p->

11、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#toen

12、dPleaseinputNode_data:matInput#toendPleaseinputNode_data:#mat,lat,jat,hat,fat,Deletenode(y/n):yPleaseinputDelete_data:hateat,cat,bat,mat,lat,jat,fat,eat,Insertnode(y/n):ycat,bat,PleaseinputInsert_data：putposition:5mat,lat,jat,fat,eat,put,cat,bat,请按任意键继续示意图：headbateatcatjathatfatmatlatNULLheadbatcatf

13、ateatmatlatjatNULLhatheadbatcatjatfateatlatmatNULLput心得体会：另外对链表的些基本操作也更加熟练了。本次实验使我们对链表的实质了解更加明确r,这使我们认识到实验过程中不能想当然的直接编实验指导书上给出的代码是有些问题的，译执行,应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。实验2实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作。实验主要步骤：1、分析、理解程序。2、调试

14、程序，设计棵二叉树，输入完全二叉树的先序序列，用#代衣虚结点(空指针)，如ABD#CE斜F附，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶广及结点总数。实验代码#includestdio.h#includestdlib.hwincludestriiighdefineMax20结点的最大个数typedefstructnodechardata;structnode*lchild,*rchild;BmTNode;自定义二叉树的结点类型n-pedefBmTNode*BinTree;/定义二叉树的指针intNodeNum.leaf;/NodeNum为结点数，leaf为叶上数/=基于先序遍

15、历算法创建二叉树=要求输入先序序列，其中加入虚结点？以示空指针的位置=BmTreeCreatBinTree(void)BuiTreeT;charch;if(ch=getchai()='#')reUim(NULL);读入#,返回空指针elseT=(BinTNode*)malloc(3izeof(BinTNode);生成结点T->data=ch;构造左广树构造右子树T->lchild=CreatBinTree();T->rchild=CreatBmTreeO：reUim(T);)/=NLR先序遍历voidPreorder(BinTreeT)if(T)printf(

16、%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->lcluld);Po$torder(T->rchild);prmtf(%c,T->

17、;data);)后序遍历左子树后序遍历右子树访问结点=采用后序遍历求二叉树的深度、结点数及叶广数的递归算法intTreeDepth(BmTreeT)inthlliraiiax:if(T)lil=TreeDepth(T->lcliild);求左深度hr=TreeDepth(T->rcliild);求右深度niax=lil>lir?hl:lir;取左右深度的最大值NodeNum=NodeNiun+1;求结点数if(lil=O&&lir=O)leaMeaf+1;若左右深度为0,即为叶0remrn(max+l);)elseretiini(O);)=利用先进先出(FIF

18、O)队列，按层次遍历二叉树=voidLevelorder(BinTreeT)intfront=0.rear=l;BmTNode*cqMax.*p;定义结点的指针数组cqcql=T;/根入队while(front!=rear)(front=(front+l)%NodeNum;p=cqfront;出队pnntf(%c,p->data);出队，输出结点的值if(p->lcluld!=NULL)rear=(rear+l)%NodeNiun:cqrear=p->lchild;左子树入队)if(p->rcluld!=NULL)rear=(rear+l)%NodeNiun:cqrea

19、r=p->rcliild;右子树入队)=数叶子节点个数=intcountleaf(BinTieeT)mthl.hr;if(T)hl=countleaf(T->lchild);lir=countleaf(T->rchild);if(lil=O&&lir=O)若左右深度为0,即为叶九renirn(l);elsereturnhl+hr:elsereturn0;)/=±函数=voidmain。BinTreeroot;chari;intdepth;printf();pnntf(CreatBin_Tree：Inputpreorder:);输入完全二叉树的先序序列

20、,用#代表虚结点，如root=CreatBmTree();创建二叉树，返回根结点do从菜单中选择遍历方式，输入序号。printg*select*Qyprintf(1:PreorderTraversabn);printf(2:lorderTraversal'n);printf(3:Postordertraversaln);pnntf(4:PostTreeDepth,Nodenumber,LeafnumberVn);prmtfC'.5:LevelDepth'g);按层次遍历之前，先选择4,求出该树的结点数。printf(0:Exit'm);printf*fflush

21、(stdin);scanf(%c,&i);输入菜单序号(0-5)switch(i-'0')case 1: printf(PrintBiii_treePreorder:);Preorder(root);先序遍历break:case 2: printf(PrintBin_TreeInorder:);Inorder(root);中序遍历breakcase 3: printf(PrintBin_TreePostorder:);Postorder(root);后序遍历breakcase4:depth=TreeDq)th(root);求树的深度及叶子数printf(BiiiTree

22、Depth=%dBinTreeNodenumber=%d.depth,NodeNum);pnntf(BinTreeLeafnumber=%d,coiuitleaf(root);break:case5:printf(Le-ePrmtBin_Tree:);Le-elorder(root);按层次遍历break:default:exit(l);)printf();vhile(i!=0);)实验结果：CreatBin-Tree：Inputpreorder:ABD#CE#F#*select*1: PreorderTraversal2: lorderTraversal3: Postordertravers

23、al4: PostTreeDeptKNodenumber,Leafnumber5: LevelDepth0:Exit*1PrintBin_treePreorder:ABDCEFPrintBm_TreeInorder:DBAECF3PrintBin_TreePostorder:DBEFCA4BinTreeDepth=3BinTreeNodenumber=6BinTreeLeafnumber=35LevePrintBinTree:ABCDEF0ACBFDE心得体会：同时这次实验加深了我对二叉树的印象,尤其是对二叉树的各种遍历操作有了定的/解。认识到，在设计程序时辅以图形化的描述是非常有用处的。实验

24、3实验题目：图的遍历操作实验目的：掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构：掌握DFS及BFS对图的遍历操作：了解图结构在人工智能、工程等领域的广泛应用。实验要求：采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。实验主要步骤：设计个有向图和个无向图，任选种存储结构，完成有向图和无向图的DFS（深度优先通历）和BFS（广度优先遍历）的操作。1.邻接矩阵作为存储结构Sincludestdio.hSincludestdlib.hdefineMaxVertexNum100定义最大顶点数typedefstructcharvexsMaxVertexN

25、um;/顶点表intedgesMaxVertexNumMaxVertexNum;邻接矩阵，可看作边表intn,e;/图中的顶点数n和边数eMGraph;/用邻接矩阵表示的图的类型=建立邻接矩阵=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(

26、%c,&a);G->vexsi=a;/读入顶点信息，建立顶点表for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)G->edgesij=0;/初始化邻接矩阵printf(Inputedges,CreatAdjacencyMatrix");for(k=0;k<G->e;k+)读入e条边，建立邻接矩阵scanf(%d%d,&i,&j);输入边(Vi,Vj)的顶点序号G->edgesij=l;G-edgesji=l;若为无向图,矩阵为对称矩阵：若建立有向图,去掉该条语句=定义标志向量，为全局变

27、量=typedefenumFALSE,TRUEBoolean;BooleanvisitedMaxVertexNum;=DFS：深度优先遍历的递归算法=voidDFSM(MGraph*G,inti)以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0,1矩阵intj;printf (%c, G->vexsi); visitedi=TRUE;for(j=0;j<G->n;j+)if (G->edgesi j-1 && !访问顶点Vi置已访问标志依次搜索Vi的邻接点 visitedCj)DFSM (G, j);void DFS(MGraph *G)(

28、int i;for(i=0;i<G->n;i+) visitedi=FALSE;for(i=0;i<G->n;i+) if(!visitedi)DFSM(G, i);r=r+l; cqr>j;/访问过Vj入队/(Vi,Vj)WE,且Vj未访问过，故Vj为新出发点标志向量初始化/Vi未访问过/以Vi为源点开始DFS搜索=BFS：广度优先遍历=voidBFS(MGraph*G,intk)以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索intifj,f=0,r=0;intcqMaxVertexNum;定义队列for(i=0;i<G->n;i+)visite

29、di=FALSE;标志向量初始化for(i=0;i<G->n;i+)cqi=-l；队列初始化printf(%c,G->vexsk);访问源点Vkvisitedk=TRUE;cqr=k;/Vk已访问，将其入队。注意，实际上是将其序号入队while(cqf!=-1)队非空则执行i=cqf;Vf出队for(j=0;j<G->n;j+)依次Vi的邻接点Vjif(G->edgesij=l&&!visitedtj)/Vj未访问printf(%c,G->vexsj);访问Vjvisitedj=TRUE;/=main=:voidmainOinti;MG

30、raph*G;G=(MGraph*)malloc(sizeof(MGraph);为图G申请内存空间CreatMGraph(G);建立邻接矩阵printf(PrintGraphDFS:);DFS(G);深度优先遍历printf();printf(PrintGraphBFS:);BFS(G,3);/以序号为3的顶点开始广度优先遍历printf();)2.邻接链表作为存储结构Sincludestdio. hSincludestdlib. hdefine MaxVertexNum 50 typedef struct node int adjvex;struct node *next;EdgeNode;

31、typedef struct vnode char vertex;EdgeNode *firstedge;VertexNode;/定义最大顶点数边表结点邻接点域链域顶点及结点顶点域边表头指针typedefVertexNodeAdjListiMaxVertexNum;/AdjList是邻接表类型typedefstructAdjListadjlist;邻接表intn,e;图中当前顶点数和边数ALGraph;图类型/=建立图的邻接表=voidCreatALGraph(ALGraph*G)inti,j,k;chara;EdgeNode*s;定义边表结点printf(InputVertexNum(n)a

32、ndEdgesNum(e):);scanf(%d,%d,&G->n,&G->e);读入顶点数和边数scanf(%c,&a);printf(InputVertexstring:);for(i=0;i<G->n;i+)建立边表scanf(%c,&a);G->adjlisti.vertex=a;读入顶点信息G->adjlisti.firstedge=NULL;/边表置为空表printf(Inputedges,CreatAdjacencyListn);for(k=0;k<G->e;k+)/建立边表scanf(%d%d,&a

33、mp;i,&j);读入边(Vi,Vj)的顶点对序号s=(EdgeNode*)malloc(sizeof(EdgeNode);生成边表结点s->adjvex=j;邻接点序号为js->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;将新结点*S插入顶点Vi的边表头部s=(EdgeNode*)malloc(sizeof(EdgeNode);s->adjvex=i;/邻接点序号为is->next=G->adjlistj.firstedge;G->adjlistj.firstedge=s;将新结

34、点*S插入顶点Vj的边表头部=定义标志向量，为全局变量=typedefenumFALSE,TRUEBoolean;BooleanvisitedMaxVertexNum;=DFS：深度优先遍历的递归算法=voidDFSM(ALGraph*G,inti)以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode*p;printf(%c,G->adjlisti.vertex);访问顶点Vip=G->adjlisti. firstedge; while(p) if(! visitedp->adjvex)DFSM(G, p->adjvex);p=p->next;vis

35、itedi=TRUE;标记Vi已访问取Vi边式的头指针/依次搜索Vi的邻接点Vj,这里j=p->adjvex若Vj尚未被访问则以Vj为出发点向纵深搜索找Vi的下个邻接点voidDFS(ALGraph*G)(inti;标志向量初始化/Vi未访问过for(i=0;i<G->n;i+)visitedi=FALSE;for(i=0;i<G->n;i+)if(!visitedi)DFSM(G, i);以Vi为源点开始DFS搜索/=BFS：广度优先遍历=voidBFS(ALGraph*G,intk)以Vk为源点对用邻接链表表示的图G进行广度优先搜索inti,f=0,r=0;E

36、dgeNode*p;intcqMaxVertexXum;/定义FIFO队列for(i=0;i<G->n;i+)visitedi=FALSE;/标志向量初始化for(i=0;i<=G->n;i+)cqi=-l;初始化标志向量printf(%c,G->adjlistk.vertex);访问源点Vkvisitedk=TRUE;cqr=k;Vk已访问，将其入队。注意，实际上是将其序号入队while(cqf!=-1)队列非空则执行i=cqf;Vi出队p=G->adjlisti.firstedge;/取Vi的边表头指针while(p)依次搜索Vi的邻接点Vj(令p-&g

37、t;adjvex=j)if(!visitedp->adjvex)若Vj未访问过printf(%c,G->adjlistp->adjvex.vertex);/访问VjvisitedLp->adjvex=TRUE;r=r+l;cqr=p->adjvex;访问过的Vj入队p=p->next;/找Vi的下个邻接点/endwhile=主函数=voidmainO(inti;ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph);CreatALGraph(G);printf(PrintGraphDFS:);DFS(G);printf()；

38、printf(PrintGraphBFS:);BFS(G,3);printf()；实验结果：1 .邻接矩阵作为存储结构执行顺序：InputVertexNum(n)andEdgesNum(e):9voInputVertexstring:01234567V2viInputedges,CreatAdjacencyMatrix01V302V4V5V62 33 44 5V75 66 74756PrintGraphDFS:01374256PrintGraphBFS:317042562.邻接链表作为存储结构执行顺序:9,InputVertexNum(n)andEdgesNum(e):8InputVertex

39、string:01234567Inputedges,CreatAdjacencyListvo0102v2vi13V314V4V5V64 7v75 6PrintGraphDFS:02651473PrintGraphBFS:37140265心得体会：这次实验较以前的实验难度加大，必须先理解深度优先和广度优先两种遍历思路，和数据结构中队列的基本操作，才能看懂理解代码。同时图这种数据结构对抽象的能力要求非常高，代码不容易看懂，排错也比较麻烦，应该多加练习，才能掌握。实验4实验题目：排序实验目的:掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适

40、的排序方法。实验要求：实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。实验主要步骤:实验代码Sincludestdio.hSincludestdlib. h define Max 100 typedef struct int key;RecType;/假设文件长度/定义记录类型/关键字项typedefRecTypeSeqList;/SeqList为顺序表，表中第0个元素作为哨兵intn;顺序表实际的长度=直接插入排序法=voidInsertSort(SeqListR)对顺序表R中的记录R1-n按递增序进行插入排序inti,j;for(i=2;i<=n;i+)

41、/依次插入R2,Rnif(Ril.key<Ri-l.key)若Ri.key大于等于有序区中所有的keys,则Ri留在原位RO=Ri;j=i-l;/R0是Ri的副本do从右向左在有序区1中查找Ri的位置Rj+l=Rj;将关键字大于REil.key的记录后移while(R0.key<Rj.key);当Ri.key>Rj.key是终止Rj+1=RO;Ri插入到正确的位置上/endif/=冒泡排序=typedefenumFALSE,TRUEBoolean;/FALSE为0,TRUE为1voidBubbleSort(SeqListR)自下向上扫描对R做冒泡排序inti,j;Boolea

42、nexchange;交换标志for(i=l;i<n;i+)最多做n-l趟排序exchange=FALSE;本趟排序开始前，交换标志应为假for(j=n-l;j>=i;j)对当前无序区Ri自下向上扫描ifkey<Rj.key)两两比较，满足条件交换记录RO=Rj+lJ;Rj+l=Rj;Rj=RO;exchange=TRUE;if(! exchange)/R0不是哨兵,仅做暂存单元发生了交换，故将交换标志置为真/本趟排序未发生交换，提前终止算法return;/endfor(为循环)/I.=次划分函数=intPartition(SeqListR,inti,intj)/对做一次划分，

43、并返回基准记录的位置RecTypepivot=Ri;/用第一个记录作为基准while(i<j)/从区间两端交替向中间扫描，直到i=jwhile(i<jkey>=pivot.key)基准记录pivot相当与在位置i上j；从右向左扫描，查找第个关键字小于pivot,key的记录Rjif(i<j)若找到的Rj.key<pivot.key,则Ri+=Rj；交换R和Rj,交换后i指针加1while(i<j.key<=pivot.key)基准记录pivot相当与在位置j上i+；从左向右扫描，查找第个关键字小于pivot,key的记录Riif(i<j)/若找到

44、的Ri.key>pivot,key,则RjT=Ri；交换Ri和Rj，交换后j指针减1Ri=pivot;此时，i=j,基准记录已被最后定位returni;返回基准记录的位置/2.=快速排序=voidQuicksort(SeqListR,intlow,inthigh)/Rlow.,high快速排序intpivotpos;划分后基准记录的位置if(low<high)仅当区间长度大于1时才排序pivotpos=Partition(R,low,high);/对Rlow.high做,次划分，得到基准记录的位置Quicksort(R,low,pivotpos-1);/对左区间递归排序对右区间递归

45、排序Quicksort(R,pivotpos+1,high);/=宜接选择排序=voidSelectSort(SeqListR)(intfor(i=l;i<n;i+)/做第i趟排序(iWiWnT)k=i;for(j=i+l;j<=n;j+)在当前无序区Ri-n中选key最小的记录Rkif(Rj.key<Rk.key)k=j;/k记下目前找到的最小关键字所在的位置if(k!=i)/交换Ri和RkR0=Ri;Ri=Rk;Rk=RLO;/endif/endfor/=大根堆调整函数=voidHeapify(SeqListR,intlow,inthigh)将Rlow.high调整为大根

46、堆，除Rlow外，其余结点均满足堆性质intlarge;/large指向调整结点的左、右孩子结点中关键字较大者RecTypetemp=Rlow;暂存调整结点for(large=2*low;large<=high;large*=2)/Rlow是当前调整结点若large>high,则表示RlowJ是叶子，调整结束：否则先令large指向Rlow的左孩子if(large<high&&Rlarge.key<Rlargel.key)large+;若Rlow的右孩子存在且关键字大于左兄弟，则令large指向它/现在Rlarge是调整结点Rlow的左右孩子结点中关键字

47、较大者if(temp.key>=Rlarge.key)/temp始终对应Rlowbreak;当前调整结点不小于其孩子结点的关键字，结束调整Rlow=RlargeZ;/相当于交换Rlow和Rlargelow=large;/令low指向新的调整结点，相当于temp已筛下到large的位置Rlow=temp;/将被调整结点放入最终位置上/=构造大根堆=voidBuildHeap(SeqListR)/将初始文件RL.n构造为堆inti;for(i=n/2;i>0;i)Heapify (R, i, n);/将Ri.n调整为大根堆/=堆排序=voidHeapSort(SeqListR)/对进行

48、堆排序，不妨用R0做暂存单元inti;BuildHeap(R);将Rl.n构造为初始大根堆for(i=n;i>l;i)对当前无序区Rl.i进行堆排序，共做n-l趟。RO=R1;Rl=Ri;Ri=R0;将堆顶和堆中最后个记录交换Heapify(R,1,i-1);/将Rl.i-1重新调整为堆,仅有Rl可能违反堆性质。/=将两个有序的子序列Rlow.m和Rm+1.high归并成有序的序列Rlow.high>=voidMerge(SeqListR,intlow,intm»inthigh)(inti=low,j=m+l,p=0;置初始值RecType*R1;/RI为局部量Rl=(R

49、ecType*)malloc(high-low+1)*sizeof(RecType);申请空间while(i<=m&&j<=high)/两个子序列非空时取其小者输出到Rlp上RIp+=(Ri.key<=Rj.key)?Ri+:Rj+;while(i<=m)若第个子序列非空，则复制剩余记录到RIRlp+=Ri+;while(j<=high)若第二个子序列非空，则复制剩余记录到RI中Rlp+=Rj+;for(p=0,i=low;i<=high;i+)Ri=Rlp;/归并完成后将结果复制回RElow.high，7=对RL.n做,趟归并排序=void

50、MergePass(SeqListR,intlength)(inti;for(i=l;i+2*length-l<=n;i=i+2*length)Merge(R,i,i+length-1,i+2*length-l);/归并长度为length的两个相邻的子序列if(i+length-l<n)尚有个子序列，其中后个长度小于lengthMerge(R,i,i+length-1,n);归并最后两个子序列注意：若iWn且i+length-12n时，则剩余个子序列轮空，无须归并/=自底向上对Rl.n做二路归并排序=voidMergeSort(SeqListR)intlength;/做Ign趟排序

51、for(length=l;length<n;length*=2)MergePass(R,length);有序长度2n时终止=目谕入顺序&=voidinput_int(SeqListR)(inti;printf(Pleaseinputnum(int):);scanf(%d,&n);printf(Plaseinput%dinteger:,n);for(i=l;i<=n;i+)scanf(%d,&Ri.key);/=输出顺序表=voidoutput_int(SeqListR)(inti;for(i=l;i<=n;i+)printf(M,Ri.key);/=主

52、函数=voidmainO(inti;SeqListR;input_int(R);printf(*Select*n);printf(1:InsertSortn);printf(2:BubbleSortn);printf(3:QuickSortn);printf(4:StraightSelectionSortn);printf(5:HeapSortn);printf(6:MergeSortn);printf(7:Exitn);printf(*");scanf(%d,&i);输入整数1-7,选择排序方式switch(i)case1:InsertSort(R);break;值为1,直接插入排序case2:BubbleSort(R);break;/值为2,冒泡法排序值为3,快速排序/值为4,直接选择排序值为5,堆排序值为6,归并排序值为7,结束程