目录

[toc]

学号20182323 2019-2020-1 《数据结构与面向对象程序设计》第7周学习总结

教材学习内容总结

第12章

• 算法分析

1. 什么叫做算法：是对特定问题求解方法，或者说是步骤的一种描述。

   
   



2. 什么叫做好算法（具有以下标准）：

   
   
   
   
   1. 正确性
   
   
   2. 可读性
   
   
   3. 健壮性
   
   
   4. 通用性
   
   
   5. 效率与储存空间需求
   
   
   
   



3. 冰与火之歌：【时间】与【空间】复杂度

   
   

• 时间复杂度：在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。

  
  



• 算法的时间复杂度，也就是算法的时间量度，记作：T（n）= O（f（n））。它表示随问题规模的增大，算法执行时间的增长率和f（n）的增长率相同，称为算法的渐进复杂度，简称为时间复杂度。

  
  



• 其中f（n）是问题规模n的某个函数。这样用大写 O（） 来体现算法时间复杂度的记法，我们称为大O记法

  
  

4. 常见的时间复杂度如下图所示：
   

   
   



5. 每个复杂度的时间比如下图所示：
   

   
   

第14章

• 栈

1. 什么是栈：栈是一个有序集合，其中添加和删除元素都是发生在同一端，通常称作发生操作的这一端为顶部，对应的端为底部。（先进后出）

   
   



2. 栈的操作：
   
   

   
   



3. 利用栈完成后缀表达式的计算：后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) * 3 ， 即2 1 + 3 *。利用栈结构，将后缀表达式的结果计算出来。

   
   



4. 实现队列的两种编程方法：

   
   
   
   
   1. 链表实现
   
   
   2. 数组实现
   
   
   
   

第15章

• 队列

1. 什么是队列：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。（先进先出）


2. 实现队列
   
   
   
   1. 与栈类似：
      
      
      
      1. 数组每次被填满后，加入下一个元素时，把数组拓展成现有数组的两倍大小。
      
      
      2. 每次移除元素时，检测数组空余空间有多少。当数组里的元素个数只有整个数组大小的四分之一时，数组减半。
      
      
      
      
   
   
   2. 不同之处在于：
      
      
      
      1. 由于是先进先出，移除是从队列的最前端开始的。所以当我们移除数个数据后，队列数据是存储在数组的中间部分的。令队列数据的尾端数据ID为Num,首端数据ID为HeadIndex，则Num - HeadIndex为队列数据元素个数。
      
      
      2. 当队列数据元素个数为整个数组空间的四分之一时，数组减半，且队列数据左移至数组最左端。即Num-=HeadIndex；HeadIndex=0；
      
      
      
      
   
   
   
   

图中，HeadIndex=2；Num=5；


3. 实现队列的两种编程方法：
   
   
   
   1. 链表实现
   
   
   2. 数组实现
   
   
   
   

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

• 问题1：在用数组实现队列时，为什么环形数组较其他数组较好？

  
  



• 问题1解决方案：

  
  
  
  

  1. 环形数组的优点：

     可以有效的利用资源。用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的；循环队列也是一种数组，只是它在逻辑上把数组的头和尾相连，形成循环队列，当数组尾满的时候，要判断数组头是否为空，不为空继续存放数据。

     
     
  
  

  2. 但是呢，环形数组还是有缺点的：

     循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件frOnt==rear来判别队列是"空"是"满"。

     
     
  
  

  3. 拓展知识：

     为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环（环形）队列。

     
     
  
  
  
  



• 问题2：链表和数组的优缺点

  
  



• 问题2解决方案：

  
  

1. 不同点：

   
   
   
   
   1. 链表是链式的存储结构；数组是顺序的存储结构。
   
   
   2. 链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。
   
   
   3. 链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难；数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。
   
   
   
   



2. 相同点：

   两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构。

   
   

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

• 问题1：编程练习的时候，排序时第一个位置并不参与

• 解决过程：

  关键代码

  
  

public void SelectionSortList(){
int min;
SelectionSortNode a = null;
SelectionSortNode b = null;
for (a=list.next;a!=null;a=a.next){
for (b=a.next;b!=null;b=b.next){
if (a.num>b.num){
min = b.num;
b.num = a.num;
a.num = min;
}
}
}
}


经检查后发现，a=list.next导致跳过了节点的头，所以第一个节点被跳过了，因此它并没有参与排序；

修改后的代码：

public void SelectionSortList(){
int min;
SelectionSortNode a = null;
SelectionSortNode b = null;
for (a=list;a!=null;a=a.next){
for (b=a.next;b!=null;b=b.next){
if (a.num>b.num){
min = b.num;
b.num = a.num;
a.num = min;
}
}
}
}


输入a=list，重新运行。

代码托管

结对及互评

点评模板：

• 博客中值得学习的或问题：

  
  
  
  
  • 随着学习内容难度增加，问题分析更加深刻
  
  
  • 不断查阅资料，努力解决出现的问题
  
  
  
  



• 代码中值得学习的或问题：

  
  
  
  
  • 代码的逻辑性有待提高
  
  
  • 代码中适当加入注释会更好
  
  
  
  



• 基于评分标准，我给本博客打分：12分。得分情况如下：

  
  

1. 正确使用Markdown语法（加1分）：

   
   
   
   
   • 不使用Markdown不加分
   
   
   • 有语法错误的不加分（链接打不开，表格不对，列表不正确...）
   
   
   • 排版混乱的不加分
   
   
   
   



2. 模板中的要素齐全（加1分）

   
   
   
   
   • 缺少“教材学习中的问题和解决过程”的不加分
   
   
   • 缺少“代码调试中的问题和解决过程”的不加分
   
   
   • 代码托管不能打开的不加分
   
   
   • 缺少“结对及互评”的不能打开的不加分
   
   
   • 缺少“上周考试错题总结”的不能加分
   
   
   • 缺少“进度条”的不能加分
   
   
   • 缺少“参考资料”的不能加分
   
   
   
   



3. 教材学习中的问题和解决过程（2分）

   
   



4. 代码调试中的问题和解决过程（2分）

   
   



5. 本周有效代码超过300分行的（加0分）

   
   



6. 其他加分：

   
   
   
   
   • 周五前发博客的加1分
   
   
   • 感想，体会不假大空的加1分
   
   
   • 进度条中记录学习时间与改进情况的加1分
   
   
   • 有动手写新代码的加1分
   
   
   • 错题学习深入的加1分
   
   
   • 点评认真，能指出博客和代码中的问题的加1分
   
   
   • 结对学习情况真实可信的加1分
   
   
   
   

• 参考示例

点评过的同学博客和代码

• 本周结对学习情况
  
  
  
  • 结对同学学号20182315
  
  
  • 结对照片
  
  
  • 结对学习内容
    
    
    
    • 算法分析，栈，队列
    
    
    
    
  
  
  
  

其他（感悟、思考等，可选）

• 这两周学习任务有点重，学习的东西更加难了，加油加油。


• 课外的知识汲取很有必要，没事可以多看看别人的博客，交流经验

学习进度条

• 计划学习时间:25小时

  
  



• 实际学习时间:20小时

  
  



• 改进情况：

  
  

参考资料