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

admin

题目：创建一个链表。
( x# G; _1 U1 L$ ]$ c5 Q5 W0 e& N5 h程序分析：原文不太靠谱。
1 _& z" Q$ ~9 H7 B# T

1. class Node:
   5 D3 D  W; a5 S" P
2. 
   % V( J& J" `7 M( ?8 c1 {
3.     def __init__(self, data):
   
4.         self.data = data
   
5.         self.next = None
   
6. 
   
7.     def get_data(self):
   5 f% J. I( F" Q' r
8.         return self.data
   
9. 
   
10. class List:
    ) D' h  O; F' v' l
11. 
    0 k6 U" Q3 w' f" T7 R
12.     def __init__(self, head):
    7 F5 H- ?% f* y% ]8 g3 m0 `5 b6 i
13.         self.head = head
    / H; I3 a) L( W* |+ ~3 u6 {. |; p9 l' @
14. 
    , Y, G3 S, h% H$ D+ n
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    
17. 
    
18.     def get_len(self):  
    : v5 G% u( \7 g. \
19.         length = 0
    ( A* X7 c; D8 a4 B' ~8 ~
20.         temp = self.head
    5 T. @* k7 R7 f0 ?1 k7 K" p4 Z
21.         while temp is not None:
    % i1 H1 N, d7 b- s
22.             length += 1
    
23.             temp = temp.next
    ; t; x: w) m8 Q7 \& M  ?7 p9 R
24.         return length
    
25. 
    % m' E" x: {8 C5 r
26.     def append(self, node):
    
27.         temp = self.head
    ' e. S8 T3 T( L9 j; c
28.         while temp.next is not None:
    
29.             temp = temp.next
    ! u4 ]# l  j' c, ]$ b4 g, q
30.         temp.next = node
    
31. 
    
32.     def delete(self, index):
    0 ~3 U& N7 U+ Q7 I
33.         if index < 1 or index > self.get_len():
    + Z+ J: `6 ^' W% k5 Q0 {) G) J+ b
34.             print("给定位置不合理")
    
35.             return
    
36.         if index == 1:
    
37.             self.head = self.head.next
    
38.             return
    
39.         temp = self.head
    
40.         cur_pos = 0
    0 W) }5 f6 j$ i+ O% ~0 C
41.         while temp is not None:
    
42.             cur_pos += 1
    
43.             if cur_pos == index-1:
    
44.                 temp.next = temp.next.next
    ) o# e; m# k. p/ S
45.             temp = temp.next
    . O! R' g1 r! K, V
46. 
    , @1 z! K5 u) [# x
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    0 y% O) C; i) `4 e/ p6 K' W
49.             print("插入结点位置不合理")
    
50.             return
    $ }1 S3 W. k6 {( U2 @' }2 |
51.         temp = self.head
    
52.         cur_pos = 0
    ; n9 G, F+ A4 D& j7 I1 d8 [
53.         while temp is not Node:
    
54.             cur_pos += 1
      o, V$ Q3 ~# K3 p6 d% a7 m. `
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    . n  E& ]% |- E% Q
57.                 temp.next =node
    
58.                 break
    * L$ I- r" ]0 I9 c
59.             temp = temp.next
    . z/ I4 Z# c, s* T6 d2 e
60. 
    * z! K0 h1 E  T3 v2 m! l
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    1 ~4 l% h7 A2 y: Z) ^3 w
63.             return head
    % h& y5 i' e, g. G& C% _: \7 T
64.         pre = head
    
65.         cur = head.next
    2 H2 f: `5 t2 h9 \
66.         while cur is not None:
    ! f* E1 Y4 ?, F: {
67.             temp = cur.next
    
68.             cur.next = pre
    7 A5 V+ S+ }, V* a$ l2 [) S
69.             pre = cur
    
70.             cur = temp
    2 V; L2 `* W( c
71.         head.next = None
    
72.         return pre
    : p" m# v3 u. X) d6 ]8 Z' k9 f! `
73. 
    
74.     def print_list(self, head):
    3 S8 _, }( o# p: D9 {
75.         init_data = []
    
76.         while head is not None:
    2 |0 L% ], H' ^+ s# B
77.             init_data.append(head.get_data())
    0 g6 l2 |  H3 R# j; m! H
78.             head = head.next
    , R" y9 f2 M; b+ ^
79.         return init_data
    + O4 t/ b; l0 U  \& V  e
80. 
    
81. if __name__=='__main__':
    
82.     head=Node('head')
    ( @4 H0 x1 }3 N
83.     link=List(head)
    
84.     for i in range(10):
    
85.         node=Node(i)
    
86.         link.append(node)
    
87.     print(link.print_list(head))

复制代码