【2023王道数据结构】【排序】通过C++实现插入排序（单链表插入排序）C、C++完整实现（可直接运行）

~~~笔锋至此又怎能平淡而终，故事开始便不承认普通✌✌✌

✌ 题目及题解持续更新中
【2023王道数据结构目录】课后算法设计题C、C++代码实现完整版大全

题目： 通过C++实现插入排序（单链表插入排序）

运行截图：

代码实现：

#include 
#include 
using namespace std;

typedef struct LNode
{
    int data;
    struct LNode *next;
    int length = 0;
} LNode, *LinkList;

// 尾插法
void TailInsert(LinkList &L)
{
    int val = 0;
    LNode *r = L;
    while (cin >> val)
    {
        LNode *s = new LNode;
        s->data = val;
        r->next = s;
        r = s;
        r->next = NULL;
        L->length++;

        if (cin.get() == 'n')
        {
            break;
        }
    }
}

// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next;
    while (p)
    {
        cout << p->data << 't';
        p = p->next;
    }
    cout << endl;
}

void Insert_Sort(LinkList &L)
{
    

    LNode *cur, *pre, *p, *r; // 定义指针变量，分别指向待插入、找到待插入前驱、工作指针、排好序尾指针
    r = L->next;              // 将尾指针指向第一个元素，默认第一个元素已经排好序
    cur = L->next->next;      // 从第二个元素开始

    // 只要待插入不为空，没到表尾
    while (cur)
    {
        pre = L, p = L->next; // 分别指向头指针、首元

        // 只有当前值小于尾指针的值进行
        if (cur->data < r->data)
        {
            // p位置为大于cur的位置，pre是其前驱，待插入元素插入在p和pre之间
            while (p != NULL && p != cur && p->data <= cur->data)
            {
                pre = p;
                p = p->next;
            }

            // 有序表尾指针链接待插入元素后面指针
            r->next = cur->next;
            // 将cur插入到pre和p之间
            cur->next = p;
            pre->next = cur;
            // 指针后移
            cur = p->next;
            r = p;
        }

        // 如果大于，直接将尾指针和当前指针后移一位
        else
        {
            r = cur;
            cur = cur->next;
        }
    }
}

int main()
{
    LinkList L = new LNode;
    TailInsert(L);
    cout << "排序前:" << endl;
    Print(L);
    Insert_Sort(L);
    cout << "排序后:" << endl;
    Print(L);
}