python实现链表

心愉所想 發表於 2021-11-8 22:21:00

链表
链表是计算机的一种数据结构，是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
<img src="https://img2020.cnblogs.com/blog/2554219/202111/2554219-20211108204659899-1500284596.png">
如上图，一个简单的单向链表。可见节点由数据和指针构成。
 
在python中没有指针，我们要用引用来代替指针，下文用指针来说，但是在这不是指针，是引用。
<div class="cnblogs_code">
<pre>1 class node():
2 def __init__(self,data=0,next=None):
3 self.data=data
4 self.next=next</pre>
</div>
如上图，创建了节点
 
 
之后我们要让节点连起来，组成链表
<div class="cnblogs_code">
<pre>1 class linklist():
2 def __init__(self):
3 self.head=None
4 self.len=0</pre>
</div>
在链表中，头结点很重要，一般会从头结点开始遍历链表
 
 
参考了一些其他的博客，总结得出，我们对链表主要有以下的操作：
1.在链表尾添加节点
2.在链表中插入节点
3.在链表中删除节点
4.在链表中搜索节点
5.在链表中修改节点
6.遍历输出链表数据
 
1.在链表尾添加节点（和数组中append（）函数作用相同）
思路：找到尾节点，让尾结点next的指针为新节点
　　    如果链表为空，直接添加新节点
<div class="cnblogs_code">
<pre> 1 def append_node(self,data):
 2 newnode=node(data,None)
 3 temp=self.head
 4 if self.head==None:
 5 self.head=newnode
 6 else :
 7 while temp.next!=None:
 8 temp=temp.next
 9 temp.next=newnode
10 self.len+=1</pre>
</div>
2.在链表中插入节点
思路：新节点指向插入位置的节点，插入位置前一个节点指向新节点。如果插入到首位，只用执行前半句
<div class="cnblogs_code">
<pre> 1 def insert(self,number,newdata):
 2 temp = self.head
 3 j = 0
 4 newnode=node(newdata)
 5 if self.len < number:
 6 print("error")
 7 else:
 8 while j < number-1:
 9 temp = temp.next
10 j += 1
11 newnode.next=temp.next
12 temp.next=newnode
13 self.len+=1</pre>
</div>
3.在链表中删除节点
思路：让删除节点前节点指向删除节点指向的节点，清除删除节点所占用的内存。（在python中不会内存管理，第二句就不执行了）
<div class="cnblogs_code">
<pre> 1 def del_node(self,number):#首项为0
 2 temp=self.head
 3 j=0
 4 if self.len<number:
 5 print("error")
 6 else:
 7 while j<number-1:
 8 temp = temp.next
 9 j+=1
10 temp.next=temp.next.next
11 self.len-=1</pre>
</div>
4.在链表中搜索节点
思路：从头结点开始遍历链表。
<div class="cnblogs_code">
<pre>1 def search_node(self,data):
2 temp = self.head
3 j = 0
4 while temp.next!=None:
5 temp = temp.next
6 j += 1
7 if temp.data==data:
8 break
9 return j</pre>
</div>
5.在链表中修改节点
思路：从头结点开始遍历链表，找到目标节点后修改其数据。
<div class="cnblogs_code">
<pre> 1 def change_data(self,number,newdata):
 2 temp = self.head
 3 j = 0
 4 if self.len < number:
 5 print("error")
 6 else:
 7 while j < number:
 8 temp = temp.next
 9 j += 1
10 temp.data=newdata</pre>
</div>
6.遍历输出链表数据
思路：从头结点开始遍历链表并输出数据。
<div class="cnblogs_code">
<pre>1 def print_list(self):
2 temp=self.head
3 while temp.next!=None:
4 print(temp.data,"-> ",end="")
5 temp=temp.next
6 print(temp.data)</pre>
</div>
完整代码，有需要请自取：
<div class="cnblogs_code">
<pre> 1 class node():
 2 def __init__(self,data=0,next=None):
 3 self.data=data
 4 self.next=next
 5
 6 class linklist():
 7 def __init__(self):
 8 self.head=None
 9 self.len=0
10
11 def append_node(self,data):
12 newnode=node(data,None)
13 temp=self.head
14 if self.head==None:
15 self.head=newnode
16 else :
17 while temp.next!=None:
18 temp=temp.next
19 temp.next=newnode
20 self.len+=1
21
22 def print_list(self):
23 temp=self.head
24 while temp.next!=None:
25 print(temp.data,"-> ",end="")
26 temp=temp.next
27 print(temp.data)
28
29 def del_node(self,number):#首项为0
30 temp=self.head
31 j=0
32 if self.len<number:
33 print("error")
34 else:
35 while j<number-1:
36 temp = temp.next
37 j+=1
38 temp.next=temp.next.next
39 self.len-=1
40
41 def search_node(self,data):
42 temp = self.head
43 j = 0
44 while temp.next!=None:
45 temp = temp.next
46 j += 1
47 if temp.data==data:
48 break
49 return j
50
51 def change_data(self,number,newdata):
52 temp = self.head
53 j = 0
54 if self.len < number:
55 print("error")
56 else:
57 while j < number:
58 temp = temp.next
59 j += 1
60 temp.data=newdata
61
62 def insert(self,number,newdata):
63 temp = self.head
64 j = 0
65 newnode=node(newdata)
66 if self.len < number:
67 print("error")
68 else:
69 while j < number-1:
70 temp = temp.next
71 j += 1
72 newnode.next=temp.next
73 temp.next=newnode
74 self.len+=1
75
76 a=linklist()
77 for i in range (0,10):
78 a.append_node(i)
79 print("append_node:",end="")
80 a.print_list()
81 print("del_node(2):",end="")
82 a.del_node(2)
83 a.print_list()
84 print("search_node(5):",end="")
85 print(a.search_node(5))
86 print("change_data(4,999):",end="")
87 a.change_data(4,999)
88 a.print_list()
89 print("a.insert(4,19909)):",end="")
90 a.insert(4,19909)
91 a.print_list()</pre>
</div>
  
来源：https://www.cnblogs.com/guozhangyang/p/15526189.html

頁: [1]

琼殿技术论坛's Archiver

python实现链表