哪些网站可以做画赚钱,作品集制作网站,深圳网站建设主页,网站建设实训周记引言#xff1a;在本篇博客中#xff0c;我们将学到数据结构——栈#xff0c;讲到栈的含义与关于栈的数据操作代码。栈可以在顺序表、双向链表以及单链表的基础上实现#xff0c;而于本篇博客中#xff0c;我们选择在顺序表的基础上实现栈。 更多有关C语言和数据结构知识… 引言在本篇博客中我们将学到数据结构——栈讲到栈的含义与关于栈的数据操作代码。栈可以在顺序表、双向链表以及单链表的基础上实现而于本篇博客中我们选择在顺序表的基础上实现栈。 更多有关C语言和数据结构知识详解可前往个人主页计信猫 目录 一栈的含义
二栈的结构体的定义
三栈数据操作函数
1栈的初始化
2栈的销毁
3入栈 4出栈
5取栈顶的数据
6获取栈中数据的个数
7判断栈是否为空
四结语 一栈的含义 栈是一种特殊的线性表只允许在表中固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端成为栈顶另一端成栈底。 压栈栈的数据插入操作。 出栈栈的数据删除操作。 而因为栈特殊的数据插入和删除遵循LIFO后进先出的原则使得栈可以被比作一个羽毛筒。因为羽毛球里边的球都是从最上边开始使用的类比于栈顶 二栈的结构体的定义 这次我们仍然使用三文件操作法分别创建stack.h、stack.c、test.c三个文件。 因为前文提到栈是一种特殊的顺序表那么栈的定义应该和顺序表的定义方式极其相似所以在stack.h中我们如下定义栈
//包含实现栈的操作函数所要用到的头文件
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h
typedef int STDataType;
//创建栈结构体
typedef struct Stack
{STDataType* a;//动态数组int top;//栈顶的下一位int capacity;//数组总空间大小
}ST; 可能大家会不理解栈中top的含义那么请看如下的图片讲解吧。 如果栈里边没有元素的时候那么此时top便指向数组中下标为零的地方。
三栈数据操作函数 因为栈是在顺序表的基础上实现的所以栈的数据操作函数与顺序表及其类似甚至更简单好好听吧一定可以听懂
1栈的初始化 对于栈的初始化其实就是将栈结构体中的指针类型赋值为NULL整型类型赋值为0就可以了我们直接上代码
// 初始化栈
void StackInit(ST* ps)
{//断言判断栈不为NULLassert(ps);ps-a NULL;ps-capacity ps-top 0;//top指向栈顶数据的下一位
}
2栈的销毁 在该函数中我们所需要做的就是释放掉动态数组所开辟的空间再将指针置空防止野指针的出现最后将整型类型改为0就可以了。代码如下
// 销毁栈
void StackDestroy(ST* ps)
{free(ps-a);//释放动态数组空间ps-a NULL;//防止野指针的出现ps-capacity ps-top 0;
}
3入栈 入栈顾名思义就是在栈顶插入数据。 而在插入数据之前我们就需要先判断动态数组的空间是否足够不够我们就使用realloc函数进行空间大小的修改。判断空间代码如下
//判断空间是否足够if (ps-top ps-capacity)//topcapacity说明空间不够{int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;//三目操作符STDataType* tmp (STDataType*)realloc(ps-a,sizeof(STDataType) * newcapacity);if (tmpNULL)//防止空间申请失败{perror(realloc fail!);return;}ps-a tmp;ps-capacity newcapacity;} 于此段代码之中有两个非常巧妙之处1空间是否足够的判断让我们仔细想想当top变量等于capacity变量时是什么情况 对就是如上图所示当两者相等的时候也就意味着整个动态数就只有一个空间以供使用了而这时我们就需要进行空间的动态开辟了。 2三目操作符的使用仔细想想以下两种代码有什么不一样的呢
代码一
int newcapacity ps-capacity * 2
代码二
int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2; 其实答案十分简单在我们对栈进行初始化的时候我们将top和capacity变量都初始化为了0那如果是代码一0*2就为0则不就乱套了吗所以我们便使用代码二用到了三目操作符来避免0*2为0的尴尬情况。 而之后的入栈函数就十分简单了但千万别忘了要对top进行处理 // 入栈
void StackPush(ST* ps, STDataType data)
{assert(ps);//判断空间是否足够if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a,sizeof(STDataType) * newcapacity);if (tmpNULL){perror(realloc fail!);return;}ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] data;//top处加入新的元素ps-top;//栈顶的移动
}
4出栈 对于出栈函数其实我们所需要做的就是删除掉栈顶的元素并且将栈顶向后移动一位。而对于栈顶元素的删除我们也无需像链表一样使用free函数我们只需要将top减1即可十分的简单。直接上代码
// 出栈
void StackPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}
5取栈顶的数据 因为栈顶是一个栈中及其特殊的位置所以我们也就时不时会用到栈顶的数据而这个函数就很好的帮我们解决了这个问题。 在这个函数中我们唯二需要注意的就是栈不可以为空指针栈的数据个数不可以为零。代码走起
// 获取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);//栈不为空指针assert(ps-top 0);//栈的数据个数不能为零STDataType tmp ps-a[ps-top - 1];//top-1才为栈顶元素的下标return tmp;
}
6获取栈中数据的个数 这个函数是关于栈的数据操作函数中最简单的一个函数。栈中的数据个数不就是top的值吗所以我们直接返回top就可以了。代码如下
// 获取栈中有效元素个数
int StackSize(ST* ps)
{assert(ps);return ps-top;
}
7判断栈是否为空 该函数比较特殊它使用到的是布尔类型。如果栈为空就返回true反之则返回false。而对于是否为空的判断我们只需要观察top是否为零就可以了。所以代码如下
// 检测栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps-top 0;//若top为零则为true;反之则为false
}
四结语 这是有关数据结构中栈的讲解是不是易如反掌呢之后我也会接着更新数据结构中另一个知识点——队列的讲解。 博客不仅是我记录所学习到的知识点的工具也是我找到同样有学习编程爱好的人的朋友圈希望我的博客可以对你有所帮助也希望你可以留下你的鼓励你的鼓励就是我最大的动力加油
