数据结构课程设计-大数相乘等_第1页
数据结构课程设计-大数相乘等_第2页
数据结构课程设计-大数相乘等_第3页
数据结构课程设计-大数相乘等_第4页
数据结构课程设计-大数相乘等_第5页
已阅读5页,还剩47页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、.数据结构课程设计报告班 级 学 号 姓 名 指导教师 课题一、大数相乘一、问题描述要求:输入两个较大的整数,进行乘法运算,能够通过程序计算出其正确的结果,并输出结果,使整数相乘不受计算机内存空间的限制。二、设计思路及步骤1、首先,要输入两个大数,所以在void multil()大数相乘操作函数中,定义两个字符型数组AN和BN,其中,N为数组的最大长度,以字符串的形式来记录这两个较大的整数,定义字符型指针res记录这两个整数相乘结果的返回地址,用于输出结果。2、在大数乘法计算过程中,首先,将字符串各位的字符先转化为所对应的数字,然后再进行一系列的计算,由于整数乘法计算是从低位到高位依次计算,所

2、以为符合这一规律,先对两个大数字符串先进行逆序操作(void swap(char* str, int p, int q)逆序操作函数),最后再将所得的结果进行逆序操作,并输出结果。3、在char* LargeNum_ multi (char* A, char* B)大数相乘函数中,分别定义整型变量m和 n分别记录数组AN和数组BN的长度,定义字符型指针变量result记录两大数相乘后的地址用于返回地址,result的最大长度为(m+n),定义整型变量multiFlag和addFlag分别表示乘法进位和加法进位,初始化均为0,在之后的运算过程中记录乘法进位和加法进位。 三、函数清单 void s

3、wap(char* str, int p, int q); /逆序操作函数 void menu(); /菜单函数 void multil(); /大数相乘操作函数 char* LargeNum_ multi (char* A, char* B); /大数相乘函数四、源程序代码#include <stdio.h> #include <stdlib.h>#include <string.h> #define N 100 void swap(char* str, int p, int q); /逆序 void menu(); /菜单void multil(); /

