单向链表每个节点都是由两部分组成:数据字段和指针,指针指向下一个元素在内存中的位置。
单向链表的第一个节点节点是链表头指针,而最后一个节点的指针设为None,不指向任何元素。(链表头指针相当重要!!!)
使用Python实现单向链表,我们可以使用一个节点类来封装节点,每创建一个节点就生成一个节点类的实例。
这里主要实现了单向链表节点的遍历、添加、插入、删除,反转。
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
class Player: """节点类""" def __init__( self ): """初始化姓名,分数,指针""" self .name = '' self .score = 0 self . next = None def ergodic(head, num = None , is_print = False ): """遍历函数,num是遍历到哪一个位置序号,is_print是否触发打印方法""" ptr = head count = 0 while True : if num = = count: break if ptr. next : count + = 1 ptr = ptr. next if is_print: print ( 'No.' + str (count), ptr.name, ptr.score, '--->' , ptr. next .name if ptr. next else None ) else : break return ptr # 返回遍历完成后的最后一个节点 def invert(x): # x是链表的第一个节点(即head的指针的指向) """反转链表""" y = x. next # y是x原来的next if y is None : # y等于None表示当前链表只有一个节点 return x x. next = None # 将第一个节点的next指向None(因为反转了) while True : # 循环反转后面的所有节点 r = y. next y. next = x if r is None : # r是None说明y已经是原本链表的最后一个节点了 return y # 返回y,这个y是反转后的链表的第一个节点 x = y y = r head = Player() while True : select = input ( "(1).新增 (2).查看 (3).插入 (4).删除 (5).反转 (6).离开\n输入:" ) if select = = "1" : # 新增节点 ptr = ergodic(head) # 获取当前链表最后一个节点 next_data = Player() # 创建一个新节点 next_data.name = input ( "姓名:" ) next_data.score = input ( "分数:" ) next_data. next = None ptr. next = next_data # 连接节点 elif select = = "2" : # 遍历查看链表所有节点 print ( "所有数据显示如下:" ) ergodic(head, is_print = True ) # 遍历链表,将打印参数设为True elif select = = '3' : # 向链表中任意位置插入节点,位置以序号表示,即第一个节点序号为1,第二个节点序号为2,以此类推 try : num = int ( input ( "请输入需要插入的节点位置序号:" )) # 输入序号必须是大于0的正整数,如果输入大于最后一个节点的序号则插入到最后一个节点之后 if num < 1 : print ( "输入必须为大于0的正整数" ) continue except ValueError: print ( "输入有误" ) continue ptr = ergodic(head, num - 1 ) # 获取需要插入位置的前一个节点 insert_data = Player() insert_data.name = input ( "姓名:" ) insert_data.score = input ( "分数:" ) insert_data. next = ptr. next ptr. next = insert_data elif select = = '4' : # 删除链表中任意位置的节点 try : num = int ( input ( "请输入需要删除的节点位置序号:" )) # 输入序号必须是大于0的正整数,如果输入大于最后一个节点的序号则删除最后一个节点 if num < 1 : print ( "输入必须为大于0的正整数" ) continue except ValueError: print ( "输入有误" ) continue ptr = ergodic(head, num - 1 ) # 获取需要删除位置的前一个节点 ptr. next = ptr. next . next elif select = = '5' : # 反转链表 new_first = invert(head. next ) # 获取新的第一个节点 head. next = new_first # head指向新的第一个节点 print ( '成功反转' ) elif select = = '6' : print ( "成功离开" ) break else : print ( "输入错误,请重试" ) |
部分运行结果:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/heibuliuqiu_gk/article/details/102641541