时间戳

首页 > 解决方案 > 无法对动态分配节点的链表进行排序

c - 无法对动态分配节点的链表进行排序

问题描述

我的程序从用户那里接收任意数量的单词，并且仅在用户键入三个星号 (***) 时停止。这些单词将存储在一个链表中并排序，但是当我尝试打印列表时，列表中的元素没有排序。为什么会这样？

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

#define MAX_STRING_LEN 32  // Limit on length of each string


/* Link list node */
struct Node
{
    int data;
    struct Node* next;
};

// Function to insert a given node in a sorted linked list
void sortedInsert(struct Node**, struct Node*);

// function to sort a singly linked list using insertion sort
void insertionSort(struct Node **head_ref)
{
    // Initialize sorted linked list
    struct Node *sorted = NULL;

    // Traverse the given linked list and insert every
    // node to sorted
    struct Node *current = *head_ref;
    while (current != NULL)
    {
        // Store next for next iteration
        struct Node *next = current->next;

        // insert current in sorted linked list
        sortedInsert(&sorted, current);

        // Update current
        current = next;
    }

    // Update head_ref to point to sorted linked list
    *head_ref = sorted;
}

/* function to insert a new_node in a list. Note that this
  function expects a pointer to head_ref as this can modify the
  head of the input linked list (similar to push())*/
void sortedInsert(struct Node** head_ref, struct Node* new_node)
{
    struct Node* current;
    /* Special case for the head end */
    if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
    {
        new_node->next = *head_ref;
        *head_ref = new_node;
    }
    else
    {
        /* Locate the node before the point of insertion */
        current = *head_ref;
        while (current->next!=NULL &&
                current->next->data < new_node->data)
        {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */

/* Function to print linked list */
void printList(struct Node *head)
{
    struct Node *temp = head;
    while(temp != NULL)
    {
        printf("%s \n ", temp->data);
        temp = temp->next;
    }
}

/* A utility function to insert a node at the beginning of linked list */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

    /* put in the data  */
    new_node->data  = new_data;

    /* link the old list off the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}


// Main function
int main()
{
    struct Node *a = NULL;

    int index=1;
    int i;
    char * strings[MAX_STRINGS]; // Array of pointers

    do
    {

        strings[index] = malloc(MAX_STRING_LEN * sizeof(char));
        printf("Please input a word : ", index);
        fgets(strings[index],MAX_STRING_LEN,stdin);

        strtok(strings[index], "\n")=='\0';

    }
    while(strcmp(strings[index++], "***")!=0);

    printf("\nThe input set, in alphabetical order:\n");

    for (i = 1; i < index-1; i++)
    {
    push(&a, strings[i]);    
    }

    insertionSort(&a);
    printList(a);
    free(strings[i]);

    return 0;
}

输入：

pear
apple
***

给定输出：

 pear
 apple

预期输出：

apple
pear

标签： clinked-list

解决方案

Hii 我花了一些时间思考你想做什么。并看到您的代码存在许多问题。我想你想要这样的东西。

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

#define MAX_STRING_LEN 32  // Limit on length of each string
#define MAX_STRINGS 100 // Limit the number of strings

struct Node {
    char *data;
    struct Node *next;
};

void sortedInsert(struct Node **head_ref, struct Node* new_node) {
    struct Node *counter = *head_ref;
    struct Node *previous = NULL;
    while (counter != NULL && strcmp(counter->data,new_node->data) < 0){
        previous = counter;
        counter = counter->next;
    }
    if (previous != NULL) {
        previous->next = new_node;
        new_node->next = counter;
    } else {
        new_node->next = *head_ref;
        *head_ref = new_node;
    }
}

void push(struct Node **head_ref, char *new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data  = new_data;
    new_node->next = NULL;
    if (!head_ref) {
        *head_ref = new_node;
        return;        
    }
    sortedInsert(head_ref,new_node);
}

void printList(struct Node *head) {
    struct Node *temp = head;
    while(temp != NULL) {
        printf("%s\n", temp->data);
        temp = temp->next;
    }
}

void freeLinkedList(struct Node *head) {
    struct Node *next;
    while(head) {
        next = head;
        head = head->next;
        free(next);
    }
}
// Main function
int main() {
    struct Node *a = NULL;
    int index = 0;
    int i;
    char * strings[MAX_STRINGS]; // Array of pointers
    do {
        strings[index] = malloc(MAX_STRING_LEN * sizeof(char));
        printf("Please input a word %d: ", index);
        scanf("%s",strings[index]);
        fflush(stdin);
    } while(strcmp(strings[index++], "***") != 0 && index < MAX_STRINGS);
    printf("\nThe input set, in alphabetical order:\n");
    for (i = 0; i < index-1; i++) push(&a, strings[i]);
    printList(a);
    return 0;
}

我已经对其进行了测试，并且效果很好。如果您有任何疑问，我想清除它们。如果您想知道您的代码中有什么错误，请随时询问。

推荐阅读