7-数据结构-单链表的插入删除操作

2023-11-16

问题:

单链表的各种插入和删除操作。

思路:

(1)按位插入(带头结点):

  1. 创建一个单链表结点。——typedef struct lnode{ int data; lnode *next}lnode,*linklist;
  2. 初始化单链表——void inilist(linklist &l)
  3. 进行插入操作——bool listinsert(linklist &l,int i,int e) //  i表示插入位置,e表示插入的数值
  4. 插入函数中,我们先判断插入位置是否有误——if(i<1)return false;//因为带头结点,实际存储位置就是从数组下标1开始的,所以,插入位置应该大于等于1
  5. 之后,要想在第i个位置插入,需要先知道第i-1个位置在哪,所以找位置。
  6. 定义一个结构体指针lnode*p;让他开始指向头结点。——p=l;
  7. 在定义一个变量 j 表示p指针所指的位置(这是为了计算出p最后的位置)——int j=0;
  8. 来个while循环,终止条件为p不指向空,并且p所指位置,等于i-1时,跳出循环,所以j才<i-1,而不是=i-1;——while(p!=NULL&& j<i-1)
  9. 每次循环,p就往右移一位——p=p->next,j随之跟着变,j++从而保证j表示p所指的位置。
  10. 找到位置后,判断p是否为空,为空则无效,返回false;
  11. 之后进行连接,创一块空间,数据类型为lnode——lnode *s=(lnode*)malloc(sizeof(lnode));
  12. 然后给该空间数据域赋值——s->data=e;
  13. 之后该空间的指针域指向i-1的下一个位置,即——s->next=p->next;
  14. 随后p指向该空间——p->next=s;

代码如下:

bool listinsert(linklist &l,int i,int e)
{
	if(i<1)
	{
		return false;
	}
	//找出第i-1的结点 
	lnode* p;
	p=l;
	int j=0;//表示p所指向的结点 
	while(p!=NULL && j<i-1)//找到第i-1的结点,因此不能<=i-1,应< ,while循环,先判断,再变化。 
	{
		p=p->next;  //每次循环,p结点从头结点,往后移1位。 
		j++;
	}
	
	//创建新节点,进行连接 
	if(p==NULL)
	return false;
	
	lnode* s=(lnode*)malloc(sizeof(lnode));
	s->data=e;//数据域赋值 
	s->next=p->next;
	p->next=s;
	return true;
}

(2)按位插入(不带头结点)

  1. 由于单链表不带头结点,因此在插入第一位时,需要额外进行一步插入操作。
  2. 之后与带结点操作一样。

代码如下:
 

