链表是一种常见的数据结构,其中运用到了结构体指针,链表可以实现动态存储分配,换而言之,链表是一个功能强大的数组,可以在某个节点定义多种数据类型,可以实现任意的添加,删除,插入节点等。(废话结束
前置知识:
地址,结构体,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;//将结点名定义为Node
typedef Node* List;//相当于Node List[]
//一个结点数组就是一个链表
将多个结点通过next相连就变成了一个链表。
链表操作
链表操作一般分为六部分:建立链表,插入结点,删除结点,查找结点,更新结点,遍历链表。我们将这六步写为六个函数依次实现。
建立链表:
创建一个空链表,初始化头节点,并将头节点的指针置为NULL(在这里提一下,链表是没有规定长度的,我们一般在遍历到结点->next==NULL时认为链表结束)
void BuildList(List& L){
node=(Node*)malloc(sizeof(Node));//申请一个结点内存
//申请内存
if(!node){//node==NULL时
cout<<"申请失败\n";
return;
}
node->next=NULL;
}
调用函数后,链表结构如下:(一个结点,data为空,看作头节点)
插入结点:
插入结点分为两种方式:头插法和尾插法,我们通过动图来演示一下
尾插法:
头插法:
可以比较清楚的看出两者的差异,尾插法是将新建结点插入到链表末尾,头插法是将新建结点插入到链表头节点后面。下面分别是两种方法的代码实现:
void Postinsert(List& L){//尾插法
Node* node=(Node*)malloc(sizeof(Node));
//申请一个结点内存
L->next=node;
//尾结点更新为node
node->next=NULL;
//尾结点下一位为NULL
}
void Preinsert(List& L){//头插法
Node node=(Node*)malloc(sizeof(Node));
//申请一个结点内存
node->next=L->next;
//node结点下一位应为原来头节点下一位
L->next=node;
//将node放入头节点的next位
}
删除结点:
找到要删除的节点,并将其删除,之后将删除节点的两侧相连。
动图演示如下:
代码实现如下:
void DeleteNode(List& L,int t){//删除第t个结点
Node* node=L->next;
//定义结点指针
Node* pre=L;
//定义结点前一位指针
while(--t){
//while循环遍历第t个结点
if(node==NULL){//当结点不存在时
cout<<"此结点不存在\n";
break;
}
pre=node;
node=node->next;
//更新pre,node指针
}
free(node);//释放内存
}
查找结点:
查找到 data为t 结点位于链表的第几位,并return位置
动图演示如下:
代码实现如下:
int SearchNode(List& L,int T){//查找data为T的结点
int cnt=1;//记录位数
Node* node=L->next;
while(node!=NULL){
if(node->data==T)
return cnt;
//找到时return位数
node=node->next;
cnt++;//更新node指针与位数
}
cout<<"未找到结点\n";
return -1;
}
更新结点:
找到要更新的节点位置,并将其data更新。
动图演示如下:
void UpdateNode(List& L,int a,int b){//将第a个结点data更新为b
Node* node=L->next;
//定义结点指针
int cnt=1;
//cnt用于计数
while(node!=NULL){
//while循环遍历找到第a个结点
if(cnt==a){//找到结点时
node->data=b;//update
break; //停止循环
}
cnt++;
node=node->next;
//更新cnt和结点指针
}
if(node==NULL)//结点不存在时
cout<<"该结点不存在\n";
}
遍历链表:
遍历整个链表,输出每个结点的值
动图演示如下:
代码实现如下:
void ErgodicList(List& L){//遍历输出
Node* node=L->next;
cout<<"链表遍历结果如下:\n";
while(node!=NULL){
cout<<node->next<<" ";
node=node->next;
}
cout<<"\n";
}
结束文章来源:https://www.toymoban.com/news/detail-703842.html
文章来源地址https://www.toymoban.com/news/detail-703842.html
到了这里,关于单向链表(c/c++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!