实验报告：城市链表问题和约瑟夫环_[问题描述] 将若干城市的信息,存入一个带头结点的单链表。结点中的城市信息包括:

作者：天景科技苑 | 2024-07-01 06:42:08

踩

[问题描述] 将若干城市的信息,存入一个带头结点的单链表。结点中的城市信息包括:

实验目的

本次实验的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。
熟悉线性表在软件工程项目中数据存储和处理中的运用。

实验内容

城市链表

[问题描述]

将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。

[基本要求]

　　（1）给定一个城市名，返回其位置坐标；

　　（2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。

[测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据。

约瑟夫环

[问题描述]

约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，

每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

[基本要求]

利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

[测试数据]

　　m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。

[实现提示]

程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。

实验环境

Dev C++

实验过程和实验结果

问题分析与设计方案：

分析每个结点的结构体里应该包含的元素：城市名字，经纬度
打印信息：注意排版提高美观增强用户观赏性
实现查找功能（注意健壮性）
利用数学库封装出距离比较函数

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define OK 1
#define ERROR 0
typedef int Status ;
typedef struct LNode{
char name[200] ; //存储城市名；
float x, y ; //存储城市坐标；
struct LNode *next ;
}LNode, *LinkList;
//创建一个链表
LinkList CreatList (int n) {
LinkList l, tmp, p ;
l = (LinkList)malloc(sizeof(LNode)) ;
l->next = NULL ;
tmp = l ;
int i = 0;
for(i = 0 ; i < n ; i ++) { //向链表中存储数据
p = (LinkList)malloc(sizeof(LNode)) ;
scanf("%s %f %f", &p->name, &p->x, &p->y) ;
p->next = tmp->next ;
tmp->next = p ;
tmp = p ;
}
return l ;
}
//打印出链表的信息
Status Display(LinkList l) {
LinkList p ;
p = l ;
p = p->next ;
printf("\n\n") ;
printf("城市信息为：") ;
printf("\n") ;
printf("-----------------------------------------------\n") ;
printf("序号\t城市名称\t城市坐标\n", p->name, p->x, p->y) ;
int order = 1 ;
while(p) {
printf("%02d\t %-8s\t( %.2f°N, %.2f°E )\n",order, p->name, p->x, p->y) ;
p = p->next ;
order++ ;
}
printf("-----------------------------------------------\n\n" ) ;
return OK ;
}
//查找一个链表元素
LinkList SearchList(LinkList l){
LinkList q ;
q = (LinkList)malloc(sizeof(LNode)) ;
q->next = NULL ;
scanf("%s", &q->name) ;
LinkList p ;
p = l ;
while(p) {
p = p->next ;
if(!strcmp(p->name, q->name)){
return p ;
}
if(p->next == NULL){
printf("没有录入此地区信息，系统关闭") ;
return NULL ;
break ;
}
}
}
//进入城市距离计算比较功能
LinkList DistanceCity(LinkList l, float e){
printf("请输入一个城市的名称作为定位标志:\n") ;
LNode *index , *p, *q;
index = SearchList(l) ;
//计算列表中其他城市与定位城市的距离
int i = 0 ;
float dx = 0 , dy = 0 ;
float distance = 0 ;
LinkList dis ; //距离小于给定值的城市的所有信息存储在此链表 ;
LNode *d ; //一直指向dis链表末尾的指针;
dis = (LinkList)malloc(sizeof(LNode)) ;
dis->next = NULL ;
d = dis ;
q = l ; //利用两个坐标点间的距离公式，开始计算
while(q){
q = q->next ;
dx = q->x - index->x ;
dy = q->y - index->y ;
distance = sqrt(dx * dx + dy * dy) ;
printf("%-8s距%-8s的距离为%.2f\n",q->name, index->name, distance) ;
if(distance <= e) {
LinkList temp ;
temp = (LinkList)malloc(sizeof(LNode)) ;
strcpy(temp->name , q->name) ;
temp->x = q->x ;
temp->y = q->y ;
temp->next = d->next ;
d->next = temp ;
d = temp ;
}
if(q->next == NULL)
Display(dis) ;
}
return dis ;
}
Status Entrance(char c, LinkList l ){
//查找城市信息
if(c == 'A' || c == 'a') {
LNode *index ;
printf("请输入希望查询的城市：") ;
index = SearchList(l) ;
printf(" ( %.2f°N, %.2f°E )", index->x, index->y) ;
}
//进入城市距离计算比较功能
if(c == 'B' || c =='b') {
float n ;
printf("输入查询的距离范围：\n") ;
scanf("%f", &n) ;
LinkList l_1 ;
l_1 = DistanceCity(l,n);
Display(l_1) ;
}
return OK ;
}
int main() {
printf("建立城市链表ing\n") ;
int e = 0 ;
printf("请输入城市数目:") ;
scanf("%d", &e) ;
//创建一个城市链表
LinkList l ;
printf("请批量输入城市名及经纬坐标（例：a 120 12 b 23 45 c 12 32）：\n") ;
l = CreatList(e) ;
Display(l) ;
//入口
printf("操作菜单\n") ;
printf("A.查找城市信息\n") ;
printf("B.查找一定距离内的所有城市\n") ;
printf("C.退出操作\n") ;
while(1){
char c ;
printf("\n请输入操作数:\n") ;
scanf("%s", &c) ;
if(c == 'C' || c == 'c'){
printf("退出程序。\n") ;
break ; // 退出程序
}
Entrance(c, l) ;
}
return 0 ;
}

问题分析与设计方案：

1. 1. 1. 分析每个结点的结构体里应该包含的元素：包括所在位置（最开始的时候没有考虑到和单链表不同而没有设置，走了一些弯路）和密码
    2. 打印环形链表（也作为检验措施帮助调试）
    3. 实现每次出列更改密码操作

#include<stdio.h>
#include<stdlib.h>
typedef struct node {
int num; //num为人的顺序
int data; //data为人所带的密码
struct node* next;
} node, * Linklist;
void Initlist(Linklist* L) {
(*L) = (Linklist)malloc(sizeof(node));
(*L)->next = (*L);
}
void CreateList(Linklist* L, int n) {
node* s, * r;
r = *L;
int i;
while (n--) {
s = (Linklist)malloc(sizeof(node));
printf("请输入人的位置和密码:");
scanf("%d%d", &s->num, &s->data);
r->next = s;
r = s;
}
r->next = (*L)->next; //让尾节点指向首节点
}
void print(Linklist L, int n, int m) {
Linklist p, r;
p = L;
r = L->next;
printf("出列顺序:");
while (n--)
{
for (int j = 1; j < m; j++) //循环m-1次后后继节点就是要删除的节点！！
{
p = r;
r = r->next;
}
printf("%2d", r->num);
p->next = r->next;
m = r->data;
free(r);
r = p->next;
}
}
int main() {
int n;
int m;
printf("初始报数上限值:");
scanf("%d", &m); //第一个开始密码
Linklist L;
Initlist(&L);
printf("请输入人数大小:");
scanf("%d", &n);
CreateList(&L, n);
print(L, n, m);
return 0;
}

实验心得

巩固了C语言和C++的知识点，对指针的理解更进一步：指针调用结构体内的变量是高效，在初次学习C语言的时候并未理解透彻
基本掌握了链表的知识点，熟练掌握了链表的增、删、查：但链表的简单八股文基本能够熟练操作了，但是针对每个题目而异的部分还需要反复思考，不能很快写出。
对于用户交互界面的设计更加友好：oj风格的输入输出便于机器检查，但不利于自己和他人阅读，在和同学的交流过程中需要增加一些交互式的设计包括一些提示，有助于下次阅读代码时能够快速理解
对于边界的调试更加细致：在实际写代码的时候链表中间的步骤本身不是难点，但是在初始化第一位元素和检验边界条件的时候往往有很多的bug。这时可以使用debug对一些函数里的元素进行观测。另一方面也可以通过“打印”的方式来检验。在进行实验构成中，建立的Display函数往往最大的作用不是打印出这个链表本身，而是在循环过程中反复打印，帮助理解每次循环赋值后内部结构到底是什么样子的。
对于编译器本身有了更好的理解：在实验过程中尝试了多种编译器，对包括不同版本dev c++会遇到的因版本不同而产生的bug有了一定的理解。
忘记free导致指针重复写入出现报错
注意代码健壮性，把一些由于用户输入不当产生的错误做好提前的预防和解决措施（包括用户输入选项时候输入的大小写同时设置提高使用效果）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/775466