C语言链表中数组实现数据选择排序，升序、降序功能主要难点

痛定思痛。 2022-02-01 09:23 116阅读 0赞

链表排序讲解：

head指针指向链表的头结点，是找到整个链表的唯一依据，如果head指针丢失，整个链表就找不到了。

head存储的是第一个节点的地址，head->next存储的是第二个节点的地址； 任意一个节点p的地址，只能通过它前一个节点的next来求得。

单向链表的选择排序图示： ---->\[1\]---->\[3\]---->\[2\]...---->\[n\]---->\[NULL\]（原链表）

head 1->next 3->next 2->next n->next

选择排序(Selection sort)是一种简单直观的排序算法。

首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

动画演示：http://www.nowamagic.net/librarys/veda/detail/1849

选择排序

定义的结构体

struct student
    {  
    char ID[11]; //学生学号
    char name[20];  //学生姓名
     
    struct student *next;  //next 指针 指向 struct  student 类型的变量
    }stu;

里面的变量均为数组

那怎么实现结构体中定义（有）数组变量，链表遍历结构体，按照结构体里面变量来排序呢？

**其中对数组比较大小、比较两个字符串的大小来使用的函数是： strcmp() 也就是string compare字符串比较。**

**对数组之间的赋值函数是 strcpy() ==="string copy"**

升序：

/***************
    
    函数功能:
    升序排列出勤学生
    返回:指向链表表头的指针
    
    /***************/
    
    
    struct student *sort_message_order(struct student* head) //升序  按照ID顺序
    
    {   
        struct student *Back,*pointer; //p指针指向新的节点 back指针指向链表的尾节点
        struct student  temp; // 定义结构体student别名,typedef也可以定义的结构体别名
        Back=head->next; 
        pointer=head->next; //跳过头结点 指向下一个节点 头结点中没有学生信息 
        while(Back!=NULL) //如果尾节点不为空 就一直遍历下去
        {
            while(pointer->next!=NULL) //如果指向新开辟的结点不为空就一直遍历下去
            {
                pointer=pointer->next; //指向下一个新开辟的结点
                if ( strcmp( Back->ID,pointer->ID)>0  )  //如果back->ID大于pointer->ID就返回大于0的值；后面大于前面的 往后放
                {
                    strcpy(temp.ID,Back->ID);
                    strcpy(temp.name,Back->name);  //把尾节点值赋值给临时temp结构体变量
                    
                    
                    strcpy( Back->ID,pointer->ID);
                    strcpy(Back->name,pointer->name); //把指向的新节点 跟尾节点交换 位置
                    
                    
                    strcpy(pointer->ID,temp.ID);
                    strcpy(pointer->name,temp.name);//将临时temp结构体变量赋值给指向的结构体变量
                    
                }
            }
            Back=Back->next; //指向下一个尾节点
            pointer=Back;  //指向尾节点
        }
        return head;  //返回头结点
        
    }

降序：

/***************
    
    函数功能:
    降序排列出勤学生
    返回:指向链表表头的指针
    
    /***************/
    
    struct student * sort_message_Desc(struct student* head)//Descending降序
    {
        struct student *Back,*pointer; //p总是指向新申请的结点  back总是指向链表的尾节点
        struct student  temp;
        Back=head->next;
        pointer=head->next;//跳过头结点，头结点中没有学生信息
        while(Back!=NULL)
        {
            while(pointer->next!=NULL)
            {
                pointer=pointer->next;
    
                if ( strcmp( Back->ID,pointer->ID)<0  ) // back->ID小于pointer->ID返回负数 把最小的 往后放  降序
                {
                    strcpy(temp.ID,Back->ID);
                    strcpy(temp.name,Back->name);     //把尾节点值赋值给临时temp结构体变量
                    
                    strcpy( Back->ID,pointer->ID);
                    strcpy(Back->name,pointer->name); //指向的新节点 跟尾节点交换 位置
                                
                    strcpy(pointer->ID,temp.ID);
                    strcpy(pointer->name,temp.name);  //将临时temp结构体变量赋值给指向的结构体变量
                }
            }
            Back=Back->next; //指向下一个尾节点
            pointer=Back;   //指向尾节点
        }
        return head;  //返回头结点
    }

输出打印链表内容：

void Print_List(struct student *head)
    {
        struct student* pointer;
        pointer=head->next; //跳过无数据的头结点
        while(pointer!=NULL)
            {  
                printf(" ",pointer->ID);
                printf(" ",pointer->name);
                 
                pointer=pointer->next;//指向下一个节点
            }     
    }