2

I have a project, that generates a Linked List, delete them and show this at the User. Now, I want to sort the list. My struct:

typedef struct YugiohCard {
    char Name[100];
    char CardType[20];
    int Level;
    int Rank;
    int PendulumStage;
    int Link;
    int ATK;
    int DEF;
    char Property[20];
    char MonsterType[40];
    char CardType2[30];
    char Description[500];
    struct YugiohCard* pNext;
    struct YugiohCard* pPrev;
} struYugiohCard;

When the User says: "CardType2 Ascending" then the program sort the list by CardType2 and Ascending.

In this case alphematicaly. It is also possible to sort by the other struct contents(Monstertyp, ATK, DEF, etc.). Ascending or Descending.

How can I do it without things from C++?

Sorry for my bad English. I'm not very well at this.

Edit: Here is my complete Code:

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "time.h"

typedef struct YugiohCard {
    char Name[100];
    char CardType[20];
    int Level;
    int Rank;
    int PendulumStage;
    int Link;
    int ATK;
    int DEF;
    char Property[20];
    char MonsterType[40];
    char CardType2[30];
    char Description[500];
    struct YugiohCard* pNext;
    struct YugiohCard* pPrev;
} struYugiohCard;

bool OutputList(struYugiohCard* pStart)
{
    int count = 0;
    struYugiohCard* current = pStart;  // Initialize current 
    while (current != NULL)
    {
        count++;
        current = current->pNext;
    }

    char answer[265];
    int CountetCardsThatWillBeOutputet;
    printf("How many Yugioh cards would you like to spend? 0 means all, 
            otherwise the number counts. Number of elements in list: %i Input:", 
            count);
    fgets(answer, 265, stdin);
    CountetCardsThatWillBeOutputet = atoi(answer);
    int countOutputetCards = 0;

    if (CountetCardsThatWillBeOutputet > count)
    {
        printf("Please enter a correct number!");
        system("pause");
        return false;
    }
    else if (CountetCardsThatWillBeOutputet == 0)
    {
        CountetCardsThatWillBeOutputet = count;
    }

    system("cls");
    printf("%10s %20s %10s %10s %20s %10s %10s %10s %20s %20s %20s %20s\n", 
    "Name", "CardType", "Level", "Rank", "PendulumStage", "Link", "ATK", 
    "DEF", "Property", "MonsterType", "CardType2", "Description");
    for (struYugiohCard* pOut = pStart; pOut != NULL; pOut = pOut->pNext)
    {
        printf("%10s %20s %10i %10i %20i %10i %10i %10i %20s %20s %20s 
                %20s\n", pOut->Name, pOut->CardType, pOut->Level, pOut- 
                >Rank, pOut->PendelumStage, pOut->Link, pOut->ATK, pOut->DEF, 
                pOut->Property, pOut->MonsterType, pOut->CardType2, pOut- 
                >Description);
        countOutputetCards++;
        if (countOutputetCards == CountetCardsThatWillBeOutputet )
        {
            break;
        }
    }
    system("pause");
}

void DeleteList(struYugiohCard** head_ref)
{
    struct YugiohCard* prev = *head_ref;

    while (*head_ref)
    {
        *head_ref = (*head_ref)->pNext;
        free(prev);
        prev = *head_ref;
    }
}

