数据结构--单链表

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

目录

1.单链表的定义:

单链表基本操作的实现:

2.单链表的初始化(构造带头结点的空表)

2.将头结点的指针域置空

3.链表是否为空:

4.单链表的销毁:

5.单链表的清空:

6.求单链表的表长:

7.   取值  取单链表第i个元素:

8按值查找 根据指定数据查找指定数据所在位置序号(地址)

9.插入操作 在第i个结点前插入元素为e的新结点

10.删除结点:删除第i个元素

11.头插法 元素插入在链表头部


表示空表:

1.无头结点 : 头指针的指针域为空

2.有头结点:  头节点的指针域为空 

1.单链表的定义:
typedef struct Lnode{

   int data;

   struct Lnode *next;

}Lnode,*LinkList;

首先定义struct Londe结构体,结构体内有data ,指向该结构体的指针next

再用typedef 将该结构体命名为Lnode类型,*LinkList为指向Lnode结构体的指针类型

定义链表(头指针):LinkList L;//L即为指针

定义结点指针:Lnode *p;

数据结构--单链表,数据结构

单链表基本操作的实现:
2.单链表的初始化(构造带头结点的空表)

算法步骤:

1.生成新结点作头结点,用头指针L指向头结点

2.将头结点的指针域置空
int InitList(LinkList &L)

{

    L = new Lnode;

    L->next=NULL;

    return 1;

}
3.链表是否为空:

空表:链表中无元素,称为空链表(头指针和头结点仍然在)

int ListEmpty(LinkList L)
{
  if(L->next)
      cout<<"空表"<<endl;
      return 0;
else
      return 1;
}
4.单链表的销毁:

算法思路:从头指针开始,依次释放所有结点

int DestoryList(LinkList &L)

{

    Lnode *p;

  while(L)
  {  

  p=L;

  L=L->next;

  delete p;

   }
return OK;
}
5.单链表的清空:

数据结构--单链表,数据结构

int ClearList(LinkList &L)

{

     Lnode *p,* q;

     p=L->next;

     q=p->next;

    delete p;

while(p!=NULL)

{

   q=p;

   q=q->next;

delete p;

}

L->next=NULL;
}

int ClearList(LinkList &L)
{
  Lnode *p,*q;
  p=L->next;
  while(p)
   {
   q=p->next;
   delete p;
   q=p;
   }
  L->next=NULL;
  return ok;

}
6.求单链表的表长:

算法思路:从首元结点开始,依次计数所有结点

int ListLength(LinkList L)
{   
    Lnode *p;
    p = L->next;
      int i=0;
    while(p)
   {
     p=p->next;
      i++;
   } 
   return i;
}
7.   取值  取单链表第i个元素:

算法步骤:从第一个结点顺链扫描,用指针p指向当前扫描到的结点,p初值p=L->next

j作计数器,累计当前扫描过得结点数,j初值为1

当p指向扫描到的下一结点时,计数器j加1

当j==i时,p所指的结点就是要找的第i个结点

int GetElem(LinkList L,int i,int &e)
{
  Lnode *p;
  p=L->next;
  int j=1; 
  while(p&&j>i){//向后扫描,直到P指向第i个元素或p为空
   P=P->next;
   ++j;
  }
    if(!p||j>i) return ERROR;
  e=p->data;
  return OK;
}
8按值查找 根据指定数据查找指定数据所在位置序号(地址)

数据结构--单链表,数据结构

int FindElem(LinkList L,int e){
    Lnode *p;
    p=L->next;
    int i=1;
   while(p&&p->data!=e)
   {
     p=p->next;
     i++;
   }
   return i;
   if(p) return i;
    else return 0;
}
Lnode *LocateElem(LinkList L,int e){
//在线性表中查找值为e的数据元素
//找到,则返回L中值为e的数据元素地址,查找失败返回NULL
     p=p->next;
     while(p&&p->data!=e)
    {
      p=p->next;
    }
     return p;
}
9.插入操作 在第i个结点前插入元素为e的新结点

数据结构--单链表,数据结构

算法步骤:1.首先找到ai-1的存储位置p

 2生成一个数据域为e的新节点s

3插入新结点:1新结点的指针域指向结点ai

                       2.结点ai-1的指针域指向新结点

int InsertElem(LinkList &L,int i,int e)
{
  Lnode *p,*s;
  L = p;
  int j=0;
  while(p!=NULL&&j<i-1) 
  {
    p=p->next;
    ++j;
  }
  if(p==NULL||j>i-1) return ERROR;
  s -> data = e ;
  s -> next = p ->next;
  p -> next = s;
   
return OK;


}
10.删除结点:删除第i个元素
int DeleteElem(LinkList &L,int i,int &e){
    Lnode *p,*q;
    int j=0;
    while(p->next&&j<i-1){
     p=p->next;
     ++j;
    }
    if(!(p->next)||j>i-1)
    q=p->next;
    p->next=q->next;
    e=q->data;//将要删除元素用e保存,要用时可以用
    delete q;
    return OK;
}
11.头插法 元素插入在链表头部

 数据结构--单链表,数据结构文章来源地址https://www.toymoban.com/news/detail-556114.html

int CreatList(LinkList &L,int n){
    
    L = new Lnode;
    L->next=NULL;//建立一个带头结点的单链表

    for(int i=n;i>0;--i)
    {
       p = new Lnode;//生成新结点
       cin>>p->data;//输入插入的元素
       p->next=L->next;//将新结点插到表头
       p=L->next;//在将新结点与头结点连接
    }
}

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

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

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

相关文章

  • 【数据结构】单链表(详解)

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

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

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

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

    🌇个人主页:_麦麦_ 📚今日名言:“生活总是让我们遍体鳞伤,但到后来,那些受伤的地方一定会变成我们最强壮的地方。”        ——海明威《永别了武器》 目录 ​编辑 一、前言 二、正言  3.1链表的概念及结构 3.2链表的分类 3.3链表的实现【无头单向非循环】 3.

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

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

    2024年01月25日
    浏览(74)
  • 数据结构--单链表

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

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

    目录 前言 链表的定义 链表的创建 头插法创建链表 尾插法创建链表 链表的删除 在头部删除元素 在尾部删除元素 查找固定元素 在链表中插入元素 在pos位置前插入 在pos位置后插入 删除链表结点 删除pos位置的结点 删除pos后的结点 链表的销毁 写在最后 前面我们学习了顺序表

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

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

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

    🌇个人主页:_麦麦_ 📚今日名言:年轻时候的我以为坚持是永不动摇,到这个年纪明白了坚持就是犹疑着,退缩着,心猿意马着,一步三停着,还在往前走。——《十二月历》 目录 一、引言  二、单链表剩余功能的实现         1.单链表的查找         2. 单链表指定位

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

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

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

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

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包