【数据结构与算法】线性表链式存储结构

标签：结点 单链 LNode 指针 next 链表 链式 数据结构 线性表

线性表链式存储结构

文章目录

• 链式存储结构
• *头结点和头指针
• 一.线性链表（单链表）
• • 1.1定义
  • 1.2初始化
  • • 1.2.1带头结点的初始化
    • 1.2.2不带头结点的初始化
  • 1.3插入
  • • 1.3.1按位序插入
    • 1.3.2指定结点的后插入操作
    • 1.3.3指定结点的前插入操作
  • 1.4销毁
  • 1.5清空
  • 1.6删除
  • • 1.6.1按位序删除
    • 1.6.2指定结点的删除
  • *求单链表的表长
  • 1.7查找操作
  • • 1.7.1按位查找操作
    • 1.7.2按值查找操作
  • 1.8创建
  • • 1.8.1尾插法
    • 1.6.2头插法
• 二.静态链表
• 三.循环链表
• 四.双向链表
• • 4.1初始化
  • 4.2插入
  • 4.3删除
• 链表优缺点

前面所讲的顺序存储结构，简而言之就是相邻两个元素的存储位置具有邻居关系，它们在内存中的位置是紧挨着的，中间没有间隔，无法快速的插入和删除。那么，我们换一种方法，哪里有空位我们就放哪里，利用指针对元素进行定位，所有的元素就可以通过遍历来找到了。本篇文章，我将详细的介绍线性表的另外一种存储结构——链式存储结构。

链式存储结构

1. 定义

• 结点：线性表的链式存储结构的特点是，用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），因此，为了表示某个数据元素a i与它的直接后继元素a i + 1 之间的逻辑关系，对数据元素a i 来说，除存储其本身的信息之外，还需要存储一个指示它直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素a i 的存储映像，称为结点（node）。

• 它包括两个域：其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域，指针域中存储的信息称为指针或链，n 个结点（a i (1<=i<=n)的存储映像）链结成一个链表，即为线性表的链式存储结构。data的类型根据具体问题，next的类型是（data类型的）指针

• 头指针：是指向链表中第一个结点的指针

• 头结点：它是链表中的辅助结点，只包含指向第0个数据元素的指针，而没有数据信息，头结点有简化代码的作用，因为它始终指向了第0个元素，便于执行时对元素位置的定位。

• 首元结点：是指链表中存储第一个数据元素a1的结点

• 尾结点：尾结点中存储的地址信息可以用于区分链表类型。尾指针为空：单链表。尾指针指向链表的开头：循环链表。为随机值：非法链表。

• 数据结点：它是链表中代表数据元素的结点，表现为数据域和指针域。

2. 特点

• 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
• 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找到一个结点和最后一个结点所花费的时间不等。这种存取元素的方法称为顺序存储法

3. 分类

• 单链表： 每个结点只包含直接后继的地址信息，结点只有一个指针域的链表。
• 循环链表：单链表的最后一个结点的直接后继为第一给结点（首尾相接）
• 双向链表：单链表中的结点包含直接前驱和后继的地址信息（结点有两个指针域 ）

*头结点和头指针

上文我们提到了，头结点的数据域一般不存储任何信息，这是它作为第一个结点的特性。但是一个链表中不一定有头结点：

那么这个时候就会有疑惑了，既然头结点的数据域不存储任何信息，那么头指针和头结点又有什么异同呢？

1. 头指针

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

2. 头结点

• 头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义（但也可以用来存放链表的长度），但此结点不能计入链表长度值。
• 有了头结点，对在第一个元素结点前插入结点和删除第一结点起操作域其他结点从操作就统一了。
• 头结点不一定是链表的必须要素。

那么，在链表中设置头结点有什么好处呢？

1. 便于首元结点的处理

   首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无需进行处理

2. 便于空表和非空表的统一处理

   无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

一.线性链表（单链表）

1.1定义

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

带头结点的单链表

我们在C语言中可以用结构指针来描述单链表：

typedef struct Node{//声明结点的类型和指向结点的指针类型
    ElemType data;//结点的数据域
    struct Node* Next;//结点的指针域
}Node;
typedef struct Node* LinkList;//LinkList为指向结构体Lnode的指针类型

• 定义链表L：LinkList L
• 定义结点指针p：LNode *p或LinkList p

为了统一链表的操作，通常我们这样定义：先将数据域中要存储的多个数据项定义成一个结构类型，然后直接用这个结构类型来定义这个数据域data.

实例：存储学生学号，姓名，成绩的单链表结点类型定义如下：

