当前位置： 首页 > ds >正文

Day22 顺序表与链表的实现及应用（含字典功能与操作对比）

ds 2025/8/20 12:06:25

day22 顺序表与链表的实现及应用（含字典功能与操作对比）

使用顺序表实现查字典功能

  • 支持连续查询单词，输入 #quit 退出程序。
  • 数据格式示例如下：
a\0                indef art one\r\n
word			mean
[---buf--->]       [---i--->]
[buf]   &Buf[i+1]

使用 fgets 读取一行内容，通过 strtok 分割单词与释义：

Fgets(buf);                 // 读取一行文本到 buf
Char* word = NULL;          // 定义单词指针
Char* mean = NULL;          // 定义释义指针
Word = Strtok(buf, " ");    // 以空格分割，获取单词
Mean = Strtok(NULL, "\r");  // 继续分割，获取换行前的释义

理想运行结果：
成功从 dict.txt 中逐行解析出单词和对应释义，并存入顺序表。用户输入单词后能快速查到释义，输入 #quit 后正常退出。

seqlist.h

顺序表结构定义及操作接口声明。

#ifndef _SEQLIST_H_
#define _SEQLIST_H_// 数据类型定义：存储单词和释义
typedef struct person {char word[50];      // 单词字段，最多50字符char mean[512];     // 释义字段，最多512字符
} DATATYPE;// 顺序表结构体
typedef struct list {DATATYPE *head;     // 指向动态数组的指针int tlen;           // 数组总容量int clen;           // 当前有效元素个数
} SeqList;// 函数声明
SeqList *CreateSeqList(int len);                     // 创建顺序表
int ShowSeqList(SeqList *list);                      // 显示全部数据
int InsertTailSeqList(SeqList *list, DATATYPE *data); // 尾部插入
int IsFullSeqList(SeqList *list);                    // 判断是否满
int IsEmptySeqList(SeqList *list);                   // 判断是否空
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos); // 按位置插入
int FindSeqList(SeqList *list, char *name);          // 查找指定单词
int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata); // 修改数据
int ClearSeqList(SeqList *list);                     // 清空顺序表
int DestroySeqList(SeqList *list);                   // 销毁顺序表
int DeleteSeqList(SeqList *list, char *name);        // 删除指定元素
int GetSizeSeqList(SeqList *list);                   // 获取有效元素个数
DATATYPE *GetItemSeqlist(SeqList *list, int pos);    // 获取指定位置元素
int ShowSeqListOne(SeqList *list, int inx);          // 显示单条记录#endif
seqlist.c

顺序表的实现文件，包含所有接口函数的具体实现。

