什么软件做网站,网站建设费如何入账,软件编程和网站开发差别,大气蓝色企业网站模板目录
一、栈的定义
二、栈的实现 2.1 栈的结构 2.2 栈的初始化 2.3 栈的销毁 2.3 栈元素的插入 2.4 栈元素的删除 2.5 栈顶元素获取 2.6 栈元素有效个数获取 2.7 栈是否为空判断
三、代码总览 Stack.h Stack.c 测试代码:test.c
四、例题 例一#xff1a; 例二#xff…目录
一、栈的定义
二、栈的实现 2.1 栈的结构 2.2 栈的初始化 2.3 栈的销毁 2.3 栈元素的插入 2.4 栈元素的删除 2.5 栈顶元素获取 2.6 栈元素有效个数获取 2.7 栈是否为空判断
三、代码总览 Stack.h Stack.c 测试代码:test.c
四、例题 例一 例二 例三 一、栈的定义 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除 操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out 的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 栈可以这样理解相信大家都对枪械有一定粗略的了解咱们就用压子弹来帮助大家进行理解。 压栈大家可以想象为压子弹子弹是一发一发往下压那压栈就是在容量之内一个数据一个数据往下压。 出栈大家可以理解为子弹射出的过程即最后压入的子弹先出。数据最后的先出。 这就是压栈与出栈的过程当然也可以压一个出一个压多个出一个都可以大家完全就可以把栈当作压子弹和子弹射出。 好了基础知识我们已经掌握那么我们该用什么结构来实现栈呢 通过单链表双链表还是什么大家可以在此处进行思考稍后公布答案。
二、栈的实现 上文说到我们要选择一个结构来实现栈。我们来一一分析一下 双链表全称为带头双向循环链表用它来实现可以吗还用说吗太过于完美当然可以但是要用两个指针同学们一个指针已经困扰大家已久那两个指针想必是大家不想经历的大恐怖。所以这个时候咱们把它先列为备胎实在没办法在想它在特殊情况下能渣则渣。 单链表全称为不带头单向不循环链表大家想单链表找到尾元素麻烦吗找一遍时间复杂度为ON。虽然我们可以反转一下但是你愿意用吗要是放两个指针还不如用双链表。 这个时候怎么办难道我们要使用双链表不绝对不行。这时数组意外路过对啊我们可以用数组。 数组每次使用前像顺序表一样判断是否开辟空间在用一个变量size来记录尾这样不就完美符合要求了。那说干就干吧。打开我们心爱的VS。 2.1 栈的结构 栈的结构可以借鉴一下顺序表要有数组、容量和栈定元素。结构如下
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack; 2.2 栈的初始化 要进行初始化大家想一想top赋值为多大合适如果为0那么0是不是为栈的第一个元素是不是答案是是的。那么有没有办法不叫top指向数组第一个元素有使top的值为-1即可。在后续代码中我会将top初始化为0别问问就是top此时可以当顺序表中的size使用。代码如下
// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-a NULL;ps-capacity ps-top 0;
} 2.3 栈的销毁 在我们今后写代码一定要记住只要你mallocrealloc一定要free你创建了就一定要销毁。 那我们创建了一个栈那么我们一定要销毁。代码如下
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);//此处记得释放ps指向的数组不要写成psps-a NULL;ps-capacity ps-top 0;
} 注意事项写在代码里了一定要记住 2.3 栈元素的插入
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps-capacity ps-top){int newcapacity ps-capacity 0 ? 4 : 2 * sizeof(ps-capacity);STDataType* newnode (STDataType*)realloc(ps-a,newcapacity*sizeof(STDataType));if (newnode NULL){perror(realloc fail);return;}ps-capacity newcapacity;ps-a newnode;}//这里之所以没有封装成一个接口是因为这里只用一次其余的都不使用ps-a[ps-top] data;ps-top;//这里也可以合二为一//ps-a[ps-top] data;
} 此处要点与顺序表类似就不过多强调。 2.4 栈元素的删除
// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps-top 0);ps-top--;
} 此处代码过于简单那么能不能不把这个封装了直接写。其实你要是想这么干你可以试一试不过提醒一下可能会出乱子。还是那句话专业的事专业的人做。 2.5 栈顶元素获取
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
} 对于此代码最后的返回值可能会有人有疑问我简单解释一下 2.6 栈元素有效个数获取
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;
} 上文说过top初始化为0时可当size来使用代码简单不过多解释。 2.7 栈是否为空判断
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
} 注意点必须包含头文件stdbool.h。
三、代码总览 Stack.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps); Stack.c
#includeStack.h// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-a NULL;ps-capacity ps-top 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps-capacity ps-top){int newcapacity ps-capacity 0 ? 4 : 2 * sizeof(ps-capacity);STDataType* newnode (STDataType*)realloc(ps-a,newcapacity*sizeof(STDataType));if (newnode NULL){perror(realloc fail);return;}ps-capacity newcapacity;ps-a newnode;}//这里之所以没有封装成一个接口是因为这里只用一次其余的都不使用ps-a[ps-top] data;ps-top;//这里也可以合二为一//ps-a[ps-top] data;
}
// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;
}
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);//此处记得释放ps指向的数组不要写成psps-a NULL;ps-capacity ps-top 0;
} 测试代码:test.c
#includeStack.hint main()
{Stack p;StackInit(p);StackPush(p, 1);StackPush(p, 2);StackPush(p, 3);StackPush(p, 4);while (!StackEmpty(p)){printf(%d , StackTop(p));StackPop(p);}StackDestroy(p);return 0;
}
四、例题 既然明白了那么来几道题巩固一下吧 例一 设栈S和队列 Q的初始状态均为空元素 abcdepg 依次进入栈S。若每个元素出栈后立即进入队列 Q且7个元素出队的顺序是 bdcfeag则栈S的容量至少是 例二 若元素a,b,c,d,e,f依次进栈允许进栈、退栈操作交替进行但不允许连续3次进行退栈操作不可能得到的出栈序列是。 A. dcebfa B. cbdaef C.bcaefd D.afedcb 例三 元素 a,b,c,d,e依次进入初始为空的栈中若元素进栈后可停留、可出栈直到所有元素都出栈则在所有可能的出栈序列中以元素d开头的序列个数是 好了我们的学习到现在就结束了如有疑惑可私信也可在评论区留言。
完
