文章目录
- 顺序表，链表的有点和缺点
- 链表
- 顺序表
- 栈和队列
- 栈的实现
- 栈的应用（括号匹配问题）
顺序表，链表的有点和缺点
链表
顺序表
栈和队列
栈的实现
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
//定义栈的类型
typedef int STDataType;typedef struct stack
{STDataType* a;int top;int capacity;
}ST;//函数接口的声明
void STInit(ST* pst);
void STDestory(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);
STDataType STTop(ST* pst);
在对栈初始化时我们需要考虑top的值初始化为多少，如果初始化为-1指向的就是栈顶的元素，初始化为0指向的就是栈顶元素的下一个位置。
栈的接口实现：
#include "Stack.h"
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = pst->top = 0;
}
void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}
void STPush(ST* pst, STDataType x)
{assert(pst);//考虑扩容if (pst->capacity == pst->top){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//当a为空指针时，realloc的作用和malloc的作用一样STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp==NULL){perror("realloc failed");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top++] = x;
}
void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst->top--;
}
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}
int STSize(ST* pst)
{assert(pst);return pst->top;
}
STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst->a[(pst->top) - 1];
}
栈的应用（括号匹配问题）
bool isValid(char * s){//首先初始化一个栈ST st;//初始化栈STInit(&st);while(*s){//遇到左括号进栈if(*s=='('||*s=='{'||*s=='['){STPush(&st,*s);}else //遇到右括号，退栈{//如果此时的栈为空，即没有左括号，括号不匹配，返回falseif(STEmpty(&st)){STDestory(&st);return false;}char top = STTop(&st);STPop(&st);if((top=='('&&*s!=')')||(top=='{'&&*s!='}')||(top=='['&&*s!=']')){STDestory(&st);return false;}} s++;}//销毁栈bool ret = STEmpty(&st);STDestory(&st);if(ret){STDestory(&st);return true;}return false;
}
队列的实现见下一篇。
本文链接：https://my.lmcjl.com/post/1853.html
展开阅读全文
4 评论