玉林专业网站建设,Wordpress不能修改导航名称,泰兴住房和城乡建设厅网站,微信网页版手机端单链表的使用 1、基本概念2、链表的分类3、链表的基本操作a、单链表节点设计b、单链表初始化c、单链表增删节点**节点头插#xff1a;****节点尾插#xff1a;****新节点插入指定节点后#xff1a;**节点删除#xff1a; d、单链表修改节点e、单链表遍历#xff0c;并打印… 单链表的使用 1、基本概念2、链表的分类3、链表的基本操作a、单链表节点设计b、单链表初始化c、单链表增删节点**节点头插****节点尾插****新节点插入指定节点后**节点删除 d、单链表修改节点e、单链表遍历并打印数据 4、链表优缺点5、完整示例代码 1、基本概念
顺序表顺序存储的线性表。链式表链式存储的线性表简称链表。 既然顺序存储中的数据因为挤在一起而导致需要成片移动那很容易想到的解决方案是将数据离散地存储在不同内存块中然后在用来指针将它们串起来。这种朴素的思路所形成的链式线性表就是所谓的链表。
顺序表和链表在内存在的基本样态如下图所示
顺序表 链表
2、链表的分类 \quad 根据链表中各个节点之间使用指针的个数以及首尾节点是否相连可以将链表细分为如下种类 1.单向链表 2.单向循环链表 3.双向循环链表 \quad 这些不同链表的操作都是差不多的只是指针数目的异同。以最简单的单向链表为例其基本示意图如下所示 上图中所有的节点均保存一个指针指向其逻辑上相邻的下一个节点末尾节点指向空。 另外注意到整条链表用一个所谓的头指针 head 来指向由 head 开始可以找到链表中的任意一个节点。head 通常被称为头指针。
3、链表的基本操作
节点设计初始化空链表增删节点链表遍历(改查)销毁链表
下面着重针对这几项常见操作讲解单向链表的处理。
a、单链表节点设计
单向链表的节点非常简单节点中除了要保存用户数据之外这里以整型数据为例只需要增加一个指向本类节点的指针即可如下所示
typedef struct single_list{// 数据域--》真实的数据int data; // 以整型数据为例// 指针域struct single_list *next; // //用来指向下一个元素在内存中的首地址
}single_list_t;b、单链表初始化 \quad 首先空链表有两种常见的形式。一种是带头结点的一种是不带头结点的。所谓的头结点是不存放有效数据的节点仅仅用来方便操作如下 而不带头结点的空链表如下所示 \quad 由于头结点是不存放有效数据的因此如果空链表中带有头结点那么头指针 head 将永远不变这会给以后的链表操作带来些许便捷。 下面以带头结点的链表为例展示单向链表的初始化的示例代码
single_list_t *single_list_init()
{single_list_t *head_node malloc(sizeof(single_list_t));if (head_node ! NULL){head_node-next NULL;}return head_node;
}c、单链表增删节点 \quad 相对于顺序表需要整片移动数据链表增删节点只需要修改几个相关指针的指向动作非常快速。 \quad 与顺序表类似可以对一条链表中的任意节点进行增删操作示例代码
节点头插
int insert_list_head(int newdata, single_list_t *list)
{// 申请一个节点 -堆空间single_list_t *new_node malloc(sizeof(single_list_t));// 初始化数据域new_node-data newdata;new_node-next NULL;// 插入节点new_node-next list-next;list-next new_node;return 0;
}节点尾插
int insert_list(int newdata, single_list_t *list)
{// 申请一个节点 -堆空间single_list_t *new_node malloc(sizeof(single_list_t));// 初始化数据域new_node-data newdata;new_node-next NULL;// 定义指针p去找到链表的尾部single_list_t *p list;while (p-next ! NULL){p p-next;}// 此时p已经到最后一个节点的位置p-next new_node;return 0;
}新节点插入指定节点后
int insert_list_mid(int olddata, int newdata, single_list_t *list)
{// 找到要插入的节点single_list_t *p list;while (p-next ! NULL){p p-next;if (p-data olddata) // 待插入的节点在链表中间{break;}}// 申请一个新的节点 single_list_t *new_node malloc(sizeof(single_list_t));// 初始化数据域new_node-data newdata;new_node-next NULL;// p指向最后一个节点if (p-next NULL){// 最后一个节点是要插入的节点if (p-data olddata){new_node-next p-next; // 先让新增加的节点指向找到节点的下一个节点p-next new_node; // 再将该节点指向新增加的节点}else{printf(要插入的数据不存在\n);return -1;}}else // 遍历到中间找到需要插入的节点{new_node-next p-next; // 先让新增加的节点指向找到节点的下一个节点p-next new_node; // 再将该节点指向新增加的节点}return 0;
}节点删除
int list_delnode(int deldata, single_list_t *list)
{single_list_t *q list;single_list_t *p list-next;while (p-next ! NULL){// 找到要删除的节点并进行删除if (p-data deldata){q-next p-next; // 将q指向的节点指向被删除节点的下一个节点p-next NULL; // p节点的next指针指向NULLfree(p); // 释放p后此时p是野指针p q-next;// 将p指向被删除节点的下一个节点}else{p p-next;q q-next;} }// 遍历到最后一个节点if (p-next NULL){// 若最后一个节点是要删除的节点则删除if (p-data deldata){q-next p-next;p-next NULL;free(p);}else{printf(最后一个节点不是要删除的节点\n);return 0;}}
}d、单链表修改节点
int list_update_node(int old_data, int new_data, single_list_t *list)
{single_list_t *p list;while (p-next ! NULL){p p-next; // p指向下一个节点if (p-data old_data){p-data new_data;}}return 0;
}e、单链表遍历并打印数据
int list_show(single_list_t *list)
{single_list_t *p list;while (p-next ! NULL){p p-next;printf(当前p指向的节点数据:%d\n, p-data);}
}4、链表优缺点 \quad 链式存储中所有节点的存储位置是随机的他们之间的逻辑关系用指针来确定跟物理存储位置无关因此从上述示例代码可以很清楚看到增删数据都非常迅速不需要移动任何数据。另外又由于位置与逻辑关系无关因此也无法直接访问某一个指定的节点只能从头到尾按遍历的方式一个个找到想要的节点。简单讲链式存储的优缺点跟顺序存储几乎是相对的。 总结其特点如下
优点 a.插入、删除时只需要调整几个指针无需移动任何数据 b.当数据节点数量较多时无需一整片较大的连续内存空间可以灵活利用离散的内存 c.当数据节点数量变化剧烈时内存的释放和分配灵活速度快缺点 a.在节点中需要多余的指针来记录节点之间的关联 b.所有数据都是随机存储的不支持立即访问任意一个随机数据。
5、完整示例代码
#include stdio.h
#include stdlib.h// 1.封装一个结构体来表示单链表
typedef struct single_list{int data;struct single_list *next;
}single_list_t;// 2.初始化单链表--定义结构体变量 创建头节点
single_list_t *single_list_init()
{single_list_t *head_node malloc(sizeof(single_list_t));if (head_node ! NULL){head_node-next NULL;}return head_node;
}// 头插
int insert_list_head(int newdata, single_list_t *list)
{// 申请一个节点 -堆空间single_list_t *new_node malloc(sizeof(single_list_t));// 初始化数据域new_node-data newdata;new_node-next NULL;// 插入节点new_node-next list-next;list-next new_node;return 0;
}
/*brief:3.插入数据--尾插(在最后一个有效成员的后面插入数据)*param(in): newdata :待插入的数据 list:待插入的链表*param(out): *retval:
*/
int insert_list(int newdata, single_list_t *list)
{// 申请一个节点 -堆空间single_list_t *new_node malloc(sizeof(single_list_t));// 初始化数据域new_node-data newdata;new_node-next NULL;// 定义指针p去找到链表的尾部single_list_t *p list;while (p-next ! NULL){p p-next;}// 此时p已经到最后一个节点的位置p-next new_node;return 0;
}// 中间插入
int insert_list_mid(int olddata, int newdata, single_list_t *list)
{// 找到要插入的节点single_list_t *p list;while (p-next ! NULL){p p-next;if (p-data olddata){break;}}// 申请一个节点 -堆空间single_list_t *new_node malloc(sizeof(single_list_t));// 初始化数据域new_node-data newdata;new_node-next NULL;// p指向最后一个节点if (p-next NULL){if (p-data olddata){new_node-next p-next; // 先让新增加的节点指向找到节点的下一个节点p-next new_node; // 再将该节点指向新增加的节点}else{printf(要插入的数据不存在\n);return -1;}}else // 遍历到中间找到需要插入的节点{new_node-next p-next; // 先让新增加的节点指向找到节点的下一个节点p-next new_node; // 再将该节点指向新增加的节点}return 0;
}
// 删除节点
int list_delnode(int deldata, single_list_t *list)
{single_list_t *q list;single_list_t *p list-next;while (p-next ! NULL){// 找到要删除的节点并进行删除if (p-data deldata){q-next p-next; // 将q指向的节点指向被删除节点的下一个节点p-next NULL; // p节点的next指针指向NULLfree(p); // 释放p后此时p是野指针p q-next;// 将p指向被删除节点的下一个节点}else{p p-next;q q-next;} }// 遍历到最后一个节点if (p-next NULL){// 若最后一个节点是要删除的节点则删除if (p-data deldata){q-next p-next;p-next NULL;free(p);}else{printf(最后一个节点不是要删除的节点\n);return 0;}}
}
// 修改节点
int list_update_node(int old_data, int new_data, single_list_t *list)
{single_list_t *p list;while (p-next ! NULL){p p-next; // p往后移动if (p-data old_data){p-data new_data;}}return 0;
}// 4.遍历链表,打印节点数据
int list_show(single_list_t *list)
{single_list_t *p list;while (p-next ! NULL){p p-next;printf(当前p指向的节点数据:%d\n, p-data);}
}int main(int argc, char const *argv[])
{// 初始化单链表single_list_t *my_list single_list_init();// 往链表插入数据insert_list(15, my_list);insert_list(18, my_list);insert_list(15, my_list);insert_list(25, my_list);insert_list(666, my_list);insert_list(123, my_list);insert_list(11111111, my_list);insert_list_mid(666, 777, my_list);insert_list_mid(1, 222, my_list);insert_list_head(15, my_list);printf(插入的节点\n);list_show(my_list);printf(插入的节点\n);// 删除节点list_delnode(25,my_list);printf(删除后的节点\n);list_show(my_list); // 打印数据printf(删除后的节点\n);// 修改数据list_update_node(123, 234, my_list);printf(修改后的节点\n);list_show(my_list); // 打印数据printf(修改后的节点\n);return 0;
}
/*
执行结果
要插入的数据不存在
插入的节点
当前p指向的节点数据:15
当前p指向的节点数据:15
当前p指向的节点数据:18
当前p指向的节点数据:15
当前p指向的节点数据:25
当前p指向的节点数据:666
当前p指向的节点数据:777
当前p指向的节点数据:123
当前p指向的节点数据:11111111
插入的节点
最后一个节点不是要删除的节点
删除后的节点
当前p指向的节点数据:15
当前p指向的节点数据:15
当前p指向的节点数据:18
当前p指向的节点数据:15
当前p指向的节点数据:666
当前p指向的节点数据:777
当前p指向的节点数据:123
当前p指向的节点数据:11111111
删除后的节点
修改后的节点
当前p指向的节点数据:15
当前p指向的节点数据:15
当前p指向的节点数据:18
当前p指向的节点数据:15
当前p指向的节点数据:666
当前p指向的节点数据:777
当前p指向的节点数据:234
当前p指向的节点数据:11111111
修改后的节点
*/
