排序带有升序/降序选项的链表

Question

我需要实现sortList，它应该按名称对链表进行排序，第二个参数决定它应该升序还是降序排序。

newItem和freeList函数是强制性的，但我已经实现了它们，没有问题。

我的问题是功能sortList，这取决于compare，和changeListPointers:我不能使它工作如预期。

这是我试过的代码:

typedef struct TItem {
struct TItem *m_Next;
char *m_Name;
char m_Secret[24];
} TITEM;
//mandatory function
TITEM *newItem(const char *name, TITEM *next) {
TITEM *result = (TITEM *) malloc((sizeof(TITEM)) + 4);  //creates new Item, if the sizeof is 0 then it adds 4B
result->m_Next = next;
result->m_Name = strdup(name);
return result;
}
int compare(TITEM * firstName, TITEM * secondName) {
if(firstName->m_Name != NULL || secondName->m_Next->m_Name != NULL){
return strcmp(firstName->m_Name, secondName->m_Next->m_Name);
}else {
// if the last list is null what next?
}
}
int changeListPointers(TITEM * firstBox, TITEM * secondBox) {   //
if(firstBox->m_Name != NULL || secondBox->m_Next->m_Name != NULL){
firstBox->m_Name, secondBox->m_Next->m_Name;
return 1;
}else{
return 0;
}
}
//mandatory function
TITEM *sortList(TITEM *l, int ascending) {  // should sort the lists by m_Name
int compareWords = compare(l, l);
if(ascending == 0){ //sort in descending order
if(compareWords >= 1){
//  redo pointers
changeListPointers(l,l);
}else{
//first one is bigger second one is smaller do nothing
}
}else{
}
}
//mandatory function
void freeList(TITEM *src) {     //frees up allocated memory
//loops through the link list until it finds the last one which will have NULL value
while (src != NULL) {       
TITEM *next = src->m_Next;  
free(src);                  //frees the list value
src = next;
}
}
int main(int argc, char *argv[]) {
TITEM *l;
char tmp[50];

如果有一个简单的解决方案来修复我的代码，我将不胜感激。

Answer 1

从你的compare函数，似乎你总是想比较两个相邻的名称。我建议使用归并排序，你可以比较那些不一定相邻的节点。

这里有一些函数可以用来实现合并排序:

int listSize(TITEM *l) {
int count = 0;
while (l != NULL) {
count++;
l = l->m_Next;
}
return count;
}
// Split list in two halves, the pointer to the second halve is returned
TITEM *splitList(TITEM *l) {  
int halfCount = listSize(l) / 2;
if (halfCount == 0) return NULL;
TITEM *curr = l;
while (--halfCount) {
curr = curr->m_Next;
}
TITEM *l2 = curr->m_Next;
curr->m_Next = NULL;
return l2;
}
// Compare two nodes by their name, negating the result when descending is indicated
int compare(TITEM *l1, TITEM * l2, int ascending) {
int cmp = strcmp(l1->m_Name, l2->m_Name);
return ascending ? cmp : -cmp;
}
// Merge two sorted lists into one sorted list
TITEM *mergeLists(TITEM *l1, TITEM *l2, int ascending) {
TITEM *dummy = newItem("", NULL);
TITEM *tail = dummy;
while (l1 != NULL && l2 != NULL) {
if (compare(l1, l2, ascending) > 0) {
tail->m_Next = l2;
l2 = l2->m_Next;
} else {
tail->m_Next = l1;
l1 = l1->m_Next;
}
tail = tail->m_Next;
}
tail->m_Next = l1 == NULL ? l2 : l1;
return dummy->m_Next;
}
//mandatory function
TITEM *sortList(TITEM *l, int ascending) {  // should sort the lists by m_Name
TITEM *l2 = splitList(l);
if (l2 == NULL) return l; // base case
return mergeLists(sortList(l, ascending), sortList(l2, ascending), ascending);
}