• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

实现栈(链式存储)

算法笔记 站点默认 2个月前 (10-03) 34次浏览 已收录 0个评论
文章目录[隐藏]

自己写的链式栈

#include<bits/stdc++.h>
using namespace std; 
//自己写的链式栈
//要实现的操作有: 初始化栈initstack  , 销毁栈destroystack  , 判断栈空emptystack
// 取栈顶元素 gettop   进栈pushstack , 出栈popstack  ,   打印栈元素printstack 
typedef struct linknode{
	int data;
	struct linknode *next;
}sqstack;
void initstack(sqstack*&st){
	st=(sqstack*)malloc(sizeof(sqstack));
	st->next=NULL;
} 
void destroystack(sqstack*&st){
	sqstack *pre=st,*p=st->next;
	while(p){
		free(pre);
		pre=p;
		p=pre->next;
	}
	free(pre);
}
bool emptystack(sqstack*st){
	return(st->next==NULL);
}
int gettop(sqstack*st){//栈空的时候请不要用这个函数 
	return st->next->data;
}
void pushstack(sqstack*&st,int e){
	sqstack*p;
	p=(sqstack*)malloc(sizeof(sqstack));
	p->data=e;
	p->next=st->next;
	st->next=p;
}
bool popstack(sqstack*&st){
	if(st->next==NULL)
	return false;
//	st->next=st->next->next;
//	free(st->next);
//	return true;
	sqstack *p;
	p=st->next;  //p指向首结点 
	st->next=p->next;//删除首结点 
	free(p);
	return true;
}
void printstack(sqstack*st){
	st=st->next;//栈的头结点是没有数据的 
	while(st){
		cout<<st->data<<" ";
		st=st->next;
	}
}
int main(){
	sqstack *st;
	initstack(st);
	for(int i=1;i<=10;i++)
	pushstack(st,i);
	popstack(st);
	printstack(st);
	int bl=emptystack(st);
	cout<<bl; 
}

标准栈结构(链式)

//链栈基本运算算法
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct linknode
{	
	ElemType data;				//数据域
	struct linknode *next;		//指针域
} LinkStNode;					//链栈类型
void InitStack(LinkStNode *&s)
{
	s=(LinkStNode *)malloc(sizeof(LinkStNode));
	s->next=NULL;
}
void DestroyStack(LinkStNode *&s)
{
	LinkStNode *p=s->next;
	while (p!=NULL)
	{	
		free(s);
		s=p;
		p=p->next;
	}
	free(s);	//s指向尾结点,释放其空间
}
bool StackEmpty(LinkStNode *s)
{
	return(s->next==NULL);
}
void Push(LinkStNode *&s,ElemType e)
{	LinkStNode *p;
	p=(LinkStNode *)malloc(sizeof(LinkStNode));
	p->data=e;				//新建元素e对应的结点p
	p->next=s->next;		//插入p结点作为开始结点
	s->next=p;
}
bool Pop(LinkStNode *&s,ElemType &e)
{	LinkStNode *p;
	if (s->next==NULL)		//栈空的情况
		return false;
	p=s->next;				//p指向开始结点
	e=p->data;
	s->next=p->next;		//删除p结点
	free(p);				//释放p结点
	return true;
}
bool GetTop(LinkStNode *s,ElemType &e)
{	if (s->next==NULL)		//栈空的情况
		return false;
	e=s->next->data;
	return true;
}

括号配对

例子3-5:设计一个算法判断输入的表达式中括号是否配对(假设只有左右,圆括号)


思路很明确,题目只设计圆括号,我觉得还可以加上方括号和❀括号,遇到左括号就进栈,遇到右括号就判断栈顶元素是否和它匹配,匹配就出栈,
这里我用自己写的栈代码来写,顺便看看自己写的栈有没有错误

