博客

学会了单向链表后，学习双向链表就简单很多了。需要注意的是：

双向链表的头节点和尾节点是指向NULL的，而不是尾指针指向头节点形成一个环

，这一点之前博主学了单向链表后就想自己建一个双向链表，结果没憋出来。。。

双向链表其实就是多了一个指针域，在定义结构体时多定义一个指针就好。下面直接上代码。

#include<iostream>
#include<cstdlib>//malloc()函数头文件
using namespace std;
typedef struct Node {//定义结构体
	int data;
	struct Node* prev;//头指针
	struct Node* next;//尾指针
}node;
node* create(int n) {//尾插法创建链表
	node* head = (node*)malloc(sizeof(node));//开辟内存空间
	cin >> head->data;//先将一个数据进行输入
	head->next = NULL;
	head->prev = NULL;//将头节点的头尾指针指向NULL
	node* q = head;
	for (int i = 1; i < n; i++) {
		node* p = (node*)malloc(sizeof(node));//开辟内存空间
		cin >> p->data;
		p->next = NULL;//此时尾节点其实就是p，所以要将尾节点的尾指针指向NULL
		q->next = p;
		p->prev = q;//将p的头指针指向前一个节点
		q = q->next;//将q移到p的位置，方便，下一次输入将数据插入尾部
	}
	return head;//返回头指针
}
void print(node* head) {//遍历输出链表
	node* p = head;
	while (p != NULL) {//将链表从头开始打印
		cout << p->data << " ";
		p = p->next;//指向后一个节点
	}
	cout << endl;
	p = head;
	while (p->next != NULL)p = p->next;
	node* q = p;//进行循环找到尾节点
	while (q != NULL) {//从尾节点开始倒回来输出
		cout << q->data << " ";
		q = q->prev;//指向前一个节点
	}
}
int main() {
	int n;
	cin >> n;//输入要用链表保存的数据个数
	node* head = create(n);//创建链表
	print(head);//调用函数输出
	return 0;
}

运行结果：

这代码就是简单的建立了一个双向链表并进行了简单的遍历输出，还没有开始对双向链表进行操作（删除、修改、增加）。

最后是双向循环链表，也是突发奇想(也不算是奇想吧)，就想实现一下(其实就是在输入的最后将头尾连接一下，就是循环打印比较麻烦点)：

#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct Node {
	int data;
	struct Node* prev;//头指针
	struct Node* next;//尾指针
}node;
node* Create(int n) {
	node* head = (node*)malloc(sizeof(node));
	head->prev = NULL;
	head->next = NULL;
	cin >> head->data;//头节点也存储数据，所以先给头节点输入数据
	node* q = head, * p = NULL;;
	for (int i = 1; i < n; i++) {
		p = (node*)malloc(sizeof(node));
		cin >> p->data;
		p->next = q->next;
		p->prev = q;
		q->next = p;
		q = p;
	}
	p->next = head;//最后将链表头尾相接
	head->prev = p;
	return head;
}
void Print(node* head) {//将链表循环打印
	node* p = head;
	while (p->next != head) {
		node* q = p;
		while (q->next != p) {
			cout << q->data << " ";
			q = q->next;
		}
		cout << q->data << endl;
		p = p->next;
	}
	node* s = p;
	while (s->next != p) {
		cout << s->data << " ";
		s = s->next;
	}
	cout << s->data << endl;
}
int main() {
	int n;
	cin >> n;
	node* head = Create(n);
	cout << endl;
	Print(head);
	return 0;
}

下面这个图是运行结果：

挺好玩的吧