单向链表增删改查排序操作

在讨论链表这个概念之前，我觉得有必要说一下为什么会有链表？作为一个新手如果不明白这个问题上来就盲目的写链表的代码没有任何意义，就算你现在背下来了，早晚也会忘掉。

链表属于一种数据结构，数据结构目的就是用来以固定的结构储存数据，数组也是一种数据结构，只不过他在内存中表现的样式是连续的一段内存，中间不能插入其他数据，一旦插入其他数据则数组就无效了。而链表则是另外一种储存数据的格式，他可以让我们使用一个结构体，表示第一个数据和第二个数据之间的关联关系，比如第一个数据在内存的某个位置，同时这个数据的另外一个成员表明了下一个数据在内存中的位置，这些位置可能是不相连的。但通过这个表明了下一个数据位置的指针，我们就可以将数据一和数据二连接起来，这样连接起来的数据我们就称为链表了。

链表一般用来储存自定义的一些相对较大的数据，它可以在堆上自己分配管理数据所需的内存。随之而来的操作链表时就会有各种内存申请和释放的操作，稍不留心就由可能造成内存泄漏。

我们上面谈到的是单向链表，链表也可以做成循环的，也就是最后一个数据指向第一个数据的位置，这样整个链表中的数据就练成一个环形状了。只要找到其中一个数据，就能找到整个链表中的所有数据。而这样带来的问题就是，分不清哪里是链表头了，所以一般情况下程序开发人员都会创建一个空的链表节点，表示这个节点是链表头。

除了单向链表、环形链表，还有双向链表，也就是一个链表中的节点不仅仅包含存储的数据和下一个数据的位置指针，还包含了上一个数据的位置指针。这样只要找到其中一个数据，就可以从两个分别指向了上一个数据或下一个数据的指针来遍历你所需要的内容了。下面我们就来看一下链表的实现。

单向链表非常详细的增删改查操作方法，每一步都有非常详细的文字提示。特别要记录的是链表的排序，其中包含交换数据和交换指针的方法。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct node
{
    int data;
    struct node* next;
}Node;

// 创建链表
Node* createList();
// 给链表插入数据，头插法
void insertNode(Node* head, int data);
// 显示所有节点数据
void displayList(Node* head);
// 查找一个包含某数据的节点，返回节点指针
Node* findNode(Node* head, int data);
// 根据数据删除包含该数据的节点
void deleteNode(Node* head, Node* pFind);
// 获取链表长度
int getListLen(Node* head);
// 冒泡排序，交换数据
void popSortList(Node* head, int nLen);
// 冒泡排序，交换指针
void popSortForPointer(Node* head, int nLen);

int main(int argc, char* argv[])
{
    Node* head;
    // 创建链表
    head = createList();
    // 打印链表数据
    displayList(head);
    // 在链表中查找数据域为5的节点
    Node* pFind = findNode(head, 5);
    if (NULL != pFind)
    {
        // 如果找到包含5的节点，则打印并删除该节点
        printf("delete pFind->data = %d\n", pFind->data);
        deleteNode(head, pFind);
        // 重新打印删除后的链表信息
        displayList(head);
    }
    else
    {
        // 没有找到提示信息
        printf("not in the list !\n");
    }

    // 求链表有效节点个数
    int nLen = getListLen(head);
    printf("the list length is : %d\n", nLen);
    // 冒泡排序交换指针
    popSortForPointer(head, nLen);
    // 冒泡排序交换数据
    //popSortList(head, nLen);
    // 打印链表
    displayList(head);

}

Node* createList()
{
    Node* head = (Node*)malloc(sizeof(Node));
    head->next = NULL;

    srand(time(NULL));
    for (int i = 0; i < 10; i++)
    {
        // 插入随机数据
        insertNode(head, rand() % 10);
    }

    return head;
}

// 头插法
void insertNode(Node* head, int data)
{
    // 创建新的节点
    Node* cur = (Node*)malloc(sizeof(Node));
    // 给新的节点数据域赋值
    cur->data = data;
    // 让新的节点先有所指向 
    cur->next = head->next;
    // 让头节点与新节点相连
    head->next = cur;
}

void displayList(Node* head)
{
    // 掉过头节点，因为头节点数据无效
    head = head->next;
    // 如果head不为NULL，那么一直循环
    while (head)
    {
        // 打印data数据
        printf("%d ", head->data);
        // head向后移动
        head = head->next;
    }
    // 打印回车
    putchar(10);
}

Node* findNode(Node* head, int nFind)
{
    // 跳过头节点
    head = head->next;
    // 如果head不为NULL，那么一直循环
    while (head)
    {
        // 如果data值 == 传递进来的数值
        if (head->data == nFind)
            // 返回这个节点的指针
            return head;
        // 没找到就一直向后移动
        head = head->next;
    }
    // 到这里证明没有找到符合的节点，反回NULL
    return NULL;
}

void deleteNode(Node* head, Node* pFind)
{
    // 循环遍历链表查找pFind的上一个节点
    while (head->next != pFind)
        head = head->next;
    // 找到后让已经移动到pFind上一个节点的head->next = pFind->next
    head->next = pFind->next;
    // 销毁pFind
    free(pFind);
    pFind = NULL;
}

int getListLen(Node* head)
{
    // 跳过头节点
    head = head->next;
    int nLen = 0;
    // 如果head不为NULL，那么一直循环
    while (head)
    {
        // 计数器+1
        nLen++;
        // 向后移动head
        head = head->next;
    }
    // 返回链表长度
    return nLen;
}

void popSortList(Node* head, int nLen)
{
    Node* pHead;
    for (int i = 0; i < nLen - 1; i++)
    {
        // 让临时变量每次都指向头节点，这样才能一次跟后面的相比
        pHead = head->next;
        for (int j = 0; j < nLen - 1 - i; j++)
        {
            if (pHead->data > pHead->next->data)
            {
                // 位或交换数据
                pHead->data = pHead->data ^ pHead->next->data;
                pHead->next->data = pHead->data ^ pHead->next->data;
                pHead->data = pHead->data ^ pHead->next->data;
            }
            // 向后移动指针，继续比较下一个数据
            pHead = pHead->next;
        }
    }
}

void popSortForPointer(Node* head, int nLen)
{
    Node* p;
    Node* q;
    Node* pre;
    Node* tmp;
    for (int i = 0; i < nLen - 1; i++)
    {
        // pre一直跟随着是p节点的上一个节点
        pre = head;
        // p一直是pre的下一个节点
        p = pre->next;
        // q一直是p的下一个节点
        q = p->next;
        for (int j = 0; j < nLen - 1 - i; j++)
        {
            // 判断p的data是否大于q的data
            if (p->data > q->data)
            {
                // 让pre的next等于q的当前位置
                pre->next = q;
                // 让p的next指向q的next
                p->next = q->next;
                // 让q的next指向p，至此指针交换完毕
                q->next = p;
                
                // 如果要继续下次循环，必须恢复p和q的位置为进入循环前保持的位置
                tmp = p;
                p = q;
                q = tmp;
            }
            // 所有指针向后移动一次
            pre = p;
            p = q;
            q = q->next;
        }
    }
}