请设计一个单链表的存储结构,并实现单链表中以下基本运算算法,单链表的结构和算法存放在头文件中 (1)初始化单链表(带头结点) (2)单链表中当前结点后面插入一个新结点 (3)删除单链表当前结点 (4)输出单链表的元素和长度 (5)判断单链表是否为空
时间: 2024-10-18 21:12:54 浏览: 32
C语言第1讲-程序和程序设计_算法_结构化程序设计方法.zip-综合文档
首先,我们设计一个简单的单链表节点结构体,包含数据域data和指向下一个节点的指针next:
```cpp
// 定义单链表节点
struct ListNode {
int data; // 数据域
ListNode* next; // 指向下一个节点的指针
};
```
接下来,我们在头文件中定义单链表相关的函数:
```cpp
// 头文件:single_linked_list.h
#ifndef SINGLE_LINKED_LIST_H
#define SINGLE_LINKED_LIST_H
#include <iostream>
class SingleLinkedList {
public:
// 初始化单链表,头结点默认值设为nullptr
SingleLinkedList();
// 插入新节点到链表尾部
void insertNode(int value);
// 删除指定节点(通过引用)
void deleteNode(ListNode*& current);
// 输出链表元素并打印长度
void printList();
// 判断链表是否为空
bool isEmpty() const;
private:
ListNode* head; // 链表头指针
};
#endif // SINGLE_LINKED_LIST_H
```
**实现部分**:
```cpp
// 单链表.cpp
#include "single_linked_list.h"
SingleLinkedList::SingleLinkedList() : head(nullptr) {}
void SingleLinkedList::insertNode(int value) {
if (head == nullptr) {
head = new ListNode{value, nullptr};
} else {
ListNode* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = new ListNode{value, nullptr};
}
}
void SingleLinkedList::deleteNode(ListNode*& current) {
if (current == nullptr || current->next == nullptr) {
return; // 如果空节点或只有一个节点,则直接返回
}
ListNode* nextTemp = current->next;
current->next = nextTemp->next;
delete nextTemp;
}
void SingleLinkedList::printList() {
ListNode* temp = head;
std::cout << "Linked list elements: ";
while (temp != nullptr) {
std::cout << temp->data << " -> ";
temp = temp->next;
}
std::cout << "NULL\n";
std::cout << "Length: " << countNodes(head) << "\n";
}
bool SingleLinkedList::isEmpty() const {
return head == nullptr;
}
int SingleLinkedList::countNodes(ListNode* node) {
int count = 0;
while (node != nullptr) {
++count;
node = node->next;
}
return count;
}
```
**示例如何使用**:
```cpp
int main() {
SingleLinkedList list;
list.insertNode(1);
list.insertNode(2);
list.insertNode(3);
list.printList();
list.deleteNode(list.head); // 删除第一个节点
list.printList();
std::cout << "Is empty? " << (list.isEmpty() ? "Yes" : "No") << "\n";
return 0;
}
```
阅读全文