数据结构~09.顺序栈和链栈的应用

你的名字 2023-03-02 10:21 3阅读 0赞

# 数据结构~09.顺序栈和链栈的应用 #

## [本文是上一篇文章的后续,详情点击该链接~][Link 1] ##

## 例1 ##

编写算法:判断一个表达式的括号是否正确配对,表达式已经存入字符数组arr\[ \]中,表达式中的字符个数为n。

#include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE 100
    //顺序栈的定义
    typedef struct { 
    	char data[MAXSIZE];		//存放栈中元素,MAXSIZE是已经定义的常量
    	int top;				//栈顶指针
    }SqStack;					//顺序栈结点定义
    
    //初始化栈
    void initStack(SqStack& stack) { 
    	stack.top = -1;		//初始化一个栈,只需将栈顶指针置为 -1 即可
    }
    
    //判断栈空
    int isEmpty(SqStack stack) { 
    	return stack.top == -1 ? 1 : 0;
    }
    
    //进栈
    int push(SqStack& stack, char x) { 
    	//如果栈满了,则不能进栈
    	if (stack.top == MAXSIZE - 1) { 
    		return 0;
    	}
    	//先移动指针,再进栈
    	++(stack.top);
    	stack.data[stack.top] = x;
    	return 1;
    }
    
    //判断是否匹配
    
    int match(char exp[], int n) { 
    	//创建栈
    	SqStack Temp;
    	//初始化
    	initStack(Temp);
    	int i;
    	for (i = 0; i < n; i++) { 
    		//如果遇到了 ( 就存到栈里面
    		if (exp[i] == '(') { 
    			push(Temp, exp[i]);
    		}
    		//如果遇到了 ) 我们就判断
    		if (exp[i] == ')') { 
    			//假如栈是空,就说明前面没有遇到 ( 那就说明不匹配,返回0
    			return isEmpty(Temp) == 1 ? 0 : 1;//如果遇到了的话,那就说明匹配。返回 1
    		}
    	}
    	//如果没有遇到 ) 那就说明不匹配返回 0
    	return 0;
    }
    
    //统计字符串的长度
    
    int Count(char* arr) { 
    	int i = 0, n = 0;
    	for (i = 0; arr[i - 1] != NULL; i++) { 
    		n++;
    	}
    	return n;
    }
    
    int main(int argc, char* argv[]) { 
    	int i = 1, x = 0, n = 0;
    	//赋值
    	char arr[] = "你好(我是黄贵根)";
    	//统计字符数组的大小
    	n = Count(arr);
    
    	printf("用来验证的字符串: %s \n", arr);
    	//现在进行验证
    	int flag = match(arr, n);
    	printf("是否匹配: 1/0 : %d\n ", flag);
    	getchar();
    	return 0;
    }

## 例2 ##

编写一个函数,求后缀式的数值,其中后缀式存于一个字符数组exc中,exc中最后一个字符为"\\0"作为结束符，并且假设后缀式中的数字都只有一位。

##### 分析: #####

当遇到数值的时候入栈,当遇到运算符的时候连续两次出栈。将两个出栈元素结合运算符进行运算,将结果当成新遇到的数值入栈。如此往复,直到扫描到终止符"\\0"。此时栈底元素的值为表达式的值。

#include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE 100
    //顺序栈的定义
    typedef struct { 
    	int data[MAXSIZE];		//存放栈中元素,MAXSIZE是已经定义的常量
    	int top;				//栈顶指针
    }SqStack;					//顺序栈结点定义
    
    //初始化栈
    void initStack(SqStack& stack) { 
    	stack.top = -1;		//初始化一个栈,只需将栈顶指针置为 -1 即可
    }
    
    //判断栈空
    int isEmpty(SqStack stack) { 
    	return stack.top == -1 ? 1 : 0;
    }
    
    //进栈
    int push(SqStack& stack, int x) { 
    	//如果栈满了,则不能进栈
    	if (stack.top == MAXSIZE - 1) { 
    		return 0;
    	}
    	//先移动指针,再进栈
    	++(stack.top);
    	stack.data[stack.top] = x;
    	return 1;
    }
    
    //出栈
    int pop(SqStack& stack) { 
    	//用来保存被删除的元素
    	int x = 0;
    	//如果栈空则不能出栈
    	if (stack.top == -1) { 
    		return 0;
    	}
    	//先取出元素,再移动指针
    	x = stack.data[stack.top];
    	--(stack.top);
    	//返回被删除的元素
    	return x;
    }
    
    //运算函数
    int operation(int a,char op,int b) { 
    	if (op == '+') return a + b;
    	if (op == '-') return a - b;
    	if (op == '*') return a * b;
    	
    	if (op == '/') { 
    		//被除数不能为0!
    		if (b == 0) { 
    			printf("error");
    			return 0;
    		}
    		else { 
    			return a / b;
    		}
    	}
    }
    //后缀式函数运算
    int suffix(char exp[]) { 
    	int i, a, b, c;
    	//定义栈并初始化
    	SqStack stack;	initStack(stack);
    	//OP用来取消运算符
    	char OP;
    	for (i = 0; exp[i] != '\0'; i++) { 
    		//如果遇到了操作数,那么就入栈等待处理。体现了栈的记忆功能。
    		if (exp[i] >= '0' && exp[i] <= '9') { 
    			//入栈
    			push(stack,(exp[i] - '0')); //字符型和整型的转换
    		}
    		else { 
    			//如果遇到运算符,则说明前边待处理的数字处理条件已经具备
    			OP = exp[i];	//取运算符
    			b = pop(stack);	//取第二个运算符
    
    			a = pop(stack);	//取第一个操作符
    			c = operation(a,OP,b);
    			//运算结果入栈
    			push(stack,c);
    		}
    	}
    	return stack.data[stack.top];
    }
    int main(int argc, char* argv[]) { 
    	char arr[] = "23*";
    	int result = suffix(arr);
    	printf("result = %d",result);	//结果是6
    	getchar();
    	return 0;
    }

## 例3 ##

用不带头节点的单链表存储链栈,设计初始化栈,判断栈是否为空，进栈和出栈等相应的算法。

#include<stdio.h>
    #include<stdlib.h>
    //链栈结点定义
    typedef struct StackNode { 
    	int data;					//数据域
    	struct StackNode* next;			//指针域
    }StackNode;
    //初始化栈
    void initStack(StackNode *&stack) { 
    	stack = NULL;
    }
    //判断是否为空
    int isEmpty(StackNode *stack) { 
    	return stack == NULL ? 1 : 0;
    }
    //进栈
    void push(StackNode *&list, int x) { 
    	StackNode* p;
    	p = (StackNode*)malloc(sizeof(StackNode));
    	p->next = NULL;
    	p->data = x;
    	//增加结点操作
    	p->next = list;
    	list = p;
    }
    //出栈
    int pop(StackNode *&stack) { 
    	int x;
    	//栈空的情况
    	if (isEmpty(stack) == 1) { 
    		return -1;
    	}
    	//删除结点操作
    	x = stack->data;
    	stack = stack->next;
    	return x;
    }
    //遍历栈
    void Print(StackNode *stack) { 
    	if (isEmpty(stack) == 1) { 
    		printf("[ ]");
    	}
    	StackNode* temp = stack;
    	while (temp != NULL) { 
    		//判断是否到了最后一个元素
    		if (temp->next != NULL) { 
    			printf("%d -> ",temp->data);
    		}
    		else { 
    			printf("%d",temp->data);
    		}
    		temp = temp->next;
    	}
    	printf("\n");
    }
    int main(int argc,char*argv[]) { 
    	//创建栈
    	StackNode* stack;
    	//初始化
    	initStack(stack);
    	//进栈
    	int i,n;
    	for (i = 1; i < 10; i++) { 
    		push(stack,i);
    	}
    	//遍历
    	Print(stack);
    	//出栈
    	n = pop(stack);
    	printf("被删除的元素: %d \n",n);
    	Print(stack);
    }

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/107631321