数据结构之_栈的顺序存储和链式存储的代码实现

加入我们QQ群：183791416 致读者的话：曾经的我们很年少，现在我们要为理想的路疯狂的走下去。

数据结构之_栈的顺序存储和链式存储的代码实现

正文

回到顶部

数据结构之_栈的顺序存储和链式存储的代码实现

1.栈的基本概念

概念：

　　　　首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

特性

　　　　它的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。

操作
- 　　栈的插入操作，叫做进栈，也成压栈。类似子弹入弹夹（如下图所示）
- 　　栈的删除操作，叫做出栈，也有的叫做弾栈，退栈。如同弹夹中的子弹出夹（如下图所示）

- 　　创建栈
- 　　销毁栈
- 　　清空栈
- 　　进栈
- 　　出栈
- 　　获取栈顶元素
- 　　获取栈的大小

栈的抽象数据类型

ADT 栈（stack）

Data

通线性表。元素具有相同的类型，相邻的元素具有前驱和后继关系。

Operation

// 初始化，建立一个空栈S

InitStack(*S);

// 若栈存在，则销毁它

DestroyStack(*S);

// 将栈清空

ClearStack(*S);

// 若栈为空则返回true，否则返回false

StackEmpty(S);

// 若栈存在且非空，用e返回S的栈顶元素

GetTop(S，*e);

// 若栈S存在，插入新元素e到栈S中并成为其栈顶元素

Push(*S，e);

// 删除栈S中的栈顶元素，并用e返回其值

Pop（*S, *e）;

// 返回栈S的元素个数

StackLength(S);

endADT

2.栈的顺序存储代码实现

基本概念

　　　　栈的顺序存储结构简称顺序栈，它是运算受限制的顺序表。顺序栈的存储结构是：利用一组地址连续的的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top只是栈顶元素在顺序表中的位置。

设计与实现

　　　　因为栈是一种特殊的线性表，所以栈的顺序存储可以通过顺序线性表来实现。

SeqStack.h　　

#ifndef SEQSTACK_H

#define SEQSTACK_H

#include<stdlib.h>

#include<stdio.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);

#endif

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 (stack->size == MAX_SIZE) {

return;

}

if (data == NULL) {

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];

}

//出栈

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);

}

栈的顺序存储.c　　

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "SeqStack.h"

typedef struct PERSON {

char name[64];

int age;

}Person;

int main(void) {

//创建栈

SeqStack* stack = Init_SeqStack();

//创建数据

Person p1 = { "aaa", 10 };

Person p2 = { "bbb", 20 };

Person p3 = { "ccc", 30 };

Person p4 = { "ddd", 40 };

Person p5 = { "eee", 50 };

//入栈

Push_SeqStack(stack, &p1);

Push_SeqStack(stack, &p2);

Push_SeqStack(stack, &p3);

Push_SeqStack(stack, &p4);

Push_SeqStack(stack, &p5);

//输出

while (Size_SeqStack(stack) > 0) {

//访问栈顶元素

Person* person = (Person*)Top_SeqStack(stack);

printf("Name:%s Age:%d\n", person->name, person->age);

//弹出栈顶元素

Pop_SeqStack(stack);

}

//释放内存

FreeSpace_SeqStack(stack);

system("pause");

return 0;

}

3.栈的链式存储　　

基本概念

　　　　栈的链式存储结构简称链栈。

　　　　思考如下问题：

　　栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？

　　　　答：由于单链表有头指针，而栈顶指针也是必须的，那干嘛不让他俩合二为一呢，所以比较好的办法就是把栈顶放在单链表的头部。另外都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

设计与实现

　　　　链栈是一种特殊的线性表，链栈可以通过链式线性表来实现。

LinkStack.h

#ifndef LINKSTACK_H

#define LINKSTACK_H

#include <stdlib.h>

#include <stdio.h>

//链式栈的结点

typedef struct LINKNODE {

struct LINKNODE* next;

}LinkNode;

//链式栈

typedef struct LINKSTACK {

LinkNode head;

int size;

}LinkStack;

//初始化函数

LinkStack* Init_LinkStack();

//入栈

void Push_LinkStack(LinkStack* stack, LinkNode* data);

//出栈

void Pop_LinkStack(LinkStack* stack);