typedef Struct{
    char num[8];//数据域
    char name[8];//数据域
    int score;//数据域
}ElemType;
typedef struct Lnode{
    ElemType data;//数据域
    struct Londe* next;//指针域
}Lnode;
typedef struct Node* LinkList;

1.2初始化

1.2.1带头结点的初始化

算法思路：构造一个空表：从内存中找到头结点，用指针变量L指向头结点，给结点的指针域置空。

typedef struct LNode{//定义单链表结点类型
    ElemType data;//每个结点存放一个数据元素
    struct LNode* next;//指针指向下一个结点
}LNode;
typedef struct LNode* LinkList;

//初始化一个单链表（带头结点）
bool InitList(LinkList &L){
    L=(LNode*)malloc(sizeof(LNode));//分配一个头结点
    if(L==NULL){//内存分配不足，分配失败
        return false;
    }
    L->next=NULL;//建立空的单链表，结点之后暂时还没有结点
    return true;
}//bool类型函数返回true或false

void test(){
    LinkList L;//声明一个指向单链表的指针
    //初始化一个空表
    InitList(L);
    ……
}

注意：

L是指向单链表的头结点的指针，用来接收主程序中待初始化单链表的头指针变量的地址

*L相当于主程序中待初始化单链表的头指针变量

1.2.2不带头结点的初始化

typedef struct LNode{//定义单链表结点类型
    ElemType data;//每个结点存放一个数据元素
    struct LNode* next;//指针指向下一个结点
}LNode;
typedef struct Lnode* LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){
    L=NULL;//空表，暂时没有任何结点（防止脏数据）
    return true;
}

void test(){
    LinList L;//声明一个指向单链表的指针
    //初始化空表
    InitList(L);
    ……
}

//判断单链表是否为空
bool Empty(LinkList L){
    if(L==NULL){
        return true;
    }else{
        return false;
    }
}

由此可见这两种情况下判断空表的方法：

• 无头结点时，头指针为空时表示空表
• 有头结点时，当头结点的指针域为空时表示空表

1.3插入

1.3.1按位序插入

在表L中的第i个位置上插入指定元素。那么就要找到第i-1个结点的存储位置p，生成一个数据域为e的新结点t，然后将新结点插入其后面：新结点的指针域指向ai，结点ai-1的指针域指向新结点。注意：这两步操作不能交换顺序，不然会丢失ai的地址。

• 带头结点：

typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList               

//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1){
        return false;
    }
    if(i==1){
        LNode *t = (LNode *)malloc(sizeof(LNode));
        t->data = e;
        t->next = L;
        L = t:      //头指针指向新结点
        return true;
    }
    LNode *p;       //指针p指向当前扫描的结点
    int j = 1;      //当前p指向的是第几个结点
    p = L;          //p指向第一个结点(注意：不是头结点)
    while(p != NULL && j<i-1){      //循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if(p == NULL){      //i值不合法
        return false;
    }
    LNode *t = (LNode *)malloc(sizeof(LNode));
    t->data = e;
    t->next = p->next;
    p->next = t;
    return true;        //插入成功
}

• 不带头结点：

typedef struct LNode{//定义单链表结点类型
    ElemType data;//每个结点存放一个数据元素
    struct LNode* next;//指针指向下一个结点
}LNode;
typedef struct LNode* LinkList;

//在第i个位置插入元素e（不带头结点）
bool ListInsert(LinkList &L,int i,ElemType e){//参数可以是各种类型
    if(i<1){
        return false;
    }
    LNode* p;//指针p指向当前扫描的结点
    int j=0;//当前p指针的是第几个结点
    while(p!=NULL && j<i-1){//循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL){//i值不合法
        return false;
    }
    LNode* t=(LNode*)malloc(sizeof(LNode));//给结点t分配空间
    t->data=e;//给结点t的data赋值为e
    t->next=p->next;//结点t的指针赋值为当前结点p的下一个结点
    p->next=t;//将结点t连接到p之后
    return true;//插入成功
}

当i=1时，执行插入操作所需要的时间复杂度为T(n)=O(1)

当i>1 && i<=n时，时间复杂度为T(n)=O(n)

但是，值得注意的是，实际上插入这个操作真正的时间复杂度为T(n)=O(1),而程序运行所耗费时间都在找到要插入的元素位置的前一个位置，所以综合考究：

标签：结点,单链,LNode,指针,next,链表,链式,数据结构,线性表
From： https://blog.csdn.net/2301_79279099/article/details/142930369