鱼C论坛

 找回密码
 立即注册
查看: 2178|回复: 13

[已解决]求教c语言的 动态链表排序

[复制链接]
发表于 2018-4-14 16:29:10 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
struct Postgraduate {                                                        //研究生
        int num;                                                                        //学号
        char name[10];                                                                //姓名
        char sex1[4];                                                            //性别
        int score;
        struct  Postgraduate *next;
}*head;


例如head有 3个数据,|01  小明  男   66 | 02  小甲鱼  99 | 03 大甲鱼 88|NULL

然后怎么才能按照分数由大到小排好???
最佳答案
2018-4-14 22:30:19
ssg 发表于 2018-4-14 19:17
没有人吗?????

^_^

今天先就写到这里,我明天有事,要早点睡觉
Swap函数已经调试到完美,希望没有什么问题了,^_^
就剩下 void SortList(struct Postgraduate *head) 这个函数了
你先试着写一写,看看能不能写出来,如果明天有时间,我再来写,不过真的建议你先写一写

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. typedef struct Postgraduate                        // 研究生
  5. {
  6.         int num;                                // 学号
  7.         char name[10];                                // 姓名
  8.         char sex1[4];                                // 性别
  9.         int score;
  10.         struct  Postgraduate *prior;
  11.         struct  Postgraduate *next;
  12. } Node;

  13. struct Postgraduate *CreateListDebug(struct Postgraduate arr[], int count)
  14. {
  15.         // 头结点不存储数据
  16.         struct Postgraduate *head = malloc(sizeof(Node));;
  17.         head->num = 0;
  18.         head->name[0] = '\0';
  19.         head->sex1[0] = '\0';
  20.         head->score = 0;
  21.         head->prior = NULL;
  22.         head->next = NULL;

  23.         Node *p = head;
  24.         for(int i = 0; i < count; ++i)
  25.         {
  26.                 Node *n = malloc(sizeof(Node));

  27.                 n->num = arr[i].num;
  28.                 strcpy(n->name, arr[i].name);
  29.                 strcpy(n->sex1, arr[i].sex1);
  30.                 n->score = arr[i].score;
  31.                 n->prior = NULL;
  32.                 n->next = NULL;

  33.                 p->next = n;
  34.                 n->prior = p;
  35.                 p = p->next;
  36.         }

  37.         return head;
  38. }

  39. void Swap(Node *a, Node *b)
  40. {
  41.         // a和b紧挨着的时候需要另一种方法
  42.         if((a->next == b) || (b->next == a))
  43.         {
  44.                 // a在b的前面和b在a的前面不能使用同一种方法
  45.                 if(b->next == a)        // 让a始终在b的前面
  46.                 {
  47.                         struct  Postgraduate *temp = a;
  48.                         a = b;
  49.                         b = temp;
  50.                 }

  51.                 struct  Postgraduate *a_prior = a->prior;
  52.                 struct  Postgraduate *b_next = b->next;

  53.                 if(b_next == NULL)        // b是尾结点
  54.                 {
  55.                         a_prior->next = b;
  56.                         b->prior = a_prior;
  57.                         a->next = b_next;
  58.                         a->prior = b;
  59.                         b->next = a;
  60.                 }
  61.                 else
  62.                 {
  63.                         a_prior->next = b;
  64.                         b->prior = a_prior;
  65.                         a->next = b_next;
  66.                         a->prior = b;
  67.                         b->next = a;
  68.                         b_next->prior = a;
  69.                 }
  70.         }
  71.         else
  72.         {
  73.                 struct  Postgraduate *a_prior = a->prior;
  74.                 struct  Postgraduate *a_next = a->next;
  75.                 struct  Postgraduate *b_prior = b->prior;
  76.                 struct  Postgraduate *b_next = b->next;


  77.                 if((a_next == NULL) || (b_next == NULL))        // 这两个结点中有一个是尾结点
  78.                 {
  79.                         if(a_next == NULL)        // 让b成为尾结点
  80.                         {
  81.                                 struct  Postgraduate *temp = a;
  82.                                 a = b;
  83.                                 b = temp;

  84.                                 // update
  85.                                 a_prior = a->prior;
  86.                                 a_next = a->next;
  87.                                 b_prior = b->prior;
  88.                                 b_next = b->next;
  89.                         }

  90.                         a_prior->next = b;
  91.                         b->prior = a_prior;
  92.                         a->next = b_next;
  93.                         a->prior = b_prior;
  94.                         a_next->prior = b;
  95.                         b_prior->next = a;
  96.                         b->next = a_next;
  97.                 }
  98.                 else
  99.                 {
  100.                         a_prior->next = b;
  101.                         b->prior = a_prior;
  102.                         a->next = b_next;
  103.                         a->prior = b_prior;
  104.                         a_next->prior = b;
  105.                         b_prior->next = a;
  106.                         b->next = a_next;
  107.                         b_next->prior = a;
  108.                 }
  109.         }
  110. }

  111. void SortList(struct Postgraduate *head)
  112. {

  113. }

  114. int main(void)
  115. {
  116.         struct Postgraduate arr[] =
  117.         {
  118.                 {0, "小红", "女", 100},
  119.                 {1, "小明", "男", 10},
  120.                 {2, "小玲", "女", 50},
  121.                 {3, "小丽", "女", 40},
  122.                 {4, "小林", "男", 90},
  123.                 {5, "小张", "男", 5}
  124.         };
  125.         int arr_count = sizeof(arr) / sizeof(arr[0]);

  126.         struct Postgraduate *head = CreateListDebug(arr, arr_count);

  127.         Swap(head->next, head->next->next->next);
  128.         Swap(head->next->next->next, head->next);
  129.        
  130.         Swap(head->next, head->next->next);
  131.         Swap(head->next->next, head->next);
  132.        
  133.         Swap(head->next, head->next->next->next->next->next->next);
  134.         Swap(head->next->next->next->next->next->next, head->next);
  135.        
  136.         Swap(head->next->next->next->next->next, head->next->next->next->next->next->next);
  137.         Swap(head->next->next->next->next->next->next, head->next->next->next->next->next);
  138.         return 0;
  139. }