//自己写的链式栈
//要实现的操作有: 初始化栈initstack  , 销毁栈destroystack  , 判断栈空emptystack
// 取栈顶元素 gettop   进栈pushstack , 出栈popstack  ,   打印栈元素printstack 
#include<bits/stdc++.h>
using namespace std; 
typedef struct linknode{
	char data;
	struct linknode *next;
}sqstack;
void initstack(sqstack*&st){
	st=(sqstack*)malloc(sizeof(sqstack));
	st->next=NULL;
} 
void destroystack(sqstack*&st){
	sqstack *pre=st,*p=st->next;
	while(p){
		free(pre);
		pre=p;
		p=pre->next;
	}
	free(pre);
}
bool emptystack(sqstack*st){
	return(st->next==NULL);
}
char gettop(sqstack*st){//栈空的时候请不要用这个函数 
	return st->next->data;
}
void pushstack(sqstack*&st,char e){
	sqstack*p;
	p=(sqstack*)malloc(sizeof(sqstack));
	p->data=e;
	p->next=st->next;
	st->next=p;
}
bool popstack(sqstack*&st){
	if(st->next==NULL)
	return false;
//	st->next=st->next->next;
//	free(st->next);
//	return true;
	sqstack *p;
	p=st->next;  //p指向首结点 
	st->next=p->next;//删除首结点 
	free(p);
	return true;
}
void printstack(sqstack*st){
	st=st->next;//栈的头结点是没有数据的 
	while(st){
		cout<<st->data<<" ";
		st=st->next;
	}
}
int main(){
	string s;
	cin>>s;
	sqstack *st;
	char ss;
	int bl=1;
	initstack(st);
	for(int i=0;i<s.length();i++){
		if(s[i]=='('||s[i]=='['||s[i]=='{')
		pushstack(st,s[i]);
		if(s[i]==')'){
				if(emptystack(st)){
				bl=0;
				break;
			}
			ss=gettop(st);
			if(ss=='(')
			popstack(st);
			else{
				bl=0;
				break;
			}	
		}
		if(s[i]==']'){
					if(emptystack(st)){
				bl=0;
				break;
			}
			ss=gettop(st);
		
			if(ss=='[')
			popstack(st);
			else{
				bl=0;
				break;
			}	
		}
		if(s[i]=='}'){
					if(emptystack(st)){
				bl=0;
				break;
			}
			ss=gettop(st);
			if(ss=='{')
			popstack(st);
			else{
				bl=0;
				break;
			}	
		}
	}
	if(!emptystack(st))
	bl=0;
	if(bl)
	cout<<"true"<<endl;
	else
	cout<<"false"<<endl;
}

标准答案(只判断了圆括号

//【例3.5】的算法:判断表达式中的括号是否配对
#include "listack.cpp"
#include <string.h>
bool Match(char exp[],int n)
{
	int i=0; char e;
	bool match=true;
	LinkStNode *st;
	InitStack(st);						//初始化栈
	while (i<n && match)				//扫描exp中所有字符
	{
		if (exp[i]=='(')				//当前字符为左括号,将其进栈
			Push(st,exp[i]);
		else if (exp[i]==')')			//当前字符为右括号
		{
			if (GetTop(st,e)==true)
			{	
				if (e!='(')				//栈顶元素不为'('时表示不匹配
					match=false;
				else
					Pop(st,e);			//将栈顶元素出栈
			}
			else  match=false;			//无法取栈顶元素时表示不匹配
		}
		i++;							//继续处理其他字符
	}
	if (!StackEmpty(st))				//栈不空时表示不匹配
		match=false;
	DestroyStack(st);					//销毁栈
	return match;
}

int main()
{
	char exp[]="(1+2*(5+3)/2)";
	if (Match(exp,strlen(exp))==1)
		printf("表达式%s括号配对\n",exp);
	else
		printf("表达式%s括号不配对\n",exp);
	return 1;
}

栈的应用二:逆波兰数


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:实现栈(链式存储)
喜欢 (2)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到