文章目录

1. 栈
2. 循环队列
3. 中级Day4作业
4. 中级Day5作业

1. 栈

1.1 定义

在这里插入图片描述

基本操作

1.2 栈的顺序存储

栈为空
栈满

1.2.1 元素入栈

// 入栈
bool Push(SqStack& S, ElemType x)
{
	if (S.top == MaxSize - 1)// 栈满，不能入栈
	{
		return false;
	}
	S.data[++S.top] = x;// top从-1开始，++S.top之后top = 0
	return true;// 入栈成功
}

在这里插入图片描述

1.2.2 元素出栈

// 弹出栈顶元素
bool Pop(SqStack& S, ElemType& x)
{
	if (StackEmpty(S))// 栈为空
	{
		return false;
	}
	x = S.data[S.top];// 等价于x = S.data[S.top--]
	S.top--;
	return true;
}

在这里插入图片描述

1.3 栈的链表存储

元素入栈
元素出栈，Lhead后面的元素就是栈顶元素(top)
栈满

1.4 总程序

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

// 实现栈，可以用数组，也可以用链表，这里使用数组
#define MaxSize 50
typedef int ElemType;
typedef struct
{
	ElemType data[MaxSize];// 数组
	int top;
}SqStack;// 结构体起别名Sqstack

// 初始化
void InitStack(SqStack &S)// 加引用表示要对其进行修改操作
{
	S.top = -1;// 栈顶 = -1，代表栈为空
}

// 读数据
bool StackEmpty(SqStack S)// 不用加引用
{
	if (S.top == -1)
	{
		return true;
	}
	return false;
}

// 入栈
bool Push(SqStack& S, ElemType x)
{
	if (S.top == MaxSize - 1)// 栈满，不能入栈
	{
		return false;
	}
	S.data[++S.top] = x;// top从-1开始，++S.top之后top = 0
	return true;// 入栈成功
}

// 获取栈顶元素
bool GetTop(SqStack S, ElemType &x)// x的值要改变
{
	if (StackEmpty(S))// 栈为空，则StackEmpty(S)的值为true
	{
		return false;
	}
	/*if (S.top == -1)与上面StackEmpty(S)的效果一致
		return false;*/
	x = S.data[S.top];
	return true;
}

// 弹出栈顶元素
bool Pop(SqStack& S, ElemType& x)
{
	if (StackEmpty(S))// 栈为空
	{
		return false;
	}
	x = S.data[S.top];// 等价于x = S.data[S.top--]
	S.top--;
	return true;
}

int main()
{
	SqStack S;// 先进后出 FILO LIFO
	bool flag;
	ElemType m;// 用来存放拿出的元素，下面有用
	InitStack(S);// 初始化
	flag = StackEmpty(S);
	if (flag)
	{
		printf("栈是空的\n");
	}
	Push(S, 3);// 入栈元素3
	Push(S, 4);// 入栈元素4
	Push(S, 5);
	flag = GetTop(S, m);// 获取栈顶元素,但是S.top的值不变
	if (flag)
	{
		printf("获取栈顶元素为%d\n", m);
	}
	flag = Pop(S, m);// 弹出栈顶元素
	if (flag)
	{
		printf("弹出元素为%d\n", m);
	}
	return 0;
}

2. 循环队列

2.1 定义

在这里插入图片描述

初始化

2.2 元素入队

// 入队
bool EnQueue(SqQueue& Q, ElemType x)
{
	if ((Q.rear + 1) % MaxSize == Q.front)// 表示队列满了
	{
		return false;// 队列满了
	}
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;// 向后移动一格
	return true;
}

在这里插入图片描述

2.3 元素出队

// 出队
bool DeQueue(SqQueue &Q, ElemType &x)// 两个都要加引用,出队要改变x,x是起接收的作用
{
	if (Q.front == Q.rear)// 队列为空
	{
		return false;
	}
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;// 向后移动一格
	return true;
}

在这里插入图片描述

2.4 总程序

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

