_DataStructure_C_Impl:鏈棧

_DataStructure_C_Impl:鏈棧

//_DataStructure_C_Impl:鏈棧
#include
#include

typedef char DataType;
typedef struct node{
	DataType data;
	struct node *next;
}LStackNode,*LinkStack;
//將鏈棧初始化為空。動態生成頭結點，並將頭結點的指針域置為空
void InitStack(LinkStack *top){
	if((*top=(LinkStack)malloc(sizeof(LStackNode)))==NULL)		//為頭結點分配一個存儲空間
		exit(-1);
	(*top)->next=NULL;		//將鏈棧的頭結點指針域置為空
}
//判斷鏈棧是否為空，就是通過判斷頭結點的指針域是否為空
int StackEmpty(LinkStack top){
	if(top->next==NULL)		//當鏈棧為空時，返回1；否則返回0
		return 1;
	else 
		return 0;
}
//進棧操作就是要在鏈表的第一個結點前插入一個新結點，進棧成功返回1
int PushStack(LinkStack top,DataType e){
	LStackNode *p;	//指針p指向新生成的結點
	if((p=(LStackNode *)malloc(sizeof(LStackNode)))==NULL){
		printf(內存分配失敗
);
		exit(-1);
	}
	p->data=e;
	p->next=top->next;	//指針p指向表頭結點
	top->next=p;
	return 1;
}
//刪除單鏈表中的第i個位置的結點。刪除成功返回1，失敗返回0
int PopStack(LinkStack top,DataType *e){
	LStackNode *p;
	p=top->next;
	if(!p){		//判斷鏈棧是否為空
		printf(棧已空
);
		return 0;
	}
	top->next=p->next;	//將棧頂結點與鏈表斷開，即出棧
	*e=p->data;		//將出棧元素賦值給e
	free(p);		//釋放p指向的結點
	return 1;
}
//取棧頂元素操作
int GetTop(LinkStack top,DataType *e){
	LStackNode *p;
	p=top->next;
	if(!p){		//判斷鏈棧是否為空
		printf(棧已空
);
		return 0;
	}
	*e=p->data;	//將棧頂元素賦值給e
	return 1;
}
//求表長操作
int StackLength(LinkStack top){
	LStackNode *p;
	int count=0;
	p=top;
	while(p->next!=NULL){
		p=p->next;
		count++;
	}
	return count;
}
//銷毀鏈棧操作
void DestroyStack(LinkStack top){
	LStackNode *p,*q;
	p=top;
	while(!p){
		q=p;
		p=p->next;
		free(q);
	}
}
void main_LinkStack(){
	LinkStack S;
	DataType ch[50],e,*p;
	InitStack(&S);
	printf(請輸入進棧的字符：
);
	gets(ch);
	p=&ch[0];
	while(*p){
		PushStack(S,*p);
		p++;
	}
	printf(當前棧頂的元素是：);  
	if(GetTop(S,&e)==0){
		printf(棧已空！
);
		return ;
	}else{
		printf(%4c
,e);
	}
	printf(當前棧中的元素個數是：%d
,StackLength(S));
	printf(元素出棧的序列是：);
	while(!StackEmpty(S)){
		PopStack(S,&e);
		printf(%4c,e);
	}
	printf(
);
	system(pause);
}
//********************************
int Match(DataType e,DataType ch){
	if(e=='('&&ch==')')
		return 1;
	else if(e=='['&&ch==']')
		return 1;
	else if(e=='{'&&ch=='}')
		return 1;
	else
		return 0;
}
void main_Match(){
	LinkStack S;
	char *p;
	DataType e;
	DataType ch[100];
	InitStack(&S);
	printf(請輸入帶括號的表達式('{}','[]','()').
);
	gets(ch);
	p=ch;
	while(*p){
		switch(*p){
		case '(':
		case '[':
		case '{':
			PushStack(S,*p++);
			break;
		case ')':
		case ']':
		case '}':
			if(StackEmpty(S)){
				printf(缺少左括號.
);
				return;
			}else{
				GetTop(S,&e);
				if(Match(e,*p))
					PopStack(S,&e);
				else{
					printf(左右括號不配對.
);
					return;
				}
			}
		default:
			p++;
		}
	}
	if(StackEmpty(S))
		printf(括號匹配.
);
	else
		printf(缺少右括號.
);
	system(pause);
}
//===========
void main(){
	main_LinkStack();
	main_Match();
}