当前位置：网站首页>受限线性表
受限线性表
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
边栏推荐
- Installing gradle
- 进度播报|广州地铁七号线全线29台盾构机全部完成始发
- 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
- ESP at installation esp8266 and esp32 versions
- 企业应用需求导向开发之人力部门，员工考勤记录和实发工资业务程序案例
- One week learning summary of STL Standard Template Library
- Display the server hard disk image to the browser through Servlet
- Reverse output three digit and arithmetic sequence
- Have all the fresh students of 2022 found jobs? Is it OK to be we media?
- Summary of common methods of object class (September 14, 2020)
猜你喜欢
Deep understanding of MySQL lock and transaction isolation level
Understand TCP's three handshakes and four waves with love
Summary of SQL single table query 2020.7.27
S2b2b mall solution of intelligent supply chain in packaging industry: opening up a new ecosystem of e-commerce consumption
Ora-02437 failed to verify the primary key violation
Explain
SAP HR 社会工作经历 0023
As a new force, chenglian premium products was initially injected, and the shares of relevant listed companies rose 150% in response
Digital procurement management system for fresh food industry: help fresh food enterprises solve procurement problems and implement online procurement throughout the process
SRM supplier cloud collaborative management platform solution for building materials industry to realize business application scalability and configuration
随机推荐
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
Three questions TDM
Benchmarking Detection Transfer Learning with Vision Transformers（2021-11）
Installing gradle
B_QuRT_User_Guide(39)
Dataguard 主备清理归档设置
redis缓存工具类，值得拥有~
Markdown
Oracle string sorting
SQL database execution problems
进度播报|广州地铁七号线全线29台盾构机全部完成始发
Deep understanding of MySQL lock and transaction isolation level
Windows set redis to start automatically
MongoDB快速入门
C simple question one
Enumeration, simulation, and sorting
8.31 Tencent interview
Progress broadcast | all 29 shield machines of Guangzhou Metro Line 7 have been launched
Ora-02437 failed to verify the primary key violation
B_ QuRT_ User_ Guide(36)