请编写链表的Init、Length、GetElem、Locate、Insert、Delete和CreatList(头插或尾插)七个函数,并编写main函数调用以上函数实现完整的功能。
时间: 2024-09-24 16:01:46 浏览: 40
链表是一种线性数据结构,每个节点包含数据和指向下一个节点的指针。为了实现这个功能,我们可以创建一个Node类表示链表的节点,然后定义一个LinkedList类作为链表的操作工具。以下是用C++编写的简单示例:
```cpp
#include <iostream>
// 定义链表节点
struct Node {
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
class LinkedList {
private:
Node* head; // 链表头节点
int length; // 链表长度
public:
// 初始化链表
LinkedList() : head(nullptr), length(0) {}
// 插入元素到头部
void InsertAtHead(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
length++;
}
// 插入元素到尾部(尾插)
void InsertAtTail(int value) {
if (head == nullptr) {
head = new Node(value);
length++;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = new Node(value);
length++;
}
}
// 获取链表长度
int Length() const {
return length;
}
// 获取指定索引处的元素
int GetElement(int index) const {
if (index >= 0 && index < length) {
Node* current = head;
for (int i = 0; i < index; i++) {
current = current->next;
}
return current->data;
}
throw std::out_of_range("Index out of range.");
}
// 查找元素位置(若存在则返回,不存在返回-1)
int Locate(int value) const {
Node* current = head;
int position = 0;
while (current != nullptr) {
if (current->data == value) {
return position;
}
current = current->next;
position++;
}
return -1;
}
// 删除指定位置的元素(从0开始计数)
bool Delete(int index) {
if (index >= 0 && index < length - 1) {
Node* current = head;
for (int i = 0; i < index; i++) {
current = current->next;
}
current->next = current->next->next;
delete current->next;
length--;
return true;
}
return false;
}
// 主函数演示链表操作
static void MainFunction() {
LinkedList list;
// 示例操作
list.InsertAtHead(5); // 添加头元素
list.InsertAtTail(3); // 添加尾元素
std::cout << "Length: " << list.Length() << "\n";
std::cout << "Element at 0: " << list.GetElement(0) << "\n";
std::cout << "Located position of 3: " << list.Locate(3) << "\n";
list.Delete(0); // 删除第一个元素
std::cout << "After deletion:\n";
list.PrintList(); // 自定义打印函数(仅示例)
阅读全文