数据结构 链表2
目录
前言：
一，反转一个链表(迭代)
二，打印一个链表（递归）
三，反转一个链表(递归)
四，双向链表
总结
前言：
我们根据 [文章 链表1] 可以知道链表相比较于数组的优缺点和计算机是如何管理内存的，然后介绍了链表的实现，头插法，任意节点插入，任意节点删除，接下来我们就来学习反转链表与打印链表的迭代和递归操作
一，反转一个链表(迭代)
反转一个链表并不是移动位置，而是改变输出方向，就好比如数组一样，我们打印一个反转的数组，就是for循环反着循环就好了，取决于下角标，而不是数据的位置，这里也是同理
#include<iostream> #include<new> using namespace std; struct Node { int data; Node* Next; }; Node* head; void reverse(){ Node* current, * prev, * next; current = head; prev = NULL; while (current != NULL) { next = current->Next; current->Next = prev; //这里可以设置第一个节点为NULL prev = current; current = next; } head = prev; } void print() { Node* temp = head; while(temp!=NULL) { cout << temp->data << " "; temp = temp->Next; } } int main() { head = NULL; Node* temp1 = new Node; temp1->data = 1; temp1->Next = NULL; Node* temp2 = new Node; temp2->data = 2; temp2->Next = NULL; Node* temp3 = new Node; temp3->data = 3; temp3->Next = NULL; Node* temp4 = new Node; temp4->data = 4; temp4->Next = NULL; temp1->Next = temp2; temp2->Next = temp3; temp3->Next = temp4; head = temp1; reverse(); print(); }这是反转一个链表的操作，然后我们来详细的看一下这个反转链表的函数
void reverse(){ Node* current, * prev, * next; current = head; prev = NULL; while (current != NULL) { next = current->Next; current->Next = prev; //这里可以设置第一个节点为NULL prev = current; current = next; } head = prev; }这里就是反转链表的函数，我们反转链表主要就是利用改变后面的指向，使得输出方向发生变化，因为head永远都是这个链表的第一个节点的位置
这里设置了三个指针
prev： 先前的 这个是用来当current为空的时候，好用prev给head提供最好一个节点的位置，还有一个就是让current指向前一个
current：现在的 这个是用来表示现在这个节点的，利用current来来指向前一个
next： 下一个的 这个是用来为current提供下一个位置的
二，打印一个链表（递归）
这里就不讲解递归的思想了，可以去看我的文章函数的递归
我们根据这个思想来编写这个递归思想书写这个代码
#include<iostream> #include<new> using namespace std; struct Node { int data; Node* Next; }; Node* head; void reverse(){ Node* current, * prev, * next; current = head; prev = NULL; while (current != NULL) { next = current->Next; current->Next = prev; //这里可以设置第一个节点为NULL prev = current; current = next; } head = prev; } void print1(Node* p) { if (p == NULL) { return; } cout << p->data << " "; print1(p -> Next); cout << p->data << " "; } int main() { head = NULL; Node* temp1 = new Node; temp1->data = 1; temp1->Next = NULL; Node* temp2 = new Node; temp2->data = 2; temp2->Next = NULL; Node* temp3 = new Node; temp3->data = 3; temp3->Next = NULL; Node* temp4 = new Node; temp4->data = 4; temp4->Next = NULL; temp1->Next = temp2; temp2->Next = temp3; temp3->Next = temp4; head = temp1; reverse(); print1(head); }这个里面有利用递归来书写的打印链表
if (p == NULL) { return; }这个为递归的基准条件，什么时候跳出递归进行反转
cout << p->data << " "; print1(p -> Next); cout << p->data << " ";这个是递归的过程，上面的为正序打印，下面为逆序打印，至于为什么这样，看我的文章函数的递归
三，反转一个链表(递归)
#include<iostream> #include<new> using namespace std; struct Node { int data; Node* Next; }; Node* head; void reverse1(Node*p){ if (p->Next == NULL) { head = p; return; } reverse1(p->Next); Node* q = p->Next; q->Next = p; p->Next = NULL; } void print1(Node* p) { if (p == NULL) { return; } cout << p->data << " "; print1(p -> Next); } int main() { head = NULL; Node* temp1 = new Node; temp1->data = 1; temp1->Next = NULL; Node* temp2 = new Node; temp2->data = 2; temp2->Next = NULL; Node* temp3 = new Node; temp3->data = 3; temp3->Next = NULL; Node* temp4 = new Node; temp4->data = 4; temp4->Next = NULL; temp1->Next = temp2; temp2->Next = temp3; temp3->Next = temp4; head = temp1; reverse1(head); print1(head); }我们来看这个递归反转链表的代码
void reverse1(Node*p){ if (p->Next == NULL) { head = p; return; } reverse1(p->Next); Node* q = p->Next; q->Next = p; p->Next = NULL; }这个相较于迭代，代码量少了很多
if语句是用来设置基准条件的，着p是为了寻找最后一个节点赋值给head，另外一个就是挖掘深度，提供可以改变指向的一个环境，后面就是递归完之后，我们知道这个如果是打印数字的话就是反着来的，所以我们就知道这个已经是到最后一个节点了，然后我们只需要改变指向
递归调用过程
初始调用：
reverse1(head)，即reverse1(A)。递归调用：
reverse1(B)。递归调用：
reverse1(C)。递归调用：
reverse1(D)。当
D的Next为NULL时，设置head = D，并返回。我们可以知道在D的时候，Next已经为空，则这个时候就开始return了，然后我们就进入C，我们以C为例子来讲解
这个就是过程，改变下一个，本个为空
四，双向链表
struct Node { int data; Node* next; Node* prev; };双向链表是由两个地址域的
优点：如果我们由指向任意节点的指针，那么我们是方便反向查询的（仅需一个指针）
缺点：代码量增加，占用内存
双向链表的实现跟单向链表很像，只是多了一个地址域而已，这里就不过多解释了，对于堆的数据，我们链表一般都是在堆的，在堆里面查找数据一般都是利用指针
总结
我们目前基本学习完了链表的全部知识
-----增删改查
-----打印链表（迭代，递归）
-----反转链表（迭代，递归）
增删改查：这个就是要注意指向问题，比如增加到中间的位置的时候，是需要找到前面那个节点进程处理的
递归 ：需要注意的就是基准条件和过程，释放到入口的上面还是下面