引言
在C语言编程中,容器(如数组、链表、树等)是处理数据的重要工具。然而,随着程序的运行,容器中可能会积累不再需要的数据,导致数据冗余,影响系统效率。因此,掌握容器删除技巧对于维护数据结构和提升系统性能至关重要。本文将详细介绍C语言中容器删除的技巧,帮助读者告别数据冗余,提升系统效率。
一、数组删除技巧
1.1 数组删除概述
数组是C语言中最常用的容器之一。删除数组中的元素需要注意保持数组的连续性。
1.2 删除单个元素
以下是一个删除数组中单个元素的示例代码:
#include <stdio.h>
void deleteElement(int *array, int size, int index) {
if (index < 0 || index >= size) {
printf("Index out of bounds!\n");
return;
}
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
}
size--;
}
int main() {
int array[] = {1, 2, 3, 4, 5};
int size = sizeof(array) / sizeof(array[0]);
int index = 2; // 删除索引为2的元素
printf("Original array: ");
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
deleteElement(array, size, index);
printf("Modified array: ");
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
return 0;
}
1.3 删除多个元素
删除多个元素时,需要计算删除元素后的新数组大小,并重新分配内存。
#include <stdio.h>
#include <stdlib.h>
int *deleteMultipleElements(int *array, int size, int *indices, int numElements) {
int *tempArray = (int *)malloc(size * sizeof(int));
if (tempArray == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
int tempIndex = 0;
for (int i = 0; i < size; i++) {
int shouldDelete = 0;
for (int j = 0; j < numElements; j++) {
if (i == indices[j]) {
shouldDelete = 1;
break;
}
}
if (!shouldDelete) {
tempArray[tempIndex++] = array[i];
}
}
int newSize = size - numElements;
int *newArray = (int *)realloc(tempArray, newSize * sizeof(int));
if (newArray == NULL) {
free(tempArray);
printf("Memory reallocation failed!\n");
return NULL;
}
return newArray;
}
int main() {
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int size = sizeof(array) / sizeof(array[0]);
int indices[] = {2, 4, 6}; // 删除索引为2、4、6的元素
int numElements = sizeof(indices) / sizeof(indices[0]);
printf("Original array: ");
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
int *newArray = deleteMultipleElements(array, size, indices, numElements);
printf("Modified array: ");
for (int i = 0; i < sizeof(newArray) / sizeof(newArray[0]); i++) {
printf("%d ", newArray[i]);
}
printf("\n");
free(newArray);
return 0;
}
二、链表删除技巧
2.1 链表删除概述
链表是一种动态数据结构,删除元素时需要修改指针。
2.2 删除单个元素
以下是一个删除链表中单个元素的示例代码:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
void deleteElement(Node **head, int key) {
Node *temp = *head, *prev = NULL;
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
int main() {
Node *head = (Node *)malloc(sizeof(Node));
head->data = 1;
head->next = NULL;
Node *second = (Node *)malloc(sizeof(Node));
second->data = 2;
second->next = NULL;
Node *third = (Node *)malloc(sizeof(Node));
third->data = 3;
third->next = NULL;
head->next = second;
second->next = third;
printf("Original linked list: ");
Node *temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
deleteElement(&head, 2);
printf("Modified linked list: ");
temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
return 0;
}
2.3 删除多个元素
删除多个元素时,需要遍历链表,找到所有需要删除的节点,并修改指针。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
void deleteMultipleElements(Node **head, int *keys, int numKeys) {
Node *temp = *head, *prev = NULL;
while (temp != NULL) {
for (int i = 0; i < numKeys; i++) {
if (temp->data == keys[i]) {
if (prev == NULL) {
*head = temp->next;
free(temp);
temp = *head;
} else {
prev->next = temp->next;
free(temp);
temp = prev->next;
}
break;
}
}
if (temp != NULL) {
prev = temp;
temp = temp->next;
}
}
}
int main() {
Node *head = (Node *)malloc(sizeof(Node));
head->data = 1;
head->next = NULL;
Node *second = (Node *)malloc(sizeof(Node));
second->data = 2;
second->next = NULL;
Node *third = (Node *)malloc(sizeof(Node));
third->data = 3;
third->next = NULL;
Node *fourth = (Node *)malloc(sizeof(Node));
fourth->data = 4;
fourth->next = NULL;
Node *fifth = (Node *)malloc(sizeof(Node));
fifth->data = 5;
fifth->next = NULL;
head->next = second;
second->next = third;
third->next = fourth;
fourth->next = fifth;
printf("Original linked list: ");
Node *temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
int keys[] = {2, 4};
int numKeys = sizeof(keys) / sizeof(keys[0]);
deleteMultipleElements(&head, keys, numKeys);
printf("Modified linked list: ");
temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
return 0;
}
三、树删除技巧
3.1 树删除概述
树是一种非线性数据结构,删除节点时需要考虑子节点和父节点的指针。
3.2 删除单个节点
以下是一个删除二叉树中单个节点的示例代码:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
Node *deleteNode(Node *root, int key) {
if (root == NULL) return root;
if (key < root->data) {
root->left = deleteNode(root->left, key);
} else if (key > root->data) {
root->right = deleteNode(root->right, key);
} else {
if (root->left == NULL) {
Node *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
Node *temp = root->left;
free(root);
return temp;
}
Node *temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
Node *minValueNode(Node *node) {
Node *current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
int main() {
Node *root = (Node *)malloc(sizeof(Node));
root->data = 50;
root->left = NULL;
root->right = NULL;
root->left = (Node *)malloc(sizeof(Node));
root->left->data = 30;
root->left->left = NULL;
root->left->right = NULL;
root->right = (Node *)malloc(sizeof(Node));
root->right->data = 80;
root->right->left = NULL;
root->right->right = NULL;
root->left->left = (Node *)malloc(sizeof(Node));
root->left->left->data = 20;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (Node *)malloc(sizeof(Node));
root->left->right->data = 40;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right->right = (Node *)malloc(sizeof(Node));
root->right->right->data = 90;
root->right->right->left = NULL;
root->right->right->right = NULL;
printf("Original binary tree: \n");
printInorder(root);
root = deleteNode(root, 30);
printf("\nModified binary tree: \n");
printInorder(root);
return 0;
}
void printInorder(Node *root) {
if (root != NULL) {
printInorder(root->left);
printf("%d ", root->data);
printInorder(root->right);
}
}
3.3 删除多个节点
删除多个节点时,需要遍历树,找到所有需要删除的节点,并修改指针。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
void deleteMultipleNodes(Node **root, int *keys, int numKeys) {
Node *temp = *root;
while (temp != NULL) {
for (int i = 0; i < numKeys; i++) {
if (temp->data == keys[i]) {
if (temp->left == NULL && temp->right == NULL) {
free(temp);
temp = temp->next;
} else if (temp->left == NULL) {
Node *nextNode = temp->right;
free(temp);
temp = nextNode;
} else if (temp->right == NULL) {
Node *nextNode = temp->left;
free(temp);
temp = nextNode;
} else {
Node *nextNode = minValueNode(temp->right);
temp->data = nextNode->data;
temp->right = deleteNode(temp->right, nextNode->data);
}
break;
}
}
if (temp != NULL) {
temp = temp->next;
}
}
}
int main() {
Node *root = (Node *)malloc(sizeof(Node));
root->data = 50;
root->left = NULL;
root->right = NULL;
root->left = (Node *)malloc(sizeof(Node));
root->left->data = 30;
root->left->left = NULL;
root->left->right = NULL;
root->right = (Node *)malloc(sizeof(Node));
root->right->data = 80;
root->right->left = NULL;
root->right->right = NULL;
root->left->left = (Node *)malloc(sizeof(Node));
root->left->left->data = 20;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (Node *)malloc(sizeof(Node));
root->left->right->data = 40;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right->right = (Node *)malloc(sizeof(Node));
root->right->right->data = 90;
root->right->right->left = NULL;
root->right->right->right = NULL;
printf("Original binary tree: \n");
printInorder(root);
int keys[] = {30, 80};
int numKeys = sizeof(keys) / sizeof(keys[0]);
deleteMultipleNodes(&root, keys, numKeys);
printf("\nModified binary tree: \n");
printInorder(root);
return 0;
}
void printInorder(Node *root) {
if (root != NULL) {
printInorder(root->left);
printf("%d ", root->data);
printInorder(root->right);
}
}
总结
本文介绍了C语言中数组、链表和树的删除技巧,帮助读者告别数据冗余,提升系统效率。在实际编程中,根据具体需求选择合适的数据结构和删除方法,可以有效提高程序性能。希望本文对您有所帮助!