#include "seqlist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** 创建顺序表* @param len 初始容量* @return 成功返回指针，失败返回 NULL*/
SeqList *CreateSeqList(int len)
{SeqList *sl = malloc(sizeof(SeqList));if (NULL == sl){perror("CreateSeqList malloc error\n");return NULL;}sl->head = malloc(sizeof(DATATYPE) * len);if (NULL == sl->head){perror("CreateSeqList malloc2 error\n");return NULL;}sl->tlen = len;sl->clen = 0;return sl;
}/*** 尾部插入数据* @param list 目标顺序表* @param data 待插入数据* @return 0 成功，1 失败（已满）*/
int InsertTailSeqList(SeqList *list, DATATYPE *data)
{if (IsFullSeqList(list)){printf("seqlist is full\n");return 1;}memcpy(&list->head[list->clen], data, sizeof(DATATYPE)); // 安全拷贝list->clen++;return 0;
}/*** 判断顺序表是否已满* @param list 顺序表* @return 1 满，0 未满*/
int IsFullSeqList(SeqList *list)
{return list->clen == list->tlen;
}/*** 显示整个顺序表内容* @param list 顺序表* @return 0*/
int ShowSeqList(SeqList *list)
{int len = GetSizeSeqList(list);for (int i = 0; i < len; ++i){printf("word:%s mean:%s\n", list->head[i].word, list->head[i].mean);}return 0;
}/*** 获取顺序表有效元素个数* @param list 顺序表* @return 元素个数*/
int GetSizeSeqList(SeqList *list)
{return list->clen;
}/*** 判断顺序表是否为空* @param list 顺序表* @return 1 空，0 非空*/
int IsEmptySeqList(SeqList *list)
{return 0 == list->clen;
}/*** 在指定位置插入数据* @param list 顺序表* @param data 待插入数据* @param pos 插入位置（0-based）* @return 0 成功，1 失败*/
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)
{if (IsFullSeqList(list)){printf("seqlist is full\n");return 1;}int len = GetSizeSeqList(list);if (pos < 0 || pos > len){printf("pos is incorrect\n");return 1;}// 从后往前移动元素，腾出位置for (int i = list->clen; i > pos; i--){memcpy(&list->head[i], &list->head[i - 1], sizeof(DATATYPE));}memcpy(&list->head[pos], data, sizeof(DATATYPE));list->clen++;return 0;
}/*** 查找指定单词的位置* @param list 顺序表* @param name 要查找的单词* @return 找到返回索引，否则返回 -1*/
int FindSeqList(SeqList *list, char *name)
{int len = GetSizeSeqList(list);for (int i = 0; i < len; i++){if (0 == strcmp(list->head[i].word, name)){return i;}}return -1;
}/*** 获取指定位置的元素* @param list 顺序表* @param pos 位置* @return 指向该位置元素的指针，非法位置返回 NULL*/
DATATYPE* GetItemSeqlist(SeqList* list, int pos)
{int len = GetSizeSeqList(list);if (pos < 0 || pos >= len)  // 修正：pos 应 < len{printf("pos is incorrect\n");return NULL;}return &list->head[pos];
}/*** 修改指定单词的数据* @param list 顺序表* @param oldname 原单词* @param newdata 新数据* @return 0 成功，1 失败（未找到）*/
int ModifySeqList(SeqList *list, char *oldname, DATATYPE *newdata)
{int ret = FindSeqList(list, oldname);if (-1 == ret){printf("modify failure...\n");return 1;}memcpy(&list->head[ret], newdata, sizeof(DATATYPE));return 0;
}/*** 清空顺序表（不清除内存）* @param list 顺序表* @return 0*/
int ClearSeqList(SeqList *list)
{list->clen = 0;return 0;
}/*** 销毁顺序表并释放内存* @param list 顺序表* @return 0*/
int DestroySeqList(SeqList *list)
{free(list->head);free(list);return 0;
}/*** 显示指定位置的一条记录* @param list 顺序表* @param inx 索引* @return 0 成功，1 失败*/
int ShowSeqListOne(SeqList *list, int inx)
{int len = GetSizeSeqList(list);if (inx < 0 || inx >= len)  // 修正：inx 应 < len{printf("pos is incorrect\n");return 1;}printf("word:%s mean:%s\n", list->head[inx].word, list->head[inx].mean);return 0;
}
main.c

主程序：加载字典文件，支持交互式查询。

#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"
#include <string.h>int main(int argc, char** argv)
{FILE* fp = fopen("/home/linux/dict.txt", "r");if (NULL == fp){perror("fopen");return 1;}SeqList* sl = CreateSeqList(20000);if (NULL == sl){fprintf(stderr, "CreateSeqList error\n");return 1;}// 从文件逐行读取并构建字典while (1){DATATYPE data;char *word = NULL;char *mean = NULL;char linebuf[1024] = {0};if (NULL == fgets(linebuf, sizeof(linebuf), fp)){break;  // 文件读取结束}word = strtok(linebuf, " ");mean = strtok(NULL, "\r");  // 去除回车符strcpy(data.word, word);strcpy(data.mean, mean);InsertTailSeqList(sl, &data);}// 交互式查询while (1){char want_word[50] = {0};printf("input word: ");fgets(want_word, sizeof(want_word), stdin);  // 输入如 "book\n"want_word[strlen(want_word) - 1] = '\0';     // 去掉末尾换行符if (0 == strcmp(want_word, "#quit")){break;}int ret = FindSeqList(sl, want_word);if (-1 == ret){printf("cant find %s\n", want_word);}else{ShowSeqListOne(sl, ret);  // 输出释义}}fclose(fp);DestroySeqList(sl);  // 释放资源return 0;
}

