|
/*
* 我也遵循GPL协议
* A simple single list implementation.
*
* Copyright (C) 2008 Bob Zhang
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*
*/
/* ===================================================================================
* 用链式存储结构实现一个栈
* 我们的策略是用栈或者链表的时候， 都是先构造一个节点，
* 然后把节点插入链表或者入栈或者出栈
* 其实就用往header的后面不断的插入数据
*
* ==================================================================================*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node_t {
void *data_p; //可以兼容所有的数据类型
struct node_t *next;
}node_t;
//当top = header的时候，说明是空栈
typedef struct stack_t {
node_t *top; //栈顶 其实就是相当于链表的header
// int size; //元素个数
}stack_t;
//初始化一个节点
#define INIT_NODE(node,ptr) do { node->data_p = ptr; node->next = NULL; } while(0)
//声明一个节点
#define DECLARE_NODE(name,ptr) \
node_t *name = (node_t *)malloc(sizeof(node_t));\
INIT_NODE(name,ptr);
//初始化一个栈
#define INIT_STACK_TOP(stack) \
stack->top = (node_t *)malloc(sizeof(node_t)); \
stack->top->next = NULL;
//声明一个栈
#define DECLARE_STACK(STACK_NAME) \
stack_t *STACK_NAME = (stack_t *)malloc(sizeof(stack_t)); \
INIT_STACK_TOP(STACK_NAME); \
/* 函数声明 */
int push(stack_t * stack,node_t *node); //入栈
int pop(stack_t *stack,node_t **pop_node); //出栈,返回值来判断是否成功，pop_node表示弹出的节点
int empty_stack(stack_t *stack); //是否空栈
int free_stack(stack_t *stack);
/* 函数实现 */
//对于push来说比链表更简单， 直接更新top后面的第一个节点就好了
int push(stack_t * stack,node_t *node)
{
node->next = stack->top->next;
stack->top->next = node;
return 0;
}
//这里必须传二重指针，试想如果传 node_t *node_p肯定不行
int pop(stack_t *stack, node_t **node_p)
{
node_t *top = stack->top;
if(!top->next)
{
printf("this is empty stack \n");
return -1;
}
*node_p = top->next;
//只需删掉top后面节点即可，并返回给node_p
top->next = top->next->next;
(*node_p)->next = NULL; //这里很关键， 一定要在这里，不能在上面一行，因为这是旧的头结点
return 0;
}
int free_stack(stack_t *stack)
{
free(stack->top);
free(stack);
return 0;
}
//开始把十进制转换其他的进制
int convert(int n, int B)
{
DECLARE_STACK(stack_xx);
int x = 0;
node_t * tmp = NULL;
do
{
node_t *node = (node_t *)malloc(sizeof(node_t));
x = n % B;
INIT_NODE(node,&x);
push(stack_xx,node);
n/=B;
}while(n);
tmp = stack_xx->top->next;
while(tmp) {
printf("xx %d\n",*(int *)(tmp->data_p));
tmp = tmp->next;
}
//计算完毕， 开始打印最后结果，开始依次出栈
while(1)
{
node_t *node = NULL;
int ret = 0;
ret = pop(stack_xx,&node);
if(ret < 0)
break;
ret = *(int *)(node->data_p);
if(ret < 10)
printf("%d",ret);
else
printf("%c",ret+55);
//释放这个节点
free(node);
}
printf("\n");
free_stack(stack_xx);
return 0;
}
int main(void)
{
node_t *p = NULL;
DECLARE_STACK(stack);
int n = 10;
int B = 2;
int ret = 0;
DECLARE_NODE(p1,"zhanglinbao");
DECLARE_NODE(p2,"1234567890");
DECLARE_NODE(p3,"ABCDEFGHIJKLMN");
push(stack,p1);
push(stack,p2);
push(stack,p3);
p = stack->top->next;
while(p)
{
printf("content=%s\n",(char *)(p->data_p));
p=p->next;
}
printf("Stack \n\n");
while(1) {
ret = pop(stack,&p);
if(ret < 0)
break;
printf("content=%s\n",(char *)(p->data_p));
printf("pointer = %p\n",p->next);
free(p); //因为这些节点都是malloc得来的，必须free
}
free_stack(stack);
scanf("%d,%d",&n,&B);
convert(n,B);
return 0;
}
|
