任意长整数的乘法数据结构课程设计报告样本.doc

课 程 设 计 任 务 书

专 业
计算机科学与技术( 专升本)
班 级

姓 名

设 计 起 止 日 期

设计题目: 任意长整数的乘法
设计任务( 主要技术参数) :
数据结构课程设计要求结合《数据结构( C语言版) 》课程所学的基础知识进行程序设计, 并实现下列目标:
1. 经过课堂讲解和学习研究, 查阅和收集C语言程序设计的相关资料;
2. 进行方案的选择、 分析与设计;
3. 对程序进行上机调试;
4. 写出设计体会;
5. 撰写数据结构课程设计报告。报告力求做到观点正确、 方法科学、 技术先进。 
硬件环境: CPU:  酷睿i5-2430    内存: 6G  硬盘: 750G 
软件环境: 操作系统: win7
程序开发环境: VC++6.0
指导教师评语:

成绩:     签字:
年   月   日
课程设计说明书 NO.1
 任意长整数的乘法
1、 课程设计目的
( 1) 较熟练地掌握数据结构( C语言) 课程的基本内容, 程序设计的基本方法与编程技巧。
( 2) 较熟练地掌握C语言程序编辑、 编译、 连接和运行的方法。
( 3) 经过运行C程序, 了解C语言的特点, 培养学生应用计算机解决和处理实际问题的思维方法与基本能力。
2、 课程设计方案论证
2.1  设计思路
( 1) 输入的形式和输入值的范围:
用户从键盘输入2个任意长度的长整数, 输入的时候是按4个为一段输入的, 即一段一段输入的, 求它们的乘积的大小, 并将结果在屏幕上显示; 2个长整数的输入没有大小的限制, 要输入多大的数据,就能够输入多大的数据。
( 2) 输出的形式:
输出直接在屏幕上显示2个任意长度的长整数的乘积大小。
( 3) 程序所能达到的功能:
对于用户输入的任意长度的2个的长整数, 能够正确没有错误的显示结果, 和电脑附件中的计算器的计算值要一致; 能够准确无误地显示结果。
( 4) 测试数据:
如输入1000 1000 和1111 2个长整数后, 显示0111 1111 1111 1000的话, 就是正确的结果形式。
如输入1111 1111 1111和1111 2个长整数后, 结果显示0123 4444 4444 4322就不是正确结果, 因为这2个长整数的积为0123 4444 4444 4321
2.2概要设计
( 1) 抽象数据类型的定义
为了实现任意长整数的乘法, 因为这种运算存在进位和位移等操作, 因此选择双链表的结构体( 如图2.2.1和图2.2.2) , 它有一个data, left, right; 考虑到data表示的数据的范围, 使它只接受4个数字的整数, 这样一个长整数就分为若干段, 每一段为4个数
沈 阳 大 学
课程设计说明书 NO2
字, 便于进位和借位以及位移的操作, 用户在输入时就是每次输入4个数字。
( 2) 主程序的流程
主程序是首先调用初始化2个长整数的函数, 用户4个数字一段一段地输入2个长整数, 用双链表的形式和头插法的形式建立, 返回2个长整数的头节点; 建立完2个长整数后,就开始进行2个长整数的乘积的运算了;
首先将第一个长整数的全部去乘第2个长整数的最后一段, 这样得到一个长整数; 接着将第一个长整数的全部去乘第2个长整数的倒数第2段; 这样得到一个长整数, 可是要向左位移4位; 这次得到的长整数要和上一次相加, 得到一个新的长整数; 接着接着将第一个长整数的全部去乘第2个长整数的倒数第3段, 得到一个长整数, 再和前面相加;
依次进行, 一直到已经到第一个长整数的全部乘于了第2个长整数的最高1段,
那么乘法就结束了; 这时将得到的长整数从高位到低位一段一段, 4个4个数字显示在屏幕上, 程序就运行结束了。
( 3) 模块之间的层次(调用)关系
程序的调用关系如下: 主函数调用了初始化2个长整数的函数, 然后再调用了2个2个长整数的乘积的函数; 2个长整数的乘积的函数调用了部分求和的函数和从表头得到表尾的函数, 以及将一个长整数前后数值交换的函数以及显示一个长整数的函数。

