c语言 - 无法对链表进行排序

Question

我正在尝试按升序对列表进行排序。

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

struct city {
char ISO[3];
char name[20];
unsigned long inhabitants;
};
typedef struct city City;
struct listnode {
City thecity;
struct listnode *nextPtr;
};
typedef struct listnode ListNode;

ListNode *sortForInhabitants(ListNode *, size_t );
int main(){
/* stuff to initialize list */

ListNode sortedlist = *sortForInhabitants(&startPtr,num_elem);

/* printf the output */
}

ListNode *sortForInhabitants(ListNode *sPtr, size_t num_nodes){
ListNode *newsortedlist = NULL;
ListNode *prevsortedPtr;
ListNode *prevUNsortedPtr = sPtr;
ListNode *exchangePtr;
ListNode *currUNsortedPtr = sPtr;
ListNode *tempPtr;
for (size_t i=1; i<=num_nodes; ++i){
exchangePtr = prevUNsortedPtr;
for (size_t i=1; i<=num_nodes; ++i){
if (exchangePtr->thecity.inhabitants > currUNsortedPtr->thecity.inhabitants){
tempPtr = exchangePtr;
exchangePtr = currUNsortedPtr;
currUNsortedPtr = tempPtr;
}
}
prevUNsortedPtr = prevUNsortedPtr->nextPtr;
if (newsortedlist==NULL){
ListNode *newsortlinkPtr = calloc(1,sizeof(ListNode));
if (newsortlinkPtr){
newsortlinkPtr->thecity.inhabitants = exchangePtr->thecity.inhabitants;
newsortlinkPtr->nextPtr = NULL;
newsortedlist = newsortlinkPtr;
prevsortedPtr = newsortlinkPtr;
} else {
printf("nNo memory.n");
}
} else {
ListNode *newsortlinkPtr = calloc(1,sizeof(ListNode));
if (newsortlinkPtr){
newsortlinkPtr->thecity.inhabitants = exchangePtr->thecity.inhabitants;
newsortlinkPtr->nextPtr = NULL;
prevsortedPtr->nextPtr = newsortlinkPtr;
prevsortedPtr = newsortlinkPtr;
} else {
printf("nNo memory.n");
}
}
}
return newsortedlist;
}

输出：

Unsorted list:
PA Palermo 673735
ME Messina 236962
CT Catania 313396
TP Trapani 68528
AG Agrigento 59605
RG Ragusa 73500
Sorted list:
673735
236962
313396
68528
59605
73500

为什么？我花了很长时间，但我看不到努力的效果。

另外，我想知道是否建议创建一个新的 ListNode(就像我在这个排序函数中所做的那样(或者只是使用指针"调整"以前的 ListNode......什么会更好？

Answer 1

我假设您正在实现选择排序算法。您的辅助循环有一个非常明显的错误，您错过了。

ListNode *sortForInhabitants(ListNode *sPtr, size_t num_nodes){
// initial code
// this loop is for finding the i_th smallest element
for (size_t i=1; i<=num_nodes; ++i){
exchangePtr = prevUNsortedPtr;
// your second loop is wrong. Correct access of the loop is given below.
// as you have already found (i-1) smallest elements, you are now going
// to search through the rest of the linked list.
for (size_t j=i+1; j<=num_nodes; ++j){
if (exchangePtr->thecity.inhabitants > currUNsortedPtr->thecity.inhabitants){
tempPtr = exchangePtr;
exchangePtr = currUNsortedPtr;
currUNsortedPtr = tempPtr;
}
// rest of your code
}