栈和队列——考研笔记

发布于：2024-11-28 ⋅ 阅读:(17) ⋅ 点赞:(0)
微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

文章目录

一.栈（Stack）基本概念

  • 定义——“逻辑结构”
  • 基本操作——“运算”
    数据结构三要素——逻辑结构，数据的运算，存储结构（物理结构）存储结构不同，运算的实现方式也不同
    栈是仅允许在一端进行插入或删除操作的线性表

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

插入和删除和线性表有区别

1.栈的基本操作

在这里插入图片描述

2.栈的常考题型

在这里插入图片描述
所以有42种在这里插入图片描述

二.顺序栈的实现

在这里插入图片描述

1.顺序栈的定义

和顺序表类似

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];//静态数组存放栈中元素
	int top;//栈顶指针
}SqStack;

void testStack(){
	SqStack S;//声明一个顺序栈
	......
}

在这里插入图片描述

顺序存储，给各个数据元素分配连续的存储空间，大小为：MaxSize*sizeof(ElemType)

//初始化
void InitStack(SqStack &s){
	S.top=-1;//初始化栈顶指针
}
void test Stack（）{
	SqStack S;//声明一个顺序栈（分配空间）
	InitStack(S);
}
//判断栈空
bool StackEmpty(SqStack S){
	if(S.top==-1)//栈空
		return true;
	else
		return false;
}

在这里插入图片描述

2.增（进栈操作）

bool Push(SqStack &s,ElemType x){
	if(S.top==MaxSize-1)//栈满，报错
		return false;
	S.top=S.top+1;//指针先加一
	S.data[S.top]=x;//新元素入栈
	return true;
}

3.删（出栈操作）

bool Pop(SqStack &s,ElemType &x)
{
	if(S.top==-1)//栈空，报错
		return false;
	x=S.data(S.top);//栈顶元素先出栈
	S.top=S.top-1;//指针再-1
	return true;
}

在这里插入图片描述
读栈操作

bool GetTop(SqStack S,ElemTy0pe &x){
	if(S.top==-1)
		return false;
	x=S.data[S.top];//x记录栈顶元素
	return true;
}

注意审题top指针到底指那个位置

4.共享栈（两个栈共享同一片空间）

在这里插入图片描述

typedef struct{
	ElemType data[MaxSize];
	int top0;
	int top1;
}ShStack;
void InitStack(ShStack &S){
	S.top0=-1;
	S.top1=MaxSize;
}

栈满条件：top0+1==top+1
在这里插入图片描述

三.链栈的实现

  • 用链式存储方式实现的栈
  • 基本操作（增，删等）

1.头插法建立单链表->对应：进栈

在这里插入图片描述

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){
	if(p==NULL)
		return false;
	LNode* s=(LNode *)malloc(sizeof(LNode));
	if(s==NULL)//内存分配失败
		return false;
	s->data=e;//用结点s保存数据元素e
	s->next=p->next;
	p->next=s;//将结点s连接在p之后
	return true;
}

头插法建立单链表：
初始化单链表
while 循环
{
每次取一个数据元素e；
InsertNextNode（L，e）；
}

2.单链表删除操作（出栈）

链头=栈顶在这里插入图片描述
链栈的定义

typedef struct Linknode{
	ElemType data;//数据域
	struct Linknode * next;//指针域
}*Listack;//栈类型定义

在这里插入图片描述
在这里插入图片描述

四.队列（Queue）

  • 定义
  • 基本操作
    存储结构不同，运算方式也不同
    队列：只允许在一端插入（入队），另一端删除（出队）的线性表
    在这里插入图片描述
    先进先出
  1. 队头：
  2. 队尾
  3. 空队列：队列中无任何数据元素
  4. FIFO在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
#define MaxSize 10
	typedef struct data[MaxSize];//静态数组存放队列元素
	int front,rear;//队头和队尾指针
}SqQueue;

//变量声明
vid testQueue(){
	SqQueue Q;
}

在这里插入图片描述

//初始化队列
void InitQueue(SqQueue &Q){
	//初始时，队头队尾指针指向0
	Q.rear=Q.front=0;
}
void testQueue(){
	SqQueue Q;
	InitQueue(Q);
}
//判断队头队尾是否为空
bool QueueEmpty(SqQueue Q){
	if(Q.rear==Q.front)//队空
		return true;
	else
		return false;
}

1.入队操作

//从队尾入队
bool Insert(SqQueue &Q,ElemType x)
{
	if((Q.rear)+1%MaxSize==Q.front)
		return false;
	Q.data[Q.rear]=x;//x插到队尾
	Q.rear=（Q.rear+1）%MaxSize;///环状
	return true;
}

2.循环队列

用模运算将存储空间在逻辑上变成“环状”
在这里插入图片描述
在这里插入图片描述

3.循环队列（出队操作）

