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

admin

题目：创建一个链表。
6 L& f9 U9 L8 {6 h( c/ T程序分析：原文不太靠谱。
  w" V7 i4 {* D  ?

1. class Node:
   * P, I9 n) z5 O3 @  C$ m; T9 F
2. 
   ! b9 k& U2 {* C1 F
3.     def __init__(self, data):
   ' N3 i0 K+ a: D2 _) \4 N* k
4.         self.data = data
   
5.         self.next = None
   
6. 
   
7.     def get_data(self):
   7 @( @8 q8 u7 M, t6 F* M8 S
8.         return self.data
   & ]" j6 T- b. m4 ~; t* u) E6 o
9. 
   
10. class List:
    
11. 
    
12.     def __init__(self, head):
    0 f- n9 r% K4 h/ v
13.         self.head = head
    1 G% q5 ]. b: s1 K$ l& K7 @. _
14. 
    5 @  {# F- c$ `( Q# |
15.     def is_empty(self):
    / G6 ^1 W  \4 w
16.         return self.get_len() == 0
    
17. 
    
18.     def get_len(self):  
    ) f# n" O1 \3 \! ~( T2 y
19.         length = 0
    3 U& b$ E2 p* ]( L& P: C
20.         temp = self.head
    ; Q! R" m1 d* ~, V7 H
21.         while temp is not None:
    ( {& y/ |$ k2 ]- u  M5 o$ {
22.             length += 1
    . ?8 X, f1 f( d9 P
23.             temp = temp.next
    ( W2 W4 l" U9 K( w$ W2 o+ b
24.         return length
    # a$ g; Z+ j4 J2 |
25. 
    9 Q  {: I1 ^9 p$ m8 r
26.     def append(self, node):
    " s8 s7 i8 C0 P9 y- s2 C
27.         temp = self.head
    
28.         while temp.next is not None:
    
29.             temp = temp.next
    
30.         temp.next = node
    
31. 
    ( O7 c, @2 n8 K+ H
32.     def delete(self, index):
    
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    6 }3 S# s2 J  u2 S$ A- L4 A) k
35.             return
    
36.         if index == 1:
      b6 |! T- M* X+ j
37.             self.head = self.head.next
    ) [( D6 G1 }$ n1 P% I& I
38.             return
    
39.         temp = self.head
    1 l; {. N9 D& y. G, @- `
40.         cur_pos = 0
    
41.         while temp is not None:
    
42.             cur_pos += 1
    & [0 m0 L& k- ?6 q  B" Y
43.             if cur_pos == index-1:
    
44.                 temp.next = temp.next.next
      u8 b# j  i8 k; x, C* [
45.             temp = temp.next
    
46. 
    & C  C* v8 n3 l8 Z
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    
49.             print("插入结点位置不合理")
    
50.             return
    
51.         temp = self.head
    ( ^+ Z3 {$ G* `7 |; q
52.         cur_pos = 0
    % U  |5 y8 a4 {$ O7 F* E4 h
53.         while temp is not Node:
    ; p$ F, A* E$ u5 H2 }
54.             cur_pos += 1
    : @% {8 v4 o* E% {6 l* l( _
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    
57.                 temp.next =node
    
58.                 break
    
59.             temp = temp.next
    
60. 
    
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    8 C3 i9 b! [2 Q5 L
63.             return head
    0 n, v! q: G6 ?/ ~# a0 J1 [
64.         pre = head
    7 K- P1 x& m% a7 r
65.         cur = head.next
    
66.         while cur is not None:
    
67.             temp = cur.next
    
68.             cur.next = pre
    
69.             pre = cur
    2 [# E- b" K! w5 h, q( b
70.             cur = temp
    2 z$ z7 x! R  A; D
71.         head.next = None
      k3 h) g! K) @7 I3 w( }6 M! C6 n( {
72.         return pre
    
73. 
    
74.     def print_list(self, head):
    
75.         init_data = []
    
76.         while head is not None:
      J/ [% s* o* k; r
77.             init_data.append(head.get_data())
    6 S) D8 \! e( f) C. S, {* Z; r
78.             head = head.next
    & A: l( G7 U& e# T5 j
79.         return init_data
    1 g& E: R, ~& w9 ^% A. V# W7 M
80. 
    
81. if __name__=='__main__':
    
82.     head=Node('head')
    1 r+ \) A4 Q' ~& j
83.     link=List(head)
    
84.     for i in range(10):
    
85.         node=Node(i)
    
86.         link.append(node)
    
87.     print(link.print_list(head))

复制代码