Как бы я изменил этот односвязный алгоритм сортировки списка, чтобы он сортировал по возрастанию должным образом?

Question

В настоящее время я пытаюсь отсортировать односвязный список в порядке убывания. Понимая, что не существует простого способа сделать это с помощью только следующего указателя, я выбрал метод сортировки списка сначала по возрастанию, а затем наоборот, чтобы элементы сортировались в порядке убывания.

Редактировать 1: Я пытаюсь убедиться, что элементы хранятся в порядке убывания в зависимости от того, как часто они доступны в связанном списке. Печать просто чтобы помочь мне проверить порядок связанного списка.

Редактировать 2: Минимальный рабочий пример по запросу:

main. c

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

typedef struct node_struct {
    char *name;
    int accessCount;
    struct node_struct *next;
}Knowledge_Node;

int knowledge_put();
int knowledge_get();
void printList();
void sortList();
void reverseList();

Knowledge_Node *head = NULL;

int main(int argc, char*argv[]){
  // Putting James into the linked list
  knowledge_put("James");

  //Get the James node twice
  knowledge_get("James");
  knowledge_get("James");

  //Add Carrie to the linked list
  knowledge_put("Carrie");

  //Get the Carrie node thrice
  knowledge_get("Carrie");
  knowledge_get("Carrie");
  knowledge_get("Carrie");

  // Add adams to linked list
  knowledge_put("Adams");
  knowledge_get("Adams");

  printList();
}

Добавить функцию узла

int knowledge_put(char * name) {
  Knowledge_Node *node = (Knowledge_Node *)malloc(sizeof(Knowledge_Node));
  if (node == NULL) {
      return -3;
  }
  node->name = (char *)malloc(sizeof(char) * 255);
  if (node->name == NULL){
      return -3;
  }
  strncpy(node->name, name, strlen(name) + 1);
  node->accessCount = 0;

  node->next = head;
  head = node;

  sortList();
}

Получить функцию узла

int knowledge_get(char * name){
    Knowledge_Node *search = head;

    while (search != NULL){
        if (strcmp(search->name, name) == 0){
            search->accessCount = search->accessCount + 1;
            sortList();
            return 0;
        }
        search = search->next;
    }
    return -1;
}

Функция списка сортировки:

void sortList(){
    Knowledge_Node *temp = head;
    Knowledge_Node *backPtr = head;
    Knowledge_Node *prevNode = NULL;

    while (temp != NULL){
        Knowledge_Node *nextNode = temp->next;
        //currentNode is assigned to temp, which is the pointer used to iterate through the list
        Knowledge_Node *currentNode = temp;
        //Doing a simple check to see if nextNode has something
        if (nextNode != NULL) {

            if(nextNode != NULL){
                if (currentNode->accessCount > nextNode->accessCount) {
                    //If previousNode is NULL it means currentNode is the head of //the linked list
                    //There's different logic to handle each case
                    if (prevNode != NULL){
                        prevNode->next = nextNode;
                        nextNode->next = currentNode;
                        currentNode->next = NULL;
                    } else if (prevNode == NULL){
                        currentNode->next = nextNode->next;
                        nextNode->next = currentNode;
                        head = nextNode;
                    }
                }
            }
        }
        //Assigning of previousNode. We'll need this for the linking/un-linking //process
        prevNode = currentNode;
        temp = temp->next;
    }
    reverseList();
} 

Функция обратного списка:

void reverseList(){
    //Initialise three pointers, which we'll use to reverse the links of the 
    //linked list
    Knowledge_Node *prevNode = NULL;
    Knowledge_Node *currentNode = head;
    Knowledge_Node *nextNode = NULL;

    //This is where the linked list reversal is done
    while (currentNode != NULL){
        nextNode = currentNode->next;
        currentNode->next = prevNode;
        prevNode = currentNode;
        currentNode = nextNode;
    }

    //Previous Node points to the last node in the original list, so let's 
    //make it the new head
    head = prevNode;
}

Функция печати списка:

void printList() {
    Knowledge_Node *temp = head;
    while (temp != NULL){
        printf("%s %d\n", temp->name, temp->accessCount);
        temp = temp->next;
    }
}

Ожидаемый вывод:

Carrie 3
James 2
Adams 1

Фактический вывод:

Adams 1
Carrie 3
James 2

