hello every body

iam very lucky and happy to be here
iam very very happy

and iam really need this site
because iam studying comp. eng.
and i have some problems, i hope and i think you will help:)


my ques. here is

how I write aprogram that read a list of student from afile(this is easy:) ) and creat a linked list each entry should have the students name, a pointer to the next student, and pointer to a link list of scores,there may up to 4 scores
[the scores' prompt should include the name of the student];

after all scores have been entered, the program should print the scores for each student along with score total and average score.

i hope the idea was reahed:)

good bye
waiting you.

I'm not so sure how much of a help this is, but I actually had to write a similar program in the past. It's posted here:

http://www.daniweb.com/techtalkforums/thread239-hash+table.html

The program that I had to write read a list of grocery list items from a file, and put them into a hash table. A hash table is basically a linked list of linked lists ;) I hope that you could look through my code, follow it along, (I comment pretty well), and be able to figure out the rest on your own. Good luck :)

>A hash table is basically a linked list of linked lists
An array of linked lists you mean. If the table is implemented as a linked list then the time required to traverse to the proper hash index would dominate search times and it's not much of an improvement. If the table is an array then indexing can be done in constant time and then search time is dominated by the length of the chains, which, because they should be short, is very fast.

>my ques. here is
Can you be more specific as to what part of the program you're having trouble with?

you are write but what i want is a linked list insde other linked list

like this picture

and what i can't to write this part
with the this adt

i solved it without this ADT but i should solved it with this ADT:-

//  Node Declaration
template <class  TYPE>
struct NODE
{
TYPE    data;
NODE   *link;
}; //  End of Node Declaration


//  List Class Declaration


template <class  TYPE, class KTYPE>
class List
{
private:
NODE<TYPE> *head;
NODE<TYPE> *pos;
NODE<TYPE> *rear;
int         count;


//       Function Declarations
bool  _insert  (NODE<TYPE>   *pPre,
TYPE          dataIn);
void  _delete  (NODE<TYPE>   *pPre,
NODE<TYPE>   *pLoc,
TYPE         *dataOutPtr);
bool  _search  (NODE<TYPE>  **pPre,
NODE<TYPE>  **pLoc,
KTYPE         key);


public:
List (void);
~List (void);
int        addNode      (TYPE   dataIn);
bool       removeNode   (KTYPE  key,
TYPE  *dataOutPtr);
bool       retrieveNode (KTYPE  Argu,
TYPE&  dataOut);
bool       getNext      (int    fromWhere,
TYPE&  dataOut);
int        listCount    (void);
bool       emptyList    (void);
bool       fullList     (void);
}; // class List


//  End of List Class Declaration


/*  =============== List Constructor  ==============
Initialize the list.
Pre    Class is being instantiated
Post   Class instantiated and initialized
*/
template <class TYPE, class KTYPE>
List<TYPE, KTYPE> :: List (void)
{
//  Statements
head     = NULL;
pos      = NULL;
rear     = NULL;
count    = 0;
} //  List Constructor


/*  ==================== addNode ===================
Inserts data into linked list.
Pre     dataIn contains data to be inserted
Post    Data inserted or error
Return -1 if overflow,
0 if successful,
1 if duplicate key
*/
template <class TYPE, class KTYPE>
int List<TYPE, KTYPE> :: addNode (TYPE dataIn)
{
//  Local Definitions
bool  found;
bool  success;


NODE<TYPE>  *pPre;
NODE<TYPE>  *pLoc;


//  Statements
found = _search (&pPre, &pLoc, dataIn.key);
if (found)
// Duplicate keys not allowed
return (+1);


success = _insert (pPre,  dataIn);
if (!success)
// Overflow
return (-1);
return (0);
}   //  addNode


/*  ===================== _insert ====================
Inserts data into a new node in the linked list.
Pre     Insertion location identified by pPre
dataIn contains data to be inserted
Post    data inserted in linked list or overflow
Return  true  if successful, false if overflow
*/
template <class TYPE, class KTYPE>
bool List<TYPE, KTYPE> :: _insert (NODE<TYPE> *pPre,
TYPE        dataIn)
{
//  Local Definitions
NODE <TYPE>  *pNew;


//  Statements
if (! (pNew = new NODE<TYPE>))
return false;


pNew->data = dataIn;
pNew->link = NULL;


if (pPre == NULL)
{
//  Adding before first node or to empty list.
pNew->link = head;
head = pNew;
} // if pPre
else
{
// Adding in middle or at end
pNew->link  = pPre->link;
pPre->link  = pNew;
} // if else


// Now check for add at end of list
if (pNew->link == NULL)
// Adding to empty list. Set rear
rear = pNew;


count++;


return true;
}   // _insert


