数据结构课程设计

项目名称：

图的遍历

课程设计主要目的：

1.了解并掌握数据结构与算法的设计方法。 2.通过应用数据结构的基本理论和方法来解决实际问题。 3.初步掌握软件开发过程中的问题分析、系统设计、程序编码、调试、数据测试等基本方法和技能。 4.学习编写课程设计报告，软件开发文档。

课程设计任务要求：

任务：实现图的深度遍历（递归和非递归两种方法）以及实现图的广度遍历（队列） 要求： 1.程序能够正确运行，实现图的深度遍历和广度便利的基本功能。 2.用户操作界面大方、简洁。 3.程序的可读性要好，源程序采用锯齿型书写格式，关键代码要有注释。 4.写明所用存储结构，对关键功能画出程序流程图。 5.要有测试数据和结果、调试程序，对调试程序时出现的错误进行分析，思考导致错误的原因。

一、设计任务说明

实现图的深度遍历（递归和非递归两种算法）以及实现图的广度遍历（队列）。

1. 题目分析

用C语言编写代码用递归和非递归两种方法分别实现图的深度遍历，然后再用队列的方法实现图的广度优先遍历。       2.任务具体要求 本次课程设计题目是设计一个图的遍历，其要求为要实现图的深度优先遍历（用递归、非递归两种方法）和图的广度遍历（用队列实现）。要求能够只能够 正确的运行，用户操作界面简洁大方，代码可读性较好。     此次课题的限制条件为：实现深度优先遍历时要有两种方法来实现，实现图的遍历时要用到队列的方法。

二、设计方案 

2.1总体设计

     1. 存储结构       在这个程序中，首先定义了一个邻接矩阵graph和一个变量numVertices来存储图的顶点数量。我们还声明了一个布尔数组visited来跟踪访问过的顶点。然后，定义了栈和队列的基本操作。 // 图的邻接矩阵 int graph[MAX_SIZE][MAX_SIZE]; int numVertices;  // 辅助数组用于DFS bool visited[MAX_SIZE];     // 栈和队列的声明 int stack[MAX_SIZE]; int top = -1; int queue[MAX_SIZE]; int front = 0, rear = -1;        2.系统功能介绍       系统通过数据的输入、DFS递归实现、DFS非递归实现（使用栈）、BFS实现、打印菜单等结构模块来实现图的遍历功能。各个功能模块的实现依靠主函数的void executeChoice(int choice)函数中的switch语句实现。具体如下：

系统流程图：

图1系统流程图

系统功能结构图：

图2系统功能结构图

