0.前言

存储方式分为顺序存储结构和链式存储结构。

顺序存储结构的优缺点：

优点：可以通过一个简单的公式随机存取表中的任一元素，逻辑关系上相邻的两个元素在物理位置上也是相邻的，且很容易找到前驱跟后继元素。

缺点：在线性表的长度不确定时，必须分配最大的存储空间，使存储空间得不到充分利用，浪费了宝贵的存储资源；线性表的容量一经定义就难以扩充；在插入和删除线性表的元素时，需要移动大量的元素，浪费了时间。

链式存储结构：

在程序执行过程中，通过两个命令向计算机随时申请存储空间或随时释放存储空间，以达到动态管理、使用计算机的存储空间、保证存储资源的充分利用。这样的存储方式称为动态存储。

1.基本概念

为了表示任意存储单元之间的逻辑关系，对于每个数据元素来说，除了要存储它本身的信息（数据域、data）外，还要存储它的直接后继元素的存储位置（指针域、link或next）。我们把这两部分信息合在一起称为一个“结点node”。

（1）N个结点链接在一起就构成了一个链表。N=0时，称为空链表。

（2）为了按照逻辑顺序对链表中的元素进行各种操作，我们需要定义一个变量用来存储整个链表的第一个结点的物理位置，这个变量称为“头指针、H或head”。也可以把头指针定义成一个结点，称为“头结点”，头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头结点的指针域（头指针）存储指向第一个结点的指针，若线性表为空表，则头结点的指针域为空。由于最后一个元素没有后继，所以线性表中最后一个结点的指针域为空。

2.单链表定义

类型和变量的说明

struct Node
{
    int data;
    Node * next;
};
Node * p;

申请存储单元

p = new Node;    //动态申请、空间大小由指针变量的基类型决定

指针变量的赋值：

指针变量名=NULL