【实验报告概述】
本实验报告主要探讨了两个数据结构应用问题——城市链表和约瑟芬环问题。实验旨在让学生熟悉线性表的基本运算在不同存储结构上的实现，特别是链表的操作，并理解线性表在实际软件工程中的应用。
### 一、城市链表
城市链表是一个带头结点的单链表，每个结点包含城市名和位置坐标。实验要求实现以下功能：
1. **查找城市坐标**：给定城市名，返回对应的城市坐标。
2. **查找范围内的城市**：给定一个位置坐标P和距离D，返回所有与P的距离小于等于D的城市。
实验中，首先创建链表，输入所有城市的信息。然后设计相应的函数来实现查找、插入、删除和更新操作。例如，可以使用以下算法实现查找功能：
```c
// 查找城市坐标
Node* FindByName(LinkList l, char* name) {
Node* p = l->next;
while (p != NULL) {
if (strcmp(p->name, name) == 0)
return p;
p = p->next;
}
return NULL; // 如果未找到返回NULL
}
// 查找范围内的城市
LinkList FindInRange(LinkList l, float px, float py, float d) {
LinkList result = CreatList(0);
Node* p = l->next;
while (p != NULL) {
float dist = sqrt((p->x_index - px) * (p->x_index - px) + (p->y_index - py) * (p->y_index - py));
if (dist <= d) {
Append(result, p->name, p->x_index, p->y_index); // 将符合条件的城市添加到新链表
}
p = p->next;
}
return result;
}
```
### 二、约瑟夫环问题
约瑟夫环问题是一个经典的计算机科学问题，使用单向循环链表存储结构进行模拟。初始设定一个报数上限值m，从1开始报数，当报到m时，该人退出循环，同时将他的密码作为新的m值，从下一个人开始重新报数，直到所有人退出。实验要求按照出列顺序打印各人的编号。
```c
// 约瑟夫环
void JosephusProblem(LinkList l, int m) {
Node* current = l->next;
Node* next = l->next->next;
int count = 0;
while (l->next != NULL) {
count++;
if (count % m == 0) {
printf("%d ", current->data);
next = current->next;
l->next = next;
free(current);
current = next;
} else {
current = current->next;
}
}
free(current);
}
```
### 三、实验环境
实验环境为Dev或VS，这两种集成开发环境均支持C/C++语言编程，可用于编写和运行上述链表操作的代码。
### 四、实验过程与结果
在实验过程中，首先根据给定的测试数据创建城市链表，然后对链表进行增删查改等操作，验证功能正确性。对于约瑟夫环问题，同样输入测试数据，通过程序输出验证出列顺序是否正确。在实验报告中，应当详细记录实验步骤、操作过程、结果分析以及可能遇到的问题与解决方案。
此外，实验报告还可以包含扩展部分，如将城市链表的操作扩展到顺序存储结构，以对比不同存储结构的优缺点。
通过这个实验，学生不仅加深了对线性表的理解，也锻炼了问题解决和编程能力，为将来在软件工程中处理类似问题打下了坚实的基础。
