小菜一步一步学数据结构之(四)单链表

简介: 上一篇博客学习了顺序表,最后也说明了顺序表属于静态存储,数据元素的个数不能自由的扩充。为了解决这个问题我们引入了链表链表存储结构结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻,因此线性表的链式表示又称为非顺序映像或链式映像。

上一篇博客学习了顺序表,最后也说明了顺序表属于静态存储,数据元素的个数不能自由的扩充。为了解决这个问题我们引入了链表

链表存储结构

结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻,因此线性表的链式表示又称为非顺序映像或链式映像。

各个结点有两个域组成:

结点构成
* 数据域:存储元素数值数据
* 指针域:存储直接后继结点的存储位置

名词解析

结点
1. 结点:数据元素的存储映像。有数据域和指针域两部分组成。
2. 链表:n个结点由指针链组成一个链表。它是线性表的链式存储映像,称为线性表的链式存储结构
3. 单链表、双链表、循环链表:
* 结点只有一个指针域的链表,称为单链表或线性链表
* 有两个指针域的链表,称为双链表
* 首尾相接的链表称为循环链表
4. 头指针是指向链表中第一个结点的指针
5. 首元结点是指链表中存储第一个数据元素a1的结点
6. 头结点是在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息(可无)

当头结点的指针域为空时表示空表
头结点不能计入链表长度值

单链表的定义和实现

非空表

空表
表
单链表是由表头唯一确定,因此单链表可以用头指针的名字来命名
若头指针名是L,则把链表称为表L

单链表的存储结构定义

     typedef struct LNode
     {
         ElemType data;              //数据域
         struct LNode *next;         //指针域

     }LNode,*LinkList;               //*LinkList为Lnode类型的指针

注意:
指针变量p:表示结点地址
结点变量*p:表示一个结点

单链表基本操作的实现

1.初始化(构造一个空表)

【算法思想】

(1)生成新结点作为头结点,用头结点L指向头结点。

(2)头结点的指针域置空。

【算法描述】

 Status InitList_L(LinkList &L)
 {
 L=new LNode;
 L->next=NULL;
return OK;
 }

2.查找

(1)按序号查找

【算法思想】

从链表的第一个结点(L->next)开始顺着链域扫描,用指针p指向当前扫描到的结点,p的初始值指向第1个结点(p=L->next)。用j做计数器,累计当前扫描过的结点数,j的初值为1,当p指向扫描到的下一个结点时,计数器j相应加1.当j=i时,p所指向的结点是想要找的第i个结点。

【算法描述】

Status GetElem_L(LinkList L,int i,ElemType &e)
{
p=L->next;j=1;
while(p&&j<i)
{
p=p->next;
 ++j;
}
if(!p||j>i)
return ERROR;
e=p->data;
return OK;
}

按值查找

【算法思想】

链表中查找其值与给定e相等的数据元素的过程和顺序表类似,从第一个结点起,依次和e相比较,如果找到一个其值与e相等的数据元素,则返回其在链表中的“位置”;如果查遍整个链表都没有找到其值和e相等的元素,则返回“NULL”。因此需要设置一个指针变量p顺链扫描,直至p为“NULL”,或者p->data和e相等为止。

【算法描述】

LNode *LocateElem_L(LinkList L,ElemType e)
{
p=L->next;
while(p&&p->data!=e)
{
 p=p->next;
}
return p;
}

3.插入

【算法思想】
插入
将值为e的新结点插入到表的第i个结点的位置上,即插入到结点ai-1与ai之间,分为一下几步:

  1. 找到结点ai-1并由指针p指向该结点。
  2. 生成一个新结点*s。
  3. 将新结点*s的数据域置为e。
  4. 将新结点*s的指针域指向结点ai。
  5. 令结点ai-1的指针域指向新结点*s。

【算法描述】

Status ListInsert_L(LinkList &L,int i,ElemType e)
{
p=L;j=0;
while(p&&j<i-1)
{
p=p->next;
 ++j;
}
if(!p||j>i-1)
return ERROR;
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}

4.删除

【算法思想】

要删除单链表的第i个结点ai,分以下几步:
删除
1. 找到结点ai-1并由指针p指向该结点。
2. 临时保存待删除结点ai的地址在q中,以备释放。
3. 令p->next指向ai的直接后继结点。
4. 将待删除结点ai的值保留在e中
5. 释放结点ai的空间。

【算法描述】

