河南省监理协会官方网站建设,室内设计知名网站,长春网站建设及推广,企业信息网页模板链表是一种常见的数据结构#xff0c;其中运用到了结构体指针#xff0c;链表可以实现动态存储分配#xff0c;换而言之#xff0c;链表是一个功能强大的数组#xff0c;可以在某个节点定义多种数据类型#xff0c;可以实现任意的添加#xff0c;删除#xff0c;插入节… 链表是一种常见的数据结构其中运用到了结构体指针链表可以实现动态存储分配换而言之链表是一个功能强大的数组可以在某个节点定义多种数据类型可以实现任意的添加删除插入节点等。废话结束 前置知识
地址,结构体,malloc函数与循环选择结构。 那我们先来学习一下malloc函数
/*
格式为
(数据类型*)malloc(申请内存大小)
malloc函数可以通过传入要申请的内存大小在总堆里申请内存
之后会回归一个地址在其前面的(数据类型*)是将这个地址定义
为要求数据类型。
*/int* ptr(int*)malloc(sizeof(int));
/*
sizeof是一个传入数据类型返回其所占内存的函数
那么sizeof(int),就是一个int类型的数所占的内存
之后将申请到的内存转换为int类型存储
*/int* ptd(int*)malloc(5*sizeof(int));
//申请的内存大小为5*sizeof(int)也就是五个int类型的数字
之后我们来看通过结构体定义的链表节点
typedef struct Node{int data;//存储数据Node* next;//存储下个结点地址
}Node;//将结点名定义为Nodetypedef Node* List;//相当于Node List[]
//一个结点数组就是一个链表 将多个结点通过next相连就变成了一个链表。 链表操作 链表操作一般分为六部分建立链表插入结点删除结点查找结点更新结点遍历链表。我们将这六步写为六个函数依次实现。 建立链表 创建一个空链表初始化头节点并将头节点的指针置为NULL(在这里提一下链表是没有规定长度的我们一般在遍历到结点-nextNULL时认为链表结束) void BuildList(List L){node(Node*)malloc(sizeof(Node));//申请一个结点内存//申请内存if(!node){//nodeNULL时cout申请失败\n;return;}node-nextNULL;
}
调用函数后链表结构如下一个结点data为空看作头节点 插入结点 插入结点分为两种方式头插法和尾插法我们通过动图来演示一下 尾插法: 头插法 可以比较清楚的看出两者的差异尾插法是将新建结点插入到链表末尾头插法是将新建结点插入到链表头节点后面。下面分别是两种方法的代码实现
void Postinsert(List L){//尾插法Node* node(Node*)malloc(sizeof(Node));//申请一个结点内存L-nextnode;//尾结点更新为node node-nextNULL;//尾结点下一位为NULL
}
void Preinsert(List L){//头插法Node node(Node*)malloc(sizeof(Node));//申请一个结点内存node-nextL-next;//node结点下一位应为原来头节点下一位 L-nextnode;//将node放入头节点的next位
} 删除结点 找到要删除的节点并将其删除之后将删除节点的两侧相连。 动图演示如下 代码实现如下
void DeleteNode(List L,int t){//删除第t个结点Node* nodeL-next;//定义结点指针Node* preL;//定义结点前一位指针while(--t){//while循环遍历第t个结点if(nodeNULL){//当结点不存在时cout此结点不存在\n;break;}prenode;nodenode-next;//更新prenode指针}free(node);//释放内存
} 查找结点 查找到 data为t 结点位于链表的第几位并return位置 动图演示如下 代码实现如下
int SearchNode(List L,int T){//查找data为T的结点int cnt1;//记录位数Node* nodeL-next;while(node!NULL){if(node-dataT)return cnt;//找到时return位数nodenode-next;cnt;//更新node指针与位数}cout未找到结点\n;return -1;
} 更新结点 找到要更新的节点位置并将其data更新。 动图演示如下 void UpdateNode(List L,int a,int b){//将第a个结点data更新为bNode* nodeL-next;//定义结点指针int cnt1;//cnt用于计数while(node!NULL){//while循环遍历找到第a个结点if(cnta){//找到结点时node-datab;//updatebreak; //停止循环}cnt;nodenode-next;//更新cnt和结点指针}if(nodeNULL)//结点不存在时cout该结点不存在\n;
} 遍历链表 遍历整个链表输出每个结点的值 动图演示如下 代码实现如下
void ErgodicList(List L){//遍历输出Node* nodeL-next;cout链表遍历结果如下\n;while(node!NULL){coutnode-next ;nodenode-next;}cout\n;
}
结束
