データ構造_P 15

# include 
# include 
# include 
/*
*	   （   ）   ：   、  、  、  、    、  
*	  pBottom              ，       ，        pTop    。
*	2016 6 14 15:12:50
*/

typedef struct Node		//           
{
	int data;
	struct Node* pNext;
}NODE, *PNODE;

typedef struct Stack	//        
{
	PNODE pTop;
	PNODE pBottom;		// ！：      ！
}STACK, *PSTACK;

void init(PSTACK);
void push(PSTACK, int);		//push        ，      ，      
bool pop(PSTACK, int*);			//pop     ，       bool      
void traverse(PSTACK);
bool empty(PSTACK);
void clear(PSTACK);		//clear   (pTop==pBottom)，destroy   (   )

int main(void)
{
	STACK S;	//   （         ）
	int val;	//val    pop    ，      

	init(&S);	//    ， pTop、pBottom  
	traverse(&S);
	push(&S, 1);		//     （  ）
	push(&S, 2);
	push(&S, 3);
	traverse(&S);
	if( pop(&S, &val) )		//  （    ）,    x    val ，         
		printf("pop    ，  %d
", val);
	else
		printf("pop    ！
");

	traverse(&S);		//    
	clear(&S);
	traverse(&S);

	return 0;
}

void init(PSTACK pStack)
{
	pStack->pBottom = (PNODE)malloc(sizeof(NODE));
	if( pStack->pBottom == NULL )
	{
		printf("        ，    ！");
		exit(-1);
	}
	else
	{
		pStack->pBottom = NULL;			//pStack->pBottom->data、pStack->pBottom->pNext  NULL，     
		pStack->pTop = pStack->pBottom;
	}
	return;
}

void push(PSTACK pStack, int val)
{
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if( pNew == NULL )
	{
		printf("        ，    ！");
		exit(-1);
	}
	else
	{
		printf("push    ：%d
", val);
		pNew->data = val;
		pNew->pNext = pStack->pTop;
		pStack->pTop = pNew;
	}
	return;
}

bool pop(PSTACK pStack, int* pVal)
{
	if( empty(pStack) )
	{
//		printf("     ，pop  !");		// !             ，    main   if       
		return false;
	}
	else
	{
		PNODE p = pStack->pTop;
		*pVal = p->data;
		pStack->pTop = p->pNext;
		free(p);
		p = NULL;			//          ，    ！

		return true;
	}
}

void traverse(PSTACK pStack)
{
	printf("       ： ");
	PNODE p = pStack->pTop;

	while( p != pStack->pBottom)	//pStack->pBottom  NULL   
	{
		printf("%d ", p->data);
		p = p->pNext;
	}
	printf("
");
	return;
}

bool empty(PSTACK pStack)
{
	if( pStack->pBottom == pStack->pTop )
		return true;
	else 
		return false;
}

void clear(PSTACK pStack)
{
	if( empty(pStack) )
		return;
	else
	{
		while(pStack->pTop != pStack->pBottom)	//pStack->pBottom  NULL   
		{
			PNODE p = pStack->pTop;
			pStack->pTop = pStack->pTop->pNext;
			free(p);
			p = NULL;
		}
	}	
}