1 概述
1.1 背景介绍
在现代软件开发中，数据结构的选择对程序的性能和可维护性有着至关重要的影响。数组和链表作为两种最基本的数据结构，分别适用于不同的场景。理解它们的特性和优劣，能够帮助开发者在实际项目中做出更合理的技术选型，从而优化系统性能。
链表是一种动态的数据结构，它通过结点之间的指针链接来组织数据。与数组不同，链表的存储空间是动态分配的，不需要预先分配固定大小的内存。单向链表是一种基础的数据结构，由一系列节点组成，每个节点包含两部分：数据域和指针域。其核心特点是节点之间通过单向指针连接，形成线性序列，仅支持从头节点开始顺序访问。
本案例相关实验将在华为云开发者空间云主机进行，开发者空间云主机为开发者提供了高效稳定的云资源，确保用户的数据安全。云主机当前已适配完整的 C/C++开发环境，支持 Visual Studio Code 等多种 IDE 工具安装调测。
1.2 适用对象
1.3 案例时间
本案例总时长预计 90 分钟。
1.4 案例流程
说明：
① 开通开发者空间，搭建 C/C++开发环境。② 打开 VS Code，编写代码运行程序。
2 配置实验环境
参考案例中心《基于开发者空间，定制C&C++开发环境云主机镜像》“2. 实验环境搭建”、“3. VS Code 安装部署”章节完成开发环境、VS code 及插件安装。
3 单向链表的基本操作
3.1 单向链表的初始化
添加必要的头文件，定义链表结点结构。
#include <stdio.h>#include <stdlib.h>// 定义链表结点结构typedef struct LNode { int data; // 数据域（可根据需要修改类型） struct LNode *next; // 指针域} LNode, *LinkList; // LinkList为指向结构体的指针类型
复制代码
实现链表初始化函数 list_init。1） 创建头结点，头结点的指针域置空；2） 创建头指针，头指针指向头结点（将头结点的地址赋值给头指针）。
// 链表初始化函数LinkList list_init() { LNode *t = (LNode *)malloc(sizeof(LNode)); // 创建头结点 if (t == NULL) { printf("内存分配失败！\n"); exit(EXIT_FAILURE); } t->next = NULL; // 头结点的指针域置空 LinkList head = t; // 头指针指向头结点 return head;}
复制代码
编写 main 函数，测试初始化函数，验证初始化结果。释放内存。
int main() { // 测试初始化函数 LinkList mylist = list_init(); // 验证初始化结果 if (mylist != NULL && mylist->next == NULL) { printf("链表初始化成功！\n"); printf("头结点地址：%p\n", mylist); printf("头结点next指针：%p\n", mylist->next); } else { printf("链表初始化失败！\n"); } // 释放头结点内存 free(mylist); return 0;}
复制代码
实验结果：
链表初始化成功！头结点地址：0xaaaaaaac12a0头结点next指针：(nil)
复制代码
3.2 单向链表的销毁
添加必要的头文件和宏，定义链表结点结构。
#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0typedef struct LNode { int data; struct LNode* next;} LNode, *LinkList;
复制代码
创建带 3 个结点的测试链表，用于测试。
LinkList list_create() { LinkList head = (LinkList)malloc(sizeof(LNode)); if (!head) return NULL; head->next = NULL; // 添加3个结点，数据为1、2、3 for (int i = 3; i >= 1; i--) { LNode* newNode = (LNode*)malloc(sizeof(LNode)); if (!newNode) { // 创建失败时清理已分配的内存 while (head->next) { LNode* temp = head->next; head->next = temp->next; free(temp); } free(head); return NULL; } newNode->data = i; newNode->next = head->next; head->next = newNode; } return head;}
复制代码
实现 list_destroy 函数。1） 使用临时指针 t 从链表的第一个数据结点开始遍历，直到遍历到链表的末尾；2） 每遍历到一个结点首先将头结点的 next 赋值为当前结点的下一个结点即 head->next = t->next，然后临时指针 t 指向下一个结点 t = head->next；3） 如果整个链表遍历完毕则删除结点。
int list_destroy(LinkList head) { if (NULL == head) { printf("[%s %d] head pointer is NULL...\n", __func__, __LINE__); return FALSE; }
LNode* t = head->next; while (t != NULL) { head->next = t->next; free(t); t = head->next; } free(head); return TRUE;}
复制代码
编写 main 函数，创建链表，调用销毁函数，测试正常销毁和传入 NULL 的情况。
int main() { // 测试正常销毁 LinkList list = list_create(); if (list) { printf("创建链表成功，开始销毁...\n"); int result = list_destroy(list); printf("销毁结果：%s\n", result ? "成功" : "失败"); } // 测试传入NULL的情况 printf("\n测试传入NULL：\n"); int null_result = list_destroy(NULL); printf("销毁结果：%s\n", null_result ? "成功" : "失败"); return 0;}
复制代码
实验结果：
创建链表成功，开始销毁...销毁结果：成功
测试传入NULL：[list_destroy **] head pointer is NULL...销毁结果：失败
复制代码
3.3 单向链表的插入操作
3.3.1 单向链表头插法
添加必要的头文件，定义链表结点结构。
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#define TRUE 1#define FALSE 0typedef int ElemType; // 假设元素类型为int
typedef struct LNode { ElemType data; struct LNode *next;} LNode, *LinkList;
复制代码
实现单向链表头插法函数 head_insert。 1）创建一个新的结点 p； 2）将新的结点 p 的 next 指向头结点的下一个结点（head->next）； 3）头结点的 next 指向新的结点 p。
bool head_insert(LinkList head, ElemType data) { // 检查参数有效性，防止对空指针进行操作导致程序崩溃。 if (NULL == head) { printf("[%s %d] head pointer is NULL...\n", __func__, __LINE__); return FALSE;}// 创建头结点，验证头结点有效性。 LNode *p = (LNode *)malloc(sizeof(LNode)); if (p == NULL) { fprintf(stderr, "Memory allocation failed\n"); return FALSE; } //头结点p指针指向数据域p->data = data;//指针连接，将新的结点p的next指向头结点的下一个结点（head->next）p->next = head->next;//头结点的next指向新的结点p head->next = p; return TRUE;}
复制代码
实现辅助函数 print_list，打印单向链表。
void print_list(LinkList head) { LNode *current = head->next; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n");}
复制代码
参考 3.2 单向链表的销毁实验步骤：3.实现函数 list_destroy，释放内存。
编写 main 函数，测试链表头插法函数，打印链表内容。最后释放内存。
int main() { // 创建带头结点的空链表 LinkList head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; // 插入测试数据 head_insert(head, 10); head_insert(head, 20); head_insert(head, 30); // 打印链表 printf("头插法测试: "); print_list(head); // 释放内存 list_destroy(head); return TRUE;}
复制代码
实验结果：
3.3.2 单向链表尾插法
参考 3.3.1 单向链表头插法小节的实验步骤：1.添加必要的头文件，定义链表结点结构。
实现尾插法函数 tail_insert。1） 新建一个新的结点；2） 将尾指针的 next 指向新的结点；3） 将尾指针指向新的结点。
bool tail_insert(LinkList head, LNode **pp_tail, ElemType data) { // 参数有效性检查（同时检查二级指针） if (head == NULL || pp_tail == NULL) { fprintf(stderr, "[%s %d] 无效指针参数\n", __func__, __LINE__); return FALSE; } // 创建头结点，验证头结点有效性，并初始化新结点。 LNode *p = (LNode *)malloc(sizeof(LNode)); if (p == NULL) { fprintf(stderr, "[%s %d] 内存分配失败\n", __func__, __LINE__); return FALSE; } p->data = data;p->next = NULL;// 如果链表为空，将头结点的next指向新的结点 if (head->next == NULL) { head->next = p; // 空链表情况 } else { (*pp_tail)->next = p; // 非空链表情况 } *pp_tail = p; // 更新尾指针 return TRUE;}
复制代码
参考 3.3.1 单向链表头插法小节的实验步骤：3.实现辅助函数 print_list，打印单向链表。
参考 3.2 单向链表的销毁小节的实验步骤：3.实现函数 list_destroy，释放内存。
编写 main 函数，测试链表尾插法以及边界测试。
int main() { // 初始化带头结点的空链表 LinkList head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; LNode *tail = NULL; // 初始尾指针为NULL // 测试尾插法 tail_insert(head, &tail, 10); tail_insert(head, &tail, 20);tail_insert(head, &tail, 30);// 打印链表 printf("尾插法测试：");print_list(head); // 释放内存 list_destroy(head); return TRUE;}
复制代码
实验结果：
3.4 单向链表的查找操作
3.4.1 查找单向链表的指定元素
参考 3.3.1 单向链表头插法小节的实验步骤：1.添加必要的头文件，定义链表结点结构。
参考 3.3.1 单向链表头插法小节的实验步骤：2. 实现单向链表头插法函数 head_insert。
参考 3.3.1 单向链表头插法小节的实验步骤：3.实现辅助函数 print_list，打印单向链表。
参考 3.2 单向链表的销毁小节的实验步骤：3.实现函数 list_destroy，释放内存。
实现单向链表查找指定元素的函数 get_elem。1） 从链表的第一个数据结点开始遍历 2） 将遍历到的每一个结点上的数据域与需要查找的元素比较 3） 如果相等返回该结点的地址，如果不相等则继续往后遍历，如果遍历到链表末尾依然没有找到则返回 NULL。
LNode *get_elem(LinkList head, int data) { if (NULL == head) { printf("[%s %d] head pointer is NULL ...\n", __FUNCTION__ , __LINE__); return NULL; } LNode *t = head->next; while (t != NULL) { if (t->data == data) return t; t = t->next; } return NULL;}
复制代码
编写 main 函数，测试查找存在和不存在的元素。
int main() { // 创建带头结点的空链表 LinkList head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; // 插入测试数据 head_insert(head, 1); head_insert(head, 2); head_insert(head, 3); head_insert(head, 4); head_insert(head, 5); // 打印链表 printf("当前链表元素：");print_list(head);// 测试查找存在的元素 int target = 3; LNode *result = get_elem(head, target); if (result) { printf("找到元素 %d，结点地址：%p\n", target, result); } else { printf("未找到元素 %d\n", target); } // 测试查找不存在的元素 target = 6; result = get_elem(head, target); if (result) { printf("找到元素 %d，结点地址：%p\n", target, result); } else { printf("未找到元素 %d\n", target); }
// 释放内存 list_destroy (head); return TRUE;}
复制代码
实验结果：
当前链表元素：5 4 3 2 1 找到元素 3，结点地址：0xaaaaaaac1300未找到元素 6
复制代码
3.4.2 查找单向链表指定位置的元素
参考 3.3.1 单向链表头插法小节的实验步骤：1.添加必要的头文件，定义链表结点结构。
参考 3.3.1 单向链表头插法小节的实验步骤：2. 实现单向链表头插法函数 head_insert。
参考 3.3.1 单向链表头插法小节的实验步骤：3.实现辅助函数 print_list，打印单向链表。
参考 3.2 单向链表的销毁小节的实验步骤：3.实现函数 list_destroy，释放内存。
实现单向链表指定位置元素查找函数 get_elem_by_index。1） 从链表的第一个数据结点开始遍历；2） 每遍历一个结点遍历次数+1，同时判断是否遍历到了链表的末尾；3） 如果遍历到了链表末尾返回 NULL；4） 或者遍历到了指定位置返回结点指针。
LNode *get_elem_by_index(LinkList head, int index) { if (NULL == head) { printf("[%s %d] head pointer is NULL ...\n",__FUNCTION__ , __LINE__); return NULL; } //用一个临时指针指向链表的第一个数据结点 LNode *t = head->next; int i=1; //判断是否遍历到了链表末尾或者遍历到了指定的位置 while (i<=index && t!=NULL) { i++; t = t->next; } return t;}
复制代码
编写 main 函数，测试查找越界和非越界的元素。
int main() { // 创建带头结点的空链表 LinkList head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; // 插入测试数据 head_insert(head, 1); head_insert(head, 2); head_insert(head, 3); head_insert(head, 4); head_insert(head, 5); // 打印链表 printf("当前链表元素："); print_list(head);
// 测试非越界索引的函数查找 int index = 3; LNode *result = get_elem_by_index(head, index); if (result != NULL) { printf("索引 %d 的元素值: %d\n", index, result->data); } else { printf("索引 %d 索引无效或越界\n", index); }
// 测试越界索引的函数查找 index = 6; LNode *result_out = get_elem_by_index(head, index); if (result_out != NULL) { printf("索引 %d 的元素值: %d\n", index, result_out->data); } else { printf("索引 %d 索引无效或越界\n", index); } // 释放内存 list_destroy(head); return TRUE;}
复制代码
实验结果：
当前链表元素：5 4 3 2 1 索引 3 的元素值: 2索引 6 索引无效或越界
复制代码
3.5 单向链表的删除操作
3.5.1 单向链表删除指定位置的元素
参考 3.3.1 单向链表头插法小节的实验步骤：1.添加必要的头文件，定义链表结点结构。
参考 3.3.1 单向链表头插法小节的实验步骤：2. 实现单向链表头插法函数 head_insert。
参考 3.3.1 单向链表头插法小节的实验步骤：3.实现辅助函数 print_list，打印单向链表。
参考 3.2 单向链表的销毁小节的实验步骤：3.实现函数 list_destroy，释放内存。
实现单向链表指定位置元素删除函数 delete_by_index。 1 ) 使用临时指针 current 从链表的第一个数据结点开始遍历； 2 ) 使用临时指针 prev 保存遍历到的结点的前驱结点； 3 ) 每遍历一个结点遍历次数+1，指针 prev 与随之往后移动，同时判断是否遍历到了链表的末尾； 4 ) 如果遍历到了链表的末尾则返回 FALSE； 5 ) 如果遍历到的位置恰好是最后一个结点（尾结点），则将尾指针指向该结点的前一个结点，尾指针的 next 赋值为 NULL，并且删除最后一个结点； 6 ) 如果遍历到的结点是中间结点，则将前驱结点指向遍历到的结点的下一个结点（指针 p->next = t->next）。
int delete_by_index(LinkList head, LNode **tail, int index) { if (head == NULL || tail == NULL) { printf("[%s %d] Invalid input parameters\n", __func__, __LINE__); return FALSE; } LNode *prev = head; LNode *current = head->next; int i = 1; // 定位要删除的结点及其前驱 while (i < index && current != NULL) { prev = current; current = current->next; i++; } if (current == NULL) { printf("[%s %d] Index %u out of bounds\n", __func__, __LINE__, index); return FALSE; } // 更新前驱结点的next指针 prev->next = current->next; // 如果是尾结点则更新tail if (current->next == NULL) { *tail = prev; } free(current); return TRUE;}
复制代码
编写 main 函数，测试删除中间结点和尾结点。
int main() { // 创建带头结点的空链表 LinkList head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; LNode *tail = NULL; // 创建测试数据 for (int i = 1; i <= 5; i++) { head_insert(head, i); } // 打印链表 printf("删除操作前的链表元素："); print_list(head); // 测试删除中间结点 printf("删除索引 3: %s\n",delete_by_index(head, &tail, 3) ? "成功" : "失败"); // 打印删除操作后的链表 printf("删除中间结点后的链表元素："); print_list(head); // 测试删除尾结点 printf("删除尾结点: %s\n",delete_by_index(head, &tail, 4) ? "成功" : "失败"); printf("删除后尾结点的数据: %d\n", tail->data); // 打印删除操作后的链表 printf("删除尾结点后的链表元素："); print_list(head); // 释放内存 list_destroy(head); return TRUE;}
复制代码
实验结果：
删除操作前的链表元素：5 4 3 2 1删除索引 3: 成功删除中间结点后的链表元素：5 4 2 1删除尾结点: 成功删除后尾结点的数据: 2删除尾结点后的链表元素：5 4 2
复制代码
3.5.2 单向链表删除指定的元素
参考 3.3.1 单向链表头插法小节的实验步骤：1.添加必要的头文件，定义链表结点结构。
参考 3.3.1 单向链表头插法小节的实验步骤：2. 实现单向链表头插法函数 head_insert。
参考 3.3.1 单向链表头插法小节的实验步骤：3.实现辅助函数 print_list，打印单向链表。
参考 3.2 单向链表的销毁小节的实验步骤：3.实现函数 list_destroy，释放内存。
实现单向链表指定元素删除函数 delete_by_elem_value。
int delete_by_elem_value(LinkList head, LNode **tail, ElemType data) { if (NULL == head) { printf("[%s %d] head pointer is NULL ...\n", __FUNCTION__ , __LINE__); return FALSE; } LNode *t = head->next; LNode *p = head; //遍历到链表的末尾 while (t != NULL) { //如果遍历到了需要删除的结点 if (t->data == data) { //如果当前结点为尾结点 if (t->next == NULL) { *tail = p; (*tail)->next = NULL; free(t); return TRUE; } //如果是中间的结点 前驱结点指向当前结点的下一个结点 p->next = t->next; free(t); t = p->next; } else { t = t->next; p = p->next; } } return TRUE;}
复制代码
编写 main 函数，测试删除中间结点、尾结点和不存在的结点。
int main() { // 创建带头结点的空链表 LinkList head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; LNode *tail = head; // 初始尾指针指向头结点 // 创建测试数据 for (int i = 1; i <= 5; i++) { head_insert(head, i); } // 打印链表 printf("删除操作前的链表元素："); print_list(head); // 删除中间结点，数值3 printf("删除中间结点（数值3）后的链表元素："); if (delete_by_elem_value(head, &tail, 3)) { print_list(head); } // 删除尾结点，数值1 printf("删除尾结点（数值1）后的链表元素："); if (delete_by_elem_value(head, &tail, 1)) { print_list(head); printf("新尾结点值: %d\n", tail->data); } // 删除不存在的结点，数值6 printf("删除不存在的结点（数值6）后的链表元素："); if (delete_by_elem_value(head, &tail, 6)) { printf("删除失败！\n"); printf("尾结点值保持: %d\n", tail->data); } // 打印链表 printf("删除操作后的链表元素："); print_list(head); // 释放内存 list_destroy(head); return TRUE;}
复制代码
实验结果：
删除操作前的链表元素：5 4 3 2 1删除中间结点（数值3）后的链表元素：5 4 2 1 删除尾结点（数值1）后的链表元素：5 4 2新尾结点值: 2删除不存在的结点（数值6）后的链表元素：删除失败！尾结点值保持: 2删除操作后的链表元素：5 4 2
复制代码
4 综合案例：通讯录管理系统
4.1 需求分析及代码实现
4.1.1 功能需求
通讯录管理系统功能设计如下：
添加联系人：用户可以输入联系人的姓名、电话号码和地址，将其添加到通讯录中。
查找联系人：用户可以通过姓名查找联系人的电话号码和地址。
删除联系人：用户可以通过姓名删除联系人。
显示通讯录：用户可以查看所有联系人的信息。
退出系统：用户可以退出程序。
4.1.2 编写代码
添加必要的头文件和宏，定义结构体。
将原先的单向链表结点结构，修改成 Contact 结构体，用于存储联系人信息（姓名、电话、地址），修改链表结点数据域为 Contact 类型
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdbool.h>
#define NAME_LEN 50#define PHONE_LEN 20#define ADDR_LEN 100
typedef struct { char name[NAME_LEN]; char phone[PHONE_LEN]; char address[ADDR_LEN];} Contact;
typedef struct LNode { Contact data; struct LNode *next;} LNode, *LinkList;
复制代码
添加初始化链表函数。
LinkList list_init() { LNode *head = (LNode *)malloc(sizeof(LNode)); if (head == NULL) { printf("内存分配失败！\n"); exit(EXIT_FAILURE); } head->next = NULL; return head;}
复制代码
添加销毁链表函数。
void list_destroy(LinkList head) { if (head == NULL) return; LNode *current = head->next; while (current != NULL) { LNode *temp = current; current = current->next; free(temp); } free(head);}
复制代码
使用尾插法添加联系人。
void tail_insert(LinkList head, Contact data) { LNode *new_node = (LNode *)malloc(sizeof(LNode)); if (new_node == NULL) { printf("内存分配失败！\n"); return; } new_node->data = data; new_node->next = NULL; LNode *current = head; while (current->next != NULL) { current = current->next; } current->next = new_node;}
复制代码
按姓名查找联系人。
LNode* search_by_name(LinkList head, const char *name) { if (head == NULL) return NULL; LNode *current = head->next; while (current != NULL) { if (strcmp(current->data.name, name) == 0) { return current; } current = current->next; } return NULL;}
复制代码
删除联系人。
bool delete_contact(LinkList head, const char *name) { if (head == NULL) return false; LNode *prev = head; LNode *current = head->next; while (current != NULL) { if (strcmp(current->data.name, name) == 0) { prev->next = current->next; free(current); return true; } prev = current; current = current->next; } return false;}
复制代码
显示所有联系人。
void display_contacts(LinkList head) { if (head == NULL || head->next == NULL) { printf("通讯录为空！\n"); return; }
printf("\n%-20s %-15s %-30s\n", "姓名", "电话", "地址"); printf("------------------------------------------------------------\n"); LNode *current = head->next; while (current != NULL) { printf("%-20s %-15s %-30s\n", current->data.name, current->data.phone, current->data.address); current = current->next; } printf("\n");}
复制代码
获取用户输入。
Contact get_input() { Contact new_contact; printf("请输入姓名: "); fgets(new_contact.name, NAME_LEN, stdin); new_contact.name[strcspn(new_contact.name, "\n")] = '\0'; printf("请输入电话: "); fgets(new_contact.phone, PHONE_LEN, stdin); new_contact.phone[strcspn(new_contact.phone, "\n")] = '\0'; printf("请输入地址: "); fgets(new_contact.address, ADDR_LEN, stdin); new_contact.address[strcspn(new_contact.address, "\n")] = '\0'; return new_contact;}
复制代码
实现菜单界面和 main 函数。
void menu() { printf("\n====== 通讯录管理系统 ======\n"); printf("1. 添加联系人\n"); printf("2. 删除联系人\n"); printf("3. 查找联系人\n"); printf("4. 显示所有联系人\n"); printf("5. 退出系统\n"); printf("请选择操作: ");}
int main() { LinkList contacts = list_init(); int choice; char name[NAME_LEN]; while (1) { menu(); scanf("%d", &choice); getchar(); // 清除输入缓冲区 switch (choice) { case 1: { Contact new_contact = get_input(); tail_insert(contacts, new_contact); printf("联系人添加成功！\n"); break; } case 2: { printf("请输入要删除的姓名: "); fgets(name, NAME_LEN, stdin); name[strcspn(name, "\n")] = '\0'; if (delete_contact(contacts, name)) { printf("联系人删除成功！\n"); } else { printf("未找到该联系人！\n"); } break; } case 3: { printf("请输入要查找的姓名: "); fgets(name, NAME_LEN, stdin); name[strcspn(name, "\n")] = '\0'; LNode *result = search_by_name(contacts, name); if (result) { printf("\n找到联系人：\n"); printf("姓名: %s\n电话: %s\n地址: %s\n", result->data.name, result->data.phone, result->data.address); } else { printf("未找到该联系人！\n"); } break; } case 4: display_contacts(contacts); break; case 5: list_destroy(contacts); printf("系统已退出，感谢使用！\n"); exit(0); default: printf("无效的选项，请重新输入！\n"); } } return 0;}
复制代码
4.1.3 功能演示
添加联系人：输入联系人姓名、电话号码和地址，将其添加到链表中。
添加联系人 "张三"，电话号码 " 13611112222"，地址“北京”。
添加联系人 "李四"，电话号码 " 13899990000"，地址“南京”。
查找联系人：输入联系人姓名，查找并显示其电话号码、地址。例如：查找 "张三"，显示电话号码 " 13611112222"，地址“北京”。
====== 通讯录管理系统 ======1. 添加联系人2. 删除联系人3. 查找联系人4. 显示所有联系人5. 退出系统请选择操作: 3 请输入要查找的姓名: 张三
找到联系人：姓名: 张三电话: 13611112222地址: 北京
复制代码
显示通讯录：显示所有联系人的姓名和电话号码。
====== 通讯录管理系统 ======1. 添加联系人2. 删除联系人3. 查找联系人4. 显示所有联系人5. 退出系统请选择操作: 4
姓名 电话 地址------------------------------------------------------------张三 13611112222 北京 李四 13899990000 南京
复制代码
删除联系人：输入联系人姓名，从链表中删除该联系人。例如：删除 "张三"，通讯录中不再显示该联系人。
====== 通讯录管理系统 ======1. 添加联系人2. 删除联系人3. 查找联系人4. 显示所有联系人5. 退出系统请选择操作: 2请输入要删除的姓名: 张三联系人删除成功！
复制代码
退出系统：销毁链表并退出程序。
====== 通讯录管理系统 ======1. 添加联系人2. 删除联系人3. 查找联系人4. 显示所有联系人5. 退出系统请选择操作: 5系统已退出，感谢使用！
复制代码
4.2 总结
4.2.1 单向链表的优缺点
优点：
动态数据管理：链表适用于需要频繁插入和删除数据的场景，如通讯录管理。
内存高效利用：链表可以动态分配内存，避免内存浪费，适合资源受限的系统。
扩展性强：可以轻松扩展功能，如添加联系人分组、排序等功能。
缺点：
随机访问效率低（必须遍历）：必须从头节点开始逐个遍历（O(n)），无法像数组一样通过索引直接访问（O(1)）。
额外空间开销：每个节点需存储指向下一个节点的指针（next），若数据本身较小（如存储一个整数），指针可能占用较大比例的内存。
缓存不友好：节点在内存中非连续存储，无法利用 CPU 缓存的局部性原理，访问效率低于数组。
操作复杂度与边界问题：中间或尾部操作需遍历前驱节点，代码实现需注意边界条件（如空链表、单节点链表）。指针操作易出错，例如未正确处理指针可能导致链表断裂或内存泄漏。
4.2.2 案例总结
我们通过本案例的前半部分，系统的学习了单向链表的初始化、销毁、插入、查找和删除等操作逻辑和代码实现。最后通过实现一个电话通讯录管理系统，展示了链表在实际应用中的灵活性和实用性。链表的基本操作被广泛应用于各种场景，如内存管理、文件系统、网络编程等。通过此案例，可以更好地理解链表的工作原理及其在实际开发中的应用价值。
评论