20172319 2018.09.29-10.08
《程序设计与数据结构》第4周学习总结
目录
教材学习内容总结
第六章 列表:
- 6.1?列表集合:
- 6.2?java集合API中的列表:
- 队列(queue): 一种线性集合,其元素从一端加入,从另一端删除。处理方式: 先进先出(First In First Out, FIFO)。
- 比较FIFO与LIFO两种处理方式:
- 队列中:处理过程可在两端进行。

队列的操作:
enqueue |
向队列末端添加一个元素 |
dequeue |
从队列前端删除一个元素 |
first |
考察队列前端的那个元素 |
isEmpty |
判定队列是否为空 |
size |
判定队列中的元素数目 |
toString |
返回队列中的字符串表示 |
- 6.5?列表ADT:
- 队列与栈的主要差别: 要操作链表的两端。
- 1.需创建两个引用:一个指向链表首元素(head),一个指向链表末元素(tail);
- 2.另需一个整型变量count来跟踪队列中的元素数目;
- 3.若链表是单向链接,则应区分往链表的哪端添加或入列元素与从哪端删除或出列元素;
- 4.enqueue操作中,往前端和末端的添加新元素对应的处理步骤相似:新节点的next指向head,然后head指向新节点;
- 5.dequeue操作则有所区别:
- 1.表末端enqueue,表前端dequeue,在进行dequeue时,只需设置一个临时变量指向链表前端的元素,然后把front变量设置为第一个结点的next指针的值;
- 2.表前端enqueue,表末端dequeue,需把一个临时变量设置为指向链表末端的元素,然后将tail指针设置为指向当前末端之前的结点。
双向链表可以解决遍历链表的问题,因此无所谓从哪端出入列。

- 6.6?用数组实现列表:
- 将队列的某一端固定在数组的索引0处,所有元素不间断地存放在数组中。
- 元素移位,dequeue的复杂度为O(n);
- 用固定数组实现栈的效率并不高;
环形数组(circular array),数组的最后一个索引后面跟的是第一个索引;可以去除在队列的数组实现中元素移位的需要
- 6.7?使用链表实现列表:
队列的扩展,允许从队列的两端添加、删除和查看元素。
返回目录
教材学习中的问题和解决过程
返回目录
代码调试中的问题和解决过程
- 问题1:队列前端位置元素丢失。

- 20172301并不在队列里;
- 解决:
- 通过对代码顺序的更换,我们发现tostring和first两个方法的内容发生了冲突;


- 最后通过对方法的代码调试,发现在队头的元素已被修改,所以导致并非预期元素:

- 通过将其修改,最终实现了预想的效果:

返回目录

返回目录
上周考试错题总结
返回目录
结对及互评
点评过的同学博客和代码
返回目录
其他(感悟、思考等,可选)
返回目录
学习进度条
目标 |
3000行 |
15篇 |
300小时 |
第一周 |
0/0 |
1/1 |
12/12 |
第二周 |
935/935 |
1/2 |
24/36 |
第三周 |
849/1784 |
1/3 |
34/70 |
返回目录
补充作业
对编程整体的理解 |
3 |
8 |
程序理解 |
5.5 |
8 |
代码质量 |
4 |
7 |
架构设计、模块化设计、接口设计 |
3 |
7 |
效能分析和改进 |
2.5 |
6 |
处理大数据 |
2.5 |
7 |
返回目录
参考资料
数据结构(Java实现)之单向链表的节点表示、插入、删除、单向链表反转和串联
【数据结构】链表的原理及java实现
java集合包总结(添加、删除等操作实现原理)
返回目录
20172319 《程序设计与数据结构》 第四周学习总结
原文:https://www.cnblogs.com/Tangcaiming/p/9751435.html