/*  ================== removeNode ==================
Removes data from linked list.
Pre    dltkey is identifier of node to be deleted
pDataOut is pointer to data variable to
receive a copy of the deleted data
Post   data copied to output variable and node
deleted or not found
Return false if not found
true  if deleted
*/
template <class TYPE, class KTYPE>
bool List<TYPE, KTYPE> ::
removeNode (KTYPE dltkey, TYPE *pDataOut)
{
//  Local Definitions
bool         found;
NODE<TYPE>  *pPre;
NODE<TYPE>  *pLoc;


//  Statements
found = _search (&pPre, &pLoc, dltkey);
if (found)
_delete (pPre, pLoc, pDataOut);
return found;
} // removeNode


/*  =================== _delete ==================
Deletes data from a linked list and returns
data to calling module.
Pre  pPre is a pointer to predecessor node
pLoc is a pointer to target node
pDataOut is pointer to output data area
Post Data have been deleted and returned
Data memory has been recycled
*/
template <class TYPE, class KTYPE>
void List<TYPE, KTYPE> :: _delete (NODE<TYPE>   *pPre,
NODE<TYPE>   *pLoc,
TYPE         *pDataOut)
{
//  Statements
*pDataOut = pLoc->data;
if (pPre == NULL)
// Deleting first node
head = pLoc->link;
else
// Deleting any other node
pPre->link = pLoc->link;


// Test for deleting last node
if (pLoc->link == NULL)
rear = pPre;


count--;
delete pLoc;


return;
}   //  _delete


/*  =================== retrieveNode ==================
Interface to search function.
Pre    key is the search argument
dataOut is variable to receive data
Post   dataOut contains located data if found
if not found, contents are unchanged
Return true if successful, false if not found
*/


template <class TYPE, class KTYPE>
bool List<TYPE, KTYPE>
:: retrieveNode (KTYPE  key, TYPE&  dataOut)
{
//  Local Definitions
bool          found;
NODE <TYPE>  *pPre;
NODE <TYPE>  *pLoc;


//  Statements
found = _search (&pPre, &pLoc, key);
if (found)
dataOut = pLoc->data;
return found;
}   // retrieveNode


/*  ==================== _search ===================
Searches list and passes back address of node
containing target and its logical predecessor.
Pre    pPre is pointer variable for predecessor
pLoc is pointer variable for found node
key  is search argument
Post   pLoc points to first node equal/greater key
-or- null if target > key of last node
pPre points to largest node smaller than key
-or- null if target < key of first node
Return true if successful, false if not found
*/
template <class TYPE, class KTYPE>
bool List<TYPE, KTYPE> :: _search (NODE<TYPE> **pPre,
NODE<TYPE> **pLoc,
KTYPE        key)
{
//  Statements
*pPre  = NULL;
*pLoc  = head;
if (count == 0)
return false;


// Test for argument > last node in list
if (key > rear->data.key)
{
*pPre = rear;
*pLoc = NULL;
return false;
} // if


while (key > (*pLoc)->data.key)
{
//  Have not found search argument location
*pPre = *pLoc;
*pLoc = (*pLoc)->link;
} // while


if (key == (*pLoc)->data.key)
//   argument found--success
return true;
else
return false;
}   //  _search


/*  =============== emptyList ==============
Returns Boolean indicating whether the
list is empty.
Pre    Nothing
Return true if empty, false if list has data
*/
template<class TYPE, class KTYPE>
bool List<TYPE, KTYPE> :: emptyList (void)
{
//  Statements
return (count == 0);
}   //  emptyList


/*  =================== fullList ==================
Returns Boolean indicating whether the list is full
or has room for more data.
Pre    Nothing
Return true if full, false if room for another node
*/
template <class TYPE, class KTYPE>
bool List<TYPE, KTYPE> :: fullList (void)
{
//  Local Definitions
NODE<TYPE>  *temp;


//  Statements
if (temp = new NODE<TYPE>)
{
delete temp;
return false;
} // if


// Dynamic memory full
return true;
}   // fullList


