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

admin

题目：创建一个链表。
程序分析：原文不太靠谱。
/ v5 ~+ @: t0 z9 \

1. class Node:
   
2. 
   ! Y$ C4 i. R/ u( A6 |
3.     def __init__(self, data):
   2 g' F1 o5 E- h, Z1 y
4.         self.data = data
   
5.         self.next = None
   
6. 
   
7.     def get_data(self):
   
8.         return self.data
     v0 P5 t: v5 D" J/ X! |
9. 
   4 T  ~; J; y( ?, J; N
10. class List:
    6 U; d$ q; q+ p5 d
11. 
    ' \3 E% i% q! b8 ~$ }  b% @5 ^
12.     def __init__(self, head):
    ! z) `5 l* y! ?! z: o
13.         self.head = head
    ( {' q: ^3 W' L  |; z+ X. _: V
14. 
    
15.     def is_empty(self):
    - o/ X/ c# n+ R& |
16.         return self.get_len() == 0
    
17. 
    3 \8 S4 X+ u8 S- f1 V9 @+ g* j8 ~2 M
18.     def get_len(self):  
    
19.         length = 0
    
20.         temp = self.head
    ) V( B# [2 C1 @, A4 r" e
21.         while temp is not None:
    
22.             length += 1
    
23.             temp = temp.next
    7 Y& s# U. l9 _; }- n
24.         return length
      f- ?" ~2 v( A* p. h$ E8 Z/ P
25. 
    ( v+ O( p0 W  E
26.     def append(self, node):
    & X2 ^/ X4 r1 c, v
27.         temp = self.head
      u2 ?: T/ a7 C2 n
28.         while temp.next is not None:
    4 a- l8 C, s4 S& u+ [5 E  n0 v: N
29.             temp = temp.next
    
30.         temp.next = node
    
31. 
    3 ?) @7 V$ [! O$ Z6 E
32.     def delete(self, index):
    4 _; K4 p, ]) {0 b( t* o0 g
33.         if index < 1 or index > self.get_len():
    4 M" M7 k7 {: E9 q2 A* D! a# H
34.             print("给定位置不合理")
    
35.             return
    # U, K: N  \  [) ~- d$ G7 X  u
36.         if index == 1:
    
37.             self.head = self.head.next
    
38.             return
    6 g& a; D. Y! g. e
39.         temp = self.head
    9 ]9 y5 S8 g* Z. P+ E  U4 ?0 y
40.         cur_pos = 0
    9 C0 M" q  `6 L
41.         while temp is not None:
    4 q' z1 V; p0 F+ p
42.             cur_pos += 1
    
43.             if cur_pos == index-1:
    , ]& K0 E6 m4 `4 ^" c* b; }
44.                 temp.next = temp.next.next
    
45.             temp = temp.next
    
46. 
    
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    2 F7 P' k7 B+ \( z3 O4 x
49.             print("插入结点位置不合理")
    - [' t; o  i; o0 B! X
50.             return
    
51.         temp = self.head
    $ {  S2 z/ u, i
52.         cur_pos = 0
    
53.         while temp is not Node:
    
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    ! d( `$ H8 x3 J+ j
57.                 temp.next =node
    ; ]/ K% d6 c  N- ~9 |1 U+ w
58.                 break
    
59.             temp = temp.next
    
60. 
    6 q. g9 l( c2 m2 J6 q9 E" m4 z
61.     def reverse(self, head):
    + u. L7 I% K$ t, W& z
62.         if head is None and head.next is None:
    
63.             return head
    : b1 b6 V+ w; C( \
64.         pre = head
    ( V8 Q9 A: B6 y( L( D0 ]
65.         cur = head.next
    6 H% S6 W# B# N) _
66.         while cur is not None:
    , |$ N# m) a  @) C6 R- F
67.             temp = cur.next
    ) l( ^  w: b1 {; b+ j' _/ R. N
68.             cur.next = pre
    
69.             pre = cur
    
70.             cur = temp
    
71.         head.next = None
    
72.         return pre
    7 F8 {  P5 |  p2 j1 w
73. 
    
74.     def print_list(self, head):
    
75.         init_data = []
    8 _* Y' \- c# l( m3 L
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    ! `0 ?- b( S; ~/ |. A" \9 x" I
78.             head = head.next
    
79.         return init_data
    6 {, G8 C! V7 i* u  I7 M
80. 
    
81. if __name__=='__main__':
    
82.     head=Node('head')
    
83.     link=List(head)
    2 d* L+ }1 `3 V7 G' h$ W9 s. p
84.     for i in range(10):
    
85.         node=Node(i)
    
86.         link.append(node)
    
87.     print(link.print_list(head))

复制代码