数据结构-栈、队列和数组

发布于：2022-11-28 ⋅ 阅读:(322) ⋅ 点赞:(0)

目录

3.1 栈

3.1.1 栈的定义

3.1.2 顺序栈

3.1.3 链栈

3.2 队列

3.2.1 队列的概念

3.2.2 顺序队列

3.2.3 链式队列

3.2.4 双端队列

3.3 栈和队列的应用

3.3.1 栈的应用

1 括号匹配

2 表达式求值

3 递归

4 进制转换

5 迷宫求解

3.3.2 队列的应用

1 树的层次遍历

2 图的广度优先遍历

3 计算机缓冲区

4 页面替换算法

3.4 数组和特殊矩阵

3.1 栈

3.1.1 栈的定义

1、定义：栈是只允许在一端进行插入或删除操作的线性表。

2、基本概念：

  • 栈顶
  • 栈底
  • 空栈
  • 卡特兰数

3、操作特性：后进先出  LIFO

3.1.2 顺序栈

//顺序栈 
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10

typedef struct StackList {
	int data[MaxSize];
	int top;
}StackList;

//初始化
//栈顶指针初始设为-1，指向栈顶元素；若为0，则指向栈顶元素的下一个元素 
bool InitStack(StackList& S)
{
	S.top = -1;
	return true;
}

//判空 
//-1：空栈为-1     0：空栈为0 
bool EmptyStack(StackList S)
{
	if (S.top == -1)
		return true;
	else
		return false;
}

//判满 
//-1：满栈为maxsize-1    0：满栈为maxsize 
bool FullStack(StackList S)
{
	if (S.top == MaxSize - 1)
		return true;
	else
		return false;
}

//输出栈
bool PrintStack(StackList S)
{
	if (EmptyStack(S))
	{
		printf("the stack is empty!\n");
		return false;
	}
		
	for (int i = 0; i < S.top + 1; i++)
	{
		printf("%d\t", S.data[i]);
	}
	printf("\n");
	return true;
}

//入栈 
//-1：先top++再赋值   0：先赋值再top++ 
bool PushStack(StackList& S, int e)
{
	if (FullStack(S))
		return false;
	S.top++;
	S.data[S.top] = e;
	return true;
}

//出栈 
//-1：先赋值然后top--   0：先top--再赋值 
bool PopStack(StackList& S, int& e)
{
	if (EmptyStack(S))
		return false;
	e = S.data[S.top];
	S.top--;
	return true;
}

//弹出栈顶元素
//-1：S.top  0:S.top--
bool GetTop(StackList S, int& e)
{
	if (EmptyStack(S))
		return false;
	e = S.data[S.top]; 
	return true;
}

int main()
{
	StackList S;
	InitStack(S);
	PushStack(S, 1);
	PushStack(S, 55);
	PushStack(S, 999);
	PushStack(S, 888);

	PrintStack(S);

	int i=0;
	while(i<4)
	{
		int e=0;
		GetTop(S,e);
		printf("the top elem is %d\n",e);
		PopStack(S,e);
		PrintStack(S);
		i++;
	}

	return 0;

}

3.1.3 链栈

//带头结点的链栈 
#include <stdio.h>
#include <stdlib.h>


typedef struct SNode{
	int data;
	struct SNode *next;
}SNode,*LiStack;

//初始化
bool InitStack(LiStack &S)
{
	S=(SNode*)malloc(sizeof(SNode));
	if(S==NULL)
	{
		return false;
	}
	S->next=NULL;
	return true;	
}

//判空
bool EmptyStack(LiStack S)
{
	if(S->next==NULL)
		return true;
	else
		return false;	
} 

//输出
bool PrintStack(LiStack S)
{
	if(EmptyStack(S))
	{
		printf("the stack is empty\n");
		return false;
	}
	SNode *p=S->next;
	while(p!=NULL)
	{
		printf("%d\t",p->data);
		p=p->next;
	}
	printf("\n");
	return true;	
}

//进栈
bool PushStack(LiStack &S,int e)
{
	SNode *p=(SNode*)malloc(sizeof(SNode));
	p->data=e;
	p->next=S->next;
	S->next=p;
	return true;
}

//出栈
bool PopStack(LiStack &S,int &e)
{
	if(EmptyStack(S))
	{
		printf("the stack is empty\n");
		return false;
	}
	SNode *p=S->next;
	e=p->data;
	S->next=p->next;
	free(p);
}

//获取栈顶元素
int GetTop(LiStack S)
{
	if(EmptyStack(S))
	{
		printf("the stack is empty\n");
		return false;
	}
	int s=S->next->data;
	return s;
}

