20172326 《程序设计与数据结构》第十周学习总结

学号 20172326 《程序设计与数据结构》第十周学习总结

教材学习内容总结

数据结构有多种，通过不同的数据结构可以实现不同的结构。
集合是一种对象，可以是同构或者异构的。
数据结构分为逻辑结构和物理结构。
逻辑结构：
物理结构：

顺序存储结构和链式存储结构。

顺序存储结构：在内存中开辟若干的连续空间，将每个空间存入数据，数据关联与其地址一致。比如数组。

结论：

顺序存储结构：

优点：

无需为表示表中元素之间的逻辑关系而添加空间

　　　2. 可以快速地存取表中任意位置的元素

缺点：

插入和删除操作需要移动大量元素

　　 2. 需要考虑索引越界为题

　　 3. 扩容空间可能会造成空间浪费，缩小空间又可能会索引越界

　　 4. null值会造成空间“碎片”

链式存储结构：每个元素只记住它下一个元素是谁（地址）。

链式存储结构：

优点：插入和删除操作只需改变节点next和prev成员的指向即可，无需移位，无需扩容

缺点：失去了直接存取表中任意位置元素的能力

顺序存储结构和链式存储结构的对比：

存储分配方式：

顺序存储结构使用一段连续的存储单元依次存储线性表元素

链式存储结构使用任意存储单元存放线性表的元素

时间性能：

查找：

顺序存储结构O(1)

链式存储结构O(n)

插入和删除：

顺序存储结构O(n)

链式存储结构O(1)

空间性能：

顺序存储结构：空间分大了浪费，分小了上溢，还得扩容

链式存储结构：有空间就能分配，元素个数不受限制

ArrayList是顺序存储的线性表，LinkedList是链式存储的线性表,它们的特点都是有序，元素值可以重复。区别是底层算法不同。

教材学习中的问题和解决过程

问题1：书上说到，ArrayList不是高效的实现方案，也就不是动态的数据结构，但是明显，ArrayList是可以随用随加的，那么，二者区别到底在哪？
问题1理解：动态数据结构的大小规模是随需要而增长或收缩的。并不需要在声明中静态确定。换言之，arraylist是静态声明过的。但它是怎样实现的呢？这是我查到的array list的方法代码，

public void ensureCapacity(int minCapacity) {  
    modCount++;  
    int oldCapacity = elementData.length;  
    if (minCapacity > oldCapacity) {  
        Object oldData[] = elementData;  
        int newCapacity = (oldCapacity * 3)/2 + 1;  //增加50%+1
            if (newCapacity < minCapacity)  
                newCapacity = minCapacity;  
      // minCapacity is usually close to size, so this is a win:  
      elementData = Arrays.copyOf(elementData, newCapacity);  
    }  
 }

可以看到，当被判定空间不足时，每次都会将容量增加至原先容量的150%。所以，arraylist自然不是动态的。而例如链结，栈之类的动态数据结构是不需要事先定义其大小的。

问题2：集合（Collection）类的作用
问题2理解：JAVA集合主要分为三种类型：Set(集),List(列表),Map(映射)。集合的主要作用是相当于一个容器，你可以在里面装你希望装的对象，可以是Java内置的类，也可以是自定义的类。再者，这些集合支持一些方便的操作，比如Set可以排除重复，Map可以快速检索。所以说，集合可以存放任何类型的对象。

代码调试中的问题和解决过程

问题1：PP13.3编写的问题
问题1解决方案：
可以看到，是栈溢出地问题，回到相关代码

原来是方法问题。改正即可

代码托管

上周考试错题总结

错题1
理解：这是一个递归方法，从字符串a从第一个到最后一个逐个与‘b’比较，最后返回b出现的字数
错题2
理解：如果输入大于零的数，那么将不会进入else语句，也就说一直在大于零的情况下进行递归的循环
错题3
理解：汉诺塔问题的操作数为2^n-1，所以具有指数型
错题4
理解：E选项也可以计算出结果，但是使用的时循环而不是递归
错题5
理解：如果没有基本情况，递归方法会不停地调用而无法停止，从而导致无限递归，例如错题2
错题6与7一起吧
理解：1)递归就是在过程或函数里面调用自身;

2)在使用递归时,必须有一个明确的递归结束条件,称为递归出口.
3）由于递归自动执行回溯，任何需要回溯的问题使用递归更容易解决。

错题8
理解；两种产生地条件不同

结对及互评

结对博客
20172313
20172332
值得学习的地方：问题总结的很细致，感想很生动有趣。

其他

这本书的学习到了尾声，很开心

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）
目标	5000行	30篇	400小时
第一周	110/110	1/1	20/20
第二周	315/425	1/2	18/38
第三周	475/900	2/4	22/60
第四周	600/1500	1/5	30/90
第五周	1215/2715	1/6	20/110
第六周	382/3097	1/7	20/130
第七周	721/3818	1/8	15/145
第八周	771/4589	2/10	15/160
第九周	311/4900	1/11	15/175
第十周	282/5182	1/11	15/190