Status ListDelete_L(LinkList &L,int i,ElemType &e)
{
 p=L;j=0;
 while(p->next&&j<i-1)
 {
  p=p->next;++j;
     }
 if(!(p->next)||j>i-1)
 return ERROR;
 q=p->next;
 e=q->data;
 delete q;
 return OK;
}

5.创建单链表

(1)前插法

【算法思想】

前插法是通过将新结点逐个插入链表的头部(头结点之后)来创建链表。首先建立只有一个头结点的空链表,每读入一个数据元素则申请一个新结点,并将新结点插入到头结点之后。
前插法
【算法描述】

void CreateLst_F(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;
for(i=n;i>0;--i)
{
p=new LNode;
cin>>p->data;
p->next=L->next;L->next=p;
}
}

(2)后插法

【算法思想】

后插法是通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样,首先要创建一个只有头结点的空链表L,不同的是,为了使新结点能够插入到表尾,需要增加一个尾指针r指向链表的尾结点,初始化时,r同L均指向头结点。每读入一个数据元素则申请一个新结点,将新结点插入到尾结点*r之后,然后使r指向新的尾结点。
后插法
【算法描述】

void CreateList_L(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;
r=L;
for(i=0;i<n;++i)
{
p=new LNode;
cin>>p->data;
p->next=NULL;r->next=p;
r=p;
}
}

循环链表

循环链表是表中最后一个结点的指针域指向头结点,整个链表形成一个环。
l两个链表合并
两个线性表合并成一个表,将第一个表的尾指针指向第二个表的第一个结点,第二个表的尾指针指向第一个表的头结点,然后释放第二个表的头结点。

 p=B->next->next;
 B->next=A->next;
 A->next=p;

附录代码

#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100
#include<stdio.h>
#include<iostream>
using namespace std;
typedef int Status;
typedef int ElemType ;

typedef struct LNode 
{
    ElemType data;
   struct LNode *next;
}LNode,*LnkList;
Status InitList_L(LnkList &L)
{
    L=new LNode;
    L->next=NULL;
return OK; 
}
Status ListInsert_L(LnkList &L,int i,ElemType e)
{
    LnkList p=L;
    int j=0;
    while(p&&j<i-1)
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i-1)
    return ERROR;
   LnkList  s=new LNode;
   s->data=e;
   s->next=p->next;
   p->next=s;
   return OK;
}
Status ListTraverse(LnkList &L)
{
        LnkList p=L;
        p=p->next;
        while(p)
        {

        printf("%d\n",p->data);
    p=p->next;
        }
}
Status ListDelete_L(LnkList &L,int i)
{
        LnkList p=L;
        int j=0;
        while(p&&j<i-1)
        {
            p=p->next;
            ++j; 
        }
        if(!(p->next)||j>i-1)
        return ERROR; 
            LnkList q=p->next;
            p->next=q->next;
            printf("要删除的数为%d\n",q->data);
            delete q;

            return OK;
}
Status CreatList_A(LnkList &L,int n)
{
    L=new LNode;
    L->next=NULL;
    for(int i=n;i>0;i--)
    {
    LnkList p=new LNode;
    printf("正插入,请输入");
    cin>>p->data;
    p->next=L->next;
    L->next=p;  
    }
}
Status CreatList_B(LnkList &L,int n)
{
    L=new LNode;
    L->next=NULL;
        LnkList r=new LNode;
        r=L;
    for(int i=n;i>0;i--)
    {
            LnkList p=new LNode;
    printf("反插入,请输入");
    cin>>p->data;
    p->next=NULL;
    r->next=p;
    r=p;

    }
}
int main()
{
    LnkList L;
    InitList_L(L);
     ListInsert_L(L,1,10);

      ListInsert_L(L,1,20);
       ListInsert_L(L,1,30);
      ListDelete_L(L,2);
     ListTraverse(L);
     CreatList_A(L,2);
      ListTraverse(L);
       CreatList_B(L,2);
      ListTraverse(L);
    return 0;
}
相关文章
|
2月前
【数据结构】单链表(长期维护)(1)
【数据结构】单链表(长期维护)(1)
|
17天前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
2天前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
|
3天前
|
存储
数据结构2——单链表
数据结构2——单链表
15 1
|
6天前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
5天前
|
存储
数据结构--单链表
数据结构--单链表
|
6天前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
1月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
171 6
|
2月前
|
算法 索引
【初阶数据结构篇】单链表算法题进阶
深拷贝应该正好由 n 个全新节点组成,其中每个新节点的值都设为其对应的原节点的值。
19 0
|
2月前
【数据结构】单链表(长期维护)(2)
【数据结构】单链表(长期维护)(2)