数据结构课设报告 - 长整型的加法运算

课程设计(论文)任务书

软 件 学 院 学 院 专 业 班

一、课程设计(论文)题目 长整数的加法运算 二、课程设计(论文)工作自 2011 年 12 月 26 日起至 2011 年 12 月 30 日止

三、课程设计(论文) 地点: 四、课程设计(论文)内容要求： 1．本课程设计的目的

⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，

编写程序求解指定问题；

⑵初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生

的理论知识，提升编程水平。 2．课程设计的任务及要求 1）基本要求：

⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象

数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告； ⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率； ⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释； ⑷每位同学需提交可独立运行的程序和规范的课程设计报告。 2）课程设计论文编写要求

⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进

行书写和装订；

⑵课程设计报告（论文）包括中文目录、设计任务、需求分析、概要设计、详细设计、

编码实现、调试分析、课设总结、谢辞、参考文献、附录等；

1

目录

1.设计任务 .......................................................................................... 3 2.功能需求分析 .................................................................................. 3 3.功能算法设计 .................................................................................. 4 4.编码实现 .......................................................................................... 5 5.程序的调试与结果 .......................................................................... 8 5课设小结 .......................................................................................... 9 6参考文献 .......................................................................................... 9

2

1.设计任务

问题描述：

设计一个实现任意长的整数进行加法运算的演示程序。

基本要求： 1利用双向循环链表实现长整数的存储，每个结点含一个整型变量。 2任何整型变量的范围是-(2^15-1)~(2^15-1)。

3输入和输出形式按照中国对于长整数的表示习惯，每四位一组,组间用逗号隔开。 如：-2345，6789，3211；

2.功能需求分析

1.因为要实现任意长的整数进行加法运算，本程序使用C语言的整型变量int存放数据，一个int型的变量值的范围为-32768~32767，显然远远不能满足。因此利用双向循环链表实现长整数的存储，每个结点存放一个整型变量，且只存10进制数的4位，即不超过9999的非负整数，整个链表表示为万进制数。

表头数据域的符号代替长整数的符号。相加过程不破坏两个操作数链表。长整数位数没有上限。

2.演示程序以用户和计算机的对话方式执行，在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在后。 3.程序执行的命令包括：

1）构造链表1存放第一个输入数据 2）构造链表2存放第二个输入数据 3）求两数之和 4）结束 4.测试数据 ⑴0；0；应输出0

⑵-2345，6789；-7654，3211；应输出-1，0000，0000

⑶-9999，9999；1，0000，0000，0000；应输出9999，0000，0001

3

3.功能算法设计

