Solved

Linked list dilemma

Posted on 1998-12-03
7
225 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
What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 

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

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Programmer's Notepad is, one of the best free text editing tools available, simply because the developers appear to have second-guessed every weird problem or issue a programmer is likely to run into. One of these problems is selecting and deleti…
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.

760 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

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now