数据结构--单链表

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

目录

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模板网!

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

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

相关文章

  • 【数据结构】单链表(超全)

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

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

    目录 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. 单链表指定位

    2024年01月17日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包