数据结构—单链表

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

目录

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.2  在pos位置之后插入(主要使用这种功能)---不需要找pos前一个

      3.10 删除

             3.10.1 删除pos位置的值

             3.10.2  删除pos后一个(主要使用这种功能)---不需要找pos前一个

      3.11 单链表总结


1.前言

          学习了顺序表发现有以下缺点:


        1.1 空间不够,需要扩容(扩容有一定的空间浪费)。

        1.2 头插、头删(需要移动数据)时间复杂度是O(N),效率低。

         所以我们学习单链表来按需申请释放空间,不需要移动数据,提高效率。


2.了解单链表

  概念:单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。

  特点:每个结点除了存放数据元素外,还要存储指向下一个节点的指针

  优点:不要求大片连续空间,改变容量方便。。

  缺点:不可随机存取,要耗费一定空间存放指针。

  单链表逻辑及重要性:

数据结构—单链表


3.单链表代码实现

      3.1 单链表结构体实现

typedef int SLTDataType; 
typedef struct SListNode
{
	SLTDataType data;//存放数据
	struct SListNode* next;//指向下一个结构体的指针
}SLTNode;

       3.2 创建节点

void TestSList1()
{
	//struct SListNode* 
	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n1);
	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n2);
	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n3);
	SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n4);

	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
}

      3.3  打印单链表

cur = cur->next理解:

第一次进来cur指向的是链表的头,cur=cur—>next说明把下一个节点的地址赋给cur,现在的cur指向的是第二个结构体,是第二个结构体的地址.......

循环下去就可以打印出节点里的data数据,直到cur=NULL。

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

       3.4 尾插 

 注意点:

当链表为空的时候,newnode给phead时,由于phead是一个形参,函数中形参的改变不会改变实参。

这时要改变指针变量(plist)就要传指针变量的地址——就要传二级指针。

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾节点
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

         3.5  头插 

单链表头插不需要和尾插一样要特殊处理

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

          3. 6 头删

void SListPopFront(SLTNode** pphead)
{
	assert(*pphead != NULL);//暴力检查
	//if (*pphead == NULL)  //温柔检查
	//	return;

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

         3.7  尾删

void SListPopBack(SLTNode** pphead)
{
	assert(*pphead);

	// 1、只有一个节点
	// 2、多个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{  
        //两种方法   
		/*SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;*/
//
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}	
}

      3.8  查找

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;

		cur = cur->next;
	}

	return NULL;
}

       3.9  插入

              3.9.1 在pos位置之前插入 

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)

{  
  assert(pos);
  assert(ppheart);
  
  //头插
  if (pos= *pphead)
  {
    
      SListPushFront(pphead.x);
  }
  
  else
   {
         SLTNNode* prev= *ppheart;
         while(prev->next !=pos)

           {
                 prev=prev->next;
           }
         
           SLTNode* newnode=BuySListNode(x);
           prev->next=newnode;
           newnode->next=pos;  

   }

           3.9.2  在pos位置之后插入(主要使用这种功能)---不需要找pos前一个

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	/*SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;*/

	// 不在乎链接顺序
	SLTNode* newnode = BuySListNode(x);
	SLTNode* next = pos->next;
	// pos newnode next
	pos->next = newnode;
	newnode->next = next;
}

      3.10 删除

             3.10.1 删除pos位置的值

void SListErase(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
   assert(pos);
  assert(ppheart);
    
   //头删    
   if (pos= *pphead)
   {
    
       SListPopFront(pphead);
   }
   
    else
    { 
       SLTNode* prev= *pphesd;
       while(prev->next !=pos)
        {
            prev=prev->next;
        }
    
      prev->next= pos->next;
       free(pos);
     }

            3.10.2  删除pos后一个(主要使用这种功能)---不需要找pos前一个

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);

	if (pos->next == NULL)
		return;

	SLTNode* del = pos->next;
	//pos->next = pos->next->next;//这样就释放不了节点
	pos->next = del->next;

	free(del);
	del = NULL;
}

          3.11 单链表总结

        由单链表的在pos位置之后插入和删除pos位置之后的值可知,单链表没有完全解决顺序表的缺陷,所以我们后面学习双向的链表来提高效率。文章来源地址https://www.toymoban.com/news/detail-418974.html

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

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

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

相关文章

  • 【数据结构】数据结构小试牛刀之单链表

    不讲虚的啦,直接肝! 单链表所要实现的功能罗列如下: 初始化工作我们先初始化一个节点类型,类型中包括了数据域和指针域,数据与中保存着该节点要保存的数据,指针域则保存着链表下一个节点的地址: 然后我们在创建一个函数,用于创建一个新的节点,因为后面我

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

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

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

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

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

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

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

    单链表 1 链表的概念及结构 概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。 在我们开始讲链表之前,我们是写了顺序表,顺序表就是类似一个数组的东西,它的存放是连续的,优点有很多,比如支持

    2024年02月12日
    浏览(41)
  • 【数据结构】单链表(详解)

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

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

    概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。  从以上图片可以看出: 1.链式结构在逻辑上是连续的,但在物理上不一定是连续的。 2.现实中的节点一般是在堆上申请出来的。 3.从堆上申请的空间,

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

    前言:  上一次我们分享了线性表中的一种结构顺序表,它存在着一些其缺点,比如:在中间位置或者头部进行元素插入或者删除的时候时间复杂度是 O ( N ) O(N) O ( N ) 效率比较低,并且顺序表在扩容的时候也存在时间和空间上的消耗,由于我们每次都是按照二倍来扩的,那

    2024年02月11日
    浏览(38)
  • 数据结构——单链表

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

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

    目录 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日
    浏览(102)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包