栈和队列——考研笔记

发布于:2024-11-28 ⋅ 阅读:(29) ⋅ 点赞:(0)

一.栈(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稀疏矩阵的压缩存储

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

在这里插入图片描述