数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++实现双向链表程序
双向链表是一种数据结构，它由使用自引用结构创建的节点组成。每个节点包含三个部分：数据、指向下一个链表节点的引用和指向前一个链表节点的引用。
只需要第一个链表节点的引用就可以访问整个链表。这被称为头节点。链表中的最后一个节点不指向任何节点，因此该部分存储NULL。此外，双向链表可以双向遍历，因为每个节点都指向其前一个节点和下一个节点。
实现双向链表的程序如下所示。
示例
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *prev;
struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = newdata;
newnode->prev = NULL;
newnode->next = head;
if(head != NULL)
head->prev = newnode ;
head = newnode;
}
void display() {
struct Node* ptr;
ptr = head;
while(ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The doubly linked list is: ";
display();
return 0;
}输出
The doubly linked list is: 9 2 7 1 3
在上面的程序中，结构体Node构成双向链表节点。它包含数据以及指向下一个和前一个链表节点的指针。如下所示。
struct Node {
int data;
struct Node *prev;
struct Node *next;
};函数insert()将数据插入到双向链表的开头。它创建一个newnode并将数字插入到newnode的数据字段中。然后，newnode中的prev指针指向NULL（因为它是在开头插入的），next指针指向head。如果head不为NULL，则head的prev指针指向newnode。最后，head指向newnode，即链表从此处开始。如下所示。
void insert(int newdata) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = newdata;
newnode->prev = NULL;
newnode->next = head;
if(head != NULL)
head->prev = newnode ;
head = newnode;
}函数display()显示整个双向链表。首先，ptr指向head。然后，它不断向前移动到下一个节点，直到打印所有节点的数据值。如下所示。
void display() {
struct Node* ptr;
ptr = head;
while(ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}在main()函数中，首先通过调用insert()将各种值插入到双向链表中。然后显示双向链表。如下所示。
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The doubly linked list is: ";
display();
return 0;
}
更新于：2023年10月5日
36K+ 浏览量
广告