数据结构课程设计范文样本.doc

资料内容仅供您学习参考，如有不当之处，请联系改正或者删除。

- 第二学期
《数据结构》课程设计

题目1: 大数相乘
题目2: 马的遍历

学 院: 计算机学院
姓 名: 陈 浩
学 号:
班 级: 软件091班
评阅教师: 汤亚玲

6月9日

安徽工业大学

一、 目　　的
加深对《数据结构》课程所学知识的理解, 进一步巩固C语言语法规则。学会编制结构清晰、 风格良好、 数据结构适当的Ｃ语言程序, 从而具备解决综合性实际问题的能力。

题目一: 大数相乘

目录:

系统功能分析……………………………………………………………………………3

基本要求……………………………………………………………………………..…3

功能需求…………………………………………………………………………..……3

开发工具……………………………………………………………………………… 3

程序说明…………………………………………………………………………….…3

大数相乘总括…………………………………………………………………… ……4

源程序………………………………………………………………………………………4

测试与结论……………………………………………………………………… ………5

创新及难点……………………………..………………………….………………………6

程序设计总结心得体会……………………………………………………………………6

-6-9

正文内容如下:
一、 系统功能分析
功能分析: 大数相乘能够实现对两个任意大的正数相乘。
用户能够经过本程序对无法实现的两数进行相乘, 其意在方便用户, 方便群众。

二、 1编写基本目的要求:
分析程序开发过程的具体问题, 构架程序的功能, 同时使该程序的使用者对本程序有一定的了解, 为实现功能的编码做好基础, 对数据结构有一个更深入的了解。

1、 背景:
a.开发的软件系统的名称: 大数相乘。
b.本项目的任务提出者 汤亚玲; 开发者: 陈浩。

2、 功能需求:
根据大数相乘的实际需求, 分析系统应该设计的功能, 其中应该包括对于超过整型大数的输入, 存储, 运算, 输出。实现乘法的一般功能。

3、 数据需求:

运行环境及知识要求:
运行环境要求: windows xp/visita/7
知识要求:
① 熟悉vc++6.0编译系统
② 熟悉AISCC
③ 熟练掌握字符与数字之间的转换

4﹑分析及实现简介:

由于大数相乘问题相对简单, 我只写了一个主函数实现了其功能。大数用字符数组存储, 用AISCC数字之间转换进行运算。

二、 程序的说明:
首先定义两个字符数组存储两个大数, 在定义两个数组, 一个用与保存结果, 另一个为辅助只用, 具体的思想是a b 两个大数 用b的个位一次乘a的每一位结果保存在辅助数组temp中, 在进位取余得到正常的10进制数, 用sum数组的temp的求和, 用flag标记, 以便temp的错位相加。用while能够控制大数运行的次数。

三、 模块分析及源程序:
/////////////////////////////////////////////////////////////////////
/* 大数相乘问题 */
////////////////////////////////////////////////////////////////////
#include<stdio.h>
#include<string.h>
#define MAX 10000
int main()
{
int n,i,j,t,s;
char a[100],b[100],temp[105]={0},sum[MAX]={0}; /*定义两个字符数组a, b用来存储大数 temp为辅助*/
int lena,lenb,flag,m=0;
printf("输入运算的次数n:\n");
scanf("%d",&n); /*输入运算的次数n*/

while(n--)
{ m++;
flag=0; /*设置标志flag*/
printf("输入将要运算的两数a, b; 用回车键相分隔\n");
scanf("%s%s",a,b); /*输入两要相乘的大数用回车键相分隔*/
lena=strlen(a);
lenb=strlen(b); /*求两数的长度*/
for(j=lenb-1;j>=0;j--)
{
for(t=lena,i=lena-1;i>=0;i--,t--)
{
temp[t]=(a[i]-48)*(b[j]-48); /*依次从低位开始求的b的某一位与a的乘积*/
}
for(t=lena;t>=1;t--)
{
if(temp[t]>9)
{
temp[t-1]+=temp[t]/10;
temp[t]%=10; /* 进位取余*/
}
}
for(s=lena+lenb-flag,t=lena;t>=0;t--,s--) /*标志flag确保错位相加*/
sum[s]+=temp[t];
for(t=lena;t>=0;t--)
temp[t]=0; /*辅助数组复位志零*/
for(s=lena+lenb;s>=1;s--)
{
if(sum[s]>9)
{
sum[s-1]+=sum[s]/10;
sum[s]%=10; /* s 进位取余*/
}
}
flag++;
}
sum[lena+lenb+1]='\0';
for(s=0;s<=lena+lenb;s++)
sum[s]=sum[s]+48; /* 数值还原, 48对应‘0’字符*/
for(s=0;s<lena+lenb;s++)
if(sum[0]==48)
{
for(t=0;t<=lena+lenb-s;t++)
sum[t]=sum[t+1]; /* 高位有零向前移位, 防止输出的数第一位为零*/
}
else break;

printf("Case %d:\n",m); //输出结果;
printf("%s * %s = %s\n",a,b,sum);
if(n!=0)
printf("\n");
for(s=lena+lenb+1;s>=0;s--) /*sum字符数组复位志零等待下一轮while循环*/
sum[s]=0;
}

return 0;
}

