一般做网站需要多少钱,wordpress博客怎么搜索,wordpress推荐适合seo的主题,wordpress的分享插件20. 有效的括号 判断左右括号是否匹配#xff0c;匹配返回true#xff0c;不匹配返回false 通过栈来实现#xff0c;类型和顺序#xff0c;数量都要匹配 控制数量通过size 每个右括号都要找最近的左括号去判断类型匹配不匹配#xff0c;顺序匹配不匹配 最后来判断数量匹配…20. 有效的括号 判断左右括号是否匹配匹配返回true不匹配返回false 通过栈来实现类型和顺序数量都要匹配 控制数量通过size 每个右括号都要找最近的左括号去判断类型匹配不匹配顺序匹配不匹配 最后来判断数量匹配不匹配
左括号入栈右括号出栈顶括号进行匹配
栈接口
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);// 11:40if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);// assert(ps-top 0);--ps-top;
}STDataType STTop(ST* ps)
{assert(ps);// assert(ps-top 0);return ps-a[ps-top - 1];
}int STSize(ST* ps)
{assert(ps);return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}
if版本 bool isValid(char * s){ST st;STInit(st);char top;while(*s){if (*s [ || *s ( || *s {){STPush(st, *s);}else{//数量不匹配if (STEmpty(st)){STDestroy(st);return false;}top STTop(st);STPop(st);//顺序不匹配if((*s ] top ! [)|| (*s ) top ! ()|| (*s } top ! {)){STDestroy(st);return false;}}s;}// 栈不为空false说明数量不匹配bool ret STEmpty(st);STDestroy(st);return ret;
}switch版本
bool isValid(char * s){ST st;STInit(st);char top;while (*s){switch(*s){case [:case (:case {:STPush(st, *s);break;case }:// 数量不匹配if (STEmpty(st))return false;top STTop(st);STPop(st);// 顺序不匹配if (top ! {)return false;break;case ]:// 数量不匹配if (STEmpty(st))return false;top STTop(st);STPop(st);//顺序不匹配if (top ! [)return false;break;case ):// 数量不匹配if (STEmpty(st))return false;top STTop(st);STPop(st);//顺序不匹配if (top ! ()return false;break;}s;}//数量不匹配bool ret STEmpty(st);STDestroy(st);return ret;
}225. 用队列实现栈 用两个队列实现栈
Push 1 2 3 4
Pop 4 分别出1 2 3插入到另一个队列最后剩下4把最后一个数据Pop掉 Push 5 6 入到不为空的那个队列里
空队列是用来倒数据的
Pop 6
入队列不为空的队列 出队列不为空队列前N-1个出队列插入空队列删除剩余数据
队列接口
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);void QueueInit(Que* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq-head NULL;
}int QueueSize(Que* pq)
{assert(pq);return pq-size;
}
队列实现栈 typedef struct {Que q1;Que q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst (MyStack*)malloc(sizeof(MyStack));QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}void myStackPush(MyStack* obj, int x) {if (!QueueEmpty(obj-q1)){QueuePush(obj-q1, x);}else{QueuePush(obj-q2, x);}
}int myStackPop(MyStack* obj) {Que* empty obj-q1;Que* nonempty obj-q2;if (!QueueEmpty(obj-q1)){nonempty obj-q1;empty obj-q2;}while(QueueSize(nonempty) 1){// 前size-1个导入空队列QueuePush(empty, QueueFront(nonempty));QueuePop(nonempty);}int top QueueFront(nonempty);QueuePop(nonempty);return top;
}int myStackTop(MyStack* obj) {if (!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}
232. 用栈实现队列 用两个栈来实现队列 Push 1 2 3 4
Pop 1 把数据往另一个栈里倒
Push 5 6
存数据的栈称为pushst出数据的栈称为popst
栈接口
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);// 11:40if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);// assert(ps-top 0);--ps-top;
}STDataType STTop(ST* ps)
{assert(ps);// assert(ps-top 0);return ps-a[ps-top - 1];
}int STSize(ST* ps)
{assert(ps);return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}
栈实现队列 typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(obj-pushst, x);
}int myQueuePeek(MyQueue* obj) {if(STEmpty(obj-popst)){// 倒数据while(!STEmpty(obj-pushst)){STPush(obj-popst, STTop(obj-pushst));STPop(obj-pushst);}}return STTop(obj-popst);
}int myQueuePop(MyQueue* obj) {int front myQueuePeek(obj);STPop(obj-popst);return front;
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-popst) STEmpty(obj-pushst);
}void myQueueFree(MyQueue* obj) {STDestroy(obj-popst);STDestroy(obj-pushst);free(obj);
}
622. 设计循环队列 循环队列 Pop 1
Push 5
Pop 2
Push 6
当队列为空
front和rear相等队列为空 插入一个数据rear往后走 rear不是指向最后一个数据而是指向最后一个数据的下一个位置
如何判断队列满
多开一个空间 k 4表示队列只能存四个数
front rear 空 rear的下一个就是front 满
rear在中间的情况
(rear 1)% (k 1) front取队尾 (rear (k 1) - 1) % (k 1)
循环队列实现
typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));// 多开一个方便区分空和满obj-a (int*)malloc(sizeof(int)*(k1));obj-front obj-rear 0;obj-k k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-front obj-rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-rear 1)%(obj-k 1) obj-front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj-a[obj-rear] value;obj-rear;obj-rear % (obj-k 1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return false;obj-front;obj-front % (obj-k 1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;elsereturn obj-a[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;else//(rear (k 1) - 1) % (k 1)return obj-a[(obj-rear obj-k) % (obj-k 1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}
