Python实现不带头结点的单链表
1 # 创建一个节点类2 class Node:
3 def __init__(self, item):
4 self.item = item
5 self.next = None
6
7
8 # 创建一个单链表类
9 class SingleLink:
10 def __init__(self):
11 self.header = None # 初始化单链表的头结点
12 self.length = 0 # length:单链表的长度
13
14 # 判断单链表是否为空
15 def is_empty(self):
16 if self.header is None:
17 return True
18 else:
19 return False
20
21 '''
22 实现向单链表添加元素的功能:
23 有三种实现方式:
24 1.头插法
25 2.尾插法
26 3.从任意指定位置添加元素
27 '''
28
29 # 1.头插法
30 def preadd(self, value):
31 node = Node(value)
32 if self.is_empty():
33 self.header = node
34 else:
35 node.next = self.header
36 self.header = node
37 self.length += 1
38
39 # 2.尾插法
40 def append(self, value):
41 node = Node(value)
42 cur = self.header
43 while cur.next is not None:
44 cur = cur.next
45 cur.next = node
46 self.length += 1
47
48 # 3.从任意指定位置添加元素
49 def insert(self, index, value):
50 node = Node(value)
51 cur = self.header
52 if index <= 0:
53 self.preadd(value)
54 self.length += 1
55 elif index > self.length:
56 self.append(value)
57 self.length += 1
58 else:
59 for i in range(1, index - 1):
60 cur = cur.next
61 node.next = cur.next
62 cur.next = node
63 self.length += 1
64
65 '''
66 实现从单链表中删除元素的功能
67 有三种删除方式:
68 1.根据指定位置来删除元素
69 2.直接删除元素
70 3.清空单链表
71 '''
72
73 # 1.根据指定位置来删除元素
74 def __delitem__(self, index):
75 if index <= 0 or index > self.length:
76 raise IndexError
77 if index == 1:
78 self.header = self.header.next
79 else:
80 cur = self.header
81 for i in range(1, index - 1):
82 cur = cur.next
83 cur.next = cur.next.next
84 self.length -= 1
85
86 # 2.直接删除元素
87 def __delete__(self, value):
88 self.__delitem__(self.isExist(value))
89 self.length -= 1
90
91 # 3.清空单链表
92 def clear(self):
93 while self.length != 0:
94 self.__delitem__(self.length)
95 self.length -= 1
96 '''
97 实现修改元素的功能
98 1.修改指定位置的元素
99 '''
100 # 1.修改指定位置的元素
101 def __setitem__(self, index, value):
102 cur=self.header
103 if not isinstance(index,int):
104 raise TypeError
105 if 0<index<self.length:
106 for i in range(index-1):
107 cur=cur.next
108 cur.item=value
109 else:
110 print('您输入的信息有误！')
111 '''
112 实现对单链表的查找功能
113 有三种实现方式:
114 1.查找某元素，并返回其在链表中的位置
115 2.根据位置来查找对应的元素
116 3.遍历单链表,查找出所有元素
117 '''
118
119 # 1.查找某元素，并返回其在链表中的位置
120 def isExist(self, value):
121 cur = self.header
122 for i in range(self.length):
123 if cur.item == value:
124 return i + 1
125 cur = cur.next
126
127 # 2.根据位置来查找对应的元素
128 def __getitem__(self, index):
129 cur = self.header
130 if index <= 0 or index > self.length:
131 return print('您输入的信息有误')
132 for i in range(index - 1):
133 cur = cur.next
134 return print('第%d个位置的元素是%d' % (index, cur.item))
135
136 # 3.遍历单链表,查找出所有元素
137 def show(self):
138 cur = self.header
139 if self.length == 0:
140 print('目前单链表中没有数据!')
141 else:
142 print('目前单链表的元素有:', end=' ')
143 for i in range(self.length):
144 print('%s' % cur.item, end=' ')
145 cur = cur.next
146 print('\n')
147
148
149 if __name__ == '__main__':
150 s = SingleLink()
151 s.preadd(12)
152 s.preadd(23)
153 s.preadd(32)
154 s.show()
155 s.append(14)
156 s.append(43)
157 s.append(15)
158 s.show()
159 print('元素32在单链表的第%d个位置' % s.isExist(32))
160 print('从第三个位置插入元素:57')
161 s.insert(3, 57)
162 s.show()
163 print('删除第一个位置的元素')
164 s.__delitem__(1)
165 s.show()
166 print('直接删除元素43:')
167 s.__delete__(43)
168 s.show()
169 s.__getitem__(2)
170 s.__setitem__(3,9000)
171 s.show()
172 print('清空单链表:')
173 s.clear()
174 s.show()
以上是 Python实现不带头结点的单链表 的全部内容， 来源链接： utcz.com/z/387383.html
