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

admin

题目：创建一个链表。
+ h+ [) A1 |  @- J) `程序分析：原文不太靠谱。
  O4 P- f6 t- k; [: P

1. class Node:
   
2. 
   / S) W" R' z" \7 b, C8 r6 N6 v
3.     def __init__(self, data):
   ! B$ E' {6 \% R# h! t
4.         self.data = data
   
5.         self.next = None
   ; h. t1 Y3 x9 N% M8 [5 t
6. 
   ! _% d0 _: F3 n2 U& m& T
7.     def get_data(self):
   8 y2 S: E* Y0 r( l0 N; Z% ]) g
8.         return self.data
   : c5 o$ d- Y3 I$ _+ V. I1 ~& n
9. 
   4 K1 ~# I6 B. ?0 }
10. class List:
    * Y* n& D3 K; c
11. 
    
12.     def __init__(self, head):
    # G/ U3 k* j* z
13.         self.head = head
    
14. 
    
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    3 d+ I+ C, s; W8 U$ M' D
17. 
    
18.     def get_len(self):  
    4 x' ]- k; l& q3 R( r8 ^
19.         length = 0
    + m7 N, \2 @3 K& d- c1 }
20.         temp = self.head
    % T3 A; Y& H" @' L" ^, X5 l6 h
21.         while temp is not None:
    
22.             length += 1
      c) s# t/ R! p5 g; P8 c5 h; k
23.             temp = temp.next
    
24.         return length
    
25. 
    
26.     def append(self, node):
    6 H- C. A: w$ }4 |+ x- T+ ?' D  A
27.         temp = self.head
    2 F& k! y6 f$ E+ a
28.         while temp.next is not None:
    6 O9 y! j1 G0 D2 |, n- s
29.             temp = temp.next
    
30.         temp.next = node
    
31. 
    
32.     def delete(self, index):
    
33.         if index < 1 or index > self.get_len():
    1 K; r; ]& A5 k. n0 C7 C
34.             print("给定位置不合理")
    
35.             return
    
36.         if index == 1:
    
37.             self.head = self.head.next
    
38.             return
    ! N( b% e4 k% P  f
39.         temp = self.head
    
40.         cur_pos = 0
    4 Y% C* {  D! [3 [+ b/ c) T6 h6 G
41.         while temp is not None:
    
42.             cur_pos += 1
    & p8 r6 _% S2 j  G
43.             if cur_pos == index-1:
    
44.                 temp.next = temp.next.next
    
45.             temp = temp.next
    ) K4 q/ U# T% a* {; R
46. 
    . C- ~( h) C0 L$ G1 L" q% n6 H1 S
47.     def insert(self, pos, node):
      B1 }  _0 Q! V8 d2 h/ q# h
48.         if pos < 1 or pos > self.get_len():
    
49.             print("插入结点位置不合理")
    
50.             return
    + k* T8 N" y3 c) m! g( s' R* _
51.         temp = self.head
    
52.         cur_pos = 0
      ~7 j" {5 }/ e* L
53.         while temp is not Node:
    " O5 _" M  V$ h9 h  C9 e! S& k
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    
57.                 temp.next =node
    - u) R9 ^  X1 j6 g7 O2 ]8 [
58.                 break
    3 E; j' |1 K: j' ?" H7 b
59.             temp = temp.next
    
60. 
    ' s$ l2 E' V. h3 _# Y
61.     def reverse(self, head):
    / w( M! |- I9 C- }' E1 u
62.         if head is None and head.next is None:
    % C2 i6 k9 r3 y) t- v
63.             return head
    
64.         pre = head
    
65.         cur = head.next
    
66.         while cur is not None:
    
67.             temp = cur.next
    
68.             cur.next = pre
    
69.             pre = cur
    , S" d9 T) S: w# D, i
70.             cur = temp
    
71.         head.next = None
    9 b3 i! V8 v4 g9 A
72.         return pre
    * r/ D% @, O6 E  A4 N
73. 
    ! n7 y% P' W& I
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
    
79.         return init_data
    ! y' N- X& P# |* Z& S" i# Z$ v2 R
80. 
    
81. if __name__=='__main__':
    5 a! R1 Q2 m) ~; w6 j5 y
82.     head=Node('head')
    
83.     link=List(head)
    
84.     for i in range(10):
    
85.         node=Node(i)
    
86.         link.append(node)
    
87.     print(link.print_list(head))

复制代码