struYugiohCard* CreateList()
{
    system("cls");
    char answer[265];
    int countedCards;
    printf("\nHow many Yugioh cards would you like to create? Please enter 
            only enter numbers, otherwise you'll crash.");
    fgets(answer, 265, stdin);
    countedCards = atoi(answer);

    struYugiohCard* pFirst = NULL;

    for (int i = 0; i < countedCards; i++)
    {
        struYugiohCard* pNew = 
            (struYugiohCard*)malloc(sizeof(struYugiohCard));
        if (pNew == NULL) break;
        pNew->Name[0] = 'A' + rand() % 26;
        pNew->Name[1] = '\0';
        pNew->CardType[0] = 'A' + rand() % 26;
        pNew->CardType[1] = '\0';
        pNew->Level = 1 + rand() % 12;
        pNew->Rank = 1 + rand() % 13;
        pNew->PendulumStage = 1 + rand() % 12;
        pNew->Link = 1 + rand() % 8;
        pNew->ATK = rand() % 10001;
        pNew->DEF = rand() % 10001;
        pNew->Property[0] = 'A' + rand() % 26;
        pNew->Property[1] = '\0';
        pNew->MonsterType[0] = 'A' + rand() % 26;
        pNew->MonsterType[1] = '\0';
        pNew->CardType2[0] = 'A' + rand() % 26;
        pNew->CardType2[1] = '\0';
        pNew->Description[0] = 'A' + rand() % 26;
        pNew->Description[1] = '\0';
        if (pFirst != NULL)
        {
            pNew->pNext = pFirst;
        }
        else
        {
            pNew->pNext = NULL;
        }
        pFirst = pNew;
    }
    return pFirst;
}

int main()
{   
    struYugiohCard* pStart = NULL;
    printf("\nIMPORTANT: Please maximize the window, otherwise it will not 
            represents everything correctly.");
    do
    {
        system("cls");
        printf("\nDo you want to create a Yugioh card list (YKE) that 
                Delete Yugioh card list(YKL), a single Yugioh card 
                delete(EYKL), sort the list(YKS), the Yugioh- 
                Output card list(YKA) or the program 
                close(Prsc):");
        char answer[265];
        fgets(answer, 265, stdin);
        if (strcmp(answer, "YKE\n") == 0)
        {
            pStart = CreateList();
        }
        else if (strcmp(answer, "YKS\n") == 0)
        {
            //SortList(pStart);
        }
        else if (strcmp(answer, "EYKL\n") == 0)
        {
            //DeleteOneCard(pStart);
        }
        else if (strcmp(answer, "YKL\n") == 0)
        {
            DeleteList(&pStart);
        }
        else if (strcmp(answer, "YKA\n") == 0)
        {
            OutputList(pStart);
        }
        else if (strcmp(answer, "Prsc\n") == 0)
        {
            return 0;
        }
        else
        {
            printf("Please enter a shortcut!");
        }
    } while (true);
}
Improve this question
16
  • Create an array of pointers. Have the array members point to the list members. Then follow this answer. Then, string the list members into the sorted order. Commented Jan 8, 2020 at 8:11
  • First, the list exist already, but I need it to sort. I also not understand the answer. I'm new in C. Please an Example with a String and Integer ASC and DESC. And Explain how it works. Commented Jan 8, 2020 at 8:13
  • Maybe this helps Commented Jan 8, 2020 at 8:15
  • @Jabberwocky, Sorry no. In your comment Link, the questioner have one struct content and I have 12. That help with one, but not with 12. Commented Jan 8, 2020 at 8:21
  • @a.b_om it doesn't matter if the struct has 1 or 100 fields, you're dealing with pointers here. Commented Jan 8, 2020 at 8:23

1 Answer 1

Reset to default
2

Make an array

Create an array of pointers. Have the array members point to the list members. The code uses a little trick so that the last element of the list will get its pNext member set to NULL properly.

struYugiohCard *arr[size_of_list + 1], **arrp = arr, *iter;

for (iter = list; iter != NULL; iter = iter->pNext) {
    *arrp++ = iter;
}
*arrp = NULL;

Write a comparison function, then call qsort

There are lots of examples of how to use qsort, but the trick is writing an appropriate comparison function. It is important to realize that qsort will pass in the addresses of the array elements it is comparing. Since our array contains pointers, the comparison function will be passed pointers to pointers.

In your case, I would guess CardType2 Ascending might be implemented using strcmp, which has return values that match up to what qsort expects (negative if a is less than b, positive if greater than, zero if equal):

int cmp_CardType2_Ascending(const void *a, const void *b) {
    const struYugiohCard * const *aa = a;
    const struYugiohCard * const *bb = b;
    return strcmp((*aa)->CardType2, (*bb)->CardType2);
}

//...

qsort(arr, size_of_list, sizeof(*arr), cmp_CardType2_Ascending);

Fix your list

Now, rewire your list to the sorted order. Notice the pNext of the last iteration is making use of the extra array member which was set to NULL.

arr[0]->pNext = arr[1];
arr[0]->pPrev = NULL;
for (int i = 1; i < size_of_list; ++i) {
    arr[i]->pNext = arr[i+1];
    arr[i]->pPrev = arr[i-1];
}
list = arr[0];

Putting it into a function

Below is a function that puts most of this logic into a single function. The sorting function is passed in, and this function is then passed to qsort.

void sort_YugiohCard(struYugiohCard **pList, int size_of_list,
                     int (*By)(const void *, const void *)) {

    if (size_of_list == 0) return;

    struYugiohCard *list = *pList;
    struYugiohCard *arr[size_of_list+1], **arrp = arr, *iter;

    for (iter = list; iter != NULL; iter = iter->pNext)
        *arrp++ = iter;
    *arrp = NULL;

    qsort(arr, size_of_list, sizeof(*arr), By);

    arr[0]->pNext = arr[1];
    arr[0]->pPrev = NULL;
    for (int i = 1; i < size_of_list; ++i) {
        arr[i]->pNext = arr[i+1];
        arr[i]->pPrev = arr[i-1];
    }
    list = arr[0];

    *pList = list;
}

Then, you can call this function like this:

sort_YugiohCard(&list, 5, cmp_CardType2_Ascending);

And the list will be returned in sorted order as determined by the comparison function.

A demo

Try it online!

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Is that C++? I think, that is C++. I don't know.
It is C. Answer updated for your doubly linked lists.
Ok. I'll try it.
Reading the data into an array of struct, sorting the array with qsort and then adding the sorted structs to your list will be Orders of Magnitude faster than scanning the list on each insert to insert the nodes in sorted order. Answer is right-on-point.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.