数据结构之线性表

数据结构与算法

---

一、线性表的定义

线性表：零个或多个数据元素的有限序列。
A1——A2——A3——...——Ai-1——Ai——Ai+1——...——An
其中，Ai-1称为Ai的直接前驱元素，Ai+1称为Ai的直接后继元素。直接前驱元素与直接后继元素都是唯一的。n(n>=0)为线性表的长度，n=0称为空表，i为数据元素Ai在线性表中的为位序。在复杂的线性表中，一个数据元素可以由若干个数据项组成。

1.1 线性表的抽象数据定义

ADT 线性表(List)
Data
    线性表的数据对象集合为{a1, a2, ......, an}，每个元素的类型均为DataType。
    其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，
    除了最后一个元素an外，每一个元素有且只有一个直接后继元素。
    数据元素之间的关系是一对一的关系。
Operation
    InitList(*L):          初始化操作，建立一个空的线性表L。
    ListEmpty(L):          若线性表为空，返回true，否则返回false。
    ClearList(*L):         将线性表清空。
    GetElem(L, i, *e):     将线性表L中的第i个位置元素值返回给e。
    LocateElem(L, e):      在线性表L中查找与给定值e相等的元素，
                           如果查找成功，返回该元素在表中序号表示成功；
    ListInsert(*L,i,e):    在L的第i个位置插入新元素e。
    ListDelete(*L,i,*e):   删除L中的第i个元素，并用e返回其值。
    ListLength(L):         返回L中的元素个数
endADT

1.2 例子：两线性表的并集操作：A=A∪B

/* 将所有的在线性表Lb中但不在La中的数据元素插入到La中 */
void unionL(List *La, List Lb)
{
    int La_len, Lb_len, i;
    /* 声明与La和Lb相同的数据元素e */
    ElemType e;                             
    /* 求线性表的长度 */
    La_len = ListLength(*La);               
    Lb_len = ListLength(Lb);
    for (i = 1; i <= Lb_len; i++)
    {
        /* 取Lb中第i个数据元素赋给e */
        GetElem(Lb, i, &e);                 
        /* La中不存在和e相同数据元素 */
        if (!LocateElem(*La, e))            
            /* 插入 */
            ListInsert(La, ++La_len, e);    
    }
}

二、线性表的顺序存储结构

2.1 顺序存储结构的定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
线性表顺序存储的结构代码

/* 存储空间初始分配量 */
#define MAXSIZE 20             
/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;          
typedef struct
{
    /* 数组存储数据元素，最大值为MAXSIZE */
    ElemType data[MAXSIZE];    
    /* 线性表当前长度 */
    int length;                
} SqList;

描述顺序存储结构需要三个属性：

• 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
• 线性表的最大存储容量：数组长度MaxSize。
• 线性表的当前长度：length。
  地址计算方法
  
  从图中可看出，在任意时刻，线性表的长度应该小于等于数组的长度。
  地址：存储器中的每个存储单元都有自己的编号，这个编号称为地址。
  每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间的。假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）。

LOC(ai+1)=LOC(ai)+c
LOC(ai)=LOC(a1)+(i-1)*c

2.2 插入与删除操作

获取元素

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/* Status是函数的类型，其值是函数结果状态代码，如OK等 */
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(SqList L, int i, ElemType *e)
{
    if (L.length == 0 || i < 1 || 
        i > L.length)
        return ERROR;
    *e = L.data[i - 1];
    return OK;
}

插入操作
基本思路：

• 如果插入位置不合理，抛出异常；
• 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
• 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
• 将要插入元素填入位置i处；
• 表长加1。

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L, int i, ElemType e)
{
    int k;
    /* 顺序线性表已经满 */
    if (L->length == MAXSIZE)                       
        return ERROR;
    /* 当i不在范围内时 */
    if (i < 1 || i >L->length + 1)                  
        return ERROR;
    /* 若插入数据位置不在表尾 */
    if (i <= L->length)                             
    {
        /*将要插入位置后数据元素向后移动一位 */
        for (k = L->length - 1; k >= i - 1; k--)    
            L->data[k + 1] = L->data[k];
    }
    /* 将新元素插入 */
    L->data[i - 1] = e;                             
    L->length++;
    return OK;
}

$$\color{red}{注意：第i个元素的下标是i，但是其数据对应的是data[i-1]。}$$
删除操作
删除算法的思路：

• 如果删除位置不合理，抛出异常；
• 取出删除元素；
• 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
• 表长减1。

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L, int i, ElemType *e)
{
    int k;
    /* 线性表为空 */
    if (L->length == 0)                    
           return ERROR;
    /* 删除位置不正确 */
    if (i < 1 || i > L->length)            
        return ERROR;
    *e = L->data[i - 1];    /*返回删除的元素*/
    /* 如果删除不是最后位置 */
    if (i < L->length)                     
    {
        /* 将删除位置后继元素前移 */
        for (k = i; k < L->length; k++)    
            L->data[k - 1] = L->data[k];
    }
    L->length--;
    return OK;
}

$\color{red}{插入与删除操作的时间复杂度都是O(n)}$
线性表顺序存储结构的优缺点

优点	缺点
无须为表示表中元素之间的逻辑关系而增加额外的存储空间	插入和删除需要移动大量的元素
可以快速地存取表中任一位置的元素	当线性表长度变化较大时，难以确定存储空间的容量
	造成存储空间的“碎片”

三、线性表的链式存储结构

3.1 链式存储结构的基本概念

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。
存储数据元素信息的域称为数据域，存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。

n个结点（ai的存储映像）链结成一个链表，即为线性表（a1,a2,...,an）的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起，如下图所示：

链表中第一个结点的存储位置叫做头指针，整个链表的存取必须是从头指针开始。之后的每一个结点，是上一个的后继指针指向的位置。线性链表的最后一个结点指针为“空”（通常用NULL或“^”符号表示）。
有时，为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，指针域存储指向第一个结点的指针。

头指针与头结点的异同

头指针	头结点
头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针	头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据一般无意义（也可能存放链表的长度）
头指针具有标识作用，所以常用头指针冠以链表的名字	有了头指针，对在第一元素结点前插入结点和删除第一节点，其操作与其它结点的操作就统一了
无论链表是否为空，头指针均不为空，头指针是链表的必要元素	头结点不一定是链表的必要元素

线性表链式存储结构代码描述
不带头指针的单链表示意图：

/* 线性表的单链表存储结构 */
typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node;
/* 定义LinkList */
typedef struct Node *LinkList; 

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

3.2 单链表的读取

获得链表第i个数据的算法思路：

• 声明一个指针p指向链表第一个结点，初始化j从1开始；
• 当j
• 若到链表末尾p为空，则说明第i个结点不存在；
• 否则查找成功，返回结点p的数据。

实现代码算法如下：

/* 初始条件：顺序线性表L已存在，1≤i≤
   ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L, int i, ElemType *e)
{
    int j;
    LinkList p;            /* 声明一指针p */
    p = L->next;        /* 让p指向链表L的第个结点 */
    j = 1;                 /* j为计数器 */
    /* p不为空且计数器j还没有等于i时，循环继续 */
    while (p && j < i)    
    {
        p = p->next;    /* 让p指向下一个结点 */
        ++j;
    }
    if (!p || j > i)
        return ERROR;      /* 第i个结点不存在 */
    *e = p->data;       /* 取第i个结点的数据 */
    return OK;
}

$\color{red}{最坏情况的时间复杂度是O(n)。}$
单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就不方便使用for来控制循环。其主要核心思想就是“工作指针后移”，这也是很多算法的常用技术。

3.3 单链表的插入与删除

单链表的插入

单链表第i个数据插入结点的算法思路：

• 声明一指针p指向链表头结点，初始化j从1开始；
• 当j
• 若到链表末尾p为空，则说明第i个结点不存在；
• 否则查找成功，在系统中生成一个空结点s；
• 将数据元素e赋值给s->data；
• 单链表的插入标准语句s->next=p->next;p->next=s； （不能反！！）
• 返回成功。

