单链表可以顺序非递归的遍历访问。同时，单链表具有递归的性质，可以递归访问。
递归访问有两种方式，一是首先访问当前节点，再递归访问剩下的节点。
二是首先递归访问剩下的节点，在访问当前节点。这种方式的递归访问可以实现单链表的逆序访问。
来自于《算法：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 阅读(428)
评论(0) 编辑 收藏 引用