GIDForums  

Go Back   GIDForums > Computer Programming Forums > C Programming Language
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 05-Oct-2004, 20:15
Kareem1984 Kareem1984 is offline
New Member
 
Join Date: Oct 2004
Posts: 4
Kareem1984 is on a distinguished road

Linked List


Hi,

I'm not a programmer, just a computer science student. However maybe a good samaritan will help me out, having a little trouble.

My goal is this:

1. Create an empty singly-linked dynamic list LIST represented by a global pointer.
2. In a loop (referred to as main loop) prompt the user to enter a word. (must be less than 80 characters)
3. If word entered is quit (regardless of letter case (ie. QuiT, quiT etc.), main loop is terminated.
If not, word is stored in LIST in lexicographic order using procedure InsertIntoList(word) and main loop is repeated.

Any help would be really appreciated!

all I've got so far is this:

CPP / C++ / C Code:
typedef struct element{
	<type> data; //not sure of type
	struct element *next;
} LIST;

LIST *head=NULL;
Last edited by LuciWiz : 06-Oct-2004 at 00:37. Reason: Please insert your c code between [c] [/c] tags
  #2  
Old 06-Oct-2004, 00:39
nkhambal nkhambal is offline
Regular Member
 
Join Date: Jul 2004
Location: CA USA
Posts: 313
nkhambal is a jewel in the roughnkhambal is a jewel in the rough
Hi,

you are on right track. The data type can be char array (static storage) or char pointer (dynamic storage) to save the word. Choice is yours.

To add a node to list, create a new node and points previous node's next pointer to the current node and current node's next pointer to NULL.

So steps to build your function InsertIntoList(word) would be

Make head node of the list if list is empty. Store word in it. Point head node's next to NULL. Do not touch head node if list is not empty.

Keep head node's address in a new pointer variable called "lastnode" (or anything of your choice) of type LIST.

Prepare a new node in a similar way as head node and just keep pointing lastnode's next to this new node and this node's next to NULL. Also,make this new node as lastnode everytime.

Ofcourse,this is one logic.

You can check the if the word entered is "quit" or not using string manipulation functions available in C. Its called strcasecmp. It does a case insensitive comparison of two strings and returns 0 if they are equal. Check man strcasecmp on any unix machine to check its syntax and related help.

Pls see the linked list tutorial in "C/C++ Source Code and Tutorials" in this forum.Its explained very well there.

Good Luck.
  #3  
Old 06-Oct-2004, 10:21
Kareem1984 Kareem1984 is offline
New Member
 
Join Date: Oct 2004
Posts: 4
Kareem1984 is on a distinguished road
Hi,

Thank you for the advice.

I was thinking to ensure that the word is less than 80 characters (that is one of the conditions) I could just do this:

CPP / C++ / C Code:
string word;
puts ("Enter a word");
scanf ("%80s", &word);

then after the word is stored as a string called word I would check for 'quit' and go from there.

Does that make sense?
Quote:
Originally Posted by nkhambal
Hi,

you are on right track. The data type can be char array (static storage) or char pointer (dynamic storage) to save the word. Choice is yours.

To add a node to list, create a new node and points previous node's next pointer to the current node and current node's next pointer to NULL.

So steps to build your function InsertIntoList(word) would be

Make head node of the list if list is empty. Store word in it. Point head node's next to NULL. Do not touch head node if list is not empty.

Keep head node's address in a new pointer variable called "lastnode" (or anything of your choice) of type LIST.

Prepare a new node in a similar way as head node and just keep pointing lastnode's next to this new node and this node's next to NULL. Also,make this new node as lastnode everytime.

Ofcourse,this is one logic.

You can check the if the word entered is "quit" or not using string manipulation functions available in C. Its called strcasecmp. It does a case insensitive comparison of two strings and returns 0 if they are equal. Check man strcasecmp on any unix machine to check its syntax and related help.

Pls see the linked list tutorial in "C/C++ Source Code and Tutorials" in this forum.Its explained very well there.

Good Luck.
Last edited by LuciWiz : 06-Oct-2004 at 23:09. Reason: Please insert your code between [c] [/c] tags
  #4  
Old 06-Oct-2004, 12:32
nkhambal nkhambal is offline
Regular Member
 
Join Date: Jul 2004
Location: CA USA
Posts: 313
nkhambal is a jewel in the roughnkhambal is a jewel in the rough
Hi,

scanf won't help in checking the length of the word. What you need to do is define some temp word variable as char array of size say 100 (to accomodate for word size 80+1 end-of-line character) in your main program.

After the word is entered and stored in temp word variable, you can use strlen() function in C to measure the length of the word entered. strlen() will read count the total number of characters in the string suuplied till it hits '\0'. You can try following to check length of the word and if the word is "quit" or not by using following if loop.

CPP / C++ / C Code:
 if ( strlen(tempword)<=0 || strlen(tempword)>80)
 {
   print error..do something..and exit program or ask for word again.
   
 } else if {(strcasecmp(tempword,"quit"))==0)  /* word entered is quit */
  {
    exit program or do something....
  }

If the tempword has passed the above two tests ,i.e. word length is less than 80 and word is not "quit", then you can store tempword in you actual linked list node data variable that you are building.

Use "man strlen" to checkout help for strlen() function.
  #5  
Old 06-Oct-2004, 21:23
Kareem1984 Kareem1984 is offline
New Member
 
Join Date: Oct 2004
Posts: 4
Kareem1984 is on a distinguished road

I'm having some serious problems


The linked list must be in lexicographic order, so new entries must be checked for their proper place. I'm having a serious problem knowing how to create a loop to go through the list and change which node it is looking at. I'd really appreciate some advice. Also it is a requirement that I make a deep copy of any new word, not just point somethng to it. This is what I have right now:

CPP / C++ / C Code:
#include <stdio.h>
#include <string.h>

typedef struct element {

	char *data;
	struct element *next;

}LIST;

LIST *head=NULL;

void main (void) {

	char word[81];
	char end[5]="QUIT";

	void InsertIntoList(char *new) {

		char *new=malloc(sizeof(word));

		strcpy (new, word);

		if (*head=NULL) {

		head=malloc(sizeof(LIST));
		head->data=new;
		head->next=NULL;
	}

LIST *current=head;
LIST *previous=head;
LIST *new_node;
new_node->data=*new;
new_node->next=NULL;


while (strcmp (*new, *current)<0) {

	if ((current->next)=NULL) { 

	current=new_node; 

// I don't know how to change the pointers to add a new element
// Or how to change the previous pointer to point at the new element
//Or how to change the pointer of the new element to point at the next 
//element
// I don't even know how to reference any of the elements of the list other 
// than head!
// Can't seem to figure out how I would go about manipulating this list in any 
// way
Last edited by LuciWiz : 06-Oct-2004 at 23:14. Reason: Please insert your C code between [c] [/c] tags
  #6  
Old 07-Oct-2004, 17:13
nkhambal nkhambal is offline
Regular Member
 
Join Date: Jul 2004
Location: CA USA
Posts: 313
nkhambal is a jewel in the roughnkhambal is a jewel in the rough
First of all, In C, you can not have function definition inside another function. You can not define your function InsertintoInsertIntoList() inside main(). It should be moved outside main(), either before or after.

Secondly,about lexicographic order. You need to add a string to the list by comparing it with the last inserted string. Following is the camparison criteria.

String1 preceeds String2 lexicographically if, first character of string1 prceeds ( or less than) first character of string 2. So if current string is lexicographically preceeds the last string then you need to swap current string with last string. Following is a small function which determines , out of the two strings passed which string lexicographically preceeds the other one.

CPP / C++ / C Code:
boolean stringcmp(char *str1,char *str2)
{
	int str1len,str2len;
	int min,i;
	str1len=strlen(str1);
	str2len=strlen(str2);
    
	min=(str1len<str2len)? str1len : str2len;
	
	i=0;

	while (i<min)
	{
		if (str1[i]<str2[i])
		{
			return TRUE;   //String 1 preceeds String 2
		} else if (str2[i]<str1[i])
		{
			return FALSE;  ////String 2 preceeds String 1
		} else {
			i++;
		}
	}
	/* If both strings are the lexicographically similar till the last character compared then smaller one in length preceeds in length*/
    if (str1len<str2len)
    {
		return TRUE;
    } else if (str2len<str1len)
    {
		return FALSE;
    } 
}

where is boolean is my custom enum data type defined as

CPP / C++ / C Code:
typedef enum {
	FALSE,
	TRUE
} boolean;

You can also return 1 for TRUE and 0 for FALSE if you are not comfortable with enum data types.

Also, by deep copy, if you mean saving new word to "data" then yes ofcourse, you need to do that. Your node holds actual data and a "pointer" to the location of next node.

I am just giving you the logic of add function. You need to fill in the code.

CPP / C++ / C Code:
function addtolist (word)

{
 allocate memory for new node
 allocate memory for data in new node of the size word
 save the word in new node->data
 point new node->next to NULL

 if list is empty then
 make new node as head node
 make head node as the last added node
 else 
 get the last added node
 compare last node ->data with  new node->data (lexicographical order)
     if new node->data preceeds last node -> data then 
          point last node ->next to new node
          swap last node ->data with new node ->data
          make new node as the last added node
    else 
         point last node ->next to new node
         make new node as the last added node

}

Good luck.
 
 

Recent GIDBlogDeveloping GUIs with wxPython (Part 2) by crystalattice

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Merge sort on a linked list Temujin_12 C++ Forum 1 06-Mar-2008 20:33
Insert problem in linked list with two function code Kay Chan C++ Forum 1 03-Sep-2004 09:52
Question about linked list and queue Kay Chan C++ Forum 7 02-Sep-2004 09:27
help on linked lists any1????? nick4 C Programming Language 1 17-May-2004 09:32
[include] list1.h -- Linked list class dsmith C Programming Language 2 04-May-2004 09:42

Network Sites: GIDNetwork · GIDWebHosts · GIDSearch · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 20:38.


vBulletin, Copyright © 2000 - 2008, Jelsoft Enterprises Ltd.