指针和数组
-
数组的用途:
- 固定大小的存储: 数组用于存储固定大小的一组相同类型的元素。数组的大小在声明时必须指定，并且在程序运行期间不能改变。
- 访问效率高: 数组允许通过下标进行快速访问，时间复杂度为 O(1)。
- 内存连续性: 数组的元素在内存中是连续存储的，这对于某些算法或硬件操作非常有利。
-
指针的用途:
指针使用过程中可能遇到的问题
1.内存管理复杂
-
动态内存分配与释放: 使用指针动态分配内存时（如通过
malloc、calloc），需要手动释放内存（使用free）。忘记释放内存会导致内存泄漏，频繁分配和释放则可能导致内存碎片化。 -
悬空指针 (Dangling Pointer): 当指针指向的内存已经被释放，但指针仍然在使用时，就会出现悬空指针。这可能导致程序崩溃或出现未定义行为。
2. 指针运算的复杂性
-
指针算术: 对指针进行加减运算时，需要非常谨慎。错误的指针算术操作可能导致访问无效或错误的内存地址，导致程序崩溃或数据损坏。
-
多级指针: 使用指向指针的指针（如
int** p）会使代码复杂化，容易引入错误。多级指针的解引用和操作需要特别小心。
3. 指针类型转换
-
类型不匹配: 不同类型指针之间的转换需要小心处理，尤其是将
void*转换为具体类型的指针时，必须确保转换后的指针能够正确访问内存，否则会导致未定义行为。 -
指针对齐: 某些平台上，指针指向的地址可能要求对齐。如果不遵守对齐要求，可能会导致性能下降甚至崩溃。
4. 指针和数组的混淆
-
数组名与指针的混淆: 虽然数组名可以被视为指针，但它们并不完全相同。数组名是一个常量指针，不能被修改；而指针可以指向任何内存位置。理解这两者的区别对于正确使用非常重要。
-
多维数组与指针: 处理多维数组时，理解其在内存中的布局和如何通过指针访问各元素可能比较复杂，尤其是在传递给函数时。
5. 指针的初始化问题
-
未初始化指针: 如果指针在使用前未被初始化，它将指向一个未知的内存地址。使用这样的指针进行操作可能会导致不可预测的结果或程序崩溃。
-
NULL指针: 使用指针前，通常需要检查其是否为
NULL，以防止对空指针进行解引用操作，这会导致程序崩溃。
6. 并发和多线程环境中的指针
-
数据竞争 (Data Race): 在多线程环境中，如果多个线程同时访问或修改同一个指针指向的内存，而没有适当的同步措施，可能会导致数据竞争，进而导致不可预测的行为。
-
共享指针的管理: 在并发编程中，共享指针的管理是一个挑战，特别是在需要安全地共享和释放资源时。
7. 指针错误调试困难
-
调试复杂: 指针错误（如悬空指针、野指针）往往很难调试和定位，因为错误通常不会立即显现，而是可能在其他地方引发问题。
-
未定义行为: 由于指针错误导致的未定义行为，使得问题具有随机性和不可重复性，进一步增加了调试的难度。
8. 指针的安全性问题
-
缓冲区溢出 (Buffer Overflow): 由于指针可以直接操作内存，如果对内存访问不加限制，容易造成缓冲区溢出，导致内存损坏，甚至引发安全漏洞。
-
指针攻击: 恶意代码可能通过操纵指针导致程序执行任意代码或进行非法访问。因此，指针的使用安全性需要特别注意。
9. 指针与函数指针的复杂性
-
函数指针: 使用函数指针可以实现回调函数和动态函数调用，但其语法复杂且容易出错。函数指针的声明、初始化和调用需要非常谨慎。
10. 跨平台指针差异
-
不同平台的指针大小: 指针的大小可能随平台变化（如32位系统中为4字节，64位系统中为8字节），这会影响到内存操作和数据结构的设计。
-
指针的字节序: 不同平台可能使用不同的字节序（大端或小端），这在指针操作中可能带来问题，尤其是在网络编程或文件读写中。
11. 指针的深层拷贝与浅层拷贝
-
深拷贝 vs 浅拷贝: 使用指针时，特别是在拷贝复杂数据结构时，需要理解深拷贝和浅拷贝的区别。浅拷贝只复制指针本身，而深拷贝则会复制指针指向的数据。错误的拷贝方式可能导致数据共享和意外修
部分存储结构
1. 顺序存储结构
- 定义: 数据元素按顺序存储在内存的连续地址空间中。
- 特点:
- 每个元素的地址是固定的，并且可以通过数组下标直接访问。
- 适合实现随机访问操作，时间复杂度为O(1)。
- 插入和删除操作通常需要移动大量元素，效率较低。
- 应用: 数组、顺序表（如 C 语言中的
int arr[]）。 - 示例: 在数组
int arr[5] = {1, 2, 3, 4, 5};中，arr[2]直接访问第三个元素3。
2. 链式存储结构
- 定义: 数据元素存储在内存的任意位置，元素之间通过指针相连形成一个链表结构。
- 特点:
- 不要求数据元素在内存中是连续的，内存利用率高。
- 插入和删除操作高效，因为只需修改指针即可。
- 访问操作需要从头遍历，时间复杂度为O(n)。
- 应用: 单链表、双向链表、循环链表等。
- 示例: 在单链表中，每个节点包含数据和指向下一个节点的指针，如
struct Node { int data; Node* next; }。
3. 索引存储结构
- 定义: 在存储数据的同时，建立一个额外的索引表来加速数据的查找。
- 特点:
- 通过索引可以快速定位数据位置，查找效率高。
- 适合大规模数据的查找和排序操作。
- 维护索引需要额外的空间和时间开销。
- 应用: 数据库索引、跳表（Skip List）、B树、B+树等。
- 示例: 在数据库中，给一个表建立索引后，可以通过索引快速查找到所需的记录。
4. 散列存储结构
- 定义: 通过散列函数将数据映射到存储空间的特定位置（散列表），并以这种方式进行存储和查找。
- 特点:
- 查找、插入和删除操作的平均时间复杂度为O(1)。
- 可能出现哈希冲突，需要采用解决方案如链地址法或开放地址法。
- 应用: 哈希表（如 C++ 中的
std::unordered_map）、哈希集合。 - 示例: 使用哈希函数
h(key) = key % table_size将键值key映射到哈希表的位置。
1. 有头链表（Headed Linked List）
定义
有头链表是指在链表的最前面有一个特殊的节点，即头节点（head node）。头节点不存储实际的数据，它的作用是指向链表的第一个数据节点，或者作为链表的起点。
结构特点
- 头节点: 有头链表有一个头节点，它始终存在，即使链表为空。头节点的
next指针指向链表的第一个数据节点。 - 统一的操作: 由于头节点的存在，链表的插入、删除、查找等操作可以统一处理，即不需要特殊处理链表的第一个节点。
- 易于管理: 头节点作为链表的入口，使得链表管理更加简洁，无需担心链表为空时的特殊情况。
优点
缺点
- 额外的空间开销: 头节点虽然不存储数据，但依然占用一定的内存空间。
2. 无头链表（Headless Linked List）
定义
无头链表是指链表没有头节点，第一个节点即是链表的第一个数据节点。链表的起点直接指向第一个数据节点，如果链表为空，则该指针为 NULL。
结构特点
优点
缺点
- 操作复杂性增加: 在进行插入、删除操作时，如果涉及到第一个节点，需要特殊判断和处理，代码可能变得更复杂。
- 易出错: 由于没有头节点保护，在处理空链表或首节点操作时，容易出现错误，如空指针引用等。
无头链表中常见的操作
1. 初始化链表
无头链表的初始化通常是将头指针设置为 NULL，表示链表为空。
struct Node {int data;struct Node* next;
};struct Node* head = NULL; // 初始化为空链表
2. 插入节点
a. 在链表头部插入节点
- 如果要在链表的头部插入节点，需要创建一个新节点，并将其
next指针指向当前的head，然后更新head指向新节点。void insertAtHead(struct Node** head, int newData) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = newData;newNode->next = *head;*head = newNode; }b. 在链表中间或尾部插入节点
- 对于非头部的插入，需要遍历链表找到合适的位置，然后插入节点。
void insertAfter(struct Node* prevNode, int newData) {if (prevNode == NULL) {printf("The given previous node cannot be NULL.\n");return;}struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = newData;newNode->next = prevNode->next;prevNode->next = newNode;
}
3. 删除节点
a. 删除头节点
- 如果要删除链表的头节点，需要将
head指针指向第二个节点，并释放原头节点的内存。void deleteHead(struct Node** head) {if (*head == NULL) return; // 空链表，直接返回struct Node* temp = *head; // 暂存当前头节点*head = (*head)->next; // 将头指针移向下一个节点free(temp); // 释放原头节点的内存 }b. 删除指定节点
- 对于删除非头节点的情况，需要遍历链表找到要删除的节点的前一个节点，然后调整指针跳过要删除的节点。
void deleteNode(struct Node** head, int key) {struct 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); // 释放要删除的节点 }4. 查找节点
- 在无头链表中查找节点需要从头开始遍历，直到找到目标数据或链表结束。
struct Node* search(struct Node* head, int key) {struct Node* current = head; // 从头节点开始while (current != NULL) {if (current->data == key) {return current; // 找到节点}current = current->next;}return NULL; // 如果没有找到
}
5. 遍历链表
void printList(struct Node* head) {struct Node* current = head; // 从头节点开始while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n"); // 表示链表结束
}
6. 求链表长度
- 通过遍历整个链表，可以计算出链表的长度。
int getLength(struct Node* head) {int length = 0;struct Node* current = head;while (current != NULL) {length++;current = current->next;}return length; }在无头链表中使用结构体记录链表长度
1. 定义链表结构体
首先，定义一个链表结构体 LinkedList，其中包括链表的头指针和一个长度字段 length，用于记录链表中节点的数量。
#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
struct Node {int data;struct Node* next;
};// 定义链表结构体，包含头指针和长度
struct LinkedList {struct Node* head;int length;
};// 初始化链表
void initList(struct LinkedList* list) {list->head = NULL;list->length = 0;
}
2. 插入节点时更新长度
在插入节点时，无论是在链表头部还是中间或尾部，都需要更新 length 字段
// 在链表头部插入节点
void insertAtHead(struct LinkedList* list, int newData) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = newData;newNode->next = list->head;list->head = newNode;list->length++; // 更新链表长度
}// 在链表中间或尾部插入节点
void insertAfter(struct Node* prevNode, int newData, struct LinkedList* list) {if (prevNode == NULL) {printf("The given previous node cannot be NULL.\n");return;}struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = newData;newNode->next = prevNode->next;prevNode->next = newNode;list->length++; // 更新链表长度
}
3. 删除节点时更新长度
类似地，在删除节点时也需要更新 length 字段。
// 删除头节点
void deleteHead(struct LinkedList* list) {if (list->head == NULL) return; // 空链表，直接返回struct Node* temp = list->head; // 暂存当前头节点list->head = list->head->next; // 将头指针移向下一个节点free(temp); // 释放原头节点list->length--; // 更新链表长度
}// 删除指定节点
void deleteNode(struct LinkedList* list, int key) {struct Node* temp = list->head;struct Node* prev = NULL;// 如果要删除的是头节点if (temp != NULL && temp->data == key) {list->head = temp->next; // 将头指针移向下一个节点free(temp); // 释放原头节点list->length--; // 更新链表长度return;}// 搜索要删除的节点，记录其前一个节点while (temp != NULL && temp->data != key) {prev = temp;temp = temp->next;}// 如果没有找到要删除的节点if (temp == NULL) return;// 跳过要删除的节点prev->next = temp->next;free(temp); // 释放要删除的节点list->length--; // 更新链表长度
}
4. 获取链表长度
由于长度已经在插入和删除操作时自动更新，获取链表长度只需要读取 length 字段即可。
int getLength(struct LinkedList* list) {return list->length;
}
5. 遍历链表
遍历链表的操作和之前的链表操作基本相同，只不过这次是在 LinkedList 结构体中访问 head 指针。
void printList(struct LinkedList* list) {struct Node* current = list->head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n"); // 表示链表结束
}
