实现单循环链表的初始化、求数据元素个数、插入、删除、取数据元素等操作;用插入法建立带头结点的单循环链表;设计一个测试主函数验证所设计单循环链表的正确性的完整代码
时间: 2024-10-12 14:17:23 浏览: 22
单循环链表(带头结点和不带头结点)
5星 · 资源好评率100%
在实现单循环链表的操作中,我们需要创建一个节点结构,包含数据域和指向下一个节点的指针。以下是关键操作的实现:
```c++
// 定义单循环链表节点结构
typedef struct Node {
int data;
struct Node* next;
} Node;
// 初始化链表(如果头节点已存在则跳过)
void initCircularList(Node** head) {
if (*head == NULL) {
*head = new Node();
(*head)->data = 0; // 或者设置一个初始值
(*head)->next = *head; // 设置形成环
}
}
// 求数据元素个数(考虑到循环特性,需要一直遍历到头节点)
int countElements(Node* head) {
int count = 0;
Node* current = head;
while (current != head->next) { // 避免死循环
count++;
current = current->next;
}
return count;
}
// 插入数据元素(指定位置)
void insertNode(Node** head, int position, int value) {
Node* newNode = new Node();
newNode->data = value;
if (position == 0) {
newNode->next = *head;
*head = newNode;
newNode->next = head->next;
} else {
Node* prev = head;
for (int i = 0; i < position - 1 && prev != head->next; ++i) {
prev = prev->next;
}
newNode->next = prev->next;
prev->next = newNode;
}
}
// 删除节点(指定位置)
void deleteNode(Node** head, int position) {
if (position == 0 && *head != NULL) {
Node* temp = *head;
*head = (*head)->next;
delete temp;
} else {
Node* current = *head;
for (int i = 0; i < position - 1 && current != head->next; ++i) {
current = current->next;
}
if (current != head->next) {
current->next = current->next->next;
}
}
}
// 取数据元素(指定位置)
int getData(Node* head, int position) {
if (position == 0) {
return head->data;
} else {
Node* current = head;
for (int i = 0; i < position - 1; ++i) {
current = current->next;
}
return current->data;
}
}
// 测试主函数
int main() {
Node* head = NULL;
initCircularList(&head);
// 插入、删除、获取数据操作...
insertNode(&head, 0, 1); // 插入第一个元素
int numElements = countElements(head);
std::cout << "Number of elements: " << numElements << std::endl;
// ...其他测试操作...
deleteNode(&head, 0); // 删除第一个元素
// 通过循环检查链表元素是否正确
for (int i = 0; i < numElements; ++i) {
int expectedData = i == 0 ? 0 : getData(head, i);
int actualData = getData(head, i);
if (expectedData != actualData) {
std::cerr << "Test failed at position " << i << ": Expected " << expectedData << ", got " << actualData << std::endl;
return 1;
}
}
std::cout << "All tests passed." << std::endl;
return 0;
}
```
这个代码实现了单循环链表的初始化、求元素个数、插入、删除和取数据操作,并提供了一个简单的测试主函数。请注意,这里的测试仅限于插入和删除后的数据一致性检查,实际应用中可能还需要更全面的测试。
阅读全文