数据结构课程设计-大数相乘等

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