4、大数相乘操作char* LargeNum_multi(char* A, char* B); /大数相乘 void swap(char* str, int p, int q) /逆序 char temp; while(p < q) temp = strp; strp = strq; strq = temp; p +; q -; char* LargeNum_multi(char* A, char* B) /大数相乘 if(A0>='1'&&A0<='9')&&(B0>='1'&&

5、;B0<='9') /正 &&正 int m = strlen(A); int n = strlen(B); int i; char *result; int multiFlag; / 乘积进位 int addFlag; / 加法进位 result=(char*)malloc(sizeof(char)*(m+n+1); for(i=0;i<m+n;i+) *(result+i)='0' resultm+n = '0' swap(A, 0, m-1); swap(B, 0, n-1); for(i=0; i <=

6、n-1; i+) / B的每一位 multiFlag = 0; addFlag = 0; for(int j=0; j <= m-1; j+) / A的每一位 int temp1 = (Aj - '0') * (Bi - '0') + multiFlag; multiFlag = temp1 / 10; temp1 = temp1 % 10; int temp2 = (resulti+j - '0') + temp1 + addFlag; addFlag = temp2 / 10; resulti+j = temp2 % 10 + '

7、;0' resulti + m += multiFlag + addFlag; /最高位 swap(result, 0, m+n-1); / 逆序 return result; else if(A0='-'&&B0='-') /负 && 负 LargeNum_multi(A+1),(B+1); else if(A0='-'&&(B0>='1'&&B0<='9') /负 && 正 printf("-"

8、;); LargeNum_multi(A+1),B); else if(B0='-'&&(A0>='1'&&A0<='9') / 正 && 负 printf("-"); LargeNum_multi(A,(B+1); else if(B0='0'&&(A0>='1'&&A0<='9') /正 && 0 printf("0"); menu();

9、 else if(A0='0'&&(B0>='1'&&A0<='9') /0 && 正 printf("0"); menu(); else if(B0='0'&&A0='-') /负 && 0 printf("0"); menu(); else if(B0='-'&&A0='0') /0 && 负 printf("

10、;0"); menu(); else if(B0='0'&&A0='0') / 0 && 0 printf("0"); menu(); void multil() /大数相乘操作 char AN; char BN; printf("t输入第一个数字:a="); scanf("%s",A); printf("t输入第二个数字:b="); scanf("%s",B); printf("t输出结果:a*b="

11、); char *res = LargeNum_multi(A, B); if(res0 != '0') printf("%c", res0); printf("%s", res+1); menu(); void menu() /菜单 printf("nnt+-大数相乘-+n"); printf("t+ 1、进行大数相乘计算 +n"); printf("t+ 2、退出程序 +n"); printf("t+ (请正确输入数据) +n"); int item; p

12、rintf("nt请输入菜单选项:"); scanf("%d",&item); switch(item) case 1:printf("nt+进行大数相乘计算:n");multil();break;case 2:printf("nt+退出程序成功n");exit(0);break;default:printf("nt(+请在1和2中进行选择+)");menu();break; int main() menu(); return 0; 五、运行截图1、 正&&正2、 负&a

13、mp;&正3、正&&负4、负&&负5、0&&06、0&&正7、正&&08、0&&负9、负&&0六、不足之处与解决方案不足之处1:本程序只能解决整型范围内的大数相乘问题,而不能解决浮点型范围内的大数相乘。解决方案1:把浮点型大数分为整数部分和小数部分,分别对其进行大数相乘函数的调用并输出结果,这仅是一种思路,可上机进行调试和运行。 课题二、简单m 元多项式加法一、问题描述要求:输入两个简单的m 元多项式,进行加法运算,并输出结果。二、设计思路及步骤1、定义简单m元多项式的结构,

14、其中包括:系数cofe,変元 var,指数exp;2、定义link_Polynode creat()创建简单m元多项式函数,即定义一个带头结点的单链表,通过link_Polynode creat()创建简单m元多项式函数分别生成两个简单的m元多项式,并打印。3、定义void print(link_Polynode h) 打印多项式函数,标准化打印多项式。4、定义link_Polynode merge(link_Polynode h1,link_Polynode h2) 单链表连接函数,将两个简单m元多项式的单链表合并成一个单链表,并进行打印操作。5、定义link_Polynode UniteP

15、oly(link_Polynode h)合并同类项函数,将连接后的单链表进行合并同类项操作,即即单链表中変元var和指数exp完全相同的项,对其系数进行相加或相减的操作,最后只保留一项変元var和指数exp和原来相同的项,最后,进行打印操作,显示进行m 元多项式加法后的结果。三、m元多项式数据定义typedef struct node int cofe; /系数 char var; /变元 int exp; /指数struct node *next; node,*link_Polynode; 函数清单link_Polynode creat();/创建简单m元多项式link_Polynode m

16、erge(link_Polynode h1,link_Polynode h2);/单链表连接void print(link_Polynode h);/打印多项式 link_Polynode UnitePoly(link_Polynode h);/合并同类项void menu();/菜单 四、源程序代码#include "stdio.h"#include "stdlib.h"typedef struct node int cofe; /系数 char var; /变元 int exp; /指数struct node *next; node,*link_Po

17、lynode;link_Polynode creat(); /创建多项式 link_Polynode merge(link_Polynode h1,link_Polynode h2);/合并单链表void print(link_Polynode h);/打印多项式 link_Polynode UnitePoly(link_Polynode h);/合并同类项void menu();/菜单 link_Polynode creat()link_Polynode h,p,q;int c,e;char v;h=(link_Polynode)malloc(sizeof(node);p=h; printf

18、("t 输入系数:"); scanf("%d",&c); /*输入系数*/ printf("t 输入变元:"); getchar(); scanf("%c",&v); /*输入变元*/ printf("t 输入指数:"); scanf("%d",&e); /*输入指数*/ if(c!=0) while(c!=0&&v!='0') q=(link_Polynode)malloc(sizeof(node); q->co

19、fe=c; q->var=v; q->exp=e; p->next=q; p=q; printf("t 输入系数:"); scanf("%d",&c); /*输入系数*/ if(c=0) break; printf("t 输入变元:"); getchar(); scanf("%c",&v); /*输入变元*/ printf("t 输入指数:"); scanf("%d",&e); /*输入指数*/ p->next=NULL; el

20、se p->next=NULL;return h;void print(link_Polynode h)link_Polynode p;p=h->next; if(p=NULL)printf("0");while(p) if(p->cofe>0&&p!=h->next) if(p->exp>0) printf("+%d%c%d",p->cofe,p->var,p->exp); else if(p->exp<0) printf("+%d%c(%d)"

21、,p->cofe,p->var,p->exp); else printf("+%d",p->cofe); else if(p->cofe<0&&p!=h->next) if(p->exp>0) printf("%d%c%d",p->cofe,p->var,p->exp); else if(p->exp<0) printf("%d%c(%d)",p->cofe,p->var,p->exp); else printf(&q

22、uot;%d",p->cofe); else if(p->exp>0) printf("%d%c%d",p->cofe,p->var,p->exp); else if(p->exp<0) printf("%d%c(%d)",p->cofe,p->var,p->exp); else printf("%d",p->cofe); p=p->next; link_Polynode merge(link_Polynode h1,link_Polynode h

23、2) /合并单链表 link_Polynode p1,p2,q1,q2,f; p1=h1->next; p2=h2->next; if(p1=NULL) return h2; else if(p2=NULL) return h1; else for(p1=h1->next;p1;p1=p1->next) q1=p1->next; if(q1=NULL) f=p1; f->next=p2; return h1; link_Polynode UnitePoly(link_Polynode h)/合并同类项 link_Polynode p1,p2,q1,q2,te

24、mp; q1=h; p1=q1->next; while(p1!=NULL) p2=p1->next; q2=p1; while(p2!=NULL) if(p1->exp=p2->exp)&&(p1->var=p2->var) p1->cofe=p1->cofe+p2->cofe; if(p1->cofe=0) temp=p2; q2->next=p2->next; free(temp); temp=p1; q1->next=p1->next; p1=q1; free(temp); break;

25、 else temp=p2; q2->next=p2->next; p2=p2->next; free(temp); else q2=p2; p2=p2->next; q1=p1; p1=p1->next; return h;void polynomial()link_Polynode t1,t2,t3,t4;printf("t请正确输入第一个多项式:nt (系数cofe为 0 结束):n");t1=creat(); printf("t请正确输入第二个多项式:nt (系数cofe为 0 结束):n");t2=creat();

26、printf("t显示第一个多项式:m1=");print(t1);printf("n");printf("t显示第二个多项式:m2="); print(t2);printf("n");printf("t显示两个多项式合并后的多项式:m1+m2=");t3=merge(t1,t2);print(t3);printf("n");printf("t合并同类项输出最后结果:M="); t4=UnitePoly(t3);print(t4);printf("

27、;n");menu();void menu()printf("nt+-简单多元多项式加法-+n"); printf("t+ 1、进行多项式加法计算 +n"); printf("t+ 2、退出程序 +n"); printf("t+ (正确输入数据哟,否则会出错哟)+n");int item;printf("t输入菜单选项:"); scanf("%d",&item);switch(item)case 1:polynomial();break;case 2:pri

28、ntf("t 退出程序n");exit(0);break;default:printf("nt *(请在1或2中选择)*");printf("n");menu();break; int main()menu();五、运行截图1、多项式&&多项式2、0&&03、0&&多项式4、 多项式&&0六、不足之处及解决方案不足之处1:本程序只能进行两个简单多元多项式的加法运算,而不能进行减法运算。解决方案1:可对第二个多项式的所有系数进行取反操作,然后在调用多项式加法运算函数,并输出

29、结果。不足之处2:本程序可操作数的范围较小,仅为整型。解决方案2:可对程序中的系数和指数定义为浮点型,进一步扩大它们的范围。不足之处3:本程序不能进行两个多项式的乘法运算。解决方案3:(暂无)课题三、二叉树一般操作及线索化一、问题描述要求:实现二叉树的一般操作及中序线索化。二、设计思路及步骤1、定义所需的数据,如:二叉树数据定义,栈的定义,队列的定义,等等。2、要进行二叉树的一般操作,首先,要创建一个二叉树,所以定义二叉树创建函数,包括:先序遍历二叉树的创建函数Btree CreateBtree1()和 层次遍历二叉树创建函数Btree create_level_Btree2()。3、二叉树创

30、建后就进行其一般的遍历操作,于是就定义其各类遍历函数:先序递归遍历,先序非递归遍历,中序递归遍历,中序非递归遍历,后序递归遍历,后序非递归遍历,层次遍历;其中,一些遍历函数会用到栈或队列的操作。4、在进行遍历后,可进行其他的一般操作,如:节点数计算,深度计算,/叶子节点数计算,等等。5、最后,可对二叉树进行中序线索化操作,并对线索化后的二叉树进行线索化遍历。三、二叉树数据定义typedef struct Bnodechar data;int ltag,rtag; struct Bnode *lchild,*rchild;Bnode,*Btree; /定义二叉树数据栈定义typedef stru

31、ct nodeBtree data100; /指针数组int top;seqstack,*pseqstack; /定义栈队列定义typedef struct snodeBtree data100;int front ,rear;seqQuese,*pseqQuese; /定义队列函数清单int count_tree(Btree t); /节点数计算 Btree CreateBtree1(); /先序遍历二叉树创建Btree create_level_Btree2(); /层次遍历二叉树创建int Depth(Btree t); /深度计算void inOrder(Btree t); /中序线索

32、遍历void InOrder1(Btree t); /中序递归序列void InOrder2(Btree t); /中序非递归序列Btree InOrderThread(Btree t); /中序线索化二叉树void inQuese(pseqQuese Q, Btree x); /数据入队列void inThread(Btree p); /线索化 int leaf(Btree t); /叶子节点数void LevelOrder(Btree t); /层次遍历Btree outQuese(pseqQuese Q); /数据出队列Btree pop(pseqstack s); /数据出栈 void

33、 PostOrder1(Btree t); /后序递归序列void PostOrder2(Btree t); /后序非递归序列void PreOrder1(Btree t); /先序递归序列void PreOrder2(Btree t); /先序非递归序列void push(pseqstack s,Btree x); /数据入栈 void menu(); /菜单 四、源程序代码#include<stdio.h>#include<stdlib.h>typedef struct Bnodechar data;int ltag,rtag; struct Bnode *lchi

34、ld,*rchild;Bnode,*Btree; /定义二叉树数据typedef struct nodeBtree data100; /指针数组int top;seqstack,*pseqstack; /定义栈typedef struct snodeBtree data100;int front ,rear;seqQuese,*pseqQuese; /定义队列Btree pre; /全局变量 / 函数清单 int count_tree(Btree t); /节点数计算 Btree CreateBtree1(); /先序遍历二叉树创建Btree create_level_Btree2(); /层

35、次遍历二叉树创建int Depth(Btree t); /深度计算void inOrder(Btree t); /中序线索遍历void InOrder1(Btree t); /中序递归序列void InOrder2(Btree t); /中序非递归序列Btree InOrderThread(Btree t); /中序线索化二叉树void inQuese(pseqQuese Q, Btree x); /数据入队列void inThread(Btree p); /线索化 int leaf(Btree t); /叶子节点数void LevelOrder(Btree t); /层次遍历Btree ou

36、tQuese(pseqQuese Q); /数据出队列Btree pop(pseqstack s); /数据出栈 void PostOrder1(Btree t); /后序递归序列void PostOrder2(Btree t); /后序非递归序列void PreOrder1(Btree t); /先序递归序列void PreOrder2(Btree t); /先序非递归序列void push(pseqstack s,Btree x); /数据入栈 void menu(); /菜单 void submenu(); /子菜单 void push(pseqstack s,Btree x) /数据入

37、栈 s->top+;s->datas->top=x;Btree pop(pseqstack s) /数据出栈 Btree t;t=s->datas->top;s->top-;return t;void inQuese(pseqQuese Q, Btree x) /数据入队列Q->rear=(Q->rear+1)%100;Q->dataQ->rear=x; Btree outQuese(pseqQuese Q) /数据出队列Btree q;Q->front=(Q->front+1)%100;q=Q->dataQ->

38、;front;return q;Btree create_level_Btree2() /层次遍历二叉树创建char ch;Btree root,p,s;pseqQuese Q;Q=(pseqQuese)malloc(sizeof(seqQuese);Q->front=Q->rear=0; /初始化ch=getchar(); if(ch='#') root=NULL; root=(Btree)malloc(sizeof(Bnode); /生成根节点 root->data=ch; root->ltag=0;root->rtag=0; Q->da

39、taQ->rear+=root; while(Q&&Q->front<Q->rear) p=Q->dataQ->front+; ch=getchar(); if(ch!='#') s=(Btree)malloc(sizeof(Bnode); s->data=ch; s->ltag=0; s->rtag=0; p->lchild=s; Q->dataQ->rear+=s; else p->lchild=NULL; ch=getchar(); if(ch!='#') s=(

40、Btree)malloc(sizeof(Bnode); s->data=ch; s->ltag=0; s->rtag=0; p->rchild=s; Q->dataQ->rear+=s; else p->rchild=NULL; return root; Btree CreateBtree1() /先序遍历二叉树创建Btree t;char ch;ch=getchar();if(ch='#')t=NULL;elset=(Btree)malloc(sizeof(Bnode);t->data=ch;t->ltag=0;t->

41、;rtag=0;t->lchild=CreateBtree1();t->rchild=CreateBtree1();return t; void PreOrder1(Btree t) /先序递归序列if(t)printf("%c",t->data);PreOrder1(t->lchild);PreOrder1(t->rchild);void PreOrder2(Btree t) /先序非递归序列Btree p=t;Btree q;seqstack s;s.top=-1;while(p|s.top!=-1)if(p)printf("%c

42、",p->data);push(&s,p);p=p->lchild;elseq=pop(&s);p=q->rchild;void InOrder1(Btree t) /中序递归序列if(t)InOrder1(t->lchild);printf("%c",t->data);InOrder1(t->rchild);void InOrder2(Btree t) /中序非递归序列Btree p=t;Btree q;seqstack s;s.top=-1;while(p|s.top!=-1)if(p)push(&s

43、,p);p=p->lchild;elseq=pop(&s);printf("%c",q->data);p=q->rchild;void PostOrder1(Btree t) /后序递归序列if(t)PostOrder1(t->lchild);PostOrder1(t->rchild);printf("%c",t->data);void PostOrder2(Btree t) /后序非递归序列seqstack s1;seqstack s2;Btree p=t;Btree q1,q2;s1.top=-1;s2.t

44、op=-1;while(p|s2.top!=-1)if(p)push(&s1,p);push(&s2,p);p=p->rchild;elseq2=pop(&s2);p=q2->lchild;while(s1.top!=-1)q1=pop(&s1);printf("%c",q1->data);void LevelOrder(Btree t) /层次遍历 Btree p=t; Btree q; seqQuese Q;Q.front=Q.rear=0; /初始化 inQuese(&Q,p); q=outQuese(&

45、;Q); printf("%c",q->data);if(q->lchild!=NULL) inQuese(&Q,q->lchild); if(q->rchild!=NULL) inQuese(&Q,q->rchild); while(Q.front!=Q.rear) q=outQuese(&Q); printf("%c",q->data); if(q->lchild!=NULL) inQuese(&Q,q->lchild); if(q->rchild!=NULL) i

46、nQuese(&Q,q->rchild); int leaf(Btree t) /叶子节点数if(!t)return 0;else if(!t->lchild&&!t->rchild)return 1;elsereturn (leaf(t->lchild)+leaf(t->rchild);int Depth(Btree t) /深度计算int h1,h2;if(t=NULL)return 0;elseh1=Depth(t->lchild);h2=Depth(t->rchild);if(h1>h2)return h1+1;r

47、eturn h2+1;int count_tree(Btree t) /节点数计算 int lcount,rcount;if(t=NULL)return 0;lcount=count_tree(t->lchild);rcount=count_tree(t->rchild);return lcount+rcount+1; /=中序线索化= void inThread(Btree p) /线索化 if(p)inThread(p->lchild); /左子树线索化 if(p->lchild=NULL) /前驱线索 p->lchild=pre; /建立当前节点的前驱线索

48、p->ltag=1;elsep->ltag=0;if(pre->rchild=NULL) /后继线索pre->rchild=p;pre->rtag=1; elsepre->rtag=0;pre=p;inThread(p->rchild); /右子树线索化 Btree InOrderThread(Btree t) /中序线索化二叉树 Btree root;root=(Btree)malloc(sizeof(Bnode);/创建根节点root->ltag=0;root->rtag=1;root->rchild=t;if(t=NULL)ro

49、ot->lchild-root;elseroot->lchild=t; pre=root; /pre是 p 的前驱节点 inThread(t); / 中序遍历线索化二叉树 pre->rchild=root;pre->rtag=1;root->rchild=pre; /根节点右线索化 return root; void inOrder(Btree t) /中序线索遍历 Btree p=t->lchild; while(p!=t) while(p->ltag=0) p=p->lchild; printf("%c",p->da

50、ta); while(p->rtag=1&&p->rchild!=t) p=p->rchild; printf("%c",p->data); p=p->rchild; void Binary_Tree_pre()Btree t; printf("t 先序输入二叉树(#表示空节点):nt "); t=CreateBtree1(); /先序遍历创建二叉树 printf("t显示二叉树信息:n"); printf("t 先序遍历(递归):");PreOrder1(t); printf("n");printf("t 先序遍历(非递归):");PreOrder2(t);printf("n");printf("t 中序遍历(递归):");InOrder1(t); printf("n");printf("t 中序遍历(非递归):");InOr

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论