//返回栈顶元素

LinkNode* Top_LinkStack(LinkStack* stack);

//返回栈元素的个数

int Size_LinkStack(LinkStack* stack);

//清空栈

void Clear_LinkStack(LinkStack* stack);

//销毁栈

void FreeSpace_LinkStack(LinkStack* stack);

#endif

LinkStack.c　　

#include"LinkStack.h"

//初始化函数

LinkStack* Init_LinkStack() {

LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));

stack->head.next = NULL;

stack->size = 0;

return stack;

}

//入栈

void Push_LinkStack(LinkStack* stack, LinkNode* data) {

if (stack == NULL) {

return;

}

if (data == NULL) {

return;

}

data->next = stack->head.next;

stack->head.next = data;

stack->size++;

}

//出栈

void Pop_LinkStack(LinkStack* stack) {

if (stack == NULL) {

return;

}

if (stack->size == 0) {

return;

}

//第一个有效结点

LinkNode* pNext = stack->head.next;

stack->head.next = pNext->next;

stack->size--;

}

//返回栈顶元素

LinkNode* Top_LinkStack(LinkStack* stack) {

if (stack == NULL) {

return NULL;

}

if (stack->size == 0) {

return NULL;

}

return stack->head.next;

}

//返回栈元素的个数

int Size_LinkStack(LinkStack* stack) {

if (stack == NULL) {

return -1;

}

return stack->size;

}

//清空栈

void Clear_LinkStack(LinkStack* stack) {

if (stack == NULL) {

return;

}

stack->head.next = NULL;

stack->size = 0;

}

//销毁栈

void FreeSpace_LinkStack(LinkStack* stack) {

if (stack == NULL) {

return;

}

free(stack);

}

栈的链式存储.c　　

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "LinkStack.h"

typedef struct PERSON {

LinkNode node;

char name[64];

int age;

}Person;

int main(void) {

//创建栈

LinkStack* stack = Init_LinkStack();

//创建数据

Person p1, p2, p3, p4, p5;

strcpy(p1.name, "aaa");

strcpy(p2.name, "bbb");

strcpy(p3.name, "ccc");

strcpy(p4.name, "ddd");

strcpy(p5.name, "eee");

p1.age = 10;

p2.age = 20;

p3.age = 30;

p4.age = 40;

p5.age = 50;

//入栈

Push_LinkStack(stack, (LinkNode*)& p1);

Push_LinkStack(stack, (LinkNode*)& p2);

Push_LinkStack(stack, (LinkNode*)& p3);

Push_LinkStack(stack, (LinkNode*)& p4);

Push_LinkStack(stack, (LinkNode*)& p5);

//输出

while (Size_LinkStack(stack) > 0) {

//取出栈顶元素

Person* p = (Person*)Top_LinkStack(stack);

printf("Name:%s Age:%d\n", p->name, p->age);

//弹出栈顶元素

Pop_LinkStack(stack);

}

//销毁栈

FreeSpace_LinkStack(stack);

system("pause");

return 0;

}

4.栈的应用(案例)

4.1案例1: 就近匹配

几乎所有的编译器都具有检测括号是否匹配的能力，那么如何实现编译器中的符号成对检测？如下字符串:

1	`#include <stdio.h> int main() { int a[4][4]; int (*p)[4]; p = a[0]; return 0;}`

算法思路
- 　从第一个字符开始扫描
- 　当遇见普通字符时忽略，
- 　当遇见左符号时压入栈中
- 　当遇见右符号时从栈中弹出栈顶符号，并进行匹配
- 　匹配成功：继续读入下一个字符
- 　匹配失败：立即停止，并报错
- 　结束：
- 　成功: 所有字符扫描完毕，且栈为空
- 　失败：匹配失败或所有字符扫描完毕但栈非空
总结
- 　当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性
- 　栈非常适合于需要“就近匹配”的场合

案例代码：

#include"LinkStack.h"

//案例一就近匹配

