单链表Single-LinkList

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

0、节点结构体定义

typedef struct LNode{
	
	int data;
	struct LNode *next;
	
} Lnode, *LinkList;

1、初始化

bool InitList(LinkList &L)	//初始化 
{
	L = new LNode;
	
	if(!L){
		return false;
	}
	L->next = NULL;
	
	return true;
}

2、创建

(1)头插法

void CreateList_H(LinkList &L, int n)	//头插法创建 
{
	LinkList s;
	
	while(n--){	//--n不行!! 
		s = new LNode;
		
		cin>> s->data;
		
		s->next = L->next;		//链表的i++ 
		L->next =s;	
	}
}
//反复利用链表头L和新节点s添加(就是插入...) 

(2)尾插法

void CreateList_R(LinkList &L, int n)	//尾插法创建 
{
	LinkList s, r = L;
	
	while(--n){
		s = new LNode;
		
		cin>> s->data;
		
		r->next = s;			//链表的i++
		s->next = NULL;
		r = s;
	}
}
//利用r存储当前节点信息,便利于新节点s的添加 

3、查找

(1)查找具体元素

bool Finde(LinkList &L, int e)	//查找具体元素 
{
	LinkList p = L->next;
	
	while(p != NULL && p->data != e){
		p = p->next;
	}
	if(!p){
		return false;
	}
	return true;
}

(2)查找第 i 个元素

bool GetElemi(LinkList &L, int i, int &e)	//查找第i个元素 
{
	int j = 1;				//记不住就初始化为 j = 1、p = L 
	LinkList p = L->next;  //因为后面都是这样(保对),而且也没增加什么时间 
	
	while(p && j<i){
		p = p->next;
		++j;
	}
	if(!p || j>i){		//i值不合法:i>n || i<0 
		return false;
	}
	e = p->data;		//用e记录元素i 
	
	return true;
}

4、插入

bool ListInsert(LinkList &L, int i, int e) 	//在第i个元素后插入元素 
{
	 int j = 0;
	 LinkList p = L;	//保证能在第一个元素前插入 
	 
	 while(p && j<i){
	 	p = p->next;
	 	++j;
	 }
	 if(!p || j>i){
	 	return false;
	 }
	 //上面就是查找操作... 
	 LinkList s = new LNode;
	 
	 s->data = e;
	 
	 s->next = p->next;
	 p->next = s;
	 
	 return true;
}

5、删除

bool ListDelete(LinkList &L, int i)	//删除第i个元素 
{
	int j = 0;
	LinkList p = L;		//保证能删除第 1个元素 
	
	while(p && j<i-1){
		p = p->next;
		++j;
	}
	if(!p ||j>i-1){
		return false;
	}
	//上面还是查找操作...(找第元素i-1)
	LinkList q = p->next;	//使用临时变量更安全!(p->next->next = p->next; delete p->next; 
	
	p->next = q->next;	   //当n=2时会出错!因为要删除的p->next已经变成NULL了!) 
	
	delete q;
	
	return true;
}

6、释放内存

bool ListRelese(LinkList &L)
{
	LinkList p;
	
	while(L){
		p = L;			//暂存当前节点 
		L = L->next;	//更新为下一节点 
		delete p;		//删除当前节点 
		
		/*这样也ok: 
		**p = L->next;// 暂存下一个节点
		**delete L;// 删除当前节点
		**L = p;// 更新当前节点为下一个节点
		*/
	}
	
	return true;
}

7、其他操作

(1)查找中间元素

LinkList FindMid(LinkList L)	//查找中间的节点 
{						//不会修改L就不用传引用!
	LinkList p = L, q = L;
	
	while(p){
		q = q->next;
		p = p->next->next;
	}
	return q;
}

(2)查找倒数第 k 个节点

LinkList Findk(LinkList L, int k)	//查找倒数第k个节点 
{
    LinkList p, q;
    p=L->next; 
    q=L->next; 
    while(p->next!=NULL)
    {
        if(--k<=0) //k减到0时,慢指针开始走
            q=q->next; 
        p=p->next; //p为快指针,先走k-1步
    }
    if(k>0)
        return NULL;
    else
    	return q; 
}

(3)合并有序链表

/合并有序链表:将两个有序(非递减)单链表La和Lb合并为一个新的有序(非递减)单链表Lc 
LinkList ListMerge(LinkList LA, LinkList LB)
{
	LinkList p = LA->next ,q = LB->next; 
	LinkList LC = LA, r = LC;
	
	while(p && q){
		if(p->data > q->data){
			r->next = q;
			r = q;
			q = q->next;
		}else{
			r->next = p;
			r = p;
			p = p->next;
		}
	}
	r->next = p? p:q;
	
	delete LB;
	
	return LC;
} 

