Solved

Linked list dilemma

Posted on 1998-12-03
7
232 Views
Last Modified: 2013-12-14
Hi      
   I have to create a poker program with 5 players (who play 5 hands of poker). Each player will have a 5-node linked list (corresponding with the 5 hands played) with info on each hand (highest card, lowest card, etc). I'm having trouble with how to create the five different linked lists, insert new nodes in each list, then printing out the results. Here's the structure (node):

struct player {
      int highestCard;
      int lowestCard;
};

Can anyone provide an algorithm for creating the main function and also the "addData" or "insert" function? Do I have to do five different insert functions (for the 5 players) or can I do it in one function? Any help would be appreciated!
0
Comment
Question by:chadd082197
  • 3
  • 3
7 Comments
 
LVL 16

Accepted Solution

by:
imladris earned 300 total points
ID: 1254809
The structure looks like it should represent a hand played, and so it should contain a pointer to the next element in the list:

struct hand
{ int highestCard;
  int lowestCard;
  struct hand *next;
}


The players would be represented by an array of pointers to hands:

struct hand *player[5];

Creating a hand is done by allocating memory and initializing the hand structure:

struct hand *newhand;

newhand=malloc(sizeof(struct hand));
newhand->highestCard = /*something relevant*/
newhand->lowestCard= /* something relevant */
newhand->next=NULL;


The lists start at the player array, and continue until the next element is null. So inserting a new hand at the end would be a function like:

insertHand(player,handptr)
struct hand *player,*handptr;

{   struct hand *hp;

    if(player==NULL)
    {   player=handptr;
        return;
    }
    for(hp=player; hp->next!=NULL; hp=hp->next);
    hp->next=handptr;
    return;
}


This function can be called for any player or for all in a loop:

insertHand(player[i],newhand);


So there is definitely an insert function there. It inserts at the end of the list. A small change could have it insert at the beginning. The malloc bit may be the addData you were referring to. I am completely unclear on what "an algorithm for creating the main function" would comprise. Please ask for any further clarification you need.


0
 

Author Comment

by:chadd082197
ID: 1254810
Thanks for the quick response! This looks like something I can definitely use, but I guess the problem I'm having is with the basics of linked lists -- for example, if I have a program setup like this:

struct person {
   char name[20];
   int age;
   person *next;
};

int main(void)
{

   char n[20];
   int a;

   printf("Enter a name: \n");
   scanf("%s", &n);             /* I want my linked list to */
   printf("Enter an age: \n");  /* be composed of nodes like */
   scanf("%d", &a);             /* this                      */  

}

If I want to ask the user for a name & age for 5 people (for a total of 5 nodes), how do I take the input for each person and add it to the linked list? Is it better to assemble the linked list in the main() function or use a separate "insertNode" function (and if so, what do you pass as function parameters)? The text I have just shows this very simplistically. If you can help me to understand this I'll double the points. Thanks!!!!!
0
 
LVL 16

Expert Comment

by:imladris
ID: 1254811
The method would be analogous to the one I listed for creating a linked list for hands. One key point for a linked list is that you need to have a known place from which to start chasing down the pointers. So that would be something like:

struct person *playerlist;

The insertfunction would be something like:

insertPlayer(playerlist,player)
struct person *playerlist,*player;

{   struct person *pp;

    if(playerlist==NULL)
    {   playerlist=player;
        return;
    }
    for(pp=playerlist; pp->next!=NULL; pp=pp->next);
    pp->next=player;
    return;
}


and the main function would be something like:

int main(void)
{   struct person *npp; /* new player pointer */
    int i;

   playerlist=NULL;
   for(i=0; i<5; ++i)
   {   npp=(struct person *)malloc(sizeof(struct person));
       printf("Enter a name:\n");
       scanf("%s",npp->name); /* Note that name is already a
                                                 pointer to block of 20 bytes. So
                                                don't do a "&" in addition        */
      printf("Enter an age:\n");
      scanf("%d",&npp->age);
      npp->next=NULL;
      insertPlayer(playerlist,npp);
   }
   /*  do other stuff */
}

I assume this is an excersize of some sort. I originally had the players set up in an array with 5 elements (since the indication was that there were exactly 5 of them), and that would make it easy to get at them. Linked lists trade off flexibility in size for ease of access. Getting at player number 3 is no longer a simple matter (like an array access). You will need to chase down the pointers till you find the third entry (probably with yet another function). However, this will serve, of course, to familiarize you with linked lists.

Please ask for any further clarifications you need.

0
Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 

Author Comment

by:chadd082197
ID: 1254812
OK, good stuff. Thanks. I've included a listing here of a small program that doesn't do what it's supposed to. I'm trying to build 2 different linked lists (h1 and h2) and then subsequently add a node to each so that now I have 2 linked lists with 2 nodes each. Finally, I want to print out both linked lists. This program compiles but only prints out the 2nd node of each list -- like it's overwriting the first node (plus I get a null pointer allocation error after it runs). Any thoughts? Here's the listing:

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

typedef enum {won, lost} result;