Кажется, что сортировка по возрастанию работает нормально сам по себе, без обратной сортировки.

Надеюсь, кто-нибудь сможет мне на этом основать то, как я могу изменить алгоритм sortList, чтобы он сортировался в порядке возрастания, а затем в порядке убывания

Удален остаток контента для краткости

Answer 1

Я понял, что не так с вашим алгоритмом сортировки. Поскольку ваш связанный список представляет собой односвязный список, вы не можете использовать более эффективный алгоритм сортировки, такой как вставка. Поэтому я использовал пузырьковую сортировку в этом вопросе. В вашем алгоритме вы использовали только один l oop. Вы должны использовать вложенные две петли. См. Подробности о пузырьковой сортировке .

Кроме того, вместо сохранения указателя заголовка для списка в качестве недавно добавленного узла вы можете определить структуру с именем List и указатель заголовка в этом , Это более понятно.

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

typedef struct node_struct {
    char *name;
    int accessCount;
    struct node_struct *next;

}Knowledge_Node;


typedef struct list{

    Knowledge_Node* head;
    int count;

}List;

int knowledge_put();
int knowledge_get();
void printList();
void sortList();
void reverseList();

List* list1=NULL;

int main(int argc, char*argv[]){

   list1= (List*)malloc(sizeof(List)*1);
   list1->head=NULL;
   list1->count=0;
  // Putting James into the linked list
  knowledge_put("James");

  //Get the James node twice
  knowledge_get("James");
  knowledge_get("James");

  //Add Carrie to the linked list
  knowledge_put("Carrie");

  //Get the Carrie node thrice
  knowledge_get("Carrie");
  knowledge_get("Carrie");
  knowledge_get("Carrie");

  // Add adams to linked list
  knowledge_put("Adams");
  knowledge_get("Adams");

  sortList();
  reverseList();
  printList();
}

int knowledge_put(char * name) {
  Knowledge_Node *node = (Knowledge_Node *)malloc(sizeof(Knowledge_Node));
  if (node == NULL) {
      return -3;
  }
  node->name = (char *)malloc(sizeof(char) * 255);
  if (node->name == NULL){
      return -3;
  }
  strncpy(node->name, name, strlen(name) + 1);
  node->accessCount = 0;


  node->next = list1->head;
  list1->head = node;
  list1->count++;


  return -3;
}

int knowledge_get(char * name){
    Knowledge_Node *search = list1->head;

    while (search != NULL){
        if (strcmp(search->name, name) == 0){
            search->accessCount = search->accessCount + 1;

            return 0;
        }
        search = search->next;
    }
    return -1;
}

void sortList(){

    Knowledge_Node* sort=list1->head;
    Knowledge_Node* nextl=list1->head->next;
    Knowledge_Node* temp=(Knowledge_Node *)malloc(sizeof(Knowledge_Node));
    temp->name = (char *)malloc(sizeof(char) * 255);
    //const Knowledge_Node* c_sort=list1->head;

    for(int i=0;i<list1->count-1;i++){

        while(nextl!=NULL&&sort!=NULL){

            if(sort->accessCount > nextl->accessCount){

                temp->accessCount=sort->accessCount;
                strncpy(temp->name,sort->name,strlen(sort->name)+1);
                sort->accessCount=nextl->accessCount;
                strncpy(sort->name,nextl->name,strlen(nextl->name)+1);
                nextl->accessCount=temp->accessCount;
                strncpy(nextl->name,temp->name,strlen(temp->name)+1);

            }
            sort=sort->next;
            nextl=nextl->next;

        }
        sort=list1->head;
        nextl=list1->head->next;

    }


}

void reverseList(){
    //Initialise three pointers, which we'll use to reverse the links of the
    //linked list
    Knowledge_Node *prevNode = NULL;
    Knowledge_Node *currentNode = list1->head;
    Knowledge_Node *nextNode = NULL;

    //This is where the linked list reversal is done
    while (currentNode != NULL){
        nextNode = currentNode->next;
        currentNode->next = prevNode;
        prevNode = currentNode;
        currentNode = nextNode;
    }

    //Previous Node points to the last node in the original list, so let's
    //make it the new head
    list1->head = prevNode;
}

void printList() {
    Knowledge_Node *temp = list1->head;
    while (temp != NULL){
        printf("%s %d\n", temp->name, temp->accessCount);
        temp = temp->next;
    }
}