最近学习数据结构栈和队列~这题是很好的练笔~九九也来露一手~
可以计算任意位数(理论上)的大数乘法~~~~~~~~~~~~
程序代码：
#include<stdio.h>
#include<stdlib.h>
#define LEN_Stack sizeof(Stack)
#define LEN_Queue sizeof (Qnode)
typedef struct Stack //栈
{
int n;
struct Stack* next;
}Stack;
typedef struct Qnode //队列
{
int n;
struct Qnode* next;
}Qnode,*QnodePrt;
typedef struct
{
QnodePrt front;
QnodePrt rear;
}LinkQueue;
Stack* Stack_creat(); //创建一个栈
void Stack_in(Stack** stack,int n); //入栈
void Stack_out(Stack** stack); //出栈
int Stack_empty(Stack* stack); //判断栈空
void Stack_destory(Stack** stack); //销毁栈
void Stack_input(Stack** stack); //输入数据
void Stack_output(Stack* stack); //输出数据
QnodePrt Queue_creat(); //创建一个队列
void Queue_in(LinkQueue* queue,int n); //入队
void Queue_out(LinkQueue* queue); //出队
int Queue_empty(LinkQueue* queue); //判断队列空
//void Queue_destory(LinkQueue* queue); //清空队列
//void Queue_output(LinkQueue* queue); //输出队列
void fun(); //主要执行流程
void product(Stack* p2); //乘积
void carry(LinkQueue* queue); //进位
void save(QnodePrt* p2); //保存数据
void show_result(); //输出结果
Stack* a=NULL;
Stack* b=NULL;
Stack* stack_result=NULL;
LinkQueue queue={0};
LinkQueue queue_result={0};
int main()
{
//初始化数据
Stack_input(&a);
Stack_input(&b);
fun();
return 0;
}
void fun()
{
QnodePrt p3=NULL;
while (!Stack_empty(b))
{
product(b); //计算乘积
Stack_out(&b); //出栈
carry(&queue); //进位
save(&p3); //保存数据
carry(&queue_result); //进位
}
show_result();
Stack_destory(&a); //释放空间
Stack_destory(&stack_result);
}
Stack* Stack_creat()
{
Stack* stack=(Stack* )malloc(LEN_Stack);
if (stack==NULL)
{
fprintf(stderr,"入栈失败!\n");
exit(0);
}
return stack;
}
void Stack_in(Stack** stack,int n)
{
Stack* p=Stack_creat();
p->n=n;
p->next=*stack;
*stack=p;
}
void Stack_out(Stack** stack) //出栈
{
Stack* p=*stack;
if (*stack==NULL)
return ;
*stack=(*stack)->next;
free(p);
}
int Stack_empty(Stack* stack) //判断栈空
{
return stack==NULL;
}
void Stack_destory(Stack** stack) //释放栈
{
Stack* p=*stack;
if (p==NULL)
return ;
while (p)
{
*stack=(*stack)->next;
free(p);
p=*stack;
}
*stack=NULL;
return ;
}
void Stack_input(Stack** stack) //输入数据
{
char c=0;
while (c!='\n')
{
c=getchar();
if (c>='0'&&c<='9')
Stack_in(stack,c-'0');
}
}
void Stack_output(Stack* stack) //输出栈数据
{
Stack* p=stack;
while (p)
{
printf("%d",p->n);
p=p->next;
}
puts("");
}
QnodePrt Queue_creat(LinkQueue* queue) //创建一个队列
{
QnodePrt p=(QnodePrt)malloc(LEN_Queue);
if (p==NULL)
{
fprintf(stderr,"入队失败!\n");
exit(0);
}
return p;
}
void Queue_in(LinkQueue* queue,int n) //入队
{
QnodePrt p=Queue_creat();
if (queue->front==NULL)
queue->front=queue->rear=p;
else
{
queue->rear->next=p;
queue->rear=p;
}
p->n=n;
p->next=NULL;
}
void Queue_out(LinkQueue* queue)//出队
{
QnodePrt p=NULL;
if (queue->front==NULL)
return ;
p=queue->front;
queue->front=queue->front->next;
free(p);
}
int Queue_empty(LinkQueue* queue) //判断队列空
{
return queue->front==NULL;
}
/*void Queue_destory(LinkQueue* queue) //清空队列
{
QnodePrt p=queue->front;
if (queue->front==NULL)
return ;
while (p)
{
p=p->next;
free(queue->front);
queue->front=p;
}
}*/
/*void Queue_output(LinkQueue* queue) //输出队列
{
QnodePrt p=queue->front;
while (p)
{
printf("%d",p->n);
p=p->next;
}
puts("");
}*/
void product(Stack* p2) //乘积
{
Stack* p1=a; //乘数
while (p1)
{
Queue_in(&queue,(p1->n*p2->n)); //积
p1=p1->next;
}
}
void carry(LinkQueue* queue) //进位
{
QnodePrt p3=queue->front;
while (p3->next)
{
if (p3->n>9&&p3->next)
{
p3->next->n+=p3->n/10;
p3->n%=10;
}
p3=p3->next;
}
if (p3->n>9) //考虑最高位是否进位
{
Queue_in(queue,p3->n/10);
p3->n%=10;
}
}
void save(QnodePrt* p2) //保存数据
{
QnodePrt p=NULL;
if (*p2!=NULL)
*p2=(*p2)->next; //每次计算保留数据都要前移一位
p=*p2;
while (!Queue_empty(&queue))
{
if (p==NULL)
{
Queue_in(&queue_result,queue.front->n);
p=queue_result.rear;
}
else
p->n+=queue.front->n;
Queue_out(&queue); //出队
p=p->next;
}
if (*p2==NULL)
*p2=queue_result.front;
}
void show_result() //因为此时queue_result得到的结果是反向的,所以要进行处理
{
while (!Queue_empty(&queue_result))
{
Stack_in(&stack_result,queue_result.front->n); //把结果入栈
Queue_out(&queue_result); //出队
}
if (stack_result->n==0) //考虑第一位数为0的情况
{
puts("0");
return ;
}
Stack_output(stack_result); //输出数据
}
[此贴子已经被作者于2017-3-14 03:56编辑过]
