排序包含字符串的链表 [英] sorting a linked list containing strings

问题描述

所以我要做的是对仅包含字符串的链表进行排序。为此，我有2个选项。

So what I want to do is to sort an linked list containing only strings. To do so, I have 2 options.

选项1-动态分配与链表相同大小的数组，并且包含它的字符串也具有相同大小，将链接列表的内容复制到数组中，并使用 qsort 对其进行排序。

Option 1 - dynamically allocate an array with the same size as the linked list and the strings containing it also with the same size, copy the contents of the linked list into the array and sort it using qsort.

选项2-实现合并

问题之一是，如果我选择选项2而不是选项1，或者选择的选项更好，会花费更多的内存和时间吗？

One of the problems is will it cost more memory and time if I do option 2 over option 1 or the option is the better?

我的第二个问题是我正在尝试执行选项1，因此我有一个包含链接列表代码的头文件。
问题是当我尝试复制内容时，当为字符串数组分配内存后，出现分段错误。

My second problem is that I'm trying to do option 1 and to do so I have a header file which contains the code of the linked lists. The problem is after allocating memory for the array of strings when I try to copy the contents I get segmentation fault.

程序：

#include <stdlib.h> 
#include <stdio.h>
#include <string.h>
#include "Listas_ligadas_char.h"

int main() {
    link_char head = NULL;
    char **strings;
    head = insertEnd_char(head, "fcb");
    head = insertEnd_char(head, "bvb");
    head = insertEnd_char(head, "slb");
    head = insertEnd_char(head, "fcp");
    int len = length_char(head);
    int i = 0, j;
    strings = (char **)malloc(sizeof(char *) * len);
    link_char t;
    t = head;
    while (t != NULL && i <= len) {
        strings[i] = (char *)malloc(sizeof(char) * (strlen(t->str) + 1));
        strcpy(strings[i++], t->v.str)
        t = t->next;
    }
    for (t = head; t != NULL; t = t->next) {
        printf("* %s\n", strings[i]);
    }
}

头文件：

#ifndef _Listas_ligadas_char_
#define _Listas_ligadas_char_

#include <stdlib.h> 
#include <stdio.h>
#include <string.h>

typedef struct node_char {
    char *str;
    struct node_char *next;
} *link_char;

link_char lookup_str(link_char head, char *str) {
    link_char t;
    for (t = head; t != NULL; t = t->next)
        if (strcmp(t->str, str) == 0)
            return t;
    return NULL;
}

link_char NEW_str(char *str) {
    int i;
    link_char x = (link_char)malloc(sizeof(struct node_char));
    x->str = (char *)malloc(sizeof(char) * (strlen(str) + 1));
    strcpy(x->str, str);
    x->next = NULL;
    return x;
}

link_char insertEnd_char(link_char head, char *str) {
    link_char x;
    if (head == NULL)
        return NEW_str(str);
    for (x = head; x->next != NULL; x = x->next)
        ;
    x->next = NEW_str(str);
    return head;
}

int length_char(link_char head) {
    int count = 0;
    link_char x;
    for (x = head; x != NULL; x = x->next)
        count++;
    return count;
}

void print_lista_char(link_char head, int NL) {
    link_char t;
    for (t = head; t != NULL; t = t->next) {
        printf("%d * %s\n", NL, t->str);
    }
}

void FREEnode_str(link_char t) {
    free(t->str);
    free(t);
}

link_char delete_el_char(link_char head, char *str) {
    link_char t, prev;
    for (t = head, prev = NULL; t != NULL;
        prev = t, t = t->next) {
        if (strcmp(t->str, str) == 0) {
            if (t == head)
                head = t->next;
            else
                prev->next = t->next;
            FREEnode_str(t);
            break;
        }
    }
    return head;
}
#endif

btw如果您想知道什么 NL 是， NL 是一个变量，用于计算 stdin 的相应行而且我只想打印数组，而我不想保留它的元素。

btw if you are wondering what NL is, NL is a variable to count the respective line of the stdin and what I only want is to print the array, I don't want to keep its elements.

因此，如果您能告诉您哪种选择是我认为最好的

So if you can tell what option you think is the best I would appreciate it a lot.

推荐答案

您确实有2个明智的选择：

You indeed have 2 sensible options:

• 选项1通常将提供最佳性能，但需要 sizeof（link_char）* N 的额外空间。

选项2仅需要使用自下而上的mergesort或类似空间的待处理子列表的 O（log（N））堆栈空间递归自上而下的mergesort的复杂性。缺点是您必须自己编写排序函数，而且很容易出错。

