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

#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;
    }
}
}