首页  >  文章  >  链表是一种采用什么存储结构存储的线性表

链表是一种采用什么存储结构存储的线性表

青灯夜游
青灯夜游原创
2021-11-22 15:04:5813558浏览

链表是一种采用“链式”存储结构存储的线性表。链表的数据元素所占的存储单元地址可以是连续的,也可以是不连续的,可根据需要临时、动态地申请分配相应的存储空间,数据元素之间的逻辑关系可以用“链”来表达。

链表是一种采用什么存储结构存储的线性表

本教程操作环境:windows7系统、Dell G3电脑。

为了克服顺序表存储结构的缺点,充分利用存储空间和提高运行效率,线性表可以采用另一种存储结构——链式存储结构线性表的链式存储结构简称“链表(link list)”

一、链表概述

链表的数据元素所占的存储单元地址可以是连续的,也可以是不连续的,可根据需要临时、动态地申请分配相应的存储空间,数据元素之间的逻辑关系可以用“链”来表达。

链表的插入和删除不需要移动数据元素,只需要修改链即可实现。

链表分类:

1.按链表内存分配实现的方式分类

①动态链表

②静态链表

2.按链接方式分类

①单链表

②循环链表

③双链表

(它们均为动态链表)

二、单链表的定义

1.定义

为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对于每个数据元素ai,除了存储本身的信息外,还需要存储一个指示其直接后继的信息(后继的存储位置-地址)。

存储数据元素信息的域称为数据域,存储直接后继位置的域称为指针域,指针域中存储的信息称为指针或链。

这两部分信息组成数据元素ai的存储映像,称为结点

n个结点链成一个链表,即为线性表(a1,a2,a3,...,an)的链式存储结构,因为链表的每个结点中只包含一个指针域,所以称为链表

对于线性表来说,总有个头有个尾,链表也不例外。链表中指向单链表第一个结点的指针叫做头指针,整个链表的存取必须从头指针开始进行,之后的每个结点都是上个结点的后继指针指向的位置。链表的最后一个结点的指针为“(通常用NULL表示)”——空指针。

为了方便实现链表的各种运算,在单链表的第一个数据结点之前设一个类型相同的结点,该结点称为头结点。

头结点的数据域可以存储一个特殊的标志信息如链表的长度,也可以不存储任何数据。

链表的第一个数据结点和最后一个结点又称为首结点和尾结点

 2.头指针和头结点的异同点

头指针:

  • 头指针是指链表中指向第一个结点的指针,若链表有头结点,则是指向头结点的指针。
  • 头指针具有标识作用,常用头指针冠以链表的名字。
  • 无论链表是否为空,头指针均不为空。头指针是链表的必要元素

头结点:

  •  头结点是为了操作的统一和方便而设立的,放在第一个元素的结点之前,其数据域一般无意。
  • 有了头结点,对在第一元素结点前插入结点和删除第一个结点,其操作与其他结点的操作就统一了。
  • 头结点不一定是链表必须要素

 3.代码演示

/*线性表的单链表存储结构*/
/*结点定义*/
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;

/*单链表定义*/
typedef struct Node *LinkList;

三、单链表的操作

1.插入操作

1)插入模拟

假设存储元素e的结点为s,将s插入到ai结点后面,如何操作?

思考:两句插入代码能否交换?

不能,如果调换过来,会导致ai+1等后面的元素无法找到,因为s的指针域没有指向ai+1的地址。

2)单链表第i个数据插入结点的算法思路

  •  声明一个结点p指向链表的第一个结点,初始化j=1;
  • 当j
  • 若到链表末尾p为空,则说明第i个元素不存在;若查找成功,生成一个空节点s(使用malloc函数)
  • 将数据元素e赋值給s->data,即为s->data=e;
  • 插入标准语句:s->next=p->next;p->next=s;
  • 返回成功。

2.删除操作

1)删除模拟

假设存储元素ai的结点为q,要实现将结点q删除单链表的操作。

2)单链表删除第i个数据结点的算法思路

  •  声明一个结点p指向链表的第一个结点,初始化j=1;
  • 当j
  • 若到链表末尾p为空,则说明第i个元素不存在;若查找成功,将删除结点p->next赋值給q
  • 插入标准语句:p->next=q->next;
  • 将q结点赋值給e,即为e=q->data;
  • 释放q结点
  • 返回成功。

四、单链表结构和顺序表结构对比

存储方式:

  • 顺序表用一段连续的存储单元依次存储线性表中的数据元素
  • 单链表采用链式存储结构,用一组任意的存储单元存放线性表元素

时间性能:

①查找

  • 顺序表O(1)
  • 单链表O(n)

②插入和删除

  • 顺序表O(n)
  • 单链表O(1)

空间性能:

  • 顺序表需要预分配存储空间,分大了,浪费,分小了易发生上溢
  • 单链表不需要预分配存储空间,需要多少都可以分配,元素个数不受限制

更多相关知识,请访问常见问题栏目!

以上是链表是一种采用什么存储结构存储的线性表的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn