数据结构与算法-C语言6-线性表之链式存储结构

数据结构与算法-目录

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

1.1、线性表链式存储结构定义

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

以前在顺序结构中，每个元素数据只需要存储数据元素信息就可以了。现在在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。

因此，为了表示每个数据元素ai与其直接后级元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。

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

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。

最后一个，当然意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为“空”（通常用NULL或“^”符号表示）。

有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

1.2、头指针与头结点的异同

头指针与头结点的异同点。

头指针 :

• 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针

• 头指针具有标识作用，所以常用头指针冠以链表的名字

• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之间，其数据域一般无意义。

• 有了头结点，对在第一元素结点前插入结点，其操作与其它结点的操作就统一了。

• 头结点不一定是链表必须要素。

1.3、线性链表式存储结构代码描述

若线性链表为空表，则头结点的指针域为“空”。

单链表中，我们在C语言中可用结构指针来描述。

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

在这个结构定义中，我们也就知道，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。 假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针可以用p->next来表示，p->next的值是一个指针。p->next指向谁呢？当然是指向第i + 1个元素，即指向ai+1。也就是说p->data = ai，那么p->next->data=ai+1

2、单链表的读取

在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置使很容易的。但在单链表中，由于第i个元素到底在哪？没办法一开始就知道，必须从头开始找。因此，对于单链表实现获取第i个元素的操作GetElem，在算法上，相对麻烦一些。

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

1. 声明一个指针p指向链表第一个结点，初始化j从1开始。
2. 当j < i 时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1;
3. 若链表末尾p为空，则说明第i个结点不存在；
4. 否则查找成功，返回结点p的数据。
   实现代码如下：

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

说白了，就是从头开始找，直到第i个结点为止。
由于这个算法复杂度取决于i的位置，当i = 1时，不需要变量，而当i = n时则遍历n - 1次才可以。因此最坏情况的时间复杂度是O(n)。
由于单链表的结构没有定义表长，所以不知道事先循环多少次，因此也就不方便使用for来控制循环。

其主要核心思想是“工作指针后移”，这其实也是很多算法常用技术。

3、单链表的插入与删除

3.1、单链表的插入

假设存储元素e的结点为s，要实现结点p、p->next和s之间的逻辑关系的变化，只需要将s插到结点p和p->next之间即可。
根本不需要惊动其他结点，只需要让s->next和p->next的指针做一点改变。

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

1. 声明一指针p指向链表头结点，初始化j从1开始;
2. 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一结点,j累加1
3. 若到链表末尾p为空，则说明第i个结点不存在;
4. 若查找成功，在系统中生成一个空节点s；
5. 将数据元素e赋给s->data；
6. 单链表的插入标准语句s->next = p->next; p->next = s;
7. 返回成功
   实现代码如下：

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

在这段算法代码中，我们用到了C语言的malloc标准函数，它的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中开辟了一段空间，用了存放数据e的s结点。

注意：下面两句不可交换顺序(否则死循环)

s->next = p->next;
p->next = s;

3.2、单链表的删除

设存储元素ai的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向他的后继结点即可。

我们所要做的，实际上就是一步：

p->next = p->next->next;

用q来取代p->next即是：

q = p->next;
p->next = q->next;

也就是说把p的后继结点改成p的后继的后继结点。

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

1. 声明一指针p指向链表头指针，初始化j从1开始；
2. 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，i累加1；
3. 若到链表末尾p为空，则说明第i个结点不存在；
4. 否则查找成功，将欲删除的结点p->next 赋给q；
5. 单链表的删除标准与p->next = q->next；
6. 将q结点中的数据赋给e，作为返回;
7. 释放q结点
8. 返回成功

实现代码如下：

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

分析一下刚才我们讲解的单链表插入和删除算法，我们发现，它们其实都是由两部分组成：
第一部分就是遍历查找第i个结点；
第二部分就是插入和删除结点。

从整个算法来说，我们很容易推导出：它们的时间复杂度都是O(n)。
如果我们不知道第i个结点的指针位置，单链表数据结构在插入和删除操作上，与线下顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置，插入10个结点，对于顺序结构意味着，每次都要移动n - i个结点，每次都是O(n)。而单链表，我们只需在第一次时，找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，事件复杂度为O(1)。

显然，对于插入和删除数据越频繁的操作，单链表的优势就越明显。

4、单链表的整表创建

顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么几种，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置使不需要预先分配划定的，可以根据系统的情况和实际的需求即可生成。

4.1、头插法建立单链表

所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，一次建立各元素结点，并逐个插入链表。
单链表整表创建的思路算法：

1. 声明一指针p和计数器变量1；
2. 初始化一空链表；
3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
4. 循环：
   (1).生成一新结点赋值给p;
   (2).随机生成一数字赋给p的数据域p->data;
   (3).将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(sizoef(Node));//生成新的结点
        p->data = rand() % 100 + 1;//随机生成100以内的数字
        p->next = (*L)->next;
        (*L)->next = p; //插入到表头
    }
}

4.2、尾插法建立单链表

可事实上，根据排队时的正常思维，我们还可以把新结点放在最后。我们每次新结点都插在终端结点的后面，这种算法称之为尾插法。
实现代码如下：

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

注意：

L与r的关系，L指整个单链表，而r指向尾节点的变量，r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。
r->next = p的意思，其实就是将刚才的表尾终端结点r的指针指向新结点p。

5、单链表的整表删除

当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。

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

1. 声明一结点p和q；
2. 将第一个结点赋值给p；
3. 循环 :
   (1).将下一结点赋值给q;
   (2).释放p;
   (3).将q赋值给p。
   实现代码如下：

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

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

简单地对单链表结构和顺序存储结构作对比。

6.1、存储分配方式：

顺序存储结构有一段连续的存储单元依然存储线性表的数据元素。
单链表采用链式存储结构，用一组任意的存储单元存放线性表的玩意。

6.2、时间性能：

查找：

• 顺序存储结构O(1)
• 单链表O(n)

插入与删除

• 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
• 单链表在线出某位置的指针后，插入和删除时间仅为O(1)

6.3、空间性能

• 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢。
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

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

• 若线性表需要频繁查找，很少进入插入和删除操作时，宜采用顺序存储结构。
  若需要频繁插入和删除时，宜采用单链表结构。
  比如游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况下都是读取，所以应该考虑用顺序存储结构。而游戏中的玩家的武器或者装备列表，随着玩家游戏过程中，可能随时增加或删除，此时应该用单链表比较合适。当然，这只是简单地类比。现实生活中的软件开发，要考虑的问题会复杂得多。

• 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不用考虑存储空间大小问题。
  而如果事先知道线性表的大致长度，比如一年12个月，这种用顺序存储结构效率会高很多。

总之，线性表的顺序存储结构和单链表结构各有其优点，不是简单地说哪个不好，需要根据实际情况，来综合平衡采用哪种数据更能满足和达到需求和性能。

特别感谢：
鱼C工作室小甲鱼