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

admin

题目：创建一个链表。
* v  P" t+ P  Z& p程序分析：原文不太靠谱。
5 U+ c% ?9 i+ V

1. class Node:
   
2. 
   
3.     def __init__(self, data):
   
4.         self.data = data
   
5.         self.next = None
     q, I: q2 p7 x6 T! ^
6. 
   
7.     def get_data(self):
   
8.         return self.data
   
9. 
   " K1 j% \( C/ o5 z* H) d* \
10. class List:
    
11. 
    ! N  I  n' _. T" T2 s& h
12.     def __init__(self, head):
    
13.         self.head = head
    
14. 
      D) @4 ]- ^/ r  D
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    
17. 
    7 W) @% B2 h" h
18.     def get_len(self):  
    1 G: P+ m8 g1 L/ Y1 i. J
19.         length = 0
    
20.         temp = self.head
    & }' d% s- k9 L. D" z
21.         while temp is not None:
    $ Q. a- R$ I- H) S2 E4 ]
22.             length += 1
    
23.             temp = temp.next
    
24.         return length
    # }' l1 R* Y7 W
25. 
    
26.     def append(self, node):
    
27.         temp = self.head
    
28.         while temp.next is not None:
    9 v3 n; ~- W* J3 _" Y, M; r# z
29.             temp = temp.next
    
30.         temp.next = node
    ! u2 T; m2 _. c8 G6 j' ?6 m
31. 
    9 X* e) ?8 A, ?
32.     def delete(self, index):
    
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    - W2 r/ M/ l5 y4 A: Y. X( o
35.             return
    
36.         if index == 1:
    7 l( I' ]  u, G; E+ P- J0 V
37.             self.head = self.head.next
    6 h3 i/ ^' }0 f0 L& ]) x3 e
38.             return
    
39.         temp = self.head
    
40.         cur_pos = 0
    
41.         while temp is not None:
    4 f+ _. M1 W6 Z. a: _
42.             cur_pos += 1
    & `3 Y' f3 j. X& M5 o/ M
43.             if cur_pos == index-1:
    3 V3 D& z" Y4 u3 y- p; z1 O2 Z
44.                 temp.next = temp.next.next
    , N$ z6 M0 D- }5 K# W8 w
45.             temp = temp.next
    
46. 
    ' G( x3 ~$ {/ M, H8 A8 A# y
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    
49.             print("插入结点位置不合理")
    
50.             return
    
51.         temp = self.head
    9 w# r  |* |9 ~9 m3 a
52.         cur_pos = 0
    ( \/ x( z1 q9 K, n. @: s
53.         while temp is not Node:
    % z+ H6 P5 ]! B6 b4 Z
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    ' |% x7 k: D9 y9 v: x# f1 h
57.                 temp.next =node
    , d6 \2 t* F/ v) X! H+ J' {
58.                 break
    0 Q6 Q8 x: @2 L7 [! V# {
59.             temp = temp.next
    * D7 J+ \6 U. H; \- V( f
60. 
    
61.     def reverse(self, head):
    0 R) ~& v1 A0 s: i' Q. j
62.         if head is None and head.next is None:
    : D  U2 b5 e' _0 P  |5 G
63.             return head
    % L. E* J9 v. ?# \7 i1 O2 x9 }
64.         pre = head
    
65.         cur = head.next
    5 f- V$ |/ ~" u/ f" k
66.         while cur is not None:
    
67.             temp = cur.next
    . n: r: p( T( M' O- t( u9 Z
68.             cur.next = pre
    
69.             pre = cur
    
70.             cur = temp
    ; _6 x) d& k% f) `% e: k: H1 W( N
71.         head.next = None
      m+ L5 F: ^2 w; \- `3 Y
72.         return pre
    
73. 
    6 y3 `4 B1 u+ y
74.     def print_list(self, head):
    
75.         init_data = []
    
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    
78.             head = head.next
    6 M: [: e" d6 j; Q7 Y
79.         return init_data
    
80. 
    ( L7 y: k8 a" V: C7 w" l8 K
81. if __name__=='__main__':
    & i' }, g+ k& l; W
82.     head=Node('head')
    
83.     link=List(head)
    
84.     for i in range(10):
    
85.         node=Node(i)
    
86.         link.append(node)
    + J7 [5 B: K0 u" {' R( ]) [, _  U
87.     print(link.print_list(head))

复制代码