复制代码



下面是前一个版本,未完成的版本,正因为有下面这个版本,才会有双向链表的这个版本,如果有兴趣,你可以参考
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. typedef struct Postgraduate                        // 研究生
  5. {
  6.         int num;                                // 学号
  7.         char name[10];                                // 姓名
  8.         char sex1[4];                                // 性别
  9.         int score;
  10.         struct  Postgraduate *next;
  11. } Node;

  12. void GetString(char *buff, int max_count)
  13. {
  14.         fgets(buff, max_count, stdin);
  15.         int len = strlen(buff);
  16.         buff[len - 1] = '\0';
  17. }

  18. struct Postgraduate *CreateListDebug(struct Postgraduate arr[], int count)
  19. {
  20.         struct Postgraduate *head = NULL;
  21.         Node *p;

  22.         for(int i = 0; i < count; ++i)
  23.         {
  24.                 Node *n = malloc(sizeof(Node));

  25.                 n->num = arr[i].num;
  26.                 strcpy(n->name, arr[i].name);
  27.                 strcpy(n->sex1, arr[i].sex1);
  28.                 n->score = arr[i].score;
  29.                 n->next = NULL;

  30.                 if(head == NULL)
  31.                 {
  32.                         head = n;
  33.                         p = head;
  34.                         continue;
  35.                 }

  36.                 p->next = n;
  37.                 p = p->next;
  38.         }

  39.         return head;
  40. }

  41. struct Postgraduate *CreateList(void)
  42. {
  43.         struct Postgraduate *head = NULL;
  44.         Node *p;
  45.         int count = 5;
  46.        
  47.         do
  48.         {
  49.                 Node *n = malloc(sizeof(Node));

  50.                 printf("学号:");
  51.                 scanf("%d", &n->num);
  52.                 getchar();
  53.                 printf("姓名:");
  54.                 GetString(n->name, 10);
  55.                 printf("性别:");
  56.                 GetString(n->sex1, 4);
  57.                 printf("成绩:");
  58.                 scanf("%d", &n->score);
  59.                 getchar();
  60.                 n->next = NULL;

  61.                 if(head == NULL)
  62.                 {
  63.                         head = n;
  64.                         p = head;
  65.                         continue;
  66.                 }

  67.                 p->next = n;
  68.                 p = p->next;
  69.         }
  70.         while(--count);

  71.         return head;
  72. }

  73. void Swap(Node *a, Node *b)
  74. {
  75.         struct  Postgraduate *temp_a;
  76.         struct  Postgraduate *temp_b;

  77.         temp_a = a->next;
  78.         a->next = b->next;
  79.         temp_b = b->next->next;
  80.         b->next->next = temp_a;
  81.         b->next->next->next = temp_b;
  82. }

  83. void SortList(struct Postgraduate *head)
  84. {

  85. }

  86. int main(void)
  87. {
  88.         struct Postgraduate arr[] =
  89.         {
  90.                 {0, "小红", "女", 100},
  91.                 {1, "小明", "男", 10},
  92.                 {2, "小玲", "女", 50},
  93.                 {3, "小丽", "女", 40},
  94.                 {4, "小林", "男", 90},
  95.                 {5, "小张", "男", 5}
  96.         };
  97.         int arr_count = sizeof(arr) / sizeof(arr[0]);

  98.         //struct Postgraduate *head = CreateList();
  99.         struct Postgraduate *head = CreateListDebug(arr, arr_count);        // 为debug方便,使用数组录入数据,每次都要手动输入太要命了,^_^

  100.         //Swap(head, head->next);
  101.         //Swap(head->next, head->next->next);
  102.         Swap(head, head->next->next);
  103.         return 0;
  104. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-4-14 22:30:19 | 显示全部楼层    本楼为最佳答案   
ssg 发表于 2018-4-14 19:17
没有人吗?????

^_^

今天先就写到这里,我明天有事,要早点睡觉
Swap函数已经调试到完美,希望没有什么问题了,^_^
就剩下 void SortList(struct Postgraduate *head) 这个函数了
你先试着写一写,看看能不能写出来,如果明天有时间,我再来写,不过真的建议你先写一写

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. typedef struct Postgraduate                        // 研究生
  5. {
  6.         int num;                                // 学号
  7.         char name[10];                                // 姓名
  8.         char sex1[4];                                // 性别
  9.         int score;
  10.         struct  Postgraduate *prior;
  11.         struct  Postgraduate *next;
  12. } Node;

  13. struct Postgraduate *CreateListDebug(struct Postgraduate arr[], int count)
  14. {
  15.         // 头结点不存储数据
  16.         struct Postgraduate *head = malloc(sizeof(Node));;
  17.         head->num = 0;
  18.         head->name[0] = '\0';
  19.         head->sex1[0] = '\0';
  20.         head->score = 0;
  21.         head->prior = NULL;
  22.         head->next = NULL;

  23.         Node *p = head;
  24.         for(int i = 0; i < count; ++i)
  25.         {
  26.                 Node *n = malloc(sizeof(Node));

  27.                 n->num = arr[i].num;
  28.                 strcpy(n->name, arr[i].name);
  29.                 strcpy(n->sex1, arr[i].sex1);
  30.                 n->score = arr[i].score;
  31.                 n->prior = NULL;
  32.                 n->next = NULL;

  33.                 p->next = n;
  34.                 n->prior = p;
  35.                 p = p->next;
  36.         }

  37.         return head;
  38. }

  39. void Swap(Node *a, Node *b)
  40. {
  41.         // a和b紧挨着的时候需要另一种方法
  42.         if((a->next == b) || (b->next == a))
  43.         {
  44.                 // a在b的前面和b在a的前面不能使用同一种方法
  45.                 if(b->next == a)        // 让a始终在b的前面
  46.                 {
  47.                         struct  Postgraduate *temp = a;
  48.                         a = b;
  49.                         b = temp;
  50.                 }

  51.                 struct  Postgraduate *a_prior = a->prior;
  52.                 struct  Postgraduate *b_next = b->next;

  53.                 if(b_next == NULL)        // b是尾结点
  54.                 {
  55.                         a_prior->next = b;
  56.                         b->prior = a_prior;
  57.                         a->next = b_next;
  58.                         a->prior = b;
  59.                         b->next = a;
  60.                 }
  61.                 else
  62.                 {
  63.                         a_prior->next = b;
  64.                         b->prior = a_prior;
  65.                         a->next = b_next;
  66.                         a->prior = b;
  67.                         b->next = a;
  68.                         b_next->prior = a;
  69.                 }
  70.         }
  71.         else
  72.         {
  73.                 struct  Postgraduate *a_prior = a->prior;
  74.                 struct  Postgraduate *a_next = a->next;
  75.                 struct  Postgraduate *b_prior = b->prior;
  76.                 struct  Postgraduate *b_next = b->next;


  77.                 if((a_next == NULL) || (b_next == NULL))        // 这两个结点中有一个是尾结点
  78.                 {
  79.                         if(a_next == NULL)        // 让b成为尾结点
  80.                         {
  81.                                 struct  Postgraduate *temp = a;
  82.                                 a = b;
  83.                                 b = temp;

  84.                                 // update
  85.                                 a_prior = a->prior;
  86.                                 a_next = a->next;
  87.                                 b_prior = b->prior;
  88.                                 b_next = b->next;
  89.                         }

  90.                         a_prior->next = b;
  91.                         b->prior = a_prior;
  92.                         a->next = b_next;
  93.                         a->prior = b_prior;
  94.                         a_next->prior = b;
  95.                         b_prior->next = a;
  96.                         b->next = a_next;
  97.                 }
  98.                 else
  99.                 {
  100.                         a_prior->next = b;
  101.                         b->prior = a_prior;
  102.                         a->next = b_next;
  103.                         a->prior = b_prior;
  104.                         a_next->prior = b;
  105.                         b_prior->next = a;
  106.                         b->next = a_next;
  107.                         b_next->prior = a;
  108.                 }
  109.         }
  110. }

  111. void SortList(struct Postgraduate *head)
  112. {

  113. }

  114. int main(void)
  115. {
  116.         struct Postgraduate arr[] =
  117.         {
  118.                 {0, "小红", "女", 100},
  119.                 {1, "小明", "男", 10},
  120.                 {2, "小玲", "女", 50},
  121.                 {3, "小丽", "女", 40},
  122.                 {4, "小林", "男", 90},
  123.                 {5, "小张", "男", 5}
  124.         };
  125.         int arr_count = sizeof(arr) / sizeof(arr[0]);

  126.         struct Postgraduate *head = CreateListDebug(arr, arr_count);

  127.         Swap(head->next, head->next->next->next);
  128.         Swap(head->next->next->next, head->next);
  129.        
  130.         Swap(head->next, head->next->next);
  131.         Swap(head->next->next, head->next);
  132.        
  133.         Swap(head->next, head->next->next->next->next->next->next);
  134.         Swap(head->next->next->next->next->next->next, head->next);
  135.        
  136.         Swap(head->next->next->next->next->next, head->next->next->next->next->next->next);
  137.         Swap(head->next->next->next->next->next->next, head->next->next->next->next->next);
  138.         return 0;
  139. }
复制代码



下面是前一个版本,未完成的版本,正因为有下面这个版本,才会有双向链表的这个版本,如果有兴趣,你可以参考
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. typedef struct Postgraduate                        // 研究生
  5. {
  6.         int num;                                // 学号
  7.         char name[10];                                // 姓名
  8.         char sex1[4];                                // 性别
  9.         int score;
  10.         struct  Postgraduate *next;
  11. } Node;

  12. void GetString(char *buff, int max_count)
  13. {
  14.         fgets(buff, max_count, stdin);
  15.         int len = strlen(buff);
  16.         buff[len - 1] = '\0';
  17. }

  18. struct Postgraduate *CreateListDebug(struct Postgraduate arr[], int count)
  19. {
  20.         struct Postgraduate *head = NULL;
  21.         Node *p;

  22.         for(int i = 0; i < count; ++i)
  23.         {
  24.                 Node *n = malloc(sizeof(Node));

  25.                 n->num = arr[i].num;
  26.                 strcpy(n->name, arr[i].name);
  27.                 strcpy(n->sex1, arr[i].sex1);
  28.                 n->score = arr[i].score;
  29.                 n->next = NULL;

  30.                 if(head == NULL)
  31.                 {
  32.                         head = n;
  33.                         p = head;
  34.                         continue;
  35.                 }

  36.                 p->next = n;
  37.                 p = p->next;
  38.         }

  39.         return head;
  40. }

  41. struct Postgraduate *CreateList(void)
  42. {
  43.         struct Postgraduate *head = NULL;
  44.         Node *p;
  45.         int count = 5;
  46.        
  47.         do
  48.         {
  49.                 Node *n = malloc(sizeof(Node));

  50.                 printf("学号:");
  51.                 scanf("%d", &n->num);
  52.                 getchar();
  53.                 printf("姓名:");
  54.                 GetString(n->name, 10);
  55.                 printf("性别:");
  56.                 GetString(n->sex1, 4);
  57.                 printf("成绩:");
  58.                 scanf("%d", &n->score);
  59.                 getchar();
  60.                 n->next = NULL;

  61.                 if(head == NULL)
  62.                 {
  63.                         head = n;
  64.                         p = head;
  65.                         continue;
  66.                 }

  67.                 p->next = n;
  68.                 p = p->next;
  69.         }
  70.         while(--count);

  71.         return head;
  72. }

  73. void Swap(Node *a, Node *b)
  74. {
  75.         struct  Postgraduate *temp_a;
  76.         struct  Postgraduate *temp_b;

  77.         temp_a = a->next;
  78.         a->next = b->next;
  79.         temp_b = b->next->next;
  80.         b->next->next = temp_a;
  81.         b->next->next->next = temp_b;
  82. }

  83. void SortList(struct Postgraduate *head)
  84. {

  85. }

  86. int main(void)
  87. {
  88.         struct Postgraduate arr[] =
  89.         {
  90.                 {0, "小红", "女", 100},
  91.                 {1, "小明", "男", 10},
  92.                 {2, "小玲", "女", 50},
  93.                 {3, "小丽", "女", 40},
  94.                 {4, "小林", "男", 90},
  95.                 {5, "小张", "男", 5}
  96.         };
  97.         int arr_count = sizeof(arr) / sizeof(arr[0]);

  98.         //struct Postgraduate *head = CreateList();
  99.         struct Postgraduate *head = CreateListDebug(arr, arr_count);        // 为debug方便,使用数组录入数据,每次都要手动输入太要命了,^_^

  100.         //Swap(head, head->next);
  101.         //Swap(head->next, head->next->next);
  102.         Swap(head, head->next->next);
  103.         return 0;
  104. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2018-4-14 16:58:36 From FishC Mobile | 显示全部楼层
比较每一个节点的score值大小即可
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2018-4-14 16:59:32 | 显示全部楼层
BngThea 发表于 2018-4-14 16:58
比较每一个节点的score值大小即可

emmm  我想实现把排序好的顺序 放到 head2 去,怎么写??
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-4-14 17:01:51 From FishC Mobile | 显示全部楼层
将head2的next指针指向头节点即可
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-4-14 17:03:11 | 显示全部楼层
BngThea 发表于 2018-4-14 17:01
将head2的next指针指向头节点即可

那循环的条件语句怎么写,我c语言很菜
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-4-14 17:03:46 | 显示全部楼层
BngThea 发表于 2018-4-14 17:01
将head2的next指针指向头节点即可

我写好几个星期了,还没写好这程序
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-4-14 19:17:42 | 显示全部楼层
没有人吗?????
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-4-15 08:40:05 | 显示全部楼层
人造人 发表于 2018-4-14 22:30
^_^

今天先就写到这里,我明天有事,要早点睡觉

谢谢层主,膜拜,,,我 昨天 用冒泡写了一下,暂时搞定了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-4-15 08:41:55 | 显示全部楼层
人造人 发表于 2018-4-14 22:30
^_^

今天先就写到这里,我明天有事,要早点睡觉

又学到双向链表这好东西了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-4-15 09:58:39 | 显示全部楼层
ssg 发表于 2018-4-15 08:41
又学到双向链表这好东西了

^_^
我也写完了

应该没有问题了
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. typedef struct Postgraduate                        // 研究生
  5. {
  6.         int num;                                // 学号
  7.         char name[10];                                // 姓名
  8.         char sex1[4];                                // 性别
  9.         int score;
  10.         struct  Postgraduate *prior;
  11.         struct  Postgraduate *next;
  12. } Node;

  13. struct Postgraduate *CreateListDebug(struct Postgraduate arr[], int count)
  14. {
  15.         // 头结点不存储数据
  16.         struct Postgraduate *head = malloc(sizeof(Node));;
  17.         head->num = 0;
  18.         head->name[0] = '\0';
  19.         head->sex1[0] = '\0';
  20.         head->score = 0;
  21.         head->prior = NULL;
  22.         head->next = NULL;

  23.         Node *p = head;
  24.         for(int i = 0; i < count; ++i)
  25.         {
  26.                 Node *n = malloc(sizeof(Node));

  27.                 n->num = arr[i].num;
  28.                 strcpy(n->name, arr[i].name);
  29.                 strcpy(n->sex1, arr[i].sex1);
  30.                 n->score = arr[i].score;
  31.                 n->prior = NULL;
  32.                 n->next = NULL;

  33.                 p->next = n;
  34.                 n->prior = p;
  35.                 p = p->next;
  36.         }

  37.         return head;
  38. }

  39. void Swap(Node *a, Node *b)
  40. {
  41.         // a和b紧挨着的时候需要另一种方法
  42.         if((a->next == b) || (b->next == a))
  43.         {
  44.                 // a在b的前面和b在a的前面不能使用同一种方法
  45.                 if(b->next == a)        // 让a始终在b的前面
  46.                 {
  47.                         struct  Postgraduate *temp = a;
  48.                         a = b;
  49.                         b = temp;
  50.                 }

  51.                 struct  Postgraduate *a_prior = a->prior;
  52.                 struct  Postgraduate *b_next = b->next;

  53.                 if(b_next == NULL)        // b是尾结点
  54.                 {
  55.                         a_prior->next = b;
  56.                         b->prior = a_prior;
  57.                         a->next = b_next;
  58.                         a->prior = b;
  59.                         b->next = a;
  60.                 }
  61.                 else
  62.                 {
  63.                         a_prior->next = b;
  64.                         b->prior = a_prior;
  65.                         a->next = b_next;
  66.                         a->prior = b;
  67.                         b->next = a;
  68.                         b_next->prior = a;
  69.                 }
  70.         }
  71.         else
  72.         {
  73.                 struct  Postgraduate *a_prior = a->prior;
  74.                 struct  Postgraduate *a_next = a->next;
  75.                 struct  Postgraduate *b_prior = b->prior;
  76.                 struct  Postgraduate *b_next = b->next;


  77.                 if((a_next == NULL) || (b_next == NULL))        // 这两个结点中有一个是尾结点
  78.                 {
  79.                         if(a_next == NULL)        // 让b成为尾结点
  80.                         {
  81.                                 struct  Postgraduate *temp = a;
  82.                                 a = b;
  83.                                 b = temp;

  84.                                 // update
  85.                                 a_prior = a->prior;
  86.                                 a_next = a->next;
  87.                                 b_prior = b->prior;
  88.                                 b_next = b->next;
  89.                         }

  90.                         a_prior->next = b;
  91.                         b->prior = a_prior;
  92.                         a->next = b_next;
  93.                         a->prior = b_prior;
  94.                         a_next->prior = b;
  95.                         b_prior->next = a;
  96.                         b->next = a_next;
  97.                 }
  98.                 else
  99.                 {
  100.                         a_prior->next = b;
  101.                         b->prior = a_prior;
  102.                         a->next = b_next;
  103.                         a->prior = b_prior;
  104.                         a_next->prior = b;
  105.                         b_prior->next = a;
  106.                         b->next = a_next;
  107.                         b_next->prior = a;
  108.                 }
  109.         }
  110. }

  111. void SortList(struct Postgraduate *head)
  112. {
  113.         for(Node *i = head->next; i != NULL; i = i->next)
  114.         {
  115.                 for(Node *j = i->next; j != NULL; j = j->next)
  116.                 {
  117.                         if(i->score > j->score)
  118.                         {
  119.                                 Swap(i, j);

  120.                                 Node *temp = i;
  121.                                 i = j;
  122.                                 j = temp;
  123.                         }
  124.                 }
  125.         }
  126. }

  127. int main(void)
  128. {
  129.         struct Postgraduate arr[] =
  130.         {
  131.                 {0, "小红", "女", 100},
  132.                 {1, "小明", "男", 10},
  133.                 {2, "小玲", "女", 50},
  134.                 {3, "小丽", "女", 40},
  135.                 {4, "小林", "男", 90},
  136.                 {5, "小张", "男", 5}
  137.         };
  138.         int arr_count = sizeof(arr) / sizeof(arr[0]);

  139.         struct Postgraduate *head = CreateListDebug(arr, arr_count);

  140.         /*Swap(head->next, head->next->next->next);
  141.         Swap(head->next->next->next, head->next);
  142.        
  143.         Swap(head->next, head->next->next);
  144.         Swap(head->next->next, head->next);
  145.        
  146.         Swap(head->next, head->next->next->next->next->next->next);
  147.         Swap(head->next->next->next->next->next->next, head->next);
  148.        
  149.         Swap(head->next->next->next->next->next, head->next->next->next->next->next->next);
  150.         Swap(head->next->next->next->next->next->next, head->next->next->next->next->next);*/

  151.         SortList(head);

  152.         return 0;
  153. }
复制代码


无标题.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-4-15 12:17:38 | 显示全部楼层
其实链表的排序挺简单的,但是楼主说的动态链表是要重新指向么,那个就有一些复杂了,但是单单排序非循环单链表的话这个就是和平常的数组的排序一个思想
下面是一个C++代码
有错请联系俺,会更正,
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <assert.h>
  5. using namespace std;

  6. class Student{
  7. public:
  8.         class LinkNode{
  9.         public:
  10.                 int data;
  11.                 char name[128];
  12.                 LinkNode* next;
  13.         };
  14.         typedef LinkNode* NodePointer;

  15.         Student();//构造默认函数
  16.         void insert(int i, char *inputName, int value);
  17.         friend ostream& operator<<(ostream& out, Student &other);
  18.         friend void sortTheData(Student s1);
  19.        
  20. private:
  21.         NodePointer head;
  22. };

  23. Student::Student(){
  24.         head = NULL;
  25. }

  26. void Student::insert(int i, char *inputName, int value){
  27.         if (i == 1){
  28.                 NodePointer s = new LinkNode;
  29.                 strcpy(s->name, inputName);
  30.                 s->data = value;
  31.                 s->next = head;
  32.                 head = s;
  33.                 cout << "头结点插入成功" << endl;
  34.                 return;
  35.         }

  36.         int j = 1;
  37.         NodePointer p = head;
  38.         NodePointer s;
  39.         while (p && j < i - 1){
  40.                 j++;
  41.                 p = p->next;//找到前驱
  42.         }
  43.         s = new LinkNode;
  44.         strcpy(s->name, inputName);
  45.         s->data = value;
  46.         s->next = p->next;
  47.         p->next = s;
  48.         cout << "插入成功" << endl;
  49.         return;
  50. }


  51. ostream& operator<<(ostream& out, Student &other){
  52.         Student::NodePointer p = other.head;
  53.         while (p){
  54.                 out << "姓名:" << p->name << "\t" << "数据:" << p->data << endl;
  55.                 p = p->next;
  56.         }
  57.         return out;
  58. }

  59. void sortTheData(Student s1){
  60.         Student::NodePointer p = s1.head;
  61.         while (p){
  62.                 Student::NodePointer s = p;
  63.                 while (s){
  64.                         if (s->data > p->data){
  65.                                 int temp = s->data;
  66.                                 s->data = p->data;
  67.                                 p->data = temp;

  68.                                 char tempName[128];
  69.                                 strcpy(tempName, s->name);
  70.                                 strcpy(s->name, p->name);
  71.                                 strcpy(p->name, tempName);
  72.                         }
  73.                         s = s->next;
  74.                 }
  75.                 p = p->next;
  76.         }
  77. }


  78. int main(void){
  79.         Student s1;
  80.         int data;
  81.         char name[128];
  82.         for (int i = 1; i <= 3; i++){
  83.                 cout << "请输入姓名:";
  84.                 cin >> name;
  85.                 cout << "请输入数据:";
  86.                 cin >> data;

  87.                 s1.insert(i, name, data);
  88.         }

  89.         cout << "*****************************" << endl;
  90.         cout << "s1是:" << endl;
  91.         cout << s1 << endl;

  92.         cout << "*****************************" << endl;
  93.         cout << "排序后的s1是:" << endl;
  94.         sortTheData(s1);
  95.         cout << s1;
  96.         return 0;
  97. }



复制代码


其中的67到86行就是排序的了,,,,
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2018-4-15 12:23:08 | 显示全部楼层
其中这个程序里只能插入三个结点,要是想插入任意个数结点的话就可以在main函数里修改一下就行了
下面是运行结果
  1. 请输入姓名:小甲鱼
  2. 请输入数据:89
  3. 头结点插入成功
  4. 请输入姓名:大甲鱼
  5. 请输入数据:67
  6. 插入成功
  7. 请输入姓名:周西瓜
  8. 请输入数据:100
  9. 插入成功
  10. *****************************
  11. s1是:
  12. 姓名:小甲鱼     数据:89
  13. 姓名:大甲鱼     数据:67
  14. 姓名:周西瓜     数据:100

  15. *****************************
  16. 排序后的s1是:
  17. 姓名:周西瓜     数据:100
  18. 姓名:小甲鱼     数据:89
  19. 姓名:大甲鱼     数据:67
  20. 请按任意键继续. . .
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2018-4-15 21:03:47 | 显示全部楼层
溯影 发表于 2018-4-15 12:17
其实链表的排序挺简单的,但是楼主说的动态链表是要重新指向么,那个就有一些复杂了,但是单单排序非循环单 ...

谢谢大佬,我学习下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-4-16 10:10:35 | 显示全部楼层
思路:按照分数排序,链表不变,把链表里面的数据交换。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Postgraduate      //研究生
{   
        int num;         //学号
        char name[10];   //姓名
        char sex1[4];    //性别
        int score;
        struct  Postgraduate *next;
};

struct Postgraduate *CreateList()
{
        struct Postgraduate *head = (struct Postgraduate *)malloc(sizeof(struct Postgraduate));
        struct Postgraduate *xiaoming = (struct Postgraduate *)malloc(sizeof(struct Postgraduate));
        struct Postgraduate *xiaojiayu = (struct Postgraduate *)malloc(sizeof(struct Postgraduate));
        struct Postgraduate *dajiayu = (struct Postgraduate *)malloc(sizeof(struct Postgraduate));
       
        xiaoming->num = 1;
        strcpy(xiaoming->name, "小明");
        strcpy(xiaoming->sex1, "男");
        xiaoming->score = 66;

        xiaojiayu->num = 2;
        strcpy(xiaojiayu->name, "小甲鱼");
        strcpy(xiaojiayu->sex1, "男");
        xiaojiayu->score = 99;

        dajiayu->num = 3;
        strcpy(dajiayu->name, "大甲鱼");
        strcpy(dajiayu->sex1, "女");
        dajiayu->score = 88;

        head->next = xiaoming;
        xiaoming->next = xiaojiayu;
        xiaojiayu->next = dajiayu;
        dajiayu->next = NULL;
       
        return head;       
}

void Log(struct Postgraduate *head)
{
        while(head->next != NULL)
        {
                head = head->next;
                printf("%d---%s---%s---%d\n", head->num, head->name, head->sex1, head->score);
        }
}

void sort(struct Postgraduate *list)
{
    struct Postgraduate *p = NULL;
    struct Postgraduate *q = NULL;
    int t = 0;
    char Tp[32];
    memset(Tp, 0, 32);
    p = list->next;
    for(; p!=NULL; p=p->next)
    {
        for(q=p->next; q!=NULL; q=q->next)
        {
            if(p->score < q->score)
            {
                t = q->num;
                q->num = p->num;
                p->num = t;

                                strcpy(Tp, q->name);
                                strcpy(q->name, p->name);
                                strcpy(p->name, Tp);
                                memset(Tp, 0, 32);

                                strcpy(Tp, q->sex1);
                                strcpy(q->sex1, p->sex1);
                                strcpy(p->sex1, Tp);
                                memset(Tp, 0, 32);

                t = q->score;
                q->score = p->score;
                p->score = t;
               
            }
        }
    }
    return;  
}

int main()
{
        struct Postgraduate *head = CreateList();
        Log(head);
        sort(head);
        printf("++++++++++++++++++++++++++\n");
        Log(head);
        return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 20:52

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表