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]
[rein:0:]
[vest:0:]
[invest:1: vest]
[invested:3: vested vest invest]
[reinvest:3: rein vest invest]
[reinvested:6: vested rein vest invest invested reinvest]
[cap:0:]
[cape:1: cap]
[caper:2: cap cape]
[eases:1: ease]
[leases:3: eases ease lease]
[ease:0:]
[lease:1: ease]
[releases:4: eases leases ease lease]
[men:0:]
[mend:2: men end]
[ended:1: end]
[end:0:]
[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
Code:
#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;
while(1)
{
scanf("%d", &wt);
if( wt == 0 )
break;
else
push( &head, getnode(wt) );
}
return head;
}
void lstcat( NodePtr * addr_head1, Node head2 )
{
if( * addr_head1 == NULL )
{
*addr_head2 = head2;
return;
}
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