数据结构复习一 单链表(python实现)

前言

复习一下数据结构,感觉生疏了,用python重新写一遍吧

正文

单链表的实现

这里由于python变量的特殊性,python变量相当于维护的是一个地址,不像其他语言的的变量一样要事先定义自身的类型,这就使得python实现单链表比较方便,自我感觉。。。。比如在C语言里面设定了int类型的变量,你只能够往里面存放整形数据,而且是直接对应的数据,但是python的变量类型直接是一个地址,就例如 a = 20, 其实这里的a存放的是20这个数的地址, 通过a就可以找到20这个数字了。。这也解释了为什么Python里面可以这样去把两个数调换,比如

1
2
3
a =20 
b = 30
a, b = b , a

下面是单链表实现代码(python 3.5)

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
# -*- coding: utf-8 -*-
# Author:0verWatch

class Node(object):
def __init__(self, elem):
self.elem = elem
self.next = None



class SingleLinklist(object):
def __init__(self, node=None):
self.__head = node #这里用了__来实现一定程度的私有化,因为用户一般不需要知道这个参数的存在


def is_empty(self): #判断是否为空
return (self.__head == None)


def length(self): #获取长度
cur = self.__head #设置游标,类似于C里面的指针
count = 0 #最好设置为0,不然的话下面的条件可能也看情况变化,个人感觉这样好理解
while cur is not None:
count += 1
cur = cur.next
return count



def travel(self): #遍历一遍链表,这个跟获取长度就差不多
cur = self.__head
while cur is not None:
print(cur.elem,end=" ")
cur = cur.next


def add(self,item): #头插法
node = Node(item)
node.next = self.__head
self.__head = node



def append(self,item): #尾插法
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next is not None:
cur = cur.next
cur.next = node



def insert(self, pos, item ): #在某个位置插入数字
if pos < 0:
self.add(item) # 位置小于0的时候默认头插法
elif pos> self.length()-1:
self.append(item) # 位置大于长度,默认尾插法,所以不能使用等于号会误插
else:
pre = self.__head
count = 0
node = Node(item)
while count < pos-1:
count += 1
pre = pre.next
node.next = pre.next
pre.next = node




def remove(self, item): #默认删除一个找到的节点
cur = self.__head
pre = None
while cur is not None:
if cur.elem == item: #找到了的话
#判断是否为头结点
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next


def search(self,item): # 查找元素
cur = self.__head
while cur is not None:
if cur.elem == item:
return True
else:
cur = cur.next

return False


if __name__ == '__main__':
# test_1
lst = SingleLinklist()
print(lst.is_empty())
print(lst.length())

# test_2
lst.append(2)
lst.add(3) # 3 2
lst.insert(1, 5) # 3 1 5 2
lst.add(4) # 4 3 5 2
lst.append(6) # 4 3 5 2 6
print(lst.search(5))
lst.travel()


# test_3
lst.remove(5)
lst.remove(4)
lst.remove(6)
lst.travel()

小结

总体感觉在写单链表的时候要注意几个问题,注意要多考虑一下几种典型的情况,比如空链表,只有一个节点的时候,或者是最后一个节点的情况等等。。。第二的话还是要注意一下变量的赋值,这东西很容易写着写着脑子就抽了,然后就会出现溢出的情况额。。。


听说,打赏我的人最后都成了大佬。



文章目录
  1. 1. 前言
  2. 2. 正文
    1. 2.1. 单链表的实现
  3. 3. 小结