计算机软件应用结课作业

《软件技术基础》结课大作业

姓名：院振召

学号：120611335_______

日期：2014年6月20日________

2014软件技术基础期末作业

说明与要求:

1.开放式考试不仅考察知识，同时考察学生查阅文献的能力；学生可以使用Google,百

度等搜索引擎，图书馆数字资源，如同方CNKI（中国学术期刊全文数据库）查阅资料，寻

找答案和解题思路；

2.可以使用各种工具帮助自己解题，可以相互讨论，但是不允许拷贝、复制、剽窃他人

结果。如果发现雷同，按雷同人数，每次雷同从成绩中扣除10分。因不存在完美雷同

标准，因此将根据批改教师的个人识别，进行雷同确认，因此为避免雷同，请自己设

计代码或解题；

3.每个编程问题都要首先说明思路，然后给出代码；程序以及求解方法描述的编辑应该

美观；程序代码应该有层次缩进，以便阅读；

4.每个编程问题的C/C++代码的每一行必须有清晰的注释，说明改行中变量和语句的作

用，如果注释和C/C++语句不符，则视为剽窃。

5.根据自己的情况，采用C或C++语言中德一种作为编程语言，不能使用两种以上的语言；

6.编辑排版时，采用汉字五号宋体，英语和代码采用10号或五号TimesNewRoman字体，

打印时采用双面打印，连同填写好的封面一起装订，在最后一堂课时上交；禁止使用

更大号字；

2014软件技术基础期末作业

1.利用减半递推技术，写出求长度为n的数组中最大元素的递归算法（10分）。

2.编写用回溯法求解n皇后的算法（10分）。

3.给定n个城市间的距离，求从一个城市。出发经过其他城市一次且一次的一条最短路

径（15分）。

4.将单链表看做二叉树，编写递归程序打印单链表（10分）。

5.编写二叉树的层次遍历算法（15分）。

6.自底向上实现归并排序算法（10分）。

7.实现堆排序算法（15分）。

8.实现迪杰斯特拉最短路径算法（15分）

T、利用减半递推技术，写出求长度为n的数组中最大元素的递归算法

解择说明：

解决实际问题的复杂程度往往与问题的规模有着密切的关系，因此，降低问题的规模是算

法设计的关键，而减半递推技术是降低问题国模的一种有效方法。所谓的“减半”，是指将

问题慨撷泮，而问题的颉不变。所I醐“递1隹”球重复“减半”僦程。

算法如下：

#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、编写用回溯法求解n皇后的算法

解释说明：

n个皇后在n元棋盘上的布局有n的n次方种，用回溯发求解问题。

假设定义一个长度为n的一维数组q,其中的每一个元素q[i](i=l,2,...,n)随时记录

第n行上的皇后所在的序列号。

初始时，先将各皇后放在各行的第一列。即数组q的初值为=

而它们在同一列上的条件为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个城市间的距离，求从一个城市。出发经过其他城市一次且一次的一条最短路径(15

分)。

解释说明：

从理论上讲，可以计算出最短路径，但要借助计算机，计算量较大，人力难以胜任。方法

如下：

假定出发城市编号为。，其他城市编号为1〜nT,将1〜『1号城市排列，按排列顺序计

算每种排列从排头城市到徘尾城市的距离和X,实际距离D=X+O和排头城市的距离+0和排尾

城市的距离，这样共得到A<nT>=(nT)!个距禽D,从中选出最小的一个即可。编一段简单

程序，把n个城市间的距离输入进去，就能轻易算出最短距离

算法如下：

#include<stdio.h>

intmain()

{

intG[100][100]={0};〃一个记录图的邻接矩阵

inta,b,w;〃输入一共有7条边，5个点

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代表这条边的两

个顶点w代表两个点的距离

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]);//输出两点之间的最短路，这里的两个点是3和

5

return0;

代表i到j的距离，甲，乙，内，丁，戊用1，2,3,4,5代替

4、将单链表看做二叉树，编写递归程序打印单链表

解释说明：

建立和遍历二叉树的程序都比较简单，关键在于按要求打印二义树。起初一直找不到合适

