C語言實現(xiàn)單鏈表逆序與逆序輸出實例

更新時間：2014年08月23日 09:17:47 投稿：shichen2014

這篇文章主要介紹了C語言實現(xiàn)單鏈表逆序與逆序輸出,是數據結構與算法中比較基礎的重要內容,有必要加以牢固掌握,需要的朋友可以參考下

單鏈表的逆序輸出分為兩種情況，一種是只逆序輸出，實際上不逆序；另一種是把鏈表逆序。本文就分別實例講述一下兩種方法。具體如下：

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

//循環(huán)
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;
}

這里鏈表逆序用了兩種方法：循環(huán)，遞歸。讀者最容易理解的方法就是在紙上自己畫一下。

希望本文所述實例對大家的數據結構與算法學習能有所幫助。

您可能感興趣的文章: