Berkeley CS 61B Data Structures(in Java) Homework3 加分+讨论帖

Evi: JDK 9.0.l

这次作业比较简单
总结的重点应该在注释的important里~~

Let's smoosh arrays!

smooshing [  3  7  7  7  4  5  5  2  0  8  8  8  8  5  ]:

[  3  7  4  5  2  0  8  5  -1  -1  -1  -1  -1  -1  ]

smooshing [  6  6  6  6  6  3  6  3  6  3  3  3  3  3  3  ]:

[  6  3  6  3  6  3  -1  -1  -1  -1  -1  -1  -1  -1  -1  ]

smooshing [  4  4  4  4  4  ]:

[  4  -1  -1  -1  -1  ]

smooshing [  0  1  2  3  4  5  6  ]:

[  0  1  2  3  4  5  6  ]

Let's squish linked lists!

squishing [  3  7  7  7  4  5  5  2  0  8  8  8  8  5  ]:

[  3  7  4  5  2  0  8  5  ]

squishing [  6  6  6  6  6  3  6  3  6  3  3  3  3  3  3  ]:

[  6  3  6  3  6  3  ]

squishing [  4  4  4  4  4  ]:

[  4  ]

squishing [  0  1  2  3  4  5  6  ]:

[  0  1  2  3  4  5  6  ]

squishing [  ]:

[  ]

Let's twin linked lists!

twinning [  6  3  6  3  6  3  ]:

[  6  6  3  3  6  6  3  3  6  6  3  3  ]

twinning [  4  ]:

[  4  4  ]

twinning [  ]:

[  ]

上交作业

交作业～～

第三次作业。
在eclipse编写程序如果要到命令行来运行的话，一定要注意包名的问题。编译器和java运行环境会默认将文件路径识别为，package名.文件名。
所以如果编译要用的的.java文件都在一个包下的话，编译的时候要到包外的那一层路径 javac 包名\Homework3.java。
运行的时候也要到包外的那一层路径 java 包名.Homework
就这么点小问题搞了我1个多小时。头都快炸了。

另外求学分

提交第三次作业，求学分~

个人感觉第一个part比后两部分要难，数组的index如何逻辑没想清楚很容易出错，反倒是利用SList无需考虑index问题，因而一次性编译成功。
看来以后要多来点高级的数据结构了。

Homework3
1. part1解决问题还是不难的，难的在于怎么写才能简洁。
一开始自己的思路真的是繁琐：
首先给了两个变量first & sec，是array中进行比较的两个变量，sec通过for loop walk down the array，当碰到与first不同的值时，
将值覆盖原来的array；具体覆盖哪个位置呢？我又给了一个变量counter用来记录已经得到smooth的array中元素数目，一来知道了新比较得到的相异
值添加的位置，二来之后添加-1也知道从哪里添加起。覆盖后，我将sec值赋给了first，简单来说就是first跳到了sec的位置，然后
sec继续walk down进行比较。
看了大家的讨论发现自己的算法有不少地方可以变得更简洁：
其中最关键的是自己算法中first和counter的作用实际上是可以合并的，first完全没必要跳到相异的sec的位置，因为sec值已经通过counter记录在了array中。
直接用counter对应的值和sec进行比较即可。

主要是对自己前后思路的一个反思，写下来是对自己的一个总结，不算是一个讨论的发言，大家可能看不懂哈哈，对不住了。

2. part2 & part3
都不算难，对linked list的理解通过之前的lab训练得还算到位，主要理解了head的作用对linked list的操作就不难了（可以参考对之前lab的思考）。
要提到的一点是，part2中，一开始以为head是会变化的，将算法分成了确定head和之后的两部分，因为head如果不在对的位置的话，整个list打印出来
都会有问题，因为整个list是通过head进行access的。后来才发现head所指向的node肯定是不变的，是对后面node进行调整，写起来就比较简洁了。
part2判断了list为空的情况，否则循环条件while(node.next ! = null)当list为空时会报错，因为null不表示SListNode这一data structure，没有next这一变量。
part3不需要判断空的情况。

结果如下：

交作业！
Let's smoosh arrays!

smooshing [  3  7  7  7  4  5  5  2  0  8  8  8  8  5  ]:
[  3  7  4  5  2  0  8  5  -1  -1  -1  -1  -1  -1  ]
smooshing [  6  6  6  6  6  3  6  3  6  3  3  3  3  3  3  ]:
[  6  3  6  3  6  3  -1  -1  -1  -1  -1  -1  -1  -1  -1  ]
smooshing [  4  4  4  4  4  ]:
[  4  -1  -1  -1  -1  ]
smooshing [  0  1  2  3  4  5  6  ]:
[  0  1  2  3  4  5  6  ]

Let's squish linked lists!

squishing [  3  7  7  7  4  5  5  2  0  8  8  8  8  5  ]:
[  3  7  4  5  2  0  8  5  ]
squishing [  6  6  6  6  6  3  6  3  6  3  3  3  3  3  3  ]:
[  6  3  6  3  6  3  ]
squishing [  4  4  4  4  4  ]:
[  4  ]
squishing [  0  1  2  3  4  5  6  ]:
[  0  1  2  3  4  5  6  ]
squishing [  ]:
[  ]

Let's twin linked lists!

twinning [  6  3  6  3  6  3  ]:
[  6  6  3  3  6  6  3  3  6  6  3  3  ]
twinning [  4  ]:
[  4  4  ]
twinning [  ]:
[  ]

以上是运行结果，关于具体的实现，和大家差不多 都是对currennode进行判断 用currentnode=currentnode.next来进行循环；就是作业给了一些其他的方法...感觉老师的本意是让使用这些成员方法吧...写完part2才发现...squish还可以使用一下insert和构造函数；part3的twin用成员方法好像很复杂的样子...不知道大家有没有使用成员方法的精简代码～
总结：作业主要考察了 数组、链表的数据结构，要有效区分 复制引用和复制value，运算符==和equals()方法；
一个礼拜终于把前三次作业做完了...可以开心地看会儿video了...