实现代码算法如下：

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个结点位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(LinkList *L, int i, ElemType e)
{
    int j;
    LinkList p, s;
    p = *L;
    j = 1;
    /* 寻找第i-1个结点 */
    while (p && j < i)                     
    {
        p = p->next;
        ++j;
    }
    /* 第i个结点不存在 */
    if (!p || j > i)
        return ERROR;                      
    /* 生成新结点（C标准函数） */
    s = (LinkList)malloc(sizeof(Node));    
    s->data = e;
    /* 将p的后继结点赋值给s的后继 */
    s->next = p->next;                    
    /* 将s赋值给p的后继 */
    p->next = s;                           
    return OK;
}

C语言的malloc标准函数:作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中找了一小块空地，准备用来存放数据e的s结点。
单链表的删除

删除结点的算法思路：
- 声明一指针p指向链表头结点，初始化j从1开始；
- 当j - 若到链表末尾p为空，则说明第i个结点不存在；
- 否则查找成功，将欲删除的结点p->next赋值给q；
- 单链表的删除标准语句p->next=q->next；
- 将q结点中的数据赋值给e，作为返回；
- 释放q结点；
- 返回成功。

实现代码算法如下：

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个结点，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L, int i, ElemType *e)
{
    int j;
    LinkList p, q;
    p = *L;
    j = 1;
    /* 遍历寻找第i-1个结点 */
    while (p->next && j < i)    
    {
        p = p->next;
        ++j;
    }
    /* 第i个结点不存在 */
    if (!(p->next) || j > i)
        return ERROR;           
    q = p->next;
    /* 将q的后继赋值给p的后继 */
    p->next = q->next;          
    /* 将q结点中的数据给e */
    *e = q->data;               
    /* 让系统回收此结点，释放内存 */
    free(q);                    
    return OK;
}

C语言的标准函数free:作用就是让系统回收一个Node结点，释放内存。
$\color{red}{两个算法时间复杂度为O（n）},对于普通的插入一个元素，比顺序储存结构没有多大优势，，但是对于要在i位置插入几十个元素，则优势很明显。$

3.4 单链表的整表创建

顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。
所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。
单链表整表创建的算法思路：

• 声明一指针p和计数器变量i；
• 初始化一空链表L；
• 让L的头结点的指针指向NULL，即建立一个带头结点的单链表；

• 循环

  • 生成一新结点赋值给p；
  • 随机生成一数字赋值给p的数据域p->data；
  • 将p插入到头结点与前一新结点之间。

  实现代码算法如下：

/* 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L, int n)
{
    LinkList p;
    int i;
    /* 初始化随机数种子 */
    srand(time(0));                            
    *L = (LinkList)malloc(sizeof(Node));
    /* 先建立一个带头结点的单链表 */
    (*L)->next = NULL;                         
    for (i = 0; i < n; i++)
    {
        /* 生成新结点 */
        p = (LinkList)malloc(sizeof(Node));    
        /* 随机生成100以内的数字 */
        p->data = rand() % 100 + 1;            
        p->next = (*L)->next;
        /* 插入到表头 */
        (*L)->next = p;                        
    }
}

这种方法叫做头插法，始终让新结点在第一的位置。
类似的还有一种叫做尾插法，其实现代码为：

/* 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{
    LinkList p,r;
    int i;
    /* 初始化随机数种子 */
    srand(time(0));                         
    /* *L为整个线性表 */
    *L = (LinkList)malloc(sizeof(Node));    
    /* r为指向尾部的结点 */
    r = *L;                                 
    for (i = 0; i < n; i++)
    {
        /* 生成新结点 */
        p = (Node *)malloc(sizeof(Node));   
        /* 随机生成100以内的数字 */
        p->data = rand() % 100 + 1;         
        /* 将表尾终端结点的指针指向新结点 */
        r->next = p;                        
        /* 将当前的新结点定义为表尾终端结点 */
        r = p;                              
    }
    /* 表示当前链表结束 */
    r->next = NULL;                         
}

3.5 单链表的整表删除

整表删除的算法思路如下：

• 声明一指针p和q；

• 将第一个结点赋值给p；
  循环：

  • 将下一结点赋值给q；
  • 释放p；
  • 将q赋值给p。

实现代码算法如下：

