链表的部分函数实现（二）

接上文，依旧是链表的实现。

按照前面说的，链表的整表创建可以当作链表长度为0的时候将数组转化为链表的特殊情况，即这个可以分为两步：

插入n个节点。
遍历链表赋值。

所以我们需要先完成插入指定数量的节点这个函数。但是前文也说了，插入一串链表，本质上是将一串链表拼接到另一串链表上。所以插入n个节点也可以分解成两步：

创建一个长度为n的链表。
将它拼接到另一个链表上。

这样就要思考了，如果要用最省的步骤来写，是应该先写创建链表还是应该先写插入链表

创建一段空链表

整表创建

好像以前在书上看见过有这么个东西，但是从来没有用过，我也不记得具体是个什么了，也懒得再翻书了，要是再对着书上抄就没意思了。

我从字面意思上理解，应该是用数组创建整个链表，所以原型应该是这样：

1	void LinkListCreateFromArray(LinkList l, void array, size_t num, size_t size);

num为数组的元素个数，size为每个元素的大小。

既然叫做整表创建，要是使用插入函数，感觉就没有突出一个整字，而且我们每次插入时都会让长度加一，并且让两个节点的前继后继重复赋值，即每插入一个节点就会重复2次赋值和一次自增，所以整表创建可能节省了3n次操作。这个有点麻烦，就直接贴代码了：

void LinkListCreateFromArray(LinkList *l, void *array, size_t num, size_t size)
{
    LinkList a = (LinkList)malloc(sizeof(Node));
    Node **A = (Node **)malloc(num * sizeof(Node *));
    char *p = (char *)array;
    A[0] = (Node *)malloc(sizeof(Node));
    A[0]->pre = a;
    A[0]->data = malloc(size);
    memcpy(A[0]->data, p, size);
    p += size;
    for (size_t i = 1, j = 0; i < num; i++, j++)
    {
        A[i] = (Node *)malloc(sizeof(Node));
        A[j]->next = A[i];
        A[i]->pre = A[j];
        A[i]->data = malloc(size);
        memcpy(A[i]->data, p, size);
        p += size;
    }
    A[num - 1]->next = a;
    a->next = A[0];
    a->pre = A[num - 1];
    a->data = malloc(sizeof(LinkListHeader));
    memset(a->data, 0, sizeof(LinkListHeader));
    ((LinkListHeader *)a->data)->length = num;
    *l = a;
}

p是一个char类型的指针，因为char的大小为1，p指向数组的首地址，通过对p加上size可以跳到下一个数组元素的位置。

通过for循环来连接前后两个节点，就能避免前继后继重复赋值，然后对第一个数据节点和尾节点进行特殊处理，连接头节点，并在最后直接将元素个数赋与长度，即可完成整表创建。

这里之前还犯了一个错误，之前我是用malloc一次创建了整个A数组，然后后面无法用free释放单个节点，找了好久才知道是这个问题，于是就改成了在for循环里面一个个malloc，这样删除的时候也可以一个个free。

链表的清空

清空整个链表也算是一个常用操作，虽然我从来没用过，但是有句话叫可以不用，不能没有。跟整表创建相似，如果一个个erase那也会重复2n次赋值和n次自减，也可以优化一下，那就是直接遍历来删除节点，代码如下：

void LinkListClear(LinkList l)
{
    Node *p = l->next;
    while(p!=l)
    {
        free(p->data);
        p = p->next;
        free(p->pre);
    }
    l->next = l;
    l-pre = l;
    ((LinkListHeader *)l->data)->length = 0;
}

链表的销毁

清空链表之后链表就只剩下一个头节点了，只需要再释放头节点，那就是链表的销毁了，释放头节点之后，根据规范应该将指针指向NULL，所以参数用LinkList *，释放后将l置为NULL，代码如下：

