双向链表的定义,初始化,插入,删除,并编写一个读入一个字符串,把它顺序存入一个双向链表并逆序打印出
时间: 2023-06-15 07:07:14 浏览: 50
双向链表(Doubly Linked List)是一种链式存储结构,它的每个节点除了存储数据之外还有两个指向前后节点的指针。
定义:
```c++
template <typename T>
class DoublyLinkedListNode {
public:
T data;
DoublyLinkedListNode<T>* prev;
DoublyLinkedListNode<T>* next;
DoublyLinkedListNode(T d = T(), DoublyLinkedListNode<T>* p = nullptr, DoublyLinkedListNode<T>* n = nullptr)
: data(d), prev(p), next(n) {}
};
template <typename T>
class DoublyLinkedList {
public:
DoublyLinkedListNode<T>* head;
DoublyLinkedListNode<T>* tail;
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
};
```
初始化:
```c++
template <typename T>
void initDoublyLinkedList(DoublyLinkedList<T>& list) {
list.head = nullptr;
list.tail = nullptr;
}
```
插入:
```c++
template <typename T>
void insertDoublyLinkedList(DoublyLinkedList<T>& list, T data) {
DoublyLinkedListNode<T>* newNode = new DoublyLinkedListNode<T>(data);
if (list.head == nullptr) {
list.head = newNode;
list.tail = newNode;
}
else {
newNode->prev = list.tail;
list.tail->next = newNode;
list.tail = newNode;
}
}
```
删除:
```c++
template <typename T>
void deleteDoublyLinkedList(DoublyLinkedList<T>& list, DoublyLinkedListNode<T>* node) {
if (node == list.head) {
list.head = node->next;
}
else {
node->prev->next = node->next;
}
if (node == list.tail) {
list.tail = node->prev;
}
else {
node->next->prev = node->prev;
}
delete node;
}
```
读入一个字符串,把它顺序存入一个双向链表并逆序打印出:
```c++
#include <iostream>
#include <string>
using namespace std;
int main() {
// 读入一个字符串
string str;
getline(cin, str);
// 创建一个双向链表
DoublyLinkedList<char> list;
initDoublyLinkedList(list);
// 把字符串顺序存入双向链表
for (char c : str) {
insertDoublyLinkedList(list, c);
}
// 逆序打印双向链表
DoublyLinkedListNode<char>* p = list.tail;
while (p != nullptr) {
cout << p->data;
p = p->prev;
}
return 0;
}
```