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

phk7264264524

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

6 2
best
cat
east
a
free
day

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

best
a
cat
day
east
free

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

#include <stdio.h>
#include <string.h>
struct Str
{
    char a[10];
    struct Str *next;
};
int main()
{   
    struct Str *p,*q,*t,*head,*tail;
    p = head = tail = NULL;
    int n,k,i;
    char b[10];
    scanf("%d %d",&n, &k);      

    for(i=0; i<n; i++)
    {
        p = (struct Str *)malloc(sizeof(struct Str));
        scanf("%s", b);
        strcpy(p->a, b);
        if(head == NULL)
            head = p;
        else
            tail->next = p;
        tail = p;
    }
        tail->next = NULL;                                                                        //以上为输入到链表中，首地址为head 
         p = q = head;
        for(i = 0; i<=k; i++)
        {                
                p = q;
                while(p->next->next != NULL)
                {
                        if(strcmp(p->next->a, p->next->next->a)>0 )
                        {
                                t = p->next;
                                p->next = t->next;
                                t->next = p->next->next;
                                p->next->next = t;
                        }
                                p = p->next;
                }        
        } 
        for(i=0; i<n; i++)
        {
                printf("%s\n", head->a);
                head = head->next;
        }
} 

最佳答案

月排行榜 / 总排行榜

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啊

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Str
{
    char a[10];
    struct Str *next;
};
int main()
{   
    struct Str *p,*q,*t,*head,*tail;
    p = head = tail = NULL;
    int n,k,i;
    char b[10];
    scanf("%d %d",&n, &k);      

    for(i=0; i<n; i++)
    {
        p = (struct Str *)malloc(sizeof(struct Str));
        scanf("%s", b);
        strcpy(p->a, b);
        if(head == NULL)
            head = p;
        else
            tail->next = p;
        tail = p;
    }
    tail->next = NULL;                                                                        //以上为输入到链表中，首地址为head 
    for(int i=0;i<n-1;i++)
        {
                p=q=head; 
                while(p->next!=NULL){
                        if(strcmp(p->a, p->next->a)>0){
                                //节点的交换 
                                if(p==head) 
                                    head=p->next;
                                else 
                                    q->next=p->next;
                                q=q->next;
                                p->next=q->next;
                                q->next=p;
                                //执行完上面的过程后，为了能够让p顺利地执行移动到交换后的下一位 . 
                                p=q; 
                        }
                        q=p; //为了能让q保持在p的前面 
                        p=p->next; //p指针后移，即p变成了在q的前面 
                }
        }

    for(i=0; i<n; i++)
    {
            printf("%s\n", head->a);
            head = head->next;
    }
} 

phk7264264524

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

#include <stdio.h>
#include <string.h>
struct Str
{
    char a[10];
    struct Str *next;
};
int main()
{   
    struct Str *p,*q,*t,*head,*tail;
    p = head = tail = NULL;
    int n,k,i;
    char b[10];
    scanf("%d %d",&n, &k);      

    for(i=0; i<n; i++)
    {
        p = (struct Str *)malloc(sizeof(struct Str));
        scanf("%s", b);
        strcpy(p->a, b);
        if(head == NULL)
            head = p;
        else
            tail->next = p;
        tail = p;
    }
    t->next = head;
        head = t;      
        tail->next = NULL;                                                                        //以上为输入到链表中，首地址为head 
         p = q = head;
        for(i = 0; i<=k; i++)
        {                
                p = q;
                while(p->next->next != NULL)
                {
                        if(strcmp(p->next->a, p->next->next->a)>0 )
                        {
                                t = p->next;
                                p->next = t->next;
                                t->next = p->next->next;
                                p->next->next = t;
                        }
                                p = p->next;
                }        
        }
        head = head->next; 
        for(i=0; i<n; i++)
        {
                printf("%s\n", head->a);
                head = head->next;
        }
} 

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

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, 还是失败的