void LinkListDestroy(LinkList *l)
{
    LinkListClear(*l);
    free(LinkListGetHeaderInfo(*l));
    free((*l)->data);
    free(*l);
    *l=NULL;
}

将链表转化为数组

接上一节，我们还可以写个用链表生成数组的函数，大概思路就是，返回一个void *的数组，通过参数返回数组长度，代码如下：

void **LinkListToArray(LinkList l, size_t *n)
{
    size_t len = LinkListGetLength(l);
    size_t size = LinkListGetSize(l);
    void **data = (void **)malloc(len*size);
    char *p = *data;
    LinkListFor(q, LinkListGetFront(l))
    {
        memcpy(p, NodeGetData(q), size);
        p += size;
    }
    *n = len;
    return data;
}

这个是拷贝链表生成的数组，而且不管怎么样，对数组的修改也不会影响到原本的链表的数据，所以我们或许还会需要一个函数来将数组转换回链表。

将数组转化为链表

上面才写有一个整表创建，这里又写个将数组转化为链表，可能你们会觉得我想水字数，或者说为什么不直接用上面的。首先说明，我也是个懒人，如果上面的可以用我也不想重新写一个新的东西，上面那个只适用于空链表来转化，我们这个链表本身带有节点，如果这样用的话会直接让一圈的节点从世界上消失，然后又出现一圈节点取代了它们的位置，让人无法察觉到它们已经不是之前的那些节点了（出现了，传说中的沼泽人问题，只不过内存泄漏）。

首先，我们的链表本身带有节点，本身有长度，不需要全部创建，所以只需要比较链表的长度和数组的长度，会有3种情况，大于小于和等于，如果长度刚好相等，我们就只需要遍历节点然后赋值，如果长度不一样，那就是多的删除，少的补齐，然后赋值。

void LinkListCreateFromArray(LinkList *l, void *array, size_t num, size_t size)
{
    if(l == null)
    {
        LinkListCreateFromArray(l, array, num, size);
        return;
    }
    if(size != LinkListGetSize(l))
    {
        return;
    }
    size_t len = LinkListGetLength(l);
    if(num > len)
    {
        size_t n = num -len;
        Node **A = (Node **)malloc(n * sizeof(Node *));
        A[0] = (Node *)malloc(sizeof(Node));
        A[0]->pre = LinkListGetTail(l);
        A[0]->data = malloc(size);
        for (size_t i = 1, j = 0; i < n; i++, j++)
        {
            A[i] = (Node *)malloc(sizeof(Node));
            A[j]->next = A[i];
            A[i]->pre = A[j];
            A[i]->data = malloc(size);
        }
        A[num - 1]->next = l;
        l->pre->next = A[0];
        l->pre = A[num - 1];
        ((LinkListHeader *)a->data)->length = num;
    }
    
    LinkList a = (LinkList)malloc(sizeof(Node));
    
    char *p = (char *)array;
    A[0] = (Node *)malloc(sizeof(Node));
    A[0]->pre = a;
    A[0]->data = malloc(size);
    memcpy(A[0]->data, p, size);
    p += size;
    for (size_t i = 1, j = 0; i < num; i++, j++)
    {
        A[i] = (Node *)malloc(sizeof(Node));
        A[j]->next = A[i];
        A[i]->pre = A[j];
        A[i]->data = malloc(size);
        memcpy(A[i]->data, p, size);
        p += size;
    }
    A[num - 1]->next = a;
    a->next = A[0];
    a->pre = A[num - 1];
    a->data = malloc(sizeof(LinkListHeader));
    memset(a->data, 0, sizeof(LinkListHeader));
    
    *l = a;
}

文章写到这，我才发现我漏了两个重要的东西，删除某一区间的节点和指定位置插入一串节点，链表的整表创建应该也只是将数组转化为链表的一个特殊情况，即链表长度为0的情况。以及再一想，还需要链表的复制和链表的拼接，插入一串节点本质也是链表的拼接。