データ構造——チェーンスタックの実現(C言語)

スタックの順序格納の効率が低いことはよく知られています.削除や挿入には不便です.スタックのチェーンは動作が便利であり、チェーンスタックのポインタドメインポインタの方向を変えるだけで、データ項目を移動する必要がない.チェーンスタックはスタックの一番上でしか操作できません.つまり、スタックの一番上にしか入れないということです.
以下はソースプログラムです.
関数宣言:

#ifndef Stack_H
#define Stack_H

typedef int Item;
typedef struct node * PNode;
typedef struct node
{
	Item data;
	PNode next;
}Node;

typedef struct stack *PStack;
typedef struct stack
{
	Item size;
	PNode top;
}Stack;

/***    ，     ***/
PStack Creat_Stack();

/***       ***/
int Is_Empty(PStack);

/***     ***/
PStack Push_Stack(PStack,Item);

/***      ***/
int Size_Stack(PStack);

/***       ***/
Item Get_Item_Stack(PStack);

/***     ***/
Item Pop_Stack(PStack);

/***    ***/
void Clear_Stack(PStack);

/***   ，         ***/
void Traverse_Stack(PStack);
#endif

関数定義:

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

/***    ，     ***/
PStack Creat_Stack()
{
	PStack P=(PStack)malloc(sizeof(Stack));
	if(NULL!=P)
	{
		P->top=NULL;
		P->size=0;
	}
	return P;
}

/***       ***/
int Is_Empty(PStack P)
{
	if(0==P->size && NULL==P->top)
		return 1;
	else
		return 0;
}

/***     ***/
PStack Push_Stack(PStack P,Item val)
{
	PNode PNew=(PNode)malloc(sizeof(Node));
	if(NULL==PNew)
	{
		printf("Malloc the PNew is failed.
");
		exit(1);
	}
	else
	{
		PNew->data=val;
		PNew->next=P->top;
		P->top=PNew;
		P->size++;
	}
	return P;
}

/***      ***/
int Size_Stack(PStack P)
{
	/*int size=0;
	PNode PCurrent=(PNode)malloc(sizeof(Node));
	PCurrent=P->top;
	while(NULL!=PCurrent)
	{
		size++;
		PCurrent=PCurrent->next;
	}
	return size;*/
	return P->size;
}

/***       ***/
Item Get_Item_Stack(PStack P)
{
	if(NULL!=P->top->data && Is_Empty(P)==0)
		return P->top->data;
}

/***     ***/
Item Pop_Stack(PStack P)
{
	Item data;
	PNode temp=P->top;
	if(NULL==temp)
	{
		printf("The stack is empty.
");
		exit(1);
	}
	data=temp->data;
	P->top=temp->next;
	P->size--;
	free(temp);
	return data;
}

/***    ***/
void Clear_Stack(PStack P)
{
	if(Is_Empty(P))
		printf("The stack had enpty.
");
	PNode PCurrent=P->top;
	int i=P->size;
	while(i--)
	{
		P->top=PCurrent->next;
		P->size--;
		free(PCurrent);
		PCurrent=P->top;
	}
}

/***   ，         ***/
void Traverse_Stack(PStack P)
{
	 PNode PCurrent = P->top;  
    int i = P->size; 
	printf("The data of stack are:");
    while(i--)  
    {  
        printf("%d  ",PCurrent->data);  
        PCurrent = PCurrent->next;  
    } 
	printf("
");
}

プログラムテスト:

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

int main()
{
	int size=0;
	int top_data,Pop_data;
	PStack PS;
	PS=Creat_Stack();
	if(NULL!=PS)
		printf("The stack is created.
");

/***       ***/
	if(Is_Empty(PS))
		printf("The stack is empty.
");

/***     ***/
	Push_Stack(PS,2);
	Push_Stack(PS,3);
	Push_Stack(PS,5);
	Traverse_Stack(PS);

/***      ***/
	size=Size_Stack(PS);
	printf("The length of stack is: %d
",size);
	
/***       ***/
	top_data=Get_Item_Stack(PS);
	printf("The top of data is: %d
",top_data);

/***     ***/
	Pop_data=Pop_Stack(PS);
	printf("The Pop of data is: %d
",Pop_data);
	Traverse_Stack(PS);

/***    ***/
	Clear_Stack(PS);
	Traverse_Stack(PS);
	
	return 0;
}