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

admin

题目：创建一个链表。
0 r7 [3 U, f2 x! N% a程序分析：原文不太靠谱。

1. class Node:
   
2. 
   6 C$ C! w3 {: c, K, e2 p
3.     def __init__(self, data):
   6 e, \+ @% ^8 Z( R' l
4.         self.data = data
   
5.         self.next = None
   
6. 
   9 K+ M9 M6 ~7 x' n
7.     def get_data(self):
   
8.         return self.data
   # ?/ B3 L  S6 N" c8 S
9. 
   
10. class List:
      \; `7 q8 O, {# t% d0 ^# I
11. 
    
12.     def __init__(self, head):
    
13.         self.head = head
    ' ~; F( @/ `; A8 l( ~
14. 
    7 A4 o# p' J3 ]0 C# x2 F4 ~
15.     def is_empty(self):
    ; K7 ]! U# J+ u
16.         return self.get_len() == 0
    . S; S. a% F3 \+ \/ R# H
17. 
    6 ]" J/ n+ f# F5 R$ o- T* b1 [7 `
18.     def get_len(self):  
    / c# ]% M8 S6 c5 Y' T% X: g' J
19.         length = 0
    
20.         temp = self.head
    
21.         while temp is not None:
    
22.             length += 1
    
23.             temp = temp.next
    9 j' Y% o3 |9 @( V1 H7 x3 _% @
24.         return length
    + L5 A7 \! ^( E0 z
25. 
    6 O3 `9 C# D/ V+ T
26.     def append(self, node):
    / v/ @  \9 [( {
27.         temp = self.head
    
28.         while temp.next is not None:
    3 v3 B" P! r+ y- o, y8 l5 J- q
29.             temp = temp.next
    
30.         temp.next = node
    
31. 
    
32.     def delete(self, index):
    
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    9 B! v! j, ~& |! G" |& D. J, j8 ?
35.             return
    
36.         if index == 1:
    % x: D0 l( C2 J* S" E3 e/ K* r
37.             self.head = self.head.next
    
38.             return
    
39.         temp = self.head
    
40.         cur_pos = 0
    3 T: t8 q+ B0 H" V; E* S: _
41.         while temp is not None:
    * u3 A- W3 v0 ]  @7 O
42.             cur_pos += 1
    . m) ?" m1 B0 `' z- f3 G6 {
43.             if cur_pos == index-1:
    
44.                 temp.next = temp.next.next
    
45.             temp = temp.next
    : Z' d$ e2 d6 b( b- N
46. 
    
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    
49.             print("插入结点位置不合理")
    1 ], s4 v( _* V- [, I/ x( I2 d9 i8 S
50.             return
    
51.         temp = self.head
    
52.         cur_pos = 0
    $ ~3 l* B* L0 H3 W6 [
53.         while temp is not Node:
    + H7 E! ]  c% `  I' R( A$ m
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    ' F% y% Z: C$ p! \( Y8 R4 r7 p
57.                 temp.next =node
    & E3 }, r) K2 Y, ~. k. n6 m4 [
58.                 break
    
59.             temp = temp.next
    ) ^$ x! g6 o8 J! I0 `! t
60. 
    5 n. l- U& z- |0 i3 h+ a* U
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    9 i* f2 l- V3 [( C' i+ i
63.             return head
    7 H" e8 Z5 y. O  s+ n9 b% r
64.         pre = head
    9 N2 u* I( S$ d3 D: B7 C( U
65.         cur = head.next
    
66.         while cur is not None:
    
67.             temp = cur.next
    % H6 v' w: [7 M
68.             cur.next = pre
    2 {' y1 Z" n- o% X. @( T/ H
69.             pre = cur
    ; q' U2 z; d5 i4 ]
70.             cur = temp
    
71.         head.next = None
    
72.         return pre
    ( m7 Z3 G9 E) y& e  y7 c6 y. p- r
73. 
    4 z  q' P; s( l# G/ G( @
74.     def print_list(self, head):
    
75.         init_data = []
    
76.         while head is not None:
    " K/ M- m) x) p# A$ r
77.             init_data.append(head.get_data())
    3 a4 ^# l% T* h& ]
78.             head = head.next
    
79.         return init_data
    
80. 
    
81. if __name__=='__main__':
    0 y9 b) M' Z2 S' L
82.     head=Node('head')
    
83.     link=List(head)
    
84.     for i in range(10):
    
85.         node=Node(i)
    
86.         link.append(node)
    ( _- j# ?- W7 D0 g
87.     print(link.print_list(head))

复制代码