数据结构——链栈3（声明、（无头结点）初始化、头插法入栈、出栈、遍历栈）

以下是数据结构中关于无头结点链栈的声明、初始化、头插法入栈、出栈、遍历栈等基础操作（编程风格参考严蔚敏数据结构）。

经过头插法生成的无头结点链栈长这样：

#include
#include
using namespace std;
#define ElemType char
#define Status int//表示状态 
#define OK 1
#define ERROR 0

typedef struct StackNode{
	ElemType data;
	StackNode *next;
}StackNode,*LinkStack;

Status initial(LinkStack &S){
	S = NULL;
}

因为没有头结点，链栈第一个栈点直接设为null（具体原因看下面头插法的解释说明）

Status push(LinkStack &S,ElemType data){
	LinkStack p = new StackNode;
	p->data = data;
	p->next = S;
	S = p;
	return OK;
}

void pushElem(LinkStack &S){
	ElemType data = '0';
	while(1){
		cout<<"请输入新栈点(输入/结束输入):";
		cin>>data;
		if(data=='/'){
			break;
		}
		if(!push(S,data)){
			cout<<"入栈失败n";
		}
	}
	showLStack(S);
}

步骤：

1. 声明一个新栈点p；
2. 给p赋值；
3. p的next指向最初的栈点S；
4. 将p赋值给S（即：p变为S）。

画出来是这样的：
S;
p1->next = S;
(S=p1后)：S->S1（S1对应上一行的S）;
p2->next = S;
(S=p2后)：S->S2->S1（S1对应最初的S，S2是刚才的p1，S是刚才的p2）

Status pop(LinkStack &S,ElemType &data){
	if(S==NULL){//如果栈空 
		return ERROR;
	}
	data = S->data;
	LinkStack p = S;//出栈栈点 
	S = S->next;
	free(p);
	return OK; 
}

void popElem(LinkStack &S){
	ElemType data;
	if(!pop(S,data)){
		cout<<"出栈失败!栈空!n";
	}else{
		cout<<"出栈成功,出栈元素为:"< 
步骤：
 
提取出栈顶的值；
声明新的中间栈点并将栈顶赋给中间栈点（作为出栈栈点）
栈顶栈点指向下一个栈点；
将出栈栈点释放。
 
遍历栈 
void showLStack(LinkStack S){
	LinkStack p = S;
	if(p==NULL){
		cout<<"链栈为空!n"; 
		return ;
	} 
	while(p!=NULL){
		cout<data<<" ";
		p = p->next;
	}
	cout<<"|base"< 
直接从头遍历到尾即可。
 
源代码 
 
#include
#include
using namespace std;
#define ElemType char
#define Status int//表示状态 
#define OK 1
#define ERROR 0

typedef struct StackNode{
	ElemType data;
	StackNode *next;
}StackNode,*LinkStack;

Status initial(LinkStack &S){
	S = NULL;
}

void showLStack(LinkStack S){
	LinkStack p = S;
	if(p==NULL){
		cout<<"链栈为空!n"; 
		return ;
	} 
	while(p!=NULL){
		cout<data<<" ";
		p = p->next;
	}
	cout<<"|base"<
	LinkStack p = new StackNode;
	p->data = data;
	p->next = S;
	S = p;
	return OK;
}

void pushElem(LinkStack &S){
	ElemType data = '0';
	while(1){
		cout<<"请输入新栈点(输入/结束输入):";
		cin>>data;
		if(data=='/'){
			break;
		}
		if(!push(S,data)){
			cout<<"入栈失败n";
		}
	}
	showLStack(S);
}

Status pop(LinkStack &S,ElemType &data){
	if(S==NULL){//如果栈空 
		return ERROR;
	}
	data = S->data;
	LinkStack p = S;//出栈栈点 
	S = S->next;
	free(p);
	return OK; 
}

void popElem(LinkStack &S){
	ElemType data;
	if(!pop(S,data)){
		cout<<"出栈失败!栈空!n";
	}else{
		cout<<"出栈成功,出栈元素为:"<
	int c = 0;
	while(1){
		cout<<"请选择操作:"<>c;
		switch(c){
			case 1:pushElem(S);break;
			case 2:popElem(S);break;
			case 3:showLStack(S);break;
			case 4:return;
			default:;
		} 
	}
}

int main(){
	StackNode *LS;
	if(initial(LS)){
		cout<<"无头结点链栈初始化成功n";
	}
	menu(LS);
	return 0;
}

                
                
                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！