int main()
{
	LiStack S;
	InitStack(S);
	
	PushStack(S,1);
	PushStack(S,55);
	PushStack(S,666);
	PushStack(S,888);
	PushStack(S,999);
	
	PrintStack(S);
	
	int i=0;
	while(i<5)
	{
		int e=0;
		e=GetTop(S);
		printf("the top elem is %d\n",e);
		PopStack(S,e);
		PrintStack(S);
		i++;
	}
	return 0;

}

3.2 队列

3.2.1 队列的概念

1、队列：只允许在表的一端进行插入，另一端进行删除的线性表，是一种受限的线性表。

2、操作特性：先进先出  FIFO

3、队首、队尾、空队列

3.2.2 顺序队列

1、顺序队列

        分配一块连续的存储单元存放队列中的元素，并且设置两个指针front和rear，front指向队首，rear指向队尾元素的下一个位置（也可以指向队尾元素，处理方式不一样）

2、循环队列

        单纯的数组方式的顺序队列存在假溢出的问题，因此引入循环队列。

/*
rear指向队尾元素时
1、初始化
	Q.front=0
	Q.rear=MaxSize-1
2、入队
	Q.rear=(Q.rear+1)%MaxSize
	Q.data[Q.rear]=e;
3、出队
	e= Q.data[Q.front]
	Q.front=(Q.front+1)%MaxSize
4、队长
	(Q.rear+1+MaxSize-Q.front)%MaxSize
5、判空判满 
  （1）牺牲一个存储单元
  ***队空：(Q.rear+1)%MaxSize==Q.front  
  ***队满：我不会 
  （2）设置size
  （3）设置tag 
*/

/*
rear指向队尾元素的下一个元素时
1、初始化
	Q.front=0
	Q.rear=0
2、入队
	Q.data[Q.rear]=e;
	Q.rear=(Q.rear+1)%MaxSize
3、出队
	e= Q.data[Q.front]
	Q.front=(Q.front+1)%MaxSize
4、队长
	(Q.rear+MaxSize-Q.front)%MaxSize
5、判空判满 
   (1)牺牲一个存储单元，约定队首指针在队尾指针的下一位置作为队满标志
   ***空：Q.rear==Q.front  
   ***满:(Q.rear+1)%MaxSize==Q.front 
   (2)设置一个记录队列长度的变量size
   ***空：Q.size==0  
   ***满：Q.size==MaxSize 
   ***这两种情况都有Q.rear==Q.front 
   (3)设置一个tag；初始为0，每次插入后设置tag=1，删除后设置tag=0
   ***空： Q.rear==Q.front&&tag==0 
   ***满： Q.rear==Q.front&&tag==1 
*/

3、循环队列的实现（rear指向队尾的下一个元素+牺牲一个存储单元）


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MaxSize 10

typedef struct SqQueue
{
	int data[MaxSize];
	int front,rear;//front:队首指针，指向队首元素  rear:队尾指针，指向队尾元素的下一个位置 
};

bool InitQueue(SqQueue &Q); //初始化 
bool EmptyQueue(SqQueue Q); //判空 
bool FullQueue(SqQueue Q); //判满 
bool PrintQueue(SqQueue Q); //输出 
int LengthQueue(SqQueue Q); //队长 
bool EnQueue(SqQueue &Q,int e); //入队 
bool Dequeue(SqQueue &Q,int &e); //出队
bool GetFrontElem(SqQueue Q,int &e); //获取队首元素
 
//初始化 
bool InitQueue(SqQueue &Q)
{
	Q.front=Q.rear=0;
	return true;
}

//判空 
bool EmptyQueue(SqQueue Q)
{
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}
//判满 
bool FullQueue(SqQueue Q)
{
	if((Q.rear+1)%MaxSize==Q.front)
		return true;
	else
		return false;
}
//输出
bool PrintQueue(SqQueue Q)
{
	if(EmptyQueue(Q))
	{
		printf("the queue is empty, output error\n");
		return false;
	}
	//遍历是从front到rear，只要不等于rear，i就++，但是因为循环队列， 所以i要注意过了一圈，采用i=(i+1)%MaxSize 
	for(int i=Q.front;i!=Q.rear;i=(i+1)%MaxSize) 
	{
		printf("%d\t",Q.data[i]);
	}
	printf("\n");
}
//队长
int LengthQueue(SqQueue Q)
{
	return (Q.rear+MaxSize-Q.front)%MaxSize;
} 
//入队 
bool EnQueue(SqQueue &Q,int e)
{
	if(FullQueue(Q))
	{
		printf("the queue is full，insert error\n");
		return false;
	}
	Q.data[Q.rear]=e;
	Q.rear=(Q.rear+1)%MaxSize;
	return true;
}
//出队
bool DeQueue(SqQueue &Q,int &e)
{
	if(EmptyQueue(Q))
	{
		printf("the queue is empty, delete error\n");
		return false;
	}
	e=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
	return true;
} 
//获取队首元素 
bool GetFrontElem(SqQueue Q,int &e)
{
	if(EmptyQueue(Q))
	{
		printf("the queue is empty\n");
		return false;
	}
	e=Q.data[Q.front];
	return 0;
}

