时间戳

首页 > 解决方案 > 我无法在 C 中按字母顺序对链接列表进行排序

c - 我无法在 C 中按字母顺序对链接列表进行排序

问题描述

我是编程和 StackOverflow 的新手。我无法理解其他问题的答案，因为我无法阅读那么好的代码。那么，任何人都可以帮我处理我的代码吗？我正在尝试按字母顺序对链表中的给定字符串进行排序。它们很快就会从用户手中夺走。但我试图在编码该阶段之前进行调试。

当我尝试按排序打印链接列表时，它没有给出输出。没有语法错误。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
    char word[100];
    struct node *next;
}node;

node* addToLinkedList(node *head, char word[])
{
    node *temp = (node*)malloc(sizeof(node));
    strcpy(temp->word, word);

    if(head==NULL)
    {
        temp->next=NULL;
        head=temp;
        return head;
    }

    node *iter = head;
    while(iter->next!=NULL)
        iter=iter->next;

    iter->next=temp;
    temp->next=NULL;
    return head;
}

int listLenght(node *head)
{
    int len=0;
    node *iter = head;
    while(iter!=NULL)
    {
        len++;
        iter=iter->next;
    }

    return len;
}

void sortList(node *head)
{
    int len = listLenght(head);

    int i,j;
    for(i=0; i<len; i++)
    {
        node *tmp1 = head;
        node *tmp2 = tmp1->next;
        for(j=0; j<len; j++)
        {
            int idx = 0;
            while(tmp1->word[idx] == tmp2->word[idx])
                idx++;

            if(tmp1->word[idx] > tmp2->word[idx])
            {
                char wrd[100];
                strcpy(wrd, tmp1->word);
                strcpy(tmp1->word, tmp2->word);
                strcpy(tmp2->word, wrd);

            }
            tmp1=tmp1->next;
            tmp2 = tmp2->next;
        }
        tmp1 = head;
    }
}

void printfLinkedList(node *head)
{
    node *iter = head;
    while(iter!=NULL)
    {
         printf("%s ->", iter->word);
         iter=iter->next;
    }
}

int main()
{
    node *list = NULL;
    list=addToLinkedList(list,"one" );
    list=addToLinkedList(list,"two" );
    list=addToLinkedList(list, "three");
    list=addToLinkedList(list,"four" );
    list=addToLinkedList(list,"five" );
    sortList(list);
    printfLinkedList(list);

    return 0;
}

标签： c

解决方案

程序在这一行因分段错误而终止

            while(tmp1->word[idx] == tmp2->word[idx])

因为tmp2是NULL并且您尝试取消引用指针。

由于len是列表中的元素个数，这里在最后一个循环循环中

        node *tmp1 = head;
        node *tmp2 = tmp1->next;
        for(j=0; j<len; j++)
        {
            /* ... */
            tmp1=tmp1->next;
            tmp2 = tmp2->next;
        }

tmp1将指向最后一个列表元素，tmp2并将指向其不存在的后继元素，即NULL.

要查看此错误，您应该在调试器中运行程序和/或使用内存访问检查器，如valgrind.

您可以将此循环更改为少一个循环以使您的程序工作，如下所示。（另外，我修改了您的代码以显示排序前后的列表。）

/* ... */
{
    int len = listLenght(head);

    int i,j;
    for(i=0; i<len; i++)
    {
        node *tmp1 = head;
        node *tmp2 = tmp1->next;
        for(j=0; j<len-1; j++)
        {
            int idx = 0;
            while(tmp1->word[idx] == tmp2->word[idx])
                idx++;

            if(tmp1->word[idx] > tmp2->word[idx])
            {
                char wrd[100];
                strcpy(wrd, tmp1->word);
                strcpy(tmp1->word, tmp2->word);
                strcpy(tmp2->word, wrd);

            }
            tmp1=tmp1->next;
            tmp2 = tmp2->next;
        }
        tmp1 = head;
    }
}

void printfLinkedList(node *head)
{
    node *iter = head;
    while(iter!=NULL)
    {
         printf("%s ->", iter->word);
         iter=iter->next;
    }
    printf("\n");
}

int main()
{
    node *list = NULL;
    list=addToLinkedList(list,"one" );
    list=addToLinkedList(list,"two" );
    list=addToLinkedList(list, "three");
    list=addToLinkedList(list,"four" );
    list=addToLinkedList(list,"five" );
    printfLinkedList(list);
    sortList(list);
    printfLinkedList(list);

    return 0;
}

我建议不要计算循环周期的数量，而是检查tmp1and tmp2are not NULL。

void sortList(node *head)
{
    int len = listLenght(head);

    int i,j;
   
    for(i=0; i<len; i++)
    {
        node *tmp1 = head;
        node *tmp2 = (tmp1 != NULL) ? tmp1->next : NULL;
        while((tmp1 != NULL) && (tmp2 != NULL))
        {
            int idx = 0;
            while(tmp1->word[idx] == tmp2->word[idx])
                idx++;

            if(tmp1->word[idx] > tmp2->word[idx])
            {
                char wrd[100];
                strcpy(wrd, tmp1->word);
                strcpy(tmp1->word, tmp2->word);
                strcpy(tmp2->word, wrd);

            }
            tmp1=tmp1->next;
            tmp2 = tmp2->next;
        }
        tmp1 = head;
    }
}

如果所有字符都相等，则检查相等字符可能会访问数组末尾之后的数据。这是未定义的行为，也可能导致分段错误。

确保在字符串末尾停止阅读。

            while((tmp1->word[idx] == tmp2->word[idx]) &&
                  (tmp1->word[idx] != '\0'))
                idx++;

除了自己实现字符串比较之外，您还可以使用strcmp.

void sortList(node *head)
{
    int len = listLenght(head);

    int i,j;
   
    for(i=0; i<len; i++)
    {
        node *tmp1 = head;
        node *tmp2 = (tmp1 != NULL) ? tmp1->next : NULL;
        while((tmp1 != NULL) && (tmp2 != NULL))
        {
            int idx = 0;
            if(strcmp(tmp1->word, tmp2->word) > 0)
            {
                char wrd[100];
                strcpy(wrd, tmp1->word);
                strcpy(tmp1->word, tmp2->word);
                strcpy(tmp2->word, wrd);

            }
            tmp1=tmp1->next;
            tmp2 = tmp2->next;
        }
        tmp1 = head;
    }
}

推荐阅读