使用c++实现线性表的链式存储定义,完成单链表的创建,包含头插法,尾插法,以及插入,删除,查找等常用操作,将线性表逆置,即最后一个节点变成第一个节点,原来倒数第二个节点变成第二个节点,以此类推
时间: 2024-12-13 14:20:59 浏览: 9
线性表的实现_代码(初始化、判断是否为空表、求表长、输出表、插入、删除、查找、修改、清空表、释放表空间、退出
5星 · 资源好评率100%
在C++中,我们可以使用结构体(struct)和指针来实现链表的链式存储。首先,定义一个节点(Node)结构体:
```cpp
#include <iostream>
// 定义链表节点
struct Node {
int data; // 节点数据
Node* next; // 指向下一个节点的指针
};
```
接下来,我们实现单链表的基本操作:
1. **创建链表**:
- 创建一个空链表:
```cpp
Node* createList() {
return nullptr;
}
```
2. **头插法(Insert at the beginning)**:
- 在链表头部插入元素:
```cpp
void insertAtBeginning(Node*& head, int value) {
Node* newNode = new Node{value, head};
head = newNode;
}
```
3. **尾插法(Insert at the end)**:
- 在链表尾部插入元素:
```cpp
void insertAtEnd(Node*& head, int value) {
if (head == nullptr) {
insertAtBeginning(head, value);
return;
}
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = new Node{value, nullptr};
}
```
4. **插入**:
- 插入指定值到特定位置,这里仅示例插入第i个位置:
```cpp
void insert(int position, Node*& head, int value) {
if (position <= 0) return; // 非法位置
Node* newNode = new Node{value, nullptr};
if (position == 1) { // 插入头节点
newNode->next = head;
head = newNode;
} else {
Node* current = head;
for (int i = 1; i < position - 1 && current != nullptr; ++i) {
current = current->next;
}
if (current != nullptr) {
newNode->next = current->next;
current->next = newNode;
} else {
std::cout << "Invalid position." << std::endl;
}
}
}
```
5. **删除**:
- 删除给定值的节点(如果存在),这里仅示例删除值为`value`的第一个节点:
```cpp
void deleteValue(Node*& head, int value) {
if (head == nullptr) return;
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
while (current->next != nullptr && current->next->data != value) {
current = current->next;
}
if (current->next != nullptr) {
Node* temp = current->next;
current->next = temp->next;
delete temp;
} else {
std::cout << "Value not found in the list." << std::endl;
}
}
```
6. **查找**:
- 查找是否存在某个值:
```cpp
bool search(Node* head, int value) {
Node* current = head;
while (current != nullptr) {
if (current->data == value) {
return true;
}
current = current->next;
}
return false;
}
```
7. **逆置链表**:
- 将链表逆置:
```cpp
void reverseList(Node*& head) {
if (head == nullptr || head->next == nullptr) return;
Node* prev = nullptr;
Node* curr = head;
Node* nextTemp = nullptr;
while (curr != nullptr) {
nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
head = prev;
}
```
以上就是单链表的基础操作,包括创建、插入、删除、查找和逆置。请注意,在实际应用中,你需要处理内存管理,例如释放动态分配的内存。
阅读全文