《数据结构与算法》实验项目

注意： 请遵循"从编写到提交：使用Jupyter Notebook完成实验报告“中描述的实验报告格式要求

实验项目一：动态数组和链表比较

• 目标： 让学生实现动态数组和链表，并比较它们在不同操作上的性能。
• 任务：
  1. 实现一个动态数组，支持添加、删除和访问操作。
  2. 实现一个单向链表，同样支持添加、删除和访问操作。
  3. 设计实验来比较两种数据结构在插入、删除和随机访问操作上的时间复杂度。
  4. 要求学生撰写报告，分析实验结果，并讨论在何种场景下应该使用每种数据结构。
• 扩展： 添加实验部分，比较动态数组和链表在内存使用上的差异。

实验项目二：排序算法的实现与比较

• 目标： 学生将实现和比较几种不同的排序算法。
• 任务：
  1. 实现几种基本排序算法：冒泡排序、插入排序和选择排序。
  2. 实现一个更高级的排序算法，如快速排序或归并排序。
  3. 设计实验，比较各种排序算法在不同大小的输入数据集上的性能。
  4. 分析每种排序算法的时间复杂度，并在报告中讨论各种算法的优缺点及适用场景。
• 扩展： 评估排序算法在最好、平均和最坏情况下的性能。

实验项目三：探索和实现图算法

• 目标： 使学生了解和实践关键的图算法。
• 任务：
  1. 实现图的两种表示方法：邻接矩阵和邻接列表。
  2. 实现图的深度优先搜索（DFS）和广度优先搜索（BFS）算法。
  3. 实现 Dijkstra 的最短路径算法。
  4. 设计实验，使用不同规模和类型的图（如稀疏图和稠密图）来评估上述算法的性能。
  5. 要求学生撰写报告，解释算法的工作原理，分析实验结果，并讨论每种算法的应用场景。
• 扩展： 实现 A* 搜索算法，并比较其与 Dijkstra 算法在不同图中的性能。