7-数据结构-(带头节点)单链表的增删改查

这篇具有很好参考价值的文章主要介绍了7-数据结构-(带头节点)单链表的增删改查。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题:

        单链表带头结点的创建以及输出,以及带与不带头节点的区别

思路:

  1. 单链表,逻辑上是线性结构,由许多单链表结点,串成一串。其单链表结构体中,数据项由data数据域和结点指针域。
  2. 带头节点是为了使在空表时的操作更统一。如果不带头节点,空表插入时,直接让头指针,和第一节点指针相等即可。而非空表插入时,则时s->next=l->next;l->next=s;头插,两个操作。而带上头节点,所有情况下的插入操作,都同意了即都为s->next=l->next;l->next=s。
  3. 值得注意的是,带头节点的单链表,遍历输出时,记得从第二哥结点开始遍历,即让结点指针=头指针的指针域。即snode*s =l->next;
  4. 在指针改变实际值时,C语言中,要么来哥双指针,要么正常一维指针,最后返回头指针,主函数内接收即可。我觉得为了好理解,就用返回这个吧,整那么花里胡哨,也挺乱的。嗯

头插法:

//创建带头节点的单链表
snode* sheadlist(snode* l,int n)
{
		snode *phead=l;      
		phead=(snode*)malloc(sizeof(snode));//创建头节点 
		phead->next=NULL;  
		
		int i=0,x=n,k=0;
		printf("请输入想要插入的值\n");
		for(i=0;i<x;i++)
		{
			printf("输入第%d个值\n",i+1);
			scanf("%d",&k);
			snode *p=(snode*)malloc(sizeof(snode));
			p->data=k;
			p->next=phead->next;
			phead->next=p;
				
		}
		
		return phead;
} 

尾插法:

//创建带头结点尾插法 
linklist srearlist(linklist l,int x)
{
	snode* phead=l;//创建头节点
	phead=(linklist)malloc(sizeof(snode));//用头结点创造空间,指针l没有创建,因此返回的时候返回头节点 才能获取整个单链表地址 
	phead->next=NULL;
	int i,k;
	snode *end=phead;//工作指针,从头节点开始工作 
	printf("请输入值\n");
	for(i=0;i<x;i++)
	{

		scanf("%d",&k);
	
		snode *p=(snode*)malloc(sizeof(snode));//创建新结点,用来尾插进单链表 
		p->data=k;
		
		end->next=p;//直接给新结点连接起来 
		end=p;      //因为尾插,所以要时刻知道最后一个结点的位置,因此s指针也跑到新加入的结点p上面. 
	}
	end->next=NULL;	
	
	return phead;//头节点始终指向整个单链表,因此返回头节点地址,用来获取整个字符串 
} 

按位查找,返回结点:

//返回第i个结点指针
snode* Searchnode(snode* phead,int i)
{
	int count=1;//从有序数据,数组第一个开始计算
	snode* p=phead->next;
	if(i==0) return phead;//返回头节点
	if(i<0) return NULL;  //无效值
	while(p!=NULL && count != i)  //进行遍历,每一次进行比对,每次遍历指针后移
	{
		p=p->next;
		count++;
	}
	
	return p;	
} 

按值查找,返回位置:(根据不同的情况需求在while判断条件那里改变条件,进而求得想要的位置即可)

//按值查找,查找比x大的,并返回应插入的位置 
int Search_zhinode(snode* phead,int x)
{

	snode* p=phead->next;
	int count=1;
	while(x>p->data)
	{
		p=p->next;
		count++;
	}
	
	
	return count;	
} 

在某个位置插入一个结点:(按位查找的妙用:

(用按位查找找到第i-1个结点,通过这个结点,进行操作))

//在某个位置插入一个结点 
snode* SInsert(snode* phead,int pos,int x)
{
	if(pos<1 || pos>SLength(phead)) return NULL;
    //进行插入操作
	snode* p=(snode*)malloc(sizeof(snode));
	p->data=x;
	//获取第pos-1个位置上的结点,在它后面插入 
	snode* ppre=Search_weinode(phead,pos-1);
	p->next=ppre->next;
	ppre->next=p;
	
	return phead;
}

计算带头结点单链表长度:

//计算单链表长度
int SLenth(snode* phead)
{
	if(phead==NULL) return 0;
	
	int count=1;
	snode* p =phead->next;//从有效数据第一个开始 
	while(p->next!=NULL)
	{
		p=p->next;
		count++;
	}
	return count;
 } 

删除第i个结点:(用按位查找找到第i-1个结点,通过这个结点,进行操作)