#define MaxSize 5// 这里没有封号
typedef int ElemType;
typedef struct
{
	ElemType data[MaxSize];// 存储MaxSize-1个元素
	int front, rear;// 队列头，队列尾
}SqQueue;

// 队列初始化，让队列为空
void InitQueue(SqQueue& Q)
{
	Q.front = 0;
	Q.rear = 0;// 队列尾
}

// 判断队列是否是空, 知识判断, 不需要加引用
bool isEmpty(SqQueue Q)
{
	if (Q.front == Q.rear)
	{
		return true;// 是空队列
	}
	return false;
}

// 入队
bool EnQueue(SqQueue& Q, ElemType x)
{
	if ((Q.rear + 1) % MaxSize == Q.front)// 表示队列满了
	{
		return false;// 队列满了
	}
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;// 向后移动一格
	return true;
}

// 出队
bool DeQueue(SqQueue &Q, ElemType &x)// 两个都要加引用,出队要改变x,x是起接收的作用
{
	if (Q.front == Q.rear)// 队列为空
	{
		return false;
	}
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;// 向后移动一格
	return true;
}

int main()
{
	SqQueue Q;
	InitQueue(Q);// 初始化循环队列
	bool ret;// 存储返回值

	// 判断队列是否为空
	ret = isEmpty(Q);
	if (ret)
	{
		printf("队列为空\n");
	}
	else
	{
		printf("队列不为空\n");
	}

	// 入队
	EnQueue(Q, 3);
	EnQueue(Q, 4);
	EnQueue(Q, 5);
	ret = EnQueue(Q, 6);
	/*ret = EnQueue(Q, 7);*/// 只能存储4个元素
	if (ret)
	{
		printf("入队成功\n");
	}
	else
	{
		printf("入队失败\n");
	}
	
	// 出队
	ElemType element;
	ret = DeQueue(Q, element);
	if (ret)
	{
		printf("出队成功，元素值为%d\n", element);
	}
	else
	{
		printf("出队失败\n");
	}

	ret = DeQueue(Q, element);
	if (ret)
	{
		printf("出队成功，元素值为%d\n", element);
	}
	else
	{
		printf("出队失败\n");
	}
	return 0;
}

2.5 队列的链式存储

在这里插入图片描述

添加尾指针

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

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

typedef struct
{
	LinkNode* front, * rear;// 链表头，链表尾
}LinkQueue;// 先进先出

// 队列初始化
void InitQueue(LinkQueue& Q)
{
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));// 头和尾指向同一个结点
	Q.front->next = NULL;// 头结点next指针为NULL
}

bool IsEmpty(LinkQueue Q)
{
	if (Q.front == Q.rear)
	{
		return true;
	}
	else
	{
		return false;
	}
}

// 入队，尾部插入法
void EnQueue(LinkQueue& Q, ElemType x)
{
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	Q.rear->next = s;// rear始终指向尾部，相当于把s的地址填到上一个结点的next位置，就是建立与上一个结点的联系
	Q.rear = s;// 更新尾结点到s
}

// 出队，头部删除法
bool DeQueue(LinkQueue& Q, ElemType &x)
{
	if (Q.front == Q.rear)
		return false;// 队列为空
	LinkNode* p = Q.front->next;// 头结点什么都没有，所以头结点的下一个结点才有数据
	x = p->data;
	Q.front->next = p->next;// 断链，将p的链赋给front
	if (Q.rear == p)// 删除的是最后一个元素
		Q.rear = Q.front;// 队列置为空
	free(p);
	return true;
}

// 头部删除法，尾部插入法
int main()
{
	LinkQueue Q;
	bool ret;
	ElemType element;// 存储出队元素
	InitQueue(Q);// 初始化队列
	EnQueue(Q, 3);
	EnQueue(Q, 4);
	EnQueue(Q, 5);
	EnQueue(Q, 6);
	EnQueue(Q, 7);
	ret = DeQueue(Q, element);
	if (ret)
	{
		printf("出队成功，元素值为%d\n", element);
	}
	else
	{
		printf("出队失败\n");
	}
}

3. 中级Day4作业

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>// malloc关键字

typedef int ElemType;
typedef struct LNode// data是4个字节，指针是4个字节，一共8个字节
{
	ElemType data;
	struct LNode* next;// 指向下一个结点
}LNode, * LinkList;// LinkList等价于struct LNode *,LNode和上面相同没问题

// 头插法新建链表
LinkList CreateList1(LinkList& L)// list_head_insert，加了引用&函数中的L与主函数中的L是同一个值，可以修改
{
	LNode* s; int x;// s为结构体指针，所以用->指向成员
	L = (LinkList)malloc(sizeof(LNode));// 创建带头结点的链表L，L表示头指针
	L->next = NULL;// L->data里边没有东西
	scanf("%d", &x);// 从标准输入读取数据
	// 3 4 5 6 7 9999
	while (x != 9999)
	{
		s = (LNode*)malloc(sizeof(LNode));// 申请一个空间，强制类型转换
		s->data = x;// 把读取的值，给新空间中的data成员
		s->next = L->next;// 让新结点的next指针指向链表的第一个元素(不是指L,而是指a1),第一个放我们数据的元素
		L->next = s;// 让s成为第1个元素
		scanf("%d", &x);// 读取标准输入
	}
	return L;
}

// 尾插法新建链表(r用来一直指向尾部)
LinkList CreateList2(LinkList& L)
{
	int x;
	L = (LinkList)malloc(sizeof(LNode));// 带有头结点的链表
	LNode* s, * r = L;// s与r都是结构体指针，写成LinkList s , r = L也可以；r代表链表表尾结点，指向链表尾部
	// 3 4 5 6 7 9999
	scanf("%d", &x);
	while (x != 9999)// r一直是表尾结点，s是新插入的结点
	{
		s = (LNode*)malloc(sizeof(LNode));// LNode* 和 LinkLis都可以，本质是等价的
		s->data = x;
		r->next = s;// r本身就是表尾结点，让尾部结点指向新结点s,s就是不断创造出来的新结点
		r = s;// r指向新的尾插结点
		scanf("%d", &x);
	}
	r->next = NULL;// 尾结点的next指针赋值为NULL
	return L;
}

// 打印链表中每个结点的值
void PrintList(LinkList L)// 这里没写引用
{
	L = L->next;// 让L指向第1个有数据的结点
	while (L != NULL)// NULL就是代表一张空的藏宝图，
	{
		printf("%d", L->data);// 打印当前结点数据
		L = L->next;// 指向下一个结点，如果有NULL的话，就截止(L真实指向的应该是结点的第二个位置)
		if (L != NULL)
		{
			printf(" ");
		}
	}
	printf("\n");
}

int main()
{
	LinkList L = NULL;// 链表头，是结构体指针类型
	LinkList search;// 用来存储拿到的某一个节点
	CreateList1(L);// 输入的数据可以为3 4 5 6 7 999,头插法倒着排序
	PrintList(L);// 打印链表
	CreateList2(L);// 输入的数据可以为3 4 5 6 7 999，尾插法顺着排序
	PrintList(L);// 打印链表
	return 0;
}

4. 中级Day5作业

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

typedef int ElemType;
typedef struct LNode// data是4个字节，指针是4个字节，一共8个字节
{
	ElemType data;
	struct LNode* next;// 指向下一个结点
}LNode, * LinkList;

// 尾插法新建链表(r用来一直指向尾部)
LinkList CreateList2(LinkList& L)
{
	int x;
	L = (LinkList)malloc(sizeof(LNode));// 带有头结点的链表
	LNode* s, * r = L;// s与r都是结构体指针，写成LinkList s , r = L也可以；r代表链表表尾结点，指向链表尾部
	// 3 4 5 6 7 9999
	scanf("%d", &x);
	while (x != 9999)// r一直是表尾结点，s是新插入的结点
	{
		s = (LNode*)malloc(sizeof(LNode));// LNode* 和 LinkList都可以，本质是等价的
		s->data = x;
		r->next = s;// r本身就是表尾结点，让尾部结点指向新结点s,s就是不断创造出来的新结点
		r = s;// r指向新的尾插结点
		scanf("%d", &x);
	}
	r->next = NULL;// 尾结点的next指针赋值为NULL
	return L;
}

