当前位置：网站首页>受限线性表
受限线性表
2022-07-07 21:53:00 【敏儿好xun】
栈（Stack）
栈的基本概念
- 遵循先进后出规则
- 不能遍历
- 栈中的数据元素遵守”后进先出”(First In Last Out)的原则，简称FILO结构。
- 限定只能在栈顶进行插入和删除操作。
栈的顺序存储
示例：
- 先建立一个 SeqStack.h 的头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//数组去模拟栈的顺序存储
#define MAX_SIZE 1024
#define SEQSTACK_TRUE 1
#define SEQSTACK_FALSE 0
typedef struct SEQSTACK
{
void* data[MAX_SIZE];
int size;
}SeqStack;
//初始化栈
SeqStack* Init_SeqStack();
//入栈
void Push_SeqStack(SeqStack* stack, void* data);
//返回栈顶元素
void* Top_SeqStack(SeqStack* stack);
//出栈
void Pop_SeqStack(SeqStack* stack);
//判断是否为空
int IsEmpty(SeqStack* stack);
//返回栈中元素的个数
int Size_SeqStack(SeqStack* stack);
//清空栈
void Clear_SeqStack(SeqStack* stack);
//销毁
void FreeSpace_SeqStack(SeqStack* stack);
- 建立一个 SeqStack.c 的源文件
#include "SeqStack.h"
//初始化栈
SeqStack* Init_SeqStack()
{
SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
for (int i = 0; i < MAX_SIZE; i++)
{
stack->data[i] = NULL;
}
stack->size = 0;
return stack;
}
//入栈
void Push_SeqStack(SeqStack* stack, void* data)
{
if (stack == NULL)
{
return;
}
if (data == NULL)
{
return;
}
if (stack->size == MAX_SIZE)
{
return;
}
stack->data[stack->size] = data;
stack->size++;
}
//返回栈顶元素
void* Top_SeqStack(SeqStack* stack)
{
if (stack == NULL)
{
return NULL;
}
if (stack->size == 0)
{
return NULL;
}
return stack->data[stack->size-1];//数组是从0开始的
}
//出栈
void Pop_SeqStack(SeqStack* stack)
{
if (stack == NULL)
{
return;
}
if (stack->size == 0)
{
return;
}
stack->data[stack->size-1] = NULL;
stack->size--;
}
//判断是否为空
int IsEmpty(SeqStack* stack)
{
if (stack == NULL)
{
return -1;
}
if (stack->size == 0)
return SEQSTACK_TRUE;
return SEQSTACK_FALSE;
}
//返回栈中元素的个数
int Size_SeqStack(SeqStack* stack)
{
return stack->size;
}
//清空栈
void Clear_SeqStack(SeqStack* stack)
{
if (stack == NULL)
{
return;
}
for (int i = 0; i < stack->size; i++)
{
stack->data[i] = NULL;
stack->size = 0;
}
}
//销毁
void FreeSpace_SeqStack(SeqStack* stack)
{
if (stack == NULL)
{
return;
}
free(stack);
}
- 建立一个 03栈的顺序存储.c 的源文件，进行测试
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"SeqStack.h"
typedef struct PERSON
{
char name[21];
int age;
}person;
int main()
{
//创建栈
SeqStack* stack = Init_SeqStack();
//创建数据
person p[3]=//==
{
{
"张三",19},
{
"李四",18},
{
"王五",20}
};
//数据入栈
for (int i = 0; i < 3; i++)
{
Push_SeqStack(stack, &p[i]);
}
//person p1 = { "张三",19 };//==
//person p2 = { "李四",18 };
//person p3 = { "王五",20 };
数据入栈
//Push_SeqStack(stack, &p1);
//Push_SeqStack(stack, &p2);
//Push_SeqStack(stack, &p3);
//输出
while (Size_SeqStack(stack) > 0)
{
//访问栈顶元素
person* person = Top_SeqStack(stack);
printf("姓名：%s 年龄：%d\n", person->name, person->age);
//弹出栈顶元素,出栈
Pop_SeqStack(stack);
}
//释放内存
FreeSpace_SeqStack(stack);
return 0;
}
结果：
姓名：王五 年龄：20
姓名：李四 年龄：18
姓名：张三 年龄：19
栈的链式存储
示例：
- 建立一个 LinkStack.h 的头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct LINKNODE
{
struct LINKNODE* next;
}LinkNode;
//链式栈
typedef struct LINKSTACK
{
LinkNode head;
int size;
}LinkStack;
//初始化函数
LinkStack* Init_LinkStack();
//入栈
void Push_LinkStack(LinkStack* lstack, LinkNode* data);
//出栈
void Pop_LinkStack(LinkStack* lstack);
//返回栈顶元素
LinkNode* Top_LinkStack(LinkStack* lstack);
//返回栈元素的个数
int Size_LinkStack(LinkStack* lstack);
//清空栈
void Clear_LinkStack(LinkStack* lstack);
//销毁栈
void FreeSpace_LinkStack(LinkStack* lstack);
- 建立一个 LinkStack.c 的源文件
#include"LinkStack.h"
//初始化函数
LinkStack* Init_LinkStack()
{
LinkStack* lstack = (LinkStack*)malloc(sizeof(LinkStack));
lstack->head.next= NULL;
lstack->size = 0;
return lstack;
}
//入栈
void Push_LinkStack(LinkStack* lstack, LinkNode* data)
{
if (lstack == NULL )
{
return;
}
if (data == NULL)
{
return;
}
data->next = lstack->head.next;//在进行链表插入时，先安排待插入结点的右边和谁连接
lstack->head.next = data;
lstack->size++;
}
//出栈
void Pop_LinkStack(LinkStack* lstack)
{
if (lstack == NULL)
{
return;
}
if (lstack->size == 0)
{
return;
}
//第一个有效结点
LinkNode* pnext = lstack->head.next;
lstack->head.next =pnext->next;
lstack->size--;
}
//返回栈顶元素
LinkNode* Top_LinkStack(LinkStack* lstack)
{
if (lstack == NULL)
{
return NULL;
}
if (lstack->size == 0)
{
return NULL;
}
return lstack->head.next;
}
//返回栈元素的个数
int Size_LinkStack(LinkStack* lstack)
{
if (lstack == NULL)
{
return -1;
}
return lstack->size;
}
//清空栈
void Clear_LinkStack(LinkStack* lstack)
{
if (lstack == NULL)
{
return;
}
lstack->head.next = NULL;
lstack->size = 0;
}
//销毁栈
void FreeSpace_LinkStack(LinkStack* lstack)
{
if (lstack == NULL)
{
return;
}
free(lstack);
}
- 建立一个 04栈的链式存储 源文件
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"LinkStack.h"
typedef struct PERSON
{
LinkNode node;
char name[21];
int age;
}person;
int main()
{
//创建栈链表
LinkStack* lstack = Init_LinkStack();
//创建数据
person p1, p2, p3,p4,p5;
strcpy(p1.name, "壹壹");
strcpy(p2.name, "贰贰");
strcpy(p3.name, "叁叁");
strcpy(p4.name, "肆肆");
strcpy(p5.name, "伍伍");
p1.age = 19;
p2.age = 30;
p3.age = 20;
p4.age = 18;
p5.age = 22;
//入栈
Push_LinkStack(lstack, (LinkNode*)&p1);//将元素写入的时候，需要将元素转换成，初始设定的数据类型，如LinkNode*
Push_LinkStack(lstack,(LinkNode*)&p2);
Push_LinkStack(lstack, (LinkNode*)&p3);
Push_LinkStack(lstack, (LinkNode*)&p4);
Push_LinkStack(lstack, (LinkNode*)&p5);
//输出
while (Size_LinkStack(lstack) > 0)
{
//取出栈顶元素
person* person = Top_LinkStack(lstack);
printf("姓名：%s 年龄：%d\n", person->name, person->age);
//弹出栈顶元素，出栈
Pop_LinkStack(lstack);
}
//销毁栈
FreeSpace_LinkStack(lstack);
return 0;
}
结果：
姓名：伍伍 年龄：22
姓名：肆肆 年龄：18
姓名：叁叁 年龄：20
姓名：贰贰 年龄：30
姓名：壹壹 年龄：19
队列（Queue）
队列基本概念
队列的顺序存储
- 数组模拟队列的顺序存储
示例：
- 先建立一个 SeqQueue.h 头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 1024
typedef struct SEQQUEUE
{
void* data[MAX_SIZE];
int size;
}SeqQueue;
//初始化
SeqQueue* Init_SeqQueue();
//入队
void Push_SeqQueue(SeqQueue* squeue, void* data);
//返回队头元素
void* Front_SeqQueue(SeqQueue* squeue);
//出队
void Pop_SeqQueue(SeqQueue* squeue);
//返回队尾元素
void* Back_SeqQueue(SeqQueue* squeue);
//返回大小
int Size_SeqQueue(SeqQueue* squeue);
//清空队列
void Clear_SeqQueue(SeqQueue* squeue);
//销毁
void Free_SeqQueue(SeqQueue* squeue);
- 建立一个 SeqQueue.c 源文件
#include "SeqQueue.h"
//初始化
SeqQueue* Init_SeqQueue()
{
SeqQueue* squeue = (SeqQueue*)malloc(sizeof(SeqQueue));
for (int i = 0; i < MAX_SIZE; i++)//因为 data 是数组，所以每个数组元素都得为NULL
{
squeue->data[i] = NULL;
}
squeue->size = 0;
return squeue;
}
//入队
void Push_SeqQueue(SeqQueue* squeue, void* data)
{
//数组左边当作队头，在尾部进行元素的添加
if (squeue == NULL || data == NULL)
{
return;
}
if (squeue->size == MAX_SIZE)
{
return;
}
squeue->data[squeue->size] = data;
squeue->size++;
}
//返回队头元素
void* Front_SeqQueue(SeqQueue* squeue)
{
if (squeue == NULL||squeue->size==0)
{
return NULL;
}
return squeue->data[0];
}
//出队
void Pop_SeqQueue(SeqQueue* squeue)
{
//从队首开始出，需要进行元素的移动
if (squeue == NULL || squeue->size == 0)
{
return;
}
for (int i = 0; i < squeue->size-1; i++)//将后面的元素，挪到前面，覆盖前一个
{
squeue->data[i] = squeue->data[i + 1];
}
squeue->size--;
}
//返回队尾元素
void* Back_SeqQueue(SeqQueue* squeue)
{
if (squeue == NULL||squeue->size==0)
{
return NULL;
}
return squeue->data[squeue->size-1];
}
//返回大小
int Size_SeqQueue(SeqQueue* squeue)
{
if (squeue == NULL)
{
return -1;
}
return squeue->size;
}
//清空队列
void Clear_SeqQueue(SeqQueue* squeue)
{
if (squeue == NULL)
{
return;
}
squeue->size = 0;
}
//销毁
void Free_SeqQueue(SeqQueue* squeue)
{
if (squeue == NULL)
{
return;
}
free(squeue);
}
- 建立一个 05队列的顺序存储.c 源文件
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "SeqQueue.h"
typedef struct PERSON
{
char name[21];
int age;
}person;
int main()
{
//创建队列
SeqQueue* squeue = Init_SeqQueue();
person p[3] =
{
{
"嘻嘻",25},
{
"哈哈",24},
{
"呵呵",26}
};
//数据入队列
for (int i = 0; i < 3; i++)
{
Push_SeqQueue(squeue,&p[i]);
}
//输出
while (Size_SeqQueue(squeue) > 0)
{
//取出队头元素
person* p = Front_SeqQueue(squeue);
printf("姓名：%s 年龄：%d\n", p->name, p->age);
//从队头弹出元素
Pop_SeqQueue(squeue);
}
//销毁
Free_SeqQueue(squeue);
return 0;
}
结果：
姓名：嘻嘻 年龄：25
姓名：哈哈 年龄：24
姓名：呵呵 年龄：26
队列的链式存储
- 结点包括数据域和指针域。
- 数据域为void* 类型，存在头结点和为结点。
- 头结点为指针类型，在入队的时候需要创建新结点，并为其开辟空间。
示例：
- 创建一个 LinkQueue.h 的头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//链式队列的结点
typedef struct LINKNODE
{
void* data;//结点数据
struct LINKNODE* next;
}LinkNode;
//链式队列
typedef struct LINKQUEUE
{
LinkNode* head;
LinkNode* tail;//尾结点
int size;
}LinkQueue;
//初始化队列
LinkQueue* Init_LinkQueue();
//入队
void Push_LinkQueue(LinkQueue* lqueue, void* data);
//返回队首元素
void* Front_LinkQueue(LinkQueue* lqueue);
//出队
void Pop_LinkQueue(LinkQueue* lqueue);
//返回队尾元素
void* Back_LinkQueue(LinkQueue* lqueue);
//返回大小
int Size_LinkQueue(LinkQueue* lqueue);
//清空队列
void Clear_LinkQueue(LinkQueue* lqueue);
//销毁
void Free_LinkQueue(LinkQueue* lququ);
- 创建 LinkQueue.c 源文件
#include"LinkQueue.h"
//初始化队列
LinkQueue* Init_LinkQueue()
{
LinkQueue* lqueue = (LinkQueue*)malloc(sizeof(LinkQueue));
lqueue->head= NULL;
lqueue->tail = NULL;
lqueue->size = 0;
}
//入队,从队尾开始添加元素
void Push_LinkQueue(LinkQueue* lqueue, void* data)
{
if (lqueue == NULL || data == NULL)
{
return;
}
//创建新结点
LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
newnode->data = data;
newnode->next = NULL;
if (lqueue->head== NULL)
{
lqueue->head = lqueue->tail = newnode;
}
else
{
lqueue->tail->next = newnode;
lqueue->tail = lqueue->tail->next;
}
lqueue->size++;
}
//返回队首元素
void* Front_LinkQueue(LinkQueue* lqueue)
{
if (lqueue == NULL||lqueue->size==0)
{
return NULL;
}
return lqueue->head->data;
}
//出队
void Pop_LinkQueue(LinkQueue* lqueue)
{
if (lqueue == NULL || lqueue->size == 0)
{
return;
}
LinkNode* pdel = lqueue->head;
//LinkNode* pnext = lqueue->head;
lqueue->head = lqueue->head->next;;
lqueue->size--;
free(pdel);
}
//返回队尾元素
void* Back_LinkQueue(LinkQueue* lqueue)
{
if (lqueue == NULL || lqueue->size == NULL)
{
return NULL;
}
return lqueue->tail->data;//
}
//返回大小
int Size_LinkQueue(LinkQueue* lqueue)
{
if (lqueue == NULL)
{
return -1;
}
return lqueue->size;
}
//清空队列
void Clear_LinkQueue(LinkQueue* lqueue)
{
if (lqueue == NULL)
{
return;
}
lqueue->size = 0;
}
//销毁
void Free_LinkQueue(LinkQueue* lqueue)
{
if (lqueue == NULL)
{
return;
}
free(lqueue);
}
- 创建 06队列的链式存储.c 源文件
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"LinkQueue.h"
typedef struct PERSON
{
char name[21];
int age;
int score;
}person;
int main()
{
//创建队列
LinkQueue* lqueue = Init_LinkQueue();
//创建数据
person p[3]=
{
{
"花花",25,98},
{
"草草",23,89},
{
"树树",26,99}
};
//数据入队
for (int i = 0; i < 3;i++)
{
Push_LinkQueue(lqueue, &p[i]);
}
//取出队头元素
person* fnode = Front_LinkQueue(lqueue);
printf("队头的元素为——姓名：%s 年龄：%d 成绩：%d\n", fnode->name, fnode->age, fnode->score);
//取出队尾元素
person* bnode = Back_LinkQueue(lqueue);
printf("队尾的元素为——姓名：%s 年龄：%d 成绩：%d\n", bnode->name, bnode->age, bnode->score);
while (lqueue->size>0)
{
//输出
person* per = Front_LinkQueue(lqueue);
printf("姓名：%s 年龄：%d 成绩：%d\n", per->name, per->age, per->score);
Pop_LinkQueue(lqueue);
}
//销毁
Free_LinkQueue(lqueue);
return 0;
}
结果：
队头的元素为——姓名：花花 年龄：25 成绩：98
队尾的元素为——姓名：树树 年龄：26 成绩：99
姓名：花花 年龄：25 成绩：98
姓名：草草 年龄：23 成绩：89
姓名：树树 年龄：26 成绩：99
边栏推荐
- Fibonacci number of dynamic programming
- SRM supplier cloud collaborative management platform solution for building materials industry to realize business application scalability and configuration
- 【汇总】看过的一些Panel与视频
- 建筑建材行业SRM供应商云协同管理平台解决方案，实现业务应用可扩展可配置
- postgis学习
- May day C - most
- postgres timestamp转人眼时间字符串或者毫秒值
- Boost regex library source code compilation
- 0-1背包问题
- MySQL Architecture
猜你喜欢
KeePass realizes automatic input of web pages
![Balanced binary tree [AVL tree] - insert, delete](/img/1f/cd38b7c6f00f2b3e85d4560181a9d2.png)
Balanced binary tree [AVL tree] - insert, delete
B_ QuRT_ User_ Guide(38)
Lm12 rolling heikin Ashi double K-line filter
![[STM32 + esp-12s connect Tencent cloud IOT development platform 1] creation of cloud platform and burning of at firmware](/img/bc/8241a339cca9b7af475169dba39c10.jpg)
[STM32 + esp-12s connect Tencent cloud IOT development platform 1] creation of cloud platform and burning of at firmware
B_QuRT_User_Guide(36)
Markdown
C inheritance and interface design polymorphism
Class C design questions
Live server usage
随机推荐
Happy gathering time
数据分析系列 之3σ规则/依据拉依达准则来剔除异常值
B_ QuRT_ User_ Guide(38)
Deep understanding of MySQL lock and transaction isolation level
MySQL Architecture
postgres timestamp转人眼时间字符串或者毫秒值
MySQL架构
SAP HR family member information
USB (XVII) 2022-04-15
List. How to achieve ascending and descending sort() 2020.8.6
Anxinco EC series modules are connected to the multi protocol access products of onenet Internet of things open platform
One of the anti climbing methods
C simple question one
Dataguard 主备清理归档设置
Ora-02437 failed to verify the primary key violation
Anxin can internally test offline voice module vb-01 to communicate with esp-c3-12f
生鲜行业数字化采购管理系统：助力生鲜企业解决采购难题，全程线上化采购执行
Take you hand in hand to build Eureka server with idea
Given an array, such as [7864, 284, 347, 7732, 8498], now you need to splice the numbers in the array to return the "largest possible number."
B_QuRT_User_Guide(38)