当前位置:   article > 正文

c++递归的实例使用1(链表和排序二叉树)——包含单链表的倒序输出和排序二叉树的后序输出 #朱小黑的小白日记#_链表c尾插法倒序输出

链表c尾插法倒序输出

过程封装一部分比较实用的单链表函数
主要练习的是其中的 void reverse_print_list函数,需要使用简单的递归,在二叉树中的递归会更加复杂一些。

/*goodlist.h*/
#include<iostream> 
using namespace std;
struct Node {
 int value;
 Node* next;
};
int list_tail_insert(Node* list_head, int var);//单个数据插入,尾插法
Node* list_head_insert(Node* list_head, int var);//单个数据插入,头插法
Node* list_specific_insert(Node* list_head, int location, int var);//指定位置插入,可以插入头,尾,或者头尾之间任意位置
void print_list(Node* list_head);//输出链表,循环方式,空格隔开
void reverse_print_list(Node* list_head);//逆序输出,递归方式,空格隔开
//void reverseprintlist(Node* list_head);
void change_specific_var(Node* list_head, int old_var, int new_var);//修改链表中的指定元素值
Node* del_specific_var(Node* list_head, int del_var);//删除链表中的指定元素值
Node* sort(Node* list_head);//从小到大排序
int list_len(Node* list_head);//检测链表长度
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

以下是自定义这些链表函数内容(一开始为了快点交作业排序采用了交换值的方法,之后会改为交换节点,方便以后的复用)

Node* list_head_insert(Node* list_head, int var) {
 Node* p = new Node;
 p->value = var;
 p->next = NULL;
 if (list_head == NULL)return p;
 else {
  p->next = list_head;
  return p;
 }
}
int list_tail_insert(Node* list_head, int var) {
 if (list_head == NULL) {
  cout << "无法在空链表中插入尾部" << endl;
  exit(-1);
 }
 else
 {
  Node* p = new Node;
  p->value = var;
  p->next = NULL;
  Node* tmp = list_head;
  while (tmp->next) tmp = tmp->next;
  tmp->next = p;
  return 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
Node* sort(Node* list_head){
if (list_head == NULL || list_head->next == NULL) return list_head;//如果链表为空或只有一个节点,直接返回
 int len = list_len(list_head);
 Node* p = list_head;
 for (int i = 1;i <= len - 1;++i) {
  p = list_head;
  while (p->next) {
   if (p->value > p->next->value) {
    int tmp = p->value;
    p->value = p->next->value;
    p->next->value = tmp;
   }
   p = p->next;
  }
 }
 return list_head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

其他比较简单的函数在此不再列出,来到关键的单链表倒序输出

void reverse_print_list(Node* list_head) {
 static int i = 0;//设置标识符用来判断是否应该输出换行符
 ++i;
 if (list_head == NULL) {
  --i;
  return;
 }
 else reverse_print_list(list_head->next);
 cout << list_head->value << " ";
 --i;
 if (i == 0)cout << endl;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

最初没有static int作为标识符,没有办法在打印完链表后输出一个回车,所以我采用的办法是在另一个函数中包含这个递归函数,结束后再输出一个回车。

虽然这样十分的简单粗暴,效果也很好,但破坏了过程的封装,使用者还可以调用单独的递归函数(主要是觉得这样写很难看)然后再一位同学的启发下改用静态变量来控制递归函数,也是将来使用递归的一个重要的小技巧。

顺便练习节点交换的冒泡排序

Node* sort(Node* list_head){
if (list_head == NULL || list_head->next == NULL) return list_head;
 int len = list_len(list_head);
 Node* cur = list_head, * pre = list_head;
 for (int i = 1;i <= len - 1;++i) {
  cur = list_head;
  pre = list_head;
  while (cur->next) {
   if (cur->value > cur->next->value) {
    if (cur == list_head) {
     list_head = list_head->next;
     cur->next = list_head->next;
     list_head->next = cur;
     pre = list_head;
     continue;
    }
    else {
     pre->next = cur->next;
     cur->next = NULL;
     cur->next = pre->next->next;
     pre->next->next = cur;
     pre = pre->next;
     continue;
    }
   }
   pre = cur;
   cur = cur->next;
  }
 }
 return list_head;

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

————————————————————————————————————
二叉树

#include<iostream>
using namespace std;
struct Node {
 int value;
 Node* leftnext;
 Node* rightnext;
};
bool is_leaf(Node* head);//是否是叶子结点
Node* insert(Node* T, int x);//在二叉树中插入一个结点
void postorder(Node* T);//后序遍历
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
Node* insert(Node* T, int x) {
 Node* p = new Node;
 p->value = x;
 p->leftnext = NULL;
 p->rightnext = NULL;
 if (!T) return p;
 Node* temp = T;
 while (temp) {
  if (x < temp->value)
  {
   if (temp->leftnext == NULL) {
    temp->leftnext = p;
    return T;
   }
   else {
    temp = temp->leftnext;
    continue;
   }
  }
  else
  {
   if (temp->rightnext == NULL) {
    temp->rightnext = p;
    return T;
   }
   else {
    temp = temp->rightnext;
    continue;
   }
  }
 }
 exit(-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
bool is_leaf(Node* head) {
 if (head->leftnext == NULL && head->rightnext == NULL) return true;
 else return false;
}
  • 1
  • 2
  • 3
void postorder(Node* T){
if (T == NULL) return;
 else if (is_leaf(T)) {
  cout << T->value << " ";
  return;
 }
 if (T->leftnext != NULL) {
  postorder(T->leftnext);
  if(T->rightnext==NULL) cout << T->value << " ";
 }
 if (T->rightnext != NULL) {
  postorder(T->rightnext);
  cout << T->value<<" ";
 }
 return;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/784944
推荐阅读
相关标签
  

闽ICP备14008679号