文章目录
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;
}
版权声明:本文为qq_42731062原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。