//删除第i个结点 
snode* SDelete(snode* phead,int i,int *x)
{
	if(i<1 || i>SLenth(phead)) return NULL;
	
	snode* p =Search_weinode(phead,i-1);
	snode* q=p->next;
	*x=q->data;
	
	p->next=q->next;
	free(q);
	return phead;
}


 

代码如下:文章来源地址https://www.toymoban.com/news/detail-628943.html

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//创建带头结点单链表 
typedef struct snode
{
	int data;
	struct snode *next;
}snode,*linklist;
//创建带头节点的单链表
snode* sheadlist(linklist l,int n)
{
		snode *phead=l;      
		phead=(snode*)malloc(sizeof(snode));//创建头节点 
		phead->next=NULL;  
		
		int i=0,x=n,k=0;
		printf("请输入想要插入的值\n");
		for(i=0;i<x;i++)
		{
			printf("输入第%d个值\n",i+1);
			scanf("%d",&k);
			snode *p=(snode*)malloc(sizeof(snode));
			p->data=k;
			p->next=phead->next;
			phead->next=p;
				
		}
		
		return phead;
} 

//创建带头结点尾插法 
linklist srearlist(linklist l,int x)
{
	snode* phead=l;//创建头节点
	phead=(linklist)malloc(sizeof(snode));//用头结点创造空间,指针l没有创建,因此返回的时候返回头节点 才能获取整个单链表地址 
	phead->next=NULL;
	int i,k;
	snode *end=phead;//工作指针,从头节点开始工作 
	printf("请输入值\n");
	for(i=0;i<x;i++)
	{

		scanf("%d",&k);
	
		snode *p=(snode*)malloc(sizeof(snode));//创建新结点,用来尾插进单链表 
		p->data=k;
		
		end->next=p;//直接给新结点连接起来 
		end=end->next;      //因为尾插,所以要时刻知道最后一个结点的位置,因此s指针也跑到新加入的结点p上面. 
	}
	end->next=NULL;	
	
	return phead;//头节点始终指向整个单链表,因此返回头节点地址,用来获取整个字符串 
} 
//返回第i个结点指针
snode* Search_weinode(snode* phead,int i)
{
	int count=1;
	snode* p=phead->next;//从头节点的后继节点开始遍历 
	if(i==0) return phead;
	if(i<0) return NULL;
	//遍历,当值小于查找值时,一直遍历,直到相等,count停止增加,此时便时所找位置处的结点,返回即可, 
	while(p!=NULL && count != i)
	{
		p=p->next;
		count++;
	}
	
	return p;	
} 
//按值查找,查找比x大的,并返回应插入的位置 
int Search_zhinode(snode* phead,int x)
{
	//默认单链表单调递增,因此从头遍历的话,看谁比x大,便找到了,主要画图清楚 
	snode* p=phead->next;
	int count=1;
	while(x>p->data)
	{
		p=p->next;
		count++;
	}
	
	
	return count;	
} 

void slprintf(snode *s)
{
	if(s==NULL) return NULL; //空表 情况 
	
	snode *scan = s->next;//因为带头结点第一个结点为头节点,所以打印从第二个结点打印,因此这里需要注意 
	while(scan != NULL) 
	{
		printf("%d->",scan->data);
		scan = scan->next;
	}                   
	 
	printf("NULL\n");
}
//在某个位置插入一个结点 
snode* SInsert(snode* phead,int pos,int x)
{
	//进行插入操作
	//创建需要插入的结点,给结点赋值 
	snode* p=(snode*)malloc(sizeof(snode));
	p->data=x;
	//获取第pos-1个位置上的结点,在它后面插入 
	snode* ppre=Search_weinode(phead,pos-1);
	//进行插入操作 
	p->next=ppre->next;
	ppre->next=p;
	
	return phead;
}
//计算单链表长度
int SLenth(snode* phead)
{
	if(phead==NULL) return 0;
	
	int count=1;
	snode* p =phead->next;//从有效数据第一个开始 
	while(p->next!=NULL)
	{
		p=p->next;
		count++;
	}
	return count;
 } 
//删除第i个结点 
snode* SDelete(snode* phead,int i,int *x)
{
	//判断插入合法性 
	if(i<1 || i>SLenth(phead)) return NULL;
	//找到删除结点的前驱结点 
	snode* p =Search_weinode(phead,i-1);//用按位查找,找到后返回前驱结点 
	//给q删除,因此先让q指针指向删除结点,取出值,随后p的指针域指向q的后继节点,最后给q释放。 
	snode* q=p->next;
	*x=q->data;
	//删除操作 
	p->next=q->next;
	free(q);
	return phead;
}

