关于链表

链表

---

数组作为基本的数据结构被广泛使用在各种程序中，其查找十分方便，使用也十分简单。但要对其进行插入和删除操作，花费却十分昂贵。比如，对一个长度为n的数组在k位置进行插入操作，首先要把k到n-1位置的数据整体后移，而删除k则要把k+1到n-1 的位置整体前移。为了避免插入和删除的开销，我们可以使用不连续存储的链表。

链表的存储形式如下图所示：

对于链表的插入和删除操作我们可以直接修改next指针，对链表元素进行调整

删除元素

插入元素

程序实现

---

为了编程方便我们在链表开头留出一个不使用的头节点

下面列出链表的声明类型:

typedef struct{

}item;                      //链表的元素类型,由用户自定义

typedef struct node {
    item elem;              //节点的数据域
    struct node * next;                 //节点的指针域
}node;

typedef struct {
    node * head;            //头节点指针
    //可保存其它信息,如链表长度,指向链表末的指针等
}list;

/*
*创建一个链表
*并返回指向链表的指针
*如果内存申请失败，则返回空指针
*/
list * listcreate();

/*
*返回一个bool值
*如果链表为空，则返回true
*反之，则返回false
*/
bool listisempty(list * pl);

/*
*返回链表的大小
*返回值为一个unsigned int
*/
unsigned listsize(list * pl);

/*
*返回第一个使pfun返回true的节点
*/
node * listfindif(list * pl, bool(*pfun)(const item *));

/*
*返回第一个使pfun返回true节点的前一个节点
*/
node * listfindpreviousif(list * pl, bool(*pfun)(const item *));

/*
*将pi指向的数据插入链表
*插入的数据位于链表开始
*返回一个指向新节点的指针
*/
node * listpushfront(list * pl, const item * pi);

/*
*将pi指向的数据插入链表
*插入的数据位于pn指向的节点之后
*返回一个指向新节点的指针
*/
node * listinsertafter(list * pl, node * pn, const item * pi);

/*
*删除pl指向链表的第一个元素
*元素的值赋给pi指向的元素
*返回一个指向被删除元素的下一个节点的指针
*/
node * listpopfront(list * pl);

/*
*删除pn指向节点的下一个元素
*元素的值赋给pi指向的元素
*返回一个指向被删除元素的下一个节点的指针
*/
node * listeraseafter(list * pl, node * pn);

/*
*遍历链表，使链表中每一个元素都被pfun作用
*/
void listtraverse(list * pl, void(*pfun)(item *));

/*
*清空链表，使链表的size为0
*/
void listclear(list * pl);

/*
*销毁链表，并把pl赋为null
*/
void listdestroy(list ** pl);

链表的创建

---

首先我们创建一个空表、使用malloc申请一个list空间和一个头节点。由于元素数量不确定，所以我们在需要时再申请更多的空间。

list * listcreate()
{
    list * new_list = malloc(sizeof(list));               //获得链表所需空间

    if (new_list == null)
    {
        fprintf(stderr, "out of memory in function: create_list()!\n");
        return null;
    }
    
    new_list->head = make_node(null, null);        //获得一个头节点
    if (new_list->head == null)
    {
        fprintf(stderr, "out of memory in function: create_list()!\n");
        free(new_list);
        return null;
    }

    return new_list;
}

在这里使用了一个辅助函数make_node()，make_node接受一个item指针和一个node指针，把node指针作为其申请节点的next指针，如果item指针不为null的话，则将pi指向的值赋给申请的节点，其定义如下

node * make_node(const item * pi, node * pn)
{
    node * new_node = malloc(sizeof(node));

    if(new_node!=null)
    {
        if (pi != null)
            new_node->elem = *pi;
        new_node->next = pn;
    }

    return new_node;
}

现在的状态

链表的查找

---

对链表进行简单遍历，第一次使pfun返回true时返回节点

node * listfindif(list * pl, bool(*pfun)(const item *))
{
    node * temp = pl->head;

    while (temp != null && !pfun(&temp->elem))
        temp = temp->next;

    return temp;
}

链表的删除

---

如果我们要删除某个节点，我们通过调用listfindpreviousif找到符合条件节点的前一个节点

node * listeraseafter(list * pl, node * pn)
{
    node * temp = pn->next;         //删除pn->next指向的节点

    pn->next = temp->next;
    destroy_node(temp);           //自定义函数，释放temp的空间，行为与free相似

    return pn->next;
}

listfindpreviousif类似于listfindif只不过返回的是前一个节点

链表的插入

---

node * listinsertafter(list * pl, node * pn, const item * pi)
{
    node * new_node = make_node(pi, pn->next);

    if (new_node == null)
    {
        fprintf(stderr, "out of memory in function: list_push_front()!\n");
        return null;
    }

    pn->next = new_node;

    return new_node;
}

其他操作

判断链表为空

---

要判断链表是否为空，只需要判断链表头节点的next指针是否为null就行了

bool listisempty(list * pl)
{
    return pl->head->next == null;
}

清空链表

---

void listclear(list * pl)
{
    node * temp = pl->head->next;

    while (temp != null)
    {
        pl->head->next = temp->next;
        destroy_node(temp);
        temp = pl->head->next;
    }
}