bool notouinsert(linklist &l,int i,int e)//无头结点 插入 
{
	if(i==1)
	{
		lnode *s=(lnode*)malloc(sizeof(lnode));
		s->data=e;
		s->next=l;
		l=s;  //头指针,指向s ,这里l为头指针,没头结点 
		return true;
	}
	lnode *p=l;
	int j=1;
	while(p!=NULL&&j<i-1)
	{
		p=p->next;
		j++;	
	} 
	if(p==NULL)
	return false;
	lnode *s=(lnode*)malloc(sizeof(lnode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

(3)指定结点后插操作

  1. 就是在该节点之后,插入节点并赋值,相当于按位插入最后一步。
  2. bool houcha(lnode *p,int e)——结点以及插入值

代码如下:
 

bool houcha(lnode *p,int e) //后插操作 
{
	lnode *s=(lnode*)malloc(sizeof(lnode));//由于直接可以在该节点后插入,所以直接给结点赋值扩展空间
	if(s==NULL)
	return false;
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true; 
} 

有了这个后插操作函数,下次写按位插入时,最后一步可以直接写该函数。

如这样:

bool insertlist(linklist &l,int i,int e)//带头结点   插入 
{
	if(i<1)
	return false;
	lnode* p;
	p=l;
	int j=0;
	while(p!=NULL && j<i-1)
	{
		p=p->next;
		j++;
	}
	houcha(p,e);
	return true;
	
}

(4)指定节点——前插操作

  1. 在一个节点前,插入一个节点。
  2. bool qiancha(lnode *p,lnode* s)——在p节点前插入s节点。
  3. 我们需要先在p节点之后,创建节点或者给需要插入的结点放在后面先——为了最后数据对换,p中的数据跑s中,s中跑p中。
  4. 先判断,两个结点是否为空,为空,返回false;
  5. 之后给链,穿起来。s->next=p-next;  p->next = s;
  6. 然后定义一个中间值,用来存放p中data域的数值。 int temp = p-data;
  7. 这时候就可以放心给p->data中赋值,给s结点中的数值赋值给p结点——p->data=s->data;
  8. 再给中间值存放的原p的值存进s结点中。——s->data=temp;

代码如下:

bool charu(lnode *p,lnode *s)
{
	if(p==NULL ||s==NULL)
	return false;
	
	s->next=p->next;
	p->next=s;
	
	int temp =p->data;
	p->data=s->data;
	s->data=temp;
	return true; 
}

(5)按位序删除结点(带头结点)

  1. 删除节点,还是需要找到第i-1个结点。
  2. 然后再新建个q指向被删除结点,给删除节点数据赋值给e带回去。
  3. 随后p节点直接指向q节点后继即可。

代码如下:

bool wei_delete(linklist &l,int i,int &e)//因为e的值需要带回主函数去,所以加个&符号 
{
	if(i<1)
	return false;
    //找第i-1个结点
	lnode* p=l;
	int j=0;
	while(p!=NULL&&j<i-1)
	{
		p=p->next;
		j++;
	}
    //进行排错
	if(p==NULL) //p结点若不存在,则i的位置不对
	return false;
	if(p->next=NULL)//p结点后为结点,则没有要删除的结点
	return false;
	lnode *q=p->next;//q指向p结点的后继结点,即需要删除的结点
	e=q->data;       //给删除节点中的数值,赋值给e
	p->next=q->next;//直接把p结点连接到q结点的后继,绕过删除节点,相当于从单链表中剔除掉
	free(q);        //释放q结点
	return true; 
}

(6)按位查找

  1. 按照结点位置,返回该结点。
  2. lnode *  getinsert(linklist &l,int i)——由于该函数为返回结点,所以类型为lnode*,形参为整个链表l,所需返回的第几个结点i。

代码如下:

lnode * getlist(linklist l,int i)  //我所查找该位置的结点
{
	if(i<0)    //第0个结点为头结点,如果比头结点还靠前,则肯定不对,返回false
	return false;
	lnode *p;  //定义结点指针p指向所需返回的结点
	p=l;       //让p初试位置为头结点处
	int j=0;
	while(p!=NULL && j<i)//因为需要返回第i个位置的结点,所以j<i
	{
		p=p->next;
		j++;
	}
	return p;
}

这个就类似于之前按位插入中的查找第i-1个结点的操作,因此可以替换成如下:

bool insertlist(linklist &l,int i,int e)//带头结点   插入 
{
	if(i<1)
	return false;
	lnode* p;
	p=getlist(l,i-1);//查找第i-1个结点,然后返回该节点,给p 
	houcha(p,e);
	return true;
	
}

删除操作中也有

bool wei_delete(linklist &l,int i,int &e)//因为e的值需要带回主函数去,所以加个&符号 
{
	if(i<1)
	return false;
	lnode* p;
	p=getlist(l,i-1);

	if(p==NULL)
	return false;
	if(p->next=NULL)
	return false;
	lnode *q=p->next;
	e=q->data;
	p->next=q->next;
	free(q);
	return true; 
}

(7)按值查找

  1. 给出数据域的值,查找链表中的结点有无一样的。
  2. lnode *getzhi(linklist &l,int e)——需要返回所查找数据域的结点,所以类型为lnode*
  3. 令p结点指针,指向第一个节点,依次往后扫描,看是否满足p->data==e,直到扫描到或扫描结束,最后返回p即可。

代码如下:

lnode *getzhi(linklist &l,int e)
{
	lnode *p=l->next;//直接指向头结点的后继结点,即实际第一个结点
	if(p==NULL)
	return false;
	while(p!=NULL&&p->data!=e)
	{
		p=p->next;
	}
	return p;	
} 

(8)求链表长度

  1. 类似于按值查找,从头结点开始,依次往后扫描,每扫一个节点,长度++,直到扫到NULL为止。

代码如下:

int lengthlist(linklist &l)
{
	lnode *p=l;//掐头去尾,去中间,从头结点开始算
	int len=0;
	while(p!=NULL&&p->next!=NULL)//扫描到链尾为止
	{
		p=p->next;
		len++;
	}
	return len;
} 

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

7-数据结构-单链表的插入删除操作 的相关文章

  • 如何将 std::string& 转换为 C# 引用字符串

    我正在尝试将 C 函数转换为std string参考C 我的 API 如下所示 void GetStringDemo std string str 理想情况下 我希望在 C 中看到类似的东西 void GetStringDemoWrap r
  • STL 迭代器:前缀增量更快? [复制]

    这个问题在这里已经有答案了 可能的重复 C 中的预增量比后增量快 正确吗 如果是 为什么呢 https stackoverflow com questions 2020184 preincrement faster than postinc
  • 没有特殊字符的密码验证器

    我是 RegEx 的新手 已经进行了大量搜索 但没有找到任何具体内容 我正在编写一个验证密码字符串的正则表达式 可接受的字符串必须至少具有 4 种字符类型中的 3 种 数字 小写字母 大写字母 特殊字符 我对包含有一个想法 也就是说 如果这
  • std::vector 与 std::stack

    有什么区别std vector and std stack 显然 向量可以删除集合中的项目 尽管比列表慢得多 而堆栈被构建为仅后进先出的集合 然而 堆栈对于最终物品操作是否更快 它是链表还是动态重新分配的数组 我找不到关于堆栈的太多信息 但
  • 如何在 C# 中打开 Internet Explorer 属性窗口

    我正在开发一个 Windows 应用程序 我必须向用户提供一种通过打开 IE 设置窗口来更改代理设置的方法 Google Chrome 使用相同的方法 当您尝试更改 Chrome 中的代理设置时 它将打开 Internet Explorer
  • 传递给函数时多维数组的指针类型是什么? [复制]

    这个问题在这里已经有答案了 我在大学课堂上学习了 C 语言和指针 除了多维数组和指针之间的相似性之外 我认为我已经很好地掌握了这个概念 我认为由于所有数组 甚至多维 都存储在连续内存中 因此您可以安全地将其转换为int 假设给定的数组是in
  • 如何在 C++ 中标记字符串?

    Java有一个方便的分割方法 String str The quick brown fox String results str split 在 C 中是否有一种简单的方法可以做到这一点 The 增强分词器 http www boost o
  • 如何使从 C# 调用的 C(P/invoke)代码“线程安全”

    我有一些简单的 C 代码 它使用单个全局变量 显然这不是线程安全的 所以当我使用 P invoke 从 C 中的多个线程调用它时 事情就搞砸了 如何为每个线程单独导入此函数 或使其线程安全 我尝试声明变量 declspec thread 但
  • 重载 (c)begin/(c)end

    我试图超载 c begin c end类的函数 以便能够调用 C 11 基于范围的 for 循环 它在大多数情况下都有效 但我无法理解和解决其中一个问题 for auto const point fProjectData gt getPoi
  • 方程“a + bx = c + dy”的积分解

    在等式中a bx c dy 所有变量都是整数 a b c and d是已知的 我如何找到整体解决方案x and y 如果我的想法是正确的 将会有无限多个解 由最小公倍数分隔b and d 但我只需要一个解决方案 我可以计算其余的 这是一个例
  • 如何获取 EF 中与组合(键/值)列表匹配的记录?

    我有一个数据库表 其中包含每个用户 年份组合的记录 如何使用 EF 和用户 ID 年份组合列表从数据库获取数据 组合示例 UserId Year 1 2015 1 2016 1 2018 12 2016 12 2019 3 2015 91
  • 两个静态变量同名(两个不同的文件),并在任何其他文件中 extern 其中一个

    在一个文件中将变量声明为 static 并在另一个文件中进行 extern 声明 我认为这会在链接时出现错误 因为 extern 变量不会在任何对象中看到 因为在其他文件中声明的变量带有限定符 static 但不知何故 链接器 瑞萨 没有显
  • 如何定义一个可结构化绑定的对象的概念?

    我想定义一个concept可以检测类型是否T can be 结构化绑定 or not template
  • 两个类可以使用 C++ 互相查看吗?

    所以我有一个 A 类 我想在其中调用一些 B 类函数 所以我包括 b h 但是 在 B 类中 我想调用 A 类函数 如果我包含 a h 它最终会陷入无限循环 对吗 我能做什么呢 仅将成员函数声明放在头文件 h 中 并将成员函数定义放在实现文
  • C# 动态/expando 对象的深度/嵌套/递归合并

    我需要在 C 中 合并 2 个动态对象 我在 stackexchange 上找到的所有内容仅涵盖非递归合并 但我正在寻找能够进行递归或深度合并的东西 非常类似于jQuery 的 extend obj1 obj2 http api jquer
  • 复制目录下所有文件

    如何将一个目录中的所有内容复制到另一个目录而不循环遍历每个文件 你不能 两者都不Directory http msdn microsoft com en us library system io directory aspx nor Dir
  • 如何在 Linq to SQL 中使用distinct 和 group by

    我正在尝试将以下 sql 转换为 Linq 2 SQL select groupId count distinct userId from processroundissueinstance group by groupId 这是我的代码
  • C 函数 time() 如何处理秒的小数部分?

    The time 函数将返回自 1970 年以来的秒数 我想知道它如何对返回的秒数进行舍入 例如 对于100 4s 它会返回100还是101 有明确的定义吗 ISO C标准没有说太多 它只说time 回报 该实现对当前日历时间的最佳近似 结
  • 为什么C++代码执行速度比java慢?

    我最近用 Java 编写了一个计算密集型算法 然后将其翻译为 C 令我惊讶的是 C 的执行速度要慢得多 我现在已经编写了一个更短的 Java 测试程序和一个相应的 C 程序 见下文 我的原始代码具有大量数组访问功能 测试代码也是如此 C 的
  • C# 使用“?” if else 语句设置值这叫什么

    嘿 我刚刚看到以下声明 return name null name NA 我只是想知道这在 NET 中叫什么 是吗 代表即然后执行此操作 这是一个俗称的 条件运算符 三元运算符 http en wikipedia org wiki Tern

随机推荐