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

實驗一、單鏈表的插入和刪除一、目的了解和掌握線性表的邏輯結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，掌握單鏈表的基本算法及相關(guān)的時間性能分析。二、要求：建立一個數(shù)據(jù)域定義為字符串的單鏈表，在鏈表中不允許有重復的字符串；根據(jù)輸入的字符串，先找到相應的結(jié)點,后刪除之.三、程序源代碼#include”stdio.h"#include"string。h"＃include”stdlib。h"＃include"ctype。h”typedefstructnode｛chardata［10]；串//結(jié)點的數(shù)據(jù)域為字符//結(jié)點的指針域structnode＊next;｝ListNode；typedefListNode*//自定義LinkList單鏈表類型LinkListCreatListR1(）;帶頭結(jié)點的單鏈表//函數(shù),用尾插入法建立數(shù)據(jù)結(jié)構(gòu)實驗報告ListNode*LocateNode（)；void點//函數(shù)，按值查找結(jié)點//函數(shù)，刪除指定值的結(jié)void值//函數(shù),打印鏈表中的所有void//==========主函數(shù)==============voidmain()//函數(shù),刪除所有結(jié)點,釋放內(nèi)存{charch[10]，num［10］;LinkListhead=CreatListR1()；printlist（head);//遍歷鏈表輸出其值printf("Deletenode(y/n）:");//輸入“y”或“n”去選擇是否刪除結(jié)點if（strcmp（num，"y”)==0|｜printf（"PleaseinputDelete_data:");scanf("％s",ch)；printlist(head)；//輸入要刪除的字符串}2數(shù)據(jù)結(jié)構(gòu)實驗報告//刪除所有結(jié)點，釋放內(nèi)存｝//==========用尾插入法建立帶頭結(jié)點的單鏈表===========LinkListCreatListR1（void）{charLinkList//生成頭結(jié)點ListNode＊s,*r，*pp;r=head;r—>next=NULL;printf("Input＃toend//輸入“#”代表輸入結(jié)束printf（”PleaseinputNode_data:");//輸入各結(jié)點的字符串｛//按值查找結(jié)點，返回結(jié)點指針中｛//沒有重復的字符串，插入到鏈表s=（ListNode*)malloc（sizeof(ListNode）)；strcpy(s-〉data,ch)；r—〉next=s;3數(shù)據(jù)結(jié)構(gòu)實驗報告r=s;r-〉next=NULL；}printf（”Input＃toendprintf（"Pleaseinputscanf（"％s",ch);｝return//返回頭指針}//==========按值查找結(jié)點，找到則返回該結(jié)點的位置,否則返回NULL==========ListNode*LocateNode(LinkListhead,char＊key)｛ListNode＊p=head—〉next;//從開始結(jié)點比較）//直到p為NULL或p->data為key止p=p—〉next；returnp;//掃描下一個結(jié)點p=NULL則查找失敗，否則p指向找到的值key的結(jié)點}//==========刪除帶頭結(jié)點的單鏈表中的指定結(jié)點=======voidDeleteList（LinkListhead，char*key)4數(shù)據(jù)結(jié)構(gòu)實驗報告｛ListNode*p,*r,*q=head；p=LocateNode(head,key)；if（p==NULL){key值查找結(jié)點的//若沒有找到結(jié)點，退出printf（”positionexit(0)；}//p為p的前結(jié)點q=q—〉next；r=q—>next；q->next=r—〉next；//釋放結(jié)點｝//===========打印鏈表=======voidprintlist(LinkList｛ListNode＊p=head->next；while(p){//從開始結(jié)點打印printf（"％s,p=p—>next；｝5數(shù)據(jù)結(jié)構(gòu)實驗報告｝//==========刪除所有結(jié)點，釋放空間===========voidDeleteAll（LinkListhead){ListNode*p=head，*r;r=p-〉next;free（p);p=r;｝free（p);｝運行結(jié)果:加的添加結(jié)點的代碼：intInsert(ListNode*head)//theinsertfunction｛ListNode＊in，*q;intwh;printf(”inputtheinsertnode:”in=（ListNode（sizeof（ListNodein-next=NULL;p=（ListNodemalloc(sizeof（ListNode);p->next=NULL；6數(shù)據(jù)結(jié)構(gòu)實驗報告q=(ListNode）mallocsizeof（ListNodeq-next=NULL;if（!in)return0;scanf(”%s",in->dataprintf（”inputtheplacewhereyouwanttoinsertyou；scanf(”%d”，＆）;forp=head；wh>0;p=p->next，——）;q=p->next；p—>next=in;in->next=q;return1；｝運行結(jié)果：最后提示為OK添加成功。實驗心得:這個實驗中主要修改的是ch和num把它們由指針改成數(shù)組因為不改的話在后面delect函數(shù)中會出現(xiàn)沒有地址的情況找不到地址就不能執(zhí)行功能然后把locate函數(shù)的判斷語句改一下避免矛盾的出現(xiàn)。實驗二、二叉樹操作一、目的掌握二叉樹的定義、性質(zhì)及存儲方式各種遍歷算法。7數(shù)據(jù)結(jié)構(gòu)實驗報告二、要求采用二叉樹鏈表作為存儲結(jié)構(gòu)完成二叉樹的建立序以及按層次遍歷的操作，求所有葉子及結(jié)點總數(shù)的操作.三、程序源代碼＃include"stdio。h"#include”string.h”#defineMax20typedefstructchar//結(jié)點的最大個數(shù)structnode＊lchild,*rchild；｝BinTNode；//自定義二叉樹的結(jié)點類型typedefBinTNode*BinTree;intNodeNum，leaf；//定義二叉樹的指針//NodeNum為結(jié)點數(shù)，leaf為葉子數(shù)//==========基于先序遍歷算法創(chuàng)建二叉樹==============//=====要求輸入先序序列，其中加入虛結(jié)點“?！币允究罩羔樀奈恢?=========BinTreeCreatBinTree（void）｛BinTreecharif((ch=getchar(）)==’?！?return（NULL）;//讀入＃，返回空指針8數(shù)據(jù)結(jié)構(gòu)實驗報告else{T=（BinTNode//生成結(jié)點T—>data=ch;T->lchild=CreatBinTree();T—>rchild=CreatBinTree(）;return(T)；//構(gòu)造右子樹}}//========NLR先序遍歷=============voidPreorder（BinTreeT){if(T）{printf（”％c",T-〉data);//訪問結(jié)點Preorder(T-〉lchild);//先序遍歷左子樹Preorder(T—>rchild);//先序遍歷右子樹}}//========LNR中序遍歷===============voidInorder(BinTreeT){if(T）｛9數(shù)據(jù)結(jié)構(gòu)實驗報告Inorder(T->lchild)；//中序遍歷左子樹//訪問結(jié)點Inorder（T->rchild)；//中序遍歷右子樹}}//==========LRN后序遍歷============voidPostorder(BinTree{if（T）{Postorder（T-〉lchild)；//后序遍歷左子樹//后序遍歷右子樹//訪問結(jié)點}｝//=====采用后序遍歷求二叉樹的深度、結(jié)點數(shù)及葉子數(shù)的遞歸算法========intTreeDepth（BinTree{inthl,hr，max;if（T)｛hl=TreeDepth(T—〉lchild）;hr=TreeDepth（T->rchild）;//求左深度//求右深度10數(shù)據(jù)結(jié)構(gòu)實驗報告max=hl〉hr?hl：hr;NodeNum=NodeNum+1；//取左右深度的最大值//求結(jié)點數(shù)if(hl==0&＆hr==0）leaf=leaf+1;//若左右深度為}elsereturn(0）;}voidLevelorder（BinTreeT){intfront=0，rear=1;BinTNode//定義結(jié)點的指針數(shù)組cqcq［1]=T;while（front!=rear)｛front=（front+1)％NodeNum;p=cq［front］;if（p-〉lchild!=NULL）{//出隊,輸出結(jié)點的值rear=（rear+1)％NodeNum；cq［rear］=p->lchild;//左子樹入隊}11數(shù)據(jù)結(jié)構(gòu)實驗報告rear=（rear+1)%NodeNum；cq[rear]=p—>rchild;//右子樹入隊}}}//==========主函數(shù)=================voidmain(）{BinTreeroot;inti，depth;printf(”\n"）;printf（"CreatBin_Tree；Inputpreorder：");//輸入完全二叉樹的先序序列，//用#代表虛結(jié)點,如ABD＃＃＃CE＃＃F##root=CreatBinTree（)；//創(chuàng)建二叉樹，返回根結(jié)點//從菜單中選擇遍歷方式，輸入序號.do｛select＊*＊*＊＊＊*＊＊＊＊\n")；printf(”\t1：PreorderTraversal\n");printf（"\t2:IorderTraversal\n"）;12數(shù)據(jù)結(jié)構(gòu)實驗報告printf("\t3：Postorderprintf（"\t4:PostTreeDepth,Nodenumber，Leafnumber\n")；printf（”\t5:LevelDepth\n”)；//按層次遍歷之前,先選擇4,求出該樹的結(jié)點數(shù)。printf（"\t0:Exit\n")；printf（"\t＊**＊***＊＊＊******＊＊＊＊****＊＊**＊**\n”);scanf（"％d”,&i）;switch//輸入菜單序號（0—5)case1:printf（”PrintBin_treePreorder:"Preorder（root)；break；//先序遍歷case2：printf（"PrintBin_TreeInorder:");break;//中序遍歷case3:printf(”PrintBin_Treebreak；//后序遍歷case4：depth=TreeDepth(root)；葉子數(shù)//求樹的深度及printf（”BinTreeBinTreeNode13數(shù)據(jù)結(jié)構(gòu)實驗報告printf（”BinTreeLeafbreak；case5:printf("LevePrintBin_Tree://按層次遍歷break;default:｝printf（"\n”);｝while（i！=0)；｝執(zhí)行程序1.先序遍歷2.中序遍歷3.后序遍歷4.結(jié)點數(shù)葉子數(shù)高度5..層次遍歷自己設(shè)計的：abdhl＃#i##e#jn#cf＃kog#＃1.預計先序遍歷結(jié)果：abdhlmiejncfkog2。預計中序遍歷結(jié)果：lhmdibenjafokcg3。預計后序遍歷結(jié)果:lmhidnjebokfgca14數(shù)據(jù)結(jié)構(gòu)實驗報告4.結(jié)點數(shù)15高度5葉子數(shù)6實際結(jié)果:實驗心得：這次實驗主要是要讓我們熟練樹及其相關(guān)知識熟練掌握然后我們自己畫一個圖會實現(xiàn)以上功能以及葉子數(shù)結(jié)點數(shù)還有高度的計算程序里面大量運用了遞歸以及隊的應用，實驗三、圖的遍歷操作一、目的掌握有向圖和無向圖的概念;掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu)；掌握DFS及BFS對圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應用.二、要求采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作。三、DFS和BFS的基本思想深度優(yōu)先搜索法DFSG中某個頂點出發(fā)，首先訪問相鄰且沒被訪問過的頂點Vi,再從Vi出發(fā)選擇一個與Vi相鄰且沒被訪問過的頂點Vj依次繼續(xù)。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則回退到已被訪問的頂點序列中最后一個擁有未被訪問的相鄰頂點的頂點，從W出發(fā)按同樣方法向前遍歷。直到圖中所有的頂15數(shù)據(jù)結(jié)構(gòu)實驗報告點都被訪問。廣度優(yōu)先算法BFS的基本思想：從圖G中某個頂點,首先訪問然后訪問與相鄰的所有未被訪問過的頂點V1，V2，……；再依次訪問與V1，，……，Vt相鄰的起且未被訪問過的的所有頂點。如此繼續(xù)，直到訪問完圖中的所有頂點。四、程序源代碼．鄰接矩陣作為存儲結(jié)構(gòu)的程序示例＃include"stdio。h"＃include"stdlib.h”＃defineMaxVertexNum100typedefcharvexs［MaxVertexNum];intedges[MaxVertexNum][MaxVertexNum];//鄰接矩陣，可看作邊表int｝MGraph;//圖中的頂點數(shù)n和邊數(shù)e//用鄰接矩陣表示的圖的類型//=========建立鄰接矩陣=======voidCreatMGraph(MGraph*G){inti，j,k；chara;printf(”InputVertexNum（n）andEdgesNum（e）:16數(shù)據(jù)結(jié)構(gòu)實驗報告//輸入頂點數(shù)和邊數(shù)scanf（”％c",&a)；printf（"InputVertexfor（i=0；i〈G-〉n;i++）｛scanf("%c",&a)；G—〉vexs[i]=a;//讀入頂點信息,建立頂點表}for(i=0;i〈G->n;i++)for（j=0；j〈G—〉n；j++）G—〉edges［i][j］=0;//初始化鄰接矩陣printf(”Inputedges,CreatAdjacencyfor（k=0；k<G-〉e；k++）｛//讀入e條邊，建立鄰接矩陣序號G—>edges[i]［j］=1；//若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句｝｝17數(shù)據(jù)結(jié)構(gòu)實驗報告//=========定義標志向量，為全局變量=======typedefenum｛FALSE，TRUE｝Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度優(yōu)先遍歷的遞歸算法======voidDFSM(MGraph＊G，int{//以Vi為出發(fā)點對鄰接矩陣表示的圖G進行DFS搜索，鄰接矩陣是0，1矩陣int//訪問頂點Vivisited[i］=TRUE；//置已訪問標志for(j=0；j<G—〉n；j++）//依次搜索Vi的鄰接點！visited[j］)DFSM(G,j);故Vj為新出發(fā)點}Vj未訪問過，voidDFS(MGraph＊G）｛intfor（i=0；i<G->n；i++)visited［i]=FALSE；for(i=0；i<G—〉n;i++）if(！visited［i])//標志向量初始化//Vi未訪問過18數(shù)據(jù)結(jié)構(gòu)實驗報告DFSM(G,i)；Vi為源點開始DFS搜索}//===========BFS:廣度優(yōu)先遍歷=======voidBFS(MGraph＊G，int｛Vk為源點對用鄰接矩陣表示的圖G進行廣度優(yōu)先搜索inti，j,f=0,r=0；intcq[MaxVertexNum]；for（i=0;i<G-〉n;i++)visited[i]=FALSE；//定義隊列//標志向量初始化for(i=0；i<G—〉n；i++)cq［i］=-1；//訪問源點Vkprintf(”%c",G—〉vexs［k]）;visited[k］=TRUE;cq［r］=k;//Vk已訪問，將其入隊。注意，實際上是將其序號入隊while（cq［f]！=—1){i=cq[f］;f=f+1；for（j=0;j〈G->n；j++)//隊非空則執(zhí)行//Vf出隊Vi的鄰接點Vj&&｛//Vj未訪問Vj19數(shù)據(jù)結(jié)構(gòu)實驗報告visited［j］=TRUE；r=r+1;//訪問過Vj入隊}}}//==========main=====voidmain()｛inti;MGraph＊G；G=(MGraph//為圖G申請內(nèi)存空間CreatMGraph（G）;printf（"PrintGraphDFS://建立鄰接矩陣DFS(G)；//深度優(yōu)先遍歷printf（"PrintGraphBFS(G,3）;//以序號為3的頂點開始廣度優(yōu)先遍歷｝printf（"\n"）;調(diào)試結(jié)果：20數(shù)據(jù)結(jié)構(gòu)實驗報告自己畫的圖：1對應頂點下標0以此類推9對應下標8預計運行結(jié)果：DFS:012345678BFS:324105687對應我這個圖：DFS：123456789BFS：435216798實驗心得:圖在數(shù)據(jù)結(jié)構(gòu)中是相當重要的一部分聯(lián)系很多現(xiàn)實問題圖的根本就是頂點和邊通過頂點和邊建立鄰接矩陣以及鄰接鏈表廣度搜索和深度搜索是此算法著重關(guān)注的地方。要學會自己畫圖然是亮點通過TRUE和FAUSE來標記頂點是否以及訪問避免重復實驗四、排序一、目的掌握各種排序方法的基本思想、排序過程、算法實現(xiàn)，能進行時間和空間性能的分析,根據(jù)實際問題的特點和要求選擇合適的排序方法。二、要求實現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運行速度.21數(shù)據(jù)結(jié)構(gòu)實驗報告三、程序示例＃include"stdio。h"#include”stdlib。h"＃defineMax100typedefintkey;//定義記錄類型}RecType；typedefRecType//SeqList為順序表，表中第0個元素作為哨兵intn;//順序表實際的長度、直接插入排序的基本思想:每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已排序好的子文件中的適當位置，直到全部記錄插入完成為止。//==========直接插入排序法======voidInsertSort（SeqList｛//對順序表R中的記錄R[1‥n］按遞增序進行插入排序inti,j;for（i=2;i〈=n；i++)//依次插入R[2］,……，R[n］R[i］.key大于等于有序區(qū)中所有的keys，則R[i]留在原位R［0]=R［i]；j=i—1;do｛//R［0]是R［i］的副本//從右向左在有序區(qū)22數(shù)據(jù)結(jié)構(gòu)實驗報告找R[i］的位置//將關(guān)鍵字大于的記錄后移j——;//當是終止//R[i］插入到正確的位置上｝//endif}2、R[1‥n]垂直排止。//==========冒泡排序=======typedefenum｛FALSE，TRUE}Boolean;//FALSE為0,TRUE為1voidBubbleSort(SeqListR)｛//自下向上掃描對R做冒泡排序inti，j；Booleanexchange；//交換標志for(i=1;i〈n；i++){n-1趟排序23數(shù)據(jù)結(jié)構(gòu)實驗報告exchange=FALSE；//本趟排序開始前，交換標志應為假//對當前無序區(qū)R[i‥n］自下向上掃描//兩兩比較，滿足條件交換記錄元R［j]=R[0］;exchange=TRUE；//本趟排序未發(fā)生交換，提前終止真｝if(!exchange）算法return;endfor（為循環(huán)）}、快速排序的基本思想：在待排序的n個記錄中任取一個記錄（通常取第一個記錄），把該記錄作為支點（又稱基準記錄)（pivot有關(guān)鍵字比它大的記錄放置在它的位置之后（稱之為一次劃分過程）之后對所分的兩部分分別重復上述過程，直到每部分只有一24數(shù)據(jù)結(jié)構(gòu)實驗報告?zhèn)€記錄為止。//1。========一次劃分函數(shù)=====intPartition（SeqListi,intj)｛//對R[i‥j］做一次劃分，并返回基準記錄的位置RecTypewhile(i〈j）{//用第一個記錄作為基準//從區(qū)間兩端交替向中間掃描，直到i=jwhile(i<j//基準記錄pivot相當與在位置i上j-—;pivot。key的記錄R[j]//從右向左掃描，查找第一個關(guān)鍵字小于if（i〈j)//若找到的R［j]。key〈pivot。key，則R［i++］=R[j］;//交換R[i]和i指針加1錄pivot相當與在位置j上//基準記i++；//從左向右掃描,查找第一個關(guān)鍵字小于pivot。key的記錄R［i］if（i<j）//若找到的R[i］.key>pivot.key，則R[j——］=R[i];//交換R[i］和R［j]，交換后j指針減1｝25數(shù)據(jù)結(jié)構(gòu)實驗報告R［i]=pivot;return//此時，i=j，基準記錄已被最后定位//返回基準記錄的位置}//2.=====快速排序===========voidQuickSort（SeqListlow，inthigh）｛//劃分后基準記錄的位置//僅當區(qū)間長度大于1時才排序intif(low<high）{R［low..high］做一次劃分，得到基準記錄的位置QuickSort(R，low，pivotpos-1);//對左區(qū)間遞歸排序//對右區(qū)間遞歸排序QuickSort（R，pivotpos+1,high);}}、i趟排序開始時當前有序區(qū)和無序區(qū)分別為R[1‥i—1］和1）,該趟排序則是從當前無序區(qū)中選擇出關(guān)鍵字最小的記錄的的第一個記錄和R［i+1‥n］分別為新的有序區(qū)和新的無序區(qū)。如此反復進行，直到排序完畢。//======直接選擇排序========voidSelectSort(SeqListR)26數(shù)據(jù)結(jié)構(gòu)實驗報告｛inti,j,k;for(i=1;i〈n；i++）{k=i；i趟排序（1≤i≤n1）//在當前無序區(qū)key最小的記錄R[k］if(R［j]。key<R[k].key)k=j;//k記下目前找到的最小關(guān)鍵字所在的位置if（k!=i)｛//R[i］和R［k]R［0]=R[i]；R［i］=R［k］;R［k］=R［0];}//endif｝//endfor｝、的過程中，將‥］看成是一個完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系，在當前無序區(qū)中選擇關(guān)鍵字最大（或最?。┑挠涗?:把待排序文件的關(guān)鍵字存放在數(shù)組［1n］子中，將R看成是一棵二叉樹，每個結(jié)點表示一個記錄源文件的第一個記錄R［1］作為二叉樹的根,以下各記錄R［2‥n］依次逐層從左到右排列，構(gòu)成一棵完全二叉樹，任意結(jié)點［的左孩子是R2i］右孩子是R[2i+1]，雙27數(shù)據(jù)結(jié)構(gòu)實驗報告親是R[i/2字滿足下列條件：［i并且［稱小堆根或［并且稱大堆根//==========大根堆調(diào)整函數(shù)=======voidHeapify（SeqListR，intlow,inthigh)｛//將均滿足堆性質(zhì)intlarge;//large指向調(diào)整結(jié)點的左、右孩子結(jié)點中關(guān)鍵字較大者RecTypetemp=R[low］;//暫存調(diào)整結(jié)點for（large=2*low;//R[low]是當前調(diào)整結(jié)點large〉high,則表示R［low]是葉子，調(diào)整結(jié)束;否則先令large指向R[low］的左孩子if(large<high&&R[large].key〈R[large+1]。key)large++；//若R［low］的右孩子存在且關(guān)鍵字大于左兄弟，則令large指向它//現(xiàn)在R[large］是調(diào)整結(jié)點R［low]的左右孩子結(jié)點中關(guān)鍵字較大者28數(shù)據(jù)結(jié)構(gòu)實驗報告//temp始終對應break;束調(diào)整//相當于交換了low=large；//令lowtemp已篩下到large的位置｝R[low]=temp；//將被調(diào)整結(jié)點放入最終位置上}//==========構(gòu)造大根堆==========voidBuildHeap(SeqList{//將初始文件R[1.。n］構(gòu)造為堆intfor（i=n/2;i〉0；i--)//將R［i。.n]調(diào)整為大根堆}//==========堆排序===========voidHeapSort(SeqListR)｛元intBuildHeap(R);R[1.。n］構(gòu)造為初始大根堆29數(shù)據(jù)結(jié)構(gòu)實驗報告排序，共做n-1趟。//對當前無序區(qū)R[0］=R[1]；R[1］=R[i］;R[i］=R[0];中最后一個記錄交換//將1]重新調(diào)整為堆，僅有R[1］可能違反堆性質(zhì)。//將堆頂和堆｝｝、n是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并,得2或1的有序子序列;再兩兩歸并,……,如此重復,直到一個長度為n的有序序列為止。//=====將兩個有序的子序列R[m+1.。high］歸并成有序的序列R［low。.high］==voidMerge(SeqListlow,inthigh）{inti=low，j=m+1，p=0;//置初始值RecType*R1;//R1為局部量R1=(RecType//申請空間＆＆j<=high）者輸出到R1［p］上//兩個子序列非空時取其小30數(shù)據(jù)結(jié)構(gòu)實驗報告R1［p++］=（R［i].key<=R[j].key)?R［i++］:R[j++]；while(i<=m)//若第一個子序列非空，則復制剩余記錄到R1R1[p++]=R[i++]；到R1中for（p=0,i=low；i<=high;p++,i++）R[i]=R1[p];//歸并完成后將結(jié)果復制回｝//=========對R［1。.n］做一趟歸并排序========voidMergePass（SeqListR,intlength){intfor（i=1；i+2＊length—1<=n;i=i+2＊length）//歸并長度為length的兩個相鄰的子序列//尚有一個子序列，其中后一