gps建站教程视频,山东省交通运输厅网站开发单位,建设网站的市场机会,装修公司网站php源码个人主页#xff1a;点我进入主页 专栏分类#xff1a;C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 数据结构初阶 欢迎大家点赞#xff0c;评论#xff0c;收藏。 一起努力#xff0c;一起奔赴大厂。 目录 1.前言
2.概念题… 个人主页点我进入主页 专栏分类C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 数据结构初阶 欢迎大家点赞评论收藏。 一起努力一起奔赴大厂。 目录 1.前言
2.概念题
3.编程题
3.1. 括号匹配问题。OJ链接
3.2. 用队列实现栈。OJ链接
3.3. 用栈实现队列。OJ链接
3.4. 设计循环队列。OJ链接
4.总结 1.前言 在上一篇文章中我们讲解了关于栈和队列的性质以及栈和队列的实现代码还没保存吗力扣刷题用不到吗力扣解题出现错误调试时还想自己写一个栈和队列吗还愣着干嘛还不保存上。今天我们就主要针对上一篇文章的习题进行详细解析我们先对概念题进行解析然后再搞编程题。
2.概念题 1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈然后再依次出栈则元素出 栈的顺序是 。 A 12345ABCDE B EDCBA54321 C ABCDE12345 D 54321EDCBA 我们将12345AB,C,D,E依次入栈我们知道栈是先进后出所以我们的出栈顺序为EDCBA54321故答案为B. 2.若进栈序列为 1,2,3,4 进栈过程中可以出栈则下列不可能的一个出栈序列是 A 1,4,3,2 B 2,3,4,1 C 3,1,4,2 D 3,4,2,1 针对这种题型我们最好的解决方法就是模拟栈的实现我们进1出1进2进3进4出4出3出2选项A可以实现正确我们进1进2出2进3出3进4出4出1选项B可以实现正确我们进1进2进3出3想要出1需要将2出栈所以错误选择C. 3.循环队列的存储空间为 Q(1:100) 初始状态为 frontrear100 。经过一系列正常的入队与退队操作 后 frontrear99 则循环队列中的元素个数为 A 1 B 2 C 99 D 0或者100 我们知道循环队列是可以让数据进行循环我们知道有100个位置每个位置都占当我们的队列空时满足frontrear,当我们的队列满时满足frontrear,故选择D. 4.以下( )不是队列的基本运算 A 从队尾插入一个新元素 B 从队列中删除第i个元素 C 判断一个队列是否为空D 读取队头元素的值 我们知道队列是先进先出也就是头出尾进所以我们呢很容易看出选项B从队列中删除第i个元素,不满足头出尾进故选择B. 5.现有一循环队列其队头指针为front队尾指针为rear循环队列长度为N。其队内有效长度为(假设 队头不存放数据) A (rear - front N) % N 1 B (rear - front N) % N C ear - front) % (N 1) D (rear - front N) % (N - 1) 我们可以得到循环队列是有一个空位我们知道rear和front这两个位置是不定的可能在一起也可能front在前也可能rear在前故我们让这两个相减然后加上N,然后对N进行取余就可以得到有效长度。
3.编程题
3.1. 括号匹配问题。OJ链接
typedef struct Stack{char* data;int top;int capacity;
}Stack;
void InItStack(Stack *s)
{assert(s);s-capacity4;s-top-1;s-data(char*)malloc(sizeof(char)*s-capacity);
}
void CheckCapacity(Stack *s)
{assert(s);if(s-top1s-capacity)s-capacity2;char *p(char*)realloc(s-data,sizeof(char)*s-capacity);if(pNULL){perror(realloc fail);return ;}else s-datap;
}
void StackPush(Stack *s,char ch)
{assert(s);CheckCapacity(s);s-data[s-top]ch;
}
bool StackEmpty(Stack*s)
{assert(s);if(s-top-1)return true;return false ;
}
char StackPop(Stack*s)
{assert(s);if(!StackEmpty(s)){s-top--;return s-data[s-top1];}return 1;
}
void StackDestory(Stack *s)
{assert(s);free(s-data);
}
bool isValid(char* arr) {Stack s;InItStack(s);int szstrlen(arr),i;for(i0;isz;i){if(arr[i](||arr[i][||arr[i]{){StackPush(s,arr[i]);}else{char chStackPop(s);if((arr[i])ch()||(arr[i]]ch[)||(arr[i]}ch{)){;}else {StackDestory(s);return false;}}}StackDestory(s);return StackEmpty(s);
}
本题主要用到栈的操作我们遇到左括号入栈遇到右括号出栈出栈时比较是否匹配最后看栈是否空。 3.2. 用队列实现栈。OJ链接
typedef struct QNode {int data;struct QNode* next;
}QNode;
typedef struct Queue {struct QNode* head;struct QNode* tail;
}Queue;
void QueueInit(Queue* q)
{assert(q);q-head NULL;q-tail NULL;
}
QNode* QueueCreate(Queue* q, int x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-next NULL;return newnode;
}
void QueuePush(Queue* q, int x)
{QNode* newnode QueueCreate(q, x);if (q-head NULL){q-head newnode;q-tail newnode;}else{q-tail-next newnode;q-tail newnode;}
}
bool QueueEmpty(Queue* q)
{return q-head NULL;
}
int QueuePop(Queue* q)
{assert(q);if (!QueueEmpty(q)){int data q-head-data;if (q-head q-tail){free(q-head);q-head q-tail NULL;}else{QNode* cur q-head-next;free(q-head);q-head cur;}return data;}return 1;
}
int QueueSize(Queue* q)
{int count 0;QNode* cur q-head;while (cur){count;cur cur-next;}return count;
}
void QueueDestory(Queue* q)
{assert(q);if (!QueueEmpty(q)){QNode* cur q-head-next;QNode* prev q-head;while (prev){free(prev);prev cur;if (cur){cur cur-next;}}}
}
void QueuePrint(Queue* q)
{assert(q);QNode* cur q-head;while (cur){printf(%d , cur-data);cur cur-next;}
}
int top(Queue* q)
{assert(q);if (!QueueEmpty(q)){return q-head-data;}return 1;
}typedef struct {Queue queue1;Queue queue2;
} MyStack;MyStack* myStackCreate() {MyStack*obj(MyStack*)malloc(sizeof(MyStack));QueueInit(obj-queue1);QueueInit(obj-queue2);return obj;
}void myStackPush(MyStack* obj, int x) {assert(obj);if(!QueueEmpty(obj-queue1)){QueuePush(obj-queue1,x);}else{QueuePush(obj-queue2,x);}
}int myStackPop(MyStack* obj) {assert(obj);if(!QueueEmpty(obj-queue1)){QNode*cur(obj-queue1).head;while(cur-next!NULL){curcur-next;int dataQueuePop(obj-queue1);QueuePush(obj-queue2,data);}return QueuePop(obj-queue1);}else{QNode*curobj-queue2.head;while(cur-next!NULL){curcur-next;int dataQueuePop(obj-queue2);QueuePush(obj-queue1,data);}return QueuePop(obj-queue2); }
}int myStackTop(MyStack* obj) {if(!QueueEmpty(obj-queue1)){return ((obj-queue1).tail)-data;}elsereturn ( (obj-queue2).tail)-data;
}bool myStackEmpty(MyStack* obj) {assert(obj);return QueueEmpty(obj-queue1)QueueEmpty(obj-queue2);
}void myStackFree(MyStack* obj) {assert(obj);QueueDestory(obj-queue1);QueueDestory(obj-queue2);free(obj);
}
typedef struct QNode {int data;struct QNode* next;
}QNode;
typedef struct Queue {struct QNode* head;struct QNode* tail;
}Queue;
void QueueInit(Queue* q)
{assert(q);q-head NULL;q-tail NULL;
}
QNode* QueueCreate(Queue* q, int x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-next NULL;return newnode;
}
void QueuePush(Queue* q, int x)
{QNode* newnode QueueCreate(q, x);if (q-head NULL){q-head newnode;q-tail newnode;}else{q-tail-next newnode;q-tail newnode;}
}
bool QueueEmpty(Queue* q)
{return q-head NULL;
}
int QueuePop(Queue* q)
{assert(q);if (!QueueEmpty(q)){int data q-head-data;if (q-head q-tail){free(q-head);q-head q-tail NULL;}else{QNode* cur q-head-next;free(q-head);q-head cur;}return data;}return 1;
}
int QueueSize(Queue* q)
{int count 0;QNode* cur q-head;while (cur){count;cur cur-next;}return count;
}
void QueueDestory(Queue* q)
{assert(q);if (!QueueEmpty(q)){QNode* cur q-head-next;QNode* prev q-head;while (prev){free(prev);prev cur;if (cur){cur cur-next;}}}
}
void QueuePrint(Queue* q)
{assert(q);QNode* cur q-head;while (cur){printf(%d , cur-data);cur cur-next;}
}
int top(Queue* q)
{assert(q);if (!QueueEmpty(q)){return q-head-data;}return 1;
}typedef struct {Queue queue1;Queue queue2;
} MyStack;MyStack* myStackCreate() {MyStack*obj(MyStack*)malloc(sizeof(MyStack));QueueInit(obj-queue1);QueueInit(obj-queue2);return obj;
}void myStackPush(MyStack* obj, int x) {assert(obj);if(!QueueEmpty(obj-queue1)){QueuePush(obj-queue1,x);}else{QueuePush(obj-queue2,x);}
}int myStackPop(MyStack* obj) {assert(obj);if(!QueueEmpty(obj-queue1)){QNode*cur(obj-queue1).head;while(cur-next!NULL){curcur-next;int dataQueuePop(obj-queue1);QueuePush(obj-queue2,data);}return QueuePop(obj-queue1);}else{QNode*curobj-queue2.head;while(cur-next!NULL){curcur-next;int dataQueuePop(obj-queue2);QueuePush(obj-queue1,data);}return QueuePop(obj-queue2); }
}int myStackTop(MyStack* obj) {if(!QueueEmpty(obj-queue1)){return ((obj-queue1).tail)-data;}elsereturn ( (obj-queue2).tail)-data;
}bool myStackEmpty(MyStack* obj) {assert(obj);return QueueEmpty(obj-queue1)QueueEmpty(obj-queue2);
}void myStackFree(MyStack* obj) {assert(obj);QueueDestory(obj-queue1);QueueDestory(obj-queue2);free(obj);
}我们用队列实现栈这主要对栈和队列性质的考察我们入栈就是寻找空队列入队出栈是将非空队列出队剩下一个数据这一个数据就是要出栈的数据栈顶就是队尾的数据。 3.3. 用栈实现队列。OJ链接
typedef struct Stack {int* data;int top;int capacity;
}Stack;void InItStack(Stack* s)
{assert(s);s-capacity 4;s-top -1;s-data (int*)malloc(sizeof(int) * s-capacity);
}
void CheckCapacity(Stack* s)
{assert(s);if (s-top 1 s-capacity)s-capacity 2;int* p (int*)realloc(s-data, sizeof(int) * s-capacity);if (p NULL){perror(realloc fail);return;}elses-data p;
}
void StackPush(Stack* s, int ch)
{assert(s);CheckCapacity(s);s-data[s-top] ch;
}
bool StackEmpty(Stack* s)
{assert(s);if (s-top -1)return true;return false;
}
int StackPop(Stack* s)
{assert(s);if (!StackEmpty(s)){s-top--;return s-data[s-top 1];}return 1;
}
void StackDestory(Stack* s)
{assert(s);free(s-data);
}
int StackSize(Stack* s)
{assert(s);return s-top 1;
}
int StackTopdata(Stack* s)
{assert(s);return s-data[s-top];
}typedef struct {Stack s1;Stack s2;
} MyQueue;MyQueue* myQueueCreate() {MyQueue*obj(MyQueue*)malloc(sizeof(MyQueue));InItStack(obj-s1);InItStack(obj-s2);return obj;
}void myQueuePush(MyQueue* obj, int x) {assert(obj);if(!StackEmpty(obj-s1)){StackPush(obj-s1,x);}else{StackPush(obj-s2,x);}
}int myQueuePop(MyQueue* obj) {assert(obj);int data;if(!StackEmpty(obj-s1)){while(!StackEmpty(obj-s1)){StackPush(obj-s2,StackPop(obj-s1));}dataStackPop(obj-s2);while(!StackEmpty(obj-s2)){StackPush(obj-s1,StackPop(obj-s2));}}else{while(!StackEmpty(obj-s2)){StackPush(obj-s1,StackPop(obj-s2));}dataStackPop(obj-s1);while(!StackEmpty(obj-s1)){StackPush(obj-s2,StackPop(obj-s1));}}return data;
}int myQueuePeek(MyQueue* obj) {assert(obj);if(!StackEmpty(obj-s1)){return (obj-s1).data[0];}elsereturn (obj-s2).data[0];
}bool myQueueEmpty(MyQueue* obj) {assert(obj);return StackEmpty(obj-s1)StackEmpty(obj-s2);
}void myQueueFree(MyQueue* obj) {assert(obj);free((obj-s1).data);free((obj-s2).data);free(obj);
} 这道题也是考察栈和队列的性质 入队就是寻找非空的栈入栈都为空时入第二个栈由于队列是先进先出所以我们将非空栈全部转到空栈栈是先进后出所以数据会倒置栈顶就是第一个进入的数据让他出栈就是出队然后再次倒置回去正常操作即可。 3.4. 设计循环队列。OJ链接 typedef struct {int* data;int capacity;int head;int tail;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj-tailobj-head){return true;}return false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);if((obj-tail1)%(obj-capacity1)obj-head)return true;elsereturn false;
}void myCircularQueueFree(MyCircularQueue* obj) {assert(obj);free(obj-data);free(obj);
}MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*queue(MyCircularQueue*)malloc(sizeof(MyCircularQueue));queue-data(int*)malloc(sizeof(int)*(k1));queue-capacityk;queue-headqueue-tail0;return queue;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);if(!myCircularQueueIsFull(obj)){obj-data[obj-tail]value;obj-tail(obj-tail1)%(obj-capacity1);return true;}return false;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);if(!myCircularQueueIsEmpty(obj)){obj-head(obj-head1)%(obj-capacity1);return true;}return false;
}int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);if(!myCircularQueueIsEmpty(obj))return obj-data[obj-head];return -1;
}int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);if(!myCircularQueueIsEmpty(obj)){return obj-data[(obj-tailobj-capacity)%(obj-capacity1)];}return -1;
}循环队列我们利用数组或链表都可以当我们使用数组时只需要进行推理即可以得到数据的下标链表在判断队列满和空比较困难所以我们选择数组尤其是找队列的头和尾判断对满就是obj-tail1)%(obj-capacity1)obj-head队列空就是obj-tailobj-head; 4.总结 今天的内容主要是对栈和队列的性质和操作进行深入学习还有一个特别重要的就是我们在写题的时候我们的栈队列链表的外接函数我们可以进行复制过来特别注意我们可以称之为cv操作今天的内容就到这里了希望大家可以学到很多。
