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

2020-01-26 15:22:45

字体：大中小

来源：转载

供稿：网友

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

1.逆序输出

实例代码如下：

#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.单链表逆序

实例代码如下：

#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;}

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

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

上一篇：MFC控件之CListCtrl的应用实例教程

下一篇：扩展KMP算法(Extend KMP)