2.2详细设计    

        1.设计中使用的函数 void createGraph(); void DFS_recursive(int vertex); void push(int item); int pop(); void DFS_stack(int startVertex); void BFS(int startVertex); void enqueue(int item); int dequeue(); void printMenu(); void executeChoice(int choice);  2.主函数 //打印菜单，用户可以输入想要打开的系统功能选择并调用executeChoice(choice)函数 int main() {     int choice;     do {         printMenu();         scanf("%d", &choice);         executeChoice(choice);     } while (choice != 0);     return 0; }   3.子函数         （1）创建图的邻接矩阵 创建一个新的邻接矩阵，并保存到“creatGraph()”中，该功能通过定义的void creatGraph()函数来实现。 // 创建图的邻接矩阵 void createGraph() {     printf("输入顶点数: ");     scanf("%d", &numVertices);     printf("输入邻接矩阵:\n");     for (int i = 0; i < numVertices; ++i) {         for (int j = 0; j < numVertices; ++j) {             scanf("%d", &graph[i][j]);         }         （2）DFS递归实现 图的深度优先遍历通过递归调用的方式来实现，对每个访问到的节点进行特定的操作并通过递归不断深入到图的更深层。该功能通过定义的void DFS_recursive(int vertex)函数实现。 // DFS递归实现 void DFS_recursive(int vertex) {     printf("%d ", vertex);     visited[vertex] = true;     for (int i = 1; i < numVertices; ++i) {         if (graph[vertex][i] && !visited[i]) {             DFS_recursive(i);         }     } }         （3）栈操作 建立一个新的栈为DFS非递归的是实现做准备。该功能通过定义的void push(int item)函数来实现。 // 栈操作 void push(int item) {     stack[++top] = item; } int pop() {     return stack[top--]; }         （4）DFS非递归实现（使用栈） DFS的非递归方法的实现此次课题采用的是栈的方式实现， 这个函数首先重置了visited数组，确保每个顶点都标记为未访问。然后，它将起始顶点压入栈中，并开始一个循环，该循环持续到栈变空为止。在循环内部，它弹出栈顶元素作为当前正在处理的顶点，打印该顶点，并检查它的所有邻接顶点。如果找到一个未被访问的邻接顶点，就将其压入栈中并标记为已访问。这个过程重复进行，直到栈中的所有顶点都被处理完毕。该功能通过定义的void DFS_stack(int startVertex)函数来实现。 // DFS非递归实现（使用栈） void DFS_stack(int startVertex) { int i;     for (i = 1; i < numVertices; ++i) {         visited[i] = false;     }     push(startVertex);     visited[startVertex] = true;     while (top != -1) {         int currentVertex = pop();         printf("%d ", currentVertex);         for (int i = 1; i < numVertices; ++i) {             if (graph[currentVertex][i] && !visited[i]) {                 push(i);                 visited[i] = true;             }         }     } }         （5）队列操作 建立一个新的队列来为BFS的实现做准备，该功能的实现通过定义的void enqueue(int item)函数来实现。 // 队列操作 void enqueue(int item) {     queue[++rear] = item; } int dequeue() {     return queue[front++]; }         （6）BFS实现  BFS实现在此次课题中采用的是队列的方式来实现，依据之前定义的int queue[MAX_SIZE];int front = 0, rear = -1;队列函数来采用队列的方式，该功能的实现通过定义的void BFS(int startVertex)函数实现。 // BFS实现 void BFS(int startVertex) {     for (int i = 1; i < numVertices; ++i) {         visited[i] = false;     }     enqueue(startVertex);     visited[startVertex] = true;     while (rear >= front) {         int currentVertex = dequeue();         printf("%d ", currentVertex);         for (int i = 1; i < numVertices; ++i) {             if (graph[currentVertex][i] && !visited[i]) {                 enqueue(i);                 visited[i] = true;             }         }     } }

三、测试分析

3.1操作系统主界面 如图3所示：

图3

3.2创建图表 如图4所示：

图4

3.3深度优先搜索（递归） 如图5所示：

图5

3.4深度优先搜索（堆栈） 如图6所示：

图6

3.5广度优先搜索 如图7所示：

图7

五、总结

        在本次数据结构课程设计中，我经历了从理论到实践的重要转变，收获颇丰。

通过实际的项目开发，我更加深入地理解了各种数据结构的特点和应用场景。例如，在使用图表时，深刻体会到了它在动态数据管理上的灵活性。在设计过程中，我遇到了许多挑战。如算法的优化、代码的调试等，但这些难题也促使我不断思考和探索，提升了解决问题的能力。

        我学会了如何分析问题，选择合适的数据结构和算法来实现功能需求。同时，我也意识到了代码规范和注释的重要性，良好的代码结构不仅方便自己后续的维护和修改，也有利于他人的理解和复用。团队合作方面，与同学的交流和讨论让我看到了不同的思路和方法，拓宽了自己的视野。我们共同攻克难题，互相学习和进步。回顾整个课程设计过程，我不仅巩固了数据结构的知识，还培养了自己的编程能力、逻辑思维和解决问题的综合素养。我明白，数据结构是编程的基石，只有扎实掌握，才能在未来的学习和工作中更加游刃有余。

        然而，我也清楚地认识到自己存在的不足之处，例如在时间管理上还可以做得更好，以提高项目的完成效率。

        总之，这次数据结构课程设计是一次宝贵的经历，为我今后的学习和发展奠定了坚实的基础。

