将若干城市的信息存人一个带头结点的单链表,结点中的城市信息包括城市名、 城市的位置坐标。要求: (1)给定一个城市名,返回其位置坐标; (2)给定一个位置坐标P和一个距离D,返回所有与P的距离小于等于D的城市。
时间: 2024-09-29 17:05:54 浏览: 78
为了实现这个功能,我们可以创建一个单链表结构,其中每个节点包含城市名和位置坐标两个属性。头结点将用于表示链表的开始。这里是一个简单的设计思路:
1. **数据结构**:
- 使用 `City` 类作为链表节点,包含 `name`(城市名,字符串)、`position`(位置坐标,例如一对浮点数代表经纬度)以及指向下一个节点的指针 `next`。
2. **链表操作**:
- `init_list`: 初始化一个空链表。
- `insert_city(city_name, position)`: 向链表尾部添加一个新的城市节点。
- `get_position_by_name(city_name)`: 遍历链表,查找指定城市名并返回其位置。
- `find_cities_within_distance(position, distance)`: 遍历链表,对于每个节点检查它的位置是否与目标位置的距离小于等于给定距离,如果是,则返回该节点。
以下是伪代码形式:
```python
class CityNode:
def __init__(self, name, position):
self.name = name
self.position = position
self.next = None
class CityList:
def __init__(self):
self.head = None
# 插入新城市
def insert_city(self, city_name, position):
new_node = CityNode(city_name, position)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
# 根据名称获取位置
def get_position_by_name(self, city_name):
current = self.head
while current:
if current.name == city_name:
return current.position
current = current.next
return None
# 查找距离范围内城市
def find_cities_within_distance(self, position, distance):
result = []
current = self.head
while current:
if self.distance_between_positions(current.position, position) <= distance:
result.append((current.name, current.position))
current = current.next
return result
# 计算两点间的距离(假设用欧氏距离)
def distance_between_positions(self, pos1, pos2):
# 实现计算两点之间距离的方法
```
阅读全文