Datawhale第九期组队学习--数据结构与算法(上)Task03:栈与递归(2天)
发布日期:2021-06-29 03:05:00
浏览次数:2
分类:技术文章
本文共 1756 字,大约阅读时间需要 5 分钟。
理论部分
- 用数组实现一个顺序栈。
- 用链表实现一个链栈。
- 理解递归的原理。
栈:
-
定义
栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。栈又称为后进先出(Last In First Out,LIFO)的线性表。 在栈中进行插入和删除操作的一端称为栈顶(Top),相应地,另一端称为栈底(Bottom)。不含数据元素的栈称为空栈。 -
存储结构
- 顺序结构。采用顺序存储结构的栈称为顺序栈。栈空间的容量是有限的,需要预先定义(或申请)栈的存储空间。因此,在顺序栈中,当一个元素入栈时,需要判断是否满栈(栈空间中有没有空闲单元),若栈满,则元素不能入栈。
- 应用 栈的典型应用包括表达式求值、括号匹配等,在计算机语言的实现以及将递归过程转变为非递归过程的处理中,栈又非常重要的作用。 怎么理解栈的应用?有哪些实例?
练习部分
- 根据要求完成车辆重排的程序代码
假设一列货运列车共有n节车厢,每节车厢将停放在不同的车站。假定n个车站的编号分别为1至n,货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢,必须重新排列车厢,使各车厢从前至后按编号1至n的次序排列。当所有的车厢都按照这种次序排列时,在每个车站只需卸掉最后一节车厢即可。
我们在一个转轨站里完成车厢的重排工作,在转轨站中有一个入轨、一个出轨和k个缓冲铁轨(位于入轨和出轨之间)。图(a)给出一个转轨站,其中有k个(k=3)缓冲铁轨H1,H2 和H3。开始时,n节车厢的货车从入轨处进入转轨站,转轨结束时各车厢从右到左按照编号1至n的次序离开转轨站(通过出轨处)。在图(a)中,n=9,车厢从后至前的初始次序为5,8,1,7,4,2,9,6,3。图(b)给出了按所要求的次序重新排列后的结果。
具有三个缓冲区铁轨的转轨站
编写算法实现火车车厢的重排,模拟具有n节车厢的火车“入轨”和“出轨”过程。
实思路过程如图: 代码问题: 1、如果缓冲铁轨不够的话,应该在哪提示? 2、结果打印最后多一个None,不知道哪里的?# cars: 等待排序的车厢 k: 缓冲轨数量,def railroad(cars, k): cacheLists = [] for i in range(k): cacheLists.append([]) init = 1 for i in cars: if i == init: print('{}号车厢入轨->出轨'.format(i)) init += 1 continue else: for list_item in cacheLists: if not list_item: list_item.append(i) break else: if min(list_item) > i: list_item.append(i) break for item in cacheLists: for i in range(len(item)): last = item.pop() if last == init: print('{}号车厢入轨->出轨'.format(last)) init += 1car = [5, 8, 1, 7, 4, 2, 9, 6, 3]n = 3print(railroad(car, n))
打印结果:
1号车厢入轨->出轨2号车厢入轨->出轨3号车厢入轨->出轨4号车厢入轨->出轨5号车厢入轨->出轨6号车厢入轨->出轨7号车厢入轨->出轨8号车厢入轨->出轨9号车厢入轨->出轨None
转载地址:https://blog.csdn.net/z583706/article/details/103916590 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月27日 23时57分47秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
springcloud 第一篇: 服务的注册与发现Eureka(Finchley版本)
2021-07-02
springcloud 第三篇: 服务消费者(Feign)(Finchley版本)
2021-07-02
Java关于JDBC的基本使用
2021-07-02
git配置与使用说明
2021-07-02
python
2021-07-02
网络协议
2021-07-02
进程和线程
2021-07-02
sql面试题
2021-07-02
linux基础与调优
2021-07-02
软件缺陷基础
2021-07-02
软件测试-面试13问
2021-07-02
记一次django项目的部署
2021-07-02
测试项目调研
2021-07-02
接手软件测试新项目的流程
2021-07-02
jmeter-性能测试2-脚本录制开发
2021-07-02
jmeter-性能测试3-参数化
2021-07-02
期货基础知识
2021-07-02
期权基础
2021-07-02
jmeter-性能测试6-性能基础扫盲
2021-07-02
pytest+allure生成测试报告
2021-07-02