分為兩種情況，一種是只逆序輸出，實際上不逆序；另一種是把鏈表逆序。
********************逆序輸出***********************
1 #include<iostream>
2 #include<stack>
3 #include<assert.h>
4 using namespace std;
5
6
7 typedef struct node{
8 int data;
9 node * next;
10 }node;
11
12 //尾部添加
13 node * add(int n, node * head){
14 node * t = new node;
15 t->data = n;
16 t->next = NULL;
17 if (head == NULL){
18 head = t;
19 }
20 else if (head->next == NULL){
21 head->next = t;
22 }
23 else{
24 node * p = head->next;
25 while (p->next != NULL){
26 p = p->next;
27 }
28 p->next = t;
29 }
30 return head;
31 }
32
33 //順序輸出
34 void print(node * head){
35 node * p = head;
36 while (p != NULL){
37 cout << p->data << " ";
38 p = p->next;
39 }
40 cout << endl;
41 }
42
43 //遞歸
44 void reversePrint(node * p){
45 if (p != NULL){
46 reversePrint(p->next);
47 cout << p->data << " ";
48 }
49 }
50
51 //棧
52 void reversePrint2(node * head){
53 stack<int> s;
54 while (head != NULL){
55 s.push(head->data);
56 head = head->next;
57 }
58
59 while (!s.empty()){
60 cout << s.top() << " ";
61 s.pop();
62 }
63 }
64
65 int main(){
66
67 node * head = NULL;
68 for (int i = 1; i <= 5; i++){
69 head = add(i, head);
70 }
71 print(head);
72 reversePrint(head);
73 reversePrint2(head);
74 system("pause");
75 return 0;
76 }
逆序輸出可以用三種方法: 遞歸，棧，逆序後輸出。最後一種接下來講到。
*********************單鏈表逆序********************
1 #include<iostream>
2 #include<stack>
3 #include<assert.h>
4 using namespace std;
5
6
7 typedef struct node{
8 int data;
9 node * next;
10 }node;
11
12 node * add(int n, node * head){
13 node * t = new node;
14 t->data = n;
15 t->next = NULL;
16 if (head == NULL){
17 head = t;
18 }
19 else if (head->next == NULL){
20 head->next = t;
21 }
22 else{
23 node * p = head->next;
24 while (p->next != NULL){
25 p = p->next;
26 }
27 p->next = t;
28 }
29 return head;
30 }
31
32 //循環
33 node * reverse(node * head){
34
35 if (head == NULL || head->next == NULL){
36 return head;
37 }
38
39 node * p1 = head;
40 node * p2 = head->next;
41 node * p3 = NULL;
42 head->next = NULL;
43
44 while (p2 != NULL){
45 p3 = p2;
46 p2 = p2->next;
47 p3->next = p1;
48 p1 = p3;
49 }
50 head = p1;
51 return head;
52 }
53
54 void print(node * head){
55 node * p = head;
56 while (p != NULL){
57 cout << p->data << " ";
58 p = p->next;
59 }
60 cout << endl;
61 }
62
63
64 //遞歸
65 node * reverse2(node * p){
66 if (p == NULL || p->next == NULL){
67 return p;
68 }
69
70 node * newHead = reverse2(p->next);
71 p->next->next = p;
72 p->next = NULL;
73 return newHead;
74 }
75
76
77 int main(){
78
79 node * head = NULL;
80 for (int i = 1; i <= 5; i++){
81 head = add(i, head);
82 }
83 print(head);
84 head = reverse(head);
85 print(head);
86 head = reverse2(head);
87 print(head);
88
89 system("pause");
90 return 0;
91 }
這裡鏈表逆序用了兩種方法：循環，遞歸。理解的方法是在紙上自己畫一下。
#include<stdio.h>
#include<stdlib.h>
struct node{
int num;
struct node *next;
};
void display(node* p)
{
if(p==NULL)
{
return;
}
else
{
display(p->next);
printf("%d\n",p->num);
return;
}
return;
}
int main()
{
struct node *head,*tail,*p;
int num;
int size=sizeof(struct node);
head=tail=NULL;
printf("input number : \n");
scanf("%d",&num);
while(num!=0){
p=(struct node *)malloc(size);
p->num=num;
p->next=NULL;
if(head==NULL)
head=p;
else
tail->next=p;
tail=p;
scanf("%d",&num);
}
display(head);
return 0;
}
將一條鏈表按逆序輸出
假若頭結點為L,則有;
p=q=L;/*p,q為指向頭結點的兩個指針*/
while(p->next!=NULL)
p=p->next;/*讓p指向鍵表的最後一個要訪問結點*/
while(1)
{
while(q->next!=p)
q=q->next;/*讓q向後找,找到最後一個要打印的結點*/
printf("%d\n",p->data);
p=q;/*p向前移動一個*/
q=L;/*q又指向頭結點*/
if(p=L)/*訪問完了退出*/
break;
}
你參考吧
