最近学习数据结构是时候要实战巩固一下了~~看到有贴计算大位数乘法感觉不错~于是想到了用栈和队列求解~顺便巩固相关用法~

代码有点长~不过感觉其中包含了栈和队列的实战操作~可以作为参考~~

#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编辑过]