(c++)创建双向链表与双向循环链表

2021年9月7日 16点热度 0条评论 来源: print('fish')

        学会了单向链表后,学习双向链表就简单很多了。需要注意的是:双向链表的头节点和尾节点是指向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移到q的位置,方便,下一次输入将数据插入尾部
	}
	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;
}

下面这个图是运行结果:

 挺好玩的吧

    原文作者:print('fish')
    原文地址: https://blog.csdn.net/xiexieyuchen/article/details/120165535
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。