lstack.h

一些基本的数据结构

/**************2008.2.6*********************链式栈的操作*******************************/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <process.h>
/**********************************************************/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int Status;
typedef int Boolean;
/************************************************************/

typedef int Element;

typedef struct LNode
        {
          Element data;
          struct LNode *next;
        }LNode, *Llist;

typedef struct Linkstack
        {
          Llist base,top;
          int stacksize;
        }Linkstack;


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

/*********************栈的链式基本操作****************************/

/*************插入元素***********************/
Status Link_insert( Llist *p, Element *e )
{
  *p = ( Llist )malloc( sizeof( LNode ) );
  if( !*p )
  return ERROR;
  (*p)->data = *e;
  return OK;
}
Status Push( Linkstack *L, Llist *s )
{ 
	Llist p, q;
    if( !(*L).base )
                                 return ERROR;
    (*L).stacksize++;
    if( (*L).stacksize == 1 )
	 { 
		(*L).base = *s;
	    (*L).base->next = (*L).top;
	} 

	else
	{
	  p=(*L).base ;
      while( p->next!= (*L).top )
		   {             
		     p = p->next;
		   }
      p->next=(*s);
   	 (*s)->next = (*L).top;
	}
  (*L).top->next=NULL;
  return OK;
}
/************************************************/

/******************建立一个空栈*****************/
Status Init_Lstack( Linkstack *L )
{ 
 Llist p;
 p = ( Llist )malloc( sizeof( LNode ) );
 if( p )
 {
  p->next = NULL;
  (*L).base = (*L).top = p;
  (*L).stacksize = 0;
  return OK;
 }
 else
  return ERROR;
}
/*********************************************/

/********************清空栈*******************/
Status Clear_Lstack( Linkstack *L)
{
 Llist p, q;
 if( (*L).base != (*L).top )
 {
  p = q = (*L).base->next;
  (*L).base->next = NULL;
  while( p != (*L).top )
  {
   p = q->next;
   free( q );
   q = p;
  }
  free( p );
  (*L).top = (*L).base;
  (*L).stacksize = 0;
 }
 return OK;
}
/*********************************************/

/***************销毁栈************************/
Status DestoyLinkstack( Linkstack *L )
{
  Llist p;
  Clear_Lstack( L );
 p=(*L).base ;
 free( p );
 p = NULL;
 (*L).top = NULL;
 (*L).stacksize = 0;
 return OK;
}
/*********************************************/
/**************判断栈空**********************/
Status LinkstackEmpty( Linkstack L )
{
 if( L.stacksize )
  return FALSE;
 else
  return TRUE;
}


/**************获取栈顶元素*********/
Status LinkstackGetTop( Linkstack L, Element *e )
{
   Llist q;
   if( L.stacksize==0 )
                                return ERROR;
   q = L.base;
   while( q->next!=L.top)        q=q->next;
                      
  *e=q->data;
  return OK;
}
  
/************************************/
/***********删除栈顶元素*************/


Status LinkstackPop( Linkstack *L, Element *e )
{
 Llist p,q;
 if( (*L).stacksize == 0 )
  return OK;
  p = (*L).top;
  q = (*L).base;
  while( q->next!=p )
                       q=q->next;
  *e=q->data;
  q->next = NULL;
  free( p );
 (*L).top = q;
 (*L).stacksize--;
 return OK;
}