用c代码编写差分链表的插入模块和删除模块
时间: 2024-09-09 09:14:38 浏览: 36
差分链表是一种特殊的数据结构,它是一种链表的优化形式,用于高效地处理数组的连续区间修改问题。在差分链表中,每个节点表示一个区间的变化量,而不是直接存储数组元素的值。
插入模块:
在差分链表中插入一个元素,实际上是将一个区间内所有元素的值增加一个特定的差值。例如,如果我们想在差分链表中插入一个值为`val`的元素到位置`i`(位置从1开始计数),那么我们需要在位置`i`的节点增加`val`,同时在位置`i+1`的节点减少`val`。
下面是一个插入模块的C代码示例:
```c
typedef struct DiffNode {
int index; // 当前节点表示的数组索引位置
int diff; // 当前节点表示的差值
struct DiffNode *next; // 指向下一个节点的指针
} DiffNode;
void insertAt(DiffNode **head, int i, int val) {
DiffNode *newNode = (DiffNode *)malloc(sizeof(DiffNode));
newNode->index = i;
newNode->diff = val;
newNode->next = NULL;
if (*head == NULL || (*head)->index > i) {
// 插入到链表头部或当前节点之前
newNode->next = *head;
*head = newNode;
} else {
DiffNode *current = *head;
while (current->next != NULL && current->next->index < i) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
```
删除模块:
在差分链表中删除一个元素,通常意味着要删除或者合并包含该元素的区间。如果在位置`i`处的元素值为`val`,则需要在位置`i`的节点减少`val`,在位置`i+1`的节点增加`val`。如果这个操作导致`diff`变为0,则需要删除相应的节点。
下面是一个删除模块的C代码示例:
```c
void deleteAt(DiffNode **head, int i, int val) {
if (*head == NULL) return;
DiffNode *current = *head;
DiffNode *prev = NULL;
// 查找位置i的节点
while (current != NULL && current->index < i) {
prev = current;
current = current->next;
}
if (current == NULL || current->index != i) return; // 没有找到位置i
current->diff -= val; // 减少当前位置的差值
if (current->diff == 0) {
// 删除节点
if (prev == NULL) {
*head = current->next;
} else {
prev->next = current->next;
}
free(current);
}
}
```