的方法按题目要求打印二叉树，在和同学讨论了很久之后终于有了思路。打印的格式中，最上

层的节点是右子树层次最高的，于是就可以用递归调用的方式实现。递归次数最高的就是输出

最顶置的节点。在调试程序的时候也出现了问题，起初没有在意输入方式对程序运行结果的影响,

导致程序无法运行，在检查了很久之后终于找到了问题的所在，对输入进行了改正，得到了正确

的结果。

在建立二叉树时，输入的格式一定要正确，没有孩子的要用空格表示，在测试用例中，

F没有孩子，要用两个空格表示，如果输入“AB#D##CE#F”则没有输出结果。

算法如下：

#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;

〃创建堆栈

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;

)

)

)

)

)

)

〃中序遍历求结点的深度和度为0,1,2的结点数，结果保存在pAns指的。。

voidInOrderDOfBiTree*t,Answear*pAns)

〃遍历用的数据

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

〃求深度的数据

intcurDeep,MostDeep;

〃创建堆栈

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

(

printf("InOrderfailedformemery\n");

return;

}

〃初始化堆栈

top=stack;

P=t;

〃初始化数据

curDeep=MostDeep=0;

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

〃遍历循环

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结点

〃计算个结点的度

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、编写二叉树的层次遍历算法

解释说明：

二叉树结构是一种非常重要的非线性数据结构，在遍历的过程中先遍历左子数，后遍历右

子树。在先左后右的原则下，根据访问根结点的次序，最后根据二叉树的三种遍历方法，即前

序遍历、中序遍历、后序遍历，进行算法的书写。

算法如下：

//二叉树层次遍历算法

#include<stdio.h>

#include<alloc.h>

#defineMaxSize1000

typedefcharElemType;

typedefstructnode

{

ElemTypedata;

structnode*lchild;

structnode*rchild;

}BTNode;

〃创建二叉树

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;

〃主函数

intmainf)

{

BTNode*b,*h;

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

printf("请输入二叉树括号表示法字符串：\n");

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

CreateBTNode(b,s);

printf("层次遍历莫法的访问次序为：*');

LevelOrder(b);

printf("\n请输入：叉树括号表示法字符串：\n");

return0;

$

6、自底向上实现归并排序算法

解释说明：

自底向上的归并排序：归并排序主要是完成将若干个有序子序列合并成一个完整的有序子序

列；自底向上的排序是归并排序的一种实现方式，将•个无序的N长数组切个成、个有序子序

列，然后再两两合并，然后再将合并后的N/2（或者N/2+1）个子序列继续进行两两合

并，以此类推得到一个完整的有序数组。

算法如下：

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

02.*函数名称：Merge

03.*参数说明：pDataArray无序数组；

04.*int*pTempArray临时存储合并后的序列

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

06.*mlndex需要合并的序列1的结束位置

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

08.*eindex需要合并的序列2的结束位置

09」说明：将数组中连续的两个子序列合并为一个有序序列

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

124

13.intmLength=elndex-blndex;〃合并后的序列长度

14.inti=0;〃记录合并后序列插入数据的偏移

15.intj=blndex;//记录子序列1插入数据的偏移

16.intk=mlndex;〃记录子序列2掺入数据的偏移

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)〃说明序列1已经插入完毕

33.while(k<elndex)

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

35.else〃说明序列2已经插入完毕

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*******************玄****************************区*******

44.*函数名称：BottomUpMergeSort

45.*参数说明：pDataArray无序数组；

46.*iDataNum为无序数据个数

47.*说明：日底向上的归并排序

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

49.voidBottomUpMergeSort(int*pDataArray,intiDataNum)

50.{

51.int*pTempArray=(int*)malloc(sizeof(int)*iDataNum);〃临时存放合并后的序列

52.intlength=1;〃初始有序子序列长度为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;〃有序子序列长度*2

61.}

62.free(pTempArray);

63.}

7、实现堆排序算法

解释说明：

利用大顶堆(小顶堆)烂顶记录的是最大关键字(最小关犍字)这一特性，使得每次从无序中

