一份成绩为优的数据结构与算法课程设计实训报告
一份成绩为优的《数据结构与算法课程设计》实训报告
C语言版 建议使用小熊猫C++，适合初学者，此报告的代码在Visual Studio Code也可以运行
题目一 线性结构的操作
1、创建两个单链表LA=(1,2,5)，LB=(2,4,6,7)，编写算法，将它们合并成一个单链表LC，要求LC也是非递减有序排列。
思路：利用现有的单链表LA和LB中的结点空间建立新表LC；
创建一个新的单链表LC；
同时遍历LA和LB并比较元素；
将LA或LB的较小元件插入LC；
移动到列表中插入该元素的下一个元素；
继续这个过程，直到两个列表的所有元素都合并到LC里面为止；
课本用尾插法建立单链表例子：
*void CreateFromeTail(LinkList LA)
//LA是带头结点的空链表头指针
{Node r, * s;*
int flag = 1;//设置一个标志，初值为1，当输入“$“时flag为0，建表结束
r = LA; //r指针动态指向链表的当前表尾，以便做尾插入
while (flag)//循环输入表中元素值，将建立新结点s插入表尾
{c = getchar();//
if (c != ’s')
{ s = (Node)malloc(sizeof(Node));
s->data = c;r->next = s;r = s; }
else{
flag = 0; r->next = NULL;}
}}*
#include <stdio.h>
#include <stdlib.h>
// 定义单链表的节点结构
struct Node {/_结点类型定义 node_/
int data;//数据域（int）
struct Node* next;
};
// 向单链表尾部插入节点，把具有给定 new_data 值的新节点插入末尾的链表里面。
//它等下指向列表头的指针 head 和新数据 new_data 作为输入参数
void insertNode(struct Node** head, int new_data) {
struct Node* new_node=(struct Node*)malloc(sizeof(struct Node));//为新节点分配内存
struct Node* last=*head;//最后的指针设为列表头
new_node->data=new_data;//初始化新节点的 data 和 next 字段。
new_node->next=NULL;
if (*head ==NULL) {
*head =new_node;
return; //检查列表空的话，头指针设为新节点
}
while (last->next !=NULL) {
last=last->next; //last 指针遍历列表，直到到达末尾，
}
last->next=new_node; //last->next 设为新结点
}
// 构建用于合并两个排序的链表 LA 和 LB 的函数
struct Node* mergeLists(struct Node* LA, struct Node* LB) {
struct Node* LC=NULL; //创建结果合并列表
struct Node* tail =NULL;
while (1) {
if (LA==NULL) {
tail->next=LB;
break; //检查 LA 是空的话将尾部节点 tail 的 next 字段设置为 LB 并中断循环
}
if (LB==NULL) {
tail->next=LA;
break;
}
if (LA->data<=LB->data) {
insertNode(&LC, LA->data);
LA=LA->next;
} else {
insertNode(&LC, LB->data);
LB =LB->next; //比较当前节点 LA 和 LB 的数值。如果 LA->data 小于或等于 LB->data，用 insertNode（）把 LA->data 的数据插入 LC，然后，LA 针移动到下一个节点，如果 LA->data 大于 LB->data，LB->data 值插入 LC
}
if (tail==NULL) {
tail=LC;
} else {
tail = tail->next;
}
}//持续到 LALB 完全被处理
return LC;//返回 LC 作为合并后的新单链表的头节点
}
// 打印单链表
void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
int main() {
struct Node* LA = NULL;
struct Node* LB = NULL;
// 将元素插入 LA
insertNode(&LA, 1);
insertNode(&LA, 2);
insertNode(&LA, 5);
// 将元素插入 LB
insertNode(&LB, 2);
insertNode(&LB, 4);
insertNode(&LB, 6);
insertNode(&LB, 7);
// LALB 合并到 LC
struct Node* LC=mergeLists(LA, LB);
// 输出 LC
printf("合并完成的列表: ");
printList(LC);
return 0;
}输出结果：合并完成的列表: 1 2 2 4 5 6 7
_题目 二 图的操作_
2*、*用邻接矩阵法创建有向图，编写算法，实现图的深度优先遍历，输出遍历序列、领接矩阵。
知识点回顾：图是比树更一般、更复杂的非线性数据结构。图结构中结点之间的关系是任意的，每个元素都可以和其他任何元素相关，即元素之间是多对多的关系。
有向图：一个有向的、无环的图，其中顶点（节点）之间有边相连。有向图可以用邻接矩阵来表示，其中矩阵的行和列分别表示顶点。在邻接矩阵中，如果两个顶点之间有边相连，则在相应的矩阵元素中存储 1，否则为 0。
领接矩阵：采用两个数组表示图，一个用于存储顶点信息的一维数组；另一个用于存储图中顶点之间的关联关系的二维数组。
书本中的领接矩阵表示法：
#include <stdio.h>
#include <stdlib.h>
// 图结构定义:顶点数组、边数组和访问标记数组
typedef struct gr {//图
int ver[4]; // 顶点数组
int edge[4][3]; // 边数组
int vertex; // 顶点数
int ed; // 边数
} gr;
// 初始化图结构
void init_graph(gr* g) {
g->vertex = 0;
g->ed = 0;
for (int i = 0; i < 4; i++) {
g->ver[i] = 0;
for (int j = 0; j < 3; j++) {
g->edge[i][j] = 0;
}
}
}
// 添加顶点
void add_vertex(gr* g, int v) {
g->ver[v] = 1;
g->vertex++;
}
// 添加边
void add_edge(gr* g, int u, int v) {
g->edge[u][v] = 1;
g->edge[v][u] = 1;
g->ed++;
}
// 深度优先遍历
void dfs(gr* g, int v, int visited[], int* count) {//dfs 用于遍历给定图结构中的所有顶点。
visited[v] = 1; // 标记顶点 v 为已访问
printf("%d ", v); // 输出访问过的顶点 v
for (int i = 0; i < g->vertex; i++) {
if (g->edge[v][i] == 1 && visited[i] == 0) { // 如果顶点 i 与顶点 v 相邻且未访问
dfs(g, i, visited, count); // 递归调用 dfs 函数，以访问顶点 i
}
}
}
int main() {
gr g;
init_graph(&g);// 初始化图结构
int vertex, ed;// 顶点数和边数
printf("请输入顶点数和边数：");
scanf("%d%d", &vertex, &ed);// 输入顶点数和边数
for (int i = 0; i < vertex; i++) {
int v;
printf("请输入第%d 个顶点：", i + 1);
scanf("%d", &v); // 输入顶点 u 和顶点 v
add_vertex(&g, v);// 添加边(u, v)和(v, u)
}
for (int i = 0; i < ed; i++) {
int u, v;
printf("请输入第%d 条边的两个顶点（用空格隔开）：", i + 1);
scanf("%d%d", &u, &v);
add_edge(&g, u, v);
}
int visited[4];// 访问标记数组
for (int i = 0; i < 4; i++) {
visited[i] = 0;
}
int count = 0;// 访问过的顶点数
dfs(&g, 0, visited, &count);// 从顶点 0 开始深度优先遍历图结构
printf("\n 访问过的顶点数为：%d\n", count);
return 0;
}输出：
请输入顶点数和边数：4 8
请输入第 1 个顶点：0
请输入第 2 个顶点：1
请输入第 3 个顶点：2
请输入第 4 个顶点：3
请输入第 1 条边的两个顶点（用空格隔开）：0 1
请输入第 2 条边的两个顶点（用空格隔开）：1 3
请输入第 3 条边的两个顶点（用空格隔开）：2 0
请输入第 4 条边的两个顶点（用空格隔开）：0 3
请输入第 5 条边的两个顶点（用空格隔开）：2 1
请输入第 6 条边的两个顶点（用空格隔开）：3 2
请输入第 7 条边的两个顶点（用空格隔开）：2 3
请输入第 8 条边的两个顶点（用空格隔开）：1 2
0 1 2 3
访问过的顶点数为：4
这段代码实现了一个有向图结构，并提供了深度优先遍历的功能，用于遍历给定图结构中的所有顶点。
_题目 三 查找_
4*、*列表中有 11 个元素（6,12,15,18,22,25,28,35,46,58,60），编写算法，使用折半查找法查找 12 和 50。
知识点：折半查找法
别名：二分查找
要求线性表是有序表。按关键字有序排序
基本过程：中间记录关键字与查找关键字比较；如果两者相同，则查找成功；
如果查找关键字小于中间位置关键字，则查前部子表，否则查后部子表。
算法：
本题思路：
#include <stdio.h>
#define MAXSIZE 11 // 定义线性表的最大长度
typedef int KeyType; // 定义关键字类型为整型
typedef struct {
KeyType key; // 关键字
// 其他数据项
} ElemType; // 定义元素类型
typedef struct {
ElemType r[MAXSIZE + 1]; // 存储线性表元素
int length; // 线性表长度
} RecordList; // 定义线性表类型
int BinSrch(RecordList l, KeyType k);
int main() {
RecordList l={{ 6, 12, 15, 18, 22, 25, 28, 35, 46, 58, 60}, MAXSIZE};
KeyType k1 = 12, k2=50;
int pos1=BinSrch(l, k1);
int pos2=BinSrch(l, k2);
if (pos1) {
printf("元素 %d 在列表中的位置是 %d\n", k1, pos1);
} else {
printf("元素 %d 不在列表中\n", k1);
}
if (pos2) {
printf("元素 %d 在列表中的位置是 %d\n", k2, pos2);
} else {
printf("元素 %d 不在列表中\n", k2);
}
return 0;
}
int BinSrch(RecordList l, KeyType k) {
int low=1;
int high=l.length;
while (low<=high) {
int mid=(low+high) / 2;
if (k == l.r[mid].key) {
return(mid); // 找到待查元素
} else if (k < l.r[mid].key) {
high=mid-1; // 未找到,则继续在前半区间进行查找
} else {
low= mid+1; // 继续在后半区间进行查找
}
}
return(0);
}输出结果：元素 12 在列表中的位置是 1
元素 50 不在列表中
这个代码的核心方法就是二分查找算法，它通过比较关键字与列表中的元素，不断缩小搜索范围，直到找到关键字或搜索范围为空
_题目 四 图_
编写算法，求下图任意两个顶点间的最短路径。
实验思路：使用 Dijkstra 算法来找到源点到其他所有顶点的最短路径。
回顾课本知识点
1.定义
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法（一种贪心算法），用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法是很有代表性的最短路径算法，注意该算法要求图中不存在负权边。
回归题目
使用邻接表表示法表示的图：
使用 Dijkstra 算法求解从顶点 0/1/2/3/4 开始的最短路径：
#include <stdio.h>
#include <limits.h>
#define V 5 // 图中的顶点数
//定义函数来查找具有最小距离值的顶点
int mind(int dist[], int sptSet[]) {//最小距离 mind，dist[]存储每个节点的最短路径（权重），sptSet[]存储每个节点的父节点
int min = INT_MAX, min_index;//定义的常量 INT_MAX 表示整数类型的最大值，min_index 索引最小值
//寻找图中未被访问过的节点中距离最短的节点，找到下一个要添加到树中的边所连接的节点
for (int v = 0; v < V; v++) {//遍历所有节点，检查它们是否被访问过
if (sptSet[v] == 0 && dist[v] <= min) {//寻找图中未访问过的节点中，距离起点最近的节点。
min = dist[v]; // （sptSet[v] == 0）。如果节点未被访问过，并且其距离起点（dist[v]）小于等于当前找到的最小距离（min），
min_index = v; //那么就更新最小距离（min）和最小距离对应的节点索引（min_index
}
}
return min_index;
}
// 打印构造的距离数组的函数
void printSolution(int dist[], int n) {
printf("终点 路径长度\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
// 实现图的 Dijkstra 单源最短路径算法的函数
void dijkstra(int g[V][V], int src) {//g 为图
int dist[V]; // 输出数组。dist【i】保持从 src 到 i 的最短距离
int sptSet[V];
// 确定路径树或从 src 到 i 的最短距离
// 将所有距离初始化为无穷大，并将 stpSet【】初始化为 0.// 如果最短路径中包含顶点 i，则 sptSet【i】为真
for (int i = 0; i < V; i++) { // 用于寻找一个有权重图中的最短路径。
dist[i] = INT_MAX;
sptSet[i] = 0;
}
// 源顶点与自身的距离始终为 0
dist[src] = 0;
// 求所有顶点的最短路径
//用一个循环来迭代 V-1 次，每次迭代都会选择一个未被处理过的节点 u，将其标记为已处理，并更新其相邻节点的距离.
for (int count = 0; count < V - 1; count++) {
int u = mind(dist, sptSet);
// 将拾取的顶点标记为已处理
sptSet[u] = 1;
// 更新选中顶点的相邻顶点的分布值，确保找到的是最短路径
for (int v = 0; v < V; v++) {//遍历
if (!sptSet[v] && g[u][v] && dist[u] != INT_MAX &&//检查它们是否与选定顶点之间的权重边更短，
dist[u] + g[u][v] < dist[v]) { //如果是，就更新 dist【v】的值，
dist[v] = dist[u] + g[u][v]; //让它等于 dist[u] + g[u][v]
}
}
}
printSolution(dist, V);// 打印构造的距离数组
}
int main() {//权重图 g 将其传递给 dijkstra 函数，指定源节点为 0 或 1、2、3、4
int g[V][V] = {{0, 1, 0, 0, 0},//图是一个 5x5 的矩阵
{1, 0, 5, 0, 5},
{0, 5, 0, 4, 6},
{0, 0, 4, 0, 3},
{0, 5, 6, 3, 0}};
dijkstra(g, 0); //寻找从顶点 0 开始的最短路径
return 0;
}运行上述代码，调用顶点 0 时，输出结果为：
调用顶点 1 时，输出结果为：
调用顶点 2 时，输出结果为：
调用顶点 3 时，输出结果为：
调用顶点 4 时，输出结果为：
比如：
总结：
经过本次实训，对于上机操作有了更加深入的了解和认识。实践和理论知识相比还是有很大的难度的，实训考察的不仅仅是我们的理论知识，更多的是考察我们处理问题的能力和对理论知识的应用能力。丰富的理论知识并不能保证我们能顺利的应用到实践中去，当然，如果我们没有理论知识依然无法实践。实训过程中，我遇到的问题更多的是一些理论运用问题，对算法没有熟悉的认识，不能在代码出问题时冷静的处理问题。对于实训报告，最大的问题就是我不能灵活运用课本现有的基本算法应用到实验代码中，且因为缺乏对各章知识点基本定义的背诵记忆与深刻理解，几乎每段代码只有写完那三天的我才知道写的什么意思、什么思路，这些问题充分说明了写题前先理清思路、回顾课本知识点，罗列关键词的重要性。