[已解决]用链表实现冒泡排序

phk7264264524

输入格式：
输入在第1行中给出N和K（1≤K<N≤100），此后N行，每行包含一个长度不超过10的、仅由小写英文字母组成的非空字符串。

1. 6 2
   
2. best
   
3. cat
   
4. east
   
5. a
   
6. free
   
7. day

复制代码

输出格式：
输出冒泡排序法扫描完第K遍后的中间结果序列，每行包含一个字符串。

1. best
   
2. a
   
3. cat
   
4. day
   
5. east
   
6. free

复制代码

我自己写了下面的代码，想问一下如何在head（链表头指针）前面加上一个结点组成新的链表，我自己尝试了一下做不出。

1. #include <stdio.h>
   
2. #include <string.h>
   
3. struct Str
   
4. {
   
5.     char a[10];
   
6.     struct Str *next;
   
7. };
   
8. int main()
   
9. {   
   
10.     struct Str *p,*q,*t,*head,*tail;
    
11.     p = head = tail = NULL;
    
12.     int n,k,i;
    
13.     char b[10];
    
14.     scanf("%d %d",&n, &k);      
    
15. 
    
16.     for(i=0; i<n; i++)
    
17.     {
    
18.         p = (struct Str *)malloc(sizeof(struct Str));
    
19.         scanf("%s", b);
    
20.         strcpy(p->a, b);
    
21.         if(head == NULL)
    
22.             head = p;
    
23.         else
    
24.             tail->next = p;
    
25.         tail = p;
    
26.     }
    
27.         tail->next = NULL;                                                                        //以上为输入到链表中，首地址为head
    
28.         p = q = head;
    
29.         for(i = 0; i<=k; i++)
    
30.         {               
    
31.                 p = q;
    
32.                 while(p->next->next != NULL)
    
33.                 {
    
34.                         if(strcmp(p->next->a, p->next->next->a)>0 )
    
35.                         {
    
36.                                 t = p->next;
    
37.                                 p->next = t->next;
    
38.                                 t->next = p->next->next;
    
39.                                 p->next->next = t;
    
40.                         }
    
41.                                 p = p->next;
    
42.                 }       
    
43.         }
    
44.         for(i=0; i<n; i++)
    
45.         {
    
46.                 printf("%s\n", head->a);
    
47.                 head = head->next;
    
48.         }
    
49. }

复制代码

最佳答案

月排行榜 / 总排行榜

sunrise085

2020-5-21 21:34:34

phk7264264524 发表于 2020-5-21 20:53
但如果我采用的不是考虑第一个结点和第二个结点进行比较，而是在第一个结点前加上一个空的结点，然后将第0 ...

你这种方法是将无头结点链表变成了有头结点链表，相当于修改了原来的链表形式。方法是可行的。
之所以不能运行应该是有两方面的原因：
1、你的节点指针t是空的，没有初始化，就是用了，不同的编译器可能会认为是错误的。
2、程序中使用了malloc函数动态分配空间，但是没有写相应的头文件， #include <stdlib.h>

跳转到最佳答案楼层

phk7264264524

我目前写的这个会大致开头两个不进行排序，有点问题

sunrise085

你这个程序之所以没有对第一个进行排序，是因为在第34行，条件判断中，直接判断的的第二个和第三个的大小，根本没有考虑第一个节点
另外，排序的外层循环次数为什么是k啊

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. struct Str
   
5. {
   
6.     char a[10];
   
7.     struct Str *next;
   
8. };
   
9. int main()
   
