分别用数组和链表实现堆栈(C语言版)

时间:11-05-30 栏目:技术 作者:liva 评论:0 点击: 2,357 次

数组和链表是两种基础的数据结构,也是构成很多复杂数据结构的基础。本程序利用数组和链表实现堆栈。

/********************************************************

STACK.H

********************************************************/


#ifndef _STACK_H
#define _STACK_H


#ifndef BOOL
#define BOOL int
#endif

typedef char Item;

struct _Stack;
typedef struct _Stack Stack;
typedef Stack* pStack;


pStack Stack_Init(int nMax);
void Stack_Destroy(pStack pSt);

void Stack_Push(pStack pSt,Item elem);

Item Stack_Pop(pStack pSt);

int Stack_Size(pStack pSt);

BOOL Stack_IsEmpty(pStack pSt);
BOOL Stack_IsFull(pStack pSt);

#endif

/********************************************

基于数组 STACK.c

********************************************/

#include<stdio.h>
#include<stdlib.h>
#include"STACK.h"


static Error(char *msg)
{
printf("Error:%s\n",msg);
}

struct _Stack{
Item* elem;
int top;
int nMax;
};


pStack Stack_Init(int nMax)
{
pStack pSt=malloc(sizeof(*pSt));
pSt->elem=malloc(nMax*sizeof(*pSt->elem));
pSt->top=-1;
pSt->nMax=nMax-1;
return pSt;
}

void Stack_Destroy(pStack pSt)
{
free(pSt->elem);
pSt->elem=NULL;
free(pSt);
pSt=NULL;
}

void Stack_Push(pStack pSt,Item elem)
{
if(Stack_IsFull(pSt))
{
Error("Stack Is Full");
exit(-1);
}
pSt->elem[++pSt->top]=elem;
}


Item Stack_Pop(pStack pSt)
{
if(Stack_IsEmpty(pSt))
{
Error("Stack Is Empty");
exit(-1);
}
return pSt->elem[pSt->top--];
}

int Stack_Size(pStack pStk)
{
return pStk->top+1;
}

BOOL Stack_IsEmpty(pStack pSt)
{
return pSt->top==-1;
}

BOOL Stack_IsFull(pStack pSt)
{
return pSt->top==pSt->nMax ;
}


/***************************************************

基于链表

****************************************************/

typedef struct _StackElem
{
Item elem;
struct _StackElem *next;
}StackElem;

typedef StackElem* link;

_Stack
{
link head;
int nMax;

};


pStack Stack_Init(int nMax)
{
pStack pStk=malloc(sizeof(*pStk));
pStk->head=NULL;
pStk->nMax=nMax;
return pStk;
}

void Stack_Destroy(pStack pStk)
{
while(!Stack_IsEmpty(pStk))
{
Stack_Pop(pStk);
}
free(pStk);
}

void Stack_Push(pStack pStk,Item elem)
{
link ln;
if(Stack_IsFull(pStk))
{
Error("Stack Is Full");
exit(-1);
}
ln=malloc(sizeof(*ln));
ln->elem=elem;
ln->next=pStk->head;
pStk->head=ln;
}

Item Stack_Pop(pStack pStk)
{
link ln;
Item elem;
if(Stack_IsEmpty(pStk))
{
Error("Stack Is Empty");
exit(-1);
}
ln=pStk->head;
elem=ln->elem;
pStk->head=pStk->head->next;
free(ln);
return elem;
}

int Stack_Size(pStack pStk)
{
int cnt;
link ln;
for(cnt=0,ln=pStk->head;ln!=NULL;ln=ln->next,cnt++);

return cnt;
}

BOOL Stack_IsEmpty(pStack pStk)
{
return pStk->head==NULL;
}

BOOL Stack_IsFull(pStack pStk)
{
return Stack_Size(pStk)==pStk->nMax ;
}

/**********************************************

测试程序 main.c

*********************************************/


#include<stdio.h>
#include<string.h>
#include"STACK.h"


int main()
{
pStack pStk=Stack_Init(20);

char i='z';
while(!Stack_IsFull(pStk))
{
Stack_Push(pStk,i--);
}


printf("Stack Size=%d\n",Stack_Size(pStk));

while(!Stack_IsEmpty(pStk))
{
printf("%c\n",Stack_Pop(pStk));
}

Stack_Destroy(pStk);

return 0;
}

声明: 本文由( liva )原创编译,转载请保留链接: 分别用数组和链表实现堆栈(C语言版)

分别用数组和链表实现堆栈(C语言版):等您坐沙发呢!

发表评论


购物推荐

赞助商

© 2013 enjoydiy.com. Design by zijiao. 54 queries in 0.329 seconds, using 20.99MB memory