1.（4）数据结构之链表的操作，判空，求长度，排序

本人坚持更新C语言，数据结构，操作系统，前端知识，可以收藏＋关注随时了解😜😜😜

上一篇文章我们讲到了链表的创建和遍历，这一篇我们来实现链表的判空，求长度，以及排序

在实现之前，我们还是需要知道一个重要的知识

确定一条链表我们只需要知道它的头节点

我们先定义好结构体

typedef struct Node
{
    int data;           //数据域
    struct Node *pNext; //指针域
} NODE, *PNODE;         // NODE等于struct Node,PNODE等价于struct Node*

1.链表的长度

首先我们知道这个函数需要返回一个整型变量，也就是它的长度，其次我们要知道这条链表的头节点，来确定出整条链表，最后我们要知道，链表的长度，不包括头结点，链表的最后一个结点指针域为NULL。

在这个链表中，除了头节点意外，有3个结点，所以长度为3，

我们的思路是，定义一个指针，指向头节点

前三个的节点的指针域不为空，头结点的指针域保存第一个节点的地址，第二个结点保存着第三个节点的地址......根据这个思想我们写出代码

int length_list(PNODE pHead)
{
    PNODE p = pHead; //定义指向头结点的指针
    int count = 0;   //计数
    while (p->pNext != NULL)
    {
        count++;
        p = p->pNext;
    }
    return count;
}

** 每记一次数，通过p->pNext让指针后移，知道p->pNext等于NULL的时候（到了最后一个结点），停止循环，此时的count为链表的长度**

2.链表的判空

链表的判空十分简单，如果头节点的指针域为NULL，说明这个链表只存在头节点，链表为空

反之如果不NULL，则链表不空

bool empty(PNODE pHead)
{
    if (pHead->pNext == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

3.链表的排序

我们在之前的学习中，学习过一些排序方式，有选择排序，冒泡排序这两种基本的排序，在链表的排序中，我们也可以使用这样的思想。

冒泡排序就是比较数组中相邻两个数的值，如果前面的数大，就交换两个数的值，这样一次循环下来，保证最后一个数是最大的

但是链表不能通过索引值去比较大小，因此我们需要定义两个指针，这两个指针是相邻的位置

pfront开始指向首节点，pbehind代表pfront后面的值，每比较一次，就将指针们向后移动一位

void sort_list(PNODE pHead)
{
    int i, j, temp;
    int len = length_list(pHead); //传入链表的长度
    PNODE pfront, qbehind;
    for (i = 0, pfront = pHead->pNext; i < len - 1; i++, pfront = pfront->pNext)
    // pfront先指向首节点，qbehind为pfront后面的结点
    {
        for (j = i + 1, qbehind = pfront->pNext; j < len; j++, qbehind = qbehind->pNext)

        {
            if (pfront->data > qbehind->data) //并没有交换指针域，只是交换了数据域
            {
                temp = pfront->data;
                pfront->data = qbehind->data;
                qbehind->data = temp;
            }
        }
    }
}

** 我们需要清楚的是，排序仅仅交换的是节点的数据域的值，而没有交换指针域**