数据结构——链栈1（声明、初始化、尾插法入栈、出栈、遍历栈）

以下是数据结构中关于链栈的声明、声明、初始化、入栈、出栈、遍历栈等基础操作（编程风格参考天勤数据结构）。

#include
#include
using namespace std;
//链栈一般视为无满栈状态，所以无需定义链栈最大尺寸

笔记：链栈一般视为无满栈状态，所以无需定义链栈最大尺寸

typedef struct LNode{
	int data;
	LNode *next;//注意这里要写主名LNode不能写别名Lnode 
}Lnode,*Ln;

注意：指向自己同类型的节点，不能写别名

void initial(Ln &L){//等效于Lnode *&ls 是个指针实参（指针实体） 
	L = (LNode*)malloc(sizeof(LNode));//malloc与free配套使用，new与delete配套使用 
	L->next = NULL;
}

因为是给main函数里声明的链表进行初始的分配空间，所以必须把其实体（实参）传入，而不是传入形参。

void push(Ln L,int data){//等效于Lnode *L,将链栈的头位置作为形参传入(指针形参)
	Ln p = L;
	while(p->next!=NULL){
		p = p->next;
	}
	Lnode *newnode = (LNode*)malloc(sizeof(LNode));
	newnode->data = data;
	newnode->next = NULL;
	p->next = newnode;
}

void pushElem(Ln &L){
	int data = 1;
	while(1){
		cout<<"请输入新栈点(输入-1结束输入):";
		cin>>data;
		if(data==-1){
			break;
		}
		push(L,data);
	}
	showLStack(L);
}

步骤：

1. 创建新的节点；
2. 新的节点的next指向null；
3. 给新的节点赋值；
4. 把链表末尾的节点的next指向新节点。
   注意：这里传入的是实参和形参都可以，因为只是对地址进行操作，不需要对其实体进行开辟空间等操作。

void pop(Ln &L,int &x){//因为是删除链表的节点，所以要把链表实体传入 
	Ln p = L;
	if(p->next==NULL){
		cout<<"链栈为空!n"; 
		return ;
	} 
	while(p->next->next!=NULL){
		p = p->next;
	}
	Ln t = p->next;
	x = p->next->data;
	p->next = NULL; 
	free(t);
}

void popElem(Ln &L){
	int x;
	pop(L,x);
	cout<<"出栈成功,本次出栈元素为:"< 
步骤：
 
判断是否为空栈；
如果当前节点下一个节点的下一个节点是空，则说明下一个节点是栈尾；
将下一个节点值提取出来；
释放栈尾；
当前节点next设为null，当前站点变成栈尾。
 
遍历栈 
void showLStack(Ln L){//指针形参 
	Ln p = L;
	if(p->next==NULL){
		cout<<"链栈为空!n"; 
	} 
	p = p->next;//不输出头结点
	while(p!=NULL){
		cout<data<<" ";
		p = p->next;
	}
	cout< 
步骤：
 
判断是否为空栈；
新建指针指向头结点；
指针往下（next）移动一个位置（因为头结点无data无需输出）；
直到指针指向null。
 
运行截图 

 
 
 
源代码 
 
#include
#include
using namespace std;
//链栈一般视为无满栈状态，所以无需定义链栈尺寸

typedef struct LNode{
	int data;
	LNode *next;//注意这里要写主名LNode不能写别名Lnode 
}Lnode,*Ln;


void initial(Ln &L){//等效于Lnode *&ls 指针实参 
	L = (LNode*)malloc(sizeof(LNode));//malloc与free配套使用，new与delete配套使用 
	L->next = NULL;
//	L->data = 0;
}

void showLStack(Ln L){//指针形参 
	Ln p = L;
	if(p->next==NULL){
		cout<<"链栈为空!n"; 
	} 
	p = p->next;//不输出头结点
	while(p!=NULL){
		cout<data<<" ";
		p = p->next;
	}
	cout<//等效于Lnode *L,将链栈的头位置作为形参传入(指针形参)
	Ln p = L;
	while(p->next!=NULL){
		p = p->next;
	}
	Lnode *newnode = (LNode*)malloc(sizeof(LNode));
	newnode->data = data;
	newnode->next = NULL;
	p->next = newnode;
}

void pushElem(Ln &L){
	int data = 1;
	while(1){
		cout<<"请输入新栈点(输入-1结束输入):";
		cin>>data;
		if(data==-1){
			break;
		}
		push(L,data);
	}
	showLStack(L);
}

void pop(Ln &L,int &x){//因为是删除链表的节点，所以要把链表实体传入 
	Ln p = L;
	if(p->next==NULL){
		cout<<"链栈为空!n"; 
		return ;
	} 
	while(p->next->next!=NULL){
		p = p->next;
	}
	Ln t = p->next;
	x = p->next->data;
	p->next = NULL; 
	free(t);
}

void popElem(Ln &L){
	int x;
	pop(L,x);
	cout<<"出栈成功,本次出栈元素为:"<
	int c = 0;
	while(1){
		cout<<"请选择操作:"<>c;
		switch(c){
			case 1:pushElem(L);break;
			case 2:popElem(L);break;
			case 3:showLStack(L);break;
			case 4:return;
			default:;
		} 
	}
}
 
int main(){
	LNode *ls;
	initial(ls);
	menu(ls);
	return 0;
} 

                
                
                
        
        

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