数据结构(C语言版)实验报告

数据结构（C语言版）实验报告学院计算机科学与技术专业计算机大类强化学号xxx班级xxx姓名xxx指导教师xxx实验1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性 能分析。实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的 字符串，先找到相应的结点，后删除之。实验主要步骤：1、分析、理解给出的示例程序。2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。3、修改程序：（1）增加插入结点的功能。（2）将建立链表的方法改为头插入法。程序代码:#includestdio.h”#includestring.h”#includestdlib.h”#includectype.h” typedef struct node char data10;struct node *next;ListNode;typedef ListNode * LinkList;LinkList CreatListR1();LinkList CreatList(void);ListNode *LocateNode(); void DeleteList(); void printlist();void DeleteAll();ListNode * AddNode();定义结点结点的数据域为字符串结点的指针域/自定义LinkList单链表类型函数，用尾插入法建立带头结点的单链表函数，用头插入法建立带头结点的单链表函数，按值查找结点函数，删除指定值的结点函数，打印链表中的所有值函数，删除所有结点，释放内存/修改程序：增加节点。用头插法，返回头指针/=主函数=void main() char ch10,num5;LinkList head; head=CreatList();用头插入法建立单链表，返回头指针printlist(head);遍历链表输出其值printf( Delete node (y/n):); 输入y或”n”去选择是否删除结点 scanf(%s,num); if(strcmp(num,y)=0 II strcmp(num,Y)=0) printf(Please input Delete_data:); scanf(%s”,ch);输入要删除的字符串DeleteList(head,ch); printlist(head); printf( Add node ? (y/n):); 输入y或”n”去选择是否增加结点 scanf(%s,num); if(strcmp(num,y)=0 II strcmp(num,Y)=0) head=AddNode(head); printlist(head); DeleteAll(head);删除所有结点，释放内存 1/=用尾插入法建立带头结点的单链表= LinkList CreatListRl(void) char ch10; LinkList head=(LinkList)malloc(sizeof(ListNode); /生成头结点 ListNode *s,*r,*pp; r=head; r-next=NULL; printf(Input # to end ); 输入#代表输入结束 printf(nPlease input Node_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 # to end );printf(Please input Node_data:);scanf(%s,ch);return head;/返回头指针/=用头插入法建立带头结点的单链表=LinkList CreatList(void) char ch100;LinkList head,p;head=(LinkList)malloc(sizeof(ListNode);head-next=NULL;while(1)printf(Input # to end );printf(Please input Node_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;return head;/=按值查找结点，找到则返回该结点的位置，否则返回NULL=ListNode *LocateNode(LinkList head, char *key) ListNode *p=head-next; /从开始结点比较while(p!=NULL & strcmp(p-data,key)!=0) 直到 p 为 NULL 或 p-data 为 key 止p=p-next;扫描下一个结点return p; /若p=NULL则查找失败，否则p指向找到的值为key的结点11=修改程序：增加节点= ListNode * AddNode(LinkList head) char ch10;ListNode *s,*pp;printf(nPlease input a New Node_data:);scanf(%s”,ch);输入各结点的字符串pp=LocateNode(head,ch);/按值查找结点，返回结点指针printf(ok2n);if(pp=NULL) 没有重复的字符串，插入到链表中s=(ListNode *)malloc(sizeof(ListNode); strcpy(s-data,ch); printf(ok3n); s-next=head-next; head-next=s;return head;/=删除带头结点的单链表中的指定结点= void DeleteList(LinkList head,char *key) ListNode *p,*r,*q=head;p=LocateNode(head,key);/按 key 值查找结点的if(p=NULL ) 若没有找到结点，退出printf(position error); exit(0);while(q-next!=p)/p为要删除的结点，q为p的前结点q=q-next;r=q-next;q-next=r-next;free(r);释放结点/=打印链表= void printlist(LinkList head)ListNode *p=head-next;从开始结点打印while(p)printf(%s, ,p-data);p=p-next;printf(n);/=删除所有结点，释放空间= void DeleteAll(LinkList head)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,Delete node(y/n):)iPlease inputDeletedata:hatmat, lat,jat,fat, eat,cat,bat,Insert node(y/n):iPlease inputInsertdata:putposition :5mat, lat,jat,fat, eat,put,cat,bat,请按任意键继续.示意图:headhead心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外 实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编 译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。实验2实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历 的操作，求所有叶子及结点总数的操作。实验主要步骤：1、分析、理解程序。2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针)， 如ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列， 求所有叶子及结点总数。实验代码#includestdio.h”#includestdlib.h”#includestring.h”#define Max 20结点的最大个数typedef struct node( char data; struct node *lchild,*rchild;BinTNode;自定义二叉树的结点类型typedef BinTNode *BinTree; 定义二叉树的指针 int NodeNum,leaf;/NodeNum 为结点数，leaf为叶子数11=基于先序遍历算法创建二叉树= /=要求输入先序序列，其中加入虚结点#以示空指针的位置= BinTree CreatBinTree(void) BinTree T;char ch;if(ch=getchar()=#)return(NULL);读入#，返回空指针else T= (BinTNode *)malloc(sizeof(BinTNode); /生成结点 T-data=ch;T-lchild=CreatBinTree();构造左子树T-rchild=CreatBinTree(); 构造右子树 return(T); /=NLR 先序遍历=void Preorder(BinTree T) if(T) printf(%c”,T-data); 访问结点Preorder(T-lchild);先序遍历左子树Preorder(T-rchild);先序遍历右子树/=lnr 中序遍历=void Inorder(BinTree T)if(T) Inorder(T-lchild);中序遍历左子树printf(%c”,T-data); 访问结点Inorder(T-rchild);中序遍历右子树/=lrn 后序遍历=void Postorder(BinTree T)if(T) Postorder(T-lchild);/后序遍历左子树Postorder(T-rchild);/后序遍历右子树printf(%c”,T-data);访问结点/=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=int TreeDepth(BinTree T)int hl,hr,max;if(T)hl=TreeDepth(T-lchild);求左深度hr=TreeDepth(T-rchild);求右深度max=hlhr? hl:hr;/取左右深度的最大值NodeNum=NodeNum+1;求结点数if(hl=0&hr=0) leaf=leaf+1; /若左右深度为 0，即为叶子。 return(max+1);else return(0);/=利用”先进先出”(FIFO)队列，按层次遍历二叉树=void Levelorder(BinTree T) int front=0,rear=1;BinTNode *cqMax,*p;定义结点的指针数组cqcq1=T;根入队while(front!=rear) front=(front+1)%NodeNum; p=cqfront;出队printf(%c”,p-data);出队，输出结点的值if(p-lchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-lchild;/左子树入队 if(p-rchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-rchild;/右子树入队 /=数叶子节点个数= int countleaf(BinTree T) int hl,hr; if(T) hl=countleaf(T-lchild); hr=countleaf(T-rchild); if(hl=0&hr=0) 若左右深度为0，即为叶子。 return(1); else return hl+hr; else return 0; /=主函数= void main() BinTree root; char i; int depth; printf(n); printf(Creat Bin_Tree； Input preorder:); /输入完全二叉树的先序序列， /用#代表虚结点，如ABD#CE#F# root=CreatBinTree();创建二叉树，返回根结点do 从菜单中选择遍历方式，输入序号。printf(t* select *n， printf(t1: Preorder Traversaln);printf(t2: Iorder Traversaln);printf(t3: Postorder traversaln);printf(t4: PostTreeDepth,Node number,Leaf numbern);printf(t5: Level Depthn); /按层次遍历之前，先选择4,求出该树的结点数。printf(t0: Exitn);printf(t*n);fflush(stdin);scanf(%c”,&i);输入菜单序号(0-5)switch (i-0)(case 1: printf(Print Bin_tree Preorder:);Preorder(root);/先序遍历break;case 2: printf(Print Bin_Tree Inorder:);Inorder(root);中序遍历break;case 3: printf(Print Bin_Tree Postorder: );Postorder(root); /后序遍历 break; case 4: depth=TreeDepth(root);求树的深度及叶子数printf(BinTree Depth=%d BinTree Node number=%d,depth,NodeNum); printf( BinTree Leaf number=%d,countleaf(root); break;case 5: printf(LevePrint Bin_Tree:);Levelorder(root);/按层次遍历break; default: exit(1); printf(n); while(i!=0); 实验结果:Creat Bin_Tree； Input preorder:ABD#CE#F#“ 个个个个个个个个个个select“ 个个个个个个个个个个个个1: Preorder Traversal2: Iorder Traversal3: Postorder traversal4: PostTreeDepth,Node number,Leaf number5: Level Depth0: Exit*1Print Bin_tree Preorder: ABDCEF2Print Bin_Tree Inorder: DBAECF3Print Bin_Tree Postorder: DBEFCA4BinTree Depth=3 BinTree Node number=6 BinTree Leaf number=35LevePrint Bin_Tree: ABCDEF0Press any key to continue二叉树示意图心得体会：这次实验加深了我对二叉树的印象，尤其是对二叉树的各种遍历操作有了一定的了解。同时 认识到，在设计程序时辅以图形化的描述是非常有用处的。实验3实验题目：图的遍历操作实验目的：掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS 及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。实验要求：采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操 作。实验主要步骤：设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS (深度优 先遍历)和BFS (广度优先遍历)的操作。1.邻接矩阵作为存储结构#includestdio.h”#includestdlib.h”#define MaxVertexNum 100/定义最大顶点数typedef structchar vexsMaxVertexNum;/顶点表int edgesMaxVertexNumMaxVertexNum;/邻接矩阵，可看作边表int n,e;/图中的顶点数n和边数eMGraph;/用邻接矩阵表示的图的类型/=建立邻接矩阵=void CreatMGraph(MGraph *G)int i,j,k;char a;printf(Input VertexNum(n) and EdgesNum(e):);scanf(%d,%d”,&G-n,&G-e);/输入顶点数和边数scanf(%c”,&a);printf(Input Vertex string:);for(i=0;iG-n;i+)scanf(%c”,&a);G-vexsi=a;/读入顶点信息，建立顶点表for(i=0;iG-n;i+)for(j=0;jn;j+)G-edgesij=0;/初始化邻接矩阵printf(Input edges,Creat Adjacency Matrixn);for(k=0;ke;k+) /读入e条边，建立邻接矩阵scanf(%d%d”,&i,&j);/输入边(Vi，Vj)的顶点序号G-edgesij=1;G-edgesji=1; /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 /=定义标志向量，为全局变量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS :深度优先遍历的递归算法=void DFSM(MGraph *G,int i) 以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 int j;/访问顶点Vi/置已访问标志/依次搜索Vi的邻接点visitedj)/ (Vi, Vj)GE，且Vj未访问过，故Vj为新出发点printf(%c”,G-vexsi);visitedi=TRUE;for(j=0;jn;j+) if(G-edgesij=1 & !DFSM(G,j);void DFS(MGraph *G)int i;for(i=0;in;i+)/标志向量初始化/Vi未访问过/以Vi为源点开始DFS搜索visitedi=FALSE;for(i=0;in;i+)if(!visitedi)DFSM(G,i);/=BFS:广度优先遍历=void BFS(MGraph *G,int k)以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索int i,j,f=0,r=0;/定义队列int cqMaxVertexNum;for(i=0;in;i+)/标志向量初始化visitedi=FALSE;for(i=0;in;i+)队列初始化/访问源点Vkcqi=-1;printf(%c”,G-vexsk);visitedk=TRUE;/Vk已访问，将其入队。注意，实际上是将其序号入队/队非空则执行/Vf出队/依次Vi的邻接点Vjcqr=k;while(cqf!=-1) i=cqf; f=f+1;for(j=0;jn;j+)if(G-edgesij=1 & !visitedj) /Vj 未访问printf(%c,G-vexsj);/访问 Vjvisitedj=TRUE;r=r+1; cqr=j;/=main=void main()int i;MGraph *G;G=(MGraph *)malloc(sizeof(MGraph);/为图 G 申请内存空间CreatMGraph(G);/建立邻接矩阵printf(Print Graph DFS:);DFS(G);/深度优先遍历printf(n)；printf(Print Graph BFS:);BFS(G,3);/以序号为3的顶点开始广度优先遍历printf(n)；2.邻接链表作为存储结构#includestdio.h”#includestdlib.h”#define MaxVertexNum 50 typedef struct node int adjvex;struct node *next;EdgeNode;typedef struct vnode char vertex;EdgeNode *firstedge;/定义最大顶点数/边表结点邻接点域/链域/顶点表结点/顶点域边表头指针VertexNode;/AdjList是邻接表类型typedef VertexNode AdjListMaxVertexNum;typedef struct /邻接表图中当前顶点数和边数/图类型AdjList adjlist;int n,e; ALGraph;/=建立图的邻接表 void CreatALGraph(ALGraph *G) int i,j,k;char a;EdgeNode *s;/定义边表结点printf(Input VertexNum(n) and EdgesNum(e):);scanf(%d,%d”,&G-n,&G-e);/读入顶点数和边数scanf(%c”,&a);printf(Input Vertex string:);for(i=0;in;i+)/建立边表scanf(%c”,&a);G-adjlisti.vertex=a;/读入顶点信息G-adjlisti.firstedge=NULL; /边表置为空表printf(Input edges,Creat Adjacency Listn);for(k=0;ke;k+)/建立边表scanf(%d%d”,&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;/将新结点*S插入顶点Vj的边表头部/=定义标志向量，为全局变量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS :深度优先遍历的递归算法=void DFSM(ALGraph *G,int i)/以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode *p;printf(%c”,G-adjlisti.vertex);visitedi=TRUE;p=G-adjlisti.firstedge;while(p) if(! visitedp-adjvex) DFSM(G,p-adjvex);p=p-next;void DFS(ALGraph *G)int i;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+) if(!visitedi)/访问顶点Vi/标记Vi已访问/取 Vi边表的头指针/依次搜索Vi的邻接点Vj，这里j=p-adjvex/若 Vj尚未被访问则以Vj为出发点向纵深搜索/找Vi的下一个邻接点/标志向量初始化/Vi未访问过DFSM(G,i);/以Vi为源点开始DFS搜索BFS：广度优先遍历void BFS(ALGraph *G,int k) int i,f=0,r=0;EdgeNode *p;int cqMaxVertexNum;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+)以Vk为源点对用邻接链表表示的图G进行广度优先搜索/定义FIFO队列/标志向量初始化cqi=-1;/初始化标志向量printf(%c”,G-adjlistk.vertex); /访问源点 Vk visitedk=TRUE;cqr=k;/Vk已访问，将其入队。注意，实际上是将其序号入队while(cqf!=-1) 队列非空则执行i=cqf; f=f+1;/Vi 出队p=G-adjlisti.firstedge;/取 Vi 的边表头指针while(p) /依次搜索 Vi 的邻接点 Vj (令 p-adjvex=j)if(!visitedp-adjvex) /若Vj 未访问过printf(%c”,G-adjlistp-adjvex.vertex);/访问 Vjvisitedp-adjvex=TRUE;r=r+1; cqr=p-adjvex;/访问过的Vj入队p=p-next;/找Vi的下一个邻接点/endwhile/=主函数=void main()int i;ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph);CreatALGraph(G);printf(Print Graph DFS:);DFS(G);printf(n)；printf(Print Graph BFS:);BFS(G,3);printf(n)；实验结果：1.邻接矩阵作为存储结构 执行顺序：Input VertexNum(n) and EdgesNum(e): 8, 9Input Vertex string: 01234567Input edges,Creat Adjacency Matrix8，90 10 21 31 42 52 63 7vQvQ4 75 6Print Graph DFS: 01374256Print Graph BFS: 317042562.邻接链表作为存储结构执行顺序：Input VertexNum(n) and EdgesNum(e): 8，9Input Vertex string: 01234567Input edges,Creat Adjacency List0 1-VO0 21 31 42 52 63 74 75 6Print Graph DFS: 02651473Print Graph BFS: 37140265心得体会：这次实验较以前的实验难度加大，必须先理解深度优先和广度优先两种遍历思路，和数据结 构中队列的基本操作，才能看懂理解代码。同时图这种数据结构对抽象的能力要求非常高， 代码不容易看懂，排错也比较麻烦，应该多加练习，才能掌握。实验4实验题目：排序实验目的：掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析， 根据实际问题的特点和要求选择合适的排序方法。实验要求：实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。实验主要步骤:实验代码 #includestdio.h”#includestdlib.h”/假设文件长度/定义记录类型/关键字项#define Max 100typedef struct int key;RecType;typedef RecType SeqListMax+1; /SeqList为顺序表，表中第0个元素作为哨兵 int n;/顺序表实际的长度/=直接插入排序法= void InsertSort(SeqList R) 对顺序表R中的记录R1-n按递增序进行插入排序int i,j; for(i=2;i=n;i+)/依次插入 R2, , Rnif(Ri.keyRi-1.key) /若 Ri.key 大于等于有序区中所有的 keys，则 Ri 留在原位 R0=Ri;j=i-1;/R0是 Ri的副本do 从右向左在有序区R1i-1中查找Ri的位置Rj+1=Rj;/将关键字大于Ri.key的记录后移j-; while(R0.keyRj.key); /当 Ri.keyNRj.key 是终止 Rj+1=R0;/Ri插入到正确的位置上/endif /冒泡排序typedef enum FALSE,TRUE Boolean; void BubbleSort(SeqList R) int i,j; Boolean for(i=1;i=i;j-)/FALSE为 0，TRUE 为 1/自下向上扫描对R做冒泡排序/交换标志if(Rj+1.keyRj.key) R0=Rj+1; Rj+1=Rj; Rj=R0; exchange=TRUE; if(! exchange) return;/ endfor (为循环) exchange;/最多做n-1趟排序/本趟排序开始前，交换标志应为假/对当前无序区Ri-n自下向上扫描两两比较，满足条件交换记录/R0不是哨兵，仅做暂存单元发生了交换，故将交换标志置为真/本趟排序未发生交换，提前终止算法/1.=一次划分函数=int Partition(SeqList R,int i,int j)/对Ri-j做一次划分，并返回基准记录的位置RecType pivot=Ri;/用第一个记录作为基准while(ij) /从区间两端交替向中间扫描，直到i=jwhile(i=pivot.key)/基准记录 pivot 相当与在位置 i 上j-;/从右向左扫描，查找第一个关键字小于pivot.key的记录Rjif(ij)/若找到的 Rj.key pivot.key，则Ri+=Rj; 交换Ri和Rj，交换后i指针加1 while(ij &Ri.key=pivot.key)/基准记录 pivot 相当与在位置 j 上i+;/从左向右扫描，查找第一个关键字小于pivot.key的记录Riif(i pivot.key，则Rj-=Ri; 交换Ri和Rj，交换后j指针减1Ri=pivot;/此时，i=j，基准记录已被最后定位return i;/返回基准记录的位置/2.=快速排序=void QuickSort(SeqList R,int low,int high)/Rlow.high快速排序int pivotpos;/划分后基准记录的位置if(lowhigh) /仅当区间长度大于1时才排序pivotpos=Partition(R,low,high); /对 Rlow.high做一次划分，得到基准记录的 位置/对左区间递归排序QuickSort(R,low,pivotpos-1);/对右区间递归排序QuickSort(R,pivotpos+1,high); /=直接选择排序= void SelectSort(SeqList R) int i,j,k; for(i=1;in;i+)/做第 i 趟排序(IWiWnT)k=i;for(j=i+1;j=n;j+) /在当前无序区Rin中选key最小的记录Rk if(Rj.keyRk.key)k=j;/k记下目前找到的最小关键字所在的位置if(k!=i) /交换 Ri和 RkR0=Ri; Ri=Rk; Rk=R0; /endif /endfor /=大根堆调整函数=void Heapify( SeqList R,int low,int high)将Rlow.high 调整为大根堆，除Rlow外，其余结点均满足堆性质int large;/large指向调整结点的左、右孩子结点中关键字较大者RecType temp=Rlow; /暂存调整结点for(large=2*low; largehigh,则表示Rlow是叶子，调整结束；否则先令large指向Rlow的 左孩子if(largehigh & Rlarge.key=Rlarge.key) /temp 始终对应 Rlowbreak; /当前调整结点不小于其孩子结点的关键字，结束调整Rlow=Rlarge; /相当于交换了 Rlow和 Rlargelow=large; /令low指向新的调整结点，相当于temp已筛下到large的位置Rlow=temp;/将被调整结点放入最终位置上 /=构造大根堆=void BuildHeap(SeqList R)将初始文件R1.n构造为堆int i;for(i=n/2;i0;i)Heapify(R,i,n);/#Ri.n调整为大根堆/=堆排序=void HeapSort(SeqList R)对R1.n进行堆排序，不妨用R0 做暂存单元int i;BuildHeap(R); /将R1.n构造为初始大根堆for(i=n;i1;i-)/对当前无序区R1.i进行堆排序，共做n-1趟。R0=R1; R1=Ri;Ri=R0;/将堆顶和堆中最后一个记录交换Heapify(R,1,i-1);将R1.i-1重新调整为堆，仅有R1可能违反堆性质。 /=将两个有序的子序列Rlow.m和Rm+1.high归并成有序的序列Rlow.high= void Merge(SeqList R,int low,int m,int high) int i=low,j=m+1,p=0; /置初始值RecType *R1;/R1 为局部量R1=(RecType *)malloc(high-low+1)*sizeof(RecType); /申请空间while(i=m & j=high)/两个子序列非空时取其小者输出到R1p上R1p+ = (Ri.key=Rj.key)? Ri+:Rj+;while(i=m)/若第一个子序列非空，则复制剩余记录到R1R1p+=Ri+;while(j=high)/若第二个子序列非空，则复制剩余记录到R1中R1p+=Rj+;for(p=0,i=low;i=high;p+,i+)Ri=R1p;归并完成后将结果复制回Rlow.high/=对 R1.n做一趟归并排序=void MergePass(SeqList R,int length) int i;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-1n)/尚有一个子序列，其中后一个长度小于lengthMerge(R,i,i+length-1,n); /归并最后两个子序列/注意：若iWn且i+length-1Nn时，则剩余一个子序列轮空，无须归并/=自底向上对 R1.n做二路归并排序=void MergeSort(SeqList R) int length;for(length=1;lengthn;length*=2) /做lgn趟排序MergePass(R,length);/有序长度Nn 时终止/=输入顺序表=void input_int(SeqList R)int i;printf(Please input num(int):);scanf(%d”,&n);printf(Plase input %d integer:,n);for(i=1;i=n;i+)scanf(%d”,&Ri.key);/=输出顺序表=void output_int(SeqList R)int i;for(i=1;i=n;i+)printf(%4d”,Ri.key);/=主函数=void main()int i;SeqList R;input_int(R);printf(t* Select *n);printf(t1: Insert Sortn);printf(t2: Bubble Sortn);printf(t3: Quick Sortn);printf(t4: Straight Selection Sortn);printf(t5: Heap Sortn);printf(t6: Merge Sortn);printf(t7: Exitn);printf(t*n);scanf(%d”,&i);/输入整数1-7,选择排序方式switch (i)case 1: InsertSort(R); break;/值为 1,直接插入排序case 2: BubbleSort(R); break;/值为 2,冒泡法排序case 3: QuickSort(R,1,n); break;/值为 3，快速排序case 4: SelectSort(R); break;/值为 4，直接选择排序case 5: HeapSort(R); break;/值为 5，堆排序case 6: MergeSort(R); break;/值为 6,归并排序case 7: exit(0);/值为7,结束程序printf(Sort reult:);output_int(R);实验结果：Please input num(int):10Plase input 10 integer