How do I sort Linked-list created with structure, Alphabetically in C?-CodePudding

Im supposed to make program that works with linked-Lists with these functions (described under my code) using structure

This is the code I've tried:

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

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];

   //testing
    assert (sizeof(TITEM) == sizeof(TITEM *)   sizeof(char *)   24 * sizeof(char));
    l = NULL;
    l = newItem("PA1", l);
    l = newItem("PA2", l);
    l = newItem("UOS", l);
    l = newItem("LIN", l);
    l = newItem("AG1", l);
    assert (l
            && !strcmp(l->m_Name, "AG1"));
    assert (l->m_Next
            && !strcmp(l->m_Next->m_Name, "LIN"));
    assert (l->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Name, "UOS"));
    assert (l->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Name, "PA2"));
    assert (l->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Name, "PA1"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next == NULL);
    l = sortList(l, 1);
    assert (l
            && !strcmp(l->m_Name, "AG1"));
    assert (l->m_Next
            && !strcmp(l->m_Next->m_Name, "LIN"));
    assert (l->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Name, "PA1"));
    assert (l->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Name, "PA2"));
    assert (l->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Name, "UOS"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next == NULL);
    l = newItem("programming and algorithmic I", l);
    l = newItem("AAG", l);
    assert (l
            && !strcmp(l->m_Name, "AAG"));
    assert (l->m_Next
            && !strcmp(l->m_Next->m_Name, "programming and algorithmic I"));
    assert (l->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Name, "AG1"));
    assert (l->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Name, "LIN"));
    assert (l->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Name, "PA1"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Name, "PA2"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next->m_Name, "UOS"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next == NULL);
    l = sortList(l, 0);
    assert (l
            && !strcmp(l->m_Name, "programming and algorithmic I"));
    assert (l->m_Next
            && !strcmp(l->m_Next->m_Name, "UOS"));
    assert (l->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Name, "PA2"));
    assert (l->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Name, "PA1"));
    assert (l->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Name, "LIN"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Name, "AG1"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next->m_Name, "AAG"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next == NULL);
    freeList(l);
    l = NULL;
    strncpy (tmp, "PA1", sizeof(tmp) - 1);
    tmp[sizeof(tmp) - 1] = '\0';
    l = newItem(tmp, l);
    strncpy (tmp, "PA2", sizeof(tmp) - 1);
    tmp[sizeof(tmp) - 1] = '\0';
    l = newItem(tmp, l);
    strncpy (tmp, "UOS", sizeof(tmp) - 1);
    tmp[sizeof(tmp) - 1] = '\0';
    l = newItem(tmp, l);
    strncpy (tmp, "LIN", sizeof(tmp) - 1);
    tmp[sizeof(tmp) - 1] = '\0';
    l = newItem(tmp, l);
    strncpy (tmp, "AG1", sizeof(tmp) - 1);
    tmp[sizeof(tmp) - 1] = '\0';
    l = newItem(tmp, l);
    assert (l
            && !strcmp(l->m_Name, "AG1"));
    assert (l->m_Next
            && !strcmp(l->m_Next->m_Name, "LIN"));
    assert (l->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Name, "UOS"));
    assert (l->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Name, "PA2"));
    assert (l->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Name, "PA1"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next == NULL);
    l = sortList(l, 1);
    assert (l
            && !strcmp(l->m_Name, "AG1"));
    assert (l->m_Next
            && !strcmp(l->m_Next->m_Name, "LIN"));
    assert (l->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Name, "PA1"));
    assert (l->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Name, "PA2"));
    assert (l->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Name, "UOS"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next == NULL);
    strncpy (tmp, "programming and algorithmic I", sizeof(tmp) - 1);
    tmp[sizeof(tmp) - 1] = '\0';
    l = newItem(tmp, l);
    strncpy (tmp, "AAG", sizeof(tmp) - 1);
    tmp[sizeof(tmp) - 1] = '\0';
    l = newItem(tmp, l);
    assert (l
            && !strcmp(l->m_Name, "AAG"));
    assert (l->m_Next
            && !strcmp(l->m_Next->m_Name, "programming and algorithmic I"));
    assert (l->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Name, "AG1"));
    assert (l->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Name, "LIN"));
    assert (l->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Name, "PA1"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Name, "PA2"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next->m_Name, "UOS"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next == NULL);
    l = sortList(l, 0);
    assert (l
            && !strcmp(l->m_Name, "programming and algorithmic I"));
    assert (l->m_Next
            && !strcmp(l->m_Next->m_Name, "UOS"));
    assert (l->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Name, "PA2"));
    assert (l->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Name, "PA1"));
    assert (l->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Name, "LIN"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Name, "AG1"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next
            && !strcmp(l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next->m_Name, "AAG"));
    assert (l->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next->m_Next == NULL);
    freeList(l);
    return EXIT_SUCCESS;
}

/////////////////////////////

Structure:

TITEM structure represents an element of a unidirectionally linked linked list. The structure declaration is fixed in the test environment, your implementation will use this unchanged declaration (it cannot/must not change it). The structure contains the following components:

m_Next pointer to the next element in the linked list, NULL value for the last element,

m_Name a string with the name of the list element,

////////////////////////////

Functions:

(Only these three functions are mandatory all others are optional)

newItem - This function creates a new TITEM record. Additionally, the function copies the name and reference to the next element from the parameters into the m_Next and m_Name folders. (done)

freeList - The function serves to conveniently delete the connection list. (done)

sortList - The function is used to sort elements in a linked list. The parameter is the start of the ordered linked list l and the desired ascending sorting. The function rearranges the elements in the specified list so that the order matches the desired arrangement. The function must not free the elements of the original list. On the contrary, it must link the references of existing elements and return a pointer to the first element of the resulting list.

The sorting criterion is the name in the list element (m_Name), the strings will be compared case sensitive. The desired order is ascending (parameter ascending is not zero) or descending (parameter ascending is equal to zero). The function must ensure that the ordering is stable.

Thanks for any help

My attempt is shown in the functions sortList, compare, changeListPointers but I don't know how to do it or if im on the right path to do it.

If there is an easy solution that will abide by the rules mentioned above I would be very glad for any help I've been stuck for a week.

CodePudding user response：

From your compare function it seems like you always want to compare two adjacent names. I would suggest sorting with merge sort, where you will compare nodes that are not necessarily adjacent.

Here are some functions you could use for implementing merge sort:

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);
}