服务器之家

服务器之家 > 正文

python数据结构之链表详解

时间：2020-12-07 00:40     来源/作者：King_DIG

数据结构是计算机科学必须掌握的一门学问，之前很多的教材都是用C语言实现链表，因为c有指针，可以很方便的控制内存，很方便就实现链表，其他的语言，则没那么方便，有很多都是用模拟链表，不过这次，我不是用模拟链表来实现，因为python是动态语言，可以直接把对象赋值给新的变量。

好了，在说我用python实现前，先简单说说链表吧。在我们存储一大波数据时，我们很多时候是使用数组，但是当我们执行插入操作的时候就是非常麻烦，看下面的例子，有一堆数据1,2,3,5,6,7我们要在3和5之间插入4,如果用数组，我们会怎么做？当然是将5之后的数据往后退一位，然后再插入4,这样非常麻烦，但是如果用链表，我就直接在3和5之间插入4就行，听着就很方便。

那么链表的结构是怎么样的呢？顾名思义，链表当然像锁链一样，由一节节节点连在一起，组成一条数据链。

链表的节点的结构如下：

python数据结构之链表详解

data为自定义的数据，next为下一个节点的地址。

链表的结构为，head保存首位节点的地址：

python数据结构之链表详解

接下来我们来用python实现链表

python实现链表

首先，定义节点类Node：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Node:
  '''
  data: 节点保存的数据
  _next: 保存下一个节点对象
  '''
  def __init__(self, data, pnext=None):
    self.data = data
    self._next = pnext
 
  def __repr__(self):
    '''
    用来定义Node的字符输出，
    print为输出data
    '''
    return str(self.data)

然后，定义链表类：

链表要包括：

属性：

链表头：head

链表长度：length

方法：

判断是否为空: isEmpty()

