中国建设教育协会报名网站,企业型商务网站制作做法,村志网站建设,t恤在线制作网站目录 一、栈
1.栈的概念和结构
2.栈的实现方案
3.栈的具体实现
4.栈的完整代码
5.有效的括号
二、队列
1.队列的概念及结构
2.队列的实现方案
3.队列的实现
4.队列实现的完整代码 一、栈
1.栈的概念和结构 栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定…目录 一、栈
1.栈的概念和结构
2.栈的实现方案
3.栈的具体实现
4.栈的完整代码
5.有效的括号
二、队列
1.队列的概念及结构
2.队列的实现方案
3.队列的实现
4.队列实现的完整代码 一、栈
1.栈的概念和结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 2.栈的实现方案 对于这个栈想必我们也不难想到他有两种实现的方案了第一种方案是使用顺序表来实现第二种方案是使用链表来实现 顺序表实现 如果采用顺序表来实现的话由于只有在栈顶会出数据和入数据所以栈顶就应该对应着数组的尾。 而这种方式我们不难发现他是很优的而且由于cpu的局部性原理也是具有一定的优势的。因此我们发现栈是一种很适合使用顺序表实现的 链表来实现 如果采用链表来实现的话我们可以选择使用单链表和带头双向循环链表。 如果我们使用单链表 我们这里又可以细分为栈顶在链表头和在链表尾 如下图所示是栈顶在链表尾部这样的话我们显然可以得知他的效率是很低的 如果栈顶在链表头的话这样就可以提升了效率但是仍然没有顺序表更具有优势 而如果使用带头双向循环链表的话确实也可以高效的实现栈但是是没有顺序表具有优势的 3.栈的具体实现 栈的定义 根据上面的分析我们决定采用顺序表来实现栈使用顺序表又可以分为静态的和动态的。当然动态的性能是要优于静态的。我们使用动态顺序表 typedef int STDateType;typedef struct Stack
{STDateType* a;int top;int capacity;
}Stack; 栈的初始化 对于栈的初始化与动态顺序表的初始化完全一样。初始为其分配四个数据的空间。然后让top和capacity分别置为0和4 //栈的初始化
void StackInit(Stack* ps)
{assert(ps);ps-a (STDateType*)malloc(sizeof(STDateType) * 4);if (ps-a NULL){perror(malloc fail);return;}ps-top 0;ps-capacity 4;
} 栈的销毁 由于这个栈的本质是一个顺序表所以直接释放顺序表中指针所对应的那块空间即可 //栈的销毁
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top 0;ps-capacity 0;
} 入栈 对于入栈我们需要先检查容量容量不够则扩容然后直接尾插即可 //入栈
void StackPush(Stack* ps, STDateType x)
{assert(ps);if (ps-top ps-capacity){STDateType* tmp (STDateType*)realloc(ps-a, ps-capacity * 2 * sizeof(STDateType));if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity * 2;}ps-a[ps-top] x;ps-top;
} 出栈 对于出栈我们得先确定栈内元素不为空然后我们直接让top--即可 //出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps-top--;
} 栈的个数 由于我们的top代表的就是栈的个数所以直接返回即可 //栈的个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;
} 栈是否为空 对于判断栈是否为空我们直接根据top的值即可判断 //栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
} 取出栈顶的元素 我们先确定栈不为空然后直接返回栈顶元素即可 //取出栈顶的数据
STDateType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-a[ps-top - 1];
} 4.栈的完整代码 Stack.h #pragma once
#includestdio.h
#includemalloc.h
#includestdbool.h
#includeassert.htypedef int STDateType;typedef struct Stack
{STDateType* a;int top;int capacity;
}Stack;//栈的初始化
void StackInit(Stack* ps);
//栈的销毁
void StackDestroy(Stack* ps);
//入栈
void StackPush(Stack* ps, STDateType x);
//出栈
void StackPop(Stack* ps);
//栈的个数
int StackSize(Stack* ps);
//栈是否为空
bool StackEmpty(Stack* ps);
//取出栈顶的数据
STDateType StackTop(Stack* ps); Stack.c #define _CRT_SECURE_NO_WARNINGS 1#includeStack.h//栈的初始化
void StackInit(Stack* ps)
{assert(ps);ps-a (STDateType*)malloc(sizeof(STDateType) * 4);if (ps-a NULL){perror(malloc fail);return;}ps-top 0;ps-capacity 4;
}
//栈的销毁
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top 0;ps-capacity 0;
}
//入栈
void StackPush(Stack* ps, STDateType x)
{assert(ps);if (ps-top ps-capacity){STDateType* tmp (STDateType*)realloc(ps-a, ps-capacity * 2 * sizeof(STDateType));if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity * 2;}ps-a[ps-top] x;ps-top;
}
//出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps-top--;
}
//栈的个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;
}
//栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}
//取出栈顶的数据
STDateType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-a[ps-top - 1];
}Test.c #define _CRT_SECURE_NO_WARNINGS 1
#includeStack.h
void TestStack1()
{Stack s;StackInit(s);StackPush(s, 1);StackPush(s, 2);StackPush(s, 3);StackPush(s, 4);StackPush(s, 5);printf(%d\n, StackSize(s));while (!StackEmpty(s)){printf(%d , StackTop(s));StackPop(s);}StackDestroy(s);
}
int main()
{TestStack1();return 0;
} 5.有效的括号 题目链接力扣 题目解析对于这道题最简单的方法就是使用一个栈来记录左括号如果是左括号则入栈如果不是左括号先取出栈顶的元素并出栈。然后将栈顶元素与当前的字符进行比较。如果满足错误条件则销毁栈后直接返回即可。 如果可以匹配则直接让s即可。最后当所有字符串遍历完成以后然后根据栈是否为空返回即可 typedef char STDateType;typedef struct Stack
{STDateType* a;int top;int capacity;
}Stack;
//栈的初始化
void StackInit(Stack* ps)
{assert(ps);ps-a (STDateType*)malloc(sizeof(STDateType) * 4);if (ps-a NULL){perror(malloc fail);return;}ps-top 0;ps-capacity 4;
}
//栈的销毁
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top 0;ps-capacity 0;
}
//入栈
void StackPush(Stack* ps, STDateType x)
{assert(ps);if (ps-top ps-capacity){STDateType* tmp (STDateType*)realloc(ps-a, ps-capacity * 2 * sizeof(STDateType));if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity * 2;}ps-a[ps-top] x;ps-top;
}
//栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}
//出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps-top--;
}
//栈的个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;
}//取出栈顶的数据
STDateType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-a[ps-top - 1];
}
bool isValid(char * s){Stack st;StackInit(st);while(*s!\0){if( (*s()||(*s[)||(*s{)){StackPush(st,*s);}else{if(StackEmpty(st)){StackDestroy(st);return false;}char pStackTop(st);StackPop(st);if( ((*s!))(p())|| ((*s!])(p[))||((*s!})(p{))){StackDestroy(st);return false;}}s;}bool ret StackEmpty(st);StackDestroy(st);return ret;
} 二、队列
1.队列的概念及结构 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 2.队列的实现方案 对于队列的实现我们仍然又两种方法可以选择一种是链表形式一种是顺序表形式 如果采用顺序表来实现的话我们会发现头删操作时间复杂度较高。 如果采用链表来实现的话我们发现找尾部结点的时间复杂度较高但是我们可以多定义一个结点来随时知道尾部结点的地址。这样就可以优化掉找尾的时间复杂度。而且对于计算队列长度的话我们也可以多定义一个变量size我们在删除和插入数据的时候调整好size的大小。就可以优化掉计算队列长度的时间复杂度 这里我们也产生一个新的问题对于单链表能否多定义一个指针来控制尾部的地址从而优化找尾的时间复杂度。 其实是不行的对于尾插显然可以优化但是对于尾删就不可以了。因为他需要找前一个结点的地址。 对于单链表我们也可以使用一个变量size用来优化计算单链表长度的时间复杂度 综上所述我们发现采用链表的结构是最优的。这个链表有一些不同的是我们需要使用头尾两个指针以及一个size变量来进行优化既然如此那么我们就最好使用一个结构体来连接这些变量。否则传参的时候我们需要传三个以上的变量。 typedef int QDateType;typedef struct QNode
{QDateType data;struct QNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue; 3.队列的实现 1.初始化队列 //初始化队列
void QueueInit(Queue* q)
{assert(q);q-head NULL;q-tail NULL;q-size 0;
} 如上代码所示我们直接传结构体的地址就可以了。 2.队尾入数据 //申请一个结点
QNode* BuyQNode(QDateType x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-next NULL;newnode-data x;return newnode;
}
//队尾入队列
void QueuePush(Queue* q, QDateType x)
{assert(q);QNode* newnode BuyQNode(x);if (q-tail NULL){q-head q-tail newnode;}else{q-tail-next newnode;q-tail q-tail-next;}q-size;
} 队尾入数据的话与单链表的入数据思路是一致的我们先申请一个结点然后判断这个链表是否为空如果为空则特殊处理否则正常尾插即可 3.队头出数据 //队头出队列
void QueuePop(Queue* q)
{assert(q);assert(q-head);QNode* first q-head-next;free(q-head);q-head first;q-size--;if (q-head NULL){q-tail NULL;}
} 对于出数据与单链表是一样的但是我们需要特别注意尾指针如果删了队列最后一个结点后队列为空那么需要将尾结点置为空 4.获取头部尾部数据 //获取队列头部元素
QDateType QueueFront(Queue* q)
{assert(q);assert(q-head);return q-head-data;
}
//获取队列尾部元素
QDateType QueueBack(Queue* q)
{assert(q);assert(q-head);return q-tail-data;
} 对于这两个函数基本思路是一样的我们先判断链表不为空然后直接返回数据即可 5.获取队列中的有效元素的个数 //获取队列中的有效元素个数
int QueueSize(Queue* q)
{assert(q);return q-size;
} 对于这段代码我们直接返回size即可 6.检测队列是否为空 //检测队列是否为空
bool QueueEmpty(Queue* q)
{assert(q);return q-head NULL;
} 这段代码也很简单直接返回这个判断条件即可 7.销毁队列 //销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur q-head;while (cur){QNode* next cur-next;free(cur);cur next;}q-head q-tail NULL;q-size 0;
} 销毁队列的方法与单链表的销毁是一样的我们需要注意的是别忘记置空head和tail以及size。 4.队列实现的完整代码 Queue.h #pragma once
#includestdio.h
#includestdlib.h
#includemalloc.h
#includestdbool.h
#includeassert.htypedef int QDateType;typedef struct QNode
{QDateType data;struct QNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;//初始化队列
void QueueInit(Queue* q);
//队尾入队列
void QueuePush(Queue* q, QDateType x);
//队头出队列
void QueuePop(Queue* q);
//获取队列头部元素
QDateType QueueFront(Queue* q);
//获取队列尾部元素
QDateType QueueBack(Queue* q);
//获取队列中的有效元素个数
int QueueSize(Queue* q);
//检测队列是否为空
bool QueueEmpty(Queue* q);
//销毁队列
void QueueDestroy(Queue* q); Queue.c #define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.h//初始化队列
void QueueInit(Queue* q)
{assert(q);q-head NULL;q-tail NULL;q-size 0;
}
//申请一个结点
QNode* BuyQNode(QDateType x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-next NULL;newnode-data x;return newnode;
}
//队尾入队列
void QueuePush(Queue* q, QDateType x)
{assert(q);QNode* newnode BuyQNode(x);if (q-tail NULL){q-head q-tail newnode;}else{q-tail-next newnode;q-tail q-tail-next;}q-size;
}
//队头出队列
void QueuePop(Queue* q)
{assert(q);assert(q-head);QNode* first q-head-next;free(q-head);q-head first;q-size--;if (q-head NULL){q-tail NULL;}
}
//获取队列头部元素
QDateType QueueFront(Queue* q)
{assert(q);assert(q-head);return q-head-data;
}
//获取队列尾部元素
QDateType QueueBack(Queue* q)
{assert(q);assert(q-head);return q-tail-data;
}
//获取队列中的有效元素个数
int QueueSize(Queue* q)
{assert(q);return q-size;
}
//检测队列是否为空
bool QueueEmpty(Queue* q)
{assert(q);return q-head NULL;
}
//销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur q-head;while (cur){QNode* next cur-next;free(cur);cur next;}q-head q-tail NULL;q-size 0;
} Test.c #define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.hvoid TestQueue1()
{Queue pq;QueueInit(pq);QueuePush(pq, 1);QueuePush(pq, 2);QueuePush(pq, 3);QueuePush(pq, 4);QueuePush(pq, 5);printf(%d \n, QueueSize(pq));while (!QueueEmpty(pq)){printf(%d , QueueFront(pq));QueuePop(pq);}QueueDestroy(pq);
}
int main()
{TestQueue1();return 0;
}本期内容就到这里了
如果对你有帮助的话不要忘记点赞加收藏哦
