如何按字母顺序将新节点添加到链表

Question

我正在尝试使用链表构建一个包含五首歌曲的音乐库，每首歌曲都有三个标签，歌曲名称、艺术家和流派。所以我接受用户的输入并将其添加到链接列表中，按字母顺序排列其歌曲名称。比如我有3首歌，不分艺术家和流派，歌名分别是Alpha、Zebra和Cool time，那么链表应该是这样的：Alpha、Cool time、Zebra。

以下是我的代码，但如果第一个字母的 ASCII 值大于 Head，它不会将新节点添加到正确的位置。它仅在 Head 为 NULL 或所有其他节点的 ASCII 值小于等于新节点的 ASCII 值时才有效。非常感谢您的帮助。

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

typedef struct node {
  char *artist;
  char *songName;
  char *genre;
  struct node *next;
} Node;

Node *insert (Node * Head, char *art, char *song, char *gen);
void print (Node * Head);

int main() {
  char art[25], song[25], gen[25];
  Node *Head = NULL;
  
  for (int j = 0; j < 5; j++) {
    printf("Artst --> ");
    gets(art);
    printf("Song name --> ");
    gets(song);
    printf("Genre --> ");
    gets(gen);
    Head = insert (Head, art, song, gen);
  }

  printf("The elements are:");
  print(Head);
}

Node *insert(Node * Head, char *art, char *song, char *gen) {
  Node *newelement;
  newelement = (Node *)malloc(sizeof(Node));

  newelement->artist = malloc(strlen(art) + 1);
  strcpy(newelement->artist, art);

  newelement->songName = malloc(strlen(song) + 1);
  strcpy(newelement->songName, song);

  newelement->genre = malloc(strlen(gen) + 1);
  strcpy(newelement->genre, gen);

  Node *check;
  check = (Node *)malloc(sizeof(Node));

  if (Head == NULL) {
    Head = newelement;
    Head->next = NULL;
  }
  else {
    check = Head;
      
    char this = newelement->songName[0];
    char that = check->songName[0];
      
    //"this" is the value of the first letter of the new songName;
    //"that" is the value of the first letter of the songName we are comparing to;
    //when "this" has a smaller value then that (ex. this is A, and that is B), then this should go before that.

    //if the head of the linked list has a letter that has a greatere ASCII value, then the newelement should be the new head
    if (this <= that) {
      newelement->next = Head;
      Head = newelement;
      return Head;
    }
    else if (this>that) {
      while (check->next != NULL) {
        check = check->next;
        that = check->songName[0];

        if (this <= that)
          break;
      }
    }

    Node *temp = check->next;
    check->next = newelement;
    newelement->next = temp;
  }

  return Head;
}

void print(Node * Head) {
  while (Head != NULL) {
    printf("\n");
    printf("%s\n", Head->artist);
    printf("%s\n", Head->songName);
    printf("%s\n", Head->genre);
    printf("\n");
    Head = Head->next;
  }
}

Answer 1

对于初学者这个内存分配

check = (Node *)malloc(sizeof(Node));

没有意义并会产生内存泄漏，因为分配的内存未被使用且未被释放。

在此代码段中

else if (this>that) {
  while (check->next != NULL) {
    check = check->next;
    that = check->songName[0];

    if (this <= that)
      break;
  }
}

Node *temp = check->next;
check->next = newelement;
newelement->next = temp;

在节点check之后插入歌曲名称小于节点check歌曲名称的新节点。

此外，函数 gets 不安全且不受 C 标准支持。

而是使用 scanf，例如

scanf( " %24[^\n]", art );

或fgets喜欢

fgets( art, sizeof( art ), stdin );
art[ strcspn( art, "\n" ) ] = '[=13=]';

函数可以通过以下方式声明和定义

Node * insert( Node *Head, const char *art, const char *song, const char *gen ) 
{
    Node *newelement = malloc(sizeof( Node ) );

    newelement->artist = malloc( strlen( art ) + 1);
    strcpy( newelement->artist, art );

    newelement->songName = malloc( strlen( song ) + 1 );
    strcpy( newelement->songName, song );

    newelement->genre = malloc( strlen( gen ) + 1 );
    strcpy( newelement->genre, gen );

    if ( Head == NULL || strcmp( song, Head->songName ) < 0 )
    {
        newelement->next = Head;
        Head = newelement;
    }
    else 
    {
        Node *current = Head;
      
        while ( current->next != NULL && !( strcmp( song, current->next->songName ) < 0 ) )
        {
            current = current->next;
        }

        newelement->next = current->next;
        current->next = newelement;
    }

    return Head;
}

注意作为字符串指针的参数应该有修饰符const.

如何按字母顺序将新节点添加到链表

How to add a new node to a linked list alphabetically

c

sorting

struct

singly-linked-list

function-definition