设计整数单链表的基本运算程序,并用相关数据进行测试。
时间: 2024-10-09 08:00:57 浏览: 17
设计一个整数单链表的基本运算程序通常包括以下几个核心功能:
1. **创建节点** (Node creation): 定义一个节点结构体,包含一个整数值和指向下一个节点的指针。
```c++
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};
```
2. **初始化链表** (List initialization): 创建一个空链表。
```c++
ListNode* createEmptyList() {
return nullptr;
}
```
3. **插入元素** (Insertion): 向链表中添加新节点。
```c++
ListNode* insertIntoList(ListNode* head, int value) {
ListNode* newNode = new ListNode(value);
if (head == nullptr) {
head = newNode;
} else {
ListNode* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
return head;
}
```
4. **删除元素** (Deletion): 删除链表中指定值的节点。
```c++
void deleteFromList(ListNode*& head, int value) {
if (head == nullptr) {
return;
}
if (head->val == value) {
ListNode* temp = head;
head = head->next;
delete temp;
return;
}
ListNode* current = head;
while (current->next != nullptr && current->next->val != value) {
current = current->next;
}
if (current->next != nullptr) {
ListNode* temp = current->next;
current->next = current->next->next;
delete temp;
}
}
```
5. **查找元素** (Search): 搜索链表中是否存在特定值。
```c++
bool searchInList(ListNode* head, int value) {
ListNode* current = head;
while (current != nullptr) {
if (current->val == value) {
return true;
}
current = current->next;
}
return false;
}
```
6. **遍历链表** (Traversal): 输出链表的所有元素。
```c++
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
std::cout << current->val << " ";
current = current->next;
}
std::cout << std::endl;
}
```
测试示例:
```c++
int main() {
ListNode* list = createEmptyList();
insertIntoList(list, 10);
insertIntoList(list, 20);
insertIntoList(list, 30);
printList(list); // 输出: 10 20 30
deleteFromList(list, 20);
printList(list); // 输出: 10 30
std::cout << (searchInList(list, 20) ? "Found" : "Not Found") << std::endl; // 输出: Not Found
return 0;
}
```
阅读全文