單鏈表的插入和刪除實驗報告

1、數(shù)據(jù)結(jié)構(gòu)實驗報告數(shù)據(jù)結(jié)構(gòu)實驗報告 學(xué)院：計算機科學(xué)與技術(shù)專業(yè)：計算機科學(xué)與技術(shù)班級：0410804姓名：馬青學(xué)號：081004162009/12/2 實驗一、單鏈表的插入和刪除一、目的了解和掌握線性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，掌握單鏈表的基本算法及相關(guān)的時間性能分析。二、要求：建立一個數(shù)據(jù)域定義為字符串的單鏈表，在鏈表中不允許有重復(fù)的字符串；根據(jù)輸入的字符串，先找到相應(yīng)的結(jié)點，后刪除之。三、程序源代碼#include"stdio.h"#include"string.h"#include"stdlib.h"#include"c

2、type.h"typedef struct node /定義結(jié)點 char data10; /結(jié)點的數(shù)據(jù)域為字符串struct node *next; /結(jié)點的指針域 listnode;typedef listnode * linklist; / 自定義linklist單鏈表類型linklist creatlistr1(); /函數(shù)，用尾插入法建立帶頭結(jié)點的單鏈表listnode *locatenode(); /函數(shù)，按值查找結(jié)點void deletelist(); /函數(shù)，刪除指定值的結(jié)點void printlist(); /函數(shù)，打印鏈表中的所有值void deleteall()

