网站建设的资金,计算机网站建设论文.,西安企业网站建设公司,合肥网站建设步骤文中代码源文件已上传#xff1a;数据结构源码 -上一篇 初级数据结构#xff08;二#xff09;——链表 | 初级数据结构#xff08;四#xff09;——队列 下一篇-
1、栈的特性
1.1、函数栈帧简述 即使是刚入门几天的小白#xff0c;对栈这个字… 文中代码源文件已上传数据结构源码 -上一篇 初级数据结构二——链表 | 初级数据结构四——队列 下一篇-
1、栈的特性
1.1、函数栈帧简述 即使是刚入门几天的小白对栈这个字也应该略有耳闻。在操作系统层面栈是系统在内存中划分的一整块连续的地址范围。并且系统对于单个程序在栈区的空间使用也是连续的。以一段代码举例
void FunctionInside()
{/* ... */
}void Function_1()
{/* ... */
}void Function_2()
{/* ... */FunctionInside();/* ... */
}int main()
{Function_1();Function_2();return 0;
} 在运行上述代码时首先调用 main 函数系统将为 main 函数在栈上单独开辟一块空间供 main 函数使用这块空间称作 main 函数的栈帧。而当在 main 中调用 Function_1 时系统又在 main 函数栈帧之上为 Function_1 开辟一块 Function_1 的栈帧。而随着 Function_1 函数调用结束 Function_1 的栈帧也被销毁该栈帧的空间归还给操作系统。 而进入 Function_2 函数时系统同样为 Function_2 开辟一块栈帧。如果如上述代码中的 Function_1 和 Function_2 是连续调用的话 Function_2 栈帧很可能覆盖之前 Function_1 被销毁的栈帧空间。此时进入 Function_2 函数内部又在内部调用 FunctionInside 函数。此时系统将在 Function_2 栈帧之上为 FunctionInside 创建栈帧。 随着 FunctionInside 调用结束 FunctionInside 栈帧也随之归还今儿回到 Function_2 的栈帧空间。当然 Function_2 调用结束后 Function_2 的栈帧也将归还并回到 main 函数的栈帧空间。最后随着程序结束main 函数的栈帧也随之销毁。 或许有点绕。但看上图也不难发现其规律这就是栈的特性后入先出、先入后出也称为 LIFO Last In First Out 。
1.2、栈结构 基于某些需求如通过程序判断记录数学公式字符串的大中小括号是否配对、计算字符串中的数学公式的值、甚至最基本的数组倒序等程序的数据处理需要用到后入先出的特性对这类数据进行操作的结构就称为栈结构。 栈结构的实现仍然是通过顺序表或者链表实现只是在存取数据时必须遵循 LIFO 的规则。并且栈结构不存在改和查的操作。如果要必须将尾部数据至需要修改的数据之间的元素依次弹出后重新依次写入新数据至于查只允许查看尾部元素一旦查看必须弹出。 通常栈结构都用顺序表创建较为方便因此以下便以顺序表的方式进行演示。同时最后附上链表实现栈结构的代码。
2、栈创建
2.1、文件结构 与之前章节相同依然创建三个文件文件名如下 stack.h 用于创建项目的结构体类型以及声明函数 stack.c 用于创建栈各种操作功能的函数 main.c 仅创建 main 函数用作测试。 2.2、前期工作 stack.h 中内容如下
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.h//存储数据类型的定义及打印占位符预定义
#define DATAPRT %d
typedef int DATATYPE;//栈主体
typedef struct Stack
{DATATYPE* data; //数据段size_t top; //栈顶位置下标size_t capacity; //开辟空间记录
}Stack;//函数声明---------------------------------//初始化
extern int StackInit(Stack*);
//销毁
extern void StackDestroy(Stack*);
//入栈
extern void StackPush(Stack*, DATATYPE);
//出栈
extern void StackPop(Stack*); 然后 stack.c 中先创建初始化及销毁的两个函数。这里需要注意的是对结构体中的 top 值的操作。虽然这个值等同于顺序表中的 size 但需要区分 top 是储存栈结构最后一个数据的下标。顺序表中的空表 size 则是等于 0 取顺序表的最后一个元素下标都是以 size - 1 进行操作而对于栈来说如果是空栈top 则置为 -1
#include stack.h//初始化
int StackInit(Stack* st)
{//参数判断if (!st){fprintf(stderr, Illegal Stack Address\n);return;}//初始开辟1个数据位st-data (DATATYPE*)malloc(sizeof(DATATYPE) * 1);if (!st-data){fprintf(stderr, Malloc Fail\n);return -2;}st-top -1;st-capacity 1;return 0;
}//销毁
void StackDestroy(Stack* st)
{//参数判断if (!st){fprintf(stderr, Illegal Stack Address\n);return;}//释放free(st-data);st-data NULL;st-top -1;st-capacity 0;
} 在 main.c 中则预先创建一个结构体变量无需进行其他操作。
#include stack.hint main()
{Stack st;return 0;
}
3、栈的数据操作
3.1、入栈 入栈实际上就是顺序表的尾插具体实现过程可以参考第一篇顺序表中的插入数据操作。这个功能实现起来并不复杂。此外跟顺序表一样如果已开辟的空间不足则需要进行扩容操作。这里可以将扩容封装为一个函数使代码看起来更简洁。此外由于扩容函数仅在该代码文件内调用可以加上 static 修饰。 在 static.c 中加入以下代码
//扩容
static void StackExpand(Stack* st)
{//参数判断if (!st){fprintf(stderr, Illegal Stack Address\n);return;}DATATYPE* temp (DATATYPE*)realloc(st-data, sizeof(DATATYPE) * st-capacity * 2);if (!temp){fprintf(stderr, Realloc Fail\n);return;}st-data temp;st-capacity * 2;
}//入栈
void StackPush(Stack* st, DATATYPE data)
{//参数判断if (!st){fprintf(stderr, Illegal Stack Address\n);return;}st-top;//空间不足则扩容if ((st-top) (st-capacity)){StackExpand(st);}//入栈st-data[st-top] data;
} 然后在 main.c 中输入以下并测试 StackInit(NULL);StackInit(st);StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPush(st, 4);StackPush(st, 5); 测试无误进行下一步。
3.2、出栈 入栈等于尾插那出栈自然就等同于尾删。对于出栈操作需要注意两点栈是否为空以及空间回收。是否空栈只需判别 top 是否等于 -1 。至于空间回收顺序表中也有提到操作逻辑完全一致。 这里为了代码可读性将空栈判断封装为函数将空间回收也一并封装为函数。 stack.c 中增加如下代码
//收缩空间
static void StackContract(Stack* st)
{//参数判断if (!st){fprintf(stderr, Illegal Stack Address\n);return;}DATATYPE* temp (DATATYPE*)realloc(st-data, sizeof(DATATYPE) * st-capacity / 2);if (!temp){fprintf(stderr, Realloc Fail\n);return;}st-data temp;st-capacity / 2;
}//空表判断 空表返回true
static bool StackIsEmpty(Stack* st)
{//参数判断if (!st){fprintf(stderr, Illegal Stack Address\n);return true;}return (st-top -1 ? true : false);
}//出栈
void StackPop(Stack* st)
{//参数判断if (!st){fprintf(stderr, Illegal Stack Address\n);return;}//数据为空直接返回if (StackIsEmpty(st)){fprintf(stderr, Stack Empty\n);return;}//出栈st-top--;//空间过剩则收缩空间if ((st-top) (st-capacity) / 2){StackContract(st);}
}
3.3、附加功能 出栈功能写完后获取栈顶数据及打印输出栈顶数据的功能也一并加上。首先在 stack.h 中进行声明
//打印
extern void StackPrint(Stack*);
//获取栈顶数据
extern DATATYPE StackGetTopData(Stack*); 然后继续在 static.c 中补充这两个功能。 这里需要注意因为获取栈顶数据是有返回值的因此如果空表或者传入空指针便不能简单地 return 容易对返回值的接收产生误解。而不论 return 任何值均有可能被误以为栈顶数据就是该值因此这里以 assert 判定最佳
//获取栈顶数据
DATATYPE StackGetTopData(Stack* st)
{//参数判断assert(st);//空表警告assert(!StackIsEmpty(st));//取数据并出栈DATATYPE data st-data[st-top];StackPop(st);return data;
}//打印
void StackPrint(Stack* st)
{//参数判断if (!st){fprintf(stderr, Illegal Stack Address\n);return;}//空表打印NULL后返回if (StackIsEmpty(st)){printf(NULL );return;}//打印栈顶并出栈printf(DATAPRT , StackGetTopData(st));
} 至此功能完毕。之后便是测试同时也顺带测试之前出栈的函数。完整的 main 函数代码
int main()
{Stack st;StackInit(NULL);StackInit(st);StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPush(st, 4);StackPush(st, 5);StackPrint(st); //5StackPrint(st); //4StackPrint(st); //3StackPrint(st); //2StackPrint(st); //1StackPrint(st); //NULLStackPrint(st); //NULLStackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPrint(st); //3StackDestroy(st);StackPrint(st); //NULLreturn 0;
} 测试结果如下 至此栈结构便完成了。
4、以链表实现栈 链表实现栈的文件结构与顺序表实现栈的结构一致根据以下代码自行测试研究。有链表的基础打底这里实现起来也将十分轻松 stack.h
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.h#define DATAPRT %dtypedef int DATATYPE;typedef struct StackNode
{DATATYPE data;struct StackNode* next;
}StackNode;typedef struct StackInfo
{StackNode* StackHead;size_t StackSize;
}StackInfo;//函数声明---------------------------------
//初始化
extern void StackInit(StackInfo*);
//销毁
extern void StackDestroy(StackInfo*);
//入栈
extern void StackPush(StackInfo*, DATATYPE);
//出栈
extern void StackPop(StackInfo*);
//获取栈顶数据
extern DATATYPE StackGetHead(StackInfo*);
//打印栈顶数据
extern void StackPrint(StackInfo*); stack.c
#include stack.h//初始化
void StackInit(StackInfo* info)
{//参数有效判断if (!info){fprintf(stderr, Illegal StackInformation Address\n);return;}//初始化info-StackHead NULL;info-StackSize 0;
}//销毁
void StackDestroy(StackInfo* info)
{//参数有效判断if (!info){fprintf(stderr, Illegal StackInformation Address\n);}//空链表直接返回if (!info-StackSize){return;}//逐节点释放空间StackNode* currentNode info-StackHead;while (currentNode){StackNode* destroyNode currentNode;currentNode currentNode-next;free(destroyNode);}info-StackHead NULL;info-StackSize 0;
}//判空
static bool StackIsEmpty(StackInfo* info)
{//参数有效判断if (!info){fprintf(stderr, Illegal StackInformation Address\n);return;}return (info-StackSize 0 ? true : false);
}//入栈
void StackPush(StackInfo* info, DATATYPE data)
{//参数有效判断if (!info){fprintf(stderr, Illegal StackInformation Address\n);return;}StackNode* newNode (StackNode*)malloc(sizeof(StackNode));if (!newNode){fprintf(stderr, Malloc Fail\n);return;}newNode-data data;newNode-next info-StackHead;info-StackHead newNode;info-StackSize;
}//出栈
void StackPop(StackInfo* info)
{//参数有效判断if (!info){fprintf(stderr, Illegal StackInformation Address\n);return;}if (StackIsEmpty(info)){fprintf(stderr, Stack Empty\n);return;}StackNode* destroyNode info-StackHead;info-StackHead info-StackHead-next;info-StackSize--;free(destroyNode);
}//获取栈顶数据
DATATYPE StackGetHead(StackInfo* info)
{//参数有效判断assert(info);//空表警告assert(!StackIsEmpty(info));DATATYPE data info-StackHead-data;StackPop(info);return data;
}//打印栈顶数据
void StackPrint(StackInfo* info)
{//参数有效判断if (!info){fprintf(stderr, Illegal StackInformation Address\n);return;}if (StackIsEmpty(info)){printf(NULL );return;}printf(DATAPRT , StackGetHead(info));
} main.c 的测试用例
#include stack.hint main()
{StackInfo info;StackInit(NULL);StackInit(info);StackPush(info, 1);StackPush(info, 2);StackPush(info, 3);StackPush(NULL, 20);StackPush(info, 4);StackPush(info, 5);StackPrint(info);StackPrint(info);StackPrint(info);StackPrint(info);StackPrint(info);StackPrint(info);StackPrint(info);StackPrint(info);StackPush(info, 1);StackPush(info, 2);StackPush(info, 3);StackPrint(info);StackDestroy(info);StackPrint(info);return 0;
}