int main()
{
	SqQueue Q;
	InitQueue(Q);
	for(int i=0;i<5;i++)  //入队5个 
	{
		EnQueue(Q,pow(2,i));
	}
	PrintQueue(Q);
	
	int e=0;
	DeQueue(Q,e);
	printf("当前出队元素是%d\n",e); //出队1个 
	printf("the length of the queue is %d\n",LengthQueue(Q));
	PrintQueue(Q);
	
	for(int i=0;i<5;i++)  //入队6个 
	{
		EnQueue(Q,pow(4,i));
	}
	PrintQueue(Q);
	
	EnQueue(Q,100);//队满，插入失败 

	for(int j=0;j<10;j++)
	{
		if(DeQueue(Q,e))
		{
			printf("当前出队元素是%d\n",e);
			e=0; 
		}
		else
			break; //队空，停止出队 
	} 
	PrintQueue(Q); //队空，输出失败 
	
}

3.2.3 链式队列

1、链式队列

        一个同时带有队头指针和队尾指针的单链表；头指针指向队头结点，尾指针指向队尾结点。

2、实现

        

//带头结点的链式队列 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct QNode //链式队列结点 
{
	int data;
	struct QNode *next;	
}QNode;

typedef struct LinkQueue  //链式队列 
{
	QNode *front,*rear;//front指向头结点，rear指向队尾结点
	int length=0; 
}LinkQueue;

bool InitQueue(LinkQueue &Q); //初始化 
bool EmptyQueue(LinkQueue Q); //判空 
bool PrintQueue(LinkQueue Q); //输出 
int LengthQueue(LinkQueue Q); //队长 
bool EnQueue(LinkQueue &Q,int e); //入队 
bool DeQueue(LinkQueue &Q,int &e); //出队
bool GetFrontElem(LinkQueue Q,int &e); //获取队首元素

//初始化 
bool InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QNode*)malloc(sizeof(QNode));//建立头结点 
	Q.front->next=NULL; 
	return true;
}

//判空
bool EmptyQueue(LinkQueue Q)
{
	if(Q.front==Q.rear)
		return true;
	else
		return false;
} 
 
//输出
bool PrintQueue(LinkQueue Q)
{
	if(EmptyQueue(Q))
	{
		printf("the queue is empty, output error\n");
		return false;
	}
	QNode *s=Q.front->next;
	while(s)
	{
		printf("%d\t",s->data);
		s=s->next;
	}
	printf("\n");
	return true;
}

//入队
bool EnQueue(LinkQueue &Q,int e)
{
	QNode *s=(QNode*)malloc(sizeof(QNode));
	Q.rear->next=s;
	s->data=e;
	Q.rear=s;
	s->next=NULL;
	Q.length++;
	return true;
}
//出队
bool DeQueue(LinkQueue &Q,int &e)
{
	if(EmptyQueue(Q))
	{
		printf("the queue is empty,dequeue error\n");
		return false;
	}
	QNode *s=Q.front->next;
	e=s->data;
	Q.front->next=s->next;
	if(Q.rear==s)
		Q.rear=Q.front;
	free(s);
	Q.length--;
	return true;	
}
//获取队首元素
bool GetFrontElem(LinkQueue Q,int &e)
{
	if(EmptyQueue(Q))
	{
		printf("the queue is empty,dequeue error\n");
		return false;
	}
	QNode *s=Q.front->next;
	e=s->data;
	return true;
}

int main()
{
	LinkQueue Q;
	InitQueue(Q);
	
	for(int i=0;i<8;i++)  //入队8个 
	{
		EnQueue(Q,pow(2,i));
	}
	PrintQueue(Q);
	printf("the length of the queue is %d\n",Q.length);
	
	int e=0;
	printf("当前队首元素是%d\n",GetFrontElem(Q,e)); 
	
	DeQueue(Q,e);
	printf("当前出队元素是%d\n",e); //出队1个 
	printf("the length of the queue is %d\n",Q.length);
	PrintQueue(Q);
	
	printf("当前队首元素是%d\n",GetFrontElem(Q,e)); 
	
	for(int j=0;j<10;j++)
	{
		if(DeQueue(Q,e))
		{
			printf("当前出队元素是%d\n",e);
			e=0; 
		}
		else
			break; //队空，停止出队 
	} 
	PrintQueue(Q); //队空，输出失败 
	printf("the length of the queue is %d\n",Q.length);
}

3.2.4 双端队列

1、双端队列

        两端都可以进行入队和出队的队列。

2、分类

  • 输入受限的双端队列
  • 输出受限的双端队列
  • 两个栈底相邻的栈：从某端入队只能从某端出队

