數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-大數(shù)相乘等

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告班 級 學 號 姓 名 指導教師 課題一、大數(shù)相乘一、問題描述要求：輸入兩個較大的整數(shù)，進行乘法運算，能夠通過程序計算出其正確的結(jié)果，并輸出結(jié)果，使整數(shù)相乘不受計算機內(nèi)存空間的限制。二、設(shè)計思路及步驟1、首先，要輸入兩個大數(shù)，所以在void multil()大數(shù)相乘操作函數(shù)中，定義兩個字符型數(shù)組AN和BN，其中，N為數(shù)組的最大長度，以字符串的形式來記錄這兩個較大的整數(shù)，定義字符型指針res記錄這兩個整數(shù)相乘結(jié)果的返回地址，用于輸出結(jié)果。2、在大數(shù)乘法計算過程中，首先，將字符串各位的字符先轉(zhuǎn)化為所對應的數(shù)字，然后再進行一系列的計算，由于整數(shù)乘法計算是從低位到高位依次計算，所以

2、為符合這一規(guī)律，先對兩個大數(shù)字符串先進行逆序操作（void swap(char* str, int p, int q)逆序操作函數(shù)），最后再將所得的結(jié)果進行逆序操作，并輸出結(jié)果。3、在char* LargeNum_ multi (char* A, char* B)大數(shù)相乘函數(shù)中，分別定義整型變量m和 n分別記錄數(shù)組AN和數(shù)組BN的長度，定義字符型指針變量result記錄兩大數(shù)相乘后的地址用于返回地址，result的最大長度為（m+n），定義整型變量multiFlag和addFlag分別表示乘法進位和加法進位，初始化均為0，在之后的運算過程中記錄乘法進位和加法進位。 三、函數(shù)清單 void sw

3、ap(char* str, int p, int q); /逆序操作函數(shù) void menu(); /菜單函數(shù) void multil(); /大數(shù)相乘操作函數(shù) char* LargeNum_ multi (char* A, char* B); /大數(shù)相乘函數(shù)四、源程序代碼#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、數(shù)相乘操作char* LargeNum_multi(char* A, char* B); /大數(shù)相乘 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) /大數(shù)相乘 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 <= n

6、-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() /大數(shù)相乘操作 char AN; char BN; printf("t輸入第一個數(shù)字:a="); scanf("%s",A); printf("t輸入第二個數(shù)字:b="); scanf("%s",B); printf("t輸出結(jié)果:a*b=")

11、; char *res = LargeNum_multi(A, B); if(res0 != '0') printf("%c", res0); printf("%s", res+1); menu(); void menu() /菜單 printf("nnt+-大數(shù)相乘-+n"); printf("t+ 1、進行大數(shù)相乘計算 +n"); printf("t+ 2、退出程序 +n"); printf("t+ (請正確輸入數(shù)據(jù)) +n"); int item; pr

