论坛 › C\C++交流 › 用链表实现冒泡排序

phk7264264524 发表于 2020-5-21 14:40:35

用链表实现冒泡排序

输入格式：
输入在第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;
    struct Str *next;
};
int main()
{   
    struct Str *p,*q,*t,*head,*tail;
    p = head = tail = NULL;
    int n,k,i;
    char b;
    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;
        }
}

phk7264264524 发表于 2020-5-21 15:44:17

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

sunrise085 发表于 2020-5-21 16:22:17

本帖最后由 sunrise085 于 2020-5-21 17:16 编辑

你这个程序之所以没有对第一个进行排序，是因为在第34行，条件判断中，直接判断的的第二个和第三个的大小，根本没有考虑第一个节点
另外，排序的外层循环次数为什么是k啊
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Str
{
    char a;
    struct Str *next;
};
int main()
{   
    struct Str *p,*q,*t,*head,*tail;
    p = head = tail = NULL;
    int n,k,i;
    char b;
    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 发表于 2020-5-21 20:53:22

但如果我采用的不是考虑第一个结点和第二个结点进行比较，而是在第一个结点前加上一个空的结点，然后将第0个结点作为head指针，那么我的方法应该是可以正常排序的吧...
#include <stdio.h>
#include <string.h>
struct Str
{
    char a;
    struct Str *next;
};
int main()
{   
    struct Str *p,*q,*t,*head,*tail;
    p = head = tail = NULL;
    int n,k,i;
    char b;
    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 发表于 2020-5-21 20:54:09

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

区别主要在于 第27，28行

sunrise085 发表于 2020-5-21 21:34:34

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

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

phk7264264524 发表于 2020-5-21 22:40:35

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

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

查看完整版本: 用链表实现冒泡排序