无头结点的单链表直接插入排序

忘是亡心i 2023-07-25 06:19 12阅读 0赞

# 1、问题描述 #

插入排序是把一个记录插入到已排的有序序列中，使得这个序列在插入该记录后仍然保持有序。插入排序中较为简单较为简单的一种就是直接插入排序，其插入的位置的确定方法是将待插入的记录与有序区中的各记录自右向左依次比较其关建字值的大小，本实例要求使用直接插入排序由小到大进行排序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70][]

# 2、程序代码 #

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    /*
    
    *csdn学院
    
    *目的：让代码见证成长(作为一个初学的菜鸟，如
    
    *大家有发现错误，欢迎指正！)
    
    *运行软件：CodeBlocks
    
    *作者:小臣小仁
    
    *完成日期:2020年4月21日
    
    */
    typedef struct NODE//创建结构体
    {
        int data;//数据域
        struct NODE *next;//指针域
    }Node;
    
    void traverse(Node *Head)//遍历链表
    {
        Node *p = Head;//移动指针指向头指针
        printf("链表为:");
        while(p != NULL)//当指针单链表未到尾部时，为真
        {
            printf("%5d",p->data);//取出数据值
            p=p->next;//指向下一个节点
        }
        printf("\n");
        return;
    }
    void free_Link(Node *Head)//释放链表
    {
        Node *pointer = NULL;//将替换头结点的设为空
        while(Head != NULL)//头结点不为空时为真
        {
            pointer = Head->next;//pointer指向头结点的下一个结点
            free(Head);//释放头结点
            Head = pointer;//将头结点指向之前pointer指向的结点
        }
        printf("\n链表已释放\n");
        return;
    }
    
    Node *insert_sort(Node *Head)//没有头结点的直接插入排序
    {
        Node *p1=Head,*p2=p1->next;//p1和p2为向下移动指针
        Node *q=NULL;//q为从头指针移动的指针
        p1->next=NULL;//从未排序的链表处断开
        p1=p2;//p1指向断开后未排序的第一个结点，即p2
        while(p1!=NULL)//链表不为空，为真
        {
            p2=p1->next;//p2指向p1的下一个结点
            q=Head;//q移动到头结点
            if(Head->data > p1->data)//当待排序的数值小于头结点时后为真
            {
                p1->next=Head;//将小于头结点的结点设为头结点
                Head = p1;//头结点重新指向第一个单链表第一个结点
            }
            else
            {
                while(q->next!=NULL&&q->next->data < p1->data)//当单链表不为空且小于断开链表部分的待插入的前一个结点，
                    q=q->next;//向下移动
                p1->next=q->next;//插入结点操作
                q->next=p1;//插入结点操作
            }
            p1=p2;//p1指向p2,即断开的待插入单链表的第一个结点
        }
        return Head;
    }
    void *createLinkList(Node *Head,int *d)//创建链表
    {
        Node *pointer = NULL,*Last=NULL;//pointer为申请分配的地址空间，Last为尾指针
        int i;
        for(i=0;i<10;i++)
        {
            pointer=(Node *)malloc(sizeof(Node));//生成新结点
            pointer->data=d[i];//赋值
            pointer->next=NULL;//申请的空间下一个指向NULL
            if(Head==NULL)//当头结点为空时
                Head = pointer;//头结点指向动态申请的地址
            else
                Last->next = pointer;//尾指针后面插入动态申请的地址
            Last = pointer;//尾指针指向单链表末尾
        }
        return Head;
    }
    int main()
    {
        Node *head=NULL;
        int b[10]={25,12,36,45,2,9,39,22,98,37};
        head = createLinkList(head,b);//创造链表
        traverse(head);//遍历链表
        head=insert_sort(head);//直接插入排序
        printf("\n直接插入排序:\n");
        traverse(head);//遍历链表
        free_Link(head);//销毁链表
        return 0;
    }

# 3、输出结果 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70 1][]

心得体会

在编写程序的时候，无头结点的单链表直接插入排序，这可以作为c语言初学者练手的小程序，当然程序中多多少少有错误，望指正留言！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70]: /images/20230528/0979cba5ca7e48638cda8133245f1664.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70 1]: /images/20230528/33b07ea2442f4378bcf8ce54adfb0fbc.png