选择最大记录(最小记录)变得简单。

其基本思想为(大顶堆)：

1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无须又；

2)将堆顶元素R[l]与最后一个元素R[n]交换，此时得到新的无序区

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

3)由于交换后新的堆顶R[l]可能违反堆的性质，因此需要对当前无序区

(R1,R2,.RnT)调整为新堆，然后再次将R[l]与无序区最后一个元素交换，得到新的

无序区(R1,R2...Rn-2)和新的有序区(Rn-l,Rn)。不断重复此过程直到有序区的元素个数为

n-1,则整个排序过程完成。

D初始化堆：将R[L.n]构造为堆;

2)将当前无序区的堆顶元素R[l]同该区间的最后一个记录交换，然后将新的无序

区调整为新的堆。

因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事

实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

算法如下：

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

#include<iostream>

#include<algorithm>

usingnamespacestd;

voidHeapAdjust(int*a,inti,intsize)〃调整堆

intlchild=2*i;〃i的左孩子节点序号

intrchild=2*i+l;//i的右孩子节点序号

intmax=i;〃临时变量

if(i<=size/2)〃如果i不是叶节点就不用进行调整

(

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);〃避免调整之后以max为父节点的子树不是堆

|

}

|

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

(

inti;

for(i=size/2;i>=l;i-)〃非叶节点最大序号值为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|);〃交换堆顶和最后一个元素，即每次将剩余元素中的最

大者放到最后面

//BuildHeap(aj-l);〃将余下元素重新建立为大顶堆

HeapAdjust(a,l,i-l);〃重新调整堆顶节点成为大顶堆

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、实现迪杰斯特拉最短路径算法

解释说明：

Dijkslra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节

点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法

能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细

的介绍，如数据结构，图论，运筹学等等。

其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集

合S当且仅当从源到该顶点的最短路径长度已知。

初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路

称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。

Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中，同时对数组

dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的

最短路径长度。

算法如下：

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;〃用来存放源节点到该节点途径的节点下标

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个赋值distance

/24.{

25.

26.length|number|=distance;

27.}

28.

29.intVertex::output(intn)〃输出第n个值

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。)〃计算第s个节点到其他各个节点的最小距

离,结果存放在distance中

22.(

23.intv,w;

24.boolfound[13];"用来标记其他节点到第s个节点的最短距离是否被计算确定了

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

26.(

27.foundfv]=false;

28.distance^]=adjacency[s]M；//将distance的值设置为笫s个节点到其节点的现有

距离，不联通的设为无穷大，对自己设为0

29.}

30.found®=true;//当前节点s对应自己的设true,让后面寻找最短距离能避开自己

31.distanced=0;//再次赋值确保自己对自己的距离是0

32.for(inti=0;i<12;i++)〃一共有13个节点，循环12次,依次计算对其他节点的最小距

离

33.{

34.intmin=infinity;//首先将min设为无穷大

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

36.if(!found[w])//循环除s本身的其余各个节点，找出离s最近的点

37.讦(distance[w]<min)//distancew]保存当前节点到各节点(包含自己)的

距离，比较循环到的节点与当前最小距离

38.(

39.v=w;//如果比当前最小距离小，那么记下这个节点的下标

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

41.)

42.found[v]=true;//循环结束后，将距离s节点最近的点v标记出来

43.

44.numberM.passed_way.push(v);//将v点的vertex对象中passed_way队歹J1存放进

v点下标

45.

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

47.if(!found[w])〃循环除s本身和离s最近的点v除外的其余各点

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

本身以外的其余点w的距离如果该距离小于s到w的距离(不联通的距离是无限大)

49.{

50.if(adjacency[v][w]!=infinity)//如果v到w联通

51.{

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

53.number[w].passed_way=number,v|.passed_way;/v点的

vertex对象中的passed_way赋值给w点的vertex对象中的passed_way(passed_way是可变

长度队列)

54.}

55.}

56.//for循环内的两个循环，第一个for找到距离s点最近的点v；第二个for计算

有了V之后，其他节点到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