理想运行结果：

input word: hello
word:hello mean:你好
input word: #quit

// strlen()-1 的作用说明：
012345 6
Hello\n\0
1234 567

说明：fgets 会保留换行符 \n，因此用 strlen(want_word)-1 可将其替换为 \0，实现去换行。

线性表的链式存储

  • 解决顺序表在插入、删除操作中效率低及静态容量限制的问题。
  • 实现动态存储，按需分配内存。
特点
  • 链式存储使用任意内存空间存储数据元素，不要求连续。
  • 每个节点包含两部分：
    • 数据域：存储实际数据。
    • 指针域：指向下一个节点地址。
  • 结点（Node）由数据域和指针域共同构成。
LinkList| 
---------
Head Clen|  -> 数据域Data|next -> Data|next -> Data|next-> Data|next
Typedf Struct node
{Name;Sex;Age;Score;
}DATATYPE;
->
Struct node
{DATATYPE data;Struct node*next;
};
单链表的 C 语言描述
typedef struct person {char name[32];char sex;int age;int score;
} DATATYPE;

typedef struct node {DATATYPE data;               // 数据域struct node *next;           // 指针域，指向下一个节点
} LinkNode;

typedef struct list {LinkNode *head;             // 指向第一个节点int clen;                   // 当前有效节点数量
} LinkList;
linklist.h

链表接口声明。

#ifndef _LINKLIST_H_
#define _LINKLIST_H_typedef struct person {char name[32];char sex;int age;int score;
} DATATYPE;typedef struct node {DATATYPE data;struct node *next;
} LinkNode;typedef struct list {LinkNode *head;int clen;
} LinkList;// 接口函数声明
LinkList *CreateLinkList();
int InsertHeadLinkList(LinkList *list, DATATYPE *data);
int InsertTailLinkList(LinkList *list, DATATYPE *data);
int InsertPosLinkList(LinkList *list, DATATYPE *data, int pos);
int ShowLinkList(LinkList *list);
LinkNode *FindLinkList(LinkList *list, char *name);
int DeleteLinkList(LinkList *list, char *name);
int ModifyLinkList(LinkList *list, char *name, DATATYPE *data);
int DestroyLinkList(LinkList *list);
int IsEmptyLinkList(LinkList *list);
int GetSizeLinkList(LinkList *list);#endif  // _LINKLIST_H_
linklist.c

链表功能实现。