?
1
2
def isEmpty(self):
  return (self.length == 0

增加一个节点(在链表尾添加): append()

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def append(self, dataOrNode):
  item = None
  if isinstance(dataOrNode, Node):
    item = dataOrNode
  else:
    item = Node(dataOrNode)
 
  if not self.head:
    self.head = item
    self.length += 1
 
  else:
    node = self.head
    while node._next:
      node = node._next
    node._next = item
    self.length += 1

删除一个节点: delete()

?
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
#删除一个节点之后记得要把链表长度减一
def delete(self, index):
  if self.isEmpty():
    print "this chain table is empty."
    return
 
  if index < 0 or index >= self.length:
    print 'error: out of index'
    return
  #要注意删除第一个节点的情况
  #如果有空的头节点就不用这样
  #但是我不喜欢弄头节点
  if index == 0:
    self.head = self.head._next
    self.length -= 1
    return
 
  #prev为保存前导节点
  #node为保存当前节点
  #当j与index相等时就
  #相当于找到要删除的节点
  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
    prev = node
    node = node._next
    j += 1
 
  if j == index:
    prev._next = node._next
    self.length -= 1

修改一个节点: update()

?
1
2
3
4
5
6
7
8
9
10
11
12
def update(self, index, data):
  if self.isEmpty() or index < 0 or index >= self.length:
    print 'error: out of index'
    return
  j = 0
  node = self.head
  while node._next and j < index:
    node = node._next
    j += 1
 
  if j == index:
    node.data = data

查找一个节点: getItem()

?
1
2
3
4
5
6
7
8
9
10
11
def getItem(self, index):
  if self.isEmpty() or index < 0 or index >= self.length:
    print "error: out of index"
    return
  j = 0
  node = self.head
  while node._next and j < index:
    node = node._next
    j += 1
 
  return node.data

查找一个节点的索引: getIndex()

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def getIndex(self, data):
  j = 0
  if self.isEmpty():
    print "this chain table is empty"
    return
  node = self.head
  while node:
    if node.data == data:
      return j
    node = node._next
    j += 1
 
  if j == self.length:
    print "%s not found" % str(data)
    return

插入一个节点: insert()

?
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
def insert(self, index, dataOrNode):
  if self.isEmpty():
    print "this chain tabale is empty"
    return
 
  if index < 0 or index >= self.length:
    print "error: out of index"
    return
 
  item = None
  if isinstance(dataOrNode, Node):
    item = dataOrNode
  else:
    item = Node(dataOrNode)
 
  if index == 0:
    item._next = self.head
    self.head = item
    self.length += 1
    return
 
  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
    prev = node
    node = node._next
    j += 1
 
  if j == index:
    item._next = node
    prev._next = item
    self.length += 1

清空链表: clear()

?
1
2
3
def clear(self):
  self.head = None
  self.length = 0

以上就是链表类的要实现的方法。

执行的结果：

python数据结构之链表详解

python数据结构之链表详解

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
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
# -*- coding:utf8 -*-
#/usr/bin/env python
 
class Node(object):
 def __init__(self, data, pnext = None):
  self.data = data
  self._next = pnext
 
 def __repr__(self):
  return str(self.data)
 
class ChainTable(object):
 def __init__(self):
  self.head = None
  self.length = 0
 
 def isEmpty(self):
  return (self.length == 0)
 
 def append(self, dataOrNode):
  item = None
  if isinstance(dataOrNode, Node):
   item = dataOrNode
  else:
   item = Node(dataOrNode)
 
  if not self.head:
   self.head = item
   self.length += 1
 
  else:
   node = self.head
   while node._next:
    node = node._next
   node._next = item
   self.length += 1
 
 def delete(self, index):
  if self.isEmpty():
   print "this chain table is empty."
   return
 
  if index < 0 or index >= self.length:
   print 'error: out of index'
   return
 
  if index == 0:
   self.head = self.head._next
   self.length -= 1
   return
 
  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
   prev = node
   node = node._next
   j += 1
 
  if j == index:
   prev._next = node._next
   self.length -= 1
 
 def insert(self, index, dataOrNode):
  if self.isEmpty():
   print "this chain tabale is empty"
   return
 
  if index < 0 or index >= self.length:
   print "error: out of index"
   return
 
  item = None
  if isinstance(dataOrNode, Node):
   item = dataOrNode
  else:
   item = Node(dataOrNode)
 
  if index == 0:
   item._next = self.head
   self.head = item
   self.length += 1
   return
 
  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
   prev = node
   node = node._next
   j += 1
 
  if j == index:
   item._next = node
   prev._next = item
   self.length += 1
 
 def update(self, index, data):
  if self.isEmpty() or index < 0 or index >= self.length:
   print 'error: out of index'
   return
  j = 0
  node = self.head
  while node._next and j < index:
   node = node._next
   j += 1
 
  if j == index:
   node.data = data
 
 def getItem(self, index):
  if self.isEmpty() or index < 0 or index >= self.length:
   print "error: out of index"
   return
  j = 0
  node = self.head
  while node._next and j < index:
   node = node._next
   j += 1
 
  return node.data
 
 
 def getIndex(self, data):
  j = 0
  if self.isEmpty():
   print "this chain table is empty"
   return
  node = self.head
  while node:
   if node.data == data:
    return j
   node = node._next
   j += 1
 
  if j == self.length:
   print "%s not found" % str(data)
   return
 
 def clear(self):
  self.head = None
  self.length = 0
 
 def __repr__(self):
  if self.isEmpty():
   return "empty chain table"
  node = self.head
  nlist = ''
  while node:
   nlist += str(node.data) + ' '
   node = node._next
  return nlist
 
 def __getitem__(self, ind):
  if self.isEmpty() or ind < 0 or ind >= self.length:
   print "error: out of index"
   return
  return self.getItem(ind)
 
 def __setitem__(self, ind, val):
  if self.isEmpty() or ind < 0 or ind >= self.length:
   print "error: out of index"
   return
  self.update(ind, val)
 
 def __len__(self):
  return self.length

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。

原文链接：http://www.cnblogs.com/king-ding/p/pythonchaintable.html

标签：
Python 链表 数据结构 

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解，亲测可用！！！
Intellij idea2020永久破解，亲测可用！！！ 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
返回顶部