/* 初始条件：顺序线性表L已存在，操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
    LinkList p, q;
    /* p指向第一个结点 */
    p = (*L)->next;       
    /* 没到表尾 */
    while (p)             
    {
        q = p->next;
        free(p);
        p=q;
    }
    /* 头结点指针域为空 */
    (*L)->next = NULL;    
    return OK;
}

3.6 单链表结构与顺序存储结构优缺点

存储类别	顺序存储结构	单链表
存储分配方式	用一段连续的存储单元依次存储线性表的数据元素	采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能	查找O（1）、插入和删除O（n）	查找O（n）、插入和删除O（1）
空间性能	需要预分配存储空间，分大了浪费，小了容易发生上溢	不需要分配存储空间，只要有就可以分配，元素个数不受限制

通过上面的对比，可以得出一些经验性的结论：

• 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
• 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，用顺序存储结构效率会高很多。

四、静态链表

4.1 静态链表基本概念

对于可以使用指针的语言，单链表已经很方便了，但是并不是所有语言都有指针功能。那么对于没有执政功能的语言如何实现单链表呢？答案就是利用数组。

如果让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据；而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把cur叫做游标。
用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。
对于数组第一个和最后一个元素作为特殊元素处理，不存数据。通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，则为0。

此时的图示相当于初始化的数组状态，见下面代码：

/* 将一维数组space中各分量链成一备用链表， */
/* space[0].cur为头指针，"0"表示空指针 */
Status InitList(StaticLinkList space)
{
    int i;
    for (i = 0; i < MAXSIZE - 1; i++)
        space[i].cur = i + 1;
    /* 目前静态链表为空，最后一个元素的cur为0 */
    space[MAXSIZE - 1].cur = 0;    
    return OK;
}

4.2 静态链表的插入操作

先定义数组的申请与释放操作
为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SLL(StaticLinkList space)
{
    /* 当前数组第一个元素的cur存的值，就是要返回的第一个备用空闲的下标 */
    int i = space[0].cur;               
    /* 由于要拿出一个分量来使用了，所以我们就得把它的下一个分量用来做备用 */
    if (space[0].cur)
        space[0].cur = space[i].cur;    
    return i;
}

于是就有实现代码：

/* 在L中第i个元素之前插入新的数据元素e  */
  Status ListInsert(StaticLinkList L, int i, ElemType e)
  {
      int j, k, l;
      /* 注意k首先是最后一个元素的下标 */
      k = MAX_SIZE - 1;                   
      if (i < 1 || i > ListLength(L) + 1)
          return ERROR;
      /* 获得空闲分量的下标 */
      j = Malloc_SSL(L);                  
      if (j)
      {
         /* 将数据赋值给此分量的data */
         L[j].data = e;                  
         /* 找到第i个元素之前的位置 */
         for (l = 1; l <= i - 1; l++)    
             k = L[k].cur;
         /* 把第i个元素之前的cur赋值给新元素的cur */
         L[j].cur = L[k].cur;        
         /* 把新元素的下标赋值给第i个元素之前元素的cur */
         L[k].cur = j;                   
         return OK;
     }
     return ERROR;
 }   

4.3 静态链表的删除操作

先定义释放元素函数：

/* 删除在L中第i个数据元素e */
Status ListDelete(StaticLinkList L, int i)
{
    int j, k;
    if (i < 1 || i > ListLength(L))
        return ERROR;
    k = MAX_SIZE - 1;
    for (j = 1; j <= i - 1; j++)
        k = L[k].cur;
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SSL(L, j);
    return OK;
}
/* 将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticLinkList space, int k)
{
    /* 把第一个元素cur值赋给要删除的分量cur */
    space[k].cur = space[0].cur;    
    /* 把要删除的分量下标赋值给第一个元素的cur */
    space[0].cur = k;               
}

4.4 静态链表优缺点

优点	缺点
在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点	没有解决连续存储分配带来的表长难以确定的问题，失去了顺序存储结构随机存取的特性

静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管不一定会用得上，但这样的思考方式是非常巧妙的。

五、循环链表

5.1 循环链表的定义

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）。
循环链表解决了一个很麻烦的问题：如何从当中一个结点出发，访问到链表的全部结点。
非空循环链表示意图：

