如何将新节点添加到字母顺序的链接列表

Question

我正在尝试使用链接列表来构建一个音乐库，每首歌曲都有三个标签，即歌曲名称，艺术家和类型。因此，我将用户的输入添加到链接列表中，并以其歌曲名称字母顺序排列。例如，如果我有3首歌曲，无论艺术家和类型如何，歌曲名称是Alpha，Zebra和Cool Pime，那么链接的列表应该按以下顺序：Alpha，Cool Time，Zebra。

以下是我的代码，但是如果第一个字母的ASCII值大于头部，则不会将新节点添加到正确的位置。它仅在头为null时或所有其他节点的ASCII值均为＆lt; =对新节点的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" ) ] = '\0';

该函数可以按以下方式声明和定义。

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;
}

请注意，作为字符串指针的参数应具有限定符 <代码>常量。