链表反转---栈实现

前不久数据结构考试最后一题写个链表反转,我当时没怎么实现,于是无聊就用栈来实现链表反转,下面这个程序没有考虑到效率,只是随便玩玩实现的。
[code]
#include <stdio.h>
#include <stdlib.h>

#define INIT_STACK_SIZE 100
#define ADD_STACK_SIZE 100

typedef struct Node{
int data;
struct Node *next;
}Node,*pNode;

typedef struct Stack{
pNode *base;
pNode *top;
int Stack_Size;
}Stack,*pStack;

bool InitNode(pNode *p); //Initial Node of Link
bool AddLinkNode(pNode L,int t);//Insert Node to Link
bool DelFirstNode(pNode L,pNode *NewNode);//Romove first node from link
void PrintLink(pNode L);//print Nodes of Link
bool InitStack(pStack S,pNode L);//Inital Stack for storing Nodes of Link
bool push(pStack S,pNode AddNode);//push one Node into the Stack
bool pop(pStack S,pNode *DelNode);//pop one node from Stack
void PrintStack(pStack S);//print elements of Stack

int main()
{
Node header; //first node is no use
header.data = 0;
header.next = NULL;
for(int i = 0; i < 100;++i) //for debug
{
AddLinkNode(&header,i); //Insert nodes into Link
}
PrintLink(&header); //for debug,Link is full now

Stack stack;
if(!InitStack(&stack,&header)) //Initial Stack
return 0;
pNode p = NULL; //p is for getting first node removing from Link
while(DelFirstNode(&header,&p))
{
if(!push(&stack,p))
{
printf("push failured!");
return 0;
}
}
// PrintStack(&stack);
PrintLink(&header); //Link is already empty
while(pop(&stack,&p))
{
AddLinkNode(&header,p->data);
}
PrintLink(&header);
return 0;
}

bool InitNode(pNode *p) //Initial Node
{
*p = (pNode )calloc(1,sizeof(Node));
if(!*p)
return false;
(*p)->next = NULL;
(*p)->data = 0;
return true;
}

bool AddLinkNode(pNode L,int t)
{
pNode p = L;
while(p->next) //find the lastest node of link
p = p->next;
pNode NewNode = NULL;
if(!InitNode(&NewNode))
return false;
NewNode->data = t; //insert into link
p->next = NewNode;
p = NewNode;
return true;
}

void PrintLink(pNode L)
{
if(!L->next)
{
printf("Link Empty\n");
return ;
}
int i = 1;
pNode p = L->next;
while(p)
{
printf("%d Node : %d \n",i,p->data);
++i;
p = p->next;
}
}

bool DelFirstNode(pNode L,pNode *NewNode)//Remove first node out of link
{
pNode pTail = L->next;
if(pTail)
{
*NewNode = pTail;
L->next = pTail->next;
pTail->next = NULL;
return true;
}
return false;
}

bool InitStack(pStack S,pNode L)
{
S->base = (pNode *)calloc(INIT_STACK_SIZE,sizeof(pNode));
if(!S->base)
return false;
*(S->base) = L;
S->top = S->base;
S->Stack_Size = INIT_STACK_SIZE;
return true;
}

bool push(pStack S,pNode AddNode)
{
if((S->top - S->base) >= S->Stack_Size)//if stack is full,allocate more memory
{
S->base = (pNode*)realloc(S->base,sizeof(pNode)*(INIT_STACK_SIZE + ADD_STACK_SIZE));
if(!S->base)
return false;
S->top = S->base + S->Stack_Size;
S->Stack_Size += ADD_STACK_SIZE;
}
*(S->top++) = AddNode;
return true;
}

bool pop(pStack S,pNode *DelNode)//push one node into Stack
{
if(S->base == S->top) //if stack is empty
{
printf("Empty Stack\n");
return false;
}
*DelNode = *(--S->top);
return true;
}

void PrintStack(pStack S)
{
pNode *p;
p = S->base;
int i = 0;
while(p != S->top)
{
printf("Stack No,%d : %d \n",1 + i,(*p)->data);
p++;
i++;
}
}
[/code]

标签:DataStructure