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

1、實驗一、單鏈表的插入和刪除一、目的了解和掌握線性表的邏輯結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，掌握單鏈表的根本算法與相關的時間性能分析。ill, 、-二、要求：建立一個數(shù)據(jù)域定義為字符串的單鏈表，在鏈表中不允許有重復的字符串；根據(jù)輸入的字符串，先找到相應的結(jié)點，后刪除之。三、程序源代碼#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h" typedef struct nodechar data10;/定義結(jié)點/結(jié)點的數(shù)據(jù)域為字符串struct n

2、ode *next;/結(jié)點的指針域ListNode;typedef ListNode * LinkList; /LinkList CreatListR1();/自定義 LinkList 單鏈表類型函數(shù)，用尾插入法建立帶頭結(jié)點的單鏈表ListNode *LocateNode();/函數(shù)，按值查找結(jié)點void DeleteList();/函數(shù)，刪除指定值的結(jié)點void printlist();/函數(shù)，打印鏈表中的所有值void DeleteAll();/函數(shù)，刪除所有結(jié)點，釋放存/主函數(shù)void mai n()char ch10, num10;Lin kList head;head二CreatLi

3、stR1(); /用尾插入法建立單鏈表，返回頭指針prin tlist(head);/遍歷鏈表輸出其值printf(" Delete node (y/n):");輸入“y或“n去選擇是否刪除結(jié)點sca nf("%s", nu m);if(strcmp( nu m,"y")=0 | strcmp( nu m," Y")=0)prin tf("Please in put Delete_data:");sca nf("%s",ch);/輸入要刪除的字符串DeleteList(hea

4、d,ch);pri ntlist(head);DeleteAll(head);/刪除所有結(jié)點，釋放存/用尾插入法建立帶頭結(jié)點的單鏈表Lin kList CreatListRI(void)char ch10;LinkListhead=(LinkList)malloc(sizeof(ListNode);/ 生成頭結(jié)點ListNode *s,*r,*pp;r=head;r->n ext二NULL;prin tf("I nput # to end "); /輸入“ # 代表輸入完畢prin tf("Please in put Node_data:");sc

5、a nf("%s",ch);/輸入各結(jié)點的字符串while(strcmp(ch,"#")!=O) pp=LocateNode(head,ch); /按值查找結(jié)點，返回結(jié)點指針 if(pp=NULL) /沒有重復的字符串，插入到鏈表中s=(ListNode *)malloc(sizeof(ListNode);strcpy(s->data,ch);r->n ext=s;r=s;r->n ext=NULL;prin tf("I nput # to end ");prin tf("Please in put Nod

6、e_data:");sea nf("%s",ch);return head; /返回頭指針二=按值查找結(jié)點，找到那么返回該結(jié)點的位置，否那么返回 NULL二=ListNode *LocateNode(L in kList head, char *key)ListNode *p=head-> next; /從開始結(jié)點比較while(p&&strcmp(p->data,key)!=O ) /直到 p 為 NULL 或p->data 為 key 止p=p->n ext;/掃描下一個結(jié)點returnp; /假設p=NULL那么查找失

7、敗，否那么p指向找到的值key的結(jié)點/=刪除帶頭結(jié)點的單鏈表中的指定結(jié)點 void DeleteList(LinkList head,char *key)ListNode *p,*r,*q=head;if(p=NULL ) /p=LocateNode(head,key); / 按 key 值查找結(jié)點的假設沒有找到結(jié)點，退出prin tf("positi on error");exit(O);while(q->next!二p)/p為要刪除的結(jié)點，q為p的前結(jié)點q二q->n ext;r二q->n ext;q->n ext=r- >n ext;fre

8、e(r);/釋放結(jié)點二二=打印鏈表=void pr in tlist(L in kList head)ListNode *p=head-> next; /從開始結(jié)點打印while(p)prin tf("%s, ",p->data);p=p->n ext;prin tf("n");/=刪除所有結(jié)點，釋放空間=void DeleteAII(LinkList head)ListNode *p=head,*r; while(p-> next) r=p->n ext; free(p); p=r；free(p);運行結(jié)果:HnpLitt

9、ttoendPleaseinputNode._data：abcInputtttoendPleaseinputNode_data：liedI nputtttoendPleaseinputNode.= kecI npu ttttoendPleaseinputNode._data：fcI npu ttttoendPleaseinputNode._data：ttabc bed,Jcec.fc-!Delete node <y/n> Please input De le 總be,bed, hec,press ansf to continue加的添加結(jié)點的代碼:int In sert(ListN

10、ode *head)/ the in sert fun cti onListNode *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=(ListNode *)malloc(sizeof(ListNode);q-> next二NULL; if(!i n)return 0;yousca n

11、f("%s",i n->data);printf("input the place where you want to insert 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;運行結(jié)果:InputtoendPleaseinputNode._data：dhInputtttoendPleaseinputNode._data：chaInp

12、uttttoendPleaseinputNode._data：eeFcInputtttoRndPleasRinputNode._data：hfaeInpu ttttoendPleaseinputNode._data：tteefc,Delete node (y/n：n insert or not? pinput the insert node：CAdeinput the place uhere you uant to insert you data=2 OKPress any to continue最后提示為OK添加成功實驗心得：這個實驗中 主要修改的是ch和num把它們由指針改成 數(shù)組 因為不

13、改的話在后面delect函數(shù)中會出現(xiàn)沒有地址的情況找不到地址就不能執(zhí)行功能 然后把locate函數(shù)的判斷語句改一下 防 止矛盾的出現(xiàn)。實驗二、二叉樹操作目的掌握二叉樹的定義、性質(zhì)與存儲方式，各種遍歷算法一、 要求采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以與按層次遍歷的操作，求所有葉子與結(jié)點總數(shù)的操作。三、程序源代碼#i nclude"stdio.h"#i nclude"stri ng.h"#defi ne Max 20/結(jié)點的最大個數(shù)typedef struct no dechar data;struct node *lchild,

14、*rchild;Bi nTNode; /自定義二叉樹的結(jié)點類型typedef Bi nTNode *Bi nTree; /定義二叉樹的指針int NodeNum,leaf; /NodeNum 為結(jié)點數(shù)，leaf 為葉子數(shù)二=基于先序遍歷算法倉U建二叉樹 =/=要求輸入先序序列，其中參加虛結(jié)點“#以示空指針的位置Bi nTree CreatBi nTree(void)Bi nTree T;char ch;if(ch二getchar()='#')return(NULL); /讀入#，返回空指針elseT=(Bi nTNode *)malloc(sizeof(Bi nTNode);

15、/生成結(jié)點T->data=ch;T->lchild二CreatBi nTree();/構(gòu)造左子樹T->rchild二CreatBi nTree();/構(gòu)造右子樹return(T);二二=NLR 先序遍歷=void Preorder(Bi nTree T)if(T) prin tf("%c",T->data);/Preorder(T->lchild); /訪問結(jié)點先序遍歷左子樹Preorder(T->rchild); /先序遍歷右子樹=LNR 中序遍歷=void In order(Bi nTree T)if(T) In order(T-&g

16、t;lchild); /中序遍歷左子樹prin tf("%c",T->data);/訪問結(jié)點In order(T->rchild); /中序遍歷右子樹=LRN 后序遍歷=void Postorder(Bi nTree T)if(T) Postorder(T->lchild);/后序遍歷左子樹Postorder(T->rchild);/后序遍歷右子樹prin tf("%c",T->data);/訪問結(jié)點/=采用后序遍歷求二叉樹的深度、結(jié)點數(shù)與葉子數(shù)的遞歸算法int TreeDepth(Bi nTree T)int hl,hr,

17、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; return(max+1);/求左深度求右深度取左右深度的最大值求結(jié)點數(shù)/假設左右深度為0,即為葉子else return(0);/=利用“先進先出FIFO隊列，按層次遍歷二叉樹=void Levelorder(B in Tree T)int fron t=0,rear=1;BinTNode *cqMax,*p

18、; /定義結(jié)點的指針數(shù)組cqcq1=T;/根入隊while(fr on t!=rear)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->rchild!=NULL)rear=(rea 葉1)%NodeNum;cqrear=p->rchild; /出隊，輸出結(jié)點的值左子樹入隊右子樹入隊二=主函數(shù)=void mai n()Bi nTree r

19、oot;int i,depth;prin tf("n");root=CreatBi nTree();IIABD#CE#F#創(chuàng)立二叉樹，返回根結(jié)點prin tf("Creat Bin_Tree；In put preorder:");II 輸入完全二叉樹的先序序列，II用#代表虛結(jié)點，如*select*n");prin tf("t1: Preorder Traversal' n");prin tf("t2: lorder Traversaln");prin tf("t3: Postorder

20、 traversaln");prin tf("t4:PostTreeDepth,Nodenu mber,Leafnu mber n");prin tf("t5: Level Depthn"); II按層次遍歷之前，先選擇4,求出該樹的結(jié)點數(shù)。prin tf("t0: Exitn");prin tf("t*n");scanf("%d",&i); II輸入菜單序號0-5switch (i)case 1: prin tf("Pri nt Bin_tree Preorder:

21、");Preorder(root); II先序遍歷break;case 2: prin tf("Pri nt Bin_Tree Ino rder:");Ino rder(root); II中序遍歷break;case 3: printf("Print Bin_Tree Postorder:");Postorder(root); II后序遍歷break;求樹的深度與葉case 4: depth二TreeDepth(root); /子數(shù)pri ntf("Bi nTreeDepth=%dBin TreeNodenu mber=%d"

22、;,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"); while(i!=0);執(zhí)行程序1. 先序遍歷>int Bin_tvee P>keorder-： abd)*lniejncfl<og2. 中序遍歷2Print Bin_Trec I noi*dci's

23、 lhnd ibcn jaf okcg3. 后序遍歷Print Bin Tree Postorder： lnhidnjebokfca4. 結(jié)點數(shù)葉子數(shù)高度Bin Tree Depth 5 Binrrce Node nuniber 15 BinIriT Leaf nunJjer G5.層次遍歷5 -euePrint BinTret*: abcdefghijklnno自己設計的：abdhl#m#i#e#j n#cf#ko#g#1. 預計先序遍歷結(jié)果：abdhlmiejncfkog2. 預計中序遍歷結(jié)果：Ihmdibenjafokcg3. 預計后序遍歷結(jié)果：Imhidnjebokfgca4. 結(jié)點數(shù)

24、15高度5葉子數(shù)6實際結(jié)果:Great B in .Tree ; Input precede r = dbdhlttttmttttttMcXHXXXKKMICJC se lecfc XXXXJOOCJCJt>tXX1: Preordep Tr-auei'eal2= Iorder Irauersal3 - Postorder- traversal4 : Postil*EEDEpth.Nofle nunbei', Lea.£ number5: Leuel Depth0: Exlfc1Print Bln_tree Pi*envd.Er: abd.hlm±eJ

25、ncfkojf2Print Bin_Tree Tnorders lhndibenjafokcg-3Print Bin_Tree Post order： Imhidn Jebokf gca4BinTree Dept>i=5 Binlr-ee Node nunbei*3!? BinTree Leaf nunbei*=6*LeuePrin七 Bln_Tree : sib匚def g-hijklnno0Press anv hey to continue-實驗心得：這次實驗主要是要讓我們熟練樹與其相關知識熟練掌握先序中序后序遍歷，層次遍歷 然后我們自己畫一個圖 會實現(xiàn)以上功 能 以與葉子數(shù) 結(jié)點數(shù)

26、還有高度的計算 程序里面大量運用了遞歸以 與隊的應用，實驗三、圖的遍歷操作一、 目的掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖 的存儲結(jié)構(gòu)；掌握DFS與 BFS對圖的遍歷操作；了解圖結(jié)構(gòu)在人工 智能、工程等領域的廣泛應用。一、 要求采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無 向圖的DFS和BFS操作。三、DFS和BFS的根本思想深度優(yōu)先搜索法DFS的根本思想：從圖G中某個頂點 V出發(fā)， 首先訪問Vo,然后選擇一個與Vo相鄰且沒被訪問過的頂點 Vi訪問, 再從Vi出發(fā)選擇一個與Vi相鄰且沒被訪問過的頂點 Vj訪問， 依次繼續(xù)。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問

27、， 那么回退到已被訪問的頂點序列中最后一個擁有未被訪問的相鄰 頂點的頂點 W從W出發(fā)按同樣方法向前遍歷。直到圖中所有的頂 點都被訪問。廣度優(yōu)先算法BFS的根本思想：從圖G中某個頂點Vo出發(fā)，首先 訪問Vo,然后訪問與Vo相鄰的所有未被訪問過的頂點 V1, V2,Vt;再依次訪問與V1, V2,Vt相鄰的起且未被訪問過的的所 有頂點。如此繼續(xù)，直到訪問完圖中的所有頂點。四、程序源代碼1.鄰接矩陣作為存儲結(jié)構(gòu)的程序例如#i nclude"stdio.h"#i nclude"stdlib.h"#defi ne MaxVertexNum 100/定義最大頂點數(shù)t

28、ypedef structchar vexsMaxVertexNum; /頂點表int edgesMaxVertexNumMaxVertexNum; /鄰接矩陣，可看作邊表int n,e; /圖中的頂點數(shù)n和邊數(shù)eMGraph;/用鄰接矩陣表示的圖的類型/=建立鄰接矩陣=void CreatMGraph(MGraph *G)int i,j,k;char a;printf("Input VertexNum(n) and EdgesNum(e):");sca nf("%d,%d", &G-> n,&G->e);/輸入頂點數(shù)和邊數(shù)s

29、ca 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,Creat Adjace ncy Matrix' n");for(k

30、=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:深度優(yōu)先遍歷的遞歸算法=void DFSM(MGraph *G,i nt i) /以Vi為出發(fā)點對鄰接矩陣表示的圖 G進展DFS搜索

31、，鄰接矩陣是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為新出發(fā)點void DFS(MGraph *G)int i;for(i=0;i<G-> n;i+) visitedi=FALSE;/for(i=0;i<G-> n;i+)if(!visitedi)/ViDFSM(G,i);/=BFS廣度優(yōu)先遍歷= void BFS(MGra

32、ph *G,i nt k)訪問頂點Vi置已訪問標志依次搜索Vi的鄰接點Vi , Vj E,且Vj未訪問標志向量初始化未訪問過以Vi為源點開始DFS搜索/以Vk為源點對用鄰接矩陣表示的圖G進展廣度優(yōu)先搜索int i,j,f=O,r=O;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);/visitedk=TRUE;cqr=k;Vk將其序號入隊while(cqf!=-1) /i=

33、cqf; f=f+1;Vffor(j=0;j<G-> n;j+)/標志向量初始化隊列初始化訪問源點Vk已訪問，將其入隊。注意，實際上是隊非空那么執(zhí)行出隊依次Vi的鄰接點Vjif(G->edgesij=1 && !visitedj) /Vj訪問訪問Vj訪問過Vj入隊prin tf("%c",G->vexsj);/visitedj=TRUE;r二葉1; cqr=j;/mai nvoid mai n() int i;MGraph *G;G=(MGraph *)malloc(sizeof(MGraph); II 為圖 G申請存空間建立鄰接矩陣

34、深度優(yōu)先遍歷以序號為3的頂點開始廣度優(yōu)先遍CreatMGraph(G); IIprintf("Print Graph DFS:");DFS(G);IIprin tf("n");printf("Print Graph BFS:");BFS(G,3);II歷prin tf("n");調(diào)試結(jié)果:Input UertexNuin<n> and Edges=Nuit*<e>: 8,9Input Uertex string=0123456?Input edgesrCreat Adjacency Matr

35、ix0 1a 21 31 42 52 63 74 75 6Print Graph DFS= 01374ZS6Print Graph BPS: 3170425GPres key to continue自己畫的圖:1對應頂點下標0以此類推9對應下標8 預計運行結(jié)果：DFS:012345678BFS:324105687對應我這個圖：DFS 123456789BFS 435216798Input Uei*texNunCn> and Ede?NuniC&> - 9.10Input Vertex st103=012345678Input edges,Creat AdJcencsF fl

36、atrix0 16 51 21 42 33 45 65 8£ 77 8Print Graph DFS: 012345678Print Griph EFS = 32410568?Fres3 anv hey to continue實驗心得：圖在數(shù)據(jù)結(jié)構(gòu)中是相當重要的一局部 聯(lián)系很多現(xiàn)實問題 圖的根本就是頂點和邊 通過頂點和邊建立鄰接矩陣以與鄰接鏈表廣度搜索和深度搜索是此算法著重關注的地方。要學會自己畫圖然后寫出這兩種搜索的結(jié)果，程序中用了隊的算法是亮點 通過TRUE和FAUSE來標記頂點是否以與訪問防止重復實驗四、排序一、 目的掌握各種排序方法的根本思想、排序過程、算法實現(xiàn)，能進展時間和

37、空間性能的分析，根據(jù)實際問題的特點和要求選擇適宜的排序方 法。一、 要求實現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比 擬各種算法的運行速度。三、 程序例如#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大于等于有序區(qū)中所有的keys，那么Ri留在原位R0=Ri;j=i-1;do /R0是Ri的副本從右向左在有序區(qū)R1i-1中查找Ri的位置Rj+1=Rj;/將關鍵字大于Ri.key的記錄后移j-;while(R0.key<Rj.key);/當

39、 Ri.key> Rj.key是終止Rj+1=R0;/Ri插入到正確的位置上/en dif2、冒泡排序的根本思想：設想被排序的記錄數(shù)組 R1n垂直排序。根據(jù)輕氣泡不能在重氣泡之下的原那么，從下往上掃描數(shù)組R,凡掃描到違反本原那么的輕氣泡，就使其向上“漂浮交 換,如此反復進展，直到最后任意兩個氣泡都是輕者在上，重 者在下為止。二=冒泡排序=typedef enumFALSE,TRUE Boolean; /FALSE 為 0, TRUE為 1自下向上掃描對R做冒泡排序void BubbleSort(SeqList R) /int i,j;Boolea n excha nge;IIfor(i=

40、1;i< n;i+) II excha nge二FALSE;IIfor(j=n-1;j>=i;j-) II 掃描if(Rj+1.key<Rj.key) II 記錄R0=Rj+1; IIR0Rj+1=Rj;Rj=R0;excha nge二TRUE;II直/、if(!excha nge)II法return;交換標志最多做n-1趟排序本趟排序開始前，交換標志應為假對當前無序區(qū)Ri - n自下向上兩兩比較，滿足條件交換不是哨兵，僅做暫存單元發(fā)生了交換，故將交換標志置為本趟排序未發(fā)生交換，提前終止算IIendfor為循環(huán) 3、快速排序的根本思想：在待排序的n個記錄中任取一個記錄通常取第

41、一個記錄，把該記錄作為支點又稱基準記錄pivot，將所有關鍵字比它小的記錄放置在它的位置之前，將所有關鍵字比它大的記錄放置在它的位置之后(稱之為一次劃分過程)。之后對所分的兩局局部別重復上述過程，直到每局部只有一個記錄為止。1/1.= 一次劃分函數(shù)=int Partition(SeqList R,int i,int j)/對Ri -j做一次劃分，并返回基準記錄的位置RecType pivot=Ri; /用第一個記錄作為基準while(ivj) /從區(qū)間兩端交替向中間掃描，直到i=jwhile(i<j &&Rj.key>=pivot.key) /基準記錄 pivot

42、相當與在位置i上j-;/從右向左掃描，查找第一個關鍵字小于pivot.key 的記錄 Rjif(ivj) /假設找到的 Rj.key < pivot.key ，那么Ri+=Rj / 交換Ri和Rj，交換后i指針加1while(i<j &&Ri.keyv=pivot.key)/ 基準記錄pivot相當與在位置j上i+;/從左向右掃描，查找第一個關鍵字小于pivot.key 的記錄 Riif(ivj) /假設找到的Ri.key > pivot.key ，那么Rj-=Ri； 交換Ri和Rj，交換后j指針減1Ri=pivot; /此時，i=j ,基準記錄已被最后定位r

43、eturn i; /返回基準記錄的位置12=二快速排序=void QuickSort(SeqList R,i nt low,i nt high)快速排序Rlow.highint pivotpos;/劃分后基準記錄的位置if(low<high) /僅當區(qū)間長度大于1時才排序pivotpos=Partiti on (R,low,high);/對 Rlow.high做一次劃分，得到基準記錄的位置QuickSort(R,low,pivotpos-1);/對左區(qū)間遞歸排序4、QuickSort(R,pivotpos+1,high);直接選擇排序的根本思想:/對右區(qū)間遞歸排序第i趟排序開始時，當前有

44、序區(qū)和無序區(qū)分別為Rj i-1和Rin 1< i < n-1，該趟排序那么是從當前無序區(qū)中選擇出關鍵字最小的記錄Rk，將它與無序區(qū)的的第一個記錄Ri交換，有序區(qū)增加一個記錄，使 R1i,和Ri+1n分別為新的有序區(qū)和新的無序區(qū)。如此反復進展，直到排序完畢。/=直接選擇排序=void SelectSort(SeqList R)int i,j,k;for(i=1;i<n;i+)/做第 i 趟排序1< i < n-1k=i;for(j=i+1;j<=n;j+) /在當前無序區(qū) Rin中選key最小的記錄Rkif(Rj.key<Rk.key)k=j; /k記下

45、目前找到的最小關鍵字所在的位置if(k!=i) /交換 Ri禾口 RkR0=Ri；Ri=Rk;Rk=R0; /en dif en dfor5、堆排序的根本思想：它是一種樹型選擇排序，特點是：在排序的過程中，將R1n看成是一個完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的在關系，在當前無序 區(qū)中選擇關鍵字最大或最小的記錄。即：把待排序文件的關 鍵字存放在數(shù)組R1n子中，將R看成是一棵二叉樹，每個結(jié)點表示一個記錄，源文件的第一個記錄R1作為二叉樹的根，以下各記錄R2 - n依次逐層從左到右排列，構(gòu)成一棵完全二叉樹，任意結(jié)點Ri的左孩子是R2i，右孩子是R2i+1，雙親是Ri/2

46、。對這棵完全二叉樹的結(jié)點進展調(diào)整，使各結(jié)點的關鍵字滿足以下 條件：Ri.key < R2i.key 并且 Ri.key < R2i+1.key 稱小堆根或 Ri.key > R2i.key 并且 Ri.key > R2i+1.key 稱大堆根/=大根堆調(diào)整函數(shù)=void Heapify(SeqList R,i nt low,i nt high)/ 將Rlow.high調(diào)整為大根堆，除Rlow夕卜，其余結(jié)點均滿足堆性質(zhì)int large; /large指向調(diào)整結(jié)點的左、右孩子結(jié)點中關鍵字較大者RecType temp=Rlow; / 暫存調(diào)整結(jié)點for(large=2*l

47、ow; large<=high;large*=2) /Rlow是當前調(diào)整結(jié)點/假設large>high,那么表示Rlow是葉子，調(diào)整完畢；否那么先令large指向Rlow的左孩子if(large<high && Rlarge.key<Rlarge+1.key)large+; /假設Rlow的右孩子存在且關鍵字大于左兄弟，那么令large指向它/ 現(xiàn)在Rlarge是調(diào)整結(jié)點Rlow的左右孩子結(jié)點中關鍵 字較大者if(temp.key>=Rlarge.key) /temp始終對應 Rlowbreak; /當前調(diào)整結(jié)點不小于其孩子結(jié)點的關鍵字，完畢調(diào)整R

48、low=Rlarge; /相當于交換了 Rlow和 Rlargelow=large; / 令low指向新的調(diào)整結(jié)點，相當于 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)/對R仁n進展堆排序，不妨用R0做暫存單元int i;BuildHeap(R); / 將R1.n構(gòu)造為初始大根堆for(i=n

49、;i>1;i-)/對當前無序區(qū)R1.i進展堆排序，共做n-1趟。R0=R1； R1=Ri；Ri=R0；/將堆頂和堆中最后一個記錄交換Heapify(R,1,i-1); / 將 R1.i-1重新調(diào)整為堆，僅有R1可能違反堆性質(zhì)。6、二路歸并排序的根本思想：假設初始序列n個記錄，那么可看成是n個有序的子序列，每個子序列的長度為 1,然后兩兩歸并， 得到n/2個長度為2或1的有序子序列；再兩兩歸并，如 此重復，直到一個長度為n的有序序列為止。/=將兩個有序的子序列 Rlow.m和Rm+1.high歸并成有序 的序列 Rlow.high=void Merge(SeqList R,i nt low

50、,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) /假設第二個子序列非空，那么復制剩余記錄到R1中R1p+=Rj+；

51、for(p=0,i=low;i<=high;p+,i+)Ri=R1p; /歸并完成后將結(jié)果復制回 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+le ngth-1< n) /尚有一個子序列，其中后一個長度小于len gthMerge(R,i,i+le ngth-1, n); /歸并最后兩個子

52、序列/注意：假設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;i<=n ;i+)sca nf("%d"