#include "linklist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** 创建空链表* @return 新链表指针，失败返回 NULL*/
LinkList *CreateLinkList()
{LinkList* ll = malloc(sizeof(LinkList));if (NULL == ll){perror("CreateLinkList malloc");return NULL;}ll->head = NULL;ll->clen = 0;return ll;
}/*** 头插法插入节点* @param list 链表* @param data 数据* @return 0 成功，1 失败*/
int InsertHeadLinkList(LinkList *list, DATATYPE *data)
{LinkNode* newnode = malloc(sizeof(LinkNode));if (NULL == newnode){perror("InsertHeadLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;if (!IsEmptyLinkList(list)){newnode->next = list->head;  // 新节点指向原头节点}list->head = newnode;            // 更新头指针list->clen++;return 0;
}/*** 判断链表是否为空* @param list 链表* @return 1 空，0 非空*/
int IsEmptyLinkList(LinkList *list)
{return 0 == list->clen;
}/*** 显示链表所有节点* @param list 链表* @return 0*/
int ShowLinkList(LinkList *list)
{LinkNode* tmp = list->head;while (tmp){printf("name:%s sex:%c age:%d score:%d\n",tmp->data.name, tmp->data.sex, tmp->data.age, tmp->data.score);tmp = tmp->next;}return 0;
}

在这里插入图片描述

/*** 尾插法插入节点* @param list 链表* @param data 数据* @return 0 成功，-1 失败*/
int InsertTailLinkList(LinkList *list, DATATYPE *data)
{if (IsEmptyLinkList(list)){return InsertHeadLinkList(list, data);}else{LinkNode* tmp = list->head;while (tmp->next)  // 找到最后一个节点{tmp = tmp->next;}LinkNode* newnode = malloc(sizeof(LinkNode));if (NULL == newnode){perror("InsertTailLinkList malloc");return -1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;tmp->next = newnode;  // 连接新节点}list->clen++;return 0;
}

在这里插入图片描述

/*** 按位置插入节点* @param list 链表* @param data 数据* @param pos 插入位置（0-based）* @return 0 成功，1 失败*/
int InsertPosLinkList(LinkList *list, DATATYPE *data, int pos)
{int len = GetSizeLinkList(list);if (pos < 0 || pos > len){fprintf(stderr, "InsertPosLinkList pos error\n");return 1;}if (0 == pos){return InsertHeadLinkList(list, data);}else if (pos == len){return InsertTailLinkList(list, data);}else{LinkNode* tmp = list->head;int off = pos - 1;while (off--){tmp = tmp->next;}LinkNode* newnode = malloc(sizeof(LinkNode));if (NULL == newnode){perror("InsertPosLinkList malloc ");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = tmp->next;tmp->next = newnode;}list->clen++;return 0;
}int GetSizeLinkList(LinkList *list)
{return list->clen;
}

在这里插入图片描述

/*** 查找指定姓名的节点* @param list 链表* @param name 姓名* @return 找到返回节点指针，否则 NULL*/
LinkNode *FindLinkList(LinkList *list, char *name)
{LinkNode *tmp = list->head;while (tmp){if (0 == strcmp(tmp->data.name, name)){return tmp;}tmp = tmp->next;}return NULL;
}

在这里插入图片描述

/*** 删除指定姓名的节点* @param list 链表* @param name 姓名* @return 0 成功，1 失败*/
int DeleteLinkList(LinkList *list, char *name)
{if (IsEmptyLinkList(list)){fprintf(stderr, "DeleteLinkList empty list\n");return 1;}LinkNode *tmp = list->head;if (0 == strcmp(tmp->data.name, name)){list->head = list->head->next;free(tmp);list->clen--;}else{while (tmp->next){if (0 == strcmp(tmp->next->data.name, name)){LinkNode* del = tmp->next;tmp->next = tmp->next->next;free(del);list->clen--;break;}tmp = tmp->next;}}return 0;
}/*** 修改指定节点数据* @param list 链表* @param name 原名字* @param data 新数据* @return 0 成功，1 失败*/
int ModifyLinkList(LinkList *list, char *name, DATATYPE *data)
{LinkNode *tmp = FindLinkList(list, name);if (NULL == tmp){printf("modify error\n");return 1;}memcpy(&tmp->data, data, sizeof(DATATYPE));return 0;
}/*** 销毁整个链表* @param list 链表* @return 0*/
int DestroyLinkList(LinkList *list)
{LinkNode* tmp = list->head;while (tmp){list->head = list->head->next;free(tmp);tmp = list->head;}free(list);return 0;
}
main.c

测试链表功能。

#include <stdio.h>
#include "linklist.h"int main(int argc, char **argv)
{LinkList* ll = CreateLinkList();DATATYPE data[] ={{"zhangsan", 'm', 20, 80},{"lisi", 'f', 23, 84},{"wangmaizi", 'f', 32, 90},{"guanerge", 'm', 50, 91},{"liubei", 'm', 51, 92},};InsertHeadLinkList(ll, &data[0]);InsertHeadLinkList(ll, &data[1]);InsertHeadLinkList(ll, &data[2]);ShowLinkList(ll);printf("----------insert tail----------\n");InsertTailLinkList(ll, &data[3]);ShowLinkList(ll);printf("----------insert pos----------\n");InsertPosLinkList(ll, &data[4], 1);ShowLinkList(ll);char want_name[] = "zhangsan";LinkNode *tmp = FindLinkList(ll, want_name);if (NULL == tmp){printf("can't find %s\n", want_name);}else{printf("name:%s score:%d\n", tmp->data.name, tmp->data.score);}printf("----------del----------\n");DeleteLinkList(ll, "zhangsan");ShowLinkList(ll);printf("----------modify----------\n");ModifyLinkList(ll, "wangmaizi", &data[4]);ShowLinkList(ll);DestroyLinkList(ll);return 0;
}

理想运行结果：

  • 正确显示插入、删除、修改后的链表状态。
  • 查询与修改功能正常。
  • 内存无泄漏（可用 valgrind 验证）。

顺序表和链表优缺点对比

对比维度顺序表链表
存储方式连续内存空间不连续，通过指针连接
时间性能 - 查找O(1)（支持随机访问）O(n)（需遍历）
时间性能 - 插入/删除O(n)（需移动元素）O(1)（已知位置时）
空间性能需预分配，可能浪费或溢出动态分配，灵活，但每个节点多指针开销
优点访问快，缓存友好插删高效，动态扩展
缺点扩展困难，插入删除慢无法随机访问，额外指针占用内存

在这里插入图片描述

gdb 调试

常用命令：

gdb all

(gdb) p data            // 打印变量 data
(gdb) p *data           // 打印 data 指向的内容
(gdb) p list->clen      // 打印 list 的 clen 字段
(gdb) n                 // 单步执行（不进入函数）
(gdb) s                 // 单步执行（进入函数）
(gdb) p newnode         // 打印 newnode 指针
(gdb) p *newnode        // 打印 newnode 指向的节点
(gdb) q                 // 退出 gdb

valgrind 内存泄露检测

valgrind ./all

检测程序是否存在内存泄漏、非法访问等问题。

回顾

  • 单向链表：内存空间不连续，通过指针链接。
  • 优势：
    • 插入、删除时间复杂度 O(1)（已知位置）
    • 动态存储，无需预分配
  • 劣势：
    • 不支持随机访问，查找为 O(n)
  • 结点结构：数据域 + 指针域（顺序表仅数据域）
  • 手撕代码重点：头插、尾插、按位插、删除、查找、修改

作业

链表的逆序

本部分实现单向链表的逆序操作，通过调整节点指针方向，将链表从头到尾的连接顺序反转。

接口声明（linklist.h）
LinkNode* ReverseLinkList(LinkList *list);

功能：将指定链表进行逆序，并返回新的头节点。
参数：list - 指向链表结构的指针。
返回值：逆序后的头节点指针；若链表为空则返回 NULL。

实现代码（linklist.c）
LinkNode* ReverseLinkList(LinkList *list)
{// 若链表为空或头节点为空，无法逆序，直接返回 NULLif(NULL == list || NULL == list->head){return NULL;}LinkNode *before = NULL;      // 当前节点的前一个节点（初始为 NULL）LinkNode *current = list->head; // 当前处理的节点LinkNode *next;               // 临时保存当前节点的下一个节点// 遍历链表，逐个反转指针while(NULL != current){next = current->next;     // 保存下一个节点current->next = before;   // 将当前节点指向前一个节点（反转指针）before = current;         // 更新前一个节点为当前节点current = next;           // 移动到下一个节点}// 循环结束后，before 指向原链表最后一个节点，即新链表的头节点list->head = before;          // 更新链表头指针return before;                // 返回新的头节点
}

✅ 代码逻辑说明：使用三指针法（before, current, next）实现原地反转，时间复杂度 O(n)，空间复杂度 O(1)。
🧪 理想运行结果：原链表顺序被完全反转，list->head 指向原尾节点，遍历输出顺序与原始插入顺序相反。

测试代码（main.c）
#include <stdio.h>
#include "linklist.h"int main(int argc, char **argv)
{// 创建一个空链表LinkList *ll = CreateLinkList();// 定义测试数据数组，包含5个人员信息DATATYPE data[] = {{"zhangsan", 'm', 20, 80},{"lisi", 'f', 23, 84},{"wangmaizi", 'f', 32, 90},{"guanerge", 'm', 50, 91},{"liubei", 'm', 51, 92},};// 使用头插法依次插入数据（后插入的在链表前端）InsertHeadLinkList(ll, &data[0]);InsertHeadLinkList(ll, &data[1]);InsertHeadLinkList(ll, &data[2]);InsertHeadLinkList(ll, &data[3]);InsertHeadLinkList(ll, &data[4]);// 输出头插后的链表（顺序应为：liubei → guanerge → wangmaizi → lisi → zhangsan）printf("----------------insert head----------------\n");ShowLinkList(ll);// 执行链表逆序操作ReverseLinkList(ll);// 输出逆序后的链表（顺序应为：zhangsan → lisi → wangmaizi → guanerge → liubei）printf("----------------reverse----------------\n");ShowLinkList(ll);// 释放链表内存DestroyLinkList(ll);return 0;
}

✅ 预期输出示例：

----------------insert head----------------
name: liubei, gender: m, age: 51, score: 92
name: guanerge, gender: m, age: 50, score: 91
name: wangmaizi, gender: f, age: 32, score: 90
name: lisi, gender: f, age: 23, score: 84
name: zhangsan, gender: m, age: 20, score: 80
----------------reverse----------------
name: zhangsan, gender: m, age: 20, score: 80
name: lisi, gender: f, age: 23, score: 84
name: wangmaizi, gender: f, age: 32, score: 90
name: guanerge, gender: m, age: 50, score: 91
name: liubei, gender: m, age: 51, score: 92

💡 说明：由于采用头插法，原始插入顺序为 zhangsan → liubei，但链表中实际顺序为反向。逆序后恢复为插入顺序。

使用链表实现字典查询

本部分使用单向链表构建一个简易字典系统，支持单词查找、插入、修改、删除等基本操作，数据从文件加载。

头文件定义（linklist.h）
#ifndef _LINKLIST_H_
#define _LINKLIST_H_// 定义字典条目数据类型
typedef struct person
{char word[50];       // 存储单词（关键词）char mean[512];      // 存储释义（解释内容）
} DATATYPE;// 链表节点结构
typedef struct node
{DATATYPE data;       // 节点存储的数据（一个字典条目）struct node *next;   // 指向下一个节点的指针
} LinkNode;// 链表管理结构
typedef struct list
{LinkNode *head;      // 指向链表第一个节点int clen;            // 当前链表中节点数量
} LinkList;// 函数声明
LinkList *CreateLinkList();                           // 创建空链表
int ShowLinkList(LinkList *list);                    // 显示所有条目
int IsEmptyLinkList(LinkList *list);                 // 判断链表是否为空
int InsertTailLinkList(LinkList *list, DATATYPE *data); // 尾部插入新条目
int InsertPosLinkList(LinkList *list, DATATYPE *data, int pos); // 指定位置插入
LinkNode *FindLinkList(LinkList *list, char *word);  // 根据单词查找节点
int ModifyLinkList(LinkList *list, char *name, DATATYPE *data); // 修改指定单词条目
int DestroyLinkList(LinkList *list);                 // 销毁链表并释放内存
int DeleteLinkList(LinkList *list, char *word);      // 删除指定单词条目（未在.c中实现？）
int GetSizeLinkList(LinkList *list);                 // 获取链表长度
DATATYPE *GetItemLinklist(LinkList *list, int pos);  // 获取指定位置条目#endif

✅ 功能说明：提供完整的字典操作接口，包括增删改查、遍历、定位等功能。

实现代码（linklist.c）
#include "linklist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 创建新链表，初始化头指针和长度
LinkList *CreateLinkList()
{LinkList *ll = malloc(sizeof(LinkList));if (NULL == ll){perror("CreateLinkList malloc");  // 分配失败时打印错误信息return NULL;}ll->head = NULL;ll->clen = 0;return ll;
}// 尾部插入新节点
int InsertTailLinkList(LinkList *list, DATATYPE *data)
{LinkNode *newnode = malloc(sizeof(LinkNode));if (NULL == newnode){perror("InsertTailLinkList malloc");return 1;}newnode->next = NULL;newnode->data = *data;  // 复制数据if (IsEmptyLinkList(list)){list->head = newnode;  // 首次插入}else{LinkNode *tmp = list->head;while (tmp->next)      // 找到最后一个节点{tmp = tmp->next;}tmp->next = newnode;   // 插入到末尾}list->clen++;return 0;
}// 判断链表是否为空
int IsEmptyLinkList(LinkList *list)
{return 0 == list->clen;
}// 打印链表中所有条目
int ShowLinkList(LinkList *list)
{LinkNode *tmp = list->head;while (tmp){printf("word:%s mean:%s\n", tmp->data.word, tmp->data.mean);tmp = tmp->next;}return 0;
}// 获取链表当前长度
int GetSizeLinkList(LinkList *list)
{return list->clen;
}// 在指定位置插入新条目（pos 从 0 开始）
int InsertPosLinkList(LinkList *list, DATATYPE *data, int pos)
{int len = GetSizeLinkList(list);if (pos < 0 || pos > len){fprintf(stderr, "InsertPosLinkList pos error\n");return -1;}if (pos == len){return InsertTailLinkList(list, data);  // 位置在末尾，调用尾插}else{LinkNode *tmp = list->head;int off = pos - 1;while (off--)  // 移动到插入位置的前一个节点{tmp = tmp->next;}LinkNode *newnode = malloc(sizeof(LinkNode));if (NULL == newnode){perror("InsertPosLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));  // 复制数据newnode->next = NULL;newnode->next = tmp->next;  // 新节点指向原下一个节点tmp->next = newnode;        // 前驱节点指向新节点}list->clen++;return 0;
}// 根据单词查找对应节点
LinkNode *FindLinkList(LinkList *list, char *word)
{LinkNode *tmp = list->head;while (tmp){if (0 == strcmp(tmp->data.word, word))  // 字符串匹配成功{return tmp;}tmp = tmp->next;}return NULL;  // 未找到返回 NULL
}// 获取指定位置的条目数据指针
DATATYPE *GetItemLinklist(LinkList *list, int pos)
{int len = GetSizeLinkList(list);if (pos < 0 || pos >= len){printf("pos is incorrect\n");return NULL;}LinkNode *tmp = list->head;for (int i = 0; i < pos; ++i){tmp = tmp->next;}return &tmp->data;  // 返回该位置数据的地址
}// 修改指定单词的条目内容
int ModifyLinkList(LinkList *list, char *name, DATATYPE *data)
{LinkNode *tmp = FindLinkList(list, name);if (NULL == tmp){printf("modify error\n");return 1;}memcpy(&tmp->data, data, sizeof(DATATYPE));  // 覆盖原有数据return 0;
}// 销毁整个链表，释放所有内存
int DestroyLinkList(LinkList *list)
{LinkNode *tmp = list->head;while (tmp){list->head = list->head->next;  // 先保存下一个节点free(tmp);                      // 释放当前节点tmp = list->head;}free(list);  // 释放链表结构体本身return 0;
}

✅ 关键点说明：

  • FindLinkList 使用 strcmp 精确匹配单词。
  • InsertPosLinkList 支持任意合法位置插入。
  • DestroyLinkList 安全释放所有节点，防止内存泄漏。
  • 所有函数均包含错误处理机制。
主程序测试（main.c）
#include <stdio.h>
#include <string.h>
#include "linklist.h"int main(int argc, char **argv)
{// 打开字典文件（假设路径正确且格式为：单词 释义）FILE *fp = fopen("/home/linux/dict.txt", "r");if (NULL == fp){perror("fopen");return 1;}// 创建链表用于存储字典条目LinkList *ll = CreateLinkList();if (NULL == ll){fprintf(stderr, "CreateLinkList error\n");return 1;}// 逐行读取文件内容并解析while (1){DATATYPE data;char *word = NULL;char *mean = NULL;char linebuf[1024] = {0};  // 缓冲区存储每行文本if (NULL == fgets(linebuf, sizeof(linebuf), fp)){break;  // 文件读取结束}word = strtok(linebuf, " ");           // 提取第一个单词（以空格分隔）mean = strtok(NULL, "\r");             // 提取剩余部分作为释义（去除回车）strcpy(data.word, word);               // 复制单词if (NULL != mean){while (*mean == ' ' || *mean == '\t')  // 跳过释义前的空白字符{mean++;}strcpy(data.mean, mean);           // 复制有效释义}InsertTailLinkList(ll, &data);         // 尾插法加入链表}// 进入交互查询模式while (1){char want_word[50] = {0};printf("input word: ");fgets(want_word, sizeof(want_word), stdin);                    // 读取用户输入want_word[strlen(want_word) - 1] = '\0';                       // 去除换行符if (0 == strcmp(want_word, "#quit"))                           // 输入 #quit 退出{break;}LinkNode *ret = FindLinkList(ll, want_word);                   // 查找单词if (NULL == ret){printf("can't find %s\n", want_word);                      // 未找到提示}else{printf("word:%s mean:%s\n", ret->data.word, ret->data.mean); // 显示释义}}fclose(fp);             // 关闭文件DestroyLinkList(ll);    // 释放链表内存return 0;
}

✅ 理想运行流程：

  1. 成功打开 dict.txt 文件；
  2. 每行解析出 word 和 mean，如：
    hello world this is a test
    → word="hello", mean="world this is a test"
  3. 用户输入单词后，系统查找并输出释义；
  4. 输入 #quit 结束程序；
  5. 程序正常释放资源，无内存泄漏。

📄 dict.txt 示例内容：

hello world this is a greeting
apple a fruit that grows on trees
cat a small domesticated carnivorous mammal
#quit

🖥️ 交互示例：

input word: hello
word:hello mean:world this is a greeting
input word: cat
word:cat mean:a small domesticated carnivorous mammal
input word: dog
can't find dog
input word: #quit

💡 注意事项：

  • 文件路径 /home/linux/dict.txt 需存在且可读；
  • 单词与释义之间用单个空格分隔；
  • 支持忽略释义前多余的空格或制表符；
  • 不区分大小写？——当前实现为严格匹配（区分大小写）。

✅ 总结：两道题分别实现了链表的逆序操作和字典应用，涵盖了链表的基本操作（创建、插入、查找、遍历、销毁）以及实际应用场景，代码结构清晰，具备基本错误处理能力。

http://www.xdnf.cn/news/18383.html

相关文章：

  • 服务器无公网ip如何对外提供服务？本地网络只有内网IP，如何能被外网访问？
  • Vue.prototype 的作用
  • JUC之CompletableFuture【中】
  • Redis Reactor 模型详解【基本架构、事件循环机制、结合源码详细追踪读写请求从客户端连接到命令执行的完整流程】
  • FPGA 在情绪识别领域的护理应用（一）
  • 论文阅读系列（一）Qwen-Image Technical Report
  • 中和农信如何打通农业科技普惠“最后一百米”
  • 企业架构是什么？解读
  • 通过分布式系统的视角看Kafka
  • python黑盒包装
  • Matplotlib数据可视化实战:Matplotlib图表注释与美化入门
  • 抓取手机游戏相关数据
  • LWIP流程全解
  • java实现url 生成二维码, 包括可叠加 logo、改变颜色、设置背景颜色、背景图等功能，完整代码示例
  • 【运维进阶】Ansible 角色管理
  • 记一次 .NET 某自动化智能制造软件 卡死分析
  • 流程进阶——解读 49页 2023 IBM流程管理与变革赋能【附全文阅读】
  • Redis缓存加速测试数据交互：从前缀键清理到前沿性能革命
  • 微服务-07.微服务拆分-微服务项目结构说明
  • 236. 二叉树的最近公共祖先
  • 从密度到聚类：DBSCAN算法的第一性原理解析
  • 100202Title和Input组件_编辑器-react-仿低代码平台项目
  • git 创用操作
  • 【集合框架LinkedList底层添加元素机制】
  • Python网络爬虫全栈教程 – 从基础到实战
  • 网络编程day4
  • 电商平台接口自动化框架实践
  • Codeforces 斐波那契立方体
  • 寻找旋转排序数组中的最小值
  • 企业知识管理革命：RAG系统在大型组织中的落地实践