Thread: help with linked lists

  1. #1
    Registered User
    Join Date
    Oct 2003

    Angry help with linked lists

    hello guys, i have to do this project and im a little stuck. this is the description of the project:

    This program constructs a simple linked list of nodes. It uses the following node data type.

    typedef struct _node
    char string[32];
    int prcd_ct; // number of nodes that follow this node
    struct _node* next;
    } Node, *NodePtr;

    The input comes from the standard input stream, stdin, and consists of ordinary english words separated by whitespace. No words will occur twice in this stream.

    (Since we are working with the standard input and output streams, there is no need to open any files and to do so is an error.)

    If string X is a proper substring of string Y, we say X precedes Y ( or equivalently ) Y follows X. Thus, we have a partial ordering on the set of all strings. The list we create is the first stage in performing a topological sorting of the words in the input stream.

    The char* strstr(char* y, char* x,) declared in string.h returns a non-null value when x is a substring of y and returns 0 else. Use it to decide the precedence, if any, of two strings.

    (When topologically sorted the list of words has the property: if string X comes before string Y in this list, then Y is not a substring of X.)

    As each word is read (using scanf() or whatever), a node is created for it and it is copied into the string member of that node. Then both the members, prcd_ct and next, are set to 0---this must be done.

    At this point the node is added to the front of the linked list that is being constructed.

    When all words have been read (e.g., scanf() returns EOF), the program determines the prcd_ct (precedence count) for each node. The precedence count of a node Y is the number of nodes X that precede it. It will be necessary to investigate all pairs of nodes, (X, Y) with X != Y, to obtain all the precedence counts. A double loop can accomplish this.

    Next, the program prints the nodes in the list, 2 nodes per line. Use the following printf statement to print a node:

    printf("[%s:%d:%p -> %p] ", q->string, q->prcd_ct, q, q->next);

    Here, q is the pointer to the current node being printed.

    After printing, the list is investigated one more time to find a node with a maximum value for the prcd_ct. This node's string member and prcd_ct are printed on a new line, using the following format string for printf:

    "\n[%s] has maximum precedence count [%d]\n"

    this is a sample input/output:

    The following is a sample input file.

    recommend commend end ended mend men
    releases lease ease leases eases
    caper cape cap
    reinvested reinvest invested invest vest rein vested

    The two program produces. (Machine addresses will vary, of course.)

    [vested:1:003D38D0 -> 003D2818] [rein:0:003D2818 -> 003D27E8]
    [vest:0:003D27E8 -> 003D27B8] [invest:1:003D27B8 -> 003D2788]
    [invested:3:003D2788 -> 003D2758] [reinvest:3:003D2758 -> 003D2728]
    [reinvested:6:003D2728 -> 003D26F8] [cap:0:003D26F8 -> 003D26C8]
    [cape:1:003D26C8 -> 003D2698] [caper:2:003D2698 -> 003D2668]
    [eases:1:003D2668 -> 003D2638] [leases:3:003D2638 -> 003D2608]
    [ease:0:003D2608 -> 003D25D8] [lease:1:003D25D8 -> 003D25A8]
    [releases:4:003D25A8 -> 003D2578] [men:0:003D2578 -> 003D2548]
    [mend:2:003D2548 -> 003D2518] [ended:1:003D2518 -> 003D24E8]
    [end:0:003D24E8 -> 003D24B8] [commend:3:003D24B8 -> 003D2488]
    [recommend:4:003D2488 -> 00000000]
    [reinvested] has maximum precedence count [6]

    Adding the sorting phase produces (changed output format).

    [vested:1: vest]
    [invest:1: vest]
    [invested:3: vested vest invest]
    [reinvest:3: rein vest invest]
    [reinvested:6: vested rein vest invest invested reinvest]
    [cape:1: cap]
    [caper:2: cap cape]
    [eases:1: ease]
    [leases:3: eases ease lease]
    [lease:1: ease]
    [releases:4: eases leases ease lease]
    [mend:2: men end]
    [ended:1: end]
    [commend:3: men mend end]
    [recommend:4: men mend end commend]

    [reinvested] has maximum precedence count [6]


    and this is what i have done so far

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct_node
       char string[32];
       int prcd_ct;
       struct _node * next;
    }Node, *NodePtr;
    NodePtr getnode( char * str );
    NodePtr find( NodePtr head, int wt );
    NodePtr create_list();
    void lstcat( NodePtr * addr_head1, NodePtr * addr_head2 );
    void update_prcd_pair( NodePtr p, NodePtr q );
    void set_all_prcd_cts( NodePtr head );
    void push( NodePtr * addr_head, NodePtr q );
    int main( void )
    Node p, q;
    p = create_list()
    return 0;
    NodePtr getnode( char * str)
       nodeptr p = (NodePtr)malloc(sizeof(Node));
       p -> next = NULL;
       p -> prcd_ct = 0;
       strncpy( p -> string, str, 32 );
       return p;
    NodePtr create_list()
       int wt;
       NodePtr head = NULL;
          scanf("%d", &wt);
            if( wt == 0 ) 
               push( &head, getnode(wt) );
       return head;
    void lstcat( NodePtr * addr_head1, Node head2 )
       if( * addr_head1 == NULL )
            *addr_head2 = head2;
       for( p = *addr_head1; next -> p != NULL; p = p -> next )
            p -> next = head;
    NodePtr find( NodePtr head, int wt )
       while( head != NULL && head -> wt != wt )
            head = head -> next;
       return head;
    void update_prcd_pair( NodePtr p, NodePtr q )
       if( strstr( p -> string, q -> string ) )
            ++p -> prcd_ct;
       if( strstr( q -> string, p -> string ) )
            ++q -> prcd_ct;
    void set_all_prcd_cts( NodePtr head )
       NodePtr p, q;
       for( p = head; p -> next != NULL; p = p -> next )
       for( q = p -> next; q != NULL; q = q -> next )
            update_prcd_pair( p, q );
    as you can see, i dont know how to get started but i do have the functions set. any help on how to get started will be appreciated. thanx

  2. #2
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    >>i dont know how to get started
    Plan out each section of the program on paper first, then work on the code in small chunks, verifying as you go.

    Try to be more specific with your questions on here, you'll get better answers that way.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 05:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM