2024-2025-1 20241316《计算机基础与程序设计》第七周学习总结

作业信息

教材学习内容总结

• 《计算机科学概论（第七版）》第 8 章
  抽象数据类型：从三层观察数据，将数据与操作封装，用户无需了解实现细节。
  数据结构
  栈：后进先出，用于函数调用等。
  队列：先进先出，用于任务调度等。
  列表：线性结构，有多种形式。
  树：非线性，二叉检索树方便数据操作。
  图：由节点和边构成，用于网络分析等。
  子程序：可多次调用的代码模块，有参数列表，能提高代码复用和维护性。
• 《C 语言程序设计》第 6 章
  循环控制结构
  for 语句：先判断条件，适用于已知循环次数。
  while 语句：当型循环，条件满足执行循环体。
  do - while 语句：直到型循环，先执行一次再判断。
  continue 语句：结束本次循环。
  break 语句：跳出当前循环。
  数组相关操作：包括一维数组定义和引用。

教材学习中的问题和解决过程（先问 AI）

• 问题1：广度优先搜索、深度优先搜索不是很理解
• 问题1解决方案：广度优先搜索（BFS）
  概念：图遍历算法，从起始顶点开始，先访问其邻接顶点，再依次访问邻接顶点的邻接顶点，用队列实现，像水波扩散。
  示例：如迷宫、二叉树遍历，可找边权相同的最短路径。
  应用：社交网络、游戏地图找最短路径。
  深度优先搜索（DFS）
  概念：图遍历算法，从起始顶点沿一条路径尽量深地访问，到尽头回溯，可通过栈或递归实现。
  示例：迷宫中走到死胡同返回，树结构沿分支到叶节点再回溯。
  应用：拓扑排序、找图的连通分量。
  单源最短路搜索（以 Dijkstra 算法为例）
  概念：在带权图中从给定源点找至其他顶点最短路径，维护已确定最短路径顶点集合，每次选距离源点最近顶点加入并更新相邻顶点距离估计。
  示例：城市交通网络中计算从一个城市到其他城市最短距离。
  应用：网络路由、物流配送路径规划。