int main()
{
	//创建头节点 
	snode* phead;
//	phead=sheadlist(phead,3);
	//尾插法建立带头节点单链表 
	phead=srearlist(phead,5); 
	//打印单链表 
	slprintf(phead);
//	snode *p=Searchnode(phead,2);
	//在有序的列表里面(默认有序),插入数值4,单链表仍有序 
	int pos=Search_zhinode(phead,4);
	printf("pos=%d\n",pos);
	//找到需要插入的位置后,进行在pos处的插入操作——即找到pos的前驱结点,之后进行插入 
	phead=SInsert(phead,pos,4);
	slprintf(phead);
	//计算单链表的长度 
	int len=SLenth(phead);
	printf("单链表长度为%d\n",len);
	//删除第4个结点,并返回删除结点的数值 
	int x=0;
	phead=SDelete(phead,4,&x);//因为需要给删除数值带回来,所以给x的地址传过去 
	printf("删除了%d\n",x);
	slprintf(phead);
	return 0;
 } 

到了这里,关于7-数据结构-(带头节点)单链表的增删改查的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(68)
  • 数据结构:图文详解单链表的各种操作(头插法,尾插法,任意位置插入,删除节点,查询节点,求链表的长度,清空链表)

    目录  一.什么是链表 二.链表的实现 节点的插入 头插法 尾插法 指定位置插入 节点的删除 删除第一次出现的节点 删除所有节点 节点的查找 链表的清空 链表的长度 前言: 在上一篇文章中,我们认识了线性数据结构中的顺序表,而本篇文章则是介绍线性数据结

    2024年02月05日
    浏览(57)
  • 带头节点的单链表的思路及代码实现

    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) +指针(指示后继元素存储位置,元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。) 以上是

    2023年04月08日
    浏览(38)
  • 数据结构(2)—单链表(带头结点和不带头结点)

            单链表 是通过一组任意的存储单元来存储线性表中的数据元素。每个结点都有 data数据域 (用来存放数据元素)和 next指针域 (用来存放后继节点的地址)。         对于顺序表,单链表可以解决顺序表需要一整个大量的连续的存储单元的缺点,单链表的元素

    2024年02月05日
    浏览(53)
  • 【数据结构】C语言实现单链表(带头结点)

    Single linked list with leading nodes 关于不带头结点的单链表:不带头结点的单链表 结点定义: 接口定义: 初始化需要申请头结点,让头指针指向空的头结点。 将申请结点的代码进行封装: 需要越过头结点 找到尾结点,然后插入到尾结点的后面。 对比不带头结点的单链表的尾插

    2024年02月02日
    浏览(203)
  • 数据结构-带头双向循环链表的实现

    前言           带头双向循环链表是一种重要的数据结构,它的结构是很完美的,它弥补了单链表的许多不足,让我们一起来了解一下它是如何实现的吧!         它的节点中存储着数据和两个指针,一个 指针_prev 用来记录前一个节点的地址,另一个指针 _next 用来记录后一

    2024年02月13日
    浏览(47)
  • 【数据结构】双向带头循环链表的实现

    前言:在前面我们学习了顺序表、单向链表,今天我们在单链表的基础上进一步来模拟实现一个带头双向链表。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博主和博主一起学习!一起努力! 带头双向循环链

    2024年01月15日
    浏览(49)
  • 数据结构——带头节点的双向循环列表

    带头节点的双向循环链表 是一种特殊的双向链表,它与普通的双向链表相比,最大的区别是链表头结点的 next 指针不再指向第一个实际节点,而是指向链表中的第一个节点。同时,链表尾结点的 prev 指针也不再指向 NULL,而是指向链表中的最后一个节点。 另外, 带头节点的

    2024年02月11日
    浏览(46)
  • 数据结构三:线性表之单链表(带头结点单向)的设计与实现

            线性表的链式存储结构正是所谓的单链表,何谓单链表?通过地址将每一个数据元素串起来,进行使用,这可以弥补顺序表在进行任意位置的插入和删除需要进行大量的数据元素移动的缺点,只需要修改指针的指向即可;单链表的种类又可划分为很多种,本篇博客详

    2024年02月19日
    浏览(61)
  • 【数据结构】—带头双向循环链表的实现(完美链表)

    链表结构一共有八种形式,在前面的文章里已经讲完了不带头单向非循环链表的实现,但是我们发现该链表实现尾插与尾删时比较麻烦,要先从头节点进行遍历,找到尾节点,时间复杂度为O(N),而本次所讲的带头双向循环单链表,则可以直接找到尾节点。 虽然该链表看起来

    2024年01月25日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包