当前位置：网站首页>受限线性表
受限线性表
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
边栏推荐
- Windows set redis to start automatically
- Summary of common methods of object class (September 14, 2020)
- How to change the formula picture in the paper directly into the formula in word
- Display the server hard disk image to the browser through Servlet
- Map operation execution process
- 8.31 Tencent interview
- 【7.4】25. K 个一组翻转链表
- Senior programmers must know and master. This article explains in detail the principle of MySQL master-slave synchronization, and recommends collecting
- [experiment sharing] log in to Cisco devices through the console port
- B_QuRT_User_Guide(40)
猜你喜欢
高效的S2B2C电商系统，是这样帮助电子材料企业提升应变能力的
Take you hand in hand to build Eureka server with idea
二叉排序树【BST】——创建、查找、删除、输出
B_QuRT_User_Guide(37)
What if once again forgets the login password of raspberry pie? And you don't have a monitor yet! Today, I would like to introduce a method
UE4_ Ue5 combined with Logitech handle (F710) use record
0-1背包问题
Take you hand in hand to build feign with idea
平衡二叉樹【AVL樹】——插入、删除
PCB wiring rules of PCI Express interface
随机推荐
Ora-02437 failed to verify the primary key violation
Markdown
How to change the formula picture in the paper directly into the formula in word
B_ QuRT_ User_ Guide(39)
Fibonacci number of dynamic programming
New potential energy of industrial integration, Xiamen station of city chain technology digital summit successfully held
ASP. Net query implementation
One of the anti climbing methods
Happy gathering time
USB (XVI) 2022-04-28
2022 Season 6 perfect children's model Shaanxi finals came to a successful conclusion
Flash encryption process and implementation of esp32
ASP. Net core middleware request processing pipeline
C number of words, plus ￥, longest word, average value
USB (XVII) 2022-04-15
ping报错:未知的名称或服务
SQL database execution problems
webflux - webclient Connect reset by peer Error
redis缓存工具类，值得拥有~
[compilation principle] lexical analysis design and Implementation