12、intf("nt請輸入菜單選項："); scanf("%d",&item); switch(item) case 1:printf("nt+進行大數(shù)相乘計算: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、 負&am

13、p;&正3、正&&負4、負&&負5、0&&06、0&&正7、正&&08、0&&負9、負&&0六、不足之處與解決方案不足之處1：本程序只能解決整型范圍內(nèi)的大數(shù)相乘問題，而不能解決浮點型范圍內(nèi)的大數(shù)相乘。解決方案1：把浮點型大數(shù)分為整數(shù)部分和小數(shù)部分，分別對其進行大數(shù)相乘函數(shù)的調(diào)用并輸出結(jié)果，這僅是一種思路，可上機進行調(diào)試和運行。 課題二、簡單m 元多項式加法一、問題描述要求：輸入兩個簡單的m 元多項式，進行加法運算，并輸出結(jié)果。二、設(shè)計思路及步驟1、定義簡單m元多項式的結(jié)構(gòu)，其

14、中包括：系數(shù)cofe，変元 var，指數(shù)exp；2、定義link_Polynode creat()創(chuàng)建簡單m元多項式函數(shù)，即定義一個帶頭結(jié)點的單鏈表，通過link_Polynode creat()創(chuàng)建簡單m元多項式函數(shù)分別生成兩個簡單的m元多項式，并打印。3、定義void print(link_Polynode h) 打印多項式函數(shù)，標準化打印多項式。4、定義link_Polynode merge(link_Polynode h1,link_Polynode h2) 單鏈表連接函數(shù)，將兩個簡單m元多項式的單鏈表合并成一個單鏈表，并進行打印操作。5、定義link_Polynode UnitePo

15、ly(link_Polynode h)合并同類項函數(shù)，將連接后的單鏈表進行合并同類項操作，即即單鏈表中変元var和指數(shù)exp完全相同的項，對其系數(shù)進行相加或相減的操作，最后只保留一項変元var和指數(shù)exp和原來相同的項，最后，進行打印操作，顯示進行m 元多項式加法后的結(jié)果。三、m元多項式數(shù)據(jù)定義typedef struct node int cofe; /系數(shù) char var; /變元 int exp; /指數(shù)struct node *next; node,*link_Polynode; 函數(shù)清單link_Polynode creat();/創(chuàng)建簡單m元多項式link_Polynode me

16、rge(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; /系數(shù) char var; /變元 int exp; /指數(shù)struct node *next; node,*link_Pol

17、ynode;link_Polynode creat(); /創(chuàng)建多項式 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 輸入系數(shù):"); scanf("%d",&c); /*輸入系數(shù)*/ printf("t 輸入變元:"); getchar(); scanf("%c",&v); /*輸入變元*/ printf("t 輸入指數(shù):"); scanf("%d",&e); /*輸入指數(shù)*/ if(c!=0) while(c!=0&&v!='0') q=(link_Polynode)malloc(sizeof(node); q->cof

19、e=c; q->var=v; q->exp=e; p->next=q; p=q; printf("t 輸入系數(shù):"); scanf("%d",&c); /*輸入系數(shù)*/ if(c=0) break; printf("t 輸入變元:"); getchar(); scanf("%c",&v); /*輸入變元*/ printf("t 輸入指數(shù):"); scanf("%d",&e); /*輸入指數(shù)*/ p->next=NULL; els

20、e 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(&qu

22、ot;%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 h2

23、) /合并單鏈表 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,tem

24、p; 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 (系數(shù)cofe為 0 結(jié)束)：n");t1=creat(); printf("t請正確輸入第二個多項式:nt (系數(shù)cofe為 0 結(jié)束)：n");t2=creat();p

26、rintf("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合并同類項輸出最后結(jié)果: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+ (正確輸入數(shù)據(jù)喲，否則會出錯喲)+n");int item;printf("t輸入菜單選項："); scanf("%d",&item);switch(item)case 1:polynomial();break;case 2:prin

28、tf("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：可對第二個多項式的所有系數(shù)進行取反操作，然后在調(diào)用多項式加法運算函數(shù)，并輸出結(jié)

29、果。不足之處2：本程序可操作數(shù)的范圍較小，僅為整型。解決方案2：可對程序中的系數(shù)和指數(shù)定義為浮點型，進一步擴大它們的范圍。不足之處3：本程序不能進行兩個多項式的乘法運算。解決方案3:（暫無）課題三、二叉樹一般操作及線索化一、問題描述要求：實現(xiàn)二叉樹的一般操作及中序線索化。二、設(shè)計思路及步驟1、定義所需的數(shù)據(jù)，如：二叉樹數(shù)據(jù)定義，棧的定義，隊列的定義，等等。2、要進行二叉樹的一般操作，首先，要創(chuàng)建一個二叉樹，所以定義二叉樹創(chuàng)建函數(shù)，包括：先序遍歷二叉樹的創(chuàng)建函數(shù)Btree CreateBtree1()和 層次遍歷二叉樹創(chuàng)建函數(shù)Btree create_level_Btree2()。3、二叉樹創(chuàng)建

30、后就進行其一般的遍歷操作，于是就定義其各類遍歷函數(shù)：先序遞歸遍歷，先序非遞歸遍歷，中序遞歸遍歷，中序非遞歸遍歷，后序遞歸遍歷，后序非遞歸遍歷，層次遍歷；其中，一些遍歷函數(shù)會用到棧或隊列的操作。4、在進行遍歷后，可進行其他的一般操作，如：節(jié)點數(shù)計算，深度計算，/葉子節(jié)點數(shù)計算，等等。5、最后，可對二叉樹進行中序線索化操作，并對線索化后的二叉樹進行線索化遍歷。三、二叉樹數(shù)據(jù)定義typedef struct Bnodechar data;int ltag,rtag; struct Bnode *lchild,*rchild;Bnode,*Btree; /定義二叉樹數(shù)據(jù)棧定義typedef struc

31、t nodeBtree data100; /指針數(shù)組int top;seqstack,*pseqstack; /定義棧隊列定義typedef struct snodeBtree data100;int front ,rear;seqQuese,*pseqQuese; /定義隊列函數(shù)清單int count_tree(Btree t); /節(jié)點數(shù)計算 Btree CreateBtree1(); /先序遍歷二叉樹創(chuàng)建Btree create_level_Btree2(); /層次遍歷二叉樹創(chuàng)建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); /數(shù)據(jù)入隊列void inThread(Btree p); /線索化 int leaf(Btree t); /葉子節(jié)點數(shù)void LevelOrder(Btree t); /層次遍歷Btree outQuese(pseqQuese Q); /數(shù)據(jù)出隊列Btree pop(pseqstack s); /數(shù)據(jù)出棧 void

33、PostOrder1(Btree t); /后序遞歸序列void PostOrder2(Btree t); /后序非遞歸序列void PreOrder1(Btree t); /先序遞歸序列void PreOrder2(Btree t); /先序非遞歸序列void push(pseqstack s,Btree x); /數(shù)據(jù)入棧 void menu(); /菜單 四、源程序代碼#include<stdio.h>#include<stdlib.h>typedef struct Bnodechar data;int ltag,rtag; struct Bnode *lchil

34、d,*rchild;Bnode,*Btree; /定義二叉樹數(shù)據(jù)typedef struct nodeBtree data100; /指針數(shù)組int top;seqstack,*pseqstack; /定義棧typedef struct snodeBtree data100;int front ,rear;seqQuese,*pseqQuese; /定義隊列Btree pre; /全局變量 / 函數(shù)清單 int count_tree(Btree t); /節(jié)點數(shù)計算 Btree CreateBtree1(); /先序遍歷二叉樹創(chuàng)建Btree create_level_Btree2(); /層次

35、遍歷二叉樹創(chuàng)建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); /數(shù)據(jù)入隊列void inThread(Btree p); /線索化 int leaf(Btree t); /葉子節(jié)點數(shù)void LevelOrder(Btree t); /層次遍歷Btree out

36、Quese(pseqQuese Q); /數(shù)據(jù)出隊列Btree pop(pseqstack s); /數(shù)據(jù)出棧 void PostOrder1(Btree t); /后序遞歸序列void PostOrder2(Btree t); /后序非遞歸序列void PreOrder1(Btree t); /先序遞歸序列void PreOrder2(Btree t); /先序非遞歸序列void push(pseqstack s,Btree x); /數(shù)據(jù)入棧 void menu(); /菜單 void submenu(); /子菜單 void push(pseqstack s,Btree x) /數(shù)據(jù)入棧

37、 s->top+;s->datas->top=x;Btree pop(pseqstack s) /數(shù)據(jù)出棧 Btree t;t=s->datas->top;s->top-;return t;void inQuese(pseqQuese Q, Btree x) /數(shù)據(jù)入隊列Q->rear=(Q->rear+1)%100;Q->dataQ->rear=x; Btree outQuese(pseqQuese Q) /數(shù)據(jù)出隊列Btree q;Q->front=(Q->front+1)%100;q=Q->dataQ->

38、front;return q;Btree create_level_Btree2() /層次遍歷二叉樹創(chuàng)建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); /生成根節(jié)點 root->data=ch; root->ltag=0;root->rtag=0; Q->dat