10. {   
    
11.     struct Str *p,*q,*t,*head,*tail;
    
12.     p = head = tail = NULL;
    
13.     int n,k,i;
    
14.     char b[10];
    
15.     scanf("%d %d",&n, &k);      
    
16. 
    
17.     for(i=0; i<n; i++)
    
18.     {
    
19.         p = (struct Str *)malloc(sizeof(struct Str));
    
20.         scanf("%s", b);
    
21.         strcpy(p->a, b);
    
22.         if(head == NULL)
    
23.             head = p;
    
24.         else
    
25.             tail->next = p;
    
26.         tail = p;
    
27.     }
    
28.     tail->next = NULL;                                                                        //以上为输入到链表中，首地址为head
    
29.     for(int i=0;i<n-1;i++)
    
30.         {
    
31.                 p=q=head;
    
32.                 while(p->next!=NULL){
    
33.                         if(strcmp(p->a, p->next->a)>0){
    
34.                                 //节点的交换
    
35.                                 if(p==head)
    
36.                                     head=p->next;
    
37.                                 else
    
38.                                     q->next=p->next;
    
39.                                 q=q->next;
    
40.                                 p->next=q->next;
    
41.                                 q->next=p;
    
42.                                 //执行完上面的过程后，为了能够让p顺利地执行移动到交换后的下一位 .
    
43.                                 p=q;
    
44.                         }
    
45.                         q=p; //为了能让q保持在p的前面
    
46.                         p=p->next; //p指针后移，即p变成了在q的前面
    
47.                 }
    
48.         }
    
49. 
    
50.     for(i=0; i<n; i++)
    
51.     {
    
52.             printf("%s\n", head->a);
    
53.             head = head->next;
    
54.     }
    
55. }

复制代码

phk7264264524

但如果我采用的不是考虑第一个结点和第二个结点进行比较，而是在第一个结点前加上一个空的结点，然后将第0个结点作为head指针，那么我的方法应该是可以正常排序的吧...

1. #include <stdio.h>
   
2. #include <string.h>
   
3. struct Str
   
4. {
   
5.     char a[10];
   
6.     struct Str *next;
   
7. };
   
8. int main()
   
9. {   
   
10.     struct Str *p,*q,*t,*head,*tail;
    
11.     p = head = tail = NULL;
    
12.     int n,k,i;
    
13.     char b[10];
    
14.     scanf("%d %d",&n, &k);      
    
15. 
    
16.     for(i=0; i<n; i++)
    
17.     {
    
18.         p = (struct Str *)malloc(sizeof(struct Str));
    
19.         scanf("%s", b);
    
20.         strcpy(p->a, b);
    
21.         if(head == NULL)
    
22.             head = p;
    
23.         else
    
24.             tail->next = p;
    
25.         tail = p;
    
26.     }
    
27.     t->next = head;
    
28.         head = t;      
    
29.         tail->next = NULL;                                                                        //以上为输入到链表中，首地址为head
    
30.         p = q = head;
    
31.         for(i = 0; i<=k; i++)
    
32.         {               
    
33.                 p = q;
    
34.                 while(p->next->next != NULL)
    
35.                 {
    
36.                         if(strcmp(p->next->a, p->next->next->a)>0 )
    
37.                         {
    
38.                                 t = p->next;
    
39.                                 p->next = t->next;
    
40.                                 t->next = p->next->next;
    
41.                                 p->next->next = t;
    
42.                         }
    
43.                                 p = p->next;
    
44.                 }       
    
45.         }
    
46.         head = head->next;
    
47.         for(i=0; i<n; i++)
    
48.         {
    
49.                 printf("%s\n", head->a);
    
50.                 head = head->next;
    
51.         }
    
52. }

复制代码

以这种方式发现运行都不能正常运行，不知道错误在哪？（当然我知道你的方法是可行的，谢谢）

phk7264264524

sunrise085 发表于 2020-5-21 16:22
你这个程序之所以没有对第一个进行排序，是因为在第34行，条件判断中，直接判断的的第二个和第三个的大小， ...

区别主要在于 第27，28行

sunrise085

phk7264264524 发表于 2020-5-21 20:53
但如果我采用的不是考虑第一个结点和第二个结点进行比较，而是在第一个结点前加上一个空的结点，然后将第0 ...

你这种方法是将无头结点链表变成了有头结点链表，相当于修改了原来的链表形式。方法是可行的。
之所以不能运行应该是有两方面的原因：
1、你的节点指针t是空的，没有初始化，就是用了，不同的编译器可能会认为是错误的。
2、程序中使用了malloc函数动态分配空间，但是没有写相应的头文件， #include <stdlib.h>

phk7264264524

sunrise085 发表于 2020-5-21 21:34
你这种方法是将无头结点链表变成了有头结点链表，相当于修改了原来的链表形式。方法是可行的。
之所以不 ...

谢谢啊，问下链表指针的初始化一定要用动态分配吗？试了一下用 t = NULL, 还是失败的