测试与结论:
进过我的重复测试, 只要是两个正整数相乘结果正确, 程序稳定性好, 能够运算任意大是数。

运行结果抓图如: ”

四、 创新及难点:
1、 创新:
①只有一个主函数, while循环实现大数相乘, 使得程序简短高效。
②使用temp辅助字符数组, 降低了运算是难度, 程序清晰易懂。
③系统在操作提示上较多, 用户与系统间的信息交互比较方便, 便于操作。
2、 难点:
①要用一个大数的各个位去乘一个大数并把的到的数反向存储且使得数字每一位不大于9。
②因为相乘每一位权重不一样, 要错位相加。得数求余, 变换。

四、 心得体会:
经过为一学期的数据结构课程设计实验课使我了解到了一个程序开发的过程, 虽然规模不大, 但为我以后的编程学习打下了基础。在编程的过程中, 我体会到了学习编程的辛苦, 为了一个算法的实现而思考, 为了一个小小的编译错误而花时间去寻找, 这需要很大的毅力和耐心, 而且要有良好的思维, 这才使得我完成这个任务, 也使我感到一分喜悦, 毕竟自己完成了一个有模有样的程序。于此, 我也发现自己的一些不足, 良好的编程习惯的养成, 坚定的毅力和耐心仍是我要加强的, 同别人的交流也是必须的, 这样才能不断使我进步。

题目二: 马的遍历

目录:

流程图: ………………………………………………………… 8

系统功能分析………………………………………………………9

基本要求……………………………………………………………9

程序说明………………………………………………………….…9

创立标志矩阵函数模块……………………………………………9

巡游子函数模块………………………………………………….…9

赋值子函数模块……………………………………………….…11

主程序函数模块……………………………………………………11

测试运行与结论………………………………………… ………12

程序设计总结心得体会……………………………………………13

流程图
开始
输入入口的棋盘大小
横坐标在1—8之间
输入入口点纵坐标
纵坐标在1—8之间
显示马的遍历路径
结束

系统功能分析:
问题描述: 设计一个国际象棋上的马的遍历棋盘的演示过程的程序。

基本要求: 将马任意放在国际棋盘的8x8的棋盘board[8][8]的某个方格内, 马按走棋规则进行移动。要求每个方格只进入一次, 走遍棋盘上的全部64个方格。编制程序, 求出马的行走路线, 并按求出的行走路线, 将数字1, 2, 。。。64依次填入一个8x8的方阵, 输出之。

程序说明:
首先, 国际象棋是8*8的棋盘, 马的走法是”马走日”, 忽略”蹩脚马”的情况。
其次, 这个题目采用的是递归, 算法当中的深度优先算法和回溯法: 在”走到”一个位置后要寻找下一个位置, 如果发生”阻塞”的情况, 就是后面走不通的情况, 则向后回溯, 重新寻找。在寻找下一步的时候, 对周围的这几个点进行比较, 从而分出优劣程度, 即看它们周围能够走的点谁最少, 然后就走那条可走路线最少的那条。经过这样的筛选后, 就会为后面的路径寻找提供方便, 从而减少回溯次数。
最后, 本程序的棋盘和数组类似, 因而采用数组进行存储, 同时还有八个方向的数组, 和为栈设计的每个点周围的八个方向那些能够走的数组。

数据初始定义如下:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
/* 马 的 变 遍 历 问 题 */
/////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
int f[11][11] ; /*定义一个矩阵来模拟棋盘*/
int adjm[121][121]; /*标志矩阵, 即对于上述棋盘, 依次进行编号
1--121(行优先) 能够从一个棋盘格i跳到棋盘格j时, adjm[i][j]=1*/

void creatadjm(void); /*创立标志矩阵函数声明*/
void mark(int,int,int,int); /*将标志矩阵相应位置置1*/
void travel(int,int); /*巡游函数声明*/
int n,m; /*定义矩阵大小及标志矩阵的大小*/