39、aQ->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=(B

40、tree)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() /先序遍歷二叉樹創(chuàng)建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、quot;,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.to

44、p=-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) in

46、Quese(&Q,q->rchild); int leaf(Btree t) /葉子節(jié)點數(shù)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;re

47、turn h2+1;int count_tree(Btree t) /節(jié)點數(shù)計算 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) /前驅(qū)線索 p->lchild=pre; /建立當前節(jié)點的前驅(qū)線索 p

48、->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);/創(chuàng)建根節(jié)點root->ltag=0;root->rtag=1;root->rchild=t;if(t=NULL)roo

49、t->lchild-root;elseroot->lchild=t; pre=root; /pre是 p 的前驅(qū)節(jié)點 inThread(t); / 中序遍歷線索化二叉樹 pre->rchild=root;pre->rtag=1;root->rchild=pre; /根節(jié)點右線索化 return root; void inOrder(Btree t) /中序線索遍歷 Btree p=t->lchild; while(p!=t) while(p->ltag=0) p=p->lchild; printf("%c",p->dat

50、a); 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 先序輸入二叉樹(#表示空節(jié)點):nt "); t=CreateBtree1(); /先序遍歷創(chuàng)建二叉樹 printf("t顯示二叉樹信息：n"); printf("t 先序遍歷(遞歸):");PreOrder1(t); printf("n");printf("t 先序遍歷(非遞歸):");PreOrder2(t);printf("n");printf("t 中序遍歷(遞歸):");InOrder1(t); printf("n");printf("t 中序遍歷(非遞歸):");InOrd