中北大學(xué)軟件學(xué)院算法實驗報告(附截圖)

中北大學(xué)軟件學(xué)院實驗報告專 業(yè)： 方 向： 課程名稱： 班 級： 學(xué) 號： 姓 名： 輔導(dǎo)教師： 2016年3月制成績： 成績： 成績： 成績： 實驗時間2016年4月7日8時至10時學(xué)時數(shù)2.實驗名稱實驗一串匹配程序設(shè)計.實驗?zāi)康蘑攀炀氄莆沾ヅ涞暮x⑵掌握BF算法匹配的過程并編程實現(xiàn)⑶熟悉C++編譯環(huán)境的基本操作.實驗內(nèi)容給定兩個字符詣和T，用BF算法，在主串S中查找字串T，輸出結(jié)果，輸出時要求有文字說明。請編寫程序。.實驗原理或流程圖基本思想：從主串S的第一個字符開始和模式T的第一個字符進行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；若不相等，則從主串S的第二個字符開始和模式T的第一個字符進行比較，重復(fù)上述過程，若T中的字符全部比較完畢，則說明本趟匹配成功；若最后一輪匹配的起始位置是n-m，則主串S中剩下的字符不足夠匹配整個模式T，匹配失敗。這個算法稱為樸素的模式匹配算法，簡稱BF算法。設(shè)串S長度為n，串T長度為m，在匹配成功的情況下，考慮最壞情況，即每趟不成功的匹配都發(fā)生在串T的最后一個字符。設(shè)匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了(i-1)Xm次，第i趟成功的匹配共比較了m次，所以總共比較了iXm次，因此平均比較次數(shù)是：n甘1 /.、n甘11 /.、m(n—m+2)乙px(ixm)=乙 x(ixm)= i n-m+1 2i=1 i=1最壞情況是O(nXm)?；蛘邔憰螾39頁的偽代碼描述。5.5.實驗過程或源代碼5.5.實驗過程或源代碼#include<stdio.h>intBF(charS[],charT[]){intindex=0; 〃主串從下標(biāo)0開始第一趟匹配inti=0,j=0； 〃設(shè)置比較的起始下標(biāo)while((S[i]!='\0')&&(T[j]!=''0')){ //模式匹配沒有結(jié)束printf("->從主串的第％d個位置開始與模式串進行匹配：(只輸出回溯信息)\n",i);if(S[i]==T[j]){//相同位置字符相同i++;j++;//向后匹配}else{〃相同位置字符不同printf("由于主串下標(biāo)i為％d的字符％c和模式串下標(biāo)j為％d的字符％c失配",i,S[i],j,T[j]);index++;i=index;j=0;//i和j分別回溯printf("所以i和j分別回溯到％d,%d重新開始匹配\n",i,j);}}if(T[j]=='\0')returnindex+1; 〃返回本趟匹配的開始位置(不是下標(biāo))elsereturn0;}intmain(){charS[100],T[100];printf("請輸入主串S(不超過100個字符)：”)；scanf("%s",S);printf("請輸入子串T(不超過100個字符)：”)；scanf("%s",T);intindex=BF(S,T);if(index==0){printf("模式匹配失敗！”)；}else{printf("模式匹配成功，子串%s在主串%s中首次匹配的位置是%d",T,S,index);}return0;}成績： 成績： 成績： 成績： 6.實驗結(jié)論及心得通過本次實驗我理解了使用蠻力法解決問題的特點，蠻力法的設(shè)計思想是直接基于問題本身的描述來設(shè)計算法，即不采用任何方法來精簡計算過程、運算次數(shù)或者設(shè)法簡化問題本身。所以蠻力法設(shè)計的算法雖然簡單易懂，但是效率卻往往不是很令人滿意，比如串的模式匹配問題中采用BF算法效率低下的主要原因就在于BF算法一旦主串和子串匹配失敗就會產(chǎn)生回溯，如果能利用已有的匹配結(jié)果來減少回溯就可以提高效率，如KMP算法。實驗時間2016年4月7日8時至10時學(xué)時數(shù)2.實驗名稱實驗二排序問題程序設(shè)計.實驗?zāi)康?1)掌握選擇排序和起泡排序的基本思想⑵掌握兩種排序方法的具體實現(xiàn)過程⑶在掌握的基礎(chǔ)上編程實現(xiàn)兩種排序方法.實驗內(nèi)容輸入一個待排序的序列，分別用選擇排序和起泡排序兩種排序方法將其變換成有序的序列，輸出結(jié)果，輸出時要求有文字說明。請編寫程序。.實驗原理或流程圖書上P42頁選擇排序想法三點抄上去書上P43頁冒泡排序想法三點抄上去5.5.實驗過程或源代碼5.5.實驗過程或源代碼// 選擇排序 #include<stdio.h>//對含有n個數(shù)的數(shù)組進行遍歷voidvisit(intr[],intn){for(inti=0;i<n;i++)printf("%4d",r[i])；printf("\n");}//選擇排序voidSelectSort(intr[],intn){inti,j,index,temp;intcompare=0,move=0;for(i=0;i<n-1;i++){ 〃對n個記錄進行n-1趟選擇排序index=i;for(j=i+1;j<n;j++){//在無序區(qū)中查找最小記錄if(r[j]<r[index])index=j;coimpare++;//比較次數(shù)增加1}if(index!=i){//交換記錄temp=r[i];r[i]=r[index];r[index]=temp;move+=3;//交換一次移動3次}visit(r,10);}printf("在本次排序中共比較y%d次，移動y%d次。\n",coimpare,move);}intmain(){intr[10]={0};printf("請依次輸入10個整數(shù)，用空格隔開：\n");for(inti=0;i<10;i++)scanf("%d”,&r[i]);printf("排序之前的記錄：\n");visit(r,10);printf("進行選擇排序：(每趟排序后的結(jié)果如下所示八n");SelectSort(r,10);printf("排序之后的記錄：\n");visit(r,10);return0;}// 選擇排序 #include<stdio.h>//對含有n個數(shù)的數(shù)組進行遍歷voidvisit(intr[],intn){for(inti=0;i<n;i++)printf("%4d",r[i])；printf("\n");}voidBubbleSort(intr[],intn){intcountl=0,count2=0;//countl和count2記載比較次數(shù)和移動次數(shù)intbound,exchange=n-1; 〃第一趟起泡排序的區(qū)間是[0,n-1]while(exchange!=0){ 〃當(dāng)上一趟排序有記錄交換時bound=exchange;exchange=0;for(intj=0;j<bound;j++) 〃一趟起泡排序區(qū)間是[0,bound]if(++count1&&r[j]>r[j+1]){ 〃注意不能寫作count1++inttemp=r[j];r[j]=r[j+1];r[j+1]=temp;count2=count2+3; //1次交換是3次移動操作exchange=j; 〃記載每一次記錄交換的位置}visit(r,10);//每趟排序輸出一次，觀察記錄的變動情況}printf("本次排序中的比較次數(shù)為％d,移動次數(shù)為％d。\n",count1,count2);}intmain(){intr[10]={0};printf("請依次輸入10個整數(shù)，用空格隔開：\n");for(inti=0;i<10;i++)scanf("%d”,&r[i]);printf("排序之前的記錄：\n");visit(r,10);printf("進行冒泡排序：(每趟排序后的結(jié)果如下所示八n");BubbleSort(r,10);printf("排序之后的記錄：\n");visit(r,10);return0;6.實驗結(jié)論及心得通過本次實驗我理解了選擇排序和起泡排序的基本思想。選擇排序和起泡排序都是通過將待排序記錄劃分成有序區(qū)和無序區(qū)，然后通過交換擴大有序區(qū)，縮小無序區(qū)，最終達到排序的目的。兩者又有區(qū)別，選擇排序可以直接選出無序區(qū)的最小記錄并一次插入到合適的位置上，之后不再調(diào)整，而冒泡排序則是通過兩兩交換實現(xiàn)移動的，由于很多移動無法將記錄一次放置到合適的位置上，所以存在很多“無效”的移動操作，從實驗結(jié)果可以看出，起泡排序的移動次數(shù)明顯比選擇排序要多就是因為這樣的“無效”的移動操作浪費了時間。成績： 成績： 成績： 成績： 實驗時間2016年4月7日8時至10時學(xué)時數(shù)21.實驗名稱實驗三數(shù)字旋轉(zhuǎn)方陣程序設(shè)計.實驗?zāi)康?1)掌握分治法的設(shè)計思想⑵掌握數(shù)字旋轉(zhuǎn)方陣的具體實現(xiàn)過程⑶熟練掌握二維數(shù)組的使用方法(4)在掌握的基礎(chǔ)上編程實現(xiàn)數(shù)字旋轉(zhuǎn)方陣的實現(xiàn)過程.實驗內(nèi)容給出一個初始數(shù)據(jù)，在此數(shù)據(jù)的基礎(chǔ)上由外層向里層填寫數(shù)據(jù)，完成一個數(shù)字旋轉(zhuǎn)方陣，輸出結(jié)果，輸出時要求有文字說明。請編寫程序。.實驗原理或流程圖用二維數(shù)組data[N][N]表示NXN的方陣，觀察方陣中數(shù)字的規(guī)律，可以從外層向里層填數(shù)。設(shè)變量size表示方陣的大小，則初始時size=N，填完一層則size=size-2；設(shè)變量begin表示每一層的起始位置，變量i和j分別表示行號和列號，則每一層初始時i=begin，j=begin。將每一層的填數(shù)過程分為A、B、C、D四個區(qū)域，則每個區(qū)域需要填寫size-1個數(shù)字，填寫區(qū)域A時列號不變行號加1,填寫區(qū)域B時行號不變列號加1,填寫區(qū)域C時列號不變行號減1,填寫區(qū)域D時行號不變列號減1。顯然，遞歸的結(jié)束條件是size等于0或size等于1?！緦懖幌戮退懔恕繑?shù)字旋轉(zhuǎn)方陣算法描述：輸入：當(dāng)前層左上角要填的數(shù)字number，左上角的坐標(biāo)begin，方陣的階數(shù)size輸出：數(shù)字旋轉(zhuǎn)方陣.如果size等于0，則算法結(jié)束；number,算法結(jié)束;.如果size等于1，則number,算法結(jié)束;.初始化行、列下標(biāo)i=begin,j=begin；4.5.6.7.重復(fù)下述操作size-1次，填寫區(qū)域A4.1data[i][j]=number;number++;重復(fù)下述操作4.5.6.7.重復(fù)下述操作size-1次，填寫區(qū)域A4.1data[i][j]=number;number++;重復(fù)下述操作size-1次，填寫區(qū)域B5.1data[i][j]=number;number++;重復(fù)下述操作size-1次，填寫區(qū)域C6.1data[i][j]=number;number++;重復(fù)下述操作size-1次，填寫區(qū)域D7.1data[i][j]=number;number++;4.25.26.27.2行下標(biāo)i++;列下標(biāo)不變;行下標(biāo)不變；列下標(biāo)j++;行下標(biāo)i--；列下標(biāo)不變;行下標(biāo)不變，列下標(biāo)j--；8.8.調(diào)用函數(shù)Full在size-2階方陣中左上角begin+1處從數(shù)字number開始填數(shù);5.5.實驗過程或源代碼5.5.實驗過程或源代碼#include<stdio.h>intdata[100][100]={0};intmaxsize=0;voidprintData(intsize){for(inti=0;i<size;i++){for(intj=0;j<size;j++)printf("%4d",data[i][j]);printf("\n");}printf("\n");}voidFull(intnumber,intbegin,intsize){〃從number開始填寫size階方陣，左上角的下標(biāo)為(begin,begin)inti,j,k;if(size==0) inti,j,k;if(size==0) 〃遞歸的邊界條件return;if(size==1){data[begin][begin]=number;printData(maxsize);return;}i=begin;j=begin;for(k=0;k<size-1;k++){data[i][j]=number;number++;i++;}for(k=0;k<size-1;k++){data[i][j]=number;number++;j++;}for(k=0;k<size-1;k++){data[i][j]=number;number++;i--;}for(k=0;k<size-1;k++){data[i][j]=number;number++;j--;}printData(maxsize);如果size等于0，則無須填寫〃遞歸的邊界條件，如果size等于1〃則只須填寫number〃初始化左上角下標(biāo)〃填寫區(qū)域A，共填寫size-1個數(shù)〃在當(dāng)前位置填寫number〃行下標(biāo)加1〃填寫區(qū)域B，共填寫size-1個數(shù)〃在當(dāng)前位置填寫number〃列下標(biāo)加1//填寫區(qū)域C，共填寫size-1個數(shù)〃在當(dāng)前位置填寫number〃行下標(biāo)減1//填寫區(qū)域D，共填寫size-1個數(shù)〃在當(dāng)前位置填寫number〃列下標(biāo)減1Full(number,begin+1,size-2);//遞歸求解，左上角下標(biāo)為begin+1intmain(){intsize;printf("輸入方陣的大?。骸?；scanf("%d",&size);maxsize=size;printf("開始填充之前的數(shù)字旋轉(zhuǎn)方陣：\n");printData(maxsize);printf("填充過程：\n");Full(1,0,size);printf("最終填充完成的結(jié)果是：\n");printData(maxsize);return0;}6.實驗結(jié)論及心得通過本次實驗，我理解了分治法解決問題的基本思想和一般過程，分治法的基本思想是“分而治之”，將大的復(fù)雜的問題分解成結(jié)構(gòu)同、規(guī)模小的子問題，分解子問題要足夠小以至于可以直接得出子問題的解，然后對子問題的解進行合并，最終得到原問題的解。由于程序中采用了遞歸技術(shù)，需要設(shè)置遞歸終止的條件，在數(shù)字旋轉(zhuǎn)方陣問題中，遞歸結(jié)束的條件是size等于0或者1。遞歸問題的解決分為回溯和遞推兩個階段，通過這兩個過程可以求解本次實驗的問題。5.5.實驗過程或源代碼5.5.實驗過程或源代碼成績： 成績： 實驗時間2016年4月8日8時至10時學(xué)時數(shù)2.實驗名稱實驗四排序中分治法的程序設(shè)計.實驗?zāi)康?1)掌握歸并排序和快速排序的劃分方法⑵掌握歸并排序和快速排序的具體分治策略⑶在掌握的基礎(chǔ)上編程兩種排序方法的實現(xiàn)過程.實驗內(nèi)容給出一個初始序列，分別用歸并排序和快速排序兩種分治法將所給序列變換為有序序列，輸出結(jié)果，輸出時要求有文字說明。請編寫程序。.實驗原理或流程圖二路歸并排序的分治策略是：(1)劃分：將待排序序列ri,r2,…，rn劃分為兩個長度相等的子序列r1,…，rn/2和rn/2+i,…，rn；(2)求解子問題：分別對這兩個子序列進行排序，得到兩個有序子序列；(3)合并：將這兩個有序子序列合并成一個有序序列?？焖倥判虻姆种尾呗允牵?1)劃分：選定一個記錄作為軸值，以軸值為基準(zhǔn)將整個序列劃分為兩個子序列ri…ri-1和ri+1…rn,前一個子序列中記錄的值均小于或等于軸值，后一個子序列中記錄的值均大于或等于軸值；(2)求解子問題：分別對劃分后的每一個子序列遞歸處理；(3)合并：由于對子序列ri…ri-1和ri+1…rn的排序是就地進行的，所以合并不需要執(zhí)行任何操作?！緦懖幌戮筒粚懥恕恳缘谝粋€記錄作為軸值，對待排序序列進行劃分的過程為：(1)初始化：取第一個記錄作為基準(zhǔn)，設(shè)置兩個參數(shù)i,j分別用來指示將要與基準(zhǔn)記錄進行比較的左側(cè)記錄位置和右側(cè)記錄位置，也就是本次劃分的區(qū)間；(2)右側(cè)掃描過程：將基準(zhǔn)記錄與j指向的記錄進行比較，如果j指向記錄的關(guān)鍵碼大，則j前移一個記錄位置。重復(fù)右側(cè)掃描過程，直到右側(cè)的記錄小(即反序)，若i<j,則將基準(zhǔn)記錄與j指向的記錄進行交換；(3)左側(cè)掃描過程：將基準(zhǔn)記錄與i指向的記錄進行比較，如果i指向記錄的關(guān)鍵碼小，則i后移一個記錄位置。重復(fù)左側(cè)掃描過程，直到左側(cè)的記錄大(即反序)，若i<j,則將基準(zhǔn)記錄與i指向的記錄交換；(4)重復(fù)(2)(3)步，直到i與j指向同一位置，即基準(zhǔn)記錄最終的位置。

