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

admin

题目：创建一个链表。
程序分析：原文不太靠谱。
% }2 J" t; n7 W# E, \7 v5 S

1. class Node:
   3 m  n! {9 R5 R6 Q/ I; l% y
2. 
   $ y' h5 Z: l% T. j7 g
3.     def __init__(self, data):
   
4.         self.data = data
   
5.         self.next = None
   
6. 
   # x2 @. j) D/ q
7.     def get_data(self):
   ) W: y. L1 u1 f. H: M
8.         return self.data
   
9. 
   1 I2 L6 W4 u! B2 o+ g  A$ Z7 f
10. class List:
    
11. 
    
12.     def __init__(self, head):
    , A0 s) N! E4 s0 @3 n  A
13.         self.head = head
    0 I: a( r6 b0 i, x
14. 
    
15.     def is_empty(self):
    # n6 C" w+ [, t; E8 O- h0 W& ~
16.         return self.get_len() == 0
    - ^2 t4 s" R. I
17. 
    / Y: w. v# P8 U! _. ?! X
18.     def get_len(self):  
    
19.         length = 0
    / F) L/ x6 _4 \
20.         temp = self.head
    2 y- z" M  o5 l  A) j+ M+ X
21.         while temp is not None:
    ! x9 `3 r3 c1 Q( f/ A$ X* x$ \
22.             length += 1
    . k& r9 `, Q( k4 J% m" D
23.             temp = temp.next
    
24.         return length
    + `0 _' R" u* e4 A  u
25. 
    
26.     def append(self, node):
    - i& L8 F3 P: ]$ P4 b: o1 y6 u% `
27.         temp = self.head
    
28.         while temp.next is not None:
      m- p0 ~) B0 F4 @$ [
29.             temp = temp.next
    
30.         temp.next = node
    
31. 
    
32.     def delete(self, index):
    3 |5 Q0 F* k: s* Y; [0 `  X# G$ {
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    
35.             return
    
36.         if index == 1:
    * y6 s) _) I/ r4 r" y
37.             self.head = self.head.next
    
38.             return
    ' A' ~7 O! ^8 L! a  ?
39.         temp = self.head
    
40.         cur_pos = 0
    % y% X" g6 {) N0 D9 B
41.         while temp is not None:
    
42.             cur_pos += 1
    : e0 x* G, H8 R/ k, y1 p% ]
43.             if cur_pos == index-1:
    0 y6 @: b7 q. o) h5 }8 U( }, [
44.                 temp.next = temp.next.next
    " `& V3 J* O( n+ T! I  L% n3 r
45.             temp = temp.next
    ' C' L. J7 o, K- Q+ p
46. 
    
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    
49.             print("插入结点位置不合理")
    
50.             return
    
51.         temp = self.head
    5 u2 v; K+ X1 h) \" A* |
52.         cur_pos = 0
    
53.         while temp is not Node:
    
54.             cur_pos += 1
    4 Q. D+ S% W* p1 D7 D
55.             if cur_pos == pos-1:
    4 N9 l- j) y% |  ]7 Z: [6 {' D0 ~
56.                 node.next = temp.next
    
57.                 temp.next =node
    
58.                 break
    
59.             temp = temp.next
    
60. 
    5 D0 H: N; I6 P
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    . j% y/ K; R; d
63.             return head
    
64.         pre = head
    1 X, t' i- n. |, Q( }" V  V8 g9 l
65.         cur = head.next
    
66.         while cur is not None:
    : F9 H- W1 _5 _5 m
67.             temp = cur.next
    
68.             cur.next = pre
    2 t7 A0 l+ d! f( m
69.             pre = cur
    
70.             cur = temp
    
71.         head.next = None
    . \# ?  X& z: X/ m2 |, T5 K
72.         return pre
    
73. 
    7 M7 d- M; w4 M9 d! ]1 M
74.     def print_list(self, head):
    3 f, M1 u7 t/ M( W
75.         init_data = []
    1 r: @2 B' S4 j) J3 @# z' e; c2 G+ s
76.         while head is not None:
    0 I7 W1 a$ K8 A- K5 ^, m9 ?  I
77.             init_data.append(head.get_data())
    
78.             head = head.next
    ) |2 P5 e4 ^" u. C' N0 @
79.         return init_data
    - h! I4 c( i5 V1 ]4 d- k
80. 
    
81. if __name__=='__main__':
    , @) G2 L6 l7 k7 |3 d* D$ @
82.     head=Node('head')
    
83.     link=List(head)
    
84.     for i in range(10):
    2 b# ~) _0 w+ {0 z" M0 V
85.         node=Node(i)
    / n  g" E3 P$ W
86.         link.append(node)
    
87.     print(link.print_list(head))

复制代码