从上图中可以看到，终端结点用尾指针rear指示，则查找终端结点是O(1)，而开始结点，其实就是rear->next->next，其时间复杂也为O(1)。

5.2 循环链表的并集操作

考虑两个循环链表：

要想把它们合并，只需要如下的操作即可：

对应的代码为：

/* 保存A表的头结点，即① */
p = rearA->next;                    
/*将本是指向B表的第一个结点（不是头结点） */
rearA->next = rearB->next->next;    
/* 赋值给reaA->next，即② */
q = rearB->next;
/* 将原A表的头结点赋值给rearB->next，即③ */
rearB->next = p;                    
/* 释放q */
free(q);

六、双向链表

6.1 双向链表定义

双向链表（double linkedlist）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

/* 线性表的双向链表存储结构 */
typedef struct DulNode
{
    ElemType data;
    struct DuLNode *prior;    /* 直接前驱指针 */
    struct DuLNode *next;     /* 直接后继指针 */
} DulNode, *DuLinkList;

双向链表也可以是循环表。
双向链表的循环带头结点的空链表:

非空的循环的带头结点的双向链表:

对于双向链表：

p->next->prior = p = p->prior->next

6.2 双向链表的插入操作

/* 把p赋值给s的前驱，如图中① */
s->prior = p;          
/* 把p->next赋值给s的后继，如图中② */
s->next = p->next;     
/* 把s赋值给p->next的前驱，如图中③ */
p->next->prior = s;    
/* 把s赋值给p的后继，如图中④ */
p->next = s;

关键在于它们的顺序，由于第2步和第3步都用到了p->next。如果第4步先执行，则会使得p->next提前变成了s，使得插入的工作完不成。

6.2 双向链表的删除操作

/* 把p->next赋值给p->prior的后继，如图中① */
p->prior->next = p->next;     
/* 把p->prior赋值给p->next的前驱，如图中② */
p->next->prior = p->prior;    
/* 释放结点 */
free(p); 

七、广义表

给定二元多项式：

$$P(x,y)=9x^{12}y^{2}+4x^{12}+15x^{8}y^{3}-x^{8}y+3x^{2}$$
如何用线性表表示？
其实，把上式稍稍变形，有
$$P(x,y)=(9y^{2}+4)x^{12}+(15y^{3}-y)x^{8}+3x^{2} ==> ax^{12}+bx^{8}+cx^{2}$$
故可以用一“复杂”的链表表示：

7.1 广义表定义

广义表(Generalized List)

• 广义表是线性表的推广
• 对于线性表而言， n个元素都是基本的单元素；广义表中，这些元素不仅可以是单元素也可以是另一个广义表。

typedef struct GNode{
int Tag; /*标志域：0表示结点是单元素，1表示结点是广义表 */
union { /* 子表指针域Sublist与单元素数据域Data复用，即共用存储空间 */
ElementType Data;
struct GNode *SubList;
} URegion;
struct GNode *Next; /* 指向后继结点 */
} GList;

7.2 多重链表

多重链表：链表中的节点可能同时隶属于多个链

• 多重链表中结点的指针域会有多个；
• 包含两个指针域的链表并不一定是多重链表，比如在双向链表不是多重链表。
• 多重链表有广泛的用途：基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。

矩阵可以用二维数组表示，但二维数组表示有两个缺陷：

• 数组的大小需要事先确定
• 对于“稀疏矩阵 ”，将造成大量的存储空间浪费

解决方案是：采用十字链表来存储稀疏矩阵

• 只存储矩阵非0元素项
  
  • 结点的数据域：行坐标Row、列坐标Col、数值Value
• 每个结点通过两个指针域，把同行、同列串起来;
  
  • 行指针(或称为向右指针)Right
  • 列指针（或称为向下指针）Down
• 用一个标识域Tag来区分头结点和非0元素结点
• 头节点的标识值为“Head”，矩阵非0元素结点的标识值为“Term”。

对于稀疏矩阵A：

$$\begin{bmatrix} 18 & 0 & 0 & 2 & 0 \\ 0 & 27 & 0 & 0 & 0 \\ 0 & 0 & 0 & -4 & 0 \\ 23 & -1 & 0 & 0 & 12 \\ \end{bmatrix}$$