/*  ==================== listCount ====================
Returns integer representing number of nodes in list.
Pre     Nothing
Return  count for number of nodes in list
*/
template <class TYPE, class KTYPE>
int List<TYPE, KTYPE> :: listCount(void)
{
//  Statements
return count;
}   // listCount


/*  ====================== getNext =====================
getNext traverses a linked list. Each call either starts
at the beginning of the list or returns the location of
the element in the list that was last returned.
Pre   fromWhere is 0 to start at the first element
dataOut is reference to data variable
Post   if another element, address placed in output area
Return true if another element located,
false if end of list
*/
template <class TYPE, class KTYPE>
bool List<TYPE, KTYPE> :: getNext (int    fromWhere,
TYPE&  dataOut)
{
//  Local Definitions
bool success;


//  Statements
if (fromWhere == 0)
{
// Start from first node
if (count == 0)
success = false;
else
{
pos      = head;
dataOut  = pos->data;
success  = true;
} // if else
} // if fromwhere is zero
else
{
// Continue from current position
if (pos->link == NULL)
success = false;
else
{
pos      = pos->link;
dataOut  = pos->data;
success  = true;
} // if else
} // if fromWhere else


return success;
}   // getNext


/*  =============== Destructor ==============
Deletes all data in list and recycles memory
Pre    List is being deleted
Post   Data and class structure have been deleted
*/
template<class TYPE, class KTYPE>
List<TYPE, KTYPE > :: ~List (void)
{
//  Local Definitions
NODE<TYPE>   *deletePtr;


//  Statements
if (head)
{
while (count > 0)
{
deletePtr = head;
head      = head->link;
count--;
delete  deletePtr;
} // while
} //  if
}   // Destructor

Edited 3 Years Ago by happygeek: fixed formatting

Comments
Use code tags.
Attachments
/*	Linked List Abstract Data Type

	Written by: G & F
	Date:       2/1998
	
	4/1999 Converted to C++

	Copyright (c) 2001
	Brooks/Cole Publishing Company
	Thomson International
	All Rights Reserved

	Linked List Abstract Data Type

	Node ADT Declaration.  
	TYPE is a standard or user-defined data type for which
	the operators <, >, and == is defined or overloaded.
	
*/

//	Node Declaration
	template <class  TYPE> 
	struct NODE 
	  {
	   TYPE    data;
	   NODE   *link;
	  }; //  End of Node Declaration

//	List Class Declaration

	template <class  TYPE, class KTYPE> 
	class List  
	   {
	     private:
	       NODE<TYPE> *head;
	       NODE<TYPE> *pos;
	       NODE<TYPE> *rear;
	       int         count;

//	     Function Declarations
	       bool  _insert  (NODE<TYPE>   *pPre,   
	                       TYPE          dataIn);
	       void  _delete  (NODE<TYPE>   *pPre,
	                       NODE<TYPE>   *pLoc,
	                       TYPE         *dataOutPtr);
	       bool  _search  (NODE<TYPE>  **pPre,
	                       NODE<TYPE>  **pLoc,
	                       KTYPE         key);

	     public:
	       List (void);
	      ~List (void);
	       int        addNode      (TYPE   dataIn);
	       bool       removeNode   (KTYPE  key, 
	                                TYPE  *dataOutPtr);
	       bool       retrieveNode (KTYPE  Argu, 
	                                TYPE&  dataOut);
	       bool       getNext      (int    fromWhere,  
	                                TYPE&  dataOut);
	       int        listCount    (void);
	       bool       emptyList    (void);
	       bool       fullList     (void); 
	   }; // class List 

// 	End of List Class Declaration

/* 	=============== List Constructor  ==============	
	Initialize the list.
	  Pre    Class is being instantiated
	  Post   Class instantiated and initialized
*/
template <class TYPE, class KTYPE>
List<TYPE, KTYPE> :: List (void)   
{
//	Statements 
	head     = NULL;
	pos      = NULL;
	rear     = NULL;
	count    = 0;
} //  List Constructor 

