数据结构（一）：线性表的顺序存储和链式存储

程序员文章站 2022-06-05 14:53:22

...

1. 线性表的定义和概念：

线性表(List) ：零个或多个数据元素的有限系列。

线性表有两个重要的特性：1）线性表中元素的个数是有限的；

2）线性表中每个元素是有序的；In another opinon, 除第一个元素无前驱节点，最后一个元素无后继节点之外，每一个元素都有且只有一个前驱节点和一个后继结点（这句话其实只是针对最基础的线性表，例如：循环链表每个元素都有前驱节点和后继节点）。

线性表的实现可以采用顺序存储的方式，也可以采用链式存储的方式。

2. 线性表之顺序存储：

1）线性表的顺序存储就是使用一块连续的内存空间进行存储。一般而言我们是使用一个固定长度的数组来实现的。抽象定义如下：

#define LIST_MAX_LENGTH  XXX         //线性表中可以存储的最大元素个数

typedef int ElemType;                //元素类型

typedef struct {
    ElemType data[LIST_MAX_LENGTH];  //定义一个固定长度的数据
    int length;                      //记录当前线性表中元素个数
}sqList;

2）由于采用顺序存储的方式，需要实现分配固定大小的连续空间（指定LIST_MAX_LENGTH），这就需要实现确定该链表的大概长度范围，否则可能因开辟空间太小造成线性表的溢出或者开辟空间太大的浪费。

3）对顺序存储的线性表进行插入操作时：在插入元素时线性表可能已满，再行存储可能造成溢出，因此需要进行线性表已满的判断处理；在进行删除操作的时候，如果线性表为空，则根本无需进行删除操作。对于顺序存储，如果进行插入操作，需要将后续元素进行统一后移，这个平均的时间复杂度为O(n/2), 删除操作也是同样，需要将该元素之后的所有元素进行前移，平均的时间复杂度也是O(n/2), 这就导致了顺序存储不适于频繁的插入和删除操作，而对于查询操作无论元素在前还是在后面可以通过数组的下标进行直接的访问。

3. 线性表之链式存储

1）链式存储就是采用链表的方式对线性表进行存储。抽象的节点定义如下：

/*  线性表之链式存储*/

typedef struct linkList_{
    ElemType data;          //存储数据
    struct node_ *next;     //存放下一个节点指针
}linkList_st, *linkList_pt;

2）头结点和头指针：

数据结构（一）：线性表的顺序存储和链式存储

头结点并不是必须的，它的存在是为了方便对第一个(也就是a1结点)的处理：操作如下

/*
*  1. 无头链表的插入linkListInsert：
*       L:    链表头指针的地址
*       data: 待插入的元素数据
*       i:    位置
*/
int linkListInsert(linkNode_pt *L, ElemType data, int i)
{
    linkNode_pt p = *L;
    linkNode_pt node = NULL;
    int n = 1;
    
    while(p && n<i){
        n++;
        p = p->next;
    }

    if(!p || n>i) return -1; /*out of range*/    

    if(!(node = (linkNode_pt)malloc(sizeof(linkNode_st)))){
        printf("molloc error\n");
        return -1;
    }
    }
    node->data = data;     /*假定为简单的数据类型，直接进行赋值操作*/
    if(n=1){               /*实际i等于1,即插入到第一个位置*/
        node->next = *L;   /*因为是改变头指针的指向，所以在函数传参时传递二级指针*/ 
        L = &node;         /*头指针前移*/
    }else{
        node->next = p->next;
        p->next = node;
    }
    return 0;
}

/*
*  2. 有头链表的插入linkListInsert：
*       L:    链表头指针的地址
*       data: 待插入的元素数据
*       i:    位置
*/
int linkListInsert(linkNode_pt *L, ElemType data, int i)
{
    linkNode_pt p = *L;
    linkNode_pt node = NULL;
    int n = 1;
    
    while(p && n<i){
        n++;
        p = p->next;
    }

    if(!p || n>i) return -1; /*out of range*/    

    if(!(node = (linkNode_pt)malloc(sizeof(linkNode_st)))){
        printf("molloc error\n");
        return -1;
    }
    }
    node->data = data;       /*假定为简单的数据类型，直接进行赋值操作*/
    {                        /*有头结点时，对第一个节点的处理和其他节点一样*/
        node->next = p->next;/*头结点地址没变化，因此可以不使用二级指针*/
        p->next = node;
    }
    return 0;
}

从上述代码中可以看出：头结点的存在是为了方便对链表进行无差别的操作(主要实在插入和删除操作时)，不用再区别对待第一个结点和其他节点；但是头结点不是必需的，无头的链表依然可以正常操作，但是得单独处理第一个节点。

3）二级指针的疑问

我们在书中经常看到函数传递参数是区分值传递和地址传递：

值传递只是将该变量a的值传递给函数的形参b，而函数的形参b将值存到自己的内存中，自己值得改变只会影响b自己, 而不会影响到a的值；

地址传递则是将变量a的地址传递给形参b, 此时的b是个指针，而b的值则为变量a的地址，也就是说，b指向a; 因此当变量b的值改变后会影响到a的值；

现在把地址传递进行升级：如果我们只关心、使用一个指针的值，则可以采用值传递，但是此时的值是指针本身，但它依然是值传递；而如果我们要修改该指针的值，则需要地址传递，需要把该指针的地址传递给形参，而我们则可以通过修改形参的值改变整个指针的指向，这里的指针的地址便是二级指针。

那为什么数据结构中有的函数传递的是一级指针即头指针，有的时候是二级指针即头指针的地址呢？

这个主要的原因在于看是否需要更改头指针的值，那问题又来了，什么时候需要更改头指针的只能？

答案有以下几种：

a. 无头链表采用头插法、头删法时，使用移动头指针；

b. 整个链表的创建、删除过程可以通过移动头指针来简单的实现(此时不区分由头无头链表)

目前只想到了两种。当然有头链表的删除可以不采用这种方式，但是得维持一个pre指针，这个被大婶Linus在coolshell上吐槽了一下。。。我也是偶尔看到这篇文章才涨的姿势(原文链接：https://coolshell.cn/articles/8990.html)。简单记录个人临时的理解

void remove_if(node ** head, remove_fn rm)
{
    for (node** curr = head; *curr; )
    {
        node * entry = *curr;
        if (rm(entry))          /*如果不是头结点，则进行删除*/
        {
            *curr = entry->next;
            free(entry);
        }
        else                    /*如果为头节点，则cur指向头节点的指针域*/
            curr = &entry->next;/*不删除头节点*/
    }
}

/*
*  上述代码的执行效果是：二级指针cur指向头结点的指针域，每次判断如果不是头结点，则更改头结点指针域的值，即将头结点的指针通过entry指向下一个节点，然后释放entry节点。再次循环时，将头结点指针域的值给entry，即entry指向下一个节点，如此循环... ... 
*
**/

线性表两种存储结构叙述完毕。

附上自己画的图：

附图一：

数据结构（一）：线性表的顺序存储和链式存储