设计一个c语言算法实现单链表中所有值的去重,要有详细注释
时间: 2024-05-04 14:16:45 浏览: 119
基于C语言实现博弈论算法源码+详细注释.zip
好的,以下是C语言算法实现单链表中所有值的去重,包含详细注释:
```c
#include <stdio.h>
#include <stdlib.h>
// 链表结构体
typedef struct Node {
int data; // 数据域
struct Node* next; // 指针域,指向下一个节点
} Node;
// 创建一个新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 分配节点内存
newNode->data = data; // 赋值数据域
newNode->next = NULL; // 初始化指针域
return newNode;
}
// 插入新节点到链表尾部
void insert(Node* head, int data) {
Node* newNode = createNode(data); // 创建新节点
Node* p = head;
while (p->next != NULL) { // 找到链表尾部
p = p->next;
}
p->next = newNode; // 将新节点插入到链表尾部
}
// 打印链表
void printList(Node* head) {
Node* p = head->next; // 从头节点的下一个节点开始遍历
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 删除链表中的重复元素
void removeDuplicates(Node* head) {
Node* p = head->next; // 从头节点的下一个节点开始遍历
while (p->next != NULL) { // 遍历到链表倒数第二个元素
Node* q = p;
while (q->next != NULL) { // 遍历到链表最后一个元素
if (q->next->data == p->data) { // 如果出现重复元素
Node* temp = q->next; // 记录要删除的节点
q->next = q->next->next; // 删除节点
free(temp); // 释放内存
} else {
q = q->next;
}
}
p = p->next;
}
}
int main() {
Node* head = (Node*)malloc(sizeof(Node)); // 创建头节点
head->next = NULL; // 初始化指针域
// 插入元素
insert(head, 1);
insert(head, 2);
insert(head, 3);
insert(head, 2);
insert(head, 4);
insert(head, 1);
printf("原始链表:");
printList(head);
removeDuplicates(head); // 删除重复元素
printf("去重后的链表:");
printList(head);
return 0;
}
```
注释中详细解释了每个函数的功能和实现细节,该算法的时间复杂度为O(n^2),并且不改变链表的顺序。
阅读全文