中石油第七建设公司网站,做网站图注意事项,中国建设银行章丘支行网站,免费详情页模板网站一、括号的匹配
题目介绍#xff1a; 思路#xff1a; 如果 c 是左括号#xff0c;则入栈 push#xff1b;否则通过哈希表判断括号对应关系#xff0c;若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应#xff0c;则提前返回 false。栈 stack 为空#xff1…一、括号的匹配
题目介绍 思路 如果 c 是左括号则入栈 push否则通过哈希表判断括号对应关系若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应则提前返回 false。栈 stack 为空 此时 stack.pop() 操作会报错因此我们采用一个取巧方法给 stack 赋初值 ?并在哈希表 dic 中建立 key: ‘?’value:’?’ 的对应关系予以配合。此时当 stack 为空且 c 为右括号时可以正常提前返回 false 字符串 s 以左括号结尾 此情况下可以正常遍历完整个 s但 stack 中遗留未出栈的左括号因此最后需返回 len(stack) 1以判断是否是有效的括号组合 typedef int STDataType;
//动态存储结构
typedef struct Stack
{STDataType *a;int top;int capacity; //容量
}ST;void STInit(ST* ps); //初始化栈
void STDestory(ST* ps); //销毁栈
bool STEmpty(ST* ps); //判断是否为空
void STPush(ST* ps, STDataType x); //入栈
void STPop(ST* ps); //出栈
STDataType STTop(ST* ps); //取栈顶元素
int STSize(ST* ps); //返回栈元素个数void STInit(ST* ps) //初始化栈
{assert(ps);ps-a NULL;ps-top 0;ps-capacity 0;
}void STDestory(ST* ps) //销毁栈
{assert(ps);free(ps-a);ps-a NULL;ps-top 0;ps-capacity 0;
}bool STEmpty(ST* ps) //判断是否为空
{assert(ps);return (ps-top 0);
}void STPush(ST* ps, STDataType x) //入栈
{assert(ps);//扩容if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tem (STDataType*)realloc(ps-a,sizeof(STDataType)* newcapacity);if (tem NULL){perror(malloc);exit(-1);}ps-a tem;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps) //出栈
{assert(ps);assert(ps-top0);--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 isValid(char * s)
{char topval;ST st;STInit(st);while(*s){if(*s(||*s[||*s{){STPush(st, *s);}else{if(STEmpty(st)){STDestory(st);return false;}topvalSTTop(st);STPop(st);if((*s}topval!{)||(*s)topval!()||(*s]topval![)){STDestory(st);return false;}}s;}bool retSTEmpty(st);STDestory(st);return ret;
} 二、队列实现栈
题目介绍 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 QueueDestory(Que* pq); //销毁队列
bool QueueEmpty(Que* pq); //判断队列是否为空
void QueuePush(Que* pq, QDataType x);//进队列
void QueuePop(Que* pq); //出队列
QDataType QueueFront(Que* pq); //取队头元素
QDataType QueueBack(Que* pq); //取队尾元素
int QueueSize(Que* pq); //返回元素个数
void QueueInit(Que* pq) //初始化队列
{assert(pq);pq-head NULL;pq-tail NULL;pq-size 0;
}void QueueDestory(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;
}bool QueueEmpty(Que* pq) //判断队列是否为空
{assert(pq);return pq - head NULL;
}void QueuePush(Que* pq, QDataType x)//进队列
{//尾插assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc);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-tailNULL;}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;
}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*emptyobj-q1;Que*nonEmptyobj-q2;if(!QueueEmpty(obj-q1)){nonEmptyobj-q1;emptyobj-q2;}while(QueueSize(nonEmpty)1){QueuePush(empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int topQueueFront(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)
{QueueDestory(obj-q1);QueueDestory(obj-q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj myStackCreate();* myStackPush(obj, x);* int param_2 myStackPop(obj);* int param_3 myStackTop(obj);* bool param_4 myStackEmpty(obj);* myStackFree(obj);
*/
三、栈实现队列
题目介绍 思路
因为队列先进先出栈先进后出所以用两个栈实现队列。栈s1用来入队栈s2用来出队。
入队对入队的栈s1直接进行元素入栈。
出队当出队的栈s2不为空时s2直接出栈若s2为空将s1的元素都导入出队的栈s2里然后s2进行出栈。、
在入队1、2、3、4后出队如图所示s1中的数据都入栈s2(s1s2中的数据相同顺序相反例s1中的栈底元素1出现在s2中的栈顶)此时s1的top0top表示栈中有多少元素0代表栈中元素都已经出栈s2的top3本来有4个数据但栈顶元素已经出栈所以为3.
typedef int STDataType;
typedef struct Stack
{STDataType *a;int top;int capacity; //容量
}ST;void STInit(ST* ps); //初始化栈
void STDestory(ST* ps); //销毁栈
bool STEmpty(ST* ps); //判断是否为空
void STPush(ST* ps, STDataType x); //入栈
void STPop(ST* ps); //出栈
STDataType STTop(ST* ps); //取栈顶元素
int STSize(ST* ps); //返回栈元素个数void STInit(ST* ps) //初始化栈
{assert(ps);ps-a NULL;ps-top 0;ps-capacity 0;
}void STDestory(ST* ps) //销毁栈
{assert(ps);free(ps-a);ps-a NULL;ps-top 0;ps-capacity 0;
}bool STEmpty(ST* ps) //判断是否为空
{assert(ps);return (ps-top 0);
}void STPush(ST* ps, STDataType x) //入栈
{assert(ps);//扩容if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tem (STDataType*)realloc(ps-a,sizeof(STDataType)* newcapacity);if (tem NULL){perror(malloc);exit(-1);}ps-a tem;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps) //出栈
{assert(ps);assert(ps-top0);--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 ;
}
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)
{STDestory(obj-popst);STDestory(obj-pushst);free(obj);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj myQueueCreate();* myQueuePush(obj, x);* int param_2 myQueuePop(obj);* int param_3 myQueuePeek(obj);* bool param_4 myQueueEmpty(obj);* myQueueFree(obj);
*/
四、循环队列
题目介绍 设计一个队列这个队列的大小是固定的且队列头尾相连 然后该队列能够实现题目中的操作。
那么是使用数组实现还是用链表实现呢我们接着往下看。
环形队列的几个判断条件 front:指向队列的第一个元素初始值front0 rear: 指向队列的最后一个元素的后一个位置预留一个空间作为约定,初始值rear0 maxSize: 数组的最大容量 队空front rear 队满(rear1)%maxSize front 队列中的有效数据个数rearmaxSize-front% maxSize 其中判断队列满的思想的话可以看下图因为是环形的起初frontrear0每当添加元素时将rear但是其实预留了一个长度没有用比如定义的队列数组长度为5时但是实际上可以使用的地址就是0,1,2,3此时rear4, 4这个空间用来判断队满的条件rear1%maxSizefront 有了上面的铺垫就可以很轻松的写出下面的函数。
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-frontobj-rear0;obj-kk;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj-frontobj-rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj)
{return (obj-rear1)%(obj-k1)obj-front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if(myCircularQueueIsFull(obj)){return false;}obj-a[obj-rear]value;obj-rear;obj-rear%(obj-k1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return false;}obj-front;obj-front%(obj-k1);return true;
}int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[(obj-rear(obj-k1)-1)%(obj-k1)];
}void myCircularQueueFree(MyCircularQueue* obj)
{free(obj-a);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj myCircularQueueCreate(k);* bool param_1 myCircularQueueEnQueue(obj, value);* bool param_2 myCircularQueueDeQueue(obj);* int param_3 myCircularQueueFront(obj);* int param_4 myCircularQueueRear(obj);* bool param_5 myCircularQueueIsEmpty(obj);* bool param_6 myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/
