北京信息科技大学
计算机软件基础课程设计
题 目： 从某个源点到其余各顶点的最短路径
学 院： 光电信息与通信工程学院
专 业： 通信工程专业
学生姓名： 班级/学号
指导老师： 曹林李振松张月霞杨玮
起止时间：
摘要
本次课程设计的问题：假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，它们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；北京到武汉的最短路径。
本次课程设计中应用Floyd算法求最短路径。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵，从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，按一个公式，构造出矩阵D(1)，又用同样地公式由D(1)构造出D(2)…最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
本次试验可以进行有向和无向的计算，不同城市之间的距离由开始进行输入，最后显示两个城市之间的最短路径。
一、应用弗洛伊德（Floyd）算法计算最短路径
假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，他们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；求北京到武汉的最短路径。
二、弗洛伊德（Floyd）算法的基本思想
Floyd 算法是通过权矩阵计算来实现的一种方法，其主要思想是从代表任意两个节点vi到vj的距离的带权邻接矩阵D(0)开始，首先计算D(1)，即计算vi到vj的距离。经过一次经转的所有可能路径，经过比较后选出最短路，代替D(0)中对应的路径，迭代列出距离矩阵D(1)，D(1)中各元素表示通过一次迭代后网络中任意两点间最短路，也即网络中任意两点之间直接到达或只经过一个中间点时的最短路。在此基础上依次计算D(2) ,D(3) ,…,D(k)，D(k)中对应的元素表示任意两点间不经过中间点或最多允许经过2k-1 个中间点时的最短路。当D(k+1)=D(k)时，表明得到的带权邻接矩阵D(k)就反映了所有顶点对之间的最短距离信息,，成为最短距离矩阵。
三、floyd算法函数
四、基本流程
Floyd采用动态规划余力和逐步优化激素和，对有向带权图G=（V, E）设计出求每对定点见最短路径的方法。该刚发使用邻接矩阵表示有向带权图G，有向图中的n个顶点从1开始编号。初始时，用邻接矩阵adges存储有向图G，即顶点i到j的最短路径长度adges[i][j]就是弧所对应的权值，它表示任意顶点对之间不经过任何中间顶点的最短路径和长度。要求顶点i到j记得最短路径长度，对每一对顶点的路径进行比较存储的试探，累加递归后产生一个n阶路径矩阵序列A，算法结束时，从该矩阵可以查找到i到j的最短路径上的所有点。
void pathchange(int i,int j,int k)//路径处理函数
{
int m,n,p,q;
for(m=0;m<max;m++)
{
path[i][j].distance[m]=-1;
}//首先将其初始化
计算两点之间的距离
for(q=0;q<max;q++)
{
if(path[i][k].distance[q]!=-1)
{
m++;
}
else
{
break;
}
}//获取path[i][k]的长度为m
for(q=0;q<max;q++)
{
if(path[k][j].distance[q]!=-1)
{
n++;
}
else
{
break;
}
}//获取path[k][j]的长度为n
五、功能实现
1、设定ABCD四个城市，之间全连通，无向。结果如下：
输入：
结果：
2、设定ABCD四个城市、之间为非全连通，无向。
输入：
结果：
3、设定ABCD四个城市、全连通，有向
输入：
结果：
4、设定ABCD四个城市、非全连通、有向。
输入：
结果：
5、ABCD四个城市，A、C之间的最短距离是ABC
截图如下：
代码：
extern "C" _declspec(dllexport)int sushu( int n)
{int i;
for(i=2;i<n;i++)
if(n%i)
return 1;
else return 0;}
#include "stdafx.h"
extern "C" _declspec(dllimport)int sushu( int i);
int main(int argc,char *argv[])
{
int i=1,m;
printf("输入的数字为:");
scanf("%d",&m);printf("素数有：\n");
while(i+1<=m)
{
i++;
if(sushu(i))
printf("%d\t",i);
}
return 0;
}
截图如下：
七、心得体会
参考文献
源代码：
#include "stdio.h"
#define max 100
struct place
{
char name[max];
}
pla[max];//地域名称
struct path
{
int distance[max];
}
path[max][max];//行进路线
int a[max][max]={0};
void pathchange(int i,int j,int k)//路径处理函数
{
int m,n,p,q;
for(m=0;m<max;m++)
{
path[i][j].distance[m]=-1;
}//首先将其初始化
m=0;
n=0;
for(q=0;q<max;q++)
{
if(path[i][k].distance[q]!=-1)
{
m++;
}
else
{
break;
}
}//获取path[i][k]的长度为m
for(q=0;q<max;q++)
{
if(path[k][j].distance[q]!=-1)
{
n++;
}
else
{
break;
}
}//获取path[k][j]的长度为n
for(p=0;p<m;p++)
{
path[i][j].distance[p]=path[i][k].distance[p];//将path[i][k]的内容转到path[i][j]中去
}
for(p=0;p<n;p++)
{
path[i][j].distance[p+m]=path[k][j].distance[p];//将path[k][j]的内容转到path[i][j]中去
}
}
void cin(int*p) //赋值和路线函数初始化函数
{
printf("请输入城市的个数 (大于二)\n");
scanf("%d",p);
while(*p<=2)
{
printf("输入值不合法请重新输入\n");
scanf("%d",p);
}
int i=0,j=0,k=0;
for(i=0;i<max;i++) //为了多次循环而进行的初始化
{
for(j=0;j<max;j++)
{
a[i][j]=0;
}
}
for(i=0;i<*p;i++)
{
for(j=0;j<*p;j++)
for(k=0;k<max;k++)
{
if(k==0)
{
path[i][j].distance[k]=i;
}
else
{
if(k==1)
{
path[i][j].distance[k]=j;
}
else
path[i][j].distance[k]=-1;
}
}
}
}
void begin(int n,int choo)//初始化函数2
{
int i=0,j=0;
for(i=1;i<=n;i++)
{
printf("请输入第"); printf("%d",i);printf("个城市的名字\n");
scanf("%s",pla[i-1].name);
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{if(i==j)
{
a[i][j]=0;
}
else{
switch (choo)
{
case 1:printf("请输入");printf("%s",pla[i].name); printf("到");
printf("%s",pla[j].name); printf("的距离 (不通请输入-1)\n");
scanf("%d",&a[i][j]);break;
case 2: if(j>i)
{
printf("请输入");printf("%s",pla[i].name); printf("到");
printf("%s",pla[j].name); printf("的距离 (不通请输入-1)\n");
scanf("%d",&a[i][j]);
} break;
}
}
}
}
if(choo==2)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
a[j][i]=a[i][j];
}
}
}
}
void floyd(int n)//floyd算法函数
{
int i=0,j=0,k=0;
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]>a[i][k]+a[k][j])
{
if(a[i][k]!=-1&&a[k][j]!=-1)
{
a[i][j]=a[i][k]+a[k][j];
pathchange(i,j,k);
}
}
}
}
}
}
int choose()
{
int num,num_check;
printf("请选择两城市间是有向图还是无向图\n");
printf("1-------------有向 (城市间来回距离可以不一样)\n");
printf("2-------------无向 (城市间来回距离完全一样)\n");
scanf("%d",&num);
while(num!=1&&num!=2)
{
printf("输入值不合法请重新输入\n");
scanf("%d",&num);
}
if(num==1)
{
printf("您已经选择有向图！\n");
}
else
{
printf("您已经选择无向图！\n");
}
return num;
}
void main()
{
int n=0,t=1;
while(t)
{int choo=0;
choo=choose();
cin(&n);
begin(n,choo);
floyd(n);
print(n,&t,&n);
}
}
第二篇：软件课程设计报告模版
编号：（ ）字 号
《软件课程设计》报告
班 级： 计科09-6班 姓 名： 冯振兵 学 号： 08093474
指导老师： 毛 磊
中国矿业大学计算机科学与技术学院
年 月
1
软件课程设计任务书
专业年级： 计算机科学与技术09级 学生姓名： 冯振兵
任务下达日期： 200 年 月 日
课程设计日期： 200 年 月 日至 200年 月 日
课程设计题目： 面向过程
2
软件课程设计指导教师评阅书
指导教师评语（①基础理论及基本技能的掌握；②独立解决实际问题的能力；③研究内容的理论依据和技术方法；④取得的主要成果及创新点；⑤工作态度及工作量；⑥总体评价及建议成绩；⑦存在问题等）：
成 绩： 指导教师签字：
年 月 日
一、面向过程设计题-------正整数转换为罗马数据
1.1 需求分析……………………………………………………………………….…9
1.2 概要设计………………………………………………………………………...10
1.3 详细设计与编码………………………………………………………………...11
1.4 调试分析………………………………………………………………………...13
1.5 用户使用说明 ………………………………………………………………….13
1.6 设计心得………………………………………………………………………...13 /***7. 将输入的罗马数据化为10进制数。假设罗马数据中只使用如下7个 “基值”字母：M、D、C、L、X、V、I，分别用来表示1000、500、100、50、
10、5、1。如，罗马数据LXXXVII表示10进制的87。
将输入的10进制正整数转换为罗马数据。假设罗马数据中只使用“基值
3
”字母：M、D、C、L、X、V、I，分别用来表示1000、500、100、50、10、5、1。 ***/ #include <iostream>
#include <string>
using namespace std;
int main()
{
string a;cout<<"Enter the Romen number: " ;
int zhuanhuan(string );
cin>>a;
cout<<"Its Arab number is : "<<zhuanhuan(a)<<endl;
return 0;}
int zhuanhuan(string a)
{int s=0,i=0,j=0,b[7]={1000,500,100,50,10,5,1};
string c="MDCLXVI";
a=a+'\0';
/*****
while(a[i++]!='u')
{for(j=0;j<7;j++)
{if(a[i]==c[j])
s+=b[j];break;}
if(j==7)
{cout<<"eror!!!!!"<<endl;break;}误用了break
}
while(a[i]!='\0')
{for(j=0;j<7;j++)
{if(a[i]==c[j])
s+=b[j];}
i++;
}
return s;}
/***将输入的10进制正整数转换为罗马数据。
假设罗马数据中只使用“基值”字母：
M、D、C、L、X、V、I，分别用来表示1000、
4 *****/
500、100、50、10、5、1。***/
#include <iostream>
#include <string>
using namespace std;
int main()
{int i,x,b[]={1000,500,100,50,10,5,1};
cout<<"Enter x:";
cin>>x;
string a="MDCLXVI";
for (i=0;i<7;i++)
if(x>=b[i])
{x-=a[i];cout<<a[i];i-=1;}
cout<<endl;
return 0;}
编写过程中误用了break语句，以为可以通过它跳出for循环而留在while循环内；导致 检测一直正确而运行不出想要的结果；
进过反复的检查，终于找出原因；
二、面向过程设计题------求Fibonacci数列
2.1 需求分析…………………………………………………………………………13
2.2 概要设计………………………………………………………………………...14
2.3 详细设计与编码………………………………………………………………...16
2.4 调试分析………………………………………………………………………...17
2.5 用户使用说明 ………………………………………………………………….17
2.6 设计心得………………………………………………………………………...17 求Fibonacci数列
#include <iostream>
using namespace std;
int main()
{int n;
int fib (int n);
while(1){cout<<"n为：";
cin>>n;
cout<<"Fibonacci数列的第"<<n<<"项值为："<<fib(n)<<endl;}
return 0;}
int fib (int n)
{if(n==1||n==2)return 1;
int a=1,b=1,c,i=2;
while(i<n)
{c=a+b;
a=b;
5
b=c;
i++;}
return c;}
#include <iostream>
using namespace std;
int main()
{int n;
double fib (int n);
while(1){cout<<"n为：";
cin>>n;
cout<<"Fibonacci数列的第"<<n<<"项值为："<<fib(n)<<endl;} return 0;}
double fib(int n)
{if(n==1||n==2)return 1;
return fib(n-1) + fib(n-2);}
第二个用递归的算法使程序更加简洁
三、面向对象设计题3------用三种方法通过虚函数求Fibonacci数列（mianxiangduixiang3.cpp）
3.1 需求分析…………………………………………………………………………17
3.2 概要设计………………………………………………………………………...19
3.3 详细设计与编码………………………………………………………………...21
3.4 调试分析………………………………………………………………………...22
3.5 用户使用说明 ………………………………………………………………….22
3.6 设计心得………………………………………………………………………...22
四、面向过程设计题9--------- 模拟ＡＴＭ机
4.1 需求分析…………………………………………………………………………22
4.2 概要设计………………………………………………………………………...23
4.3 详细设计与编码………………………………………………………………...25
4.4 调试分析………………………………………………………………………...25
4.5 用户使用说明 ………………………………………………………………….25
4.6 设计心得………………………………………………………………………...25 //模拟银行ATM取款机
#include<iostream>
#include <string>
using namespace std;
class consumer;
6
class ATM // ATM取款机
{
public:
ATM (consumer& cn):cnsm(cn){}
void welcome(); // 登陆界面
bool check_passwd(string n,string pwd); // 核对密码
void change_passwd(); // 修改密码
void fetchmoney(); // 取款
void cunmoney(); //存款
void information(); // 查询信息
void exitATM(); // 退出系统
void functionshow(); // 功能界面
void lock(); // 锁机
private:
int times; // 记录密码输入次数
consumer& cnsm;
};
class consumer // 用户
{
public:
friend class ATM;
consumer (string Name,string Num,float Money,string PassWord); protected:
string get_name(); // 取得姓名
string get_num(); // 取得卡号
string get_passwd(); // 取得密码
float get_money(); // 取得余额
void set_passwd(string pwd); // 设置密码
void set_money(float m); // 取钱
void save_money(float m) ;//存钱
private:
string passwd; // 用户密码
string name; // 用户姓名
string num;
float money;
};
consumer::consumer(string Name,string Num,float Money,string Password) {
name=Name;
num=Num;
money=Money;
7
passwd=Password;
}
float consumer::get_money()
{return money;}
string consumer::get_name()
{return name;}
string consumer::get_num()
{return num;}
string consumer::get_passwd()
{return passwd;}
void consumer::set_money(float m)
{money-=m;}
void consumer::save_money(float m)
{money+=m;}
void consumer::set_passwd(string pwd)
{passwd=pwd;}
void main()
{
consumer c1("jim","12345",5200.3f,"123"); // 先构造一个用户 ATM atm(c1);
atm.welcome();
}
void ATM::welcome()
{
times=0;
cout<<"$欢迎使用中国银行ATM自动取款机!~!"<<endl; string pwd,num,ch;
do
{
cout<<endl<<"请输入卡号:";
cin>>num; cout<<"请输入密码:"; cin>>pwd; if(!check_passwd(num,pwd)) { cout<<"你输入的卡号或密码有误,请重新输入"<<endl; times++; 8
} else { functionshow(); }
}while(times<3);
lock();
}
bool ATM::check_passwd(string num,string pwd)
{
if(num==cnsm.get_num()&&pwd==cnsm.get_passwd())
return true;
else
return false;
}
void ATM::functionshow()
{
int n;
do
{
cout<<endl<<"请你输入相应的操作序号进行操作:"<<endl;
cout<<"1) 修改密码 "<<endl<<"2) 取款"<<endl<<"3) 存款 "<<endl<<"4) 查询余额 "<<endl<<"5) 退出系统 "<<endl;
cout<<"$>"; cin>>n; while(n<1||n>5) { cout<<"请输入正确的操作序号!"<<endl; } switch(n) { case 1:change_passwd(); break; case 2: fetchmoney(); break; case 3:cunmoney(); break; case 4:information(); break; case 5:exitATM(); break; 9 cout<<"$ >"; cin>>n;
}
}while(true);
}
void ATM::change_passwd()
{
char pwd[8],repwd[8];
times=0;
do
{
cout<<endl<<"请输入旧密码：";
cin>>pwd; if(!check_passwd(cnsm.get_num(),pwd)) times++; else
break;
}while(times<3);
if(times==3)
lock();
int t=0;
do
{
cout<<"请输入新密码：";
cin>>pwd; cout<<"请再输入一次新密码："; cin>>repwd; if((t=strcmp(pwd,repwd))!=0) cout<<"你输入的两次密码不一样,请重新输入!"<<endl; } while(t!=0); cnsm.set_passwd(pwd); cout<<"密码修改成功，请牢记!"<<endl;
}
void ATM::fetchmoney()
{
float m;
char ch;
do
{
cout<<endl<<"你要取多少钱: "<<endl<<"$>" ;
cin>>m; while(m<=0) { cout<<"请输入正确的数字!"<<endl; 10
cout<<"$>"; cin>>m; } if(cnsm.get_money()-m<0) { cout<<"对不起，你的余额不足!"
<<endl;
}
else
{
cout<<endl<<"操作成功，请收好钱!"
<<endl;
cnsm.set_money(m);
}
cout<<"是否要继续该项操作：(Y/N) "
<<endl;
cout<<"$ >";
cin>>ch;
while(ch!='n'&&ch!='N'&&ch!='Y'&&ch!='y') {
cout<<"$ >";
cin>>ch;
}
}while(ch=='y'||ch=='Y');
}
void ATM::cunmoney()
{
float m;
char ch;
do
{
cout<<endl<<"你要存多少钱: "<<endl<<"$>" ;
cin>>m; while(m<=0) { cout<<"请输入正确的数字!"<<endl; cout<<"$>"; } cout<<endl<<"操作成功!" <<endl; 11 cin>>m;
cnsm.save_money(m); cout<<"是否要继续该项操作：(Y/N) " <<endl; cout<<"$ >"; cin>>ch; while(ch!='n'&&ch!='N'&&ch!='Y'&&ch!='y') { cout<<"$ >"; cin>>ch;
}
}while(ch=='y'||ch=='Y');
}
void ATM::information()
{
cout<<"**********************************"<<endl;
cout<<"*"<<endl; cout<<"* 用户姓名："<<cnsm.get_name()<<endl; cout<<"* 卡号： "<<cnsm.get_num()<<endl; cout<<"* 余额: "<<cnsm.get_money()<<endl;
cout<<"**********************************"<<endl;
}
void ATM::lock()
{
cout<<endl<<"对不起，由于你的操作有误,你的卡已经被没收! "<<endl;
exit(1);
}
void ATM::exitATM()
{
cout<<endl<<"感谢你对本银行的支持,欢迎下次光临!"<<endl;
cout<<"请取卡??"<<endl;
exit(0);
}
这个程序我在原来知道的一个模拟ＡＴＭ机程序上加以完善 设计了转账的功能 并能实现多个用户使用ＡＴＭ机 客户的人数可以任意设定 每个客户可以退出自己的操作 选择５就行 如果３次密码错误 就退出系统并关机 别人也不能用
在转账时要输入转账号 输入两次 第二次是确认 本想像真正ＡＴＭ系统一样
12
转账时输入他人账号设定时间 规定时间内输入账号 但对于Ｃ＋＋的ｓｅｔｔｉｍｅｒ函数不是很会。 另外我会继续改进功能，例如设置时间，并设计银行内部人员的类，可以去增加客户的人数，从而客户可以注册办里银行卡。 最后希望可以用ＭＦＣ写成可视化界面 。
五、图形界面1---------hello
5.1 需求分析……………………………………………………………………… .26
5.2 概要设计………………………………………………………………………..26
5.3 详细设计与编码………………………………………………………………..28
5.4 调试分析………………………………………………………………………...28
5.5 用户使用说明 ………………………………………………………………….29
5.6 设计心得………………………………………………………………………...29
class CEmployeeDialog : public CDialog
{
// Construction
public:
CEmployeeDialog(CWnd* pParent = NULL); // standard constructor
// Dialog Data
//{{AFX_DATA(CEmployeeDialog)
enum { IDD = IDD_EMPLOYEE };
UINT m_nAge;
BOOL m_bMarry;
CString m_strName;
int m_nSex;
int m_nState;
//}}AFX_DATA
// Overrides
// ClassWizard generated virtual function overrides
//{{AFX_VIRTUAL(CEmployeeDialog)
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support
//}}AFX_VIRTUAL
// Implementation
protected:
// Generated message map functions
13
//{{AFX_MSG(CEmployeeDialog)
virtual BOOL OnInitDialog();
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};
//{{AFX_INSERT_LOCATION}}
// Microsoft Visual C++ will insert additional declarations immediately before the previous line.
#endif
// !defined(AFX_EMPLOYEEDIALOG_H__F777BD94_4617_47A1_8FD5_FE68B560D4DF__INCLUDED_)
我主要是根据视频教材，做到了对话框。如上 我写了CEmployeeDialog类 作为 ＣDialog的子类。
六、数据结构2------删除结点p 的前趋结点（数据结构2.cpp）
6.1 需求分析…………………………………………………………………………30
6.2 概要设计………………………………………………………………………...30
6.3 详细设计与编码………………………………………………………………...34
6.4 调试分析………………………………………………………………………...35
6.5 用户使用说明 ………………………………………………………………….35
6.6 设计心得………………………………………………………………………...35
七、数据结构4--------统计选票(数据结构3.cpp)
7.需求分析………………………………………………………..………….……36
7.概要设计………………………………………………………………………...37
7.详细设计与编码………………………………………………………………...39
7.调试分析………………………………………………………………………...41
7.用户使用说明 ………………………………………………………………….41
7.设计心得………………………………………………………………………...41
八、课程设计总结 ……………………………………………………………… 42
14
15