创立标志矩阵子函数:
/********************创立标志矩阵子函数*************************/
void creatadjm()
{
int i,j;
for(i=1;i<=n;i++) /*遍历矩阵初始化*/
for(j=1;j<=n;j++)
f[i][j]=0;
for(i=1;i<=m;i++) /*标志矩阵初始化*/
for(j=1;j<=m;j++)
adjm[i][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j]==0) /*对所有符合条件的标志矩阵种元素置1*/
{
f[i][j]=1;
if((i+2<=n)&&(j+1<=n)) mark(i,j,i+2,j+1);
if((i+2<=n)&&(j-1>=1)) mark(i,j,i+2,j-1);
if((i-2>=1)&&(j+1<=n)) mark(i,j,i-2,j+1);
if((i-2>=1)&&(j-1>=1)) mark(i,j,i-2,j-1);
if((j+2<=n)&&(i+1<=n)) mark(i,j,i+1,j+2);
if((j+2<=n)&&(i-1>=1)) mark(i,j,i-1,j+2);
if((j-2>=1)&&(i+1<=n)) mark(i,j,i+1,j-2);
if((j-2>=1)&&(i-1>=1)) mark(i,j,i-1,j-2);
}
return;
}

巡游子函数: 、
/***************************巡游子函数*****************************/
void travel(int p,int r)
{
int i,j,q;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j]>r) f[i][j]=0; /*棋盘矩阵的置〉r时, 置0*/
r=r+1; /*跳步计数加1*/
i=((p-1)/n)+1; /*还原棋盘矩阵的横坐标*/
j=((p-1)%n)+1; /*还原棋盘矩阵的纵坐标*/
f[i][j]=r; /*将f[i][j]做为第r跳步的目的地*/

for(q=1;q<=m;q++) /*从所有可能的情况出发, 开始进行试探式巡游*/
{
i=((q-1)/n)+1;
j=((q-1)%n)+1;
if((adjm[p][q]==1)&&(f[i][j]==0))
travel(q,r); /*递归调用自身*/
}
return;
}

赋值子函数
/******************赋值子函数**********************************/
void mark(int i1,int j1,int i2,int j2)
{
adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;
adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;
return;
}

主函数: void main()
提示输入起点位置, 这里的起点位置就是日常生活观念中的顺序, 开始点是(1,1),而不是数组中的初始位置(0,0),输入错误则无效, 时间复杂度为。

/**************************主函数***************************/
int main()
{
int i,j,k,l;
printf("Please input size of the chessboard: "); /*输入矩阵的大小值*/
scanf("%d",&n);
m=n*n;
creatadjm(); /*创立标志矩阵*/
puts("The sign matrix is:");
for(i=1;i<=m;i++) /*打印输出标志矩阵*/
{
for(j=1;j<=m;j++)
printf("%2d",adjm[i][j]);
printf("\n");
}

printf("Please input the knight's position (i,j): "); /*输入骑士的初始位置*/
scanf("%d %d",&i,&j);
l=(i-1)*n+j; /*骑士当前位置对应的标志矩阵的横坐标*/
while ((i>0)||(j>0)) /*对骑士位置的判断*/
{
for(i=1;i<=n;i++) /*棋盘矩阵初始化*/
for(j=1;j<=n;j++)
f[i][j]=0;
k=0; /*所跳步数计数*/
travel(l,k); /*从i,j出发开始巡游*/
puts("The travel steps are:");
for(i=1;i<=n;i++) /*巡游完成后输出巡游过程*/
{
for(j=1;j<=n;j++)
printf("%4d",f[i][j]);
printf("\n");
}

printf("Please input the knight's position (i,j): ");/*为再次巡游输入起始位置*/
scanf("%d %d",&i,&j);
l=(i-1)*n+j;
}
puts("\n Press any key to quit... "); /*输入( 0, 0) 作为结束标准*/
getch();
return 0;
}

运行与测试:
程序运行开始时, 提示用户输入棋盘大小, 再次输入, 提示输入横纵坐标, 用回车键分隔。出现结果, 显示坐标形式; 提示可重新输入, 输入0 0表示结束标志。
运行结果举例:

心得体会:
从这学期的数据结构课程设计上机实践中, 让我体会到上机的重要性。编写和开发程序, 离不开上机, 马的遍历一段不懂的代码只有经过重复的研读与调试, 才能弄懂, 最终变成自己的代码。一周的学习, 让我学会一些知识, 不在于学到了那么点技术, 而在于心理得到了洗礼! 在此, 我不说老师的功劳, 也不提以前怎么怎么没好好听讲, 没好好复习, 没好好珍惜上机的机会。最终我确实得到了锻炼, 这就足够了! 对于接下来的路程, 脚踏实地, 勤奋努力比什么都重要; 代码是枯燥的, 但不枯燥的是学习的过程, 难得的是学习过程中体会的快乐, 有目标的学习与坚持, 生活才会更加美好!

Made by chenhao in AnHui University of Technology /06/09