(4)逆转链表文章来源地址https://www.toymoban.com/news/detail-667115.html

void ListReverse(LinkList &L)	//逆转单链表 
{
	LinkList p = L->next, q;
	L->next = NULL;
	
	while(p){
		q = p->next;
		
		p->next = L->next;
		L->next = p;
		
		p = q;
	} 
}

到了这里,关于单链表Single-LinkList的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构—单链表

    目录 1.前言 2.了解单链表 3.单链表代码实现       3.1 单链表结构体实现       3.2 创建节点       3.3  打印单链表       3.4 尾插        3.5  头插        3. 6 头删       3.7  尾删       3.8  查找       3.9  插入            3.9.1 在pos位置之前插入             3.9.

    2023年04月20日
    浏览(104)
  • 【数据结构】单链表(详解)

    所属专栏:初始数据结构 博主首页:初阳785 代码托管:chuyang785 感谢大家的支持,您的点赞和关注是对我最大的支持!!! 博主也会更加的努力,创作出更优质的博文!! 关注我,关注我,关注我,重要的事情说三遍!!!!!!!! 前面我们已经用顺序表方式来实现接口

    2023年04月24日
    浏览(52)
  • 数据结构:单链表

    单链表的全称为\\\"不带头单向不循环链表\\\" 注意:         下文提到的头节点与带头链表时两个概念,文中的头节点指的是第一个有效节点,二带头节点中的头指的是第一个无效节点 链表和顺序表一样,都是线性表,逻辑结构上是线性的,但不同的是,链表在物理结构上不是线性的

    2024年01月21日
    浏览(40)
  • 数据结构——单链表

    我们需要在程序中存储一系列的数据,这些数据不是一成不变的,需要满足随时的动态增删查改。 顺序表,虽然能满足这些要求,可是顺序表在头插或者中间插入数据时,需要将数据一个一个挪动,效率较低;而且需要频繁的扩容,扩容也是需要付出一定的代价。 为有效解

    2023年04月17日
    浏览(53)
  • 数据结构之单链表

    目录 1.什么是链表。 2.链表的优点 3.单链表的实现 1.单链表的结构体 2.节点的创建 3.参数的调用 4.头插  5.尾插 7.头删 8.尾删 8.在pos节点前插入x 9.在pos节点前插入x 10.删除pos位置节点  对于顺序表我们发现,在此基础上仍存在了些许不足: 1.中间或头部的插入时间复杂度为O

    2024年02月05日
    浏览(40)
  • 【数据结构】单链表(一)

    作者:日出等日落 专栏:数据结构 想变成仲夏夜的一只萤火虫,只要抓住你的注意力,就已经满足了。 目录 前言:  单链表的结构 :  逻辑结构: 物理结构: BuySLTNode(动态申请一个结点):   CreateSList(//循环创建结点): SLTPrint(单链表打印):  单链表的功能:  SL

    2024年02月01日
    浏览(44)
  • 数据结构·单链表

            不可否认的是,前几节我们讲解的顺序表存在一下几点问题:         1. 中间、头部的插入和删除,需要移动一整串数据,时间复杂度O(N)         2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗         3. 增容一般是2倍的增长,这势

    2024年01月25日
    浏览(75)
  • 【数据结构】单链表详解

    当我们学完顺序表的时候,我们发现了好多问题如下: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们 再继续插入了

    2024年02月09日
    浏览(34)
  • 数据结构 - 单链表

    目录 文章目录 一、什么是链表? 线性表: 顺序表: 二、链表的分类和实现 分类: 实现: 1.创建节点类 2.创建单链表  1.addTail(尾增)   2.删除节点值为key的第一个节点  3.插入节点(在指定位置) 4.获取链表长度  总结 前言 大家好,这篇博客给大家讲一下什么是链表以及单链表的实现

    2024年02月09日
    浏览(43)
  • 数据结构--单链表

    目录 1.单链表的定义: 单链表基本操作的实现: 2.单链表的初始化(构造带头结点的空表) 2.将头结点的指针域置空 3.链表是否为空: 4.单链表的销毁: 5.单链表的清空: 6.求单链表的表长: 7.   取值  取单链表第i个元素: 8按值查找 根据指定数据查找指定数据所在位置序

    2024年02月15日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包