20172319 2018.09.29-10.08
《程序设计与数据结构》第4周学习总结
目录
教材学习内容总结
第六章 列表：
-
6.1 列表集合：
-
列表 是是使事物以线性列表的方式进行组织，列表集合 没有内在的容量大小，其可以随着需要而增大。
-
列表集合有三种类型：
-
有序列表（ordered list） ： 元素按其某种内在特性排序。
-
无序列表（unordered list） ：其元素间不具有内在顺序，元素按其在列表中的位置进行排序。
-
索引列表（indexed list） ： 其元素可以用数字索引来引用。
-
6.2 java集合API中的列表：
-
java集合API提供的列表类主要是支持索引列表，在一定程度上，这些类与无序列表是重叠的，在javaAPI中并没有任何类能直接实现有序列表。
-
java.util.List接口中的一些方法：
-
| 方法 | 描述 |
| -------- | :----------------: |
| add（E element） |向列表末端添加一个元素 |
| add（int index， E element） |在指定索引处插入一个元素 |
| get（int index） |返回指定索引处的元素 |
| remove（int index） |删除指定索引处的元素 |
| remove（E Object） |删除指定对象的第一个出现 |
| set（int index ， E element） |替代指定索引处的元素 |
| size（）| 返回列表中的元素数量| -
6.5 列表ADT：
-
列表的常见操作：：
-
| 操作 | 描述 |
| -------- | :----------------: |
| removeFirst |从列表中删除第一个元素 |
| removeLast |从列表中删除最后一个元素 |
| remove |从列表中删除某个元素 |
| first |查看位于列表前端的元素 |
| last |查看位于列表末端的元素 |
| contains |确定列表是否含有某一个元素 |
| size| 确定列表中的元素数量| -
特殊操作：
-
1.有序列表：
-
| 操作 | 描述 |
| -------- | :----------------: |
| add |往列表中添加一个元素 | -
2.无序列表：
-
| 操作 | 描述 |
| -------- | :----------------: |
| addToFront |把元素添加到列表的前端 |
| addToRear |把元素添加到列表的末端 |
| addToAfter |把元素添加到列表中某个已有元素的后面 |
实例：
-
6.6 用数组实现列表
-
将列表的某一端固定在数组的索引0处，按需平移元素。
-
remove操作的复杂度： O（n），查找元素并将其删除，若删除元素位于列表首位，则只需进行一次比较操作，若位于末尾，则需进行n次比较操作；而删除后，数组的高索引为会向下平移以填补空隙，而进行了n次比较和平移后恰能完美实现。
-
contains操作复杂度： O（n），查找目标元素并返回Boolean型值，该方法执行的是链表的线性查找，查不到的情况下至多需进行n个比较操作，因此该方法平均需要进行n/2次比较操作。
-
add操作（有序列表）复杂度： O（n），进行比较找到元素在列表中的正确位置，然后平移元素以便为新元素让位，若在前端，则进行一次比较，然后平移列表中的其他n-1个元素；若在末端，则需要进行n次比较。
-
addToFront操作复杂度 ： O（n），需平移n-1个元素。
-
addToRear操作复杂度： O（1）。
-
addToAfter操作复杂度： O（n），需进行n次比较和平移操作。
-
用固定数组实现栈的效率并不高；
-
环形数组（circular array），数组的最后一个索引后面跟的是第一个索引；可以去除在列表的数组实现中元素移位的需要
-
6.7 使用链表实现列表
-
remove操作的复杂度：O（n）；
教材学习中的问题和解决过程
- 问题1：链表编成栈，编成队列；数组编成栈，编成队列，你换来、我换去的有什么用？
- 解决：
- 数组、链表、栈和队列是最基本的数据结构，任何程序语言都会涉及到其中的一种或多种；
数组：
链表：
代码调试中的问题和解决过程
- 问题1：队列前端位置元素丢失。
- 20172301并不在队列里；
- 解决：
- 通过对代码顺序的更换，我们发现tostring和first两个方法的内容发生了冲突；
- 最后通过对方法的代码调试，发现在队头的元素已被修改，所以导致并非预期元素：
- 通过将其修改，最终实现了预想的效果：
代码托管
上周考试错题总结
-
错题1：
-
解决： 多态引用使用的是对象的类型来决定调用版本的方法。
-
错题2：
-
解决：top变量指的是数组中的下一个可用位置和数组中项目的数量。
-
错题3：
-
解决：pop操作是通过返回对当前存储在顶部的元素的引用来实现的。
结对及互评
点评过的同学博客和代码
- 本周结对学习情况：
- 20172316赵乾宸
- 博客中值得学习的或存在问题：
- 20172329王文彬
- **博客中值得学习的或存在问题： **
- 博客内容充实、排版整齐、对教材内容有经过一番认真思考、继续保持。
其他（感悟、思考等，可选)
学习进度条
| 代码行数（新增/累积） | 博客量（新增/累积） | 学习时间（新增/累积） | |
|---|---|---|---|
| 目标 | 3000行 | 15篇 | 300小时 |
| 第一周 | 0/0 | 1/1 | 12/12 |
| 第二周 | 935/935 | 1/2 | 24/36 |
| 第三周 | 849/1784 | 1/3 | 34/70 |
| 第三周 | 3600/5384 | 1/5 | 50/120 |
参考资料
数据结构（Java实现）之单向链表的节点表示、插入、删除、单向链表反转和串联
【数据结构】链表的原理及java实现
java集合包总结(添加、删除等操作实现原理)