ETemp2数据结构课程设计报告

《数据结构》课程设计报告安徽工业大学计算机学院2012年6月学号姓名班级计算机科学与技术102班指导教师课题一大数相乘问题一、问题描述：本问题中，要求输入两个相对较大的正整数，能够通过程序计算出其结果。这两个大数的位数均在18位以上，不用使用longint类型来处理。二、设计思路：1、首先考虑设计将两个大数按照输入顺序存入分别存入进入线性表L1[MS],L2[MS]中；2、把这个数组中的每一位数字单独来进行乘法运算，比如我们可以用一个数字和另外一个数组中的每一位去相乘，从而得到乘法运算中一行的数字，再将每一行数字错位相加。这就是乘法运算的过从低位往高位依次计算，同时确定每一列的项数，确定每一位上的结果存入链桟PS中；3、然后将桟中元素逐个输出，也就是依次输出各位上的数值；4、通过主函数来调用其它各个函数。三、数据结构定义:1、/*桟结构体定义*/typedefstruct{DataTypedata[MS];inttop;}SeqStack,*PSeqStack;2、/*队列结构体定义*/typedefstruct{DataTypedata[MS];intfront,rear;}SeqQueue,*PSeqQueue;3、/*顺序表结构体定义*/typedefstructnode{DataTypedata[MS];intlength;}SeqList,*PSeqList;四、系统功能模块介绍:1、桟结构模块：PSeqStackInit_SeqStack()/*初始化空栈*/intEmpty_SeqStack(PSeqStackS)/*判栈空*/intPush_SeqStack(PSeqStackS,DataTypex)/*入栈*/intPop_SeqStack(PSeqStackS,DataType*x)/*出栈*/voidDestroy_SeqStack(PSeqStack*S)/*销毁栈*/2、队列结构体模块：PSeqQueueInit_SeqQueue()/*队列初始化*/intEmpty_SeqQueue(PSeqQueueQ)/*判断队空*/intIn_SeqQueue(PSeqQueueQ,DataTypex)/*入队*/intOut_SeqQueue(PSeqQueueQ,DataType*x)/*出队*/voidDestroy_SeqQueue(PSeqQueue*Q)/*销毁队列*/3、顺序表结构模块：PSeqListInit_SeqList()/*顺序表初始化*/intInsert_SeqList(PSeqListPL,inti,DataTypex)/*顺序表插入*/voidDestroy_SeqList(PSeqList*PL)/*销毁线性表*/4、大数其他模块：voidSortSeqQueue(PSeqQueuePQ)/*整理队列，主要是相乘的数进行进位*/voidMultiply(PSeqListPL1,PSeqListPL2,PSeqQueuePQ,PSeqStackPS)/*大数相乘的主函数*/voidPrintResult(PSeqStackPS)/*打印结果*/五、程序清单（源程序）：#includestdio.h#includestdlib.h#includestring.h#defineDataTypeint/*定义数据类型为整型*/#defineMS101/*相乘的两个整数总位数不超过100*//*桟结构体定义*/typedefstruct{DataTypedata[MS];inttop;}SeqStack,*PSeqStack;/*初始化空栈*/PSeqStackInit_SeqStack(){PSeqStackS;S=(PSeqStack)malloc(sizeof(SeqStack));if(S){S-top=-1;}returnS;}/*判栈空*/intEmpty_SeqStack(PSeqStackS){if(S-top==-1)return1;elsereturn0;}/*入栈*/intPush_SeqStack(PSeqStackS,DataTypex){if(S-top==MS-1)return0;else{S-top++;S-data[S-top]=x;return1;}}/*出栈*/intPop_SeqStack(PSeqStackS,DataType*x){if(Empty_SeqStack(S))return0;else{*x=S-data[S-top];S-top--;return1;}}/*销毁栈*/voidDestroy_SeqStack(PSeqStack*S){if(*S)free(*S);*S=NULL;}/*队列结构体定义*/typedefstruct{DataTypedata[MS];intfront,rear;}SeqQueue,*PSeqQueue;/*队列初始化*/PSeqQueueInit_SeqQueue(){PSeqQueueQ;Q=(PSeqQueue)malloc(sizeof(SeqQueue));if(Q){Q-front=0;Q-rear=0;}returnQ;}/*判断队空*/intEmpty_SeqQueue(PSeqQueueQ){if(Q&&Q-front==Q-rear)return1;elsereturn0;}/*入队*/intIn_SeqQueue(PSeqQueueQ,DataTypex){if((Q-rear+1)%MS==Q-front){printf(队满);return-1;}else{Q-rear=(Q-rear+1)%MS;Q-data[Q-rear]=x;return1;}}/*出队*/intOut_SeqQueue(PSeqQueueQ,DataType*x){if(Empty_SeqQueue(Q)){printf(队空);return-1;}else{Q-front=(Q-front+1)%MS;*x=Q-data[Q-front];return1;}}/*销毁队列*/voidDestroy_SeqQueue(PSeqQueue*Q){if(*Q)free(*Q);*Q=NULL;}/*顺序表结构体定义*/typedefstructnode{DataTypedata[MS];intlength;}SeqList,*PSeqList;/*顺序表初始化*/PSeqListInit_SeqList(){PSeqListPL;PL=(PSeqList)malloc(sizeof(SeqList));if(PL)PL-length=0;returnPL;}/*顺序表插入*/intInsert_SeqList(PSeqListPL,inti,DataTypex){intj;if(!PL){printf(ThereisnotSeqList!\n);return(-2);}if(PL-length=MS){printf(TheSeqListisfull!\n);return(-1);}if(i1||iPL-length+1){printf(Thelocationisnotright!\n);return0;}for(j=PL-length-1;j=i-1;j--)PL-data[j+1]=PL-data[j];PL-data[i-1]=x;PL-length++;return1;}/*销毁线性表*/voidDestroy_SeqList(PSeqList*PL){if(*PL)free(*PL);*PL=NULL;}/*判断输入是否有误*/voidIsNumber(charc[],intn){inti;for(i=0;in;i++)if(c[i]'0'||c[i]'9'){printf(Thereissomethingwrongwiththenumberyouput!\n);getchar();//exit();}}/*整理队列，主要是进行进位*/voidSortSeqQueue(PSeqQueuePQ){inti;if(!PQ){printf(TheSeqQueueisnotexist!\n);return;}for(i=PQ-front+1;iPQ-rear;i++){PQ-data[i+1]+=PQ-data[i]/10;PQ-data[i]=PQ-data[i]%10;}while(PQ-data[PQ-rear]/10){i=PQ-data[PQ-rear]/10;PQ-data[PQ-rear]=PQ-data[PQ-rear]%10;In_SeqQueue(PQ,i);}}/*大数相乘的主函数*/voidMultiply(PSeqListPL1,PSeqListPL2,PSeqQueuePQ,PSeqStackPS){inti,j;intnextBit;intk;charL1[MS],L2[MS];printf(请输入第一个大数:\n);gets(L1);IsNumber(L1,strlen(L1));for(i=0;istrlen(L1);i++)/*第一个数进入线性表*/Insert_SeqList(PL1,1,L1[i]-'0');/*判断输入是否有误*/printf(请输入第二个大数:\n);gets(L2);IsNumber(L2,strlen(L2));/*判断输入是否有误*/for(i=0;istrlen(L1);i++)/*第二个数进入线性表*/Insert_SeqList(PL2,1,L2[i]-'0');for(j=0;jPL2-length;j++)In_SeqQueue(PQ,PL1-data[0]*PL2-data[j]);SortSeqQueue(PQ);Out_SeqQueue(PQ,&nextBit);Push_SeqStack(PS,nextBit);for(i=1;iPL1-length;i++){k=PQ-front+1;for(j=0;jPL2-length;j++){if(k=PQ-rear)PQ-data[k++]+=PL1-data[i]*PL2-data[j];else{In_SeqQueue(PQ,PL1-data[i]*PL2-data[j]);k++;}}SortSeqQueue(PQ);Out_SeqQueue(PQ,&nextBit);Push_SeqStack(PS,nextBit);}while(!Empty_SeqQueue(PQ)){Out_SeqQueue(PQ,&nextBit);Push_SeqStack(PS,nextBit);}}/*打印结果*/voidPrintResult(PSeqStackPS){intTheBit;intcount=0;printf(这两个大数相乘的结果是:\n);while(!Empty_SeqStack(PS)){Pop_SeqStack(PS,&TheBit);printf(%d,TheBit);count++;if(count%5==0)printf();}}/*测试主函数*/main(){PSeqListPL1,PL2;PSeqQueuePQ;PSeqStackPS;PL1=Init_SeqList();PL2=Init_SeqList();PQ=Init_SeqQueue();PS=Init_SeqStack();Multiply(PL1,PL2,PQ,PS);PrintResult(PS);getchar();Destroy_SeqList(&PL1);Destroy_SeqList(&PL2);Destroy_SeqQueue(&PQ);Destroy_SeqStack(&PS);}六、运行结果及调试分析:七、课