图1双链表的数据结构

图2双链表的数据结构( 虚线部分为地址值, 这个是为了描述方便随便写的值)

沈 阳 大 学
课程设计说明书 NO.3
2.3详细设计
( 1) 2个长整数的输入
接着采用头插法的方式, 当输入一个 4个数字的整数时, 就产生一个新的节点, 它的值为输入的整数值, 建立起它的左右指针, 并用头节点指向它; 为了判断一个长整数是否输入结束, 定义一个结束标志, 当输入正数时就继续, 当输入负数时, 就结束一个长整数的输入; 同时用一个函数得到长整数的尾节点和段数, 段数在比较2个数的大小有用。
( 2) 2个长整数的乘法
先定义一个部分加法的函数, 就是2个正的长整数的加法的运算; 它从2个长整数的尾部开始, 同时相加, 接着再向左移一段, 又同时相加; 当2个数据的某一段同时存在时, 就相加; 当一个数据已经全部被相加后, 另外一个数据的剩下的段就要全部复制到和中; 在实行加法的时候, 设置一个进位标志位, 目的是为了使结果正确; 当一 段的数据相加产生进位时, 那么进位标志位为1; 下一次一段的数据相加就要加上这个进位标志位; 而且如果2个长整数的所有的段的数据都相加完了, 还要判断是否产生了进位标志位, 如果有的话, 就要新建一个节点, 它的值就是1; 2个正的长整数的求和就完成了。
再定义一个部分乘法的函数, 就是1个正的长整数乘于一个4位整数, 并向左位移特定的段数的运算; 其实开始实现向左位移的运算, 只需要建立新的节点, 节点的数目为需要左移段数, 并将这些节点的值设置为0; 接着实现一个长整数乘于一个4位整数的运算, 采用每一段都和这个4位整数的相乘的方法, 当积超过10000时, 那么多于高4位全为进位, 参与下一次相乘时要加上它; 低4位就是要新建的节点的值; 和加法一样, 当这个正的长整数的每一段都和这个4位整数相乘后, 但还存在进位时, 就要新建一个节点, 它的值就是进位值; 现在1个正的长整数乘于一个4位整数, 并向左位移特定的段数的运算就完成了;
再实现2个正的长整数的乘法的运算, 采用第一个长整数作为一个整体乘于第二个长整数的每一段, 并向左位移的方法; 例如当采用第一个长整数作为一个整体乘于第二个长整数的最后一段, 就不用向左位移; 可是第一个长整数作为一个整体乘于第二个