option 2 will only require O(log(N)) stack space for pending sublists using bottom-up mergesort or similar space complexity for recursive top-down mergesort. The drawback is you have to write the sorting function yourself and it is easy to make mistakes.

请注意， 1，您不应该复制字符串，而只是分配一个指针数组并将其初始化为指向节点本身。这样，您可以保留可能包含其他信息并避免额外分配的节点结构。

Note that for option 1, you should not make a copy of the strings, but just allocate an array of pointers and initialize it to point to the nodes themselves. This way you can preserve the node structures that could contain other information and avoid extra allocations.

还要注意，一旦有了节点指针数组和比较函数，您就可以可以使用 qsort 或其他排序功能，例如 timsort 或 mergesort 在最坏情况下的时间复杂度方面可能更合适。

Note also that once you have the array of node pointers and a comparison function, you can use qsort or other sorting functions such as timsort or mergesort which may be more appropriate in terms of worst case time complexity.

您的实现中存在多个问题：

There are multiple problems in your implementation:

• 循环测试而（t！= NULL& i< = len）是不正确的。测试应该是多余的，但是如果您坚持要测试 i ，则应该是 i< len 或如果 length_char 返回错误的字符串，则可能会超出 string 数组的末尾


• strcpy（strings [i ++]，t-> v.str）有语法错误，您可能是说 strcpy（strings [i ++]，t-> str）;



• 打印循环具有未定义的行为，因为您没有将 i 重置为 0 ，也不会在 i 中增加 i 循环体，因此您将 strings [i] 传递给 printf 和 i 应该为 len ，因此 strings [i] 的访问超出了分配数组的末尾。您可能会崩溃或无效的指针，或者偶然出现 printf 可能会忽略的空指针...应该是：

• the loop test while (t != NULL && i <= len) is incorrect. the tests should be redundant, but if you insist on testing i, it should be i < len or you might access beyond the end of the string array if length_char returned an incorrect count.
• strcpy(strings[i++], t->v.str) has a syntax error, you probably mean strcpy(strings[i++], t->str);

• the printing loop has undefined behavior because you do not reset i to 0 nor do you increment i in the loop body, so you pass strings[i] for all calls to printf and i should be len, so strings[i] accesses beyond the end of the allocated array. You might get a crash or an invalid pointer or by chance a null pointer that printf might ignore... It should be:

for (i = 0; i < len; i++) {
    printf("* %s\n", strings[i]);
}

这里是经过修改的版本：

Here is a modified version:

#include <stdio.h>
#include <stdlib.h>
#include "Listas_ligadas_char.h"

int cmp_char(const void *aa, const void *bb) {
    link_char a = *(const link_char *)aa;
    link_char b = *(const link_char *)bb;
    return strcmp(a->str, b->str);
}

link_char sort_char(link_char head) {
    if (head != NULL && head->next != NULL) {
        size_t i, len = length_char(head);
        link_char *array = malloc(sizeof(*array) * len);
        link_char t = head;
        for (i = 0; i < len; i++, t = t->next)
            array[i] = t;
        qsort(array, len, sizeof(*array), cmp_char);
        head = t = array[0];
        for (i = 1; i < len; i++)
            t = t->next = array[i];
        t->next = NULL;
        free(array);
    }
    return head;
}

int main() {
    link_char head = NULL;

    head = insertEnd_char(head, "fcb");
    head = insertEnd_char(head, "bvb");
    head = insertEnd_char(head, "slb");
    head = insertEnd_char(head, "fcp");

    head = sort_char(head);

    for (link_char t = head; t != NULL; t = t->next) {
        printf("* %s\n", strings[i]);
    }
    return 0;
}

注意：

• 将指针隐藏在typedef后面很容易出错。您应将 node_char 定义为 typedef struct node_char node_char 并使用 node_char * 到处都是。


• 在头文件中定义列表函数是不常规的。您可能对静态内联函数执行此操作，但是不应在头文件中定义全局函数，因为如果多个模块包含此头文件并获得链接，则这将导致名称冲突

• it is error prone to hide pointers behind typedefs. You should define node_char as typedef struct node_char node_char and use node_char * everywhere.
• it is unconventional to define the list functions in the header file. You might do this for static inline functions, but the global functions should not be defined in the header file as this will cause name clashes if multiple modules include this header file and get linked together.

这篇关于排序包含字符串的链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！