ADT Lixt{

数据对象：D={ai∣ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={∣ai-1,ai∈D,i=2,…，n} 基本操作： InitList(&L)

操作结果：构造一个空的线性表 DestroyList(&)

初始条件：线性表L已存在 操作结果：销毁线性表L ClearList(L)

初始条件：线性表L已存在 操作结果：将L重置为空表 ListEmpty(L)

初始条件：线性表L已存在

操作结果：若L为空表，则返回TRUE,否则返回FALSE ListLength(L)

初始条件：线性表L已存在 操作结果：返回L中数据元素个数 GetElem(L,i.&e)

初始条件：线性表L已存在，1≤i≤ListLength(L) 操作结果：用e返回L中第i个数据元素的值 ListInsert(&L,I,e)

初始条件：线性表L已存在，1≤i≤ListLength(L)+1

操作结果：在L中第i个位置插入新的数据元素e，L的长度加1 ListDelete(&L,I,&e)

初始条件：线性表L已存在，且非空，1≤i≤ListLength(L) 操作结果：删除L的第i个元素，并且用e返回其值，L的长度减1 }ADT List

4

4.编码实现

1.节点的定义： typedef struct node {

int data; struct node *pre; struct node *next; }DataNode;

2.对于程序中数据的输入以及对输入数据检测，主要利用for和while循环语句对输入的数据进行检测和判断： DataNode* Input() {

char ch[50];

DataNode *temp,*node;

int count=0,count1=0,i,j,n,sum=0; scanf(\

while(ch[count++]!='\\0'); count--;

node=(DataNode*)malloc(sizeof(DataNode)); temp=node; count1++;

if(ch[0]=='-'||ch[0]=='+') {

if((count-1)%2)

count1+=(count-1)/2+1; else

count1+=(count-1)/2; } else

5

{ if(count%2)

count1+=count/2+1; else

count1+=count/2; }

count--;

for(i=1;i

temp->pre=(DataNode*)malloc(sizeof(DataNode)); temp->pre->next=temp; temp=temp->pre; temp->data=0;

for(j=0;j<2&&ch[count]!='-'&&ch[count]!='+';j++) {

if(count<0) break;

sum=ch[count--]-'0'; for(n=0;ndata+=sum; } }

temp->pre=node; node->next=temp; if(ch[0]=='-') count1=0-count1; node->data=count1; return node; }

6

3.对于数据的输出同样利用for和while循环，通过对条件的判定进行数据的输出。具体代码实现如下：

void Output(DataNode *node) {

int n,i; DataNode *temp; n=node->data; temp=node->next; if(n<0) {

printf(\ n=0-n; }

for(i=0;i

if((n-1-i)%2==0&&i!=0) printf(\ if(n==1) {

printf(\ break; } if(i==0)

printf(\ else if(i==n-2)

printf(\ else

printf(\ temp=temp->next; } }

7

3.在主函数main中，主要实现链表的定义，以及对于程序的输出提示做好输出，最后再通过switch语句根据条件的不同输出不同的提示语句。使程序变得更便于使用。

5.程序的调试与结果

进入演示程序后即显示如下用户界面（图）：

以上为主界面，只有简单的三个功能，只要输入每个选项前面的数字，后按回车运算。

8

5课设小结

感谢***老师，在*的的课堂上我学得到很多实用的知识，在此表示感谢！同时，对给过我帮助的所有同学和其他的老师再次表示衷心的感谢！

此次课程设计，感慨颇多，的确，自从拿到题目到完成整个编程，从理论到实践，在做课设的这些的日子里，可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体，指针……通过这次课程设计之后，我把前面所学过的知识又重新温故了一遍。

6参考文献

[1] 严蔚敏，吴伟民。数据结构（C语言版） 清华大学出版社 [2]数据结构教程（第三版）上级实验指导 清华大学出版社 [3]数据结构课程设计（c/c++语言描述） 附录：

#include #include #include #include

typedef struct node {

9

电子工业出版社

int data; struct node *pre; struct node *next; }DataNode; int CF;

DataNode* Input() {

char ch[50];

DataNode *temp,*node; int count=0,count1=0,i,j,n,sum=0; scanf(\ while(ch[count++]!='\\0'); count--;

node=(DataNode*)malloc(sizeof(DataNode)); temp=node; count1++;

if(ch[0]=='-'||ch[0]=='+') {

if((count-1)%2)

count1+=(count-1)/2+1; else

count1+=(count-1)/2; } else { if(count%2)

count1+=count/2+1; else

count1+=count/2;

10

}

count--;

for(i=1;i

temp->pre=(DataNode*)malloc(sizeof(DataNode)); temp->pre->next=temp; temp=temp->pre; temp->data=0;

for(j=0;j<2&&ch[count]!='-'&&ch[count]!='+';j++) {

if(count<0) break; sum=ch[count--]-'0'; for(n=0;ndata+=sum; } }

temp->pre=node; node->next=temp; if(ch[0]=='-') count1=0-count1; node->data=count1; return node; }

void Output(DataNode *node) {

int n,i;

DataNode *temp; n=node->data;

11

temp=node->next; if(n<0) {

printf(\ n=0-n; }

for(i=0;i

if((n-1-i)%2==0&&i!=0) printf(\ if(n==1) {

printf(\ break; } if(i==0)

printf(\ else if(i==n-2)

printf(\ else

printf(\ temp=temp->next; } }

int test(DataNode *node1,DataNode *node2) {

DataNode *temp1,*temp2; int i,count; temp1=node1; temp2=node2;

if(abs(temp1->data)>abs(temp2->data))

12

return 1;

else if(abs(temp1->data)data)) return 2; else {

count=abs(temp1->data); for(i=1;i

temp1=temp1->next; temp2=temp2->next;

if((temp1->data)>(temp2->data)) return 1;

if((temp1->data)>(temp2->data)) return 2;

if((temp1->data)==(temp2->data)) if(i==count-1) return 0; } } }

DataNode* add(DataNode *node1,DataNode *node2) {

int i,flag,max,min; DataNode *temp1,*temp2; DataNode *result,*temp;

result=(DataNode*)malloc(sizeof(DataNode)); if((node1->data)*(node2->data)>0) {

if(abs(node1->data)>abs(node2->data)) {

max=abs(node1->data);

13

min=abs(node2->data); flag=1; } else {

max=abs(node2->data); min=abs(node1->data); flag=2; } CF=0;

temp1=node1->pre; temp2=node2->pre; temp=result; for(i=1;i

temp->pre=(DataNode*)malloc(sizeof(DataNode)); temp->pre->next=temp; temp=temp->pre; if(i

temp->data=(temp1->data+temp2->data+CF)0; CF=(temp1->data+temp2->data+CF)/100; temp1=temp1->pre; temp2=temp2->pre; }

else if(flag==1) {

temp->data=(temp1->data+CF)0; CF=(temp1->data+CF)/100; temp1=temp1->pre; }

14

else {

temp->data=(temp2->data+CF)0; CF=(temp2->data+CF)/100; temp2=temp2->pre; } } if(CF!=0) {

max++;

temp->pre=(DataNode*)malloc(sizeof(DataNode)); temp->pre->next=temp; temp=temp->pre; temp->data=CF; }

temp->pre=result; result->next=temp; if((node1->data)<0) max=0-max; result->data=max; return result; } else {

switch(test(node1,node2)) {

case 0:result->data=2;

result->next=(DataNode*)malloc(sizeof(DataNode)); result->next->data=0; result->next->pre=result; result->pre=result->next;

15

return result; case 1:CF=0;

max=abs(node1->data); min=abs(node2->data); temp1=node1->pre; temp2=node2->pre; temp=result; for(i=1;i

temp->pre=(DataNode*)malloc(sizeof(DataNode)); temp->pre->next=temp; temp=temp->pre; if(i

if((temp1->data)>(temp2->data))

temp->data=(temp1->data)-(temp2->data)+CF; else if((temp1->data)<(temp2->data)) {

temp->data=100+(temp1->data)-(temp2->data)+CF; CF=-1; } else {

if(CF!=0) {

temp->data=100+CF; CF=-1; } else

temp->data=0; }

16

} else {

if(temp1->data==0) {

temp->data=(temp1->data)+CF+100; CF=-1; } else {

temp->data=(temp1->data)+CF; CF=0; } }

temp1=temp1->pre; temp2=temp2->pre; }

temp->pre=result; result->next=temp;

result->data=node1->data;break; case 2:CF=0; max=abs(node2->data); min=abs(node1->data); temp1=node1->pre; temp2=node2->pre; temp=result; for(i=1;i

temp->pre=(DataNode*)malloc(sizeof(DataNode)); temp->pre->next=temp; temp=temp->pre;

17

if(i

if((temp2->data)>(temp1->data))

temp->data=(temp2->data)-(temp1->data)+CF; else if((temp2->data)<(temp1->data)) {

temp->data=100+(temp2->data)-(temp1->data)+CF; CF=-1; } else {

if(CF!=0) {

temp->data=100+CF; CF=-1; } else

temp->data=0; } } else {

if(temp2->data==0) {

temp->data=(temp2->data)+CF+100; CF=-1; } else {

temp->data=(temp2->data)+CF;

18

CF=0; } }

temp1=temp1->pre; temp2=temp2->pre; }

temp->pre=result; result->next=temp;

result->data=node2->data;break; }

while((result->next->data)==0) {

if(abs(result->data)==2) break;

temp=result->next; result->next=temp->next; result->next->pre=result; if((result->data)>0) (result->data)--; else

(result->data)++; }

return result; } }

void gotoxy(int a,int b) {

int x=0x0b;

HANDLE hInput, hOutput; COORD loc;

19

loc.X = a; loc.Y=b;

hOutput = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleCursorPosition(hOutput, loc); }

void main() {

DataNode *data1,*data2,*result; char key;

char menus[5][20]={\ \ \ \ }; int i,flag=0; for(i=0;i<5;i++) {

gotoxy(25,i*2+6); cprintf(menus[i]); }

scanf(\ while(key!='3') {

switch(key) {

case '1':system(\

printf(\ data1=Input();

printf(\ data2=Input();

20

flag=1; break; case '2':if(flag==0) {

system(\

printf(\ } else {

system(\

result=add(data1,data2); printf(\ Output(result); getch(); } break; }

system(\ for(i=0;i<5;i++) {

gotoxy(25,i*2+6); cprintf(menus[i]); }

scanf(\ } }

21

flag=1; break; case '2':if(flag==0) {

system(\

printf(\ } else {

system(\

result=add(data1,data2); printf(\ Output(result); getch(); } break; }

system(\ for(i=0;i<5;i++) {

gotoxy(25,i*2+6); cprintf(menus[i]); }

scanf(\ } }

21

本文来源：https://www.bwwdw.com/article/iwq8.html