// 歸并排序 #include<stdio.h>//對含有n個數(shù)的數(shù)組進行遍歷voidvisit(intr[],intn){for(inti=0;i<n;i++)printf("%4d",r[i])；printf("\n");}voidMerge(intr[],intr1[],ints,intm,intt){//合并子序列inti=s,j=m+1,k=s;printf("合并子序列r[%d]~r[%d],r[%d]~r[%d]：\n”,s,m,m+1,t);printf("r:");visit(r,10);while(i<=m&&j<=t){if(r[i]<=r[j])//取r[i]和r[j]中較小者放入r1[k]r1[k++]=r[i++];elser1[k++]=r[j++];}while(i<=m){〃若第一個子序列沒處理完，則進行收尾處理r1[k++]=r[i++];}while(j<=t){〃若第二個子序列沒處理完，則進行收尾處理r1[k++]=r[j++];}printf("r1:");visit(r1,10);}voidMergeSort(intr[],ints,intt){intm;intr1[1000]={0};if(s==t)return; 〃遞歸的邊界條件else{m=(s+t)/2; 〃劃分printf("將序列r[%d]~r[%d]劃分成r[%d]~r[%d]、r[%d]~r[%d]兩個子序列進〃求解子問題1,〃求解子問題1,歸并排序前半個子序列//求解子問題2,歸并排序后半個子序列〃合并解，合并相鄰有序子序列i++)MergeSort(r,s,m);MergeSort(r,m+1,t);Merge(r,r1,s,m,t);for(inti=s;i<=t;r[i]=r1[i]；}}intmain(){intr[10]={0};printf("請依次輸入10個整數(shù)，用空格隔開：\n");for(inti=0;i<10;i++)scanf("%d”,&r[i]);printf("排序之前的記錄：\n");visit(r,10);MergeSort(r,0,9);printf("歸并排序之后的記錄：\n");printf("r:");visit(r,10);return0;}// 快速排序 #include<stdio.h>//對含有n個數(shù)的數(shù)組進行遍歷voidvisit(intr[],intn){for(inti=0;i<n;i++)printf("%4d",r[i]);printf("\n");}intPartition(intr[],intfirst,intend){//劃分inti=first,j=end; 〃初始化待劃分區(qū)間while(i<j){while(i<j&&r[i]<=r[j])j--; 〃右側(cè)掃描if(i<j){inttemp=r[i];r[i]=r[j];r[j]=temp;//將較小記錄交換到前面i++;printf("r:");visit(r,10);}while(i<j&&r[i]<=r[j])i++; 〃左側(cè)掃描if(i<j){inttemp=r[i];r[i]=r[j];r[j]=temp;//將較大記錄交換到后面j--;printf("r:");visit(r,10);}}returni;//返回軸值記錄的位置}voidQuickSort(intr[],intfirst,intend){//快速排序intpivot;if(first<end){pivot=Partition(r,first,end);//劃分，pivot是軸值在序列中的位置printf("將序列r[%d]~r[%d]劃分成r[%d]~r[%d]、r[%d]~r[%d]兩個子序列進行求解，軸值是r[%d]=%d.\n\n",first,end,first,pivot-1<first?first:pivot-1,pivot+1,end,pivot,r[pivot]);printf("r:");visit(r,10);QuickSort(r,first,pivot-1);//求解子問題1，對左側(cè)子序列進行快速排序QuickSort(r,pivot+1,end);//求解子問題2，對右側(cè)子序列進行快速排序}}intmain(){intr[10]={0};printf("請依次輸入10個整數(shù)，用空格隔開：\n");for(inti=0;i<10;i++)scanf("%d”,&r[i]);printf("排序之前的記錄：\n");printf("r:");visit(r,10);printf("\n選取r[0]=%d作為軸值進行第一趟快速排序：\n",r[0]);QuickSort(r,0,9);printf("快速排序之后的記錄：\n");printf("r:");visit(r,10);return0;}6.實驗結(jié)論及心得通過本次實驗，我理解了歸并排序和快速排序的基本思想，兩者都是將序列分為若干子序列，通過對子序列的排序，合并子序列，最終得到一個有序序列，這體現(xiàn)了分治法“分而治之”的思想。這兩種排序方法劃分子序列的方式有所不同，歸并排序按記錄在序列中的位置進行劃分，而快速排序則按照記錄的值對序列進行劃分，這就是兩種排序方法在劃分子序列上的不同之處。成績： 成績： 實驗時間2016年4月8日8時至10時學(xué)時數(shù)21.實驗名稱實驗五漢諾塔問題的程序設(shè)計.實驗?zāi)康模?）掌握遞歸的有關(guān)概念⑵掌握漢諾塔問題的具體求解過程⑶在掌握的基礎(chǔ)上編程實現(xiàn)漢諾塔的具體實現(xiàn)過程.實驗內(nèi)容在A上有按大小排序好的n個金碟，借助B的幫助，將A上的碟子移動到C上，在移動的過程中要嚴格按照大小順序，不能將碟子放在比它小的上面，輸出結(jié)果，輸出時要求有文字說明。請編寫程序。.實驗原理或流程圖漢諾塔問題可以通過以下三個步驟實現(xiàn)：（1）將塔A上的n-1個碟子借助塔C先移到塔B上。（2）把塔A上剩下的一個碟子移到塔C上。（3）將n-1個碟子從塔B借助塔A移到塔C上。顯然，這是一個遞歸求解的過程。【下方示意圖畫不下可省略】.實驗過程或源代碼#include<stdio.h>voidHanoi(intn,charA,charB,charC){if(n==1)//將碟子從A移到C上，遞歸結(jié)束printf("%c->%c\n",A,C);else{Hanoi(n-1,A,C,B);〃將n-1個碟子從A借助C移到B上printf("%c->%c\n",A,C);〃將碟子從A移到C上Hanoi(n-1,B,A,C);〃將n-1個碟子從B借助A移到C上}}intmain(){charA,B,C;Hanoi(3,'A','B','C');printf("\n");return0;}運行結(jié)果：A->CA->BC->BA->CB->AB->CA->C.實驗結(jié)論及心得遞歸算法結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此，它為設(shè)計算法和調(diào)試程序帶來很大方便，是算法設(shè)計中的一種強有力的工具。但是，因為遞歸算法是一種自身調(diào)用自身的算法，隨著遞歸深度的增加，工作棧所需要的空間增大，遞歸調(diào)用時的輔助操作增多，因此，遞歸算法的運行效率較低。實驗時間2016年4月8日8時至10時學(xué)時數(shù)21.實驗名稱實驗六查找中減治法的程序設(shè)計2.實驗?zāi)康?1)掌握減治法的設(shè)計思想⑵掌握折半查找和二叉查找的思想及實現(xiàn)過程⑶在掌握的基礎(chǔ)上編程實現(xiàn)兩種查找方法的具體實現(xiàn)過程.實驗內(nèi)容給出一個序列及要查找的值，分別用兩種查找方法實現(xiàn)，輸出結(jié)果，輸出時要求有文字說明。請編寫程序。.實驗原理或流程圖折半查找基本思想：在有序表中，取中間記錄作為比較對象，若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。由二叉排序樹的定義，在二叉排序樹root中查找給定值k的過程是：⑴若root是空樹，則查找失??；⑵若k=根結(jié)點的值，則查找成功；⑶否則，若k＜根結(jié)點的值，則在root的左子樹上查找；⑷否則，在root的右子樹上查找；上述過程一直持續(xù)到k被找到或者待查找的子樹為空，如果待查找的子樹為空，則查找失敗。5.5.實驗過程或源代碼5.5.實驗過程或源代碼// 折半查找 #include<stdio.h>intBinSearch1(intr[],intn,intk){intlow=0,high=n-1;//設(shè)置查找區(qū)間，注意數(shù)組下標(biāo)從0開始intmid;while(low<=high){〃當(dāng)區(qū)間存在時mid=(low+high)/2;if(k<r[mid]) 〃查找在左半?yún)^(qū)間進行high=mid-1;elseif(k>r[mid])〃查找在右半?yún)^(qū)間進行l(wèi)ow=mid+1;else//查找成功，返回元素序號returnmid;}return-1;//查找失敗，返回-1}intmain(){intr[]={12,34,2,56,35,10,56,34,21,7},find=0;printf("請輸入您想查找的值：”)；scanf("%d”,&find);inti=BinSearch1(r,10,find);if(i!=-1)printf("查找成功！元素的序號是：％d\n",i+1);elseprintf("查找失??！\n");return0;}// 二叉查找樹 #include<stdio.h>typedefstructBiNode{intdata; 〃結(jié)點的值，假設(shè)查找集合的元素為整型BiNode*lchild,*rchild;〃指向左、右子樹的指針}BiNode;BiNode*insertBST(BiNode*root,intdata){if(root==NULL){〃空樹或空子樹root=newBiNode;root->data=data;root->lchild=NULL;root->rchild=NULL;returnroot;}if(data<=root->data)//將數(shù)據(jù)插入到左子樹root->lchild=insertBST(root->lchild,data);else〃將數(shù)據(jù)插入到右子樹root->rchild=insertBST(root->rchild,data);returnroot;//返回根節(jié)點}BiNode*createBST(inta[],intn){BiNode*T=NULL;for(inti=0;i<n;i++)T=insertBST(T,a[i]);returnT;}BiNode*SearchBST(BiNode*root,intk){if(root==NULL)〃二叉查找樹為空，查找失敗returnNULL;elseif(root->data==k)//查找成功returnroot;elseif(k<root->data)//查找左子樹returnSearchBST(root->lchild,k);else〃查找右子樹returnSearchBST(root->rchild,k);}intmain(){BiNode*root,*t;inta[10]={12,34,2,56,35,10,56,34,21,7},find=0;printf("->創(chuàng)建二叉排序樹：\n");root=createBST(a,10);printf("請輸入您想查找的值(整數(shù))：”)；scanf("%d”,&find);t=SearchBST(root,find);if(t!=NULL)printf("查找成功！”)；elseprintf（"查找失??！"）;return0;}6.實驗結(jié)論及心得分治法是把一個大問題劃分為若干個子問題，分別求解各個子問題，然后再把子問題的解合并得到原問題的解。減治法同樣是把一個大問題劃分成若干個子問題，但這些子問題不需要分別求解，只需求解其中一個子問題，因而也無需對子問題的解進行合并。正是因為少解了很多重復(fù)的子問題并且沒有了子問題合并的過程，應(yīng)用減治法處理問題的效率是很高的。成績： 成績： 成績： 成績： 實驗時間2016年4月11日16時至18時學(xué)時數(shù)21.實驗名稱實驗七排序中減治法的程序設(shè)計2.實驗?zāi)康模?）掌握堆的有關(guān)概念⑵掌握堆排序的基本思想和其算法的實現(xiàn)過程⑶熟練掌握篩選算法的實現(xiàn)過程⑷在掌握的基礎(chǔ)上編程實現(xiàn)堆排序的具體實現(xiàn)過程.實驗內(nèi)容給出一個記錄序列，用堆排序的方法將其進行升序排列，輸出結(jié)果，輸出時要求有文字說明。請編寫程序。.實驗原理或流程圖堆排序的基本思想是：首先將待排序的記錄序列構(gòu)造成一個堆，此時，選出了堆中所有記錄的最大者即堆頂記錄，然后將它從堆中移走（通常將堆頂記錄和堆中最后一個記錄交換），并將剩余的記錄再調(diào)整成堆，這樣又找出了次大的記錄，以此類推，直到堆中只有一個記錄為止。假設(shè)當(dāng)前要篩選結(jié)點的編號為k，堆中最后一個結(jié)點的編號為n，并且結(jié)點k的左右子樹均是堆（即r[k+1]~r[n]滿足堆的條件），則篩選算法用偽代碼可描述為：.設(shè)置i和j，分別指向當(dāng)前要篩選的結(jié)點和要篩選結(jié)點的左孩子；.若結(jié)點i已是葉子，則篩選完畢；否則，比較要篩選結(jié)點的左右孩子結(jié)點，并將j指向關(guān)鍵碼較大的結(jié)點；.將要篩選結(jié)點i的關(guān)鍵碼與結(jié)點j的關(guān)鍵碼進行比較，有以下兩種情況：如果結(jié)點i的關(guān)鍵碼大，則完全二叉樹已經(jīng)是堆；否則將r[i]與r[j]交換；令i力，轉(zhuǎn)步驟2繼續(xù)進行篩選；5.5.實驗過程或源代碼5.5.實驗過程或源代碼#include<stdio.h>voidvisit(intr[],intn){for(inti=0;i<10;i++)printf("%4d",r[i])；printf("\n");}voidSiftHeap(intr[],intk,intn){inti,j,temp；i=k；//置i為要篩的結(jié)點，j為i的左孩子j=2*i+1;while(j<n){ 〃篩選還沒有進行到葉子if(j<n-1&&r[j]<r[j+1])//比較i的左右孩子，j為較大者j++；if(r[i]>r[j])//根結(jié)點已經(jīng)大于左右孩子中的較大者break;else{temp=r[i];r[i]=r[j];r[j]=temp;//將被篩結(jié)點與結(jié)點j交換i=j；j=2*i+1；//被篩結(jié)點位于原來結(jié)點j的位置}}}voidHeapSort(intr[],intn){inti,temp;intcount=0;//記錄堆調(diào)整的次數(shù)for(i=(n-1)/2;i>=0;i--){//初始建堆，從最后一個分支結(jié)點至根結(jié)點SiftHeap(r,i,n);printf("初始建堆第％d次調(diào)整堆之后：\n",++count);printf("r[]:");visit(r,10);}printf("->建堆后：\n");printf("r[]:");visit(r,10);for(i=1;i<=n-1;i++){ //重復(fù)執(zhí)行移走堆頂及重建堆的操作temp=r[0];r[0]=r[n-i];r[n-i]=temp;SiftHeap(r,0,n-i); 〃只需調(diào)整根結(jié)點printf("第％d次重建堆之后：\n",i);printf("r[]:");visit(r,10);}}intmain(){intr[]={12,34,2,56,35,10,56,34,21,7};printf("-＞排序前的序列：\n");printf("r[]:");visit(r,10);HeapSort(r,10);printf("-＞堆排序后的序列：\n");printf("r[]:");visit(r,10);return0;}6.實驗結(jié)論及心得如何將無序序列調(diào)整為堆是堆排序算法的關(guān)鍵，篩選法調(diào)整是成功應(yīng)用減治法的例子。在堆調(diào)整的過程中，總是將根節(jié)點(即被調(diào)整結(jié)點)與左右子樹的根節(jié)點進行比較，若不滿足堆的條件，則將根節(jié)點與左右子樹中根結(jié)點的較大者交換，所以每比較一次，需要調(diào)整的完全二叉樹的問題規(guī)模就減小一半，因此，其時間性能是O(log2n)。這個自堆頂至葉子的調(diào)整過程稱為篩選。成績： 成績： 5.5.實驗過程或源代碼實驗時間2016年4月11日16時至18時學(xué)時數(shù)2.實驗名稱實驗八淘汰賽冠軍問題的程序設(shè)計.實驗?zāi)康?1)掌握減治法的設(shè)計思想⑵掌握淘汰賽冠軍問題的具體實現(xiàn)過程⑶通過這個實例進一步掌握遞歸技術(shù)的運用⑷在掌握的基礎(chǔ)上編程實現(xiàn)淘汰賽冠軍問題的具體實現(xiàn)過程.實驗內(nèi)容假設(shè)有n個選手進行競技淘汰賽，最后決出冠軍的選手，請設(shè)計競技淘汰比賽的過程，輸出結(jié)果，輸出時要求有文字說明。請編寫程序。.實驗原理或流程圖抄書上P90頁的想法#include<stdio.h>intComp(chara,charb){if(a>b)//按照字符的ASCII碼進行比較return1;elsereturn0;}charGame(charr[],intn){inti=n;while(i>1){〃比賽直到剩余1人即為冠軍=i/2;for(intj=0;j<i;j++){printf("在%c與％c的比賽中，"，r[j+i],r[j]);if(Comp(r[j+i],r[j]))〃勝者存入r[j]中r[j]=r[j+i];printf("%c勝出！\n",r[j]);}}returnr[0];}intmain(){charr[]="ABCDEFGH";charc=Game(r,8);printf("最后的冠軍是：%c",c);return0;}6.實驗結(jié)論及心得在淘汰賽冠軍問題中，通過讓選手兩兩競爭的方法，每次比賽可以去掉1/2的選手，減小了子問題的求解次數(shù)，節(jié)約了時間。將選手進行分組體現(xiàn)了分治法“分而治之”的思想，讓選手通過兩兩競爭的方法減少比賽的次數(shù)的方法體現(xiàn)了減治法的思想。實驗時間2016年4月11日16時至18時學(xué)時數(shù)2.實驗名稱實驗九數(shù)塔問題的程序設(shè)計.實驗?zāi)康?1)掌握動態(tài)規(guī)劃法的設(shè)計思想⑵掌握數(shù)塔問題的具體實現(xiàn)過程⑶熟練掌握二維數(shù)組的使用方法⑷在掌握的基礎(chǔ)上編程實現(xiàn)數(shù)塔問題的具體實現(xiàn)過程.實驗內(nèi)容給出一個數(shù)塔，從該數(shù)塔的頂層出發(fā)，在每一個節(jié)點可以選擇向左走或向右走，一直走到該數(shù)塔的最底層，找出一條路徑，使得路徑上的數(shù)值和最大，輸出最大數(shù)值及其路徑，輸出時要求有文字說明。請編寫程序。.實驗原理或流程圖想法：.求解初始子問題：底層的每個數(shù)字可以看作1層數(shù)塔，則最大數(shù)值和就是其自身；.再求解下一階段的子問題：第4層的決策是在底層決策的基礎(chǔ)上進行求解，可以看作4個2層數(shù)塔，對每個數(shù)塔進行求解；.再求解下一階段的子問題：第3層的決策是在第4層決策的基礎(chǔ)上進行求解，可以看作3個2層的數(shù)塔，對每個數(shù)塔進行求解；.以此類推，直到最后一個階段：第1層的決策結(jié)果就是數(shù)塔問題的整體最優(yōu)解?！緦懖幌戮退懔恕克惴ǎ?初始化數(shù)組maxAdd的最后一行為數(shù)塔的底層數(shù)據(jù)：for(j=0；j<n；j++)maxAdd[n-1][j]=d[n-1][j]；.從第n-1層開始直到第1層對下三角元素maxAdd[i][j]執(zhí)行下述操作：maxAdd[i][j]=d[i][j]+max{maxAdd[i+1][j],maxAdd[i+1][j+1]}；如果選擇下標(biāo)j的元素，則path[i][j]=j，否則path[i][j]=j+1；.輸出最大數(shù)值和maxAdd[0][0]；.根據(jù)path數(shù)組確定每一層決策的列下標(biāo)，輸出路徑信息；#include<stdio.h>#definen5voidprintArray(intmaxAdd[n][n],intpath[n][n]){printf("\nmaxAdd[%d][%d]:\n",n,n);for(inti=0;i<n;i++){for(intj=0;j<=i；j++){printf("%4d",maxAdd[i][j]);}printf("\n");}printf("\npath[%d][%d]:\n",n,n);for(inti=0;i<n;i++){for(intj=0；j<=i；j++){printf("%4d”,path[i][j]);}printf("\n");}}//求解數(shù)塔問題，數(shù)塔存儲在數(shù)組//求解數(shù)塔問題，數(shù)塔存儲在數(shù)組d[n][n]中={0}; //初始化={0}; //初始化〃初始化底層決策結(jié)果〃進行第i層的決策〃填寫addMax[i][j]，只填寫下三角for(j=0;j<n;j++)maxAdd[n-1][j]=d[n-1][j];printf("初始化操作后：\n");printArray(maxAdd,path);for(i=n-2;i>=0;i--){printf("第％d層決策：\n”,i+1);for(j=0;j<=i;j++){if(maxAdd[i+1][j]>maxAdd[i+1][j+1]){maxAdd[i][j]=d[i][j]+maxAdd[i+1][j];path[i][j]=j; 〃本次決策選擇下標(biāo)j的元素}else{maxAdd[i][j]=d[i][j]+maxAdd[i+1][j+1];path[i][j]=j+1; 〃本次決策選擇下標(biāo)j+1的元素}printArray(maxAdd,path);}}printf（"路徑為：％d",d[0][0]）; 〃輸出最頂層數(shù)字j=path[0][0]; 〃頂層決策是選擇下一層列下標(biāo)為path[0][0]的元素for(i=1;i<n;i++){printf("-->%d",d[i][j]);j=path[i][j]； //本層決策是選擇下一層列下標(biāo)為path[i][j]的元素}returnmaxAdd[0][0];〃返回最大數(shù)值和，即最終的決策結(jié)果}intmain(){intd[n][n]={{8},{12,15},{3,9,6},{8,10,5,12},{16,4,18,10,9}};printf("數(shù)塔：\n");printf("d[%d][%d]:\n",n,n);for(inti=0;i<n;i++){for(intj=0;j<=i;j++){printf("%4d",d[i][j]);}printf("\n");}intmax=DataTorwer(d);printf("\n最大數(shù)值和為：%d",max);return0;}6.實驗結(jié)論及心得動態(tài)規(guī)劃法將待求解問題分解成若干個相互重疊的子問題，每個子問題對應(yīng)決策過程的一個階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計算。成績： 成績： 成績： 成績： 實驗時間2016年4月14日16時至18時學(xué)時數(shù)2.實驗名稱實驗十多源點最短路徑問題的程序設(shè)計.實驗?zāi)康?1)掌握動態(tài)規(guī)劃法的設(shè)計思想⑵掌握多源點最短路徑問題的具體實現(xiàn)過程⑶通過這個實例進一步掌握動態(tài)規(guī)劃法的運用⑷在掌握的基礎(chǔ)上編程實現(xiàn)多源點最短路徑問題的具體實現(xiàn)過程.實驗內(nèi)容給定帶權(quán)有向圖G=(V，E)，對任意頂點匚和j中j)，求出頂點匕到頂點匕的最短路徑長度，輸出結(jié)果，輸出時要求有文字說明。請編寫程序。.實驗原理或流程圖抄書上106頁的想法，從設(shè)d(vi,vj,V)...一直抄到這就是著名的Floyd算法。5.5.實驗過程或源代碼5.5.實驗過程或源代碼#include<stdio.h>constintMAX=100;constintn=3；//假設(shè)圖中最多頂點個數(shù)voidprintDist(intdist[n][n]){for(inti=0;i<n;i++){for(intj=0;j<n；j++){printf("%4d",dist[i][j]);}printf("\n");}}voidFloyd(intarc[n][n],intdist[n][n]){inti,j,k;for(i=0;i<n;i++) //初始化矩陣distfor(j=0;j<n;j++)dist[i][j]=arc[i][j];printf("->初始化后的矩陣dist:\n");printDist(dist);printf("求解最短路徑，只在矩陣中的值有調(diào)整時打印矩陣：\n");for(k=0;k<n;k++)//進行n次迭代for(i=0;i<n;i++)for(j=0;j<n;j++){if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];printDist(dist);}printf("i[%d]經(jīng)過k[%d]到達j[%d]的最短路徑為%d\n",i,k,j,dist[i][j]);}}intmain(){intarc[n][n]={{0,4,11},{6,0,2},{3,MAX,0}};intdist[n][n];Floyd(arc,dist);printf("求解完成后的dist矩陣：\n");printDist(dist);return0;}成績： 成績： 成績： 成績： 6.實驗結(jié)論及心得我理解了用動態(tài)規(guī)劃法求解的問題具有特征：①能夠分解為相互重疊的若干子問題；②滿足最優(yōu)性原理（也稱最優(yōu)子結(jié)構(gòu)性質(zhì)）:該問題的最優(yōu)解中也包含著其子問題的最優(yōu)解實驗時間2016年4月14日16時至18時學(xué)時數(shù)2.實驗名稱實驗十一貪心算法解決SP問題程序設(shè)計.實驗?zāi)康?1)掌握貪心法的設(shè)計思想(2)掌握TSP問題的具體實現(xiàn)過程(3)熟練掌握二維數(shù)組的使用方法(4)在掌握的基礎(chǔ)上編程實現(xiàn)TSP問題的具體實現(xiàn)過程.實驗內(nèi)容給出n個城市及任意兩城市間的距離，要求旅行家在旅行這n個城市時，各個城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，使得所走的路徑最短。輸出結(jié)果，輸出時要求有文字說明。請編寫程序。.實驗原理或流程圖最近鄰點策略：從任意城市出發(fā)，每次在沒有到過的城市中選擇最近的一個，直到經(jīng)過了所有的城市，最后回到出發(fā)城市。設(shè)圖G有n個頂點，邊上的代價存儲在二維數(shù)組w[n][n]中，集合V存儲圖的頂點，集合P存儲經(jīng)過的邊，最近鄰點策略求解TSP問題的算法如下：P={}；.V=V-{u0};u=u0; //從頂點u0出發(fā).循環(huán)直到集合P中包含n-1條邊查找與頂點u鄰接的最小代價邊(u,v)并且v屬于集合V;P=P+{(u,v)};V=V-{v};u=v; 〃從頂點v出發(fā)繼續(xù)求解5.5.實驗過程或源代碼#include<stdio.h>constintn=5;constintmax=100;intTSP1(intarc[n][n],intw){intedgeCount=0,TSPLength=intmin,u,v;intflag[n]={0};u=w;flag[w]=1;while(edgeCount<n-1){min=100;for(intj=0;j<n;j++)0#include<stdio.h>constintn=5;constintmax=100;intTSP1(intarc[n][n],intw){intedgeCount=0,TSPLength=intmin,u,v;intflag[n]={0};u=w;flag[w]=1;while(edgeCount<n-1){min=100;for(intj=0;j<n;j++)0；〃頂點均未加入哈密頓回路〃循環(huán)直到邊數(shù)等于n-1〃求arc[u]中的最小值if((flag[j]==0)&&(arc[u][j]!=0)&&(arc[u][j]<min)){v=j;min=arc[u][j];}//將頂點加入哈密頓回路〃輸出經(jīng)過的路徑//將頂點加入哈密頓回路〃輸出經(jīng)過的路徑〃輸出最后的回邊}}int}intmain(){intarc[n][n]={{max,3,3,2,6},{3,max,7,3,2},{3,7,max,2,5},{2,3,2,max,3},{6,2,5,3,max}};printf("最短路徑是：”)；intminDist=TSP1(arc,0);printf("最短哈密頓回路的長度是：％d\n",minDist);return0;6.實驗結(jié)論及心得貪心法在解決問題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。而動態(tài)規(guī)劃法在進行下一步?jīng)Q策時一定是基于上一步得到的最優(yōu)解進行的，而且能動態(tài)的調(diào)整自己做出的選擇，所以動態(tài)規(guī)劃法得到的一定是整體最優(yōu)解。實驗一BF算法運行結(jié)果截圖S 口:\課件X營業(yè)課薄去京郵谷實所母匹配耳鼻法.醐* -nU請輸入主母5（不超過LU。個字符）:ababccabc^bab請輸入「串Tf不超過1。0個李南：a民配卜隊主串的第。個位置開始與模式串進行匹配：（只輸出回溯儲息）?從主事的第1個位置開始與模式串進行匹配：（只輸出叵潮儲息）從主串的第2個位置開始與模式申進行匹配：C只輸出叵溯信息）由「主串卜標(biāo)i為2的字符a和模式串下一標(biāo)j為2的字符c失配所以i和j分別問潮到L0重新開始匹配》從主串的第I個位置開始與模式串進行匹配；（只輸出叵潮信息）由于主串下標(biāo)i為1的字符b和模式串下標(biāo)j為0的字符a失配所以i和j分別回溯到2,0重新開始匹配》從主審的第2個位置開始與模式串進行匹配：（只輸出叵溯解息）從卞□的第3個位置開始與模式申進行匹配：（只輸出叵溯信息））■從主串的第4個位置開始與模式串進行匹配：（只輸出回溯信息）從主串的第5個位置開始與模式串進行匹配：（只輸出回溯信息）忸于主串下標(biāo)i為5的字符c和模式串下標(biāo)j為3的字符a失配所以i和」分別回溯到3,0重新開始匹配》從主串的第3個位置開始與模式串進行匹配：（只輸出回溯信息）由于主審F標(biāo)i為3的字符匕和模式串下標(biāo)j為。的字符a失配所以i和j分別回溯到4,0重新開始匹配）■從主串的第4個位置開始與模式串進行匹配：（只輸出回溯信息）由于主串下標(biāo)i為4的字符c和模式串下標(biāo)j為0的字符h失配所以i和j分別回溯到5,0重新開始匹配》從主串的第5個位置開始與模式串進行匹配：（只輸出叵溯信息）由于主串f標(biāo)i為5的字符「和模式串下標(biāo)j為0的字符a失配所以i和j分別問溯到6,0重新開始匹配＞從卞□的第6個位置開始與模式申進行匹配：（只輸出叵溯信息）＞從主審的第『個位置開始與模式串進行匹配：（只輸出回溯信息）從主串的第H個位置開始與模式串進行匹配：（只輸出回溯信息）》從主；；的第9個位置開始與模式串進行匹配；（只輸出叵溯信息）-＞從主串的第L。個位置開始與模式串進行匹配：（只輸出回溯信息）模式匹配成功.子串a(chǎn)tiuae在主串a(chǎn)b日氏izabcaftiBh中首次匹配的位置是7IVoc^ssexiTedv\t}ireturnvahie0Pressanykeytocontitiue-.搜狗拼音輸入法全：實驗二選擇排序、起泡排序運行結(jié)果截圖*■ 課件曾業(yè)球窗卻買弗吉供琬麗［改）供臉之誰薛排序就電 一口請依次輸入1。個整數(shù)，用空格隔開：123-125635103634217排序之前的記錄：12 34 2 56 35 10 56 34 21 7進行選擇排序；（每趟排序后的結(jié)果如下所示）2 34 12 56 35 10 56 34 21 72 7 12 56 33 10 36 34 21 342 7 10 56 資 12 56 34 21 342 7 10 12 35 56 56 34 21 3-12 7 10 12 2〕 56 56 34 35 312 7 10 12 21 34 56 56 35 342 7 10 12 21 34 34 56 35 562 7 10 12 21 34 34 35 36 562 7 10 12 21 34 34 35 56 56在本次排序中共比較了必次，移動了24次。排序之后的記錄：2 7 10 12 2〕 34 34 35 55H6AProcessexited霄ithreturnvalue0Pressanykeytocontinue...搜狗拼音輸入法全