源代码如下：

#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_SIZE 100 // 图的邻接矩阵 int graph[MAX_SIZE][MAX_SIZE]; int numVertices; // 辅助数组用于DFS bool visited[MAX_SIZE]; // 栈和队列的声明 int stack[MAX_SIZE]; int top = -1; int queue[MAX_SIZE]; int front = 0, rear = -1; // 函数声明 void createGraph(); void DFS_recursive(int vertex); void push(int item); int pop(); void DFS_stack(int startVertex); void BFS(int startVertex); void enqueue(int item); int dequeue(); void printMenu(); void executeChoice(int choice); int main() {     int choice;     do {         printMenu();         scanf("%d", &choice);         executeChoice(choice);     } while (choice != 0);     return 0; } // 创建图的邻接矩阵 void createGraph() {     printf("输入顶点数: ");     scanf("%d", &numVertices);     printf("输入邻接矩阵:\n");     for (int i = 0; i < numVertices; ++i) {         for (int j = 0; j < numVertices; ++j) {             scanf("%d", &graph[i][j]);         }     } } // DFS递归实现 void DFS_recursive(int vertex) {     printf("%d ", vertex);     visited[vertex] = true;     for (int i = 1; i < numVertices; ++i) {         if (graph[vertex][i] && !visited[i]) {             DFS_recursive(i);         }     } } // 栈操作 void push(int item) {     stack[++top] = item; } int pop() {     return stack[top--]; } // DFS非递归实现（使用栈） void DFS_stack(int startVertex) {     int i;     for (i = 1; i < numVertices; ++i) {         visited[i] = false;     }     push(startVertex);     visited[startVertex] = true;     while (top != -1) {         int currentVertex = pop();         printf("%d ", currentVertex);         for (int i = 1; i < numVertices; ++i) {             if (graph[currentVertex][i] && !visited[i]) {                 push(i);                 visited[i] = true;             }         }     } } // 队列操作 void enqueue(int item) {     queue[++rear] = item; } int dequeue() {     return queue[front++]; } // BFS实现 void BFS(int startVertex) {     for (int i = 1; i < numVertices; ++i) {         visited[i] = false;     }     enqueue(startVertex);     visited[startVertex] = true;     while (rear >= front) {         int currentVertex = dequeue();         printf("%d ", currentVertex);         for (int i = 1; i < numVertices; ++i) {             if (graph[currentVertex][i] && !visited[i]) {                 enqueue(i);                 visited[i] = true;             }         }     } } // 打印菜单 void printMenu() {     printf("\n\t\t==================================");     printf("\n\t\t        系统菜单             \n");     printf("\n\t\t1.     创建图表              \n");     printf("\n\t\t2.     深度优先搜索（递归）  \n");     printf("\n\t\t3.     深度优先搜索（堆栈）  \n");     printf("\n\t\t4.     广度优先搜索          \n");     printf("\n\t\t0.     退出                  \n");     printf("\n\t\t==================================");     printf("\n输入你的选择: "); } // 执行用户选择的操作 void executeChoice(int choice) {     switch (choice) {     case 1:         createGraph();         break;     case 2:         printf("输入 DFS 递归的起始顶点: ");         int startVertex;         scanf("%d", &startVertex);         DFS_recursive(startVertex);         break;     case 3:         printf("输入 DFS 堆栈的起始顶点: ");         scanf("%d", &startVertex);         DFS_stack(startVertex);         break;     case 4:         printf("输入 BFS 的起始顶点: ");         scanf("%d", &startVertex);         BFS(startVertex);         break;     case 0:         printf("退出\n");         break;     default:         printf("无效的选择。请再试一次.\n");     }     printf("\n"); }