struct stats {
      int highCard;
      int lowCard;
      result w_or_l;
      struct stats *next;
};

typedef struct stats ELEMENT;
typedef ELEMENT *LINK;

LINK add_to_list1(LINK, int, int, result);
LINK add_to_list2(LINK, int, int, result);
void print_list(LINK currPtr);

int main(void)
{
      LINK h1 = NULL, h2 = NULL;
      int hCard, lCard;
      result won_or_lost;

      //////// FIRST LINKED LIST -- 2 NODES //////////////////////////

      printf("\n\n\n\n");
      hCard = 10;
      lCard = 2;
      won_or_lost = lost;
      h1 = add_to_list1(h1, hCard, lCard, won_or_lost);

      hCard = 12;
      lCard = 4;
      won_or_lost = lost;
      h1 = add_to_list1(h1, hCard, lCard, won_or_lost);


      ////// SECOND LINKED LIST -- 2 NODES/////////////////////////

      hCard = 11;
      lCard = 3;
      won_or_lost = lost;
      h2 = add_to_list2(h2, hCard, lCard, won_or_lost);

      hCard = 13;
      lCard = 5;
      won_or_lost = lost;
      h2 = add_to_list2(h2, hCard, lCard, won_or_lost);


      /////// PRINTING OUT BOTH LINKED LISTS //////////////////////

      printf("Linked list #1: \n");
      print_list(h1);
      printf("\nLinked list #2: \n");
      print_list(h2);

      /////////////////////////////////////////////////////////////
      return 0;
}

LINK add_to_list1(LINK h1, int hCard, int lCard, result won_or_lost)
{
      LINK currPtr, tail;
      int i;

      currPtr = malloc(sizeof(ELEMENT));
      currPtr -> highCard = hCard;
      currPtr -> lowCard = lCard;
      currPtr -> w_or_l = won_or_lost;
      currPtr -> next = NULL;

      if(h1 == NULL)
            h1 = currPtr;
      else
            tail -> next = currPtr;
      tail = currPtr;

      return h1;
}

LINK add_to_list2(LINK h2, int hCard, int lCard, result won_or_lost)
{
      LINK currPtr, tail;
      int i;

      currPtr = malloc(sizeof(ELEMENT));
      currPtr -> highCard = hCard;
      currPtr -> lowCard = lCard;
      currPtr -> w_or_l = won_or_lost;
      currPtr -> next = NULL;

      if(h2 == NULL)
            h2 = currPtr;
      else
            tail -> next = currPtr;
      tail = currPtr;

      return h2;
}


void print_list(LINK h)
{
      char *resultName;
      LINK currPtr;
      currPtr = h;

      while (currPtr != NULL) {
            printf("High card: %d\n", currPtr -> highCard);
            printf("Low card: %d\n", currPtr -> lowCard);
            if (currPtr -> w_or_l == won)
                  resultName = "won";
            else if (currPtr -> w_or_l == lost)
                  resultName = "lost";
            printf("Result: %s\n", resultName);
            currPtr = currPtr -> next;
      }
}

///////////// OUTPUT //////////////////

Linked list #1:
High card:13
Low card:2
Result: lost

Linked list #2:
High card:12
Low card:1
Result:
null pointer allocation
0
 
LVL 84

Expert Comment

by:ozo
ID: 1254813
static LINK currPtr, tail;
0
 
LVL 16

Expert Comment

by:imladris
ID: 1254814
Ozo is correct. The crucial error is that in the add_to_list functions tail is on the stack. So the value you put in at the first call (tail=curr_ptr) will not be there at the second call. To do it in this fashion will require global data:

static LINK tail1,tail2;

i.e. a separate tail for each list declared globally outside of the function.

However, it is far more common, more robust, less code intensive (and therefore with lower risk of bugs and maintenance) to rely on the least possible amount of global data. Rather than maintaining a tail for each list, it really is better to find the end of the list using the head pointer and a loop. You can then also, in this case, where the elements of the 2 lists are the same, eliminate one of the add_to_list routines (see how the only difference between them is the name of the first argument (which is irrelevant) and the new static tails I recommended). (I described the separate routines since player and hand were different structures).

If the overhead of chasing down the pointers really is a problem (and they would have to be awfully big lists for that to be the case in practical reality) you should add a tail argument to the add_to_list function. Remember that the reality in the software world is that 80% of programmers time is spent maintaining existing code. CPU cycles are usually much cheaper than developer time. That's not to say you should squander them, but it is to say that code complexity needs to be justified.
And in the case of linked lists, insertions are usually a small minority kind of operation. Optimizing insertions is not usually going to make a difference that the user can notice. Or simpler things could be done (like inserting at the head of the list, rather than chasing down to the tail first).

0
 

Author Comment

by:chadd082197
ID: 1254815
Thanks for all your help! I think I've got it now.
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
How to install Selenium IDE and loops for quick automated testing. Get Selenium IDE from http://seleniumhq.org Go to that link and select download selenium in the right hand columnThat will then direct you to their download page.From that page s…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

830 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question