论坛 › C\C++交流 › 大佬帮我看看单链表排序

青衫烟雨客 发表于 2021-10-30 09:28:15

大佬帮我看看单链表排序

问题是输入学生成绩按大到小输入，大的打印在最上面。
我的思路按照不同情况分析：

1，当list是空的，把p=list。
2，当list不是空的，p最小，头指针先指向p，p指向原来的信息域
3，当list不是空的，p最大，先找到尾部的current，然后指向p
4，当list不是空的，p要插入中间，先找到比p大的第一个数为current，上一个数位previous，previous指向怕，p指向current

运行时第二种情况排序打印小的在上面
运行第三种输入两个数据后就自动结束了


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

struct Sorce
{
    int chinese;
    int math;
    int english;
};

struct Student
{
    int num;
    char name;
    struct Sorce sorce;
    float average;
    struct Student*next;
};

void getInput(struct Student*student);
void getInput(struct Student*student)
{
    printf("请输入学号");
    scanf("%d",&student->num);
    printf("请输入名字");
    scanf("%s",student->name);
    printf("请输入语文数学英语成绩");
    scanf("%d %d %d",&student->sorce.chinese,&student->sorce.math,&student->sorce.english);
    student->average=(student->sorce.chinese+student->sorce.math+student->sorce.english)/3;
}

void addStudent(struct Student**list);
void addStudent(struct Student**list)
{
    struct Student*previous;
    struct Student*current;
    struct Student*p;
    struct Student*temp;
    current=*list;
    previous=NULL;
    p=(struct Student*)malloc(sizeof(struct Student));
    if(p==NULL)
    {
      printf("内存分配失败\n");
      exit(1);
    }
    getInput(p);
    while(current!=NULL && (current->average)<(p->average))
    {
      previous=current;
      current=current->next;                  
    }
    if(current==NULL && previous==NULL)
    {
      *list=p;
    }
    else if(current!=NULL && previous==NULL)
    {
      temp=*list;
      *list=p;
      p->next=temp;
    }
    else if(current==NULL && previous!=NULL)
    {
      previous->next=p;
      p->next=NULL;
    }
    else
    {
      previous->next=p;
      p->next=current;
    }
}

void printStu(struct Student*list);
void printStu(struct Student*list)
{
    struct Student*current;
    current=list;
    while(current!=NULL)
    {
      printf("%d %s %d %d %d\n",current->num,current->name,current->sorce.chinese,current->sorce.math,current->sorce.english);
      current=current->next;
    }
    putchar('\n');
    free(current);
}
int main()
{
    struct Student*list=NULL;
    int ch;
    while(1)
    {
      printf("是否录入学生信息(Y/N)");
      do
      {
            ch=getchar();
      }
      while(ch!='Y' && ch!='N');
            if(ch=='Y')
      {
            addStudent(&list);
      }
      else
      {
                break;
      }
    }
    printStu(list);
    return 0;
}

青衫烟雨客 发表于 2021-10-30 09:29:16

本帖最后由 青衫烟雨客 于 2021-10-30 21:52 编辑

这道题题目是按照学号输入学生成绩，成绩不同，打印从成绩高到低，高的打印在最上面

第四种是previous指向p，p指向current

jackz007 发表于 2021-10-30 10:16:38

本帖最后由 jackz007 于 2021-10-30 19:39 编辑

      改写这个函数
void addStudent(struct Student**list)
【正序】
void addStudent(struct Student**list)
{
    struct Student * p , * p1 , * p2                  ;
    p=(struct Student*)malloc(sizeof(struct Student)) ;
    if(p==NULL)
    {
      printf("内存分配失败\n");
      exit(1);
    }
    getInput(p);
    for(p1 = p2 = * list ; p1 && p1 -> average < p -> average ; p2 = p1 , p1 = p2 -> next) ;
    if(p2) {
      if(p1 == * list) {
            p -> next = p2   ; // 新节点位于链头
            * list = p         ;
      } else {
            p -> next = p1   ; // 新节点位于链中、链尾
            p2 -> next = p   ;
      }
    } else {
      p -> next = NULL       ; // 新建链表
      * list = p             ;
    }
}
【逆序】：
void addStudent(struct Student**list)
{
    struct Student * p , * p1 , * p2                  ;
    p=(struct Student*)malloc(sizeof(struct Student)) ;
    if(p==NULL)
    {
      printf("内存分配失败\n");
      exit(1);
    }
    getInput(p);
    for(p1 = p2 = * list ; p1 && p1 -> average > p -> average ; p2 = p1 , p1 = p2 -> next) ;
    if(p2) {
      if(p1 == * list) {
            p -> next = p2   ; // 新节点位于链头
             * list = p         ;
      } else {
            p -> next = p1   ; // 新节点位于链中、链尾
            p2 -> next = p   ;
      }
    } else {
      p -> next = NULL       ; // 新建链表
      * list = p             ;
    }
}

青衫烟雨客 发表于 2021-10-30 13:26:42

jackz007 发表于 2021-10-30 10:16
改写这个函数

【头插法】


大佬，我想问问这个函数为啥当第一个输入数据小于第二个输入数据时，会进入死循环

青衫烟雨客 发表于 2021-10-30 16:00:33

jackz007 发表于 2021-10-30 10:16
改写这个函数

【头插法】


大佬，这道题还有方法实现嘛

jackz007 发表于 2021-10-30 19:41:11

青衫烟雨客 发表于 2021-10-30 16:00
大佬，这道题还有方法实现嘛

       3 楼的代码已经更新，现在再试。

青衫烟雨客 发表于 2021-10-30 21:06:01

jackz007 发表于 2021-10-30 19:41
3 楼的代码已经更新，现在再试。

可以了，非常感谢，麻烦您了

青衫烟雨客 发表于 2021-10-30 21:48:43

本帖最后由 青衫烟雨客 于 2021-10-30 21:56 编辑

{:10_298:} {:10_298:} {:10_298:}

查看完整版本: 大佬帮我看看单链表排序