【数据结构课程设计实验报告（完整版）】一、实验目的
本实验旨在通过实际编程实践，加深对数据结构基本概念和算法的理解，掌握线性表、树、图等常见数据结构的实现方法及其在实际问题中的应用。同时，培养学生的逻辑思维能力、程序设计能力和调试能力，为后续学习更复杂的数据结构与算法打下坚实基础。
二、实验内容
本次课程设计实验主要围绕以下内容展开：
1. 线性表的应用：使用顺序表或链表实现一个简单的通讯录管理系统，支持添加、删除、查找、修改联系人信息等功能。
2. 树结构的应用：构建二叉搜索树，并实现插入、查找、遍历等操作，用于存储和管理学生信息。
3. 图结构的应用：采用邻接矩阵或邻接表的方式表示图，实现最短路径算法（如Dijkstra算法）和最小生成树算法（如Prim算法），应用于模拟城市交通网络。
三、实验环境
- 操作系统：Windows 10
- 编程语言：C/C++
- 开发工具：Visual Studio 2019 或 Code::Blocks
- 数据结构库：标准模板库（STL）可选使用
四、实验步骤
1. 线性表应用——通讯录管理系统
功能模块设计：
- 添加联系人信息（姓名、电话、地址）
- 删除指定姓名的联系人
- 查找某位联系人的信息
- 修改已有联系人的信息
- 显示所有联系人信息
实现方式：
使用顺序表结构存储联系人信息，每个联系人作为一个结构体对象，包含姓名、电话、地址等字段。通过数组实现基本操作。
代码片段示例：
```c
typedef struct {
char name[50];
char phone[20];
char address[100];
} Contact;
Contact contacts[100];
int count = 0;
void addContact(Contact c) {
if (count < 100) {
contacts[count++] = c;
} else {
printf("通讯录已满，无法添加新联系人。\n");
}
}
```
2. 树结构应用——二叉搜索树
功能模块设计：
- 插入节点
- 查找特定值的节点
- 遍历树（前序、中序、后序）
- 删除节点
实现方式：
采用二叉搜索树结构，每个节点包含一个键值、左子节点指针和右子节点指针。根据键值大小进行插入和查找操作。
代码片段示例：
```c
typedef struct Node {
int key;
struct Node left;
struct Node right;
} Node;
Node insert(Node root, int key) {
if (root == NULL) {
Node node = (Node)malloc(sizeof(Node));
node->key = key;
node->left = node->right = NULL;
return node;
}
if (key < root->key)
root->left = insert(root->left, key);
else if (key > root->key)
root->right = insert(root->right, key);
return root;
}
```
3. 图结构应用——最短路径与最小生成树
功能模块设计：
- 构建图结构（邻接矩阵或邻接表）
- 实现Dijkstra算法计算单源最短路径
- 实现Prim算法构造最小生成树
实现方式：
采用邻接矩阵存储图的边权值，利用优先队列优化Dijkstra算法，使用集合维护已加入最小生成树的节点。
代码片段示例（Dijkstra算法）：
```c
void dijkstra(int graph[V][V], int start) {
int dist[V];
bool visited[V];
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
visited[i] = false;
}
dist[start] = 0;
for (int count = 0; count < V; count++) {
int u = minDistance(dist, visited);
visited[u] = true;
for (int v = 0; v < V; v++)
if (!visited[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, V);
}
```
五、实验结果与分析
通过本次实验，成功实现了线性表、树和图三种典型数据结构的应用，完成了相应的功能模块开发，并进行了测试验证。
- 通讯录管理系统能够正确实现增删改查操作，界面友好，运行稳定。
- 二叉搜索树具备良好的插入和查找效率，适合处理动态数据。
- 最短路径和最小生成树算法在不同规模的图上均能正常运行，时间复杂度符合预期。
实验过程中遇到的主要问题包括内存管理不当、指针操作错误以及算法逻辑不清晰，经过调试和查阅资料后均已解决。
六、实验总结
本次数据结构课程设计实验不仅巩固了课堂所学知识，还提升了动手能力和独立解决问题的能力。通过对多种数据结构的实现与应用，更加深入地理解了其在实际问题中的作用和意义。未来将继续加强对高级数据结构的学习，提升算法设计与实现能力。
附录：参考文献
1. 严蔚敏, 吴伟民. 《数据结构（C语言版）》. 清华大学出版社.
2. 王道论坛. 《数据结构考研辅导讲义》.
3. 《算法导论》. Thomas H. Cormen 等著.
---