D：\課件1營業(yè)深二廊去貨能吉慶笈源碼t改：'供蕤色起泯排序敝電請依次輸入再不整數(shù);…用空格隔開:12342563510563-1217排序之前的記錄；12進行修34f泡邦丁56 35I.Q5634（每趟排序后的結(jié)果如下所示）2171223435 10 56 34211而2123410 35 34 21 736562121.034 34 21 7 3556562101.234 21 7 34 355656210122] 734343556562101.27 21 34 34 355656210712 21 34 3435565621013 31冽34 35逋56271.012 21 34 34 355656本次排序中的比較次數(shù)為公，移動次數(shù)為69匚排序之后的記錄;2T11012 21 34 34 355556Processexitedwithreturnvalue0Pressanykey1tocontinue.■■.搜狗拼音輸入法全：1實驗三數(shù)字旋轉(zhuǎn)方陣運行結(jié)果截圖-J| 理件后業(yè)課法■侯蛤瓶若供廓S碼（改）俵蛤詈饋字旋轉(zhuǎn)方眸小麻輸入方陣的大小:于開始填充之前的數(shù)字旋轉(zhuǎn)方陣；TOC\o"1-5"\h\z0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0填充過程：16 15 14 130 0 0 120 0 0 110 0 0 106 7 8 91 16 15 14 133 17 24 23 1218 0 22 1119 20 21 106 7 8 967896111-11267896111-11234524 23 1225 22 1120 21 107 8 9最終填充完成的結(jié)果是：1 16 15 14 132 17 24 23 123 18 25 22 114 1920 21 10□ 6 7 8 9IVochssexiredwithreturnvalue0Pressanykeytocontitiue....搜狗拼音輸入法全：實驗四歸并排序、快速排序運行結(jié)果截圖D：\理用專業(yè)課而供輯報告供蛙拆（改）供我林口并排序.能電用空格隔開;34217請依次輸入1。用空格隔開;342171.234256351056123d25635 10將序列r[0]7r.9]123d25635 10將序列r[0]7r.9]劃分成r[0]>|4將序列r[0]0r研面分成1-[0Pr[2]將序列r他0r[2]劃分成r[o]Fi]耨序列r0T1閨分成rOPrED]合并予序列rQTrM.MirHU：排序之前的記錄:rrrr]■: 12 34 2 56 35rl： 12 3-1 0 0 0合并于序列*Orr[l]白[2rr[2]:r: 12 34 2 西 斯11: 2 12 34 0 05653213421 7兩個子序列進行求解:

兩個子序列進行求解!

兩個子序列進行求解:

兩個子序列進行求解:105634210000105634210000770耨序列r[3rr[4]劃分成r[3]>[3]、r[4]>[4]兩個子序列進行求解:合并「序列r[3|，[3：.r[4]i[4：：j': 211: 012 3456 35:后56j': 211: 012 3456 35:后56合并子序列r-0「r[2]”[3]、"4jr: 2 12 34 35 5611: 2 12 34 35 56耨序列r[5rr[9]劃分成r[5]\[7]，蔣序利/5『1彳7語]辦成『5「t、|6、1056342100001056342100007070幻、[9]兩個子序列進行求解:

了廣式7]兩個子序列進行求解:將序列r[5]%[6]劃分成r[5]>[5]、r[6「r[6]兩個子序列進行求解;合并于序列于5]7[5],「[€]）[6卜Ir： 2 12 34 35 又 10 56 34 2】rl: 0 0 0 0 0 10 56 0 0搜狗拼音輸入法全：,i'⑺’[[7]：?：\課件1專業(yè)深、廓云供復(fù)性告1茶發(fā)源德t改）供蝌可歸并排序敬電合并子序列r.ETr[6],r[Tr7[『|10563421h7r: 2 12 3435 5611: 0 0 0 0 0 10需序列t⑻”r[9]劃分成或明\[通I合并子序列tlXTr⑻|,式9「『[叼’r: 2 12 34 35 56 10T1: 0 0 0 0 0 0合并子序列r[5]"r[7],r[8]"r[9]tr: 2 12 34 35 56 1011: 0 0 0 0 0 7含并?^r[0]\[4],rE5]>[9Lr: 2 12 34 35 56 7rl: 2 7 10 12 21 34歸并排序之后的記錄：r: 2 7 10 12 21 3434 56 0 019廠顯9]兩個子序列進行求解：34 56 21 70 0 7 2134 36 7 2110 21 31 5610 21 34 5634 35 而 5634 35 56 56ProcessexitedwithreturnvaJupIVhssanykeytocontinue....01搜狗拼音輸入法全：

?■ 口：'課件"專業(yè)海郢云供如吉供脂源屑t改）快蝌'快固非序?加油一口，請依次輸入10個整數(shù)，用空格隔開：A123-125635105634217排序之前的記錄：r： 12 34 2 56 孤 10 56 34 21 7選取r[0]=12作為軸值進行第一趟快速排序：r: 7 34 2 56 35 10 56 34 21 12r: 7 12 2 56 35 10 56 34 21 34r; 7 10 2 56 35 12 56 34 21 34]■: 7 10 2 12 35 o6 56 34 21 31將序列r[Qrr[9]劃分成『[口:"2]、陽兩個子序列進行求解，軸值是廣匯=21： 7 10 2 12 35 而 56 34 21 34r: 2 W 1 12 35 56 56 34 21 34r: 2 7 10 12 35 56 56 34 21 34產(chǎn)序列r[0]、r⑵劃分弧H2]>⑵兩個子序列進行求解,軸值是rT=7.t: 2 7 10 12 孤 56 56 34 21 34r： 2 7 10 12 34 而 56 34 21 33r; 2 7 10 12 34 35 56 34 21 三6r: 2 7 10 12 34 21 56 34 35 56r: 2 7 10 12 34 21 35 34 56 56. 2 7 10 12 34 21 34 35 56 56將專列r⑷，網(wǎng)劃分成"4]\的，r[8]>[9]兩個子序列進行求解，軸值是廣力=；原1： 2 7 10 12 34 21 34 36 56 56r: 2 7 10 12 21 34 34 35 56 56色序列r⑷F6]劃分成r[4]F小r[6「r[6]兩個子序列進行求相軸值是r.3,=34.「： 2 7 10 12 21 34 34 35 56 56將浮列r血?]劃分成r⑻入⑻;胤兩個子序列進行求解，軸值是1<8]=鋪>1： 2 7 10 12 21 34 34 35 56 56快速排序之后的記錄，r: 2 7 10 12 21 34 34 35 56 56PmcRSSeKiredvithrpturnvaluf；0Pi'ussanykeytoeontitiue...搜狗拼音輸入法全：1實驗五漢諾塔問題運行結(jié)果截圖0 口:用件0u理xw法回a報苦兇踞似或)兇as煙硝睡， -口^■廠>Ck->bC->Bk->cp->AB->Ck->cProcessexile(iwithr(?turnvalue0Prpsf?anykeytocontinue...實驗六折半查找和二叉查找樹運行結(jié)果截圖叱 口:\課閘營業(yè)密施云燃蜘者供艱源碼（改）供恥怖半甘找.歌電請輸入您想查找的值：L2查找成功！元素的序號是：LProcessexiTedwithrpturnvalue0Prussanykeytocontinue....「 口：\課件7學(xué)業(yè)陰廓去曲用吉區(qū)驗源碼t及）貨的怖半宜找.由健請輸入您想查找的值：L9查找失?。rocessexiledwithreturnvalue0IVrssanykeyto<-ontitme...叱 件向止課xm法俵蛉弘含供密用碼C改）蟲蛇6:旦旦戰(zhàn)的.瞅9F＞創(chuàng)建二叉排序樹：話輸入您想查找的值（整數(shù)＞：12查找成功！Processexitedwitlireturnvalue0Pressanykeytocontinue...D-\封件\專業(yè)課/法讖驗報若匈蹣碼（改）道3就二出宜戰(zhàn)的后磔建二叉排序稱請輸入您想查找的值（整數(shù)）"9有找失??！Processexitedwithreturnvalue0Pressanykeytoeontinue...實驗七堆排序運行結(jié)果截圖r|\12 34 2j6初培建堆第1次調(diào)整堆之后]351036217r「：1.2 34 2 5635105634217初始建堆第2次調(diào)整堆之后:if：12 34 2 5635105634217初蛆建堆第3次調(diào)整堆之后：r|;12 34 56 563510234217初始建堆第4次調(diào)整堆之后;r「：1.2 56 56 3435102笈217初整建堆第15次調(diào)整堆之后士1T：5635前341210234217-》建推后：t|:56 36 56 341210234217第1次重建堆之后;]<':56 35 10 341272342156第2次重建堆之后：r|'：35 34 10 341272215656第3次重建堆之后，]■[';34 ：\4 10 21127235565