通过排序在链表中插入新元素 C

Question

我在链表的正确位置（插入排序）插入字符串时遇到问题。当我在链表中添加一些位置并通过键入“0”结束程序时，程序只显示第一个位置。我也怀疑“（strcmp（tmp->ch，new->ch）> 0）”它是否像我想的那样工作？（将新元素与当前元素进行比较（我的意思是它应该是'>'或'< ')). 我将非常感谢任何建议；）。这是我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_L 30

typedef struct elem{
    char ch[MAX_L];
    struct elem *next;
    struct elem *prev;
}   list_elem;

void add_to_list (list_elem *first, char ch[MAX_L])
{
    list_elem *new=(list_elem*)malloc(sizeof(list_elem));

    strcpy(new->ch, ch);
    list_elem *tmp=first;
    do
    {
        if(tmp->next==NULL)
        {
            tmp->next=new;
            new->prev=tmp;
            new->next=NULL;
        }
        if (strcmp(tmp->ch,new->ch)>0) //guess here should be inserted new element
        {
            new->prev=tmp->prev;
            new->next=tmp;
            tmp->prev=new;
        }
        else
        tmp=tmp->next;

    }while (tmp->next!=NULL);

}


void print_list(list_elem *first)
{
    first=first->next;
    if(first->ch==NULL)
    printf("lista jest pusta!!\n");
    while(first->next!=NULL){
    printf("%s\n",first->ch);
    first=first->next;}
    printf("%s\n",first->ch);
}



int main()
{
    list_elem *first=(list_elem*)calloc(1,sizeof(list_elem));
    first->next=NULL;
    first->prev=NULL;

    char a;
    char ch[MAX_L];
    printf("write ' 0 ' to end program.\n");
    printf("write smth to add it to list: \n");
        while(ch[0]!='0'){
        scanf("%s",&ch);
        add_to_list(first,ch);}
    print_list(first);
    return 0;
}

Answer 1

当您在 tmp 之前插入时，您似乎没有将 tmp->prev->next 设置为 new

为清楚起见：

if (strcmp(tmp->ch,new->ch)>0) //guess here should be inserted new element
    {
        new->prev=tmp->prev;
        new->next=tmp;
        tmp->prev=new;
    }

应该是：

if (strcmp(tmp->ch,new->ch)>0) //guess here should be inserted new element
    {
        tmp->prev->next=new;
        new->prev=tmp->prev;
        new->next=tmp;
        tmp->prev=new;
    }

旁注：使用 new 作为变量名通常不受欢迎，因为它不能立即识别为变量，因为大多数程序员都有 Java/C#/C++ 等方面的经验。 new 是关键字。

旁注 #2：不要投射 malloc。直到最近，当我阅读 this 堆栈线程时，我才这样做。这是一本非常好的读物。

Answer 2

list_elem *first=(list_elem*)calloc(1,sizeof(list_elem));

如何知道calloc成功与否？
检查first是否为NULL然后只访问first->next.

while(ch[0]!='0')

至此 ch 数组包含垃圾。那么如何将它与 ch[0] 和 '0' 进行比较呢？

scanf("%s",&ch);

%s 需要 char * 类型的参数，而 &ch 的类型是 char (*)[30].

如果用户输入长度 > sizeof(ch) 的字符串，您可能还想避免意外的缓冲区溢出。指定最大字段宽度来解决这个问题。

first=first->next; 在 print_list()

这里您刚刚跳过了第一个元素。

if(first->ch==NULL)

你真正想在这里做什么？很可能您想检查字符串 first->ch 是否为空。如果是，那么不是检查它的方法。而是检查 first->ch[0] == '[=30=]'

while(ch[0]!='0')

用于检查用户是否输入了0或其他字符串，这是不正确的方法。这将拒绝从 0 开始的字符串（例如“0bar”）

正确的方法是：

while((ch[0]!='0') || (strlen(ch) > 1))

在列表
中插入 new 节点后跳出循环
```
if (strcmp(tmp->ch,new->ch)>0) 
{  
     new->prev=tmp->prev;
     new->next=tmp;
     tmp->prev=new;
}
```
此处插入 new 节点后，if 表达式 strcmp(tmp->ch,new->ch)>0 将在所有后续循环迭代中保持 true，因为我们没有更改 tmp和 new。所以这会导致死循环。

唯一的例外是 tmp 是最后一个节点。

解决方案：

一旦 new 节点被插入到列表中就跳出循环。把break;写成上面最后一句就可以了 strcmp if

Answer 3

add_to_list 循环有问题：

do {
    if(tmp->next==NULL)
    {
        tmp->next=new;
        new->prev=tmp;
        new->next=NULL;
        break; // you must exit here, you don't want to go the "if" below...
    }
    if (strcmp(tmp->ch,new->ch)>0) 
    {
        if( tmp->prev != NULL ) 
        {
            tmp->prev->next = new; // link from previous to the new element 
        }
        new->prev=tmp->prev;
        new->next=tmp;
        tmp->prev=new;
        break; // you should exit here, work is done
    }
    else {
        tmp=tmp->next;
    }
} while (1); // try again

这里也有一个问题：

scanf("%s",&ch); // should be scanf("%s",ch);

对于你的问题：

Also i have doubts about "(strcmp(tmp->ch,new->ch)>0)" it is working as i'm thinking?

如果你错了，你会按相反的顺序排序，这样就很容易修正。

通过排序在链表中插入新元素 C

inserting new element in linked list with sorting C

c

sorting

string

linked-list

strcmp