c - 我将如何修改这个单链表排序算法，以便它正确地按升序排序？

Question

我目前正在尝试按降序对单向链表进行排序。意识到没有直接的方法可以仅使用 next 指针来做到这一点，我选择了首先按升序对列表进行排序，然后反转列表的方法，以便项目按降序排序。

编辑 1: 我正在尝试确保根据项目在链表中的访问频率以降序存储项目。打印只是为了帮我检查链表的顺序。

编辑 2:要求的最低工作示例:

主.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

我发现你的排序算法出了什么问题。由于您的链表是单链表，因此您不能使用更有效的排序算法，如插入排序。所以我在这件事上使用了冒泡排序。在您的算法中，您只使用了一个循环。您必须使用嵌套的两个循环。查看有关 bubble sort 的详细信息.

此外，您可以定义一个名为 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;
    }
}