当前位置：网站首页>受限线性表
受限线性表
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
边栏推荐
- ESP at installation esp8266 and esp32 versions
- ASP. Net core middleware request processing pipeline
- SAP HR 社会工作经历 0023
- New potential energy of industrial integration, Xiamen station of city chain technology digital summit successfully held
- 通达信买基金安全吗？
- B_QuRT_User_Guide(36)
- Understand TCP's three handshakes and four waves with love
- [untitled]
- Markdown
- 【7.4】25. K 个一组翻转链表
猜你喜欢
SAP HR family member information
SRM supplier cloud collaborative management platform solution for building materials industry to realize business application scalability and configuration
Anxinco EC series modules are connected to the multi protocol access products of onenet Internet of things open platform
Interface
Design and implementation of spark offline development framework
Live-Server使用
UE4_ Use of ue5 blueprint command node (turn on / off screen response log publish full screen display)
B_QuRT_User_Guide(36)
Anxin vb01 offline voice module access intelligent curtain guidance
B_ QuRT_ User_ Guide(38)
随机推荐
How to change the formula picture in the paper directly into the formula in word
【leetcode】day1
【实验分享】通过Console口登录到Cisco设备
How to login and enable synchronization function in Google browser
Illegal behavior analysis 1
Take you hand in hand to build Eureka server with idea
SAP HR family member information
8.31 Tencent interview
二叉排序树【BST】——创建、查找、删除、输出
Design and implementation of spark offline development framework
Learn about scratch
ASP. Net open web page
[stm32+esp8266 connects to Tencent cloud IOT development platform 3] stm32+esp8266-01s dynamically registers devices on Tencent cloud (at instruction mode) -- with source code
【7.5】15. 三数之和
家用电器行业渠道商协同系统解决方案：助力家电企业快速实现渠道互联网化
数据分析系列 之3σ规则/依据拉依达准则来剔除异常值
Windows set redis to start automatically
SAP HR 劳动合同信息 0016
C simple question 2
Oracle statistics by time