單鏈表可以順序非遞歸的遍歷訪問。同時，單鏈表具有遞歸的性質，可以遞歸訪問。
遞歸訪問有兩種方式，一是首先訪問當前節點，再遞歸訪問剩下的節點。
二是首先遞歸訪問剩下的節點，在訪問當前節點。這種方式的遞歸訪問可以實現單鏈表的逆序訪問。
來自于《算法：C 語言實現》
（CPPBLOG 刪除后為什么不能再提交，錯誤：不能重復提交！可是已經刪除了啊）
1 #include <iostream>
2 using namespace std;
3
4 struct node
5 {
6 int item;
7 node* next;
8 };
9
10 void insert(int i, node* h)
11 {
12 node* p = new node;
13 p->item = i;
14 p->next = h->next;
15 h->next = p;
16 }
17
18 void traverse(node* h)
19 {
20 h = h->next;
21 while (h != 0)
22 {
23 cout << h->item << ' ';
24 h = h->next;
25 }
26 cout << endl;
27 }
28
29 void traverseRecurse(node* h)
30 {
31 if (h->next == 0)
32 {
33 cout << endl;
34 return;
35 }
36 cout << h->next->item << ' ';
37 traverseRecurse(h->next);
38 }
39
40 void traverseRecurseIvertedSequence(node* h)
41 {
42 if (h->next == 0)
43 {
44 cout << endl;
45 return;
46 }
47 traverseRecurseIvertedSequence(h->next);
48 cout << h->next->item << ' ';
49 }
50
51 void clear(node* h)
52 {
53 node* p = h->next, *q;
54 while (p != 0)
55 {
56 q = p->next;
57 delete p;
58 p = q;
59 }
60 }
61
62 int main()
63 {
64 node* h = new node;
65 h->next = 0;
66 for (int i = 0; i < 10; ++i)
67 {
68 insert(i, h);
69 }
70 traverse(h);
71 traverseRecurse(h);
72 traverseRecurseIvertedSequence(h);
73 clear(h);
74 delete h;
75 return 0;
76 }
posted on 2011-05-18 19:13
unixfy 閱讀(445)
評論(0) 編輯 收藏 引用