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

数据结构-单向链表

ai 2025/8/6 10:44:11

1.什么是数据结构

数据结构：用来组织和存储数据
程序设计 = 数据结构 + 算法

2. 数据与数据之间的关系

1）逻辑结构：数据元素与元素之间的关系

集合：元素与元素之间平等的集合关系
线性结构：数据元素与元素之间存在一对一的关系(顺序表、链表、队列、栈)
树形结构：数据元素与元素之间存在一对多的关系（二叉树）
图形结构：数据元素与元素之间存在多对多的关系 (网状结构)
2）物理结构：数据元素在计算机内存中的存储方式
顺序结构：在内存中选用一段连续的内存空间进行存储

1.数据访问方便（O（1））
2.插入和删除数据时需要移动大量数据
3.需要预内存分配
4. 可能造成大量的内存碎片

链式结构：可以在内存中选用一段非连续的内存空间进行存储

1. 数据访问时必须要从头遍历（O（n））
2. 插入和删除元素方便
3. 不需要预内存分配，是一种动态存储的方式
索引结构：将要存储的数据的关键字和存储位置之间构建一个索引表。
散列结构（哈希结构）：将数据的存储位置与数据元素之间的关键字建立起对应的关系（哈数函数），根据该关系进行数据存储和查找

3.单向链表

（1）一般形式

（2）操作

1. 创建链表对象
2. 插入数据（头插、尾插）
3. 删除数据（头删、尾删）
4. 查找数据
5. 修改数据
6. 销毁链表

（3）快慢指针

慢指针 (slow pointer)：通常每次移动一个节点
快指针 (fast pointer)：通常每次移动两个节点（也可以是其他固定步长）

（4）例题

①查找链表中间位置

Node_t *find_Mid_link(Link_t *plink)
{Node_t *pfast = plink->phead;Node_t *pslow = pfast;if(NULL == plink){return NULL;}while(pfast != NULL){pfast = pfast->pnext;if(NULL == pfast){break;}pfast = pfast->pnext;pslow = pslow->pnext;}return pslow;
}

算法思想：
初始化阶段：
创建两个指针pfast和pslow，初始都指向链表头节点
检查链表是否为空（NULL == plink）
双指针遍历阶段：
快指针(pfast)：每次移动两步（pfast = pfast->pnext->pnext）
慢指针(pslow)：每次移动一步（pslow = pslow->pnext）
在快指针每次移动第二步前检查是否已到链表末尾（NULL == pfast）
终止条件：
当快指针pfast到达链表末尾（pfast == NULL）时停止
此时慢指针pslow指向的就是链表的中间节点
返回结果：
直接返回慢指针pslow指向的节点

②找个链表中倒数第k个元素

Node_t *find_k_link(Link_t *plink, int k)
{Node_t *pfast = plink->phead;Node_t *pslow = pfast;if(NULL == plink){return NULL;}for(int i = 0;i < k;++i){if(NULL == pfast){return NULL;}pfast = pfast->pnext;}while(NULL != pfast){pfast = pfast->pnext;pslow = pslow->pnext;}return pslow;}

算法思想：
初始化阶段：
设置两个指针pfast和pslow，初始都指向链表头节点
检查链表是否为空（NULL == plink）
快指针先行阶段：
快指针pfast先向前移动K步（for循环）
在移动过程中检查是否超出链表长度（NULL == pfast）
如果K大于链表长度，直接返回NULL
双指针同步移动阶段：
当快指针pfast移动K步后
同时移动快指针pfast和慢指针pslow，每次各移动一步
直到快指针pfast到达链表末尾（NULL != pfast）
结果返回：
当快指针pfast为NULL时，慢指针pslow正好指向倒数第K个节点
返回pslow指针

③对链表进行倒序

void reverse_link(Link_t *plink)
{if(NULL == plink){return ;}Node_t *ptmp = plink->phead;Node_t *pinsert;plink->phead = NULL;while(ptmp != NULL){pinsert = ptmp;ptmp = ptmp->pnext;pinsert->pnext = plink->phead;plink->phead = pinsert;}
}

算法思想：
初始化阶段：
保存原链表头节点指针(ptmp)
将链表头指针(plink->phead)置为NULL，准备构建新链表
逆置过程：
遍历原链表：使用ptmp指针逐个访问原链表节点
处理每个节点(pinsert)：
a. 保存当前节点(pinsert = ptmp)
b. 移动ptmp到下一个节点(ptmp = ptmp->pnext)
c. 将当前节点插入到新链表头部：
当前节点的next指向新链表头(pinsert->pnext = plink->phead)
更新链表头为当前节点(plink->phead = pinsert)
终止条件：
当ptmp为NULL时，表示原链表已全部处理完毕

④用插入排序的算法对链表进行排序

void sort_link(Link_t *plink)
{if(NULL == plink){return ;}Node_t *ptmp = plink->phead->pnext;Node_t *pinsert = NULL;plink->phead->pnext = NULL;while(ptmp != NULL){pinsert = ptmp;ptmp = ptmp->pnext;if(plink->phead->data >= pinsert->data){pinsert->pnext = plink->phead;plink->phead = pinsert;}else{Node_t *p = plink->phead;while(p->pnext != NULL && p->pnext->data < pinsert->data){p = p->pnext;}pinsert->pnext = p->pnext;p->pnext = pinsert;}}
}

算法思想：
初始化阶段：
将原链表头节点之后的节点(ptmp)逐个取出进行排序
初始化一个"已排序链表"，开始时只包含原头节点
排序过程：
外层循环：遍历原链表的每个未排序节点(ptmp)
处理每个节点(pinsert)：
a. 若节点值 ≤ 已排序链表头节点值：
直接插入到链表头部
b. 否则：
在已排序链表中顺序查找插入位置
找到第一个大于当前节点值的节点的前驱位置
将当前节点插入到该位置
终止条件：
当所有未排序节点(ptmp)都处理完毕时结束