线性表链式存储结构下基本操作的实现(初始化、建表、取值、查找、插入、删除、两个非递减有序链表的归并等)。c++
时间: 2024-10-10 10:17:22 浏览: 12
线性表的链式存储结构是一种动态数据结构,它通过节点之间的链接来组织元素,而不是连续的内存地址。以下是基本操作在C++中的实现:
1. **初始化** (创建空链表):
```cpp
struct Node {
int data;
Node* next;
};
Node* createList() {
return nullptr; // 创建一个空头指针表示空链表
}
```
2. **建表** (插入元素到链表尾部):
```cpp
void insert(Node*& head, int value) {
if (!head) {
head = new Node{value, nullptr};
} else {
Node* newNode = new Node{value, nullptr};
newNode->next = head;
head = newNode;
}
}
```
3. **取值** (访问特定位置的元素):
```cpp
int getValue(const Node* node, size_t index) {
if (index == 0 && node != nullptr) {
return node->data;
} else {
return -1; // 如果越界或链表为空,返回错误码
}
}
```
4. **查找** (定位特定元素):
```cpp
bool search(Node* head, int value) {
Node* current = head;
while (current != nullptr) {
if (current->data == value) {
return true;
}
current = current->next;
}
return false;
}
```
5. **插入** (指定位置插入元素):
```cpp
void insertAt(Node*& head, int value, size_t position) {
if (position == 0) {
insert(head, value);
} else {
Node* prev = head;
for (size_t i = 1; i < position && prev != nullptr; ++i) {
prev = prev->next;
}
if (prev != nullptr) {
Node* newNode = new Node{value, prev->next};
prev->next = newNode;
} else {
cout << "Invalid position" << endl;
}
}
}
```
6. **删除** (移除特定元素):
```cpp
void remove(Node*& head, int value) {
if (head != nullptr) {
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
} else {
Node* current = head;
while (current->next != nullptr && current->next->data != value) {
current = current->next;
}
if (current->next != nullptr) {
Node* toRemove = current->next;
current->next = current->next->next;
delete toRemove;
}
}
}
}
```
7. **两个非递减有序链表的归并** (合并两个已排序链表):
```cpp
Node* mergeSortedLists(Node* list1, Node* list2) {
Node* result = (list1 > list2)? list2 : list1;
Node* curr1 = (list1 > list2)? list1 : nullptr;
Node* curr2 = (list2 > list1)? list2 : nullptr;
while (curr1 && curr2) {
if (curr1->data <= curr2->data) {
result->next = curr1;
curr1 = curr1->next;
} else {
result->next = curr2;
curr2 = curr2->next;
}
result = result->next;
}
if (curr1) {
result->next = curr1;
} else if (curr2) {
result->next = curr2;
}
return result->next;
}
```