单链列表概念

单个链接列表

1. 链接存储方式

以链接模式存储的线性表简称为“链接列表”.

链接列表的特定存储表示为:

①使用一组任意的存储单元存储线性表的节点（此存储单元可以是连续的或不连续的）

②链表中节点的逻辑顺序和物理顺序不一定相同. 为了正确表示节点之间的逻辑关系，在存储每个节点的值的同时，还必须存储指示其后续节点的地址（或位置）信息（称为指针或链接）<

注意:

链式存储是最常用的存储方法之一. 它不仅可以用来表示线性表，而且可以用来表示各种非线性数据结构.

2. 链表的节点结构

┌──┬──┐

│数据│下一步│

└──┴──┘

数据字段-存储节点值的数据字段

下一个字段-存储节点的直接后继地址（位置）的指针字段（链字段）

注意:

①链表通过每个节点的链接域以逻辑顺序将线性表的n个节点链接在一起.

②每个节点只有一个链接域的链接列表称为单个链接列表（单链接列表）.

[示例]线性表（蝙蝠单链表，猫，吃，脂肪，帽子，杰特，拉特，席子）的单链表示形式为

3. 头指针头和终端节点指针字段的表示形式

单链接列表中每个节点的存储地址存储在其前任节点的下一个字段中单链表，并且起始节点没有前任节点，因此应将头指针设置为指向起始节点.

注意:

链接列表由头指针唯一确定. 可以使用头指针的名称来命名单个链表.

[示例]标题指针为head的链接列表可以称为表head.

终端节点没有后继节点，因此终端节点的指针字段为空，即NULL.

4. 单链列表的通用图标方法

由于我们通常只关注节点之间的逻辑顺序，而不关心每个节点的实际位置，因此我们可以使用箭头来表示链域中的指针，线性表（蝙蝠，猫，胖子，帽子，jat，lat），Mat）单链表可以表示为下图.

5. 单链列表的类型描述

typedef char DataType; //假设节点的数据字段类型为字符

typedef struct node {//节点类型定义

DataType数据； //节点的数据字段

结构节点* next; //节点的指针字段

} ListNode;

typedef ListNode * LinkList;

ListNode * p;

LinkList头;

注意:

①LinkList和ListNode *是相同的指针类型，但名称不同（为了更清晰的概念，使用不同的名称）

②LinkList类型的指针变量head表示它是单链表的head指针.

③ListNode *类型的指针变量p表示它是指向某个节点的指针

6. 指针变量和节点变量

┌────┬────────┐┬p

││指针变量│节点变量│

├────┼────────┼┼────────┤

│定义│在变量描述部分明确定义│在执行程序时，通过标准│

│││函数malloc生成│

├────┼────────┼┼────────┤

│值│当不为空时，存储某种类型的节点│实际上存储该节点每个域的内容│

││地址││

├────┼────────┼┼────────┤

│操作方法│通过指针变量名访问│通过指针生成，访问和释放│

└────┴────────┘┴p

①用于生成节点变量的标准函数

p =（ListNode *）malloc（sizeof（ListNode））;

///函数malloc分配类型为ListNode的节点变量的空间，并将其第一个地址放入指针变量p

②释放节点变量空间的标准函数

free（p）; //释放p指向的节点变量空间

③访问节点组件

使用节点变量* p的名称访问节点组件

方法一: （* p）.data和（* p）.next

方法2: p-﹥ data和p-﹥ next

④指针变量p和节点变量* p

之间的关系

指针变量p的值-节点地址

节点变量* p的值-节点的内容

（* p）.data value-p指针指向的节点的数据字段的值

（* p）.next value- * p后继节点地址

*（（（* p）.next）-* p个后继节点

注意:

①如果指针变量p的值为NULL，则它不指向任何节点. 这时，如果使用* p访问该节点，则意味着访问一个不存在的变量，从而导致程序错误.

②有关指针类型的含义和描述的详细说明，请参阅C语言的相关信息.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-235644-1.html