計(jì)算機(jī)軟件應(yīng)用結(jié)課作業(yè)

《軟件技術(shù)基礎(chǔ)》結(jié)課大作業(yè)

姓名：院振召

學(xué)號(hào)：120611335_______

日期：2014年6月20日________

2014軟件技術(shù)基礎(chǔ)期末作業(yè)

說(shuō)明與要求:

1.開(kāi)放式考試不僅考察知識(shí)，同時(shí)考察學(xué)生查閱文獻(xiàn)的能力；學(xué)生可以使用Google,百

度等搜索引擎，圖書(shū)館數(shù)字資源，如同方CNKI（中國(guó)學(xué)術(shù)期刊全文數(shù)據(jù)庫(kù)）查閱資料，尋

找答案和解題思路；

2.可以使用各種工具幫助自己解題，可以相互討論，但是不允許拷貝、復(fù)制、剽竊他人

結(jié)果。如果發(fā)現(xiàn)雷同，按雷同人數(shù)，每次雷同從成績(jī)中扣除10分。因不存在完美雷同

標(biāo)準(zhǔn)，因此將根據(jù)批改教師的個(gè)人識(shí)別，進(jìn)行雷同確認(rèn)，因此為避免雷同，請(qǐng)自己設(shè)

計(jì)代碼或解題；

3.每個(gè)編程問(wèn)題都要首先說(shuō)明思路，然后給出代碼；程序以及求解方法描述的編輯應(yīng)該

美觀；程序代碼應(yīng)該有層次縮進(jìn)，以便閱讀；

4.每個(gè)編程問(wèn)題的C/C++代碼的每一行必須有清晰的注釋，說(shuō)明改行中變量和語(yǔ)句的作

用，如果注釋和C/C++語(yǔ)句不符，則視為剽竊。

5.根據(jù)自己的情況，采用C或C++語(yǔ)言中德一種作為編程語(yǔ)言，不能使用兩種以上的語(yǔ)言；

6.編輯排版時(shí)，采用漢字五號(hào)宋體，英語(yǔ)和代碼采用10號(hào)或五號(hào)TimesNewRoman字體，

打印時(shí)采用雙面打印，連同填寫(xiě)好的封面一起裝訂，在最后一堂課時(shí)上交；禁止使用

更大號(hào)字；

2014軟件技術(shù)基礎(chǔ)期末作業(yè)

1.利用減半遞推技術(shù)，寫(xiě)出求長(zhǎng)度為n的數(shù)組中最大元素的遞歸算法（10分）。

2.編寫(xiě)用回溯法求解n皇后的算法（10分）。

3.給定n個(gè)城市間的距離，求從一個(gè)城市。出發(fā)經(jīng)過(guò)其他城市一次且一次的一條最短路

徑（15分）。

4.將單鏈表看做二叉樹(shù)，編寫(xiě)遞歸程序打印單鏈表（10分）。

5.編寫(xiě)二叉樹(shù)的層次遍歷算法（15分）。

6.自底向上實(shí)現(xiàn)歸并排序算法（10分）。

7.實(shí)現(xiàn)堆排序算法（15分）。

8.實(shí)現(xiàn)迪杰斯特拉最短路徑算法（15分）

T、利用減半遞推技術(shù)，寫(xiě)出求長(zhǎng)度為n的數(shù)組中最大元素的遞歸算法

解擇說(shuō)明：

解決實(shí)際問(wèn)題的復(fù)雜程度往往與問(wèn)題的規(guī)模有著密切的關(guān)系，因此，降低問(wèn)題的規(guī)模是算

法設(shè)計(jì)的關(guān)鍵，而減半遞推技術(shù)是降低問(wèn)題國(guó)模的一種有效方法。所謂的“減半”，是指將

問(wèn)題慨?dāng)X泮，而問(wèn)題的頡不變。所I醐“遞1隹”球重復(fù)“減半”僦程。

算法如下：

#include<iostream>

usingnamespacestd;

intmax(inta||,intright)

