C语言实现单链表逆序与逆序输出实例

http://www.jb51.net/article/54219.htm

2014

这篇文章主要介绍了C语言实现单链表逆序与逆序输出,是数据结构与算法中比较基础的重要内容,有必要加以牢固掌握,需要的朋友可以参考下

单链表的逆序输出分为两种情况，一种是只逆序输出，实际上不逆序；另一种是把链表逆序。本文就分别实例讲述一下两种方法。具体如下：

1.逆序输出

实例代码如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include<iostream> #include<stack> #include<assert.h> using namespace std; typedef struct node{  int data;  node * next; }node; //尾部添加 node * add(int n, node * head){  node * t = new node;  t->data = n;  t->next = NULL;  if (head == NULL){   head = t;  }  else if (head->next == NULL){   head->next = t;  }  else{   node * p = head->next;   while (p->next != NULL){    p = p->next;   }   p->next = t;  }  return head; } //顺序输出 void print(node * head){  node * p = head;  while (p != NULL){   cout << p->data << " ";   p = p->next;  }  cout << endl; } //递归 void reversePrint(node * p){  if (p != NULL){   reversePrint(p->next);   cout << p->data << " ";  } } //栈 void reversePrint2(node * head){  stack<int> s;  while (head != NULL){   s.push(head->data);   head = head->next;  }  while (!s.empty()){   cout << s.top() << " ";   s.pop();  } } int main(){  node * head = NULL;  for (int i = 1; i <= 5; i++){   head = add(i, head);  }   print(head);   reversePrint(head);   reversePrint2(head);  system("pause");   return 0; }

逆序输出可以用三种方法: 递归，栈，逆序后输出。最后一种接下来讲到。

2.单链表逆序

实例代码如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

#include<iostream> #include<stack> #include<assert.h> using namespace std; typedef struct node{  int data;  node * next; }node; node * add(int n, node * head){  node * t = new node;  t->data = n;  t->next = NULL;  if (head == NULL){   head = t;  }  else if (head->next == NULL){   head->next = t;  }  else{   node * p = head->next;   while (p->next != NULL){    p = p->next;   }   p->next = t;  }  return head; } //循环 node * reverse(node * head){  if (head == NULL || head->next == NULL){   return head;  }  node * p1 = head;  node * p2 = head->next;  node * p3 = NULL;  head->next = NULL;  while (p2 != NULL){   p3 = p2;   p2 = p2->next;   p3->next = p1;   p1 = p3;  }  head = p1;  return head; } void print(node * head){  node * p = head;  while (p != NULL){   cout << p->data << " ";   p = p->next;  }  cout << endl; } //递归 node * reverse2(node * p){  if (p == NULL || p->next == NULL){   return p;  }  node * newHead = reverse2(p->next);  p->next->next = p;  p->next = NULL;  return newHead; } int main(){  node * head = NULL;  for (int i = 1; i <= 5; i++){   head = add(i, head);  }  print(head);  head = reverse(head);  print(head);  head = reverse2(head);  print(head);  system("pause");  return 0; }

这里链表逆序用了两种方法：循环，递归。读者最容易理解的方法就是在纸上自己画一下。

希望本文所述实例对大家的数据结构与算法学习能有所帮助。