/*	==================== addNode =================== 
	Inserts data into linked list.
	   Pre     dataIn contains data to be inserted
	   Post    Data inserted or error
	   Return -1 if overflow, 
	           0 if successful,
	           1 if duplicate key
*/
template <class TYPE, class KTYPE> 
int List<TYPE, KTYPE> :: addNode (TYPE dataIn)
{
//	Local Definitions 
	bool  found;
	bool  success;

	NODE<TYPE>  *pPre;
	NODE<TYPE>  *pLoc;
	
//  Statements 
	found = _search (&pPre, &pLoc, dataIn.key);
	if (found)
	   // Duplicate keys not allowed 
	   return (+1);
	
	success = _insert (pPre,  dataIn);
	if (!success)
	   // Overflow 
	   return (-1);
	return (0);
}	//  addNode 

/*	===================== _insert ==================== 
	Inserts data into a new node in the linked list.
	   Pre     Insertion location identified by pPre
	           dataIn contains data to be inserted
	   Post    data inserted in linked list or overflow
	   Return  true  if successful, false if overflow
*/
template <class TYPE, class KTYPE>
bool List<TYPE, KTYPE> :: _insert (NODE<TYPE> *pPre,  
                                   TYPE        dataIn)
{
//	Local Definitions 
	NODE <TYPE>  *pNew;

//	Statements 
	if (! (pNew = new NODE<TYPE>))
	   return false;
	
	pNew->data = dataIn; 
	pNew->link = NULL; 
		 
	if (pPre == NULL)
	   {
	    //  Adding before first node or to empty list. 
	    pNew->link = head;
	    head = pNew;
	   } // if pPre 
	else
	    {
	     // Adding in middle or at end 
	     pNew->link  = pPre->link;
	     pPre->link  = pNew;
	    } // if else  
	 
	     // Now check for add at end of list 
	     if (pNew->link == NULL)
	        // Adding to empty list. Set rear  
	        rear = pNew;

	count++;

	return true;
}	// _insert 

/* 	================== removeNode ================== 
	Removes data from linked list. 
	   Pre    dltkey is identifier of node to be deleted
	          pDataOut is pointer to data variable to 
	          receive a copy of the deleted data
	   Post   data copied to output variable and node
	          deleted or not found
	   Return false if not found
	          true  if deleted
*/
template <class TYPE, class KTYPE>
bool List<TYPE, KTYPE> ::  
          removeNode (KTYPE dltkey, TYPE *pDataOut)
{
//	Local Definitions 
	bool         found;
	NODE<TYPE>  *pPre;
	NODE<TYPE>  *pLoc;
	
//	Statements 
	found = _search (&pPre, &pLoc, dltkey);
	if (found)
	    _delete (pPre, pLoc, pDataOut);
	return found;
} // removeNode

/*	=================== _delete ================== 
	Deletes data from a linked list and returns 
	data to calling module.
	   Pre  pPre is a pointer to predecessor node
	        pLoc is a pointer to target node
	        pDataOut is pointer to output data area
	   Post Data have been deleted and returned 
	        Data memory has been recycled
*/
template <class TYPE, class KTYPE>
void List<TYPE, KTYPE> :: _delete (NODE<TYPE>   *pPre,
                                   NODE<TYPE>   *pLoc, 
                                   TYPE         *pDataOut) 
{
//	Statements 
	*pDataOut = pLoc->data;
	if (pPre == NULL)
	    // Deleting first node 
	    head = pLoc->link;  
	else
	    // Deleting any other node
	    pPre->link = pLoc->link;
	 
	// Test for deleting last node 
	if (pLoc->link == NULL)
	   rear = pPre;

	count--;
	delete pLoc;
  
	return;
}	//  _delete 

/*	=================== retrieveNode ================== 
	Interface to search function. 
	   Pre    key is the search argument
	          dataOut is variable to receive data
	   Post   dataOut contains located data if found
	          if not found, contents are unchanged
	   Return true if successful, false if not found
*/

template <class TYPE, class KTYPE>
bool List<TYPE, KTYPE> 
         :: retrieveNode (KTYPE  key, TYPE&  dataOut)
{
//	Local Definitions 
	bool          found;
	NODE <TYPE>  *pPre;
	NODE <TYPE>  *pLoc;

//	Statements 
	found = _search (&pPre, &pLoc, key);
	if (found)
	   dataOut = pLoc->data;
	return found;
}	// retrieveNode 

