设计一个通用链表类,要求如下: 1)数据成员包含头指针、尾指针、链表中节点个数、顺序访问中当前节点指针和当前节点前一个节点的指针; 2)主要的成员函数包含:生成节点(在链表头、尾以及任意位置)、插入节点、删除节点、访问/修改节点、遍历链表,以及一些辅助函数等; 3)能实现两个链表的复制; 4)能实现两个链表对象的赋值; 5)在测试程序中定义两个整型链表A和B,本别插入5个元素,然后把B中的元素加入A的尾部
时间: 2024-03-24 08:41:21 浏览: 49
实现链表的基本操作。
好的,下面是通用链表类的设计代码:
```cpp
template <typename T>
class LinkedList {
private:
struct Node {
T data;
Node* next;
};
Node* head;
Node* tail;
int count;
Node* current;
Node* prev;
public:
LinkedList() {
head = nullptr;
tail = nullptr;
count = 0;
current = nullptr;
prev = nullptr;
}
~LinkedList() {
Node* temp;
while (head != nullptr) {
temp = head;
head = head->next;
delete temp;
}
}
void insertAtHead(T data) {
Node* newNode = new Node{data, nullptr};
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
newNode->next = head;
head = newNode;
}
count++;
}
void insertAtTail(T data) {
Node* newNode = new Node{data, nullptr};
if (tail == nullptr) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
count++;
}
void insertAtPosition(T data, int position) {
if (position < 0 || position > count) {
throw std::out_of_range("Invalid position");
}
if (position == 0) {
insertAtHead(data);
} else if (position == count) {
insertAtTail(data);
} else {
Node* newNode = new Node{data, nullptr};
Node* temp = head;
for (int i = 0; i < position - 1; i++) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
count++;
}
}
void deleteAtHead() {
if (head == nullptr) {
throw std::out_of_range("List is empty");
}
Node* temp = head;
head = head->next;
delete temp;
count--;
}
void deleteAtTail() {
if (tail == nullptr) {
throw std::out_of_range("List is empty");
}
if (head == tail) {
delete head;
head = nullptr;
tail = nullptr;
} else {
Node* temp = head;
while (temp->next != tail) {
temp = temp->next;
}
delete tail;
tail = temp;
tail->next = nullptr;
}
count--;
}
void deleteAtPosition(int position) {
if (position < 0 || position >= count) {
throw std::out_of_range("Invalid position");
}
if (position == 0) {
deleteAtHead();
} else if (position == count - 1) {
deleteAtTail();
} else {
Node* temp = head;
for (int i = 0; i < position - 1; i++) {
temp = temp->next;
}
Node* toDelete = temp->next;
temp->next = temp->next->next;
delete toDelete;
count--;
}
}
T& operator[](int position) {
if (position < 0 || position >= count) {
throw std::out_of_range("Invalid position");
}
Node* temp = head;
for (int i = 0; i < position; i++) {
temp = temp->next;
}
return temp->data;
}
void reset() {
current = head;
prev = nullptr;
}
bool hasNext() {
return current != nullptr;
}
T& next() {
if (current == nullptr) {
throw std::out_of_range("End of list");
}
prev = current;
current = current->next;
return prev->data;
}
void copyFrom(const LinkedList<T>& other) {
Node* temp = other.head;
while (temp != nullptr) {
insertAtTail(temp->data);
temp = temp->next;
}
}
LinkedList<T>& operator=(const LinkedList<T>& other) {
if (this != &other) {
Node* temp = head;
while (temp != nullptr) {
Node* toDelete = temp;
temp = temp->next;
delete toDelete;
}
head = nullptr;
tail = nullptr;
count = 0;
current = nullptr;
prev = nullptr;
copyFrom(other);
}
return *this;
}
};
```
下面是测试程序,实现了两个整型链表A和B,本别插入5个元素,然后把B中的元素加入A的尾部:
```cpp
#include <iostream>
#include <stdexcept>
#include "LinkedList.h"
int main() {
try {
LinkedList<int> A;
for (int i = 0; i < 5; i++) {
A.insertAtTail(i);
}
LinkedList<int> B;
for (int i = 5; i < 10; i++) {
B.insertAtTail(i);
}
A.reset();
while (A.hasNext()) {
std::cout << A.next() << " ";
}
std::cout << std::endl;
A = A;
LinkedList<int> C = A;
C.reset();
while (C.hasNext()) {
std::cout << C.next() << " ";
}
std::cout << std::endl;
A.reset();
while (A.hasNext()) {
A.next();
}
B.reset();
while (B.hasNext()) {
A.insertAtTail(B.next());
}
A.reset();
while (A.hasNext()) {
std::cout << A.next() << " ";
}
std::cout << std::endl;
} catch (std::exception& e) {
std::cerr << e.what() << std::endl;
}
return 0;
}
```
阅读全文