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

admin

题目：创建一个链表。
; O* A0 \0 ]2 I& }+ p+ O9 ^/ \程序分析：原文不太靠谱。
8 Z9 ]3 i3 O5 I6 |

1. class Node:
   / I( C  ~* A7 E( i& b5 {/ e
2. 
   
3.     def __init__(self, data):
   / @7 p: ~/ q9 G' o- r/ i& ^1 O% i7 {
4.         self.data = data
   
5.         self.next = None
   & P8 `& ?. `' u  K4 u- V3 I  D( A
6. 
   8 s6 t9 S; r( `
7.     def get_data(self):
   0 F. f$ w! r9 x* R  y8 Q6 q
8.         return self.data
   
9. 
   2 U! a6 d% V" {# F
10. class List:
    
11. 
    
12.     def __init__(self, head):
    ; P' @6 @  f, }$ b+ h8 d) l( i; l, I2 q
13.         self.head = head
    / c, p$ _7 Q8 o
14. 
    
15.     def is_empty(self):
      s' E& k% H/ a; J/ K
16.         return self.get_len() == 0
    6 W* T+ `7 p1 i: `: U; n' ~
17. 
    # O3 Z# ~7 @- {+ w" w
18.     def get_len(self):  
    2 z4 G0 L- p5 z+ r' U/ t
19.         length = 0
    - R; @1 ~5 x% ]
20.         temp = self.head
    
21.         while temp is not None:
    + I* O3 M/ \6 S2 Z6 ^9 {: _) Y9 k
22.             length += 1
    7 c! L$ O& `% Y- m
23.             temp = temp.next
    
24.         return length
    ; G/ u5 z* b' W7 o* N; e
25. 
    0 t. j2 W! \4 O. {3 Y
26.     def append(self, node):
    
27.         temp = self.head
    ( a- H! T% w# k
28.         while temp.next is not None:
    . g) ^' d( ~2 f* n' T
29.             temp = temp.next
    $ y! O1 e+ d7 B+ l" @* c; x, P
30.         temp.next = node
    4 ?  F3 V5 z4 M
31. 
    0 y2 b# J3 w3 ?/ F
32.     def delete(self, index):
    
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    
35.             return
    ! f, ?/ b& R9 W* [2 J. ]
36.         if index == 1:
    7 L1 w9 Y8 B' S, D: M6 ]  g- W
37.             self.head = self.head.next
    
38.             return
    
39.         temp = self.head
    
40.         cur_pos = 0
    
41.         while temp is not None:
    
42.             cur_pos += 1
    , a: _, @" ~6 ?1 [
43.             if cur_pos == index-1:
    - {  e7 f2 h6 ~
44.                 temp.next = temp.next.next
    4 M& n! W) K% Q: ^) f7 M7 C0 }
45.             temp = temp.next
    
46. 
    4 j% U% l# ]( s* r7 ]1 L2 i0 R: S
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    1 ?' t6 e9 j# `) x0 M( |+ Y% s8 ~
49.             print("插入结点位置不合理")
    * X& h/ ]& S" z* x
50.             return
    
51.         temp = self.head
    ! W0 T( u9 G, q( M& O4 o
52.         cur_pos = 0
    & ]" H4 W3 i" ~( h/ p
53.         while temp is not Node:
    
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    ; L. ~1 S8 S! e  D4 O1 H2 c
56.                 node.next = temp.next
    
57.                 temp.next =node
    
58.                 break
    
59.             temp = temp.next
    + |. m7 e6 @) ]. g9 q! @3 k
60. 
    
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    - Q. Y3 j8 G  D$ B( c- G! q
63.             return head
    
64.         pre = head
    ; C% m8 M/ W& Q
65.         cur = head.next
    1 }4 }2 {5 @" k
66.         while cur is not None:
    5 I2 F, Q9 d& \, t. }
67.             temp = cur.next
    
68.             cur.next = pre
    0 t9 e. m9 i2 y. c
69.             pre = cur
    
70.             cur = temp
    
71.         head.next = None
    
72.         return pre
    
73. 
    
74.     def print_list(self, head):
    
75.         init_data = []
    8 C8 U& n, d! |& {
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    0 W; o) H0 H* [, d! ?
78.             head = head.next
    # i- L2 d1 [. z7 q5 a
79.         return init_data
    ) a6 S4 s- E, @6 Z3 K# n
80. 
    
81. if __name__=='__main__':
    
82.     head=Node('head')
    
83.     link=List(head)
    5 B, s8 F+ L% a. [) p2 \/ c* A; ?
84.     for i in range(10):
    
85.         node=Node(i)
    
86.         link.append(node)
    8 @3 Z/ w) A7 D, v1 |, R
87.     print(link.print_list(head))

复制代码