void test02(){

char* str = "#include <stdio.h> int main() { int a[4][4]; int (*p)[4]; p = a[0]; return 0;}";

//初始化栈

LinkStack* lstack = InitLinkStack();

//匹配括号

char* pCurrent = str;

while (*pCurrent != '\0'){

if (*pCurrent == '('){

PushLinkStack(lstack, pCurrent);

}

else if (*pCurrent == ')'){

char* p = (char*)TopLinkStack(lstack);

if (*p == '('){

PopLinkStack(lstack);

}

pCurrent++;

}

if (GetLengthLinkStack(lstack) > 0){

printf("匹配失败!\n");

}

//销毁栈

DestroyLinkStack(lstack);

}

int main(){

test02();

system("pause");

return EXIT_SUCCESS;

4.2案例2：中缀表达式和后缀表达式

l 后缀表达式（由波兰科学家在20世纪50年代提出）
- 　将运算符放在数字后面 ===》符合计算机运算
- 　我们习惯的数学表达式叫做中缀表达式===》符合人类思考习惯
l 实例
- 　5 + 4 => 5 4 +
- 　1 + 2 * 3 => 1 2 3 * +
- 　8 + ( 3 – 1 ) * 5 => 8 3 1 – 5 * +
l 中缀转后缀算法：

　　遍历中缀表达式中的数字和符号：

- 　对于数字：直接输出
- 　　对于符号：
  - 　　　左括号：进栈
  - 　　　运算符号：与栈顶符号进行优先级比较
- 　　若栈顶符号优先级低：此符号进栈（默认栈顶若是左括号，左括号优先级最低）

- 　　若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
l 右括号：将栈顶符号弹出并输出，直到匹配左括号

　　遍历结束：将栈中的所有符号弹出并输出

l 中缀转后缀伪代码 priority

transform(exp)

{

创建栈S；

i= 0；

while(exp[i] != ‘\0’)

{

if(exp[i] 为数字)

{

Output（exp[i]）;

}

else if(exp[i] 为符号)

{

while(exp[i]优先级 <= 栈顶符号优先级)

{

output（栈顶符号）；

Pop（S）;

}

Push(S, exp[i]);

}

else if(exp[i] 为左括号)

{

Push(S, exp[i]);

}

else if(exp[i] 为右括号)

{

while(栈顶符号不为左括号)

{

output（栈顶符号）；

Pop（S）;

}

从S中弹出左括号；

}

else

{

报错，停止循环；

}

i++;

}

while(size(S) > 0 && exp[i] == ‘\0’)

{

output(栈顶符号)；

Pop（S）;

}

l 动手练习

　　将我们喜欢的读的中缀表达式转换成计算机喜欢的后缀表达式

　　中缀表达式: 8 + ( 3 – 1 ) * 5

后缀表达式: 8 3 1 – 5 * +

4.3案例3：计算机如何基于后缀表达式计算

l 思考

　　　　计算机是如何基于后缀表达式计算的？

　　　　例如：8 3 1 – 5 * +

l 计算规则

　　　　遍历后缀表达式中的数字和符号

- 　　对于数字：进栈
- 　　对于符号：
  - 　　　从栈中弹出右操作数
  - 　　　从栈中弹出左操作数
  - 　　　根据符号进行运算
  - 　　　将运算结果压入栈中

　　　　遍历结束：栈中的唯一数字为计算结果

l 代码实现（伪代码） express

compute(exp)

{

创建栈；

int i = 0;

while( exp[i] != ‘\0’)

{

if（exp[i]为数字）

{

Push（S, exp[i]）;

}

else if(exp[i]为符号)

{

1. 从栈顶弹出右操作数；

2. 从栈中弹出左操作数；

3. 根据符号进行运算；

4. Push（stack，结果）；

}

else

{

报错，停止循环；

}

i++;

}

if( Size(s) == 1 && exp[i] == ‘\0’)

{

栈中唯一的数字为运算结果；

}

返回结果；

}

别去打扰一个不愿意理你的人，因为他心里那个最重要的人不是你，想陪你吃饭的人，酸甜苦辣都爱吃，想送你回家的人，东南西北都顺路，想和你聊天的人，永远不会嫌你话多，想回你信息的人，苦累忙烦都有空，努力过，付出活，就豪气的挥挥手大步走开，没必要非得等到伤痕累累才知道离开，所有人和事，自己问心无愧就好，不是你的也别强求，其实，对不理你的人来说，你的每一条信息每一个电话都是打扰，每一次关心，每一遍问候都是压力