内容纲要

栈

栈的概念及特性:

  • 栈是一种特殊的线性表,其特殊性体现在元素插入和删除运算上,它的插入和删除运算仅限定在线性表的某一端进行,不能在表中间和另一端进行。
  • 栈的插入操作称为进栈(入栈、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;
}
最后修改日期:2020年4月11日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。