// 按序号查找结点
LNode* GetElem(LinkList L, int i)// L没有被改变，不用加引用&
{
	int j = 1;
	LNode* p = L->next;// L为头结点，让p指向第1个结点就是a1
	if (i == 0)
	{
		return L;// i为0就返回头结点
	}
	if (i < 1)
	{
		return NULL;// i是负值就返回空
	}
	while (p && j < i)
	{
		p = p->next;// p指向下一个a2
		j++;
	}
	return p;
}

// 新结点插入第i个位置
bool ListFrontInsert(LinkList L, int i, ElemType e)
{
	LinkList p = GetElem(L, i - 1);// p指向a(i-1)的位置,拿到要插入前一个位置的地址值
	if (p == NULL)
	{
		return false;
	}
	LinkList s = (LNode*)malloc(sizeof(LNode));// 为新插入的结点申请空间，LNode*换成LinkList也可以
	s->data = e;
	s->next = p->next;
	p->next = s;// s里面是起始地址，所以让p指向s
	return true;
}

// 删除第i个位置的元素
bool ListDelete(LinkList L, int i)
{
	LinkList p = GetElem(L, i - 1);// 查找删除位置的前驱结点
	if (p == NULL)// 空指针
	{
		return false;// 要删除的位置不存在
	}
	LinkList q = p->next;
	if (q == NULL)
	{
		return false;// q不存在则返回错误
	}
	p->next = q->next;// 断链
	free(q);// 释放对应结点的空间
	q = NULL;// 避免q成为野指针
	return true;//应该不是false
}

// 打印链表中每个结点的值
void PrintList(LinkList L)// 这里没写引用
{
	L = L->next;// 意思是L指向第一个放数据的元素a1的位置
	while (L != NULL)// NULL就是代表一张空的藏宝图，
	{
		printf("%3d", L->data);// 打印当前结点数据
		L = L->next;// 指向下一个结点，如果有NULL的话，就截止(L真实指向的应该是结点的第二个位置)
	}
	printf("\n");
}

int main()
{
	LinkList L;// 链表头，是结构体指针类型
	LinkList search;// 用来存储拿到的某一个节点
	CreateList2(L);// 输入的数据可以为3 4 5 6 7 999,尾插法

	// 按照序号查找
	search = GetElem(L, 2);// 查找链表第2个位置元素的值
	if (search != NULL)
	{
		printf("%d\n", search->data);
	}

	// 插入
	ListFrontInsert(L, 2, 99);// 新结点插入第i个位置
	PrintList(L);

	// 删除
	ListDelete(L, 4);// 删除第4个结点
	PrintList(L);// 打印注意函数
	return 0;
}

原文链接：https://blog.csdn.net/qq_42731062/article/details/129176765

C 数据结构2 —— 栈\队列

文章目录

1. 栈

1.1 定义

1.2 栈的顺序存储

1.2.1 元素入栈

1.2.2 元素出栈

1.3 栈的链表存储

1.4 总程序

2. 循环队列

2.1 定义

2.2 元素入队

2.3 元素出队

2.4 总程序

2.5 队列的链式存储

3. 中级Day4作业

4. 中级Day5作业

标签云

近期文章

分类

C 数据结构2 —— 栈\队列

文章目录

1. 栈

1.1 定义

1.2 栈的顺序存储

1.2.1 元素入栈

1.2.2 元素出栈

1.3 栈的链表存储

1.4 总程序

2. 循环队列

2.1 定义

2.2 元素入队

2.3 元素出队

2.4 总程序

2.5 队列的链式存储

3. 中级Day4作业

4. 中级Day5作业

相关文章