用c++定义单链表类,完成单链表的相关操作: (1) 显示输出一个已经生成的链表; (2) 对一个空表插入链表项,插入的新表被放在链表的头部,即前插入; (3) 对一个空表追加链表项,追加的新链表项被放在表尾部; (4) 两个链表相连接,既将一个链表接在另一个链表的尾部; (5) 将一个链表的数据项逆向输出; (6) 求一个链表的数据项数即长度。 提示:首先定义链表项类,包含一个int类型数据域和指针域;然后再定义单链表类,并链表类作为链表项类的友元类,来完成上述的单链表类相关操作
时间: 2023-07-10 08:22:13 浏览: 126
以下是用 C++ 定义的单链表类,实现了题目所要求的各种操作:
```cpp
#include <iostream>
using namespace std;
// 链表项类
class ListNode {
public:
int val;
ListNode* next;
ListNode(int val = 0, ListNode* next = nullptr) {
this->val = val;
this->next = next;
}
};
// 单链表类
class LinkedList {
private:
ListNode* head;
int size;
public:
LinkedList() {
head = nullptr;
size = 0;
}
~LinkedList() {
ListNode* p = head;
while (p != nullptr) {
ListNode* q = p->next;
delete p;
p = q;
}
}
// 显示输出链表
void display() {
ListNode* p = head;
while (p != nullptr) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
}
// 在链表头插入新项
void insertFront(int val) {
ListNode* p = new ListNode(val, head);
head = p;
size++;
}
// 在链表尾追加新项
void append(int val) {
if (head == nullptr) {
head = new ListNode(val);
} else {
ListNode* p = head;
while (p->next != nullptr) {
p = p->next;
}
p->next = new ListNode(val);
}
size++;
}
// 将另一个链表连接到本链表尾部
void concatenate(LinkedList& other) {
if (head == nullptr) {
head = other.head;
} else {
ListNode* p = head;
while (p->next != nullptr) {
p = p->next;
}
p->next = other.head;
}
size += other.size;
other.head = nullptr;
other.size = 0;
}
// 将链表逆序输出
void reverse() {
ListNode* p = head;
ListNode* q = nullptr;
while (p != nullptr) {
ListNode* r = p->next;
p->next = q;
q = p;
p = r;
}
head = q;
}
// 求链表长度
int getSize() {
return size;
}
};
```
下面是一个测试程序,可以用来验证上述单链表类的各种操作是否正确:
```cpp
int main() {
LinkedList lst1;
lst1.append(1);
lst1.append(2);
lst1.append(3);
lst1.display(); // 1 2 3
lst1.insertFront(0);
lst1.display(); // 0 1 2 3
LinkedList lst2;
lst2.append(4);
lst2.append(5);
lst2.append(6);
lst2.display(); // 4 5 6
lst1.concatenate(lst2);
lst1.display(); // 0 1 2 3 4 5 6
lst1.reverse();
lst1.display(); // 6 5 4 3 2 1 0
cout << lst1.getSize() << endl; // 7
return 0;
}
```
阅读全文