(

intmid=(left+right)?1;

intx,y;

if(left==right-1jreturna|left|;

x=max(a,leftmid);

y=max(a,mid,right);

returnx>y?x:y;

}

voidmain()

(

intn,i;

inta|1000|;

cin>>n;

fbr(i=O;i<n;i++)cin>>a|i|;

cout<<max(a,0,n)<<endl:

}

2、編寫(xiě)用回溯法求解n皇后的算法

解釋說(shuō)明：

n個(gè)皇后在n元棋盤上的布局有n的n次方種，用回溯發(fā)求解問(wèn)題。

假設(shè)定義一個(gè)長(zhǎng)度為n的一維數(shù)組q,其中的每一個(gè)元素q[i](i=l,2,...,n)隨時(shí)記錄

第n行上的皇后所在的序列號(hào)。

初始時(shí)，先將各皇后放在各行的第一列。即數(shù)組q的初值為=

而它們?cè)谕涣猩系臈l件為q[i]=q[j]

算法如下：

#include<iostream>

#include<cmath>

usingnamespacestd;

classNQueen

(

private:

intnumOfQueen;//thenumberofqueens

in(numOfanswer;//thenumberofanswers

int*queen;

public:

NQueen();

NQueen(intni);

~NQueen();

boolplace(intk);

voidbacktrack(intt);

voidshowQueen();

NQueen::NQueen()

{

numOfQueen=0;

numOfanswer=0;

queen=newint[1];

}

NQueen::NQucen(intm)

{

numOfQueen=m;

numOfanswer=0;

queen=newint[m+l];

for(inti=0;i<=m;i++)

{

queen[i]=0;

NQuccn::-NQuccn()

(

delete|Iquccn;

cout?"queensaredeleted!"?endl;

1

voidNQueen二showQueen。

for(inti=1;i<=numOfQueen;i++)

C0Ut?queen[i]<v"

cout<<endl;

boolNQueen::place(intk)//theconstraintfunction

(

for(intj=l;j<k;j++)

if((fabs(k-j)==fabs(queen[j|-queen|k]))||(queen[j|==queen|k]))

returnfalse;

returntrue;

voidNQueen::backtrack(intt)

(

inti=0;

if(t>numOfQueen)

(

numOfanswer++;

showQueen();

}

else

(

fbr(i=1;i<=numOfQueen;i++)

(

queen[t]=i;

if(place(t))

backtrack(t+l);

}

}

}

voidbacktrack(intt)

{

if(t>n)

output(x);

else

(

for(i=f(n,t);i<=g(n,t);i++)

(

x[t]=h(i);

if(constraint(t)&&bound(t))

backtrack(t+l);

voiditerativeBack()

{

intt=l;

while(t>0)

{

if(f(n,t)<g(n,t))

for(i=f(n,t);i<=g(n,t);i++)

x[t]=h(i);

if(constraint(t)&&bound(t)i

(

if(solution(t))

output(x);

elset++;

|

elset—;

voidbacktrack(intt)

if(t>n)

output(x);

else

for(i=0;i<=l;i++)

{

x[t]=i；

if(constraint(t)&&bound(t)j

backtrack(t+l);

voidbacktrackfintt)

{

if(t>n)

output(x);

else

{

for(i=t;i<=n;i++)

swap(x[t],x[i]);

if(cuiislraiiil(l)&&bound(t)i

backtrack(t+l);

swap(x[t],x[i]);

intmain()

{

intml=4,m2=8;

NQueenQl(ml);

cout?"thenumberofqueensare:"?ml?endl;

Ql.backtrack(l);

NQueen*Q2=newNQueen(m2);

cout?"thenumberofqueensare:"?m2?endl;

Q2->backtrack(l);

return0;

)

3、給定n個(gè)城市間的距離，求從一個(gè)城市。出發(fā)經(jīng)過(guò)其他城市一次且一次的一條最短路徑(15

分)。

解釋說(shuō)明：

從理論上講，可以計(jì)算出最短路徑，但要借助計(jì)算機(jī)，計(jì)算量較大，人力難以勝任。方法

如下：

假定出發(fā)城市編號(hào)為。，其他城市編號(hào)為1?nT,將1?『1號(hào)城市排列，按排列順序計(jì)

算每種排列從排頭城市到徘尾城市的距離和X,實(shí)際距離D=X+O和排頭城市的距離+0和排尾

城市的距離，這樣共得到A<nT>=(nT)!個(gè)距禽D,從中選出最小的一個(gè)即可。編一段簡(jiǎn)單

程序，把n個(gè)城市間的距離輸入進(jìn)去，就能輕易算出最短距離

算法如下：

#include<stdio.h>

intmain()

{

intG[100][100]={0};〃一個(gè)記錄圖的鄰接矩陣

inta,b,w;〃輸入一共有7條邊，5個(gè)點(diǎn)

inti,j,k;

for(i=l;i<=5;i++)

for(j=l;j<=5;j++)

G[i][j]=9999999;

for(i=l;i<=7;i++)

scanf("%d%d%d",&a,&b,&w);//輸入每條邊的信息，a和b代表這條邊的兩

個(gè)頂點(diǎn)w代表兩個(gè)點(diǎn)的距離

G[a][b]=w;

G|b][a]=w;

}

for(k=l;k<=5;k++)

fbr(i=1;i<=5;i++)

for(j=l;j<=5;j++)

if(G[i][j]>G[i][k]+G[k][j])

G恥]=G[i][k]+G|kJ[j]；

printf("％d”,G⑴[4]);//輸出兩點(diǎn)之間的最短路，這里的兩個(gè)點(diǎn)是3和

5

return0;

代表i到j(luò)的距離，甲，乙，內(nèi)，丁，戊用1，2,3,4,5代替

4、將單鏈表看做二叉樹(shù)，編寫(xiě)遞歸程序打印單鏈表

解釋說(shuō)明：

建立和遍歷二叉樹(shù)的程序都比較簡(jiǎn)單，關(guān)鍵在于按要求打印二義樹(shù)。起初一直找不到合適

的方法按題目要求打印二叉樹(shù)，在和同學(xué)討論了很久之后終于有了思路。打印的格式中，最上

層的節(jié)點(diǎn)是右子樹(shù)層次最高的，于是就可以用遞歸調(diào)用的方式實(shí)現(xiàn)。遞歸次數(shù)最高的就是輸出

最頂置的節(jié)點(diǎn)。在調(diào)試程序的時(shí)候也出現(xiàn)了問(wèn)題，起初沒(méi)有在意輸入方式對(duì)程序運(yùn)行結(jié)果的影響,

導(dǎo)致程序無(wú)法運(yùn)行，在檢查了很久之后終于找到了問(wèn)題的所在，對(duì)輸入進(jìn)行了改正，得到了正確

的結(jié)果。

在建立二叉樹(shù)時(shí)，輸入的格式一定要正確，沒(méi)有孩子的要用空格表示，在測(cè)試用例中，

F沒(méi)有孩子，要用兩個(gè)空格表示，如果輸入“AB#D##CE#F”則沒(méi)有輸出結(jié)果。

算法如下：

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

#include<time.h>

#defineNUM_NODE12

#defineMOST_DEPTH10

typedefstruct

BiTree{intdata;

BiTree*lchild;

BiTree*rchild;

JBiTree;

typedefstruct

Answear{int

DegreeO;

intDegree1;

intDegree2;

intDepth;

}Answear;

BiTree*CreateTree(intn)

BiTree*t;

if(n<=011n>NUM_NODE)returnNULL;

if(!(t=(BiTree*)malloc(sizeof(BiTree))))

returnNULL;

t->data=n;

printf("%d",t->data);

t->lchild=CreateTree(2*n);

t->rchild=CreateTree(2*n+1);

returnt;

)

voidFreeTree(BiTree*t)

{

if(t)

{

if(t->lchild)

FreeTree(t->lchild);

if(t->rchild)

FreeTree(t->rchild);

printf("%d",t->data);

free(t);

|

}

〃中序遍歷

voidInOrder(BiTree*t)

{

BiTree**stack,**top,*p;

〃創(chuàng)建堆棧

if(!(stack=(BiTree**)malloc(NUM_NODE*sizeof(BiTree))))

{

printf("InOrderfailedformemery\n");

return;

}

〃初始化堆棧

top=stack;

p=t;

while(p11top>stack)//p不為NULL,堆棧不空

if(P)

*top++=p;//p入堆棧

p=p->lchild;

else

p=*—top;//p出棧

if(p)printf("%dM,p->data);

p=p->rchild;

〃前序遍歷

voidPreOrder(BiTree*t)

{

BiTree**stack,**top,*p;

if(!(stack=(BiTree**)malloc(NUM_NODE*sizeof(BiTree))))

(

printff'InOrderfailedformemery\n");

return;

}

top=stack;

P=t;

while(p11top>stack)

if(P)

{

*top++=p;

if(p)printf("%d",p->data);

p=p->lchild;

}

else

{

p=*—top;

p=p->rchild;

〃后序遍歷

voidPostOrder(BiTree*t)

BiTree**stack,**top,*p,*p_old,*p_new;

intFlag;

if(!(stack=(BiTree**)malloc(NUM_NODE*sizeof(BiTree))))

{

printf("InOrderfailedformemery\rT);

return;

top=stack;

Flag=0;

*top++=t;

while(top>stack)

(

P=W-1)；

if(p->lchild&&!Flag)

*top++=p->lchild;

else

(

if(p->rchild)

(

*top++=p->rchild;

Flag=0;

)

else

(

p_old=*-top;

printf(H%d",p_old->data);

while(top>stack)

(

p_new=*(top-1);

if(p_old==p_new->lchild)

(

Flag=1;

break;

)

else

(

p_new=*-top;

printf("%d",p_new->data);

p_old=p_new;

Flag=0;

)

)

)

)

)

)

〃中序遍歷求結(jié)點(diǎn)的深度和度為0,1,2的結(jié)點(diǎn)數(shù)，結(jié)果保存在pAns指的。。

voidInOrderDOfBiTree*t,Answear*pAns)

〃遍歷用的數(shù)據(jù)

BiTree**stack,**top,*p;

〃求深度的數(shù)據(jù)

intcurDeep,MostDeep;

〃創(chuàng)建堆棧

if(!(stack=(BiTree**)malloc(NUM_NODE*sizeof(BiTree))))

(

printf("InOrderfailedformemery\n");

return;

}

〃初始化堆棧

top=stack;

P=t;

〃初始化數(shù)據(jù)

curDeep=MostDeep=0;

pAns->DegreeO=pAns->Degreel=pAns->Degree2=0;

〃遍歷循環(huán)

while(p11top>stack；//p不為NULL.堆棧不空

if(P)

{

*top++=p;//p入堆棧

p=p->lchild;

curDeep++;

if(MostDeep<curDeep)MostDeep=curDeep;〃保存最深度

}

else

{

p=*--top;〃p出棧

curDeep";

//if(p)printf("%d",p->data);//Visit結(jié)點(diǎn)

〃計(jì)算個(gè)結(jié)點(diǎn)的度

if(p->lchild&&p->rchild)pAns->Degree2++;

elseif(p->lchild11p->rchild)pAns->Degree1++;

elsepAns->DegreeO++;

p=p->rchild;

}

〃得到深度

pAns->Depth=MostDeep;

return;

〃前序遞歸求廣度

voidPre(BiTree*T,int*woed,intdepth)

woed[depth]++;

if(T->lchild)Pre(T->lchild,woed,depth+1);

if(T->rchild)Pre(T->rchild,woed,depth+1);

)

〃求廣度的程序，返回值為廣度

intGetTreeWidth(BiTree*root)

{

inti,WidthOfEachDepth|MOST_DEPTH|={0};

Pre(root,WidthOfEachDepth,0);

for(i=l;i<MOST_DEPTH;i++)

if(WidthOfEachDepth|0|<WidthOfEachDepth|i|)

WidthOfEachDepth|0]=WidthOfEachDepth[i];

returnWidthOfEachDepth[0];

)

intmain()

{

BiTree*root;

Answearans;

printf("CreateTree\n")；

root=CreateTree(l);

printf("\nInOrder\n")；

InOrder(root);

printf("\nPreOrder\n");

PreOrder(root);

printf("\nPostOrder\n");

PostOrder(root);

InOrderDO(root,&ans);

printf("\nTheMostDep:his:%d\n",ans.Depth);

printff'TheMostWidthis:%d\n",GetTreeWidth(root));

printf("EachDegree(0,l,2)is:(%d,%d,%d)\n",

ans.DegreeO,ans.Degree1,ans.Degree2);

printf("\nFreeTree\n"|;

FreeTree(root);

return0;

5、編寫(xiě)二叉樹(shù)的層次遍歷算法

解釋說(shuō)明：

二叉樹(shù)結(jié)構(gòu)是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，在遍歷的過(guò)程中先遍歷左子數(shù)，后遍歷右

子樹(shù)。在先左后右的原則下，根據(jù)訪問(wèn)根結(jié)點(diǎn)的次序，最后根據(jù)二叉樹(shù)的三種遍歷方法，即前

序遍歷、中序遍歷、后序遍歷，進(jìn)行算法的書(shū)寫(xiě)。

算法如下：

//二叉樹(shù)層次遍歷算法

#include<stdio.h>

#include<alloc.h>

#defineMaxSize1000

typedefcharElemType;

typedefstructnode

{

ElemTypedata;

structnode*lchild;

structnode*rchild;

}BTNode;

〃創(chuàng)建二叉樹(shù)

voidCreateBTNodefBTNode*&b,char*str)

{

BTNode*St[MaxSize],*p=NULL;

inttop=-l,k,j=0;

charch;

b=NULL;

ch=str[j];

while(ch!='\0')

(

switch(ch)

{

case,f:top++;St[top]=p;k=l;break;

case—;break;

case','-k=2;break;

default:p=(BTNode*)malloc(sizeof(BTNode));

p->data=ch;p->lchild=p->rchild=NULL;

if(b==NULL)b=p;

else

(

switch(k)

{

case1:St|top]->lchild=p;break;

case2:St|top]->rchild=p;break;

j++;

ch=str[j];

〃層次遍歷算法

voidLevelOrder(BTNode*b)

{

BTNode*p;

BTNode*qu|MaxSize|;

intfront,rear;

front=rear=-1;

rear++;

qu|rear|=b;

while(front!=rear)

{

front=(front+l)%MaxSize;

p=qu[front];

printf("%c",p->data);

if(p->lchild!=NULL)

{

rear=(rear+1|%MaxSize;

qu|rear]=p->lchild;

)

if(p->rchild!=NULL)

(

rear=(rear+l|%MaxSize;

qu[rear]=p->rchild;

〃主函數(shù)

intmainf)

{

BTNode*b,*h;

chars[MaxSize];//A(B(D(,G)),C(E,F))

printf("請(qǐng)輸入二叉樹(shù)括號(hào)表示法字符串：\n");

while(scanf("%s",&s))

CreateBTNode(b,s);

printf("層次遍歷莫法的訪問(wèn)次序?yàn)椋?');

LevelOrder(b);

printf("\n請(qǐng)輸入：叉樹(shù)括號(hào)表示法字符串：\n");

return0;

$

6、自底向上實(shí)現(xiàn)歸并排序算法

解釋說(shuō)明：

自底向上的歸并排序：歸并排序主要是完成將若干個(gè)有序子序列合并成一個(gè)完整的有序子序

列；自底向上的排序是歸并排序的一種實(shí)現(xiàn)方式，將?個(gè)無(wú)序的N長(zhǎng)數(shù)組切個(gè)成、個(gè)有序子序

列，然后再兩兩合并，然后再將合并后的N/2（或者N/2+1）個(gè)子序列繼續(xù)進(jìn)行兩兩合

并，以此類推得到一個(gè)完整的有序數(shù)組。

算法如下：

Q]/*******************************************吹************

02.*函數(shù)名稱：Merge

03.*參數(shù)說(shuō)明：pDataArray無(wú)序數(shù)組；

04.*int*pTempArray臨時(shí)存儲(chǔ)合并后的序列

05.*blndex需要合并的序列1的起始位置

06.*mlndex需要合并的序列1的結(jié)束位置

07,并且作為序列2的起始位置

08.*eindex需要合并的序列2的結(jié)束位置

09」說(shuō)明：將數(shù)組中連續(xù)的兩個(gè)子序列合并為一個(gè)有序序列

11.voidMerge(int*pDataArray,int*pTempArray,intblndex,intmlndex,inteindex)

124

13.intmLength=elndex-blndex;〃合并后的序列長(zhǎng)度

14.inti=0;〃記錄合并后序列插入數(shù)據(jù)的偏移

15.intj=blndex;//記錄子序列1插入數(shù)據(jù)的偏移

16.intk=mlndex;〃記錄子序列2摻入數(shù)據(jù)的偏移

17.

18.while(j<mlndex&&k<eindex)

19.(

20.if(pDataArray[j]<=pDataArray[k|)

21.(

22.pTempArray[i++]=pDataArray[j];

23.j++；

24.}

25.else

26.{

27.pTempArray[i++]=pDataArray[k];

28.k++;

29.}

30.)

31.

32.if(j==mlndex)〃說(shuō)明序列1已經(jīng)插入完畢

33.while(k<elndex)

34.pTempArray|i++]=pDataArray|k++];

35.else〃說(shuō)明序列2已經(jīng)插入完畢

36.while(j<mlndex)

37.pTempArray[i++]=pDataArray[j++|;

38.

39.for(i=0;i<mLength;i++)〃將合并后序列重新放入pDataArray

40.pDataArray[blndex+i]=pTempArray|i];

41.}

42.

43I*******************玄****************************區(qū)*******

44.*函數(shù)名稱：BottomUpMergeSort

45.*參數(shù)說(shuō)明：pDataArray無(wú)序數(shù)組；

46.*iDataNum為無(wú)序數(shù)據(jù)個(gè)數(shù)

47.*說(shuō)明：日底向上的歸并排序

48*********************************************************/

49.voidBottomUpMergeSort(int*pDataArray,intiDataNum)

50.{

51.int*pTempArray=(int*)malloc(sizeof(int)*iDataNum);〃臨時(shí)存放合并后的序列

52.intlength=1;〃初始有序子序列長(zhǎng)度為1

53.while(length<iDataNum)

54.{

55.inti=0;

56.for(;i+2*length<iDataNum;i+=2*length)

57.Merge(pDataArray,pTempArray,i,i+length,i+2*length);

58.if(i+length<iDataNum)

59.MergefpDataArray,pTempArray,i,i+length,iDataNum);

60.length*=2;〃有序子序列長(zhǎng)度*2

61.}

62.free(pTempArray);

63.}

7、實(shí)現(xiàn)堆排序算法

解釋說(shuō)明：

利用大頂堆(小頂堆)爛頂記錄的是最大關(guān)鍵字(最小關(guān)犍字)這一特性，使得每次從無(wú)序中

選擇最大記錄(最小記錄)變得簡(jiǎn)單。

其基本思想為(大頂堆)：

1)將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)須又；

2)將堆頂元素R[l]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無(wú)序區(qū)

(RI,R2,..........Rn-1)和新的有序區(qū)(Rn),且滿足R[l,2...n-l]<=R[n];

3)由于交換后新的堆頂R[l]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無(wú)序區(qū)

(R1,R2,.RnT)調(diào)整為新堆，然后再次將R[l]與無(wú)序區(qū)最后一個(gè)元素交換，得到新的

無(wú)序區(qū)(R1,R2...Rn-2)和新的有序區(qū)(Rn-l,Rn)。不斷重復(fù)此過(guò)程直到有序區(qū)的元素個(gè)數(shù)為

n-1,則整個(gè)排序過(guò)程完成。

D初始化堆：將R[L.n]構(gòu)造為堆;

2)將當(dāng)前無(wú)序區(qū)的堆頂元素R[l]同該區(qū)間的最后一個(gè)記錄交換，然后將新的無(wú)序

區(qū)調(diào)整為新的堆。

因此對(duì)于堆排序，最重要的兩個(gè)操作就是構(gòu)造初始堆和調(diào)整堆，其實(shí)構(gòu)造初始堆事

實(shí)上也是調(diào)整堆的過(guò)程，只不過(guò)構(gòu)造初始堆是對(duì)所有的非葉節(jié)點(diǎn)都進(jìn)行調(diào)整。

算法如下：

/*堆排序(大頂堆)2011.9.14*/

#include<iostream>

#include<algorithm>

usingnamespacestd;

voidHeapAdjust(int*a,inti,intsize)〃調(diào)整堆

intlchild=2*i;〃i的左孩子節(jié)點(diǎn)序號(hào)

intrchild=2*i+l;//i的右孩子節(jié)點(diǎn)序號(hào)

intmax=i;〃臨時(shí)變量

if(i<=size/2)〃如果i不是葉節(jié)點(diǎn)就不用進(jìn)行調(diào)整

(

if(lchild<=size&&a[lchild]>a[max])

{

max=lchild;

}

if(rchild<=size&&a[rchild]>a|max])

(

max=rchild;

)

if(max!=i)

(

swap(a|i|,a|max));

HeapAdjust|a,max,size);〃避免調(diào)整之后以max為父節(jié)點(diǎn)的子樹(shù)不是堆

|

}

|

voidBuildHeap(int*a,intsize)〃建立堆

(

inti;

for(i=size/2;i>=l;i-)〃非葉節(jié)點(diǎn)最大序號(hào)值為size/2

HeapAdjust(a,i,size);

voidHeapSort(int*a,intsize)〃堆排序

inti;

BuildHeap(a,size);

for(i=size;i>=l;i—)

(

//cout<<a[l]<<"

swap(a|l],a|i|);〃交換堆頂和最后一個(gè)元素，即每次將剩余元素中的最

大者放到最后面

//BuildHeap(aj-l);〃將余下元素重新建立為大頂堆

HeapAdjust(a,l,i-l);〃重新調(diào)整堆頂節(jié)點(diǎn)成為大頂堆

intmain(intargc,char*argv[])

(

//inta|]={0,16,20,3,11,17,8);

inta[100|;

intsize;

while(scanf("%d",&size)==l&&size>O)

{

inti;

fbr(i=l;i<=size;i++)

cin>>a[i];

HeapSort(a,size|;

for(i=l;i<=size;i++)

cout<<a[i|?"

cout<<endl;

return0;

|

8、實(shí)現(xiàn)迪杰斯特拉最短路徑算法

解釋說(shuō)明：

Dijkslra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)

點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法

能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。

Dijkstra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)

的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。

其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集

合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。

初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路

稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。

Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u,將u添加到S中，同時(shí)對(duì)數(shù)組

dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的

最短路徑長(zhǎng)度。

算法如下：

01.#include<limits>

O2.#include<queue>

O3.usingnamespacestd;

04.constintmax_size=20;

05.classVertex

O6.(

07.public:

08.Vertex));

09.voidinput(in:number,intdistance);

10.queue<int>passed_way;〃用來(lái)存放源節(jié)點(diǎn)到該節(jié)點(diǎn)途徑的節(jié)點(diǎn)下標(biāo)

11.intoutput(intn);

12.

13.private:

14.intlength|max_size];

15.

16.};

17.Vertex::Vertex))

18.(

19.forfinti=0;i<max_size;i++)

20.length[i|=numeric」imits<int>::max();//int的最大值

21.

22.}

23.voidVertex::input(intnumber,intdistance)/tnnumber個(gè)賦值distance

/24.{

25.

26.length|number|=distance;

27.}

28.

29.intVertex::output(intn)〃輸出第n個(gè)值

30.(

31.

32.returnlength[n];

33.}

[cpp]viewplaincopy

0l.#include"vertex.h"

02.classDigraph

03.(

04.public:

05.Digraph));

06.voidset_distances(ints,intdistance1]);

07.voidget_in(Vertexv,intn);

08.voidinitial_length();

09.

10.Vertexnumber[max_size];

11.intadjacencjf[max_size]|max_size];

12.);

13.

14.constintinfinity=numeric」imits<int>::max();//int的最大值

15.

16.Digraph::Digraph()

17.{

18.)

19.

20.

21.voidDigraph::set_distances(ints,intdistance。)〃計(jì)算第s個(gè)節(jié)點(diǎn)到其他各個(gè)節(jié)點(diǎn)的最小距

離,結(jié)果存放在distance中

22.(

23.intv,w;

24.boolfound[13];"用來(lái)標(biāo)記其他節(jié)點(diǎn)到第s個(gè)節(jié)點(diǎn)的最短距離是否被計(jì)算確定了

25.for(v=0;v<13;v++)〃初始化found、distance

26.(

27.foundfv]=false;

28.distance^]=adjacency[s]M；//將distance的值設(shè)置為笫s個(gè)節(jié)點(diǎn)到其節(jié)點(diǎn)的現(xiàn)有

距離，不聯(lián)通的設(shè)為無(wú)窮大，對(duì)自己設(shè)為0

29.}

30.found?=true;//當(dāng)前節(jié)點(diǎn)s對(duì)應(yīng)自己的設(shè)true,讓后面尋找最短距離能避開(kāi)自己

31.distanced=0;//再次賦值確保自己對(duì)自己的距離是0

32.for(inti=0;i<12;i++)〃一共有13個(gè)節(jié)點(diǎn)，循環(huán)12次,依次計(jì)算對(duì)其他節(jié)點(diǎn)的最小距

離

33.{

34.intmin=infinity;//首先將min設(shè)為無(wú)窮大

35.for(w=0;w<13;w++)

36.if(!found[w])//循環(huán)除s本身的其余各個(gè)節(jié)點(diǎn)，找出離s最近的點(diǎn)

37.訐(distance[w]<min)//distancew]保存當(dāng)前節(jié)點(diǎn)到各節(jié)點(diǎn)(包含自己)的

距離，比較循環(huán)到的節(jié)點(diǎn)與當(dāng)前最小距離

38.(

39.v=w;//如果比當(dāng)前最小距離小，那么記下這個(gè)節(jié)點(diǎn)的下標(biāo)

40.min=distance[w];//更改最小值

41.)

42.found[v]=true;//循環(huán)結(jié)束后，將距離s節(jié)點(diǎn)最近的點(diǎn)v標(biāo)記出來(lái)

43.

44.numberM.passed_way.push(v);//將v點(diǎn)的vertex對(duì)象中passed_way隊(duì)歹J1存放進(jìn)

v點(diǎn)下標(biāo)

45.

46.for(w=0;w<13;w++)

47.if(!found[w])〃循環(huán)除s本身和離s最近的點(diǎn)v除外的其余各點(diǎn)

48.if(m:n+adjacency[v][w]<distance[w])//s到v的距離+v至lj除s和v

本身以外的其余點(diǎn)w的距離如果該距離小于s到w的距離(不聯(lián)通的距離是無(wú)限大)

49.{

50.if(adjacency[v][w]!=infinity)//如果v到w聯(lián)通

51.{

52.distance[w]=min+adjacency[v][w];//更改s到w的距離

53.number[w].passed_way=number,v|.passed_way;/v點(diǎn)的

vertex對(duì)象中的passed_way賦值給w點(diǎn)的vertex對(duì)象中的passed_way(passed_way是可變

長(zhǎng)度隊(duì)列)

54.}

55.}

56.//for循環(huán)內(nèi)的兩個(gè)循環(huán)，第一個(gè)for找到距離s點(diǎn)最近的點(diǎn)v；第二個(gè)for計(jì)算

有了V之后，其他節(jié)點(diǎn)到s距離的更新

57.)

58.}

59.

60.voidDigraph::get_in(Vertexx,intn)

61.{

62.number[n]=x;

63.}

64.

65.voidDigraph::initial_length()

66.{

67.for(inti=0;i<max_size;i++)

68.for(intj=0;j<max_size;j++)

69.adjacency|i][j]=number|i].output(j);

70.

71.}

|cpp|viewplaincopy

01.#include"digraph.h"

O2.#include<iostream>

O3.#include<string>

04.usingnamespacestd;

O5.intmain()

O6.(

07.Vertexa,b,c,d,e,f,g,h,i,j,k,l,m;

08.a.input(0,0),a.input(l,2),a.input(4,8),a.input(9,4),a.input(12,8);

09.b.input(0,2),b.input(l,0),b.input(2,3),b.input(10,l);

10.c.input(1,3),c.input(2,0),c.input(3,1);

11.d.input(2,l),d.input(3,0),d.input(4,5),d.input(10,2),d.input(l1,2);

12.e.input(0,8),e.input(3,5),e.input(4,0),e.input(5,9),e.input(ll,3),e.input(12,3);

13.f.input(4,9),f.input(5,0),f.input(6,8),f.input(12,6);

14.g.input(5,8),g.input(6,0),g.input(7,10),g.input(8,l),g.input(12,5);

15.h.input(6,10),h.input(7,0);

16.i.input(6,l),i.input(8,0),i.input(9,2);

17.j.input(0,4),j.input(8,2),j.input(9,0),j.input(10,5);

18.k.input(l,l),k.input(3,2),k.input(9,5),k.input(10,0),k.input(l1,1);

1