栈
栈的概念及特性
- 栈是一种特殊的线性表,其特殊性体现在元素插入和删除运算上,它的插入和删除运算仅限定在线性表的某一端进行,不能在表中间和另一端进行。
- 栈的插入操作称为进栈(入栈、Push),删除操作称为出栈(退栈、Pop)。
- 允许进行插入和删除的一端称为栈顶,另一端称为栈底。
- 处于栈顶位置的数据元素称为栈顶元素。
- 不含任何数据元素的栈称为空栈。
- 栈是先进后出FILO (First In Last Out)或后进先出LIFO (Last In First Out)的线性表。
栈的基本运算:
- 初始化栈InitStack(S)。建立一个空栈S。
- 销毁栈DestroyStack(S)。释放栈S占用的内存空间。
- 进栈Push(S, x)。将元素x插入栈S中,使x成为栈S的栈顶元素。
- 出栈Pop(S, x)。当栈S不空时,将栈顶元素赋给x,并从栈中删除当前栈顶。
- 取栈顶元素GetTop(S)。若栈S不空,取栈顶元素x并返回1;否则返回0。
- 判断栈空StackEmpty(S)。判断栈S是否为空栈。
顺序栈:栈的顺序存储结构,由一个一维数组data和一个记录栈顶元素位置的变量top组成,习惯上将栈底放在数组下标小的那端,栈顶元素由栈顶指针top所指向。
顺序栈的运算
- 初始化栈算法InitStack(SqStack &S)
- 销毁栈算法DestroyStack(SqStack &S)
- 进栈算法Push(SqStack &S, ElemType e)
- 出栈运算算法Pop(SqStack &S, ElemType &e)
- 取栈顶元素算法GetTop(SqStack S, ElemType &e)
- 判断栈空算法StackEmpty(SqStack S)
代码实现:
#include <cstdio>
#include <cstdlib>
#define STACK_INIT_SIZE 100//存储空间初始分配量
#define STACK_INCREMENT 10//存储空间分配增量
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define Status int
typedef char ElemType;
typedef struct {
ElemType* base;//栈底指针
ElemType* top;//栈顶指针
int stacksize;//栈的大小
}SqStack;
Status InitStack(SqStack& S)
{
S.base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!S.base)
return ERROR;//分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack& S)
{
if (!S.base)
return ERROR;
free(S.base);
S.stacksize = 0;
S.base = NULL;
S.top = NULL;
return OK;
}
Status Push(SqStack& S, ElemType e)
{
if (S.top - S.base >= S.stacksize) {//栈是否满
if (S.base = (ElemType*)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(ElemType)))
return ERROR;
S.top = S.base + S.stacksize;
S.stacksize += STACK_INCREMENT;
}
*(S.top)++ = e;
return OK;
}
Status Pop(SqStack& S, ElemType& e)
{
if (StackEmpty(S))
return ERROR;
e = *--S.top;
return OK;
}
Status GetTop(SqStack S, ElemType& e)
{
if (S.top == S.base)
return ERROR;
e = *(S.top - 1);
return OK;
}
Status StackEmpty(SqStack S)
{
if (S.base == S.top)
return TRUE;
else
return FALSE;
}
链栈:栈的链式存储结构,通常用一个无头结点的单链表表示,将单链表的头指针作为栈顶指针。
链栈的运算
- 初始化栈运算算法InitStack(LinkStack *&top)
- 销毁栈算法DestroyStack(LinkStack *&top)
- 进栈算法Push(LinkStack *&top,ElemType x)
- 出栈算法Pop(LinkStack *&top,ElemType &x)
- 取栈顶元素算法GetTop(LinkStack *top,ElemType &x)
- 判断栈空算法StackEmpty(LinkStack *top)
代码实现:
#include <cstdio>
#include <cstdlib>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char ElemType;
typedef struct node {
ElemType data;
struct node* next;
}LinkStack;
Status InitStack(LinkStack*& top)
{
top = NULL;
return OK;
}
Status Destory(LinkStack*& top)
{
LinkStack* pre = top, * p;
if (pre == NULL) return ERROR;//空栈
p = pre->next;
while (p != NULL) {
free(pre);
pre = p;
p = p->next;
}
free(pre);//释放尾结点
return OK;
}
Status Push(LinkStack*& top, ElemType e)
{
LinkStack* p;
p = (LinkStack*)malloc(sizeof(LinkStack));
p->data = e;
p->next = top;
top = p;
return OK;
}
Status Pop(LinkStack*& top, ElemType& e)
{
LinkStack* p;
if (top == NULL)
return ERROR;
p = top;
e = p->data;
top = p->next;
free(p);
return OK;
}
Status GetTop(LinkStack* top, ElemType& x)
{
if (top == NULL)//空栈
return ERROR;
x = top->data;
return OK;
}
Status StackEmpty(LinkStack* top)
{
if (top == NULL)
return TRUE;
return FALSE;
}
顺序栈与链栈的区别:栈的使用中数据元素变化不可预料,有时小,有时大,用链栈。如果变化在可控范围之内,用顺序栈。
递归:在定义一个过程或函数时出现调用本过程或本函数。若调用自身称为直接递归,若使用过程或函数调用本过程本函数为间接递归。如果一个递归函数在执行语句最后一句时称为尾递归。
递归模型:有递归体与递归出口两部分构成。
表达式求值
中缀表达式: 中缀表达式是一种通用的算术或逻辑公式表示方法,操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。
前缀表达式 (波兰式):前缀表达式的运算符位于操作数之前。
前缀表达式求值: 从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算,并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。
中缀表达式转换为前缀表达式 :
- 初始化两个栈:运算符栈S1和储存中间结果的栈S2
- 从右至左扫描中缀表达式遇到操作数时,将其压入S2。遇到运算符时,比较其与S1栈顶运算符的优先级 。如果S1为空,或栈顶运算符为右括号“)”,则直接将此运算符入栈 。否则,若优先级比栈顶运算符的较高或相等,也将运算符压入S1 。否则,将S1栈顶的运算符弹出并压入到S2中,再次转到S1中与新的栈顶运算符相比较 。
- 遇到括号时,如果是右括号“)”,则直接压入S1。如果是左括号“(”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到右括号为止,此时将这一对括号丢弃。
- 重复步骤,直到表达式的最左边,将S1中剩余的运算符依次弹出并压入S2,依次弹出S2中的元素并输出,结果即为中缀表达式对应的前缀表达式。
后缀表达式(逆波兰式):后缀表达式与前缀表达式类似,只是运算符位于操作数之后。
后缀表达式的求值: 从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈中次顶 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
中缀表达式转换为后缀表达式 :
- 初始化两个栈:运算符栈S1和储存中间结果的栈S2
- 从左至右扫描中缀表达式遇到操作数时,将其压入S2。遇到运算符时,比较其与S1栈顶运算符的优先级。如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈 。否则,若优先级比栈顶运算符的较高也将运算符压入S1。否则,将S1栈顶的运算符弹出并压入到S2中,再次转到S1中与新的栈顶运算符相比较 。
- 遇到括号时,如果是左括号“(”,则直接压入S1。如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到右括号为止,此时将这一对括号丢弃。
- 重复步骤,直到表达式的最右边,将S1中剩余的运算符依次弹出并压入S2,依次弹出S2中的元素并输出,结果的倒序即为中缀表达式对应的前缀表达式。
队列
队列的概念及特性:
- 队列(简称队)也是一种运算受限的线性表。
- 队列的插入操作称为进队,删除操作称为出队。
- 允许插入的一端称为队尾,允许删除的一端称为队头。
- 新插入的元素只能添加到队尾,被删除的只能是排在队头的元素。
- 是一种先进先出(First In First Out ,简称FIFO)的线性表。
队列的基本运算:
- 初始化队列InitQueue(Q)。建立一个空队Q。
- 销毁队DestroyQueue(Q)。释放队列Q占用的内存空间。
- 进队EnQueue(Q, x)。将x插入到队列Q的队尾。
- 出队DeQueue(Q, x)。将队列Q的队头元素出队并赋给x。
- 取队头元素GetHead(Q, x)。取出队列Q的队头元素并赋给x,但该元素不出队。
- 判断队空QueueEmpty(Q)。判断队列Q是否为空。
顺序队列:队列的顺序存储结构,由一个一维数组(用于存储队列中元素)及两个分别指示队头和队尾的变量组成,这两个变量分别称为“队头指针”和“队尾指针”。初始化建空队列时,令front=rear=0。在非空队列中,头指针始终指向队列头元素,而尾指针始终指向rear队列尾元素的下一个位置。
循环队列:为了能够充分地使用数组中的存储空间,可以把数组的前端和“假想地”连接起来,形成一个环形的表,即把存储队列元素的表从逻辑上看成一个环,这个环形的表叫做循环队列或环形队列。
- 出队:front=(front+1) MOD MAXSIZE;
- 入队:rear=(rear+1) MOD MAXSIZE;
- 队空条件:front==rear ;
- 队满条件:(rear+1) MOD MAXSIZE==front
- 队中最多只能进队MAXSIZE-1个元素
顺序循环队列的运算
- 初始化队列算法InitQueue(SqQueue &Q)
- 销毁队列运算算法DestroyQueue(SqQueue &Q)
- 入队列算法EnQueue(SqQueue &Q, ElemType e)
- 出队列算法DeQueue(SqQueue &Q, ElemType &e)
- 取队头元素运算算法GetHead(SqQueue Q, ElemType &e)
- 判断队空算法QueueEmpty(SqQueue Q)
代码实现:
#include <cstdio>
#include <cstdlib>
#define MAXQSIZE 100//实际最大存储100-1
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
typedef struct {
ElemType* base;//初始化动态分配存储空间
int front;//头指针,若队列不空,指向队列头元素
int rear;//尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;
Status InitQueue(SqQueue& Q)
{
Q.base = (ElemType*)malloc(MAXQSIZE * sizeof(ElemType));
if (!Q.base)
return ERROR;
Q.front = Q.rear = 0;
return OK;
}
Status DestroyQueue(SqQueue& Q)
{
if (!Q.base)
return ERROR;
free(Q.base);
Q.front = Q.rear = 0;
return OK;
}
Status EnQueue(SqQueue& Q, ElemType e)
{
if (Q.front == (Q.rear + 1) % MAXQSIZE)
return ERROR;//是否队满
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue& Q, ElemType& e)
{
if (Q.front = Q.rear)
return ERROR;//空队列
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
Status GetHead(SqQueue Q, ElemType& e)
{
if (Q.front == Q.rear)
return ERROR;//空队列
e = Q.base[Q.front];
return OK;
}
Status QueueEmpty(SqQueue Q)
{
if (Q.front == Q.rear)
return TRUE;
return FALSE;
}
链队列:队列的链式存储结构,是一个同时带有队头指针front和队尾指针rear的链表。队头指针指向头结点,队尾指针指向队尾结点即单链表的尾结点,并将队头和队尾指针结合起来构成链队结点。
- 队空条件:Q.front->next == NULL
- 队满条件:不考虑(因为每个结点是动态分配的)
- 进队操作:创建结点p,将其插入到队尾,并由Q.rear指向它
- 出队操作:删除队头的结点。
单链表队列的运算
- 初始化队列算法InitQueue(LinkQueue &Q)
- 销毁队列算法DestroyQueue(LinkQueue &Q)
- 入队列算法EnQueue(LinkQueue &Q, ElemType e)
- 出队列算法DeQueue(LinkQueue &Q, ElemType &e)
- 取队头元素算法GetHead(LinkQueue Q, ElemType &e)
- 判断队空算法QueueEmpty(LinkQueue Q)
代码实现:
#include <cstdio>
#include <cstdlib>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
//数据结点
typedef struct QNode {
ElemType data;//存放队中元素
struct QNode* next;//指向下一个结点
}QNode,*QueuePtr;//数据结点类型
//链队结点
typedef struct {
QNode* front;//队头指针
QNode* rear;//队尾指针
}LinkQueue;//链队结点类型
Status InitQueue(LinkQueue& Q)
{
if (!(Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode))))
return ERROR;
Q.front->next = NULL;
return OK;
}
Status DestroyQueue(LinkQueue& Q)
{
while (Q.front) {
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
}
Status EnQueue(LinkQueue& Q, ElemType e)
{
QueuePtr p;
if(!(p = (QueuePtr)malloc(sizeof(QNode))))
return ERROR;//分配失败
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Status DeQueue(LinkQueue& Q, ElemType& e)
{
if (Q.front == Q.rear)
return ERROR;//队空
QueuePtr p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front;
free(p);
return OK;
}
Status GetHead(LinkQueue Q, ElemType& e)
{
if (Q.front == Q.rear)
return ERROR;
QueuePtr p = Q.front->next;
e = p->data;
return OK;
}
Status QueueEmpty(LinkQueue Q)
{
if (Q.front->next == Q.rear)
return TRUE;
return FALSE;
}
留言