Python 作业 — nasbuild.dev
作业 / 实验一.py
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
# ① 新建一个带有头结点的空链表
self.head = Node(None)
def add(self, data):
# 在链表头插入一个新结点（头插法）
new_node = Node(data)
new_node.next = self.head.next
self.head.next = new_node
def insert(self, data):
# 在指定值的结点后面插入新结点
# 找到值为 data 的前驱结点，在其后面插入 data+1
p = self.head
while p.next is not None:
if p.next.data == data:
new_node = Node(data + 1)
new_node.next = p.next.next
p.next.next = new_node
return
p = p.next
def display(self):
# 逐个输出结点的值
p = self.head.next
while p is not None:
if p.next is not None:
print(p.data, end="->")
else:
print(p.data)
p = p.next
# 主程序
L = LinkedList()
# ② 在链表头逐个插入9个结点
# 头插法是倒序插入，要得到 1,2,3,4,5,7,8,9,10 的遍历结果
# 需要按从大到小的顺序插入
nums = [10, 9, 8, 7, 5, 4, 3, 2, 1]
for x in nums:
L.add(x)
print("链表建立完成后遍历结果：")
L.display()
# ③ 在5和7之间插入一个结点，数据域为6
L.insert(5)
print("在5和7之间插入6后遍历结果：")
L.display()
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def add(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
def delete_head(self):
if self.head is None:
return None
data = self.head.data
self.head = self.head.next
if self.head is None:
self.tail = None
return data
def is_empty(self):
return self.head is None
def display(self):
p = self.head
while p is not None:
print(p.data, end=" ")
p = p.next
def radix_sort(arr):
# ① 将待排数据转换为链表方式存储
L = LinkedList()
for x in arr:
L.add(x)
print("排序前：")
L.display()
print()
# 找最大值，确定最大位数
max_val = max(arr)
max_digits = len(str(max_val))
# ② 建立10个链表，分别对应数字0-9
buckets = []
for i in range(10):
buckets.append(LinkedList())
# 按位数从个位到最高位进行分配和收集
for digit in range(max_digits):
# 分配：将链表中的元素按当前位的数字插入对应桶
while not L.is_empty():
num = L.delete_head()
# 取当前位的数字
index = (num // (10 ** digit)) % 10
buckets[index].add(num)
# 收集：将10个桶中的元素按顺序读出，回存到链表
for i in range(10):
while not buckets[i].is_empty():
num = buckets[i].delete_head()
L.add(num)
print("第", digit + 1, "轮排序后：")
L.display()
print()
return L
# 主程序
arr = [123, 45, 678, 9, 10, 321, 55, 888, 234, 66]
L = radix_sort(arr)
print("排序最终结果：")
L.display()
print()