欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

王道数据结构:栈顺序存储和链式存储以及基本操作的实现(C语言版)

程序员文章站 2022-06-05 14:47:26
...

只允许在一端进行插入或删除操作的线性表。

对于n个不同元素进栈,出栈序列的个数为(卡特兰数)

王道数据结构:栈顺序存储和链式存储以及基本操作的实现(C语言版)

顺序栈基本操作的实现代码如下:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MaxSize 10
//栈的顺序存储 
typedef struct {
	int data[MaxSize];
	int top;	
}SqStack;
//初始化栈 
void InitStack(SqStack &s){
	s.top=-1;
	for(int i=0;i<10;i++){
		s.data[i]=0;
	}
	printf("初始化完毕\n");
}
//判空 
void StackEmpty(SqStack s){
	if(s.top==-1){
		printf("栈为空\n");
	}else{
		printf("栈不为空\n");
	}
}
//入栈 
bool Push(SqStack &s,int e){
	if(s.top==MaxSize-1){
		printf("栈已满\n"); 
		return false;
	}
	s.data[++s.top]=e;
	return true;
}
//出栈 
bool Pop(SqStack &s,int &e){
	if(s.top==-1){
		printf("栈已空\n");
		return false;
	}
	e=s.data[s.top--];
	printf("出栈栈顶元素,值为%d\n",e);
	return true;
}
//获取栈顶元素 
bool GetTop(SqStack &s,int &x){
	if(s.top==-1){
		printf("栈为空\n");
		return false;
	}
	x=s.data[s.top];
	printf("栈顶元素为:%d\n",x);
	return true;
}
//打印栈 
void PrintStack(SqStack s){
	if(s.top==-1){
		for(int i=0;i<10;i++){
			//printf("|       |\n");
			printf("|_ _ _ _|\n");
		}
	}
	if(s.top!=-1){
		for(int i=0;i<MaxSize-s.top;i++){
			printf("|_ _ _ _|\n");
		}
		while(s.top!=-1){
			printf("|___%d___|\n",s.data[s.top]);
			s.top--;
		}
	}
}
int main(){
	SqStack s;
	InitStack(s);
	StackEmpty(s);
	Push(s,1);
	Push(s,2);
	Push(s,3);
	Push(s,4);
	StackEmpty(s);
	PrintStack(s);
	int e,x;
	Pop(s,e);
	PrintStack(s);
	GetTop(s,x);
}

代码运行截图如下:

王道数据结构:栈顺序存储和链式存储以及基本操作的实现(C语言版)

链式栈基本操作的实现代码如下:

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

//栈的链式存储
typedef struct Linknode{
	int data;
	struct Linknode *next;
}Linknode,*LiStack; 

//初始化栈 
void InitStack(LiStack &L){
	L =(Linknode*)malloc(sizeof(Linknode));//创建头节点 
	L->next=NULL;//初始化为空	
}

//栈判空 
bool StackEmpty(LiStack L){
	if(L->next==NULL){
		printf("栈为空\n");
		return false;
	}
	else{
		printf("栈不为空\n");
		return true;
	}
}

//入栈 
bool Push(LiStack &L,int e){
 Linknode *s=(Linknode *)malloc(sizeof(Linknode));
 s->data=e;
 s->next=L->next;
 L->next=s; 
 return true;

}

//出栈 
bool Pop(LiStack &L,int &e){
	if(L->next==NULL){
		printf("栈已空\n");
		return false;
	}
	Linknode *p=L->next;
	e=p->data;
	L->next=p->next;//成链 
	printf("出栈元素值为%d\n",e);
	free(p);
	return true;
} 
bool GetTop(LiStack L,int x){
		if(L->next==NULL){
		printf("栈已空\n");
		return false;
	}
	Linknode *p=L->next;
	x=p->data;
	printf("栈顶元素值为%d\n",x);
	return true;
}
void PrintStack(LiStack L){
	Linknode *n=L->next;
	while(n!=NULL){
		printf("|___%d___|\n",n->data);
		n=n->next;
	}
}
int main(){
	LiStack s;
	InitStack(s);
	StackEmpty(s);
	Push(s,1);
	Push(s,2);
	Push(s,3);
	Push(s,4);
	StackEmpty(s);
	PrintStack(s);
	int e,x;
	Pop(s,e);
	PrintStack(s);
	GetTop(s,x);
} 

代码运行截图如下:

王道数据结构:栈顺序存储和链式存储以及基本操作的实现(C语言版)

 

相关标签: 数据结构