c - 排序链接列表在 C 中无法正常工作

Question

对 C 来说完全陌生，我试图在 C 中创建一个链接列表，按字母顺序对预先存在的 char 数组进行排序。每个字符都分配有一个索引。所以listInsert函数应该将每个字符串插入到链表中，并按字母顺序对它们进行排序，这样当调用listPrintForward时，链表中的项目将按字母顺序打印。

这是我运行程序时的当前输出。

http://imgur.com/cZxx0rr

INSERT:
bravo oscar romeo delta whisky alpha
foxtro sierra yankee lima echo
golf november victor charlie mike
zulu tango kilo quebec hotel
juliet xray papa uniform india

FORWARD: 0 entries
india uniform papa xray juliet hotel
quebec kilo tango zulu mike
charlie victor november golf echo
lima yankee sierra foxtrot alpha
whisky delta romeo oscar bravo

正如你所看到的，我的 listInsert 函数当前所做的就是将它们插入到链接列表中(我认为)，并且当调用 printForward 函数时，它会反转链接列表的内容，而此时它应该打印链接的内容按字母顺序列出。

我想要发生的输出应该是:

INSERT:
bravo oscar romeo delta whisky alpha
foxtro sierra yankee lima echo
golf november victor charlie mike
zulu tango kilo quebec hotel
juliet xray papa uniform india

FORWARD: 0 entries
alpha bravo charlie delta echo foxtrot
golf hotel india juliet kilo
lima mike november oscar papa
quebec romeo sierra tango uniform
victor whisky xray yankee zulu 

有谁知道如何解决这个问题或者我做错了什么？完整代码如下:

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

#define SUCCESS 0
#define FAIL    1

char *phonetic[] = { "alpha", "bravo", "charlie", "delta", "echo", "foxtrot",
                     "golf", "hotel", "india", "juliet", "kilo", "lima", "mike",
                     "november", "oscar", "papa", "quebec", "romeo", "sierra",
                     "tango", "uniform", "victor", "whisky", "xray", "yankee", 
                     "zulu" };

unsigned char indexes[] = { 1, 14, 17, 3, 22, 0, 5, 18, 24, 11, 4, 6, 13, 21,
                            2, 12, 25, 19, 10, 16, 7, 9, 23, 15, 20, 8 };                       

// represents an entry in the linked-list
struct listEntry
{
  char *data_p;               // pointer to the entry's string
  struct listEntry *prev_p;   // pointer to previous entry in the linked-list  
  struct listEntry *next_p;   // pointer to next entry in the linked-list
};

// represents the linked-list
struct list
{
  int entryCount;             // number of entries present in the linked-list
  struct listEntry *head_p;   // pointer to the first entry in the list  
  struct listEntry *tail_p;   // pointer to the last entry in the list
};

// Dynamically allocate & initialise an empty linked list
int listCreate(struct list** list_p2)
{
  // allocate struct list from heap 
  *list_p2 = (struct list*) malloc(sizeof(**list_p2));

  if (*list_p2 != NULL)
  {
    // zero-initialize the list structure 
    memset(*list_p2, 0, sizeof(**list_p2));
    return SUCCESS;    
  }

  return FAIL;
}

// Free all entries in the linked-list and the list structure
int listDestroy(struct list *list_p)
{
  if (list_p != NULL)
  {
    struct listEntry *entry_p = list_p->head_p;

    while (entry_p != NULL)
    {
      struct listEntry *next_p = entry_p->next_p;
      // free the current entry
      free(entry_p);
      // move to the next entry
      entry_p = next_p;
    }

    // free list structure
    free(list_p);
  }

  return FAIL;
}

// Traverse the linked-list from head to tail printing out
// the string data from each list entry
int listPrintForward(struct list *list_p)
{ 
  if (list_p)
  {    
    struct listEntry *entry_p = list_p->head_p;
    int count = 0;

    printf("FORWARD: %d entries\n", list_p->entryCount);
    while (entry_p != NULL)
    {
      if ((count > 0) && (count % 5 == 0))
      {
        printf("%s\n", entry_p->data_p);
      }
      else
      {      
        printf("%s ", entry_p->data_p);
      }

      if (entry_p == list_p->tail_p)
        printf("\n");

      entry_p = entry_p->next_p;
      fflush(stdout);
      count++;         
    }

    return SUCCESS;
  }

  return FAIL;
}

// Traverse the linked-list from tail to head printing out
// the string data from each list entry
int listPrintReverse(struct list *list_p)
{ 
  if (list_p)
  {    
    struct listEntry *entry_p = list_p->tail_p;
    int count = 0;

    printf("REVERSE: %d entries\n", list_p->entryCount);   
    while (entry_p != NULL)
    {
      if ((count > 0) && (count % 5 == 0))
      {
        printf("%s\n", entry_p->data_p);
      }
      else
      {      
        printf("%s ", entry_p->data_p);
      }

      if (entry_p == list_p->head_p)
        printf("\n");

      entry_p = entry_p->prev_p;
      fflush(stdout);
      count++;         
    }

    return SUCCESS;
  }

  return FAIL;
}

// Insert the given string into the linked-list such that the
// entries in the linked-list are in alphabetical order
int listInsert(struct list *list_p, char *string_p)
{ 
    struct listEntry *temp;
    temp=(struct listEntry *)malloc(sizeof(struct listEntry)); 
    temp->data_p = string_p;

    if (list_p->head_p == NULL)
    {
        //List is Empty
        list_p->head_p = temp;
        temp->next_p = NULL;
    }
    else
    {
        temp->next_p =list_p->head_p;
        list_p->head_p = temp;
    }


  return FAIL;  
}

int main(int argc, char **argv)
{
  struct list *list_p = NULL;
  (void) argc;
  (void) argv;

  if (listCreate(&list_p) == SUCCESS)
  {
    unsigned int count;

    // insert every word in the phonetic alphabet into the
    // linked-list.
    printf("INSERT:\n");
    for (count = 0; count < sizeof(indexes); count++)
    {
      if ((count > 0) && (count % 5 == 0))
      {
        printf("%s\n", phonetic[indexes[count]]);
      }
      else
      {
        printf("%s ", phonetic[indexes[count]]);
      }
      listInsert(list_p, phonetic[indexes[count]]);
    }
    printf("\n");

    // print out the list in alphabetical order
    listPrintForward(list_p);
    // print out the list in reverse alphabetical order
    listPrintReverse(list_p); 

    // Destroy the linked list and free all associated memory
    listDestroy(list_p);               
  }

  return SUCCESS;
} 

Answer 1

您正在按索引顺序插入条目。您应该对 temp->p_data 执行 strcmp 并从头到尾遍历列表并插入节点。

参见http://analgorithmaday.blogspot.nl/2011/01/insertion-sort-using-linked-list.html

提示

问候

约翰