Thread: C Programming Arrays and Linked Lists

  1. #1
    Registered User
    Join Date
    Feb 2016
    Posts
    27

    C Programming Arrays and Linked Lists

    I have a deck of 52 cards in a linked list and I want to shuffle the cards so I can place them in each player's hand. However, I'm finding it very hard to randomize nodes in the list to create this shuffle function. I am trying to now put the list nodes addresses into an array and then randomize that and share the cards from the array which would be initially pointing to nodes in the linked list. I can't seem to get the code to work. Please help.

  2. #2
    Registered User
    Join Date
    Dec 2015
    Posts
    112
    Seems like you can use the Fisher–Yates shuffle function

    Code:
    voidShuffleArray(int array[]){
        int index, temp;
        srand(time(NULL)); // randomize seed with time
    
        for(int i = array.length -1; i >0; i--)
        {
            index = rand()%52; // give you a number between 0 and 51
            temp = array[index];
            array[index]= array[i];
            array[i]= temp;
        }}
    You can do the same thing with the linked list, and move pointers around.

  3. #3
    Registered User
    Join Date
    Jun 2011
    Posts
    4,513
    Quote Originally Posted by Amrita Ramnauth View Post
    I can't seem to get the code to work. Please help.
    It's hard to help you with the code if you don't post it.

    I don't see any benefits to using a linked list for a deck of cards - an array would suffice.

    If you must use a linked list, how about just posting your "plan" (in words) on how you're trying to do this, and perhaps we can offer suggestions for improvement.

  4. #4
    Registered User
    Join Date
    Jun 2015
    Posts
    1,640
    I concur that a linked list is a strange choice for a deck of cards. If you must use a linked list (homework assignments can be weird) then copy the pointers to an array, use the Fisher-Yates shuffle, and then reconnect the nodes into a linked list.

    Note that CodeSlapper has made two errors in his shuffle. Firstly you shouldn't call srand in the shuffle routine as you may want to shuffle more than once in a run of the program and srand should only be called once. Secondly, the random numbers shouldn't always be chosen from 0 to 51 but instead from 0 to i. The corrected code:
    Code:
    Node *shuffle_linked_list(Node *head) {
        Node *a[DECK_SIZE];
    
        // TODO: copy pointers to array
    
        for (int i = DECK_SIZE - 1; i > 0; i--) {
            int r = rand() % (i + 1);
            Node *t = a[i];
            a[i] = a[r];
            a[r] = t;
        }
    
        // TODO: reconnect nodes into a linked list
    
        return a[0];  // return new head
    }

  5. #5
    Registered User
    Join Date
    Feb 2016
    Posts
    27

    Arrays and Linked Lists Pt2

    I'm doing a card game which requires me to create a deck of 52 cards, shuffle the deck then share the cards to 4 players (13 cards in each player's hand). From my understanding, I wanted to use a link list so when the cards are shuffled and given to each player then the deck would be empty. Also, when a player plays a card from his hand, that card should not be there. Initially, I was thinking that if I use the array to store the cards, I would not be able to remove it from the array, but just set that index in the array to NULL. With linked lists, I would be able to remove a node when it is gone instead of just leaving an empty node lying around. However, it is challenging to use a linked list to do this. This is where I'm stuck. To use arrays or linked lists

  6. #6
    Registered User
    Join Date
    Jun 2011
    Posts
    4,513
    There are many ways you could go about this without using a linked list.

    One option would be to use an array of struct, with one member called something like "isAvailable" that is initialized to 1. When a card is "drawn", that variable is set to 0. This variable can be checked when a card is randomly selected, to see if it's valid.

    Another option would be to use a stack, which may be well suited to mimic a deck of cards.

  7. #7
    Registered User
    Join Date
    Feb 2016
    Posts
    27
    I think I'll work with an array of struct. Thanks for the feedback

  8. #8
    Registered User
    Join Date
    Feb 2016
    Posts
    27

    Deck Array Printing Problems

    I've created a deck array and I'm running into a problem when I want to print my cards with their suit and face.
    Here is the code:

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #define DECK_SIZE 52
    #define NSUITS 4
    #define NFACES 13
    #define NVALUES 13
    
    
    /*card structure definition*/
    typedef struct Card{
        int face; /* define face */
        char suit; /* define suit */
    
    
    }Card, *CardPtr; /* end structure card */
    
    
    /*Face array*/
    char *faces[] = {"Ace","2","3","4","5","6","7","8","9","10","Jack","Queen","King"};
    
    
    /*function prototypes*/
    CardPtr createDeck();
    void printCard(CardPtr deck, int x);
    
    
    int main(){
        createDeck();
    return 0;
    }
    
    
    CardPtr createDeck(){
    
    
        CardPtr deckArray[DECK_SIZE];   /*creates deck*/
    
    
        int i,j;  /*counters*/
        int k=1;
    
    
        for (j = 0; j < 4; j++){
            for (i = 1; i < 14; i++){
                if (j == 0) {
                    CardPtr newCard = (CardPtr)malloc(sizeof(Card));    /*allocates space to newly created card*/
                    newCard->suit = 'S';       /*Spades*/
                    newCard->face = i;
                    deckArray[k-1]= newCard;
                    k++;
                }
    
    
                if (j == 1) {
                    CardPtr newCard = (CardPtr)malloc(sizeof(Card));    /*allocates space to newly created card*/
                    newCard->suit = 'H';       /*Hearts*/
                    newCard->face = i;
                    deckArray[k-1]= newCard;
                    k++;
                }
    
    
                 if (j == 2) {
                    CardPtr newCard = (CardPtr)malloc(sizeof(Card));    /*allocates space to newly created card*/
                    newCard->suit = 'D';       /*Diamonds*/
                    newCard->face = i;
                    deckArray[k-1]= newCard;
                    k++;
                }
    
    
                 if (j == 3) {
                    CardPtr newCard = (CardPtr)malloc(sizeof(Card));    /*allocates space to newly created card*/
                    newCard->suit = 'S';       /*Clubs*/
                    newCard->face = i;
                    deckArray[k-1]= newCard;
                    k++;
                }
    
    
            }
        }
    
    
        int l = 0;
             for(l=0;l<52;l++){
                    printCard(deckArray, l);
                   }
    
    
    return 0;
    }
    
    
    /*prints card to screen */
    void printCard(CardPtr deckArray, int i){
        char *suit;
        switch (deckArray[i].suit) {
            case 'D':
                suit = "Diamonds";
                break;
    
    
            case 'C':
                suit = "Clubs";
                break;
    
    
            case 'H':
                suit = "Hearts";
                break;
    
    
            case 'S':
                suit = "Spades";
                break;
        }
        printf("%s of %s\n", faces[i], suit);
    return;
    }
    I can easily do a for loop to print all the cards by incrementing the index of the array.

    However, I would like if my printCard function could be something separate so I can use it in other parts of the program. I might be confusing the arrays for the printCard function.
    Kindly guide me on the right track.

  9. #9
    Registered User
    Join Date
    Jun 2011
    Posts
    4,513
    Compile with maximum warnings:

    Code:
    main.c||In function 'createDeck':|
    main.c|88|warning: passing argument 1 of 'printCard' from incompatible pointer type|
    main.c|25|note: expected 'CardPtr' but argument is of type 'struct Card **'|
    ||=== Build finished: 0 errors, 1 warnings ===|
    Typedef'ing a pointer should be avoided in most cases (such as this one). It has no real benefit here, and serves only to cause confusion.

    I'm not sure what you're trying to do with your "createDeck" function. You create an array of pointers, allocate memory to each element, and for some reason return 0 at the end. (Incidentally, you should be checking your malloc calls to ensure they've succeeded before attempting to access the memory.)

    If you want your deck to be represented by an array of struct, there's no need to create an array of pointer to struct and allocate memory. Just create an array of struct. You can declare it in "main", pass it to the "createDeck" function, and load it with values as needed.

    Also, each function should do one thing and do it well. "createDeck" should not be printing any cards.

    Since your "printCard" function only expects it to print a single card, you should just pass a single struct (or a pointer to that specific struct) to it. Passing the entire array plus the target element value is not the best approach.

    You've also created named constants for values (which is good), but you're not using them when you do your loops.

    You don't need a global array of strings to print card values - if they're only to be printed in a single function, they can be local to that function.

    The struct member "suit" doesn't need to be a character. It is perfectly acceptable, and often preferable, to separate data from it's representation. The underlying code doesn't care about Diamonds or Clubs. You can use numeric values to represent the suits, and use these to print the corresponding strings only when needed, which is basically when reporting this information to the user.

    I've created a quick mock-up of your code with these changes implemented. It's not thoroughly tested, and a bit sloppy (since I tried to maintain your basic representations), but it should illustrate the points I've made.

    Code:
    // Mock-up modification of the OP's example
    // Note: Minimal error-checking for purposes of illustration
    
    #include <stdio.h>
    
    #define DECK_SIZE 52
    #define NFACES 13
    #define NVALUES 13
    
    enum suits_e
    {
        SUIT_CLUBS,
        SUIT_DIAMONDS,
        SUIT_SPADES,
        SUIT_HEARTS,
        NSUITS
    };
    
    typedef struct Card
    {
        int face;
        int suit;
    } Card;
    
    
    void createDeck(Card *deck);
    void printCard(Card *card);
    
    
    int main(void)
    {
        Card deck[DECK_SIZE];
        int i;
    
        createDeck(deck);
    
        for(i = 0; i < DECK_SIZE; i++)
            printCard(&deck[i]);
    
        return 0;
    }
    
    
    void createDeck(Card *deck)
    {
        int face, suit;
        int i = 0;
    
        for(suit = SUIT_CLUBS; suit < NSUITS; suit++)
        {
            for(face = 0; face < NFACES; face++)
            {
                deck[i].face = face;
                deck[i].suit = suit;
                ++i;
            }
        }
    }
    
    void printCard(Card *card)
    {
        const char *face_str[NFACES] = {
            "Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King"
        };
        const char *suit_str[NSUITS] = {
            "Clubs", "Diamonds", "Spades", "Hearts"
        };
    
        printf("%s of %s\n", face_str[card->face], suit_str[card->suit]);
    }
    Any questions?

  10. #10
    Registered User
    Join Date
    Feb 2016
    Posts
    27
    I understand what's going on now but one question, for line 55, why ++i and not i++?

  11. #11
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Quote Originally Posted by Amrita Ramnauth View Post
    I understand what's going on now but one question, for line 55, why ++i and not i++?
    Because ++i is like 50x more efficient XD

    Just kidding. ++i and i++ are largely equivalent in most use-cases.

    However, it does matter if you're doing this:
    Code:
    int i = 4;
    int p = i++; // p = 4
    // vs.
    int p = ++i; // p = 5
    But honestly, you shouldn't be coding like that in the first place, imo.

  12. #12
    Registered User
    Join Date
    Feb 2016
    Posts
    27
    Never understood the difference. I got it now. Thanks (y)

  13. #13
    Registered User
    Join Date
    Feb 2016
    Posts
    27

    Shuffling Cards

    I've reached to a point where I have my deck of cards and now I'm trying to shuffle the cards right in the deck then share the cards. I have a shuffle function but it's not working as I intend for it to. It's suppose to take two random indexes and go to the array with the 1st index, store that value in a temp location, replace the 1st index with the value in the second index and then replace the second index with the temp value...I now started working with the rand() function and I'm not sure if that's where my problem is. Help please?

    I'll provide the code below:

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #define DECK_SIZE 52
    #define NFACES 13
    #define NSUITS 4
    
    
    
    
    /*enum for card suits*/
    enum suits_e{
        SUIT_DIAMONDS,
        SUIT_CLUBS,
        SUIT_HEARTS,
        SUIT_SPADES
    };
    
    
    /*card structure definition*/
     typedef struct Card{
        int face; /* define face */
        int suit; /* define suit */
    }Card, *CardPtr;/* end structure card */
    
    
    
    
    /*function prototypes*/
    void createDeck(CardPtr deck);
    void printCard(CardPtr card);
    void shuffle(CardPtr deck);
    
    
    int main(){
        Card deck[DECK_SIZE]; /*Creating deck array*/
        int i,j;  /*counter*/
        int x = 1;
        int y=1;
    
    
        createDeck(deck);
    
    
        printf("Deck before: \n");
        for(i=0; i<DECK_SIZE; i++){
            printf("%d). ", x);
            printCard(&deck[i]);
            x++;
        }
    
    
        printf("Random numbers: \n");
         srand(time(NULL));
        for (j=1;j<2;j++){
            shuffle(deck);
        }
    
    
        printf("Deck now: \n");
        for(i=0; i<DECK_SIZE; i++){
            printf("%d). ", y);
            printCard(&deck[i]);
            y++;
        }
    
    
    return 0;
    }
    
    
    /*Creates deck*/
    void createDeck(CardPtr deck){
        int face, suit;
        int i=0;    /*counter*/
    
    
        for (suit=SUIT_DIAMONDS; suit<NSUITS; suit++){
                for (face=0; face<NFACES; face++){
                    deck[i].face= face;
                    deck[i].suit= suit;
                    i++;
                }
    
    
        }
    
    
    }
    
    
    /*Prints a Card*/
    void printCard(CardPtr card){
    
    
        /*Face array*/
        const char *face[NFACES] = {
            "Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King"
        };
    
    
        /*Suit array*/
        const char *suit[NSUITS] = {
            "Diamonds", "Clubs", "Hearts", "Spades"
        };
    
    
        printf("%s of %s\n", face[card->face], suit[card->suit]);
    }
    
    
    /*Shuffles deck*/
    void shuffle(CardPtr deck){
        Card temp;
    
    
                int a;
                int b;
    
    
    
    
                /*Check to see if same random number gets called*/
    
    
                a = randNo(deck);
                b = randNo(deck);
                printf("%d & %d\n", a, b);
    
    
                deck[b] = temp;
                deck[b] = deck[a];
                temp = deck[a];
    
    
    }
    
    
    /*Random Generator*/
    int randNo(CardPtr deck){
        return (rand() % DECK_SIZE+1);
    }

  14. #14
    Registered User
    Join Date
    Jun 2015
    Posts
    1,640
    Quote Originally Posted by MutantJohn View Post
    But honestly, you shouldn't be coding like that in the first place, imo.
    I disagree completely! What you're suggesting is tantamount to saying that the postfix decrement/increment operators shouldn't be used at all. But there are simple, useful idioms such as:
    Code:
    a[i++] = n;
    
    // or the wonderful
    *a++ = *b++;
    They're probably a little confusing to beginners, but, well, I don't care.

  15. #15
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Code:
    *a++ = *b++;
    Oh God...

    I'm scared to ask what you would think of nested ternary operators...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Arrays of linked lists
    By Chuklol in forum C Programming
    Replies: 2
    Last Post: 04-17-2012, 06:45 PM
  2. pointers and linked lists in place of arrays
    By kordric in forum C++ Programming
    Replies: 8
    Last Post: 05-14-2008, 10:59 AM
  3. Arrays Vs Linked Lists
    By ianbd in forum C++ Programming
    Replies: 3
    Last Post: 08-31-2005, 08:41 AM
  4. From Python's Linked Lists to Dynamic Arrays
    By hexbox in forum C Programming
    Replies: 3
    Last Post: 01-26-2005, 03:14 PM
  5. linked lists / arrays
    By akira in forum C++ Programming
    Replies: 0
    Last Post: 11-27-2001, 01:01 AM

Tags for this Thread