7932 - [D]实例072：创建链表

admin

题目：创建一个链表。
& Z4 [7 U0 I3 p: I( v# g; D程序分析：原文不太靠谱。

1. class Node:
   
2. 
   1 G+ ]+ S7 R6 k2 K% u
3.     def __init__(self, data):
   
4.         self.data = data
   , C- l: k. R/ o' B( Y  }8 G
5.         self.next = None
   . _" T7 p7 d' e3 a# ]  u* ]
6. 
   6 N- W5 G4 H. [3 q1 Z
7.     def get_data(self):
   6 L" v/ k+ e4 S5 _
8.         return self.data
   
9. 
   1 s. z$ u0 T  `* m# g* X
10. class List:
    5 F/ }) J0 m. L) `4 X: r4 L
11. 
    
12.     def __init__(self, head):
    
13.         self.head = head
    
14. 
    
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    * u9 @0 Q6 X( ]; r! L
17. 
    6 _, h2 e5 Z( {7 E1 K
18.     def get_len(self):  
    ' j2 o6 f, i9 U$ I0 [
19.         length = 0
    
20.         temp = self.head
    8 U9 [5 o; f1 T1 ]' G3 J( ~
21.         while temp is not None:
    0 Y9 m: b/ a: E8 k, w! N8 v, c
22.             length += 1
    - J" D. d- M1 e3 |# Q4 I
23.             temp = temp.next
    5 e/ ]2 h; `) q
24.         return length
    
25. 
    
26.     def append(self, node):
    4 }1 ^1 {7 F$ D: }2 m
27.         temp = self.head
    
28.         while temp.next is not None:
    * k( [# ^8 J( V2 l- @: e" X9 ~
29.             temp = temp.next
    
30.         temp.next = node
    
31. 
    : j( N1 L! {. p* y# |) p2 V% _
32.     def delete(self, index):
    ) b' ]! C0 Y* m9 r+ ?0 Z
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    
35.             return
    
36.         if index == 1:
    . j# U3 S" H3 x+ K. y7 F
37.             self.head = self.head.next
    
38.             return
    
39.         temp = self.head
    
40.         cur_pos = 0
    ! H# g9 G0 O: \: ^+ |/ @
41.         while temp is not None:
    . K8 v6 b# \7 v) j/ G1 s4 ^
42.             cur_pos += 1
    
43.             if cur_pos == index-1:
    " z* E- C1 E. u' X" M3 m& O
44.                 temp.next = temp.next.next
    
45.             temp = temp.next
    + K! @& E" M& ]
46. 
    
47.     def insert(self, pos, node):
    6 U2 C. G/ @; `
48.         if pos < 1 or pos > self.get_len():
    
49.             print("插入结点位置不合理")
    
50.             return
    
51.         temp = self.head
    + h4 }0 L' x1 F" J; k7 h
52.         cur_pos = 0
    
53.         while temp is not Node:
    
54.             cur_pos += 1
      O" p  R2 ^9 _; n, P2 h. P
55.             if cur_pos == pos-1:
    8 }/ a& w3 r* G# t# E0 f
56.                 node.next = temp.next
    
57.                 temp.next =node
    
58.                 break
    
59.             temp = temp.next
    
60. 
    - F% u' c0 S9 F2 V% N/ r* O
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    
63.             return head
    
64.         pre = head
    
65.         cur = head.next
    
66.         while cur is not None:
    
67.             temp = cur.next
    
68.             cur.next = pre
    5 m+ n3 Q; N4 }1 }( @
69.             pre = cur
    * y6 ~( c* D1 c% e' g, r, k! P' ^
70.             cur = temp
    ! p3 O6 [: ^$ [% t
71.         head.next = None
      G! R( m+ N  K. i( C
72.         return pre
    3 s. w. n5 N) U4 v
73. 
    
74.     def print_list(self, head):
    
75.         init_data = []
    1 Y! E. V. j, t/ p3 B, p
76.         while head is not None:
    . X" V4 g- T  O4 j
77.             init_data.append(head.get_data())
    
78.             head = head.next
    * o9 Q- e& F5 x) g9 `
79.         return init_data
    + W2 o" N/ v- U% G& r, n# w
80. 
    8 r$ Z; g$ H( j0 Y' v7 f% q
81. if __name__=='__main__':
    
82.     head=Node('head')
    ! {& m9 I4 E( x
83.     link=List(head)
    
84.     for i in range(10):
      I" n+ U2 |  f# Q
85.         node=Node(i)
    
86.         link.append(node)
    
87.     print(link.print_list(head))

复制代码