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

数据结构课程设计报告班 级 学 号 姓 名 指导教师 课题一、大数相乘一、问题描述要求：输入两个较大的整数，进行乘法运算，能够通过程序计算出其正确的结果，并输出结果，使整数相乘不受计算机内存空间的限制。二、设计思路及步骤1、首先，要输入两个大数，所以在void multil()大数相乘操作函数中，定义两个字符型数组AN和BN，其中，N为数组的最大长度，以字符串的形式来记录这两个较大的整数，定义字符型指针res记录这两个整数相乘结果的返回地址，用于输出结果。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 swap(char* str, int p, int q); /逆序操作函数 void menu(); /菜单函数 void multil(); /大数相乘操作函数 char* LargeNum_ multi (char* A, char* B); /大数相乘函数四、源程序代码#include #include #include #define N 100 void swap(char* str, int p, int q); /逆序 void menu(); /菜单void multil(); /大数相乘操作char* LargeNum_multi(char* A, char* B); /大数相乘 void swap(char* str, int p, int q) /逆序 char temp; while(p =1&A0=1&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;im+n;i+) *(result+i)=0; resultm+n = 0; swap(A, 0, m-1); swap(B, 0, n-1); for(i=0; i = n-1; i+) / B的每一位 multiFlag = 0; addFlag = 0; for(int j=0; j =1&B0=1&A0=1&A0=1&A0cofe=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; else 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-cofe0&p!=h-next) if(p-exp0) printf(+%d%c%d,p-cofe,p-var,p-exp); else if(p-expcofe,p-var,p-exp); else printf(+%d,p-cofe); else if(p-cofenext) if(p-exp0) printf(%d%c%d,p-cofe,p-var,p-exp); else if(p-expcofe,p-var,p-exp); else printf(%d,p-cofe); else if(p-exp0) printf(%d%c%d,p-cofe,p-var,p-exp); else if(p-expcofe,p-var,p-exp); else printf(%d,p-cofe); p=p-next; link_Polynode merge(link_Polynode h1,link_Polynode h2) /合并单链表 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,temp; 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; 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();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(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:printf(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：可对第二个多项式的所有系数进行取反操作，然后在调用多项式加法运算函数，并输出结果。不足之处2：本程序可操作数的范围较小，仅为整型。解决方案2：可对程序中的系数和指数定义为浮点型，进一步扩大它们的范围。不足之处3：本程序不能进行两个多项式的乘法运算。解决方案3:（暂无）课题三、二叉树一般操作及线索化一、问题描述要求：实现二叉树的一般操作及中序线索化。二、设计思路及步骤1、定义所需的数据，如：二叉树数据定义，栈的定义，队列的定义，等等。2、要进行二叉树的一般操作，首先，要创建一个二叉树，所以定义二叉树创建函数，包括：先序遍历二叉树的创建函数Btree CreateBtree1()和 层次遍历二叉树创建函数Btree create_level_Btree2()。3、二叉树创建后就进行其一般的遍历操作，于是就定义其各类遍历函数：先序递归遍历，先序非递归遍历，中序递归遍历，中序非递归遍历，后序递归遍历，后序非递归遍历，层次遍历；其中，一些遍历函数会用到栈或队列的操作。4、在进行遍历后，可进行其他的一般操作，如：节点数计算，深度计算，/叶子节点数计算，等等。5、最后，可对二叉树进行中序线索化操作，并对线索化后的二叉树进行线索化遍历。三、二叉树数据定义typedef struct Bnodechar data;int ltag,rtag; struct Bnode *lchild,*rchild;Bnode,*Btree; /定义二叉树数据栈定义typedef struct 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); /中序线索遍历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 PostOrder1(Btree t); /后序递归序列void PostOrder2(Btree t); /后序非递归序列void PreOrder1(Btree t); /先序递归序列void PreOrder2(Btree t); /先序非递归序列void push(pseqstack s,Btree x); /数据入栈 void menu(); /菜单 四、源程序代码#include#includetypedef struct Bnodechar data;int ltag,rtag; struct Bnode *lchild,*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(); /层次遍历二叉树创建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 outQuese(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) /数据入栈 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-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-dataQ-rear+=root; while(Q&Q-frontrear) 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=(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-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,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,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.top=-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(&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) inQuese(&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(h1h2)return h1+1;return 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; /建立当前节点的前驱线索 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)root-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-data); 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 中序遍历(非递归):);InOrder2(t); printf(n);printf(t 后序遍历(递归):);PostOrder1(t); printf(n);printf(t 后序遍历(非递归):);PostOrd