Celebrate National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Linked list dilemma

Posted on 1998-12-03
7
Medium Priority
?
236 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 3
7 Comments
 
LVL 16

Accepted Solution

by:
imladris earned 1200 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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 

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: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

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…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.

730 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