沈 阳 大 学
课程设计说明书 NO.4
长整数的倒数第二段, 就用向左位移一段, 就是最后一段为0, 依次类推; 此过程是调用部分乘法的函数实现的; 我们只需要定义2个长整数的临时变量, 1个是本次新产生的部分乘法的结果, 1个是上次的总和; 那么总和加上本次新产生的部分乘法的结果重新给总和, 此操作是调用2个长整数的加法实现的; 第2个数的段一直向左位移, 总和也就不断扩大, 当第2个数的段达到最高一段时, 就完成了2个正的长整数的乘法的运算。
( 3) 补充说明
在程序中, 因为我们需要得到一个长整数的头部和尾部, 因此定义了2个函数, 一个是已知一个一长整数的头部, 得到它的尾部; 一个是已知一个一长整数的尾部, 得到它的头部; 具体实现都是利用指针的左移和右移, 为空时就得到头部或尾部;
在程序中, 我们输入是从高位到低位输入的, 而相加后的顺序就相反了, 因此我们需要定义一个将一个长整数的数据前后交换的函数, 新建一个一个长整数, 使用头插法, 将从原来一个长整数的尾部开始, 向左移, 一个一个给新建的长整数。
2.4  源程序清单
#include<stdio.h>
#include<malloc.h>
typedef struct linknode
{int data;/*节点的值*/
struct linknode *left,*right;
/*左指针和右指针*/
}dnode;
dnode *r1,*r2,*r3,*head1,*head2,*head3;
dnode *head_temp,*rear_temp;
/*head1为第1个数的头指针, r1为 为第1个的尾指针*/
/*head2为第2个数的头指针, r2为 为第2个的尾指针*/
/*head3为结果的头指针, r3为结果的尾指针*/
/*head_temp为临时数的头指针, rear_temp为临时数的尾指针*/
/*产生一个长整数*/
dnode* creat()
{dnode *head,*p,*s;
/*head为头指针, p和s为临时指针*/
int x,cycle=1;
/*x为输入的数据, cycle为是否继续输入的标志*/
head=(dnode*)malloc(sizeof(dnode));

沈 阳 大 学
课程设计说明书 NO.5
p=head;
/*指向头*/
while(cycle)
{scanf("%d",&x);
/*输入数据*/
if(x>=0)/*输入正数才有效*/
{s=(dnode*)malloc(sizeof(dnode));
s->data=x;
p->right=s;
s->left=p;
p=s;
/*采用的是头插法*/
}
else cycle=0;
/*输入负数就退出*/
}
head=head->right;
/*第一个头没有用到*/
head->left=NULL;
p->right=NULL;
return head;
}
dnode *rear(dnode *head)
/*根据一个数的头节点, 得到尾节点, 并得到这个数的段数*/
{dnode *p;
p=head;
while(p->right)
/*向右移*/
　　p=p->right;
return p;
}
void input_and_init()
/*初始化2个数据的大小*/
{
/*符号变为对应的0或1*/
printf("input the first data,input negative data exit\n");
head1=creat();
/*产生第一个数, 得到它的头指针*/
r1=rear(head1);
/*得到第一个数的尾指针和*/

沈 阳 大 学
课程设计说明书 NO.6
/*符号变为对应的0或1*/
printf("input the second data,input negative data exit\n");
head2=creat();
/*产生第2个数, 得到它的头指针*/
r2=rear(head2);
/*得到第一个数的尾指针和段数*/
}
/*打印一个数*/
void print(int data)
{if(data>=1000)
/*含有4个数字*/
printf("%d",data);
else if(data>=100)
/*含有3个数字, 补1个零*/
printf("0%d",data);
else if(data>=10)
/*含有2个数字, 补2个零*/
printf("00%d",data);
else
/*含有1个数字, 补3个零*/
printf("000%d",data);
}
/*显示一个结果的长整数, 从后向前移*/
void display(dnode *rear)
{dnode *p;
p=rear;
while(p)
{print(p->data);
printf(" ");
p=p->left;
/*向左移*/
}
printf("\n");
}
dnode *find_sum2(dnode *r1,dnode *r2)
/*得到2个正数的和*/
{dnode *head,*p,*s,*p1,*p2;
/*head为头指针, p,s为临时指针, p1指向第1个数并向左移动, p2指向第2个数并并向左移动*/
int inc=0,sum=0,f1=0,f2=0;
/*inc为进位, sum为和, f1为第一个数是否结束, f2为第一个数是否结束*/
head=(dnode*)malloc(sizeof(dnode));

沈 阳 大 学
课程设计说明书 NO.7
p=head;
/*开辟空间*/
p1=r1;/*指向第一个数的尾*/
p2=r2;/*指向第二个数的尾*/
while(p1!=NULL&&p2!=NULL)
/*2个数的某一段都不为空时 */
{sum=p1->data+p2->data+inc;
/*和为2个数之和加进位*/
inc=0;
/* 进位回0*/
if(sum>=10000)
/*当超过2位数的大小时, 和减去10000, 并进位*/
{sum=sum-10000;
inc=1;
}
/*用头插法建立一个新的节点*/
s=(dnode*)malloc(sizeof(dnode));
s->data=sum;
p->right=s;
s->left=p;
p=s;
/*2个数都向左移*/
p1=p1->left;
p2=p2->left;
}
if(p1==NULL&&p2==NULL)
if(inc==1)
/*当2个数据都完了, 可是存在进位时, 新建一个节点, 值就是进位*/
{s=(dnode*)malloc(sizeof(dnode));
s->data=1;
p->right=s;
s->left=p;
p=s;
}
while(p1!=NULL)
/*当第2个数空, 第1个数不为空时, 将第一个数剩下的全用新节点产生*/
{f1=1;
s=(dnode*)malloc(sizeof(dnode));
sum=p1->data+inc;
inc=0;
if(sum>=10000)

沈 阳 大 学
课程设计说明书 NO.8
{sum=sum-10000;
inc=1;
}
s->data=sum;
p->right=s;
s->left=p;
p=s;
/*第1个数都向左移*/
p1=p1->left;
}
/*当第1个数据完了, 可是存在进位时, 新建一个节点, 值就是进位*/
if(f1==1&&inc==1&&!p1)
{
s=(dnode*)malloc(sizeof(dnode));
s->data=1;
p->right=s;
s->left=p;
p=s;
}
/*当第1个数空, 第2个数不为空时, 将第一个数剩下的全用新节点产生*/
while(p2!=NULL)
{f2=1;
s=(dnode*)malloc(sizeof(dnode));
sum=p2->data+inc;
inc=0;
if(sum>=10000)
{sum=sum-10000;
inc=1;
}
s->data=sum;
p->right=s;
s->left=p;
p=s;
p2=p2->left;
/*第2个数都向左移*/
}
/*当第2个数据完了, 可是存在进位时, 新建一个节点, 值就是进位*/
if(f2==1&&inc==1)
{s=(dnode*)malloc(sizeof(dnode));
s->data=1;
p->right=s;
s->left=p;
沈 阳 大 学
课程设计说明书 NO.9
p=s;
}
head=head->right;
head->left=NULL;
p->right=NULL;
return head;
/*返回头节点*/
}
dnode * find_sub_mult(dnode * r1,int data ,int i)
/*将r1指向的数全乘于data, 并向左位移i段*/
{dnode *head,*p,*s,*rr;
/*head为头指针, p,s为临时指针, rr为尾指针*/
int k,inc=0;
/*k为循环用的, inc为进位*/
long sum=0;
/*求和*/
rr=r1;
head=(dnode*)malloc(sizeof(dnode));
p=head;
/*开辟空间*/
/*先将需要位移的段数全用0补齐*/
if(i!=0)
{for(k=1;k<=i;k++)
{
s=(dnode*)malloc(sizeof(dnode));
s->data=0;
p->right=s;
s->left=p;
p=s;
}
}
while(rr!=NULL)
/* 当rr没有到头时*/
{s=(dnode*)malloc(sizeof(dnode));
sum=rr->data*data+inc;
if(sum>10000)
{inc=sum/10000;
/*得到和的高4位*/
s->data=sum-inc*10000;
/*值为低4位的值*/
}

沈 阳 大 学
课程设计说明书 NO.10
else
{s->data=sum;
/*直接给值*/
inc=0;
}
p->right=s;
s->left=p;
p=s;
/*左移*/
rr=rr->left;
}
if(inc!=0)
/*如果还有进位, 就需要新建一个节点*/
{
s=(dnode*)malloc(sizeof(dnode));
s->data=inc;
p->right=s;
s->left=p;
p=s;
}
head=head->right;
head->left=NULL;
p->right=NULL;
/*返回头指针*/
return head;
}
/*由一个数的尾指针得到头指针*/
dnode * return_head(dnode *rear)
{
dnode *p;
p=rear;
while(p->left)
p=p->left;
return p;
}
/*由一个数的头指针得到尾指针*/
dnode * return_rear(dnode *head)
{
dnode *p;
p=head;
while(p->right)

沈 阳 大 学
课程设计说明书 NO.11
p=p->right;
return p;
}
/*将一个数的数据前后交换*/
dnode * tansfer_rear2(dnode *rear_temp)
{dnode *head,*p,*s,*rear;
rear=rear_temp;
head=(dnode*)malloc(sizeof(dnode));
p=head;
while(rear!=NULL)
/*将后面的节点向左一个一个用头插法建立, 就和原来相反了*/
{s=(dnode*)malloc(sizeof(dnode));
s->data=rear->data;
p->right=s;
s->left=p;
p=s;
rear=rear->left;
}
head=head->right;
head->left=NULL;
p->right=NULL;
return p;
}
/*2个数相乘, 将第1个数乘于第2个数的每一段, 要进行响应的移位处理, 得到一系列的数, 再相加*/
void multy(dnode *r1,dnode *r2)
{dnode * p;int i=0,flag=0;
p=r2;
while(p!=NULL)
{head_temp=find_sub_mult(r1,p->data,i);
/*将r1中所有的数乘于p->data, 并向左位移i段*/
rear_temp=return_rear(head_temp);
/*得到尾*/
rear_temp=tansfer_rear2(rear_temp);
/*求反*/
if(flag==0)
/*如果是第一个段, 直接给r3*/
{r3=rear_temp;
flag=1;
}
Else

沈 阳 大 学
课程设计说明书 NO.12
{
/*如果不是第一个段, 将r3和当前的结果相加*/
head3=find_sum2(r3,rear_temp);
r3=return_rear(head3);
r3=tansfer_rear2(r3);
}
i++;
/*需要位移的段数增加*/
/*p左移*/
p=p->left;
}
r3=tansfer_rear2(r3);
/*交换*/
display(r3);
/*显示最后结果*/
}
void main()
{
input_and_init();
multy(r1,r2);
getchar();
}