3、; /函數(shù)，刪除所有結(jié)點，釋放內(nèi)存/=主函數(shù)=void main() char ch10,num10; linklist head; head=creatlistr1(); /用尾插入法建立單鏈表，返回頭指針 printlist(head); /遍歷鏈表輸出其值 printf(" delete node (y/n):");/輸入“y”或“n”去選擇是否刪除結(jié)點 scanf("%s",num); if(strcmp(num,"y")=0 | strcmp(num,"y")=0) printf("please

4、 input delete_data:"); scanf("%s",ch); /輸入要刪除的字符串 deletelist(head,ch); printlist(head); deleteall(head); /刪除所有結(jié)點，釋放內(nèi)存/=用尾插入法建立帶頭結(jié)點的單鏈表= linklist creatlistr1(void) char ch10; linklist head=(linklist)malloc(sizeof(listnode); /生成頭結(jié)點 listnode *s,*r,*pp; r=head; r->next=null; printf(&qu

5、ot;input # to end "); /輸入“#”代表輸入結(jié)束 printf("please input node_data:"); scanf("%s",ch); /輸入各結(jié)點的字符串 while(strcmp(ch,"#")!=0) pp=locatenode(head,ch); /按值查找結(jié)點，返回結(jié)點指針 if(pp=null) /沒有重復(fù)的字符串，插入到鏈表中 s=(listnode *)malloc(sizeof(listnode); strcpy(s->data,ch); r->next=s;

6、 r=s; r->next=null; printf("input # to end "); printf("please input node_data:"); scanf("%s",ch); return head; /返回頭指針/=按值查找結(jié)點，找到則返回該結(jié)點的位置，否則返回null=listnode *locatenode(linklist head, char *key) listnode *p=head->next; /從開始結(jié)點比較 while(p&&strcmp(p->data,ke

7、y)!=0 ) /直到p為null或p->data為key止p=p->next; /掃描下一個結(jié)點 return p; /若p=null則查找失敗，否則p指向找到的值key的結(jié)點/=刪除帶頭結(jié)點的單鏈表中的指定結(jié)點=void deletelist(linklist head,char *key) listnode *p,*r,*q=head; p=locatenode(head,key); /按key值查找結(jié)點的 if(p=null ) /若沒有找到結(jié)點，退出printf("position error");exit(0); while(q->next!=

8、p) /p為要刪除的結(jié)點，q為p的前結(jié)點q=q->next; r=q->next; q->next=r->next; free(r); /釋放結(jié)點/=打印鏈表=void printlist(linklist head) listnode *p=head->next; /從開始結(jié)點打印 while(p)printf("%s, ",p->data);p=p->next; printf("n");/=刪除所有結(jié)點，釋放空間=void deleteall(linklist head) listnode *p=head,*

9、r; while(p->next)r=p->next;free(p);p=r; free(p);運行結(jié)果：加的添加結(jié)點的代碼：int insert(listnode *head) / the insert functionlistnode *in,*p,*q;int wh;printf("input the insert node:");in=(listnode *)malloc(sizeof(listnode);in->next=null;p=(listnode *)malloc(sizeof(listnode);p->next=null;q=(l

10、istnode *)malloc(sizeof(listnode);q->next=null;if(!in)return 0;scanf("%s",in->data);printf("input the place where you want to insert you data:");scanf("%d",&wh);for(p=head;wh>0;p=p->next,wh-);q=p->next;p->next=in;in->next=q;return 1;運行結(jié)果：最后提示為ok

11、 添加成功。實驗心得：這個實驗中 主要修改的是ch 和 num 把它們由指針改成數(shù)組 因為不改的話在后面delect函數(shù)中會出現(xiàn)沒有地址的情況 找不到地址就不能執(zhí)行功能 然后把locate函數(shù)的判斷語句改一下 避免矛盾的出現(xiàn)。實驗二、二叉樹操作一、 目的掌握二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法。二、 要求采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點總數(shù)的操作。三、 程序源代碼#include"stdio.h"#include"string.h"#define max 20 /結(jié)點的最大個數(shù)ty

12、pedef struct node char data; struct node *lchild,*rchild;bintnode; /自定義二叉樹的結(jié)點類型typedef bintnode *bintree; /定義二叉樹的指針int nodenum,leaf; /nodenum為結(jié)點數(shù)，leaf為葉子數(shù)/=基于先序遍歷算法創(chuàng)建二叉樹=/=要求輸入先序序列，其中加入虛結(jié)點“#”以示空指針的位置=bintree creatbintree(void) bintree t; char ch; if(ch=getchar()='#')return(null); /讀入#，返回空指針

13、else t=(bintnode *)malloc(sizeof(bintnode); / 生成結(jié)點t->data=ch;t->lchild=creatbintree(); /構(gòu)造左子樹t->rchild=creatbintree(); /構(gòu)造右子樹return(t); /=nlr 先序遍歷=void preorder(bintree t) if(t) printf("%c",t->data); /訪問結(jié)點preorder(t->lchild); /先序遍歷左子樹preorder(t->rchild); /先序遍歷右子樹 /=lnr 中序

14、遍歷= void inorder(bintree t) if(t) inorder(t->lchild); /中序遍歷左子樹printf("%c",t->data); /訪問結(jié)點inorder(t->rchild); /中序遍歷右子樹 /=lrn 后序遍歷=void postorder(bintree t) if(t) postorder(t->lchild); /后序遍歷左子樹postorder(t->rchild); /后序遍歷右子樹printf("%c",t->data); /訪問結(jié)點 /=采用后序遍歷求二叉樹的

15、深度、結(jié)點數(shù)及葉子數(shù)的遞歸算法=int treedepth(bintree t) int hl,hr,max; if(t)hl=treedepth(t->lchild); /求左深度hr=treedepth(t->rchild); /求右深度max=hl>hr? hl:hr; /取左右深度的最大值nodenum=nodenum+1; /求結(jié)點數(shù)if(hl=0&&hr=0) leaf=leaf+1; /若左右深度為0，即為葉子。return(max+1); else return(0);/=利用“先進(jìn)先出”（fifo）隊列，按層次遍歷二叉樹=void level

16、order(bintree t) int front=0,rear=1; bintnode *cqmax,*p; /定義結(jié)點的指針數(shù)組cq cq1=t; /根入隊 while(front!=rear) front=(front+1)%nodenum;p=cqfront; /出隊printf("%c",p->data); /出隊，輸出結(jié)點的值 if(p->lchild!=null) rear=(rear+1)%nodenum; cqrear=p->lchild; /左子樹入隊if(p->rchild!=null) rear=(rear+1)%noden

17、um; cqrear=p->rchild; /右子樹入隊 /=主函數(shù)=void main() bintree root; int i,depth; printf("n");printf("creat bin_tree； input preorder:"); /輸入完全二叉樹的先序序列， / 用#代表虛結(jié)點，如abd#ce#f# root=creatbintree(); /創(chuàng)建二叉樹，返回根結(jié)點 do /從菜單中選擇遍歷方式，輸入序號。printf("t* select *n");printf("t1: preorder

18、 traversaln"); printf("t2: iorder traversaln");printf("t3: postorder traversaln");printf("t4: posttreedepth,node number,leaf numbern");printf("t5: level depthn"); /按層次遍歷之前，先選擇4，求出該樹的結(jié)點數(shù)。printf("t0: exitn");printf("t*n");scanf("%d&

19、quot;,&i); /輸入菜單序號（0-5）switch (i)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=treede

20、pth(root); /求樹的深度及葉子數(shù)printf("bintree depth=%d bintree node number=%d",depth,nodenum);printf(" bintree leaf number=%d",leaf);break;case 5: printf("leveprint bin_tree: ");levelorder(root); /按層次遍歷break;default: exit(1);printf("n"); while(i!=0); 執(zhí)行程序1. 先序遍歷2. 中序遍歷

21、3. 后序遍歷4. 結(jié)點數(shù) 葉子數(shù) 高度5.層次遍歷自己設(shè)計的：abdhl#m#i#e#jn#cf#ko#g#1.預(yù)計先序遍歷結(jié)果：abdhlmiejncfkog2.預(yù)計中序遍歷結(jié)果：lhmdibenjafokcg3.預(yù)計后序遍歷結(jié)果：lmhidnjebokfgca4.結(jié)點數(shù) 15 高度5 葉子數(shù) 6實際結(jié)果：實驗心得：這次實驗主要是要讓我們熟練樹及其相關(guān)知識 熟練掌握先序中序后序遍歷，層次遍歷 然后我們自己畫一個圖 會實現(xiàn)以上功能 以及葉子數(shù) 結(jié)點數(shù)還有高度的計算 程序里面大量運用了遞歸以及隊的應(yīng)用， 實驗三、圖的遍歷操作一、 目的掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲

22、結(jié)構(gòu)；掌握dfs及bfs對圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。二、 要求采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的dfs和bfs操作。三、 dfs和bfs 的基本思想深度優(yōu)先搜索法dfs的基本思想：從圖g中某個頂點vo出發(fā)，首先訪問vo，然后選擇一個與vo相鄰且沒被訪問過的頂點vi訪問，再從vi出發(fā)選擇一個與vi相鄰且沒被訪問過的頂點vj訪問，依次繼續(xù)。如果當(dāng)前被訪問過的頂點的所有鄰接頂點都已被訪問，則回退到已被訪問的頂點序列中最后一個擁有未被訪問的相鄰頂點的頂點w，從w出發(fā)按同樣方法向前遍歷。直到圖中所有的頂點都被訪問。廣度優(yōu)先算法bfs的基本思想：從

23、圖g中某個頂點vo出發(fā)，首先訪問vo，然后訪問與vo相鄰的所有未被訪問過的頂點v1，v2，vt；再依次訪問與v1，v2，vt相鄰的起且未被訪問過的的所有頂點。如此繼續(xù)，直到訪問完圖中的所有頂點。四、 程序源代碼1 鄰接矩陣作為存儲結(jié)構(gòu)的程序示例#include"stdio.h"#include"stdlib.h"#define maxvertexnum 100 /定義最大頂點數(shù)typedef struct char vexsmaxvertexnum; /頂點表 int edgesmaxvertexnummaxvertexnum; /鄰接矩陣，可看作邊表

24、int n,e; /圖中的頂點數(shù)n和邊數(shù)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); /輸入頂點數(shù)和邊數(shù) scanf("%c",&a); printf("input vertex string:"); for(i=0;i&

25、lt;g->n;i+) scanf("%c",&a); g->vexsi=a; /讀入頂點信息，建立頂點表 for(i=0;i<g->n;i+)for(j=0;j<g->n;j+) g->edgesij=0; /初始化鄰接矩陣 printf("input edges,creat adjacency matrixn"); for(k=0;k<g->e;k+) /讀入e條邊，建立鄰接矩陣 scanf("%d%d",&i,&j); /輸入邊（vi，vj）的頂點序號

26、 g->edgesij=1; g->edgesji=1; /若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句 /=定義標(biāo)志向量，為全局變量=typedef enumfalse,true boolean;boolean visitedmaxvertexnum;/=dfs：深度優(yōu)先遍歷的遞歸算法=void dfsm(mgraph *g,int i) /以vi為出發(fā)點對鄰接矩陣表示的圖g進(jìn)行dfs搜索，鄰接矩陣是0，1矩陣 int j; printf("%c",g->vexsi); /訪問頂點vi visitedi=true; /置已訪問標(biāo)志 for(j=

27、0;j<g->n;j+) /依次搜索vi的鄰接點if(g->edgesij=1 && ! visitedj) dfsm(g,j); /（vi，vj）e，且vj未訪問過，故vj為新出發(fā)點void dfs(mgraph *g) int i; for(i=0;i<g->n;i+)visitedi=false; /標(biāo)志向量初始化 for(i=0;i<g->n;i+)if(!visitedi) /vi未訪問過 dfsm(g,i); /以vi為源點開始dfs搜索/=bfs：廣度優(yōu)先遍歷=void bfs(mgraph *g,int k) /以vk為

28、源點對用鄰接矩陣表示的圖g進(jìn)行廣度優(yōu)先搜索 int i,j,f=0,r=0; int cqmaxvertexnum; /定義隊列 for(i=0;i<g->n;i+)visitedi=false; /標(biāo)志向量初始化 for(i=0;i<g->n;i+)cqi=-1; /隊列初始化 printf("%c",g->vexsk); /訪問源點vk visitedk=true; cqr=k; /vk已訪問，將其入隊。注意，實際上是將其序號入隊 while(cqf!=-1) /隊非空則執(zhí)行 i=cqf; f=f+1; /vf出隊 for(j=0;j<

29、;g->n;j+) /依次vi的鄰接點vj if(g->edgesij=1 && !visitedj) /vj未訪問 printf("%c",g->vexsj); /訪問vj visitedj=true; r=r+1; cqr=j; /訪問過vj入隊 /=main=void main() int i; mgraph *g; g=(mgraph *)malloc(sizeof(mgraph); /為圖g申請內(nèi)存空間 creatmgraph(g); /建立鄰接矩陣 printf("print graph dfs: "); d

30、fs(g); /深度優(yōu)先遍歷 printf("n"); printf("print graph bfs: "); bfs(g,3); /以序號為3的頂點開始廣度優(yōu)先遍歷 printf("n");調(diào)試結(jié)果：自己畫的圖： 1對應(yīng)頂點下標(biāo)0 以此類推 9對應(yīng)下標(biāo)8預(yù)計運行結(jié)果：dfs:012345678bfs:324105687對應(yīng)我這個圖：dfs：123456789bfs：435216798實驗心得：圖在數(shù)據(jù)結(jié)構(gòu)中是相當(dāng)重要的一部分 聯(lián)系很多現(xiàn)實問題 圖的根本就是頂點和邊 通過頂點和邊建立鄰接矩陣以及鄰接鏈表 廣度搜索和深度搜索是此算法著

31、重關(guān)注的地方。要學(xué)會自己畫圖 然后寫出這兩種搜索的結(jié)果，程序中用了隊的算法 是亮點 通過true和fause來標(biāo)記頂點是否以及訪問 避免重復(fù) 實驗四、排序一、 目的掌握各種排序方法的基本思想、排序過程、算法實現(xiàn)，能進(jìn)行時間和空間性能的分析，根據(jù)實際問題的特點和要求選擇合適的排序方法。二、 要求實現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運行速度。三、 程序示例#include"stdio.h"#include"stdlib.h"#define max 100 /假設(shè)文件長度typedef struct /定義記錄類型 int ke

32、y; /關(guān)鍵字項rectype;typedef rectype seqlistmax+1; /seqlist為順序表，表中第0個元素作為哨兵int n; /順序表實際的長度1、 直接插入排序的基本思想：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已排序好的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。/=直接插入排序法=void insertsort(seqlist r) /對順序表r中的記錄r1n按遞增序進(jìn)行插入排序 int i,j; for(i=2;i<=n;i+) /依次插入r2，rn if(ri.key<ri-1.key) /若ri.key大于等于有序區(qū)中所有的keys

33、，則ri留在原位 r0=ri;j=i-1; /r0是ri的副本 do /從右向左在有序區(qū)r1i-1中查找ri的位置rj+1=rj; /將關(guān)鍵字大于ri.key的記錄后移j-; while(r0.key<rj.key); /當(dāng)ri.keyrj.key 是終止 rj+1=r0; /ri插入到正確的位置上/endif2、 冒泡排序的基本思想：設(shè)想被排序的記錄數(shù)組r1n垂直排序。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組r，凡掃描到違反本原則的輕氣泡，就使其向上“漂浮”（交換），如此反復(fù)進(jìn)行，直到最后任意兩個氣泡都是輕者在上，重者在下為止。/=冒泡排序=typedef enumfalse

34、,true boolean; /false為0，true為1void bubblesort(seqlist r) /自下向上掃描對r做冒泡排序 int i,j; boolean exchange; /交換標(biāo)志 for(i=1;i<n;i+) /最多做n-1趟排序exchange=false; /本趟排序開始前，交換標(biāo)志應(yīng)為假for(j=n-1;j>=i;j-) /對當(dāng)前無序區(qū)rin 自下向上掃描 if(rj+1.key<rj.key) /兩兩比較，滿足條件交換記錄r0=rj+1; /r0不是哨兵，僅做暫存單元rj+1=rj;rj=r0;exchange=true; /發(fā)生了交

35、換，故將交換標(biāo)志置為真 if(! exchange) /本趟排序未發(fā)生交換，提前終止算法 return; /endfor（為循環(huán)）3、 快速排序的基本思想：在待排序的n個記錄中任取一個記錄（通常取第一個記錄），把該記錄作為支點（又稱基準(zhǔn)記錄）（pivot），將所有關(guān)鍵字比它小的記錄放置在它的位置之前，將所有關(guān)鍵字比它大的記錄放置在它的位置之后(稱之為一次劃分過程)。之后對所分的兩部分分別重復(fù)上述過程，直到每部分只有一個記錄為止。/1.=一次劃分函數(shù)=int partition(seqlist r,int i,int j) / 對rij做一次劃分，并返回基準(zhǔn)記錄的位置 rectype pivot

36、=ri; /用第一個記錄作為基準(zhǔn) while(i<j) /從區(qū)間兩端交替向中間掃描，直到i=j while(i<j &&rj.key>=pivot.key) /基準(zhǔn)記錄pivot相當(dāng)與在位置i上 j-; /從右向左掃描，查找第一個關(guān)鍵字小于pivot.key的記錄rjif(i<j) /若找到的rj.key < pivot.key，則 ri+=rj; /交換ri和rj，交換后i指針加1while(i<j &&ri.key<=pivot.key) /基準(zhǔn)記錄pivot相當(dāng)與在位置j上 i+; /從左向右掃描，查找第一個關(guān)鍵字

37、小于pivot.key的記錄riif(i<j) /若找到的ri.key > pivot.key，則 rj-=ri; /交換ri和rj，交換后j指針減1 ri=pivot; /此時，i=j，基準(zhǔn)記錄已被最后定位 return i; /返回基準(zhǔn)記錄的位置/2.=快速排序=void quicksort(seqlist r,int low,int high) /rlow.high快速排序 int pivotpos; /劃分后基準(zhǔn)記錄的位置 if(low<high) /僅當(dāng)區(qū)間長度大于1時才排序pivotpos=partition(r,low,high); /對rlow.high做一次

38、劃分，得到基準(zhǔn)記錄的位置quicksort(r,low,pivotpos-1); /對左區(qū)間遞歸排序quicksort(r,pivotpos+1,high); /對右區(qū)間遞歸排序 4、 直接選擇排序的基本思想：第i趟排序開始時，當(dāng)前有序區(qū)和無序區(qū)分別為r1i-1和rin（1in-1），該趟排序則是從當(dāng)前無序區(qū)中選擇出關(guān)鍵字最小的記錄rk，將它與無序區(qū)的的第一個記錄ri交換，有序區(qū)增加一個記錄，使r1i,和ri+1n分別為新的有序區(qū)和新的無序區(qū)。如此反復(fù)進(jìn)行，直到排序完畢。/=直接選擇排序=void selectsort(seqlist r) int i,j,k; for(i=1;i<n;

39、i+) /做第i趟排序（1in-1）k=i;for(j=i+1;j<=n;j+) /在當(dāng)前無序區(qū)rin中選key最小的記錄rk if(rj.key<rk.key)k=j; /k記下目前找到的最小關(guān)鍵字所在的位置if(k!=i) / /交換ri和rk r0=ri;ri=rk;rk=r0; /endif /endfor5、 堆排序的基本思想：它是一種樹型選擇排序，特點是：在排序的過程中，將r1n看成是一個完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大（或最?。┑挠涗洝＜矗喊汛判蛭募年P(guān)鍵字存放在數(shù)組r1n子中，將r看成是一棵二

40、叉樹，每個結(jié)點表示一個記錄，源文件的第一個記錄r1作為二叉樹的根，以下各記錄r2n依次逐層從左到右排列，構(gòu)成一棵完全二叉樹，任意結(jié)點ri的左孩子是r2i，右孩子是r2i+1，雙親是ri/2。對這棵完全二叉樹的結(jié)點進(jìn)行調(diào)整，使各結(jié)點的關(guān)鍵字滿足下列條件：ri.keyr2i.key并且ri.keyr2i+1.key 稱小堆根或 ri.keyr2i.key并且ri.keyr2i+1.key 稱大堆根/=大根堆調(diào)整函數(shù)=void heapify(seqlist r,int low,int high) / 將rlow.high調(diào)整為大根堆，除rlow外，其余結(jié)點均滿足堆性質(zhì) int large; /la

41、rge指向調(diào)整結(jié)點的左、右孩子結(jié)點中關(guān)鍵字較大者 rectype temp=rlow; /暫存調(diào)整結(jié)點 for(large=2*low; large<=high;large*=2) /rlow是當(dāng)前調(diào)整結(jié)點 /若large>high,則表示rlow是葉子，調(diào)整結(jié)束；否則先令large指向rlow的左孩子if(large<high && rlarge.key<rlarge+1.key) large+; /若rlow的右孩子存在且關(guān)鍵字大于左兄弟，則令large指向它 /現(xiàn)在rlarge是調(diào)整結(jié)點rlow的左右孩子結(jié)點中關(guān)鍵字較大者if(temp.key&g

42、t;=rlarge.key) /temp始終對應(yīng)rlow break; /當(dāng)前調(diào)整結(jié)點不小于其孩子結(jié)點的關(guān)鍵字，結(jié)束調(diào)整rlow=rlarge; /相當(dāng)于交換了rlow和rlargelow=large; /令low指向新的調(diào)整結(jié)點，相當(dāng)于temp已篩下到large的位置 rlow=temp; /將被調(diào)整結(jié)點放入最終位置上/=構(gòu)造大根堆=void buildheap(seqlist r) /將初始文件r1.n構(gòu)造為堆 int i; for(i=n/2;i>0;i-)heapify(r,i,n); /將ri.n調(diào)整為大根堆/=堆排序=void heapsort(seqlist r) /對r1

43、.n進(jìn)行堆排序，不妨用r0做暫存單元 int i; buildheap(r); /將r1.n構(gòu)造為初始大根堆 for(i=n;i>1;i-) /對當(dāng)前無序區(qū)r1.i進(jìn)行堆排序，共做n-1趟。r0=r1; r1=ri;ri=r0; /將堆頂和堆中最后一個記錄交換heapify(r,1,i-1); /將r1.i-1重新調(diào)整為堆，僅有r1可能違反堆性質(zhì)。 6、 二路歸并排序的基本思想：假設(shè)初始序列n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或1的有序子序列；再兩兩歸并，如此重復(fù)，直到一個長度為n的有序序列為止。/=將兩個有序的子序列rlow.m

44、和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) /若第一個子序列非空，則復(fù)制剩余

45、記錄到r1r1p+=ri+; while(j<=high) /若第二個子序列非空，則復(fù)制剩余記錄到r1中r1p+=rj+; for(p=0,i=low;i<=high;p+,i+)ri=r1p; /歸并完成后將結(jié)果復(fù)制回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-1<n) /尚有一個子序列，其中后一個長度小于lengthmerge(r,i,i+length-1,n); /歸并最后兩個子序列 /注意：若in且i+length-1n時，則剩余一個子序