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

admin

题目：创建一个链表。
程序分析：原文不太靠谱。

1. class Node:
   3 _1 B+ T7 A+ J2 m
2. 
   
3.     def __init__(self, data):
   
4.         self.data = data
   
5.         self.next = None
   & k7 Y! u$ O4 |2 I; B& \1 y
6. 
   
7.     def get_data(self):
   " y7 ^. P( ]$ E* ?; V) V
8.         return self.data
   
9. 
   8 N5 W4 G" h" _7 ?$ Z& s9 H* e
10. class List:
    
11. 
    & D. X) x% [+ L' L. R  f
12.     def __init__(self, head):
    
13.         self.head = head
    " ~% l9 R. z8 k* U- h+ o: @) @
14. 
    0 ?  c+ h1 K, P. R2 G
15.     def is_empty(self):
    , [$ _/ H5 l' ]0 ^- j
16.         return self.get_len() == 0
    ) z7 o9 O3 c1 w  j% i4 P
17. 
    4 s( p) x9 C% ?$ U& K; H+ ~* y
18.     def get_len(self):  
    ' k9 `1 ^; l; |# e- g- @) ~
19.         length = 0
    ! I, J  N5 B- E1 ~5 i6 x3 N
20.         temp = self.head
    
21.         while temp is not None:
    
22.             length += 1
    
23.             temp = temp.next
    ( j- V# ~' f5 e1 {; P* r' j/ T
24.         return length
      u( d7 w: w5 L$ E
25. 
    
26.     def append(self, node):
    $ F1 f% y) T" |: P
27.         temp = self.head
    ) v$ G, o4 h& g% j
28.         while temp.next is not None:
    # ]. s: ?3 v$ g8 P0 N0 [  F
29.             temp = temp.next
    ! c4 i. F2 h8 Z' L
30.         temp.next = node
    6 h/ p; P! }- R
31. 
    
32.     def delete(self, index):
    5 J4 |4 K4 I0 X; w% j
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    
35.             return
    
36.         if index == 1:
    
37.             self.head = self.head.next
    
38.             return
    # I% M# n6 |7 a, p
39.         temp = self.head
    " o4 K3 f5 u) R
40.         cur_pos = 0
    
41.         while temp is not None:
    $ i$ @0 O( m  u* q6 t. v3 t
42.             cur_pos += 1
    
43.             if cur_pos == index-1:
    ; T5 D! Z( E$ t: U& ^
44.                 temp.next = temp.next.next
    - @7 W: L+ m: t+ W
45.             temp = temp.next
    
46. 
    5 g8 Y# @- Y- `; S0 d( B& {
47.     def insert(self, pos, node):
    & g; m3 U. |' g" G! d  b! ~% m, |+ L% N
48.         if pos < 1 or pos > self.get_len():
    ' O' W  w! l+ Z
49.             print("插入结点位置不合理")
    
50.             return
    . |' y$ C5 u  L! u" @3 F. p
51.         temp = self.head
    % {! p& }: Q% A% d0 a
52.         cur_pos = 0
    * f( B) q7 g& R& W% z  M
53.         while temp is not Node:
    ! l6 _; H" N, n! W* k4 q
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    - z/ z0 a! y# z# p2 O
56.                 node.next = temp.next
    
57.                 temp.next =node
    
58.                 break
    
59.             temp = temp.next
    
60. 
    ; W7 i  D" ^  q  p4 D* `8 V
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    % N$ {3 M( ~! E$ a. T4 o7 Q
63.             return head
    % {3 y: ^! C7 O' F" n
64.         pre = head
    
65.         cur = head.next
    ; u# ~: f% M9 M7 ^
66.         while cur is not None:
    
67.             temp = cur.next
    2 g' `+ n* B; [( C2 |2 K
68.             cur.next = pre
    7 `1 [6 f( ]$ g7 d) _" B( B0 n2 N
69.             pre = cur
    3 I1 }, {/ W% K
70.             cur = temp
    
71.         head.next = None
    - X( L3 Q' d& z% k# ]( f  W
72.         return pre
    
73. 
    ! ?/ K6 t6 X- k  c
74.     def print_list(self, head):
    
75.         init_data = []
    
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    8 G1 ~3 j9 e2 M+ h4 E& I9 C
78.             head = head.next
    $ N8 P7 N, H& z2 f6 b3 @/ w
79.         return init_data
    7 ^/ N- ~7 D9 k' x0 H6 G
80. 
    
81. if __name__=='__main__':
    0 J: B  L+ g* {! H* m) u$ b
82.     head=Node('head')
    
83.     link=List(head)
    ) [) s9 D& o" o  \+ u! [" ?
84.     for i in range(10):
      s( _- A% Z: v5 F+ M. Y/ ^
85.         node=Node(i)
    5 b$ F6 P" R- B1 D% Y; M8 v
86.         link.append(node)
    
87.     print(link.print_list(head))

复制代码