沈 阳 大 学
课程设计说明书 NO.13
3、 课程设计运行结果与分析
3.1用户使用说明
本程序使用简单,运行程序后出现了input the first data,input negative data exit的提示,告诉用户输入第一个长整数,4个数字一段输入,要想结束输入直接输入一个负数就能够结束了;如需要输入1011 1011时;
input the first data,input negative data exit
1011
1011
-1
接着出现input the second data,input negative data exit的提示,告诉用户输入第2个长整数,4个数字一段输入,要想结束输入直接输入一个负数就能够结束了;如需要输入1011 1011时;
input the second data,input negative data exit
1011
1011
-1
0102 2325 4344 2121
输入完以后,程序直接显示运行结果,按回车就退出程序。运行结果如图:

图2 运行结果

沈 阳 大 学
课程设计说明书 NO.14
3.2算法的时空分析
时间复杂度: 由于2个长整数的乘法是用第一个长整数的全部乘于了第2个长整数的每一段然后想加得到的, 因此它实际上就是2重循环的作用, 假设2个数的段数分别为n1和n2, 那么算法的时间复杂度为n1和n2的乘积;
空间复杂度: 空间复杂度是和2个长整数的段数成正比, 2个长整数的段数越多,那么需要开辟的空间越多,求和需要的长整数的开辟的空间也越多。

