2、设计一个通用链表类,要求如下: 1)数据成员包含头指针、尾指针、链表中节点个数、顺序访问中当前节点指针和当前节点前一个节点的指针; 2)主要的成员函数包含:生成节点(在链表头、尾以及任意位置)、插入节点、删除节点、访问/修改节点、遍历链表,以及一些辅助函数等; 3)能实现两个链表的复制; 4)能实现两个链表对象的赋值; 5)在测试程序中定义两个整型链表A和B,本别插入5个元素,然后把B中的元素加入A的尾部。
时间: 2024-03-14 17:46:26 浏览: 62
试写出一个计算单链表中结点个数的算法,其中指针p指向该链表的第一个结点。
下面是一个设计通用链表类的示例代码,其中包含了上述要求的实现:
```cpp
#include <iostream>
using namespace std;
template <class T>
class ListNode {
public:
T data;
ListNode<T>* next;
ListNode(T item, ListNode<T>* ptr = NULL) {
data = item;
next = ptr;
}
};
template <class T>
class LinkedList {
private:
ListNode<T>* head;
ListNode<T>* tail;
ListNode<T>* current;
ListNode<T>* previous;
int size;
public:
LinkedList();
LinkedList(const LinkedList<T>& rhs);
~LinkedList();
LinkedList<T>& operator=(const LinkedList<T>& rhs);
void clear();
int getSize() const;
bool isEmpty() const;
void insertAtFront(const T& item);
void insertAtBack(const T& item);
bool insert(const T& item, int index);
bool remove(int index);
bool get(int index, T& item) const;
bool set(int index, const T& item);
void traverse() const;
};
template <class T>
LinkedList<T>::LinkedList() {
head = tail = current = previous = NULL;
size = 0;
}
template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& rhs) {
head = tail = current = previous = NULL;
size = 0;
ListNode<T>* rhsCurrent = rhs.head;
while (rhsCurrent) {
insertAtBack(rhsCurrent->data);
rhsCurrent = rhsCurrent->next;
}
}
template <class T>
LinkedList<T>::~LinkedList() {
clear();
}
template <class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& rhs) {
if (this != &rhs) {
clear();
ListNode<T>* rhsCurrent = rhs.head;
while (rhsCurrent) {
insertAtBack(rhsCurrent->data);
rhsCurrent = rhsCurrent->next;
}
}
return *this;
}
template <class T>
void LinkedList<T>::clear() {
while (head) {
ListNode<T>* temp = head;
head = head->next;
delete temp;
}
tail = current = previous = NULL;
size = 0;
}
template <class T>
int LinkedList<T>::getSize() const {
return size;
}
template <class T>
bool LinkedList<T>::isEmpty() const {
return size == 0;
}
template <class T>
void LinkedList<T>::insertAtFront(const T& item) {
if (isEmpty()) {
head = tail = new ListNode<T>(item);
} else {
head = new ListNode<T>(item, head);
}
size++;
}
template <class T>
void LinkedList<T>::insertAtBack(const T& item) {
if (isEmpty()) {
head = tail = new ListNode<T>(item);
} else {
tail = tail->next = new ListNode<T>(item);
}
size++;
}
template <class T>
bool LinkedList<T>::insert(const T& item, int index) {
if (index < 0 || index > size) {
return false;
}
if (index == 0) {
insertAtFront(item);
} else if (index == size) {
insertAtBack(item);
} else {
ListNode<T>* newNode = new ListNode<T>(item);
ListNode<T>* current = head;
for (int i = 0; i < index - 1; i++) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
size++;
}
return true;
}
template <class T>
bool LinkedList<T>::remove(int index) {
if (index < 0 || index >= size) {
return false;
}
ListNode<T>* temp;
if (index == 0) {
temp = head;
head = head->next;
if (!head) {
tail = NULL;
}
} else {
ListNode<T>* current = head;
for (int i = 0; i < index - 1; i++) {
current = current->next;
}
temp = current->next;
current->next = temp->next;
if (!current->next) {
tail = current;
}
}
delete temp;
size--;
return true;
}
template <class T>
bool LinkedList<T>::get(int index, T& item) const {
if (index < 0 || index >= size) {
return false;
}
ListNode<T>* current = head;
for (int i = 0; i < index; i++) {
current = current->next;
}
item = current->data;
return true;
}
template <class T>
bool LinkedList<T>::set(int index, const T& item) {
if (index < 0 || index >= size) {
return false;
}
ListNode<T>* current = head;
for (int i = 0; i < index; i++) {
current = current->next;
}
current->data = item;
return true;
}
template <class T>
void LinkedList<T>::traverse() const {
current = head;
while (current) {
cout << current->data << " ";
previous = current;
current = current->next;
}
cout << endl;
}
int main() {
LinkedList<int> A;
LinkedList<int> B;
for (int i = 1; i <= 5; i++) {
A.insertAtBack(i);
B.insertAtBack(i + 5);
}
ListNode<int>* currentB = B.head;
while (currentB) {
A.insertAtBack(currentB->data);
currentB = currentB->next;
}
A.traverse();
return 0;
}
```
在这个示例代码中,通用链表类被定义为一个模板类,可以存储任意类型的数据。该类中的数据成员包括头指针、尾指针、链表中节点个数、顺序访问中当前节点指针和当前节点前一个节点的指针。主要的成员函数包括:生成节点(在链表头、尾以及任意位置)、插入节点、删除节点、访问/修改节点、遍历链表,以及一些辅助函数等。此外,该类还实现了两个链表的复制和赋值操作。
在测试程序中,定义了两个整型链表A和B,分别插入5个元素。然后将B中的元素加入A的尾部,最后输出A链表的内容。
阅读全文