//出队：删除一个队头元素，用x返回
bool DeQueeu(SqQueue &Q,ElemType &x)
{
	if(q.rear==Q.front)
		return false;//队空
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
	return true;
}
		

//查,获得头元素的值，用x返回
bool GetHead (SqQueue Q,ElemType &x){
	if(Q.rear==Q.front)
		return false;
	x=Q.data[Q.front];
	return true;
}

方案一：判断队列已满/已空
队列元素个数：(rear +MaxSize -front)%MaxSize;

在这里插入图片描述
在这里插入图片描述
方案二：判断队列已满/已空

#define MaxSize 10
typedef struct{
	Elemtype data[MaxSize];
	int front,rear;
	int size;//队列当前长度，插入：size++，删除：size--.初始化时rear=front=0;size=0;
}SqQueue;

在这里插入图片描述
在这里插入图片描述
方案三：判断队列已满/已空

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int rear,front;
	int tag;//最近进行的是删除/插入
}SqQueue;

删除：tag=0
插入：tag=1
只有删除才可能导致队空
只有插入操作才有可能导致队满
队满：front == rear && tag ==1

队空：front == rear && tag ==0
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

4.队列的链式实现

typedef struct LinkNode{//链式队列节点
	ELemType data;
	struct LinkNode *next;
}LinkNode;

typedef struct{//链式队列
	LinkNode *front,*rear;//队列的队头指针和队尾指针
}LinkQueue;

在这里插入图片描述
在这里插入图片描述
链式存储实现的队列：链队列

typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode;

typedef struct{	
	LinkNode *front,*rear;
}LinkQueue;

//初始化带头结点
void InitQueue(LinkQueue &L){
	//初始时，rear和front都指向头结点
	L.rear=L.front=(LinkNode*)malloc(sizeof(LinkNode));
	L.front->next=NULL;
}

void testLinkNode(){
	LinkQueue Q;
	InitQueue(Q);
}
	


//判断队列是否为空
bool IsEmpty(){
	if(L.rear==L.front)
		return true;
	else
		return false;
}

在这里插入图片描述

//初始化不带头结点
bool InitQueue(LinkQueue &L){
	L.rear=NULL;
	L.front=NULL;
}

在这里插入图片描述

//入队，插入节点（带头结点）
bool InsertQueue(LinkQueue &L,ElemType e){
	LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));
	s->data=e;
	s->next=NULL;
	L->rear->next=s;//新节点插入到rear之后
	L.rear=s;//修改表尾指针
}

在这里插入图片描述
在这里插入图片描述

//入队，不带头结点
bool InsertQueue(LinkQueue &L,ElemType e){
	LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
	s->data=e;
	s->next=NULL;
	if(L.front==NULL){//在空队列中插入第一个元素
		L.front=s;//修改队头队尾指针
		L.rear=s;
	}else{
		L.rear->next=s;//新节点插入到rear之后
		L.rear=s;//修改rear指针
	}
}

在这里插入图片描述

//出队，带头结点
bool DeleteQueue(LinkQueue &L,ElemType &e)
{
	if(L.rear==L.front)
		return false;
	LinkNode *p=L.front->next;
	e=p->data;//用e返回队头元素
	L.front->next=p->next;//修改头结点的next指针
	if(L.rear==p)//最后一个结点出队
		L.rear=L.front;//修改rear指针
	free(p);//释放节点空间
	return true;
}

在这里插入图片描述
在这里插入图片描述

//出队，不带头结点
bool DeleteQueue(LinkQueue &L,ELemType &e){
	if(L.front==NULL)
		return false;
	LinkNode*p=L.front;//p指向此次出队的节点
	e=p->data;//用e返回队头元素
	L.front=p->next;//修改front指针
	if(L.rear==p){
		L.front=NULL;
		L.rear=NULL;
	}
	free(p);
	return true;
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
可加int length判断长度

五.双端队列

在这里插入图片描述
如果双端队列指从一端插入和删除，则双端队列转化为栈在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

六.特殊矩阵的压缩存储

在这里插入图片描述

6.1一维数组的存储结构

ElemType a[10];//ElemType 型一维数组 ，C语言定义一维数组

  • 各数组元素大小相同，且物理上连续存放
  • 数组元素a[i]存放地址=LOC+i*sizeof(ElemType)(0<=i<10)
  • 注：除题目特别说明，否则数组下标默认从0开始
    在这里插入图片描述

6.2二维数组的存储结构

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

6.3普通矩阵的存储

在这里插入图片描述
在这里插入图片描述
压缩存储策略：只存储主对角线与上（下）三角区
用行优先原则存储到一维数组中在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

6.4三角矩阵的压缩存储

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

6.5三对角矩阵的压缩存储

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

6.6稀疏矩阵的压缩存储

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

网站公告

今日签到

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

热门文章

最新发布