设计一个单链表,实现单链表初始化、求数据元素个数操作、插入、删除、取数据元素、判非空、倒序输出操作。
时间: 2023-11-27 17:04:55 浏览: 90
单链表是一种常见的线性数据结构,它由一个头节点和若干个数据节点组成。每个节点都包含一个数据元素和一个指向下一个节点的指针。
以下是单链表的基本实现:
```c++
#include <iostream>
using namespace std;
// 定义节点结构体
struct Node {
int data;
Node* next;
};
// 单链表类
class LinkedList {
public:
LinkedList() {
// 初始化头节点
head = new Node();
head->next = nullptr;
}
~LinkedList() {
// 释放动态分配的内存
Node* p = head;
while (p != nullptr) {
Node* q = p;
p = p->next;
delete q;
}
}
// 求数据元素个数
int size() {
int count = 0;
Node* p = head->next;
while (p != nullptr) {
count++;
p = p->next;
}
return count;
}
// 插入数据元素
void insert(int value) {
Node* p = new Node();
p->data = value;
p->next = head->next;
head->next = p;
}
// 删除数据元素
void remove(int value) {
Node* p = head->next;
Node* q = head;
while (p != nullptr) {
if (p->data == value) {
q->next = p->next;
delete p;
return;
}
q = p;
p = p->next;
}
}
// 取数据元素
int get(int index) {
Node* p = head->next;
for (int i = 0; i < index; i++) {
p = p->next;
}
return p->data;
}
// 判非空
bool isEmpty() {
return head->next == nullptr;
}
// 倒序输出
void reversePrint() {
Node* p = head->next;
int size = this->size();
int* arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = p->data;
p = p->next;
}
for (int i = size - 1; i >= 0; i--) {
cout << arr[i] << " ";
}
cout << endl;
delete[] arr;
}
private:
Node* head;
};
int main() {
LinkedList list;
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
list.insert(5);
cout << "size: " << list.size() << endl;
list.remove(3);
cout << "size: " << list.size() << endl;
cout << "get(0): " << list.get(0) << endl;
cout << "get(1): " << list.get(1) << endl;
cout << "get(2): " << list.get(2) << endl;
cout << "isEmpty: " << (list.isEmpty() ? "true" : "false") << endl;
list.reversePrint();
return 0;
}
```
在该实现中,我们使用了一个头节点来避免需要对链表进行特判。头节点的数据元素没有实际意义,只是为了方便操作而添加的。
阅读全文