赞
踩
栈是一种先进后出的数据结构。FILO(firt in late out)
逻辑结构:线性结构
基于一个数组配合一个栈顶"指针(数组下标)–top"
顺序栈的本质就是对顺序表操作的一种约束:只能在一端进行插入和删除。
//结构体定义
typedef struct node
{
int data; //此处以int数据为例,可自行修改添加其他成员
}nd_t;
typedef struct stack
{
int top; //顺序栈的"top指针"只需要一个int型数据就可以了,类似于数组下标
nd_t st[N];
}st_t;
int create_stack(stack_t **my_stack);
int create_stack(st_t **my_stack){
if(NULL==my_stack) return -1;
*my_stack=(st_t *)malloc(sizeof(st_t));
if(NULL==*my_stack) return -1;
(*my_stack)->top=0;
return 0;
}
int clean_stack(stack_t *my_stack);
count置0即可
int clean_stack(st_t *my_stack){
if(NULL==my_stack) return -1;
my_stack->top=0;
return 0;
}
int destroy_stack(stack_t **my_stack);
int destroy_stack(st_t **my_stack){
if(NULL==my_stack||NULL==*my_stack) return -1;
free(*my_stack);
*my_stack=NULL;
return 0;
}
int is_full(st_t *my_stack);
int push_stack(stack_t *my_stack, int data);
//满为1,不满为0 int is_full(st_t *my_stack){ if(NULL==my_stack) return -1; return (N==my_stack->top)?1:0; } //入栈 int push_stack(st_t *my_stack, int data){ if(NULL==my_stack) return -1; if(is_full(my_stack)){ printf("栈已满\n"); return -1; } my_stack->st[my_stack->top].data=data; my_stack->top++; return 0; }
int is_empty(st_t *my_stack);
int pop_stack(stack_t *my_stack, int *num);
将栈顶的元素赋值给top
count自减
//空为1,不空为0
int is_empty(st_t *my_stack){
if(NULL==my_stack) return -1;
return (!(my_stack->top))?1:0;
}
int pop_stack(st_t *my_stack, int *num){
if(NULL==my_stack||NULL==num) return -1;
if(is_empty(my_stack)){
printf("栈空\n");
return -1;
}
*num=my_stack->st[my_stack->top-1].data;
my_stack->top--;
return 0;
}
int print_stack(stack_t *my_stack);
int print_stack(st_t *my_stack){
if(NULL==my_stack) return -1;
if(my_stack->top==0){
printf("栈空\n");
return -1;
}
for(int i=0;i<my_stack->top;i++){
printf("%d ",my_stack->st[i].data);
}
putchar(10);
return 0;
}
//链表节点结构体----数据元素
typedef struct _Node{
int data;
struct _Node *next;
}node_t;
//链式栈的结构体----数据对象
typedef struct _Stack{
node_t *top;
int count;//记录栈中元素个数
//.....其他属性信息
}stack_t;
int create_stack(stack_t **my_stack);
int create_stack(stack_t **my_stack){
if(NULL==my_stack) //判断传入参数是否为空
{
return -1;
}
*my_stack=(stack_t *)malloc(sizeof(stack_t));
if(NULL==*my_stack){
return -1;
}
//初始化
(*my_stack)->top=NULL;
(*my_stack)->count=0;
return 0;
}
int push_stack(stack_t *my_stack, int data);
int push_stack(stack_t *my_stack, int data){ if(NULL==my_stack) { return -1; } //申请一个新数据节点 node_t *node=(node_t *)malloc(sizeof(node_t)); if(NULL==node){ return -1; } node->next=my_stack->top; my_stack->top=node; node->data=data; my_stack->count++; return 0; }
int pop_stack(stack_t *my_stack, int *num);
//出栈 int pop_stack(stack_t *my_stack, int *num){ if(NULL==my_stack||NULL==num) { return -1; } if(is_empty(my_stack)){ return -1; } //头删 node_t *pdel=my_stack->top; *num=pdel->data; my_stack->top=pdel->next; free(pdel); pdel=NULL; my_stack->count--; return 0; }
int is_empty(stack_t *my_stack);
int is_empty(stack_t *my_stack){
if(NULL==my_stack)
{
return -1;
}
return (my_stack->count)?0:1;
}
int clean_stack(stack_t *my_stack);
int clean_stack(stack_t *my_stack){
if(NULL==my_stack)
{
return -1;
}
node_t *pdel=NULL;
while(my_stack->top){
pdel=my_stack->top;
my_stack->top=pdel->next;
free(pdel);
}
pdel=NULL;
my_stack->count=0;
return 0;
}
int destroy_stack(stack_t **my_stack);
int destroy_stack(stack_t **my_stack){
if(NULL==my_stack||NULL==*my_stack)
{
return -1;
}
//先清空再销毁
if(clean_stack(*my_stack)){
return -1;
}
free(*my_stack);
*my_stack=NULL;
return 0;
}
int print_stack(stack_t *my_stack);
int print_stack(stack_t *my_stack){ if(NULL==my_stack) { return -1; } if(is_empty(my_stack)){ printf("栈空\n"); return -1; } node_t *ptemp=my_stack->top; for(int i=0;i<my_stack->count;i++) { printf("%d ",ptemp->data); ptemp=ptemp->next; } putchar(10); return 0; }
在终端中输入一个字符串,判断字符串中的括号是否配对。
如果不配对,指出不配对的位置。
遇到左括号 ( [ { 就入栈
遇到右括号 ) ] } 就弹出栈顶元素 判断和当前的右括号是否配对
知道字符串遍历结束 如果栈中为 空 说明配对
记录下标
本代码实在链式栈基础上的应用实例,以下代码仅展示主函数以及部分修改后的链式栈
link_stack.h
//数据元素结构体,即用于存放入栈的左括号
typedef struct _Node{
char data; //此处修改为了char类型数据
int index; //增加下标数据
struct _Node *next;
}node_t;
link_stack.c
//入栈时不仅存储左括号本身,还存放左括号的下标 int push_stack(stack_t *my_stack, char data,int index){ if(NULL==my_stack) { return -1; } //申请一个新数据节点 node_t *node=(node_t *)malloc(sizeof(node_t)); if(NULL==node){ return -1; } node->data=data; //左括号 node->index=index; //左括号下标 node->next=my_stack->top; my_stack->top=node; my_stack->count++; return 0; } //出栈时不仅弹出左括号,还弹出它的下标 int pop_stack(stack_t *my_stack, char *num, int *index){ if(NULL==my_stack||NULL==num||NULL==index) { return -1; } if(is_empty(my_stack)){ return -1; } //头删 node_t *pdel=my_stack->top; *num=pdel->data; //左括号 *index=pdel->index; //下标 my_stack->top=pdel->next; free(pdel); pdel=NULL; my_stack->count--; return 0; }
main.c
#include "link_stack.h" int main(int argc, const char *argv[]) { char str[128]; //输入一个字符串 printf("please input a string:\n"); scanf("%s",str); //创建栈 stack_t *my_stack=NULL; if(!create_stack(&my_stack)) { printf("创建栈失败!\n"); return -1; } int index=0; //遍历字符串的下标 int i=0; //记录错误位置的下标 int j=0; //用于指出错误位置 char c; //记录当前取出的字符 int flag=0; //标记字符串中是否有括号,没有为0 while(str[index]) {//遍历字符串 if(str[index]=='('||str[index]=='['||str[index]=='{') {//遇到左括号 ( [ { 就入栈 flag=1; push_stack(my_stack,str[index],index); }else if(str[index]==')'||str[index]==']'||str[index]=='}') {//遇到右括号 ) ] } 就弹出栈顶元素 判断和当前的右括号是否配对 flag=1; if(is_empty(my_stack)){ goto ERR; } pop_stack(my_stack,&c,&i); switch(str[index]){ case ')': if(c=='(')break; else{ goto ERR; } case ']': if(c=='[')break; else{ goto ERR; } case '}': if(c=='{')break; else{ goto ERR; } } } index++; } if(flag==0){ printf("无括号,无法配对\n"); return -1; } //当字符串结束时,判断栈是否为空 if(is_empty(my_stack)){ printf("配对成功\n"); }else{ pop_stack(my_stack,&c,&i); index=i; goto ERR; } return 0; ERR: for(j=0;j<index;j++) printf(" "); printf("^\n"); printf("配对失败\n"); return 0; }
下载链接:
判断字符串括号是否配对实例代码
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。