鍊表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连线每个结点的地址数据。

以“结点的序列”表示线性表称作线性鍊表（单鍊表），单鍊表是链式存取的结构。

连结方式存储的线性表简称为鍊表（Linked List）。

鍊表的具体存储表示为：

① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）

② 鍊表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关係，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）

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

┌───┬───┐

│data │next │

└───┴───┘

data域--存放结点值的数据域

next域--存放结点的直接后继的地址（位置）的指针域（链域）

鍊表通过每个结点的链域将线性表的n个结点按其逻辑顺序连结在一起的，每个结点只有一个链域的鍊表称为单鍊表（Single Linked List）。

单鍊表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。鍊表由头指针唯一确定，单鍊表可以用头指针的名字来命名。

终端结点无后继，故终端结点的指针域为空，即NULL。

typedef char DataType; //假设结点的数据域类型为字元

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

DataType data; //结点的数据域

struct node *next;//结点的指针域

}ListNode;

typedef ListNode *LinkList;

ListNode *p;

LinkList head;

注意：

①LinkList和ListNode是不同名字的同一个指针类型（命名的不同是为了概念上更明确）

②*LinkList类型的指针变数head表示它是单鍊表的头指针

③ListNode类型的指针变数p表示它是指向某一结点的指针

①生成结点变数的标準函式

p=( ListNode *)malloc(sizeof(ListNode))；

//函式malloc分配一个类型为ListNode的结点变数的空间,并将其首地址放入指针变数p中

②释放结点变数空间的标準函式

free(p)；//释放p所指的结点变数空间

③结点分量的访问

利用结点变数的名字*p访问结点分量

方法一：(*p).data和(*p).next

方法二：p-﹥data和p-﹥next

④指针变数p和结点变数*p的关係

指针变数p的值——结点地址

结点变数*p的值——结点内容

(*p).data的值——p指针所指结点的data域的值

(*p).next的值——*p后继结点的地址

*((*p).next)——*p后继结点

注意：

① 若指针变数p的值为空（NULL），则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变数，从而引起程式的错误。

② 有关指针类型的意义和说明方式的详细解释

可见，在鍊表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。

因此，在单鍊表中第 i 个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。

单鍊表的建立有头插法、尾插法两种方法。

单鍊表是用户不断申请存储单元和改变连结关係而得到的一种特殊数据结构，将鍊表的左边称为链头，右边称为链尾。头插法建单鍊表是将鍊表右端看成固定的，鍊表不断向左延伸而得到的。头插法最先得到的是尾结点。

由于鍊表的长度是随机的，故用一个while循环来控制鍊表中结点个数。假设每个结点的值都大于O，则循环条件为输入的值大于o。申请存储空间可使用malloc()函式实现，需设立一申请单元指针，但malloc()函式得到的指针并不是指向结构体的指针，需使用强制类型转换，将其转换成结构体型指针。刚开始时，鍊表还没建立，是一空鍊表，head指针为NULL。

鍊表建立的过程是申请空间、得到数据、建立连结的循环处理过程。

若将鍊表的左端固定，鍊表不断向右延伸，这种建立鍊表的方法称为尾插法。尾插法建立鍊表时，头指针固定不动，故必须设立一个搜寻指针，向鍊表右边延伸，则整个算法中应设立三个鍊表指针，即头指针head、搜寻指针p2、申请单元指针pl。尾插法最先得到的是头结点。

鍊表操作中动态存储分配要使用标準函式，先介绍一下这些函式。

(1)malloc(size)

在记忆体的动态存储区申请一个长度为size位元组的连续空间。

(2)calloc(n，size)

在记忆体的动态存储区申请n个长度为size位元组的连续空间，函式返回值为分配空间的首地址。若此函式未被成功执行，函式返回值为0。

(3)free(p)

释放由指针p所指向的存储单元，而存储单元的大小是最近一次调用malloc()或calloc()函式时所申请的存储空间。

在头档案\"stdlib．h”中包含了这些函式的信息，使用这些函式时需在程式开头用档案包含指令#include“stdlib．h”指明。

调用动态存储分配函式返回的指针是指向void类型或char类型的指针，在具体使用时，要根据所指向的数据进行强制类型转换。