c++模板制作一个单链表的抽象数据类型和双链表的抽象数据类型,要求有头插函数,尾插函数,头删函数,尾删函数,设计接口,可通过编译,完整的测试案例,使用迭代器,可交互,规范命名,面向对象编程,操作为O(1)的时间复杂度
时间: 2023-05-30 07:02:46 浏览: 62
单链表抽象数据类型:
```
template <typename T>
class SinglyLinkedList {
public:
// 节点结构体
struct Node {
T data;
Node* next;
Node(T d, Node* n = nullptr) : data(d), next(n) {}
};
// 迭代器
class Iterator {
private:
Node* node;
public:
Iterator(Node* n) : node(n) {}
Iterator& operator++() { node = node->next; return *this; }
bool operator==(const Iterator& other) const { return node == other.node; }
bool operator!=(const Iterator& other) const { return node != other.node; }
T& operator*() const { return node->data; }
};
SinglyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
~SinglyLinkedList() { clear(); }
// 头插
void push_front(const T& data) {
head = new Node(data, head);
if (!tail) tail = head;
++size;
}
// 尾插
void push_back(const T& data) {
if (!tail) {
head = tail = new Node(data);
} else {
tail->next = new Node(data);
tail = tail->next;
}
++size;
}
// 头删
void pop_front() {
if (head) {
Node* temp = head;
head = head->next;
delete temp;
--size;
if (!head) tail = nullptr;
}
}
// 尾删
void pop_back() {
if (tail) {
if (head == tail) {
delete head;
head = tail = nullptr;
} else {
Node* temp = head;
while (temp->next != tail) temp = temp->next;
delete tail;
tail = temp;
tail->next = nullptr;
}
--size;
}
}
// 清空
void clear() {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
tail = nullptr;
size = 0;
}
// 大小
int Size() const { return size; }
// 迭代器
Iterator begin() const { return Iterator(head); }
Iterator end() const { return Iterator(nullptr); }
private:
Node* head; // 链表头指针
Node* tail; // 链表尾指针
int size; // 链表元素个数
};
```
双链表抽象数据类型:
```
template <typename T>
class DoublyLinkedList {
public:
// 节点结构体
struct Node {
T data;
Node* prev;
Node* next;
Node(T d, Node* p = nullptr, Node* n = nullptr) : data(d), prev(p), next(n) {}
};
// 迭代器
class Iterator {
private:
Node* node;
public:
Iterator(Node* n) : node(n) {}
Iterator& operator++() { node = node->next; return *this; }
Iterator& operator--() { node = node->prev; return *this; }
bool operator==(const Iterator& other) const { return node == other.node; }
bool operator!=(const Iterator& other) const { return node != other.node; }
T& operator*() const { return node->data; }
};
DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
~DoublyLinkedList() { clear(); }
// 头插
void push_front(const T& data) {
head = new Node(data, nullptr, head);
if (head->next) head->next->prev = head;
if (!tail) tail = head;
++size;
}
// 尾插
void push_back(const T& data) {
if (!tail) {
head = tail = new Node(data);
} else {
tail->next = new Node(data, tail, nullptr);
tail = tail->next;
}
++size;
}
// 头删
void pop_front() {
if (head) {
Node* temp = head;
head = head->next;
if (head) head->prev = nullptr;
delete temp;
--size;
if (!head) tail = nullptr;
}
}
// 尾删
void pop_back() {
if (tail) {
Node* temp = tail;
tail = tail->prev;
if (tail) tail->next = nullptr;
delete temp;
--size;
if (!tail) head = nullptr;
}
}
// 清空
void clear() {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
tail = nullptr;
size = 0;
}
// 大小
int Size() const { return size; }
// 迭代器
Iterator begin() const { return Iterator(head); }
Iterator end() const { return Iterator(nullptr); }
Iterator rbegin() const { return Iterator(tail); }
Iterator rend() const { return Iterator(nullptr); }
private:
Node* head; // 链表头指针
Node* tail; // 链表尾指针
int size; // 链表元素个数
};
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)