沈 阳 大 学
课程设计说明书 NO.15
4、 课程设计体会
在写程序中要规范书写, 这样便于检查错误的出现所在的地方; 写代码要前后照应, 前面的变量和函数在后面使用时可能要对应, 如果不注意, 可能发生错误; 当出现错误时, 要大胆猜测各种出错的可能的原因, 一种一种排除, 一种一种尝试, 问题可能解决。定义了指针就需要开辟空间, 否则会出错; 同时指针开辟的空间单元要初始一定的值, 否则会出现不需要的数据。
5、 参考文献
[1] 赵梦龙.数据结构在通讯录管理系统设计中的应用[M].数字技术与应用. .05:300-325
[2] 汪博.面向手机终端的数据备份系统的研究与实现[M].中南大学, .06:45-50
[3] 杨猛.学习迁移理论在数据结构课程设计中的应用及探索[M].计算机教育. .03:90-110
[4] 吴鹏.计算思维驱动的数据结构实践教学改革[J].福建电脑. .08:4-10
[5] 张淑娴.基于形象关联模式通讯录的设计与实现[J].无锡学报. .07:86-80
[6] 焦阳.具有身份验证和灾备功能的高效数据同步模型[D].南京邮电大学, .12:67-70
[7] 刘宁.手机通讯录云备份的安全处理[D].河北科技大学, .10:89-92

沈 阳 大 学