【入门】单链表的逻辑存储和空间存储及结构体伪代码详解

先了解两个定义：

逻辑结构：抽象化的数学模型
存储结构：数据元素在计算机内部存储方式

当解决问题的时候，我们先思考该怎么把数据抽象出来模型，再试图将这些抽象模型存储进计算机。

今天要介绍的单链表属于逻辑结构中的线性结构之一：线性表。

1.什么是线性表

除第一个元素之外，每个元素都只有唯一的直接前驱。
除最后一个元素之外，每个元素都只有唯一的直接后继。

线性表分为顺序表和链表。

1.1什么是顺序表

逻辑上相邻的数据，在计算机中空间存储方式也相邻。

就像在一条每个房子紧挨着的街道上，第一个房子标记为0，第二个房子标记为1…依次递增。

这个时候有个调皮的小孩小皮，想在每个房子的墙上都画上图案，可能是数字1，2，3…也可能是字母a,b,c,d…

而由于房子都是连成的一排，小皮只要从第0个房子一直往后走就能遍历往后走就可以遍历完所有的房子。

而在计算机中，最常用数组进行顺序表的存储。

1.2什么是链表

逻辑上相邻的数据，在计算机中空间存储方式不一定相邻。

小皮又来到了一张地图上。每个房子坐落在上面，但并不像顺序表一样排成一排，而像一盘散沙。同样给每个房子标记0，1，2，3…同时，如果要从第0个房子走到第一个房子，可是两个房子又不相邻，该怎么办？

链表通过增加指针域来处理空间上不相邻的情况。

链表的逻辑存储结构

很简单，只要在第0个房子墙上记录一下第1个房子的地址就可以了。当小皮逛完了第i个房子，按照墙上的地址找到第i+1个房子。

也就是说，这个房子的墙上需要记录两个类型，一个存储标记的数值（称为数据域），另一个存储下一间房子的地址（称为指针域）。

那么有了这个逻辑结构之后，我们该怎么在计算机里实现它的存储结构呢？

链表的空间存储结构

书上一般这么写：

typedef struct LNode{  ElemType data; //数据域 struct LNode *next;//指针域 }Lnode,*Linklist;//如果看教材的话，大概率都是这样的伪代码 

一堆看不懂的字母，是不是很头大？我们先忽视括号里的，看括号外的，这个最常出现的单词typedef：

typedef = type + def。type：类型，def：define的缩写。
typedef可以粗略地理解为类型定义。

我们都知道整型在C语言里叫int,长整型叫long，单精度叫char，双精度叫double…有一天这些类型突发奇想，给自己取一个接地气的名字，比如：

typedef int zhangsan;//直接打中文不行，我试过了 

之后如果要定义一个整型变量a：

zhangsan a; //不怕被打可以这么写 

typedef的作用就是给数据类型起个别名。

当然typedef的作用并不只是去干这些闲着蛋疼的操作，当我们自定义一个数据类型——结构体的时候（结构体的本质是我们自定义了一个数据类型），我们想在这个数据类型里塞整型、浮点型，甚至指针变量，比如：

struct Carpet{ //定义了一个“毯子类型”  int a;//毯子的长 int b;//毯子的宽 char c;//毯子上的图案  }; 

调用的时候这么写：

struct Carpet w;//创建了一块毯子  w.a = 1;//这块毯子长为1  w.b = 2;//宽为2 w.c = 'A';//图案是A； cout<<w.a<<" "<<w.b<<" "<<w.c<<endl;//输出 

人类的本质就是懒惰，定义一个数据类型还要写两个字母，于是发明了typedef简化一下：

struct Carpet{ //定义了一个“毯子类型”  int a;//毯子的长 int b;//毯子的宽 char c;//毯子上的图案  }; typedef struct Carpet carpet; 

声明变量时：

carpet w1;//省去了开头写struct 

人类的本质是变得更懒，我能不能直接把它们写在一起呢？于是：

typedef struct Carpet{ //定义了一个“毯子类型”  int a;//毯子的长 int b;//毯子的宽 char c;//毯子上的图案  }carpet;//等价于上面的代码  

有了这些知识储备，理解这个也就不难了。

typedef struct LNode{ } Lnode,*Linklist; 

就是说我们先定义了一个结构体struct LNode（或者说自定义了一个数据类型）,中括号里的是对这个结构体的描述，然后给这个结构体类型取了一个别名 Lnode和*Linklist（Linklist为指针类型，不理解的我以后再讲）

可以这么理解：struct LNode == Lnode == *Linklist 
它们都是“几乎”都是等价的数据类型名称。

struct LNode p; Lnode p; *Linklist p; //三者效果一样 

说完了这些，我们再看中括号里面的数据域：

ElemType data; 

ElemType显然是用英文单词拼接成的伪代码，英语：

ElemType = element type  element:元素。

连起来就是元素类型。
因为是伪码，直接写会报错，需要另外定义，比如：

#define ElemType int//定义int为数据域的元素类型 typedef int ElemType //define和typedef定义顺序相反 

嫌麻烦就直接在结构体中需要什么数据类型就写什么。

再看指针域：

struct LNode *next; 

这个就很有意思了，需要对指针有一定理解。

我们刚已经分析过，指针域是用来存储下一间房子的地址，而这些房子的类型定义为了struct LNode, struct LNode next 就是说用next存放的地址，而地址所指向的数据类型是struct LNode。

那么关于单链表的逻辑存储和空间存储就介绍到这里。当然这只是一个小小的开始，就像建房子只造了模型而未开始实践。关于单链表的初始化、创建、插入、取值等一系列的基本操作，可以见下一篇：
（看到这个括号说明我还没开始写）