数据结构专业课程设计范文.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