3.3 栈和队列的应用

3.3.1 栈的应用

1 括号匹配

  • 方法：

                依次扫描所有字符，遇到左括号入栈，遇到右括号弹出栈顶元素并判断是否匹配

  • 匹配失败的情况：

                左括号单，右括号单，左右括号不匹配

  • 代码实现
  • // stack.h
#pragma once
#ifndef STACK_H
#define STACK_H

#include <stdio.h>
#include <stdlib.h>

typedef struct StackNode
{
	char data ;
	struct StackNode* next;
}StackNode,*StackList;

bool InitStack(StackList &S);
bool EmptyStack(StackList S);
bool PrintList(StackList S);
int LengthStack(StackList S);
bool Push(StackList& S, char e);
bool Pop(StackList& S, char& e);
char GetTop(StackList S);

#endif 

    //stack.cpp
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
 
bool InitStack(StackList& S)
{
	S = (StackNode*)malloc(sizeof(StackNode));
	S->next = NULL;
	return true;
}

bool EmptyStack(StackList S)
{
	if (S->next == NULL)
		return true;
	else
		return false;
}

bool PrintList(StackList S)
{
	if (EmptyStack(S))
	{
		printf("the stack is empty,print error\n");
		return false;
	}
	StackNode* p = S->next;
	while (p != NULL)
	{
		printf("%c\t", p->data);
		p = p->next;
	}
	printf("\n");
	return true;
}

int LengthStack(StackList S)
{
	int length = 0;
	StackNode* p = S->next;
	while (p != NULL)
	{
		length++;
		p = p->next;
	}
	return length;
}

bool Push(StackList& S, char e)
{
	StackNode* p = (StackNode*)malloc(sizeof(StackNode));
	p ->data = e;
	p->next = S->next;
	S->next = p;
	return true;
}

bool Pop(StackList& S, char& e)
{
	if (EmptyStack(S))
	{
		printf("the stack is empty,pop error\n");
		return false;
	}
	StackNode* p = S->next;
	e = p->data;
	S->next = p->next;
	free(p);
	return true;
}

char GetTop(StackList S)
{
	if (EmptyStack(S))
	{
		printf("the stack is empty,GetTop error\n");
		return false;
	}
	StackNode* p = S->next;
	char e = p->data;
	free(p);
	return e;
}

  • //BracketCheck.cpp
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

#define MaxSize 100

bool BracketCheck(char s[], int length)
{
	StackList stack;
	InitStack(stack);
	for (int i = 0; i < length; i++)
	{
		if (s[i] == '(' || s[i] == '[' || s[i] == '{')
			Push(stack, s[i]);
		else
		{
			if (EmptyStack(stack))
				return false;
			char temp;
			Pop(stack, temp);
			if (s[i] == ')' && temp != '(')
				return false;
			else if (s[i] == ']' && temp != '[')
				return false;
			else if (s[i] == '}' && temp != '{')
				return false;

		}
	}
	if (EmptyStack(stack))
		return true;
	else
		return false;
}

int main()
{
	char s[MaxSize];
	char x = 'x';
	int i = 0;
	scanf_s("%c", &x,1);
	while (x != '\n')
	{
		s[i] = x;
		i++;
		scanf_s("%c", &x,1);
	}
	
	for (int j = 0; j < i; j++)
		printf("%c", s[j]);

	if (BracketCheck(s, i))
	{
		printf("success\n");
	}
	else
		printf("false\n");
	return 0;
}

2 表达式求值

···········表达式组成：界限符、运算符、操作数

（1）中缀表达式        操作数-运算符-操作数

***中缀表达式的计算：中缀转后缀+后缀的计算

（2）后缀表达式（逆波兰表达式）          操作数-操作数-运算符

***中缀转后缀

***后缀转中缀

        从左往右扫描，每遇到一个运算符，就将<左操作数  右操作数  运算符>转化为<左操作数 运算符 右操作数>的形式。

***后缀表达式的计算

        a. 手算  

        b. 代码实现

（3）前缀表达式（波兰表达式）        运算符-操作数-操作数

***中缀转前缀

*** 前缀表达式的计算

3 递归

  • 递归模型的条件：递归表达式+边界条件
  • 函数调用的特点：最后被调用的函数最先执行结束，即LIFO
  • 在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈进行数据存储，递归过多容易造成栈溢出。
  • 非递归算法通常比递归算法效率高
  • 消除递归可以借助栈实现；而对于单项递归和尾递归，可以用迭代的方式进行消除。

4 进制转换

5 迷宫求解

3.3.2 队列的应用

1 树的层次遍历

2 图的广度优先遍历

3 计算机缓冲区

  • 多个进程争抢使用有限的系统资源时，采用FCFS策略（先来先服务）

4 页面替换算法

3.4 数组和特殊矩阵

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布