线性表链式存储结构下基本操作的实现(初始化、建表、取值、查找、插入、删除、两个非递减有序链表的归并等)。
时间: 2024-10-10 15:17:08 浏览: 18
线性表的链式存储结构是一种动态的数据结构,其主要特点是数据元素之间通过链接(指针)相连。以下是链表中一些基本操作的实现:
1. **初始化**:
初始化一个空链表,创建一个链表节点,并将其头结点设置为`NULL`。
```c++
struct Node {
int data;
Node* next;
};
Node* createList() {
return nullptr; // 创建一个空链表
}
```
2. **建表**:
对于给定的数据序列,遍历并创建新节点,然后连接它们。
```c++
void buildList(Node** head, const std::vector<int>& data) {
*head = new Node{data[0], nullptr};
for (int i = 1; i < data.size(); i++) {
Node* newNode = new Node{data[i], *head};
*head = newNode;
}
}
```
3. **取值**:
节点访问通过指针逐个进行,直到找到目标位置。
```c++
int getValue(Node* current) {
if (current != nullptr) {
return current->data;
} else {
return -1; // 如果到达空指针,表示未找到
}
}
```
4. **查找**:
从头开始,如果数据匹配则返回,不匹配继续向下。
```c++
Node* findValue(Node* head, int value) {
while (head != nullptr && head->data != value) {
head = head->next;
}
return head;
}
```
5. **插入**:
在指定位置插入新节点,通常需要处理边界条件。
```c++
void insertValue(Node** head, int value, int position) {
Node* newNode = new Node{value, nullptr};
if (position == 0) {
newNode->next = *head;
*head = newNode;
} else {
Node* current = *head;
for (int i = 0; i < position - 1 && current != nullptr; i++, current = current->next) {}
newNode->next = current->next;
current->next = newNode;
}
}
```
6. **删除**:
删除特定位置或特定值的节点,同样要考虑边界条件。
```c++
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* toDelete = current->next;
current->next = current->next->next;
delete toDelete;
}
}
```
7. **合并两个非递减有序链表**:
可以采用双指针法,比较当前节点的值,将较小的那个放入结果链表。
```c++
Node* mergeLists(Node* list1, Node* list2) {
Node* resultHead = nullptr, *resultTail = nullptr;
while (list1 && list2) {
if (list1->data <= list2->data) {
if (!resultHead) {
resultHead = resultTail = list1;
} else {
resultTail->next = list1;
resultTail = list1;
}
list1 = list1->next;
} else {
if (!resultHead) {
resultHead = resultTail = list2;
} else {
resultTail->next = list2;
resultTail = list2;
}
list2 = list2->next;
}
}
if (list1) {
resultTail->next = list1;
} else {
resultTail->next = list2;
}
return resultHead;
}