数据结构试验报告

1、数据结构实验报告数据结构实验报告学院：计算机科学与技术 专业：计算机科学与技术班级：0410804姓名：马青学号：08100416实验一、单链表的插入和删除一、目的了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基 本算法及相关的时间性能分析。一、要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复 的字符串；根据输入的字符串，先找到相应的结点，后删除之。三、程序源代码#i nclude"stdio.h"#i nclude"stri ng.h"#i nclude"stdlib.h"#in clude"ctyp

2、e.h" typedef struct nodechar data10;/定义结点/结点的数据域为字符串struct node *n ext;/结点的指针域ListNode;typedef ListNode * Lin kList; /自定义LinkList单链表类型Lin kList CreatListR1();/函数，用尾插入法建立带头结点的单链表ListNode *LocateNode();/函数，按值查找结点void DeleteList();/函数，删除指定值的结点void printlist();/函数，打印链表中的所有值void DeleteAll();/函数，删除所有

3、结点，释放内存/主函数void mai n()char ch10, num10;Lin kList head;head二CreatListR1(); /用尾插入法建立单链表，返回头指针prin tlist(head);/遍历链表输出其值printf(" Delete node (y/n):");输入“y”或“n”去选择是否49删除结点sca nf("%s", nu m);if(strcmp( nu m,"y")=0 | strcmp( nu m," Y")=0)prin tf("Please in put

4、 Delete_data:");sca nf("%s",ch);/输入要删除的字符串DeleteList(head,ch);pri ntlist(head);DeleteAll(head);/删除所有结点，释放内存二=用尾插入法建立带头结点的单链表 =Lin kList CreatListRI(void)char ch10;LinkListhead=(LinkList)malloc(sizeof(ListNode);/ 生成头结点ListNode *s,*r,*pp;r=head;r->n ext=NULL;prin tf("I nput # to

5、 end "); /输入“ #” 代表输入结束prin tf("Please in put Node_data:");sca nf("%s",ch);/输入各结点的字符串while(strcmp(ch,"#")!=O) pp=LocateNode(head,ch); /按值查找结点，返回结点指针 if(pp=NULL) /没有重复的字符串，插入到链表中s=(ListNode *)malloc(sizeof(ListNode);strcpy(s->data,ch);r->n ext=s;r=s;r->n ex

6、t=NULL;prin tf("I nput # to end ");prin tf("Please in put Node_data:");sea nf("%s",ch);return head; /返回头指针二=按值查找结点，找到则返回该结点的位置，否则返回NULL二=ListNode *LocateNode(L in kList head, char *key)ListNode *p=head-> next; /从开始结点比较while(p&&strcmp(p->data,key)!=O ) /直到

7、p 为 NULL或 p->data 为 key 止p=p-> next;/扫描下一个结点return p; /若p=NULL则查找失败，否则 p指向找到的值key的结点/=删除带头结点的单链表中的指定结点 =void DeleteList(LinkList head,char *key)ListNode *p,*r,*q=head;p=LocateNode(head,key); / 按 key 值查找结点的if(p=NULL ) /若没有找到结点，退出prin tf("positi on error");exit(O);while(q->next!二p)/

8、p为要删除的结点，q为p的前结点q二q->n ext;r二q->n ext;q->n ext=r- >n ext;free(r);/释放结点二二=打印链表=void pr in tlist(L in kList head)ListNode *p=head-> next; /从开始结点打印while(p)prin tf("%s, ",p->data);p=p->n ext;prin tf("n");/=删除所有结点，释放空间=void DeleteAII(LinkList head)ListNode *p=head

9、,*r; while(p-> next) r=p->n ext; free(p);p=r；free(p);运行结果:Inputtt to endPleaseinputNode_data：abcInputII to endPleaseinputNode_data：hedInputtl to endPleaseinputNode_data：kecInputtl to endPleaseinputNode_data：fcInputtl to endPleaseinputNodeabc .hed,kecfcDelete node <y/n>：yPleaseinput Delet

10、e_data：fcabc hed,kec >Pressany keyto continue加的添加结点的代码:/ the in sert fun cti onint In sert(ListNode *head) ListNode *in ,*p,*q;int wh;prin tf("i nput the insert no de:"); in=(ListNode *)malloc(sizeof(ListNode);in->next二NULL; p=(ListNode *)malloc(sizeof(ListNode);p->next=NULL; q=(L

11、istNode *)malloc(sizeof(ListNode);q-> next二NULL; if(!i n)return 0;sca nf("%s",i n->data);printf("input the place where you want to insert you data:"); sca nf("%d", &wh);for(p=head;wh>0;p=p->n ext,wh-);q=p->n ext;p->n ext=in;in->n ext=q;return 1;

12、运行结果:InputntoendPleaseinputNode,_data:dhInputtoendPleaseinputNode,_data：cbaInputtttoendPleaseinputNode._data：eefcInpu ttttoendPleaseinputNode,_data：hfaeInpu ttttoendPleaseinputNode,_data：#讥eefc,hfae,Delete node <y/n>：n insert or not?input the insert node：cadeinput the place where you want to i

13、nsert you data：2 )KPress any kep to continue最后提示为OK添加成功实验心得：这个实验中 主要修改的是ch和num把它们由指针改成 数组 因为不改的话在后面delect函数中会出现没有地址的情况 找不 到地址就不能执行功能 然后把locate函数的判断语句改一下 避免矛 盾的出现。实验二、二叉树操作目的掌握二叉树的定义、性质及存储方式，各种遍历算法一、 要求采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。三、程序源代码#i nclude"stdio.h"#i nclud

14、e"stri ng.h"#defi ne Max 20/结点的最大个数typedef struct no dechar data;struct node *lchild,*rchild;Bi nTNode; /自定义二叉树的结点类型typedef Bi nTNode *Bi nTree; / 定义二叉树的指针int NodeNum,leaf; /NodeNum 为结点数，leaf 为叶子数二=基于先序遍历算法仓U建二叉树 =/=要求输入先序序列，其中加入虚结点“ #”以示空指针的位置Bi nTree CreatBi nTree(void)Bi nTree T;char ch

15、;if(ch二getchar()='#')return(NULL); /读入#，返回空指针elseT=(Bi nTNode *)malloc(sizeof(Bi nTNode); /生成结点T->data=ch;T->lchild二CreatBi nTree();/构造左子树T->rchild二CreatBi nTree();/构造右子树return(T);二二=NLR 先序遍历=void Preorder(Bi nTree T)if(T) prin tf("%c",T->data);/访问结点Preorder(T->lchil

16、d);/先序遍历左子树Preorder(T->rchild);/先序遍历右子树=LNR 中序遍历=void In order(Bi nTree T)if(T) In order(T->lchild); /中序遍历左子树prin tf("%c",T->data);/访问结点In order(T->rchild); /中序遍历右子树=LRN 后序遍历=void Postorder(Bi nTree T)if(T) Postorder(T->lchild);/后序遍历左子树Postorder(T->rchild);/后序遍历右子树prin tf

17、("%c",T->data);/访问结点/=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法 int TreeDepth(Bi nTree T)int hl,hr,max;hl二TreeDepth(T->lchild);hr二TreeDepth(T->rchild); / max=hl>hr? hl:hr; / NodeNum二NodeNum+1;/if(hl=0&&hr=0) leaf=leaf+1; return(max+1);else return(O);/=利用“先进先出”(FIFO)队列,/求左深度求右深度取左右深度的最

18、大值求结点数/若左右深度为0,即为叶子按层次遍历二叉树=void Levelorder(B in Tree T)int fron t=0,rear=1;Bi nTNode *cqMax,*p; /cq1=T;/while(fr on t!=rear)定义结点的指针数组cq根入队fron t=(fro nt+1)%NodeNum;p=cqfr on t;/出队prin tf("%c",p->data);/出队，输出结点的值if(p->lchild!二NULL)rear=(rea 叶1)%NodeNum;cqrear=p->lchild; /左子树入队if(p

19、->rchild!=NULL)rear=(rea 叶1)%NodeNum;cqrear=p->rchild; /右子树入队/主函数void mai n()Bi nTree root;int i,depth;prin tf("n");prin tf("Creat Bin_Tree；In put preorder:");/输入完全二叉/用#代表树的先序序列，结点，如ABD#CE#F#root二CreatBi nTree();/创建二叉树，返回根结点do /从菜单中选择遍历方式，输入序号。*select*n");prin tf("

20、;t1: Preorder Traversal' n");prin tf("t2: lorder Traversaln");prin tf("t3: Postorder traversaln");prin tf("t4:PostTreeDepth,Nodenu mber,Leafnu mber n");prin tf("t5: Level Depthn"); II按层次遍历之前，先选择4, 求出该树的结点数。prin tf("t0: Exitn");prin tf("

21、t*n");scanf("%d",&i); II输入菜单序号(0-5)switch (i)case 1: prin tf("Pri nt Bin_tree Preorder:");Preorder(root); II先序遍历break;case 2: prin tf("Pri nt Bin_Tree Ino rder:");Ino rder(root); II中序遍历break;case 3: prin tf("Pri nt Bin_Tree Postorder:");Postorder(root

22、); II后序遍历break;case 4: depth=TreeDepth(root); II求树的深度及叶子数pri ntf("Bi nTreeDepth=%dBin TreeNodenu mber=%d",depth,NodeNum);printf(” Bin Tree Leaf nu mber=%d",leaf);break;case 5: printf("LevePrint Bin_Tree:");Levelorder(root); /按层次遍历break;default: exit(1);prin tf("n")

23、; while(i!=0);执行程序1. 先序遍历1Print Bin_t>*ee Preorder: abdlilniejncfkog2. 中序遍历Print Bin_ Ti*ecnoi*dei* x lhnd ihcn jaF o keg3. 后序遍历3Print Bin_Tree P«»st order ： Inhidnjehokf qca4.结点数叶子数高度BinTree Depths Binlree Node nunbera15 Binlree Leaf number5.层次遍历LevePrint Bin_Tree: abcdefghijklmno自己设计的

24、：abdhl#m#i#e#j n#cf#ko#g#1. 预计先序遍历结果：abdhlmiej ncfkog2. 预计中序遍历结果：Ihmdibenjafokcg3. 预计后序遍历结果：Imhidnjebokfgca4. 结点数15高度5叶子数6实际结果:Great BinTree ； Input preorder1: Preorder Treversal2 : I order T t*auei*sal3: Postordei* traversal4： PostTreeDepth,Node nunberLeaf number 5: Leue1 Depth0: Exit1Pi*int Bin-ti

25、'ee Preoi'dei*: ahdhlniiejncfko2Print Binjree Inorder: lhndibenjafokcg3Print Bin_Ti*ee Postoi*der: ImhidnJebokfgcakBinTree Depth=5 BinTree Node number=15 BinTree Leaf number=65LeuePi*in t Bin_Ti'ee - abode：f hijklnnoJ仏Press any key to continue.实验心得：这次实验主要是要让我们熟练树及其相关知识熟练掌握先序中序后序遍历，层次遍历 然

26、后我们自己画一个图 会实现以上功 能 以及叶子数 结点数还有高度的计算 程序里面大量运用了递归以 及队的应用，实验三、图的遍历操作一、 目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图 的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人 工智能、工程等领域的广泛应用。一、 要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无 向图的DFS和BFS操作。三、 DFS和BFS的基本思想深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发, 首先访问Vo,然后选择一个与Vo相邻且没被访问过的顶点Vi访问, 再从Vi出发选择一个与Vi相邻且没被访问过的顶点 Vj访问, 依

27、次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问， 则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶 点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶 点都被访问。广度优先算法BFS的基本思想：从图G中某个顶点Vo出发, 首先访问Vo,然后访问与 Vo相邻的所有未被访问过的顶点 V1 , V2, , , Vt ；再依次访问与 V1 , V2, , , Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。四、程序源代码1. 邻接矩阵作为存储结构的程序示例#i nclude"stdio.h"#i nclude"stdlib.

28、h"#defi ne 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):");sca nf("%d,%d"

29、;, &G-> n,&G->e);/输入顶点数和边数sca nf("%c",&a);prin tf("I nput Vertex stri ng:");for(i=0;i<G-> n;i+)sea nf("%c",&a);G->vexsi=a;/读入顶点信息，建立顶点表for(i=0;i<G-> n;i+)for(j=0;j<G-> n;j+)G->edges曲=0; /初始化邻接矩阵prin tf("I nput edges,Cre

30、at Adjace ncy Matrix' n");for(k=0;k<G->e;k+) /读入e条边，建立邻接矩阵seanf("%d%d"，&i，&j);/输入边(Vi，Vj)的顶点序号G->edgesij=1;G->edgesji=1;/若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句/=定义标志向量，为全局变量 =typedef e nu mFALSE,TRUE Boolea n;Boolean visitedMaxVertexNum;=DFS:深度优先遍历的递归算法=void DFSM(MGraph *

31、G,i nt i) /以Vi为出发点对邻接矩阵表示的图 G进行DFS搜索，邻接矩阵 是0，1矩阵int j;prin tf("%c",G->vexsi);/visitedi=TRUE;/for(j=0;j<G-> n;j+)/if(G->edgesij=1 && ! visitedj)DFSM(Gj);/过，故Vj为新出发点void DFS(MGraph *G)int i;for(i=0;i<G-> n;i+)visitedi=FALSE;/for(i=0;i<G-> n;i+)if(!visitedi)/Vi

32、DFSM(G,i);/=BFS广度优先遍历= void BFS(MGraph *G,i nt k)访问顶点Vi置已访问标志依次搜索Vi的邻接点(Vi , Vj ) E,且Vj未访问标志向量初始化未访问过以Vi为源点开始DFS搜索/以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索int i,j,f=0,r=0;int cqMaxVertexNum; /定义队列for(i=0;i<G-> n;i+) visitedi=FALSE; /for(i=0;i<G-> n;i+)cqi=-1;prin tf("%c",G->vexsk);/visited

33、k=TRUE;cqr=k;Vk将其序号入队while(cqf!=-1) /i=cqf; f=f+1;Vffor(j=0;j<G-> n;j+)/标志向量初始化队列初始化访问源点Vk已访问，将其入队。注意，实际上是队非空则执行出队依次Vi的邻接点Vjif(G->edgesij=1 && !visitedj) /Vj未访问prin tf("%c",G->vexsj);/访问Vjvisitedj=TRUE;r二叶1; cqr=j;/访问过Vj入队/:mainvoid mai n()int i;MGraph *G;G=(MGraph *)ma

34、lloc(sizeof(MGraph); / 为图 G申请内存空 间CreatMGraph(G); /建立邻接矩阵printf("Print Graph DFS:");DFS(G);/深度优先遍历prin tf("n");printf("Print Graph BFS:");BFS(G,3);/以序号为3的顶点开始广度优先遍历prin tf("n");调试结果:Input UertexNun<n> and EdgesNum(e>： 8/Input Uertex string：01234567Inp

35、ut edges,Great Adjacency Matrix0 10 21 31 42 52 63 74 75 6Print Graph DFS: 01374256Print Graph BPS: 31?04256Press an key to continue自己画的图:11对应顶点下标0以此类推9对应下标8 预计运行结果：DFS:012345678BFS:324105687对应我这个图：DFS: 123456789BFS: 435216798Input Uei*texNum<n> and EdgesNuin<e>: 9,10Input Uertex string=

36、012345678Input edges,Great Adjacency Hsctrixu6 77 8Print Graph DFS: 012345678Print Graph BFS: 324105687Pi'ess any key to continue实验心得：图在数据结构中是相当重要的一部分联系很多现实问题图的根本就是顶点和边通过顶点和边建立邻接矩阵以及邻接链表广度搜索和深度搜索是此算法着重关注的地方。要学会自己画图然后写出这两种搜索的结果，程序中用了队的算法 是亮点 通过TRUE 和FAUSE来标记顶点是否以及访问避免重复实验四、排序一、 目的掌握各种排序方法的基本思想、排序

37、过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。一、 要求实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。三、程序示例#i nclude"stdio.h"#i nclude"stdlib.h"#defi ne Max 100/假设文件长度typedef struct /定义记录类型int key; /关键字项RecType;typedef RecType SeqListMax+1; /SeqList为顺序表，表中第 0个元素作为哨兵int n;/顺序表实际的长度1、直接插入排序的基本思

38、想：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部 记录插入完成为止。二=直接插入排序法=void In sertSort(SeqList R)/ 对顺序表R中的记录R1n按递增序进行插入排序int i,j;for(i=2;i<=n ;i+)/依次插入R2,Rnif(Ri.key<Ri-1.key) /若 Ri.key大于等于有序区中所有的keys，则Ri留在原位RO=Ri；j=i-1；/R0是 Ri的副本do /从右向左在有序区R1i-1中查找Ri 的位置Rj+1=Rj;/将关键字大于 Ri.key 的记录后while(RO.key<

39、Rj.key);/当 Ri.key > Rj.key是终止Rj+1=R0;/Ri插入到正确的位置上/en dif2、冒泡排序的基本思想：设想被排序的记录数组 R1n垂直排序。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R, 凡扫描到违反本原则的轻气泡，就使其向上“漂浮”（交换），如 此反复进行，直到最后任意两个气泡都是轻者在上， 重者在下为二=冒泡排序=typedef enumFALSE,TRUE Boolean; /FALSE 为 0, TRUE为 1 void BubbleSort(SeqList R) /int i,j;Boolea n excha nge; /for(i=1

40、;i< n;i+) / excha nge=FALSE;/for(j=n-1;j>=i;j-)/扫描if(Rj+1.key<Rj.key) / 记录R0=Rj+1;/R0Rj+1=Rj;Rj=R0;excha nge=TRUE; / 直/、if(!excha nge)/法自下向上扫描对R做冒泡排序交换标志最多做n-1趟排序本趟排序开始前，交换标志应为假对当前无序区Ri - n自下向上两两比较，满足条件交换不是哨兵，仅做暂存单元发生了交换，故将交换标志置为本趟排序未发生交换，提前终止算return;/endfor （为循环）3、快速排序的基本思想：在待排序的n个记录中任取一个记

41、录(通常取第一个记录)，把该记录作为支点(又称基准记录) (pivot)，将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别重复上述过程，直到每部分只有一 个记录为止。/1.= 一次划分函数=int Partition(SeqList R,int i,int j)/对Ri -j做一次划分，并返回基准记录的位置RecType pivot=Ri; /用第一个记录作为基准while(ivj) /从区间两端交替向中间扫描，直到i=jwhile(i<j &&Rj.key>=pivot.key)

42、/基准记录 pivot 相当与在位置i上j-;/从右向左扫描，查找第一个关键字小于pivot.key 的记录 Rjif(i<j) /若找到的 Rj.key < pivot.key，贝SRi+=Rj / 交换Ri和Rj，交换后i指针加 1while(i<j&&Ri.key<二pivot.key)/ 基准记录pivot相当与在位置j上i+;/从左向右扫描，查找第一个关键字小于pivot.key 的记录 Riif(ivj) / 若找到的 Ri.key > pivot.key ，贝SRj-=Ri； / 交换Ri和Rj，交换后j指针减1Ri=pivot; /

43、此时，i=j ,基准记录已被最后定位return i; /返回基准记录的位置2.=快速排序=void QuickSort(SeqList R,int low,int high)Rlow.highint pivotpos;/if(low<high) /pivotpos=Partiti on (R,low,high);划分，得到基准记录的位置QuickSort(R,low,pivotpos-1);QuickSort(R,pivotpos+1,high);4、直接选择排序的基本思想：无序区分别为Rj i-1和Ri快速排序划分后基准记录的位置仅当区间长度大于1时才排序/对 Rlow.high做一

44、次/对左区间递归排序/对右区间递归排序第i趟排序开始时，当前有序区和n (1< i < n-1)，该趟排序则是从当前无序区中选择出关键字最小的记录Rk，将它与无序区的的第一个记录 Ri交换，有序区增加一个记录，使R1i,和Ri+1 - n分别为新的有序区和新的无序区。如此反复进行，直到 排序完毕。/=直接选择排序=void SelectSort(SeqList R)int i,j,k;for(i=1;i<n;i+)/做第 i 趟排序(1< i < n-1)k=i;for(j=i+1;j<=n;j+) II在当前无序区 Rin中选key最小的记录Rkif(Rj

45、.key<Rk.key)k=j; Ilk记下目前找到的最小关键字所在的位置if(k!=i) II II交换 Ri和 RkR0=Ri；Ri=Rk;Rk=R0; IIen dif en dfor5、堆排序的基本思想：它是一种树型选择排序，特点是：在排序的过程中，将R1n看成是一个完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无 序区中选择关键字最大(或最小)的记录。即：把待排序文件的关键字存放在数组R1n子中，将R看成是一棵二叉树，每个结 点表示一个记录，源文件的第一个记录 R1 作为二叉树的根，以 下各记录R2n依次逐层从左到右排列，构成一棵完全二叉树，

46、任意结点Ri的左孩子是R2i,右孩子是R2i+1,双亲是Ri/2。对这棵完全二叉树的结点进行调整，使各结点的关键字满足下列 条件：Ri.key < R2i.key 并且 Ri.key < R2i+1.key 称小堆根或 Ri.key > R2i.key 并且 Ri.key > R2i+1.key 称大堆根/=大根堆调整函数=void Heapify(SeqList R,i nt low,i nt high)/ 将Rlow.high调整为大根堆，除Rlow夕卜，其余结点均满足堆性质int large; /large指向调整结点的左、右孩子结点中关键字较大者RecType

47、temp=Rlow; / 暂存调整结点for(large=2*low; large<=high;large*=2) /Rlow是当前调整结点/ 若large>high,则表示Rlow是叶子，调整结束；否则先令 large指向Rlow的左孩子if(large<high && Rlarge.keyvRlarge+1.key)large+; / 若Rlow的右孩子存在且关键字大于左兄 弟，则令large指向它/ 现在Rlarge是调整结点Rlow的左右孩子结点中关键 字较大者if(temp.key>=Rlarge.key) /temp始终对应 Rlowbrea

48、k; /当前调整结点不小于其孩子结点的关键字，结束调整Rlow=Rlarge; /相当于交换了 Rlow和 Rlargelow=large; / 令low指向新的调整结点，相当于temp已筛 下到large的位置Rlow=temp; /将被调整结点放入最终位置上二=构造大根堆=void BuildHeap(SeqList R)/将初始文件R1.n构造为堆int i;for(i=n /2;i>0;i-)Heapify(R,i,n);/将 Ri.n调整为大根堆/堆排序void HeapSort(SeqList R)/对R仁n进行堆排序，不妨用R0做暂存单元int i;BuildHeap(R)

49、; / 将R1.n构造为初始大根堆for(i=n;i>1;i-)/对当前无序区R1.i进行堆排序，共做n-1趟。R0=R1; R1=Ri;Ri=R0;/将堆顶和堆中最后一个记录交换Heapify(R,1,i-1); / 将 R1.i-1重新调整为堆，仅有R1可能违反堆性质。6、二路归并排序的基本思想：假设初始序列n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得 到n/2个长度为2或1的有序子序列；再两两归并，,，如此 重复，直到一个长度为n的有序序列为止。/=将两个有序的子序列 Rlow.m和Rm+1.high归并成有序 的序列 Rlow.high=void

50、Merge(SeqList R,i nt low,i nt m,i nt high)int i=low,j=m+1,p=0; /置初始值RecType *R1; R1为局部量R仁(RecType*)malloc(high-low+1)*sizeof(RecType);/申请空间while(i<=m&&jv二high)/两个子序列非空时取其小者输出到R1p上R1p+=(Ri.key<=Rj.key)? Ri+:Rj+;while(i<=m) /若第一个子序列非空，则复制剩余记录到R1R1p+=Ri+;while(j<=high) /若第二个子序列非空，则复

51、制剩余记录到R1中R1p+=Rj+；for(p=0,i=low;i<=high;p+,i+)Ri=R1p； /归并完成后将结果复制回 Rlow.high/=对r仁n做一趟归并排序=void MergePass(SeqList R,i nt len gth)int i;for(i=1;i+2*le ngth-1<=n;i=i+2*le ngth)Merge(R,i,i+length-1,i+2*length-1);/ 归并长度为length的两个相邻的子序列if(i+length-1<n) /尚有一个子序列，其中后一个长度小于len gthMerge(R,i,i+le ngth

52、-1, n); /归并最后两个子序列/注意：若i < n且i+length-1 > n时，则剩余一个子序列轮空，无须归并二=自底向上对R仁n做二路归并排序= void MergeSort(SeqList R)int len gth;for(length=1;lengthvn;length*=2)/做lgn趟排序MergePass(R,length);/ 有序长度n时终止/=输入顺序表=void in put_i nt(SeqList R)int i;prin tf("Please in put nu m(i nt):");sca nf("%d",&n);prin tf("Plase in put %d in teger:", n);for(i=1