08黑马笔记之栈的应用_就近匹配(括号)
思想：
前提：使用栈的链式存储来实现。
1）遇到左括号就放进栈中，再遇到右括号就将左括号从栈中删除。若栈中没有元素或者不是左括号，则说明右括号匹配失败。以上是判断右括号不匹配的，下面是判断左括号不匹配。
2）若栈中还有元素，说明左括号多了，左括号不匹配。将栈中多余的左括号循环一个个打印出来，按下标显示相应位置。
代码实现：
1）头文件：
#ifndef SEQLINKSTACK
#define SEQLINKSTACK
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//使用企业链表实现，也可传统
typedef struct LINKSNODE{
struct LINKSNODE *next;
}LinkSNode;
//管理链表结构体
typedef struct LINKSTACK{
LinkSNode head;
int size;
}LinkStack;
//链式栈初始化
LinkStack* Init_LinkStack();
//入栈
int Push_LinkStack(LinkStack *lstack,LinkSNode *data);
//出栈
int Pop_LinkStack(LinkStack *lstack);
//判断是否为空
int IsEmpty_LinkStack(LinkStack *lstack);
//返回第一个有效元素
LinkSNode *Top_LinkStack(LinkStack *lstack);
//返回栈大小
int Size_LinkStack(LinkStack *lstack);
//清空链式栈
int Clear_LinkStack(LinkStack *lstack);
//释放内存
int Destory_LinkStack(LinkStack *lstack);
#endif
2).cpp文件：
#include"Seq_LinkStack.h"
//链式栈初始化 ok
LinkStack* Init_LinkStack(){
LinkStack *lstack=(LinkStack*)malloc(sizeof(LinkStack));
lstack->head.next=NULL;
lstack->size=0;
return lstack;
}
//入栈 ok
int Push_LinkStack(LinkStack *lstack,LinkSNode *data){
if(lstack==NULL){
return -1;
}
if(data==NULL){
return -1;
}
//每次都在链表的头结点插入,与顺序栈想反
//所以每次对头结点操作插入
data->next =lstack->head.next;
lstack->head.next=data;
lstack->size++;
return 0;
}
//出栈 ok
int Pop_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
if(lstack->size==0){
return -1;
}
//也是只对头结点操作
//使头结点指向第二个有效节点
LinkSNode *first=lstack->head.next;
lstack->head.next=first->next; //使head指向第二个元素
lstack->size--;
return 0;
}
//判断是否为空
int IsEmpty_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
if(lstack->size==0){
return 1;
}
return 0;
}
//返回第一个有效元素 ok
LinkSNode *Top_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return NULL;
}
if(lstack->size==0){
return NULL;
}
return lstack->head.next;
}
//返回栈大小 ok
int Size_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
return lstack->size;
}
//清空链式栈 ok
int Clear_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
//lstack->head.next=NULL;
lstack->size=0;
return 0;
}
//释放内存
int Destory_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
free(lstack);
return 0;
}
3）主函数测试：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"Seq_LinkStack.h"
typedef struct MYCHAR{
LinkSNode node;
char *addr; //指向括号
int index; //用于保存入栈时的括号的下标
}MyChar;
//判断是否是左括号
bool IsLeft(char p){
return p == '(';
}
//判断是否为右括号
bool IsRight(char p){
return p == ')'; //写错成（
}
//创建一个元素并返回
MyChar* Create_MyChar(char *p,int index){
MyChar *myc=(MyChar*)malloc(sizeof(MyChar));
myc->addr=p;
myc->index=index; //入栈时用于保存括号的下标
return myc;
}
//展示错误 index是错误括号的下标
int ShowError(char *str,int index){
printf("%s\n",str);
for(int i=0;i<index;i++){
printf(" ");
}
printf("A");
return 0;
}
void test01(){
//创建链表
LinkStack *stack=Init_LinkStack();
char *str="1+2+6(dsf)df(((sflp(sdfs)";
char *p=str;
int index=0;
// 1 遍历整个字符串 先将左括号放进栈 然后判断右括号
while(*p != '\0'){
//若是左括号，就通过结构体直接进入链式栈
if(IsLeft(*p)){
//入栈时需要保存括号与其下标
Push_LinkStack(stack,(LinkSNode*)Create_MyChar(p,index));
}
//如果是右括号且栈有元素的话，查看栈中是否为左括号，然后出栈
if(IsRight(*p)){
if(Size_LinkStack(stack)>0){
//获取栈中元素
MyChar *mychar = (MyChar*)Top_LinkStack(stack);
//若是左括号就出栈，不是就出错，展示错误指向该出错点
if(IsLeft(*(mychar->addr))){
Pop_LinkStack(stack);
free(mychar);
}
}
else{ //否则如果栈中没有元素，即！！！size=0,就是出错了，根据下标取打印该括号的位置
printf("右括号不匹配左括号:\n");
ShowError(str,index);
break;
}
}
p++;
index++;
}
// 2 最后若栈中还有元素，就是因为左括号进栈多缺少右括号删除。 然后循环显示后并删除
while(Size_LinkStack(stack)>0){
MyChar *myc=(MyChar*)Top_LinkStack(stack);
printf("左括号没有匹配右括号：\n");
ShowError(str,myc->index); //注意！！！！！是myc->index
Pop_LinkStack(stack);
free(myc);
}
printf("\n");
Destory_LinkStack(stack);
}
int main(){
test01();
return 0;
}
总结就近匹配：与二叉树的非递归遍历思想基本一样。所以下面为了对比也给出二叉树的非递归遍历。
2 二叉树的非递归遍历：
前提：也使用栈的链式存储。
思想：首先将根节点放进栈中，若根节点的标志位falg为1则输出，否则为0就弹出栈，再将其右子节点、左子节点、自己（前序）放进栈中。然后取出栈顶元素判断为1就输出，再对栈的元素判断，不断的输出与放进栈中，直至栈中元素为0.
代码实现：
1）头文件.h：
#ifndef SEQLINKSTACK
#define SEQLINKSTACK
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//使用企业链表实现，也可传统
typedef struct LINKSNODE{
struct LINKSNODE *next;
}LinkSNode;
//管理链表结构体
typedef struct LINKSTACK{
LinkSNode head;
int size;
}LinkStack;
//链式栈初始化
LinkStack* Init_LinkStack();
//入栈
int Push_LinkStack(LinkStack *lstack,LinkSNode *data);
//出栈
int Pop_LinkStack(LinkStack *lstack);
//判断是否为空
int IsEmpty_LinkStack(LinkStack *lstack);
//返回第一个有效元素
LinkSNode *Top_LinkStack(LinkStack *lstack);
//返回栈大小
int Size_LinkStack(LinkStack *lstack);
//清空链式栈
int Clear_LinkStack(LinkStack *lstack);
//释放内存
int Destory_LinkStack(LinkStack *lstack);
#endif
2).cpp文件：
#include"Seq_LinkStack.h"
//链式栈初始化 ok
LinkStack* Init_LinkStack(){
LinkStack *lstack=(LinkStack*)malloc(sizeof(LinkStack));
lstack->head.next=NULL;
lstack->size=0;
return lstack;
}
//入栈 ok
int Push_LinkStack(LinkStack *lstack,LinkSNode *data){
if(lstack==NULL){
return -1;
}
if(data==NULL){
return -1;
}
//每次都在链表的头结点插入,与顺序栈想反
//所以每次对头结点操作插入
data->next =lstack->head.next;
lstack->head.next=data;
lstack->size++;
return 0;
}
//出栈 ok
int Pop_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
if(lstack->size==0){
return -1;
}
//也是只对头结点操作
//使头结点指向第二个有效节点
LinkSNode *first=lstack->head.next;
lstack->head.next=first->next; //使head指向第二个元素
lstack->size--;
return 0;
}
//判断是否为空
int IsEmpty_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
if(lstack->size==0){
return 1;
}
return 0;
}
//返回第一个有效元素 ok
LinkSNode *Top_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return NULL;
}
if(lstack->size==0){
return NULL;
}
return lstack->head.next;
}
//返回栈大小 ok
int Size_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
return lstack->size;
}
//清空链式栈 ok
int Clear_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
//lstack->head.next=NULL;
lstack->size=0;
return 0;
}
//释放内存
int Destory_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
free(lstack);
return 0;
}
3）主函数测试：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"Seq_LinkStack.h"
//定义二叉树节点
typedef struct BINARYNODE{
char ch;
struct BINARYNODE *lchild;
struct BINARYNODE *rchild;
}BinaryNode;
//利用链式栈进行非递归遍历
//栈的节点
typedef struct BINTREESTACKNODE{
LinkSNode node; //挂钩
BinaryNode *root; //二叉树节点
bool flag; //出入栈时是否可输出的标志位
}BinTreeStackNode;
//二叉树的递归遍历 ok 懂了
void Recursion(BinaryNode *root){
if(root==NULL){
return ;
}
//前序遍历 --根左右
printf("%c",root->ch);
Recursion(root->lchild);
Recursion(root->rchild);
return ;
}
//创建栈节点,将二叉树放进栈中
BinTreeStackNode *MyStackNode(BinaryNode *root,bool flag){
BinTreeStackNode *node=(BinTreeStackNode*)malloc(sizeof(BinTreeStackNode));
node->root=root;
node->flag=false;
return node;
}
//二叉树的非递归遍历
int UnRecursion(BinaryNode *root){
//创建栈
LinkStack *stack=Init_LinkStack();
//先创建一个二叉树节点放进栈中
Push_LinkStack(stack,(LinkSNode*)MyStackNode(root,false)); //必须是放带有二叉树节点的节点进去
//循环放与弹出
while(Size_LinkStack(stack)>0){
//先取出栈中元素
BinTreeStackNode *pcur=(BinTreeStackNode*)Top_LinkStack(stack);
Pop_LinkStack(stack); //有这个就不用删除malloc的节点，里面做了
//若二叉树节点为空则不作处理
if(pcur->root==NULL){
continue;
}
//若为真则显示
if(pcur->flag==true){
printf("%c",pcur->root->ch);
}else{
//否则就将它左右子树和本身放进栈中，并且本身变为true
//前序，但因为栈是先进后出所以倒转
Push_LinkStack(stack,(LinkSNode*)MyStackNode(pcur->root->rchild,false));
Push_LinkStack(stack,(LinkSNode*)MyStackNode(pcur->root->lchild,false));
pcur->flag=true;
Push_LinkStack(stack,(LinkSNode*)pcur);
//这四句改一下就是中序，后序
}
}
printf("\n");
return 0;
}
void CreateBinartTree(){
//创建数据节点
BinaryNode node1={'A',NULL,NULL};
BinaryNode node2={'B',NULL,NULL};
BinaryNode node3={'C',NULL,NULL};
BinaryNode node4={'D',NULL,NULL};
BinaryNode node5={'E',NULL,NULL};
BinaryNode node6={'F',NULL,NULL};
BinaryNode node7={'G',NULL,NULL};
BinaryNode node8={'H',NULL,NULL};
//建立节点关系 A-F-G-H
// \B
// \C-E
// \D
node1.lchild=&node2;
node1.rchild=&node6;
node2.rchild=&node3;
node3.lchild=&node4;
node3.rchild=&node5;
node6.rchild=&node7;
node7.rchild=&node8;
//非递归遍历
UnRecursion(&node1);
//递归遍历
Recursion(&node1);
printf("\n");
}
int main(){
CreateBinartTree();
return 0;
}
//总结：这个项目有问题再释放内存那里，但是我分析过了代码应该没有问题才对啊！！！
//懂了，在拷贝时出问题！不能用原来的树的内容给他指向，导致两个二叉树的两个指针指向同一片区域，
//必须新建变量给他新的指向
//总结：名字起得有点长，自己都记不住！！！