/*	==================== _search =================== 
	Searches list and passes back address of node 
	containing target and its logical predecessor.
	   Pre    pPre is pointer variable for predecessor
	          pLoc is pointer variable for found node
	          key  is search argument
	   Post   pLoc points to first node equal/greater key 
	          -or- null if target > key of last node
	          pPre points to largest node smaller than key
	          -or- null if target < key of first node
	   Return true if successful, false if not found
*/
template <class TYPE, class KTYPE> 
bool List<TYPE, KTYPE> :: _search (NODE<TYPE> **pPre,  
                                   NODE<TYPE> **pLoc,
                                   KTYPE        key)
{
//	Statements 
	*pPre  = NULL;
	*pLoc  = head;
	if (count == 0)
	    return false;
	
	// Test for argument > last node in list 
	if (key > rear->data.key) 
	   {
	    *pPre = rear;
	    *pLoc = NULL;
	    return false;
	   } // if 

	while (key > (*pLoc)->data.key)
	   {
	    //  Have not found search argument location 
	    *pPre = *pLoc;
	    *pLoc = (*pLoc)->link;
	   } // while 
	
	if (key == (*pLoc)->data.key)
	    //   argument found--success 
	    return true;
	else
	    return false;
}	//  _search 

/*	=============== emptyList ============== 
	Returns Boolean indicating whether the
	list is empty.
	   Pre    Nothing 
	   Return true if empty, false if list has data 
*/
template<class TYPE, class KTYPE> 
bool List<TYPE, KTYPE> :: emptyList (void) 
{
//	Statements 
 	return (count == 0);
}	//  emptyList 

/*	=================== fullList ================== 
	Returns Boolean indicating whether the list is full
	or has room for more data. 
	   Pre    Nothing 
	   Return true if full, false if room for another node
*/
template <class TYPE, class KTYPE>
bool List<TYPE, KTYPE> :: fullList (void) 
{
//	Local Definitions  
	NODE<TYPE>  *temp;

//	Statements 
	if (temp = new NODE<TYPE>)
	   {
	    delete temp;
	    return false;
	   } // if

	// Dynamic memory full 
	return true;
}	// fullList 

/*	==================== listCount ==================== 
	Returns integer representing number of nodes in list.
	   Pre     Nothing
	   Return  count for number of nodes in list
*/
template <class TYPE, class KTYPE>
int List<TYPE, KTYPE> :: listCount(void) 
{
//	Statements 
	return count;	
}	// listCount

/*	====================== getNext ===================== 
	getNext traverses a linked list. Each call either starts 
	at the beginning of the list or returns the location of  
	the element in the list that was last returned.
	   Pre   fromWhere is 0 to start at the first element
	         dataOut is reference to data variable 
	   Post   if another element, address placed in output area
	   Return true if another element located, 
	          false if end of list
*/
template <class TYPE, class KTYPE> 
bool List<TYPE, KTYPE> :: getNext (int    fromWhere,
                                   TYPE&  dataOut)
{
//	Local Definitions 
	bool success;

//	Statements 
	if (fromWhere == 0)
	   {
	    // Start from first node 
	    if (count == 0)
	        success = false;
	    else
	       {
	        pos      = head;
	        dataOut  = pos->data;
	        success  = true;
	       } // if else 
	   } // if fromwhere is zero
	else
	   {
	    // Continue from current position 
	    if (pos->link == NULL)
	        success = false;
	    else
	       {
	        pos      = pos->link;
	        dataOut  = pos->data;
	        success  = true;
	       } // if else 
	   } // if fromWhere else 
	
	return success;
}	// getNext

/*	=============== Destructor ============== 
	Deletes all data in list and recycles memory
	   Pre    List is being deleted 
	   Post   Data and class structure have been deleted
*/
template<class TYPE, class KTYPE> 
List<TYPE, KTYP
pr.gif 20.9 KB

>A hash table is basically a linked list of linked lists
An array of linked lists you mean. If the table is implemented as a linked list then the time required to traverse to the proper hash index would dominate search times and it's not much of an improvement. If the table is an array then indexing can be done in constant time and then search time is dominated by the length of the chains, which, because they should be short, is very fast.

>my ques. here is
Can you be more specific as to what part of the program you're having trouble with?

Ahh yes, oopsies. But regardless, the program I have written still reads from a text file and puts into a linked list ;)

This article has been dead for over six months. Start a new discussion instead.