C Board  

Go Back   C Board > General Programming Boards > C++ Programming

Reply
 
LinkBack Thread Tools Display Modes
Old 05-09-2008, 12:27 PM   #1
Registered User
 
Join Date: Mar 2008
Posts: 28
pointers and linked lists in place of arrays

So im trying to convert this program, to use pointers and linked list. I really have not done anything with them so im here to ask for help!


Here to read and pop the array.
Code:
    // Read names and pop
    for (i=0; i < NUMNAMES; i++)
    {
        // input
        in_stream >> popularity >> boyName >> girlName;   
        // store all data in array
        boyNames[i] = boyName;
        girlNames[i] = girlName;   
    }
    in_stream.close();
Here is my array for search

Code:
    // Search for name in arrays
    boyPopularity = -1;
    girlPopularity = -1;
    
    for (i=0; i < NUMNAMES; i++)
    {
        if (boyNames[i] == targetName)
        {
              boyPopularity = i+1;          
        }
        if (girlNames[i] == targetName)
        {
              girlPopularity = i+1;
        }
    }
Here is my output, would i need to rewrite this completely for use with pointers and linked lists?
Code:
    // Output results if matched
    cout << targetName << " is ";
    if (boyPopularity > 0)
    {
    cout << "ranked " << boyPopularity << " in popularity among boys.\n";
    }
    
    else
    {
        cout << "not ranked among the top 1000 boy names.\n";
    }
    cout << targetName << " is ";
    if (girlPopularity > 0)
    {
        cout << "ranked " << girlPopularity << " in popularity among girls.\n";
    }
    else
    {
        cout << "not ranked among the top 1000 girl names.\n";
    }
    system("PAUSE");
    return 0;
}
So really im not sure what to do to start ive never used pointers before and would like some help converting what i have, thanks!
kordric is offline   Reply With Quote
Old 05-09-2008, 12:43 PM   #2
Afraid of widths
 
medievalelks's Avatar
 
Join Date: Apr 2008
Location: Chicago
Posts: 887
std::list
medievalelks is offline   Reply With Quote
Old 05-09-2008, 01:55 PM   #3
Registered User
 
Join Date: May 2008
Posts: 4
Forgive me as I'm more of a C coder and am learning C++ but here's a quick side-by-side of arrays vs. linked lists:

Array (using chars for example)

Code:
char charArr[] = "Test String";
int i = 0;
for(i=0;i<11;i++){ cout << "char " << i << "is " << charArr[i] << endl; }

Same thing in a linked list: (It's more complicated as we need to define the data structure, populate the list, use the list, and then free the memory we populated)
Code:
// Define the data structure
typedef struct _charStruct {
  char c;
  struct _charStruct *next;
} charStruct;

// populate the data structure
char str[] = "Test String";
int i = 0;
charStruct *firstCharStruct = NULL;
charStruct *ptr = NULL;
charStruct *new = NULL;

for(i=0; i<11;i++){
  new = malloc(sizeof(charStruct));
  new->c = str[i];
  new->next = NULL;
  if(ptr){
    ptr->next = new;
  }
  ptr = new;
  if(!firstCharStruct){ firstCharStruct = new; }
}

// Now that it's populated, loop through it and print each character
for(ptr=firstCharStruct;ptr;ptr=ptr->next){
  cout << "Character: " << ptr->c << endl;
}

// We also need to delete the dynamically allocated memory:
ptr = firstCharStruct;
while(ptr){
  new = ptr; // Might as well re-use the new pointer we declared before
  ptr = ptr->next; //pointer will eventually hit the last member of the list whose "next"
                            // member will be NULL, ending the loop
  free(new);
}

Yes, the code for linked lists is more complicated but linked lists are great for lists of complex data structures of unknown variable sizes. For very simple or static things they are total overkill.

If your code already works, why are you trying to map it to linked lists?

In any event, sorry for all the code. I hope that helps!
samblack is offline   Reply With Quote
Old 05-09-2008, 02:57 PM   #4
The larch
 
Join Date: May 2006
Posts: 3,062
If you are asking for the best way to tackle this task, then no, implementing your own linked list is not a good idea (unless you really want to practice writing a linked list).

Rather you might use a std::vector (which is essentially an array, but you can add as many items to it as you like) to store the names, or you might try a std::map<std::string, int> to store both the name and the popularity together. map provides faster lookups for this kind of task.


However, an area where you might improve your code is doing away with repetitious code. As it is, there is separate code for boy and girl names, yet the only difference between them is the array they work with and the fact that one uses a literal noun "boy" where the other has "girl".

If you used a 2-element array that holds the list of boy and the list of girl names, and perhaps a 2-string array that holds the strings "boy" and "girl", you might be able to let a loop handle the repetitions.
__________________
I might be wrong.

Quote:
Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
Quoted more than 1000 times (I hope).
anon is online now   Reply With Quote
Old 05-09-2008, 03:32 PM   #5
Algorithm Dissector
 
iMalc's Avatar
 
Join Date: Dec 2005
Location: New Zealand
Posts: 2,434
Quote:
Originally Posted by samblack View Post
Forgive me as I'm more of a C coder and am learning C++ but here's a quick side-by-side of arrays vs. linked lists:

Code:
// Define the data structure
typedef struct _charStruct {
  char c;
  struct _charStruct *next;
} charStruct;

// populate the data structure
char str[] = "Test String";
int i = 0;
charStruct *firstCharStruct = NULL;
charStruct *ptr = NULL;
charStruct *new = NULL;

for(i=0; i<11;i++){
  new = malloc(sizeof(charStruct));
  new->c = str[i];
  new->next = NULL;
  if(ptr){
    ptr->next = new;
  }
  ptr = new;
  if(!firstCharStruct){ firstCharStruct = new; }
}

// Now that it's populated, loop through it and print each character
for(ptr=firstCharStruct;ptr;ptr=ptr->next){
  cout << "Character: " << ptr->c << endl;
}

// We also need to delete the dynamically allocated memory:
ptr = firstCharStruct;
while(ptr){
  new = ptr; // Might as well re-use the new pointer we declared before
  ptr = ptr->next; //pointer will eventually hit the last member of the list whose "next"
                            // member will be NULL, ending the loop
  free(new);
}
That is neither C++ code, nor C code and cannot compile as either one. ('new' cannot be used as a variable name in C++, and 'cout' cannot be used in C)

For a list in C++ you use std::list.
If you want to implement your own linked list then you're best getting a book or other reference source, possibly a web tutorial, and writing your own as you learn from it. Copying someone else's from here wont teach you how to do it, and it may teach you bad habbits.
__________________
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
iMalc is offline   Reply With Quote
Old 05-09-2008, 04:36 PM   #6
Registered User
 
Join Date: Mar 2008
Posts: 28
My goal here is to convert this into a linked list, I really am trying to understand all the different aspects, and this is what im trying to learn right now. This is why i was asking specifically for linked list.

Its not that i wish to copy but gain ideas on how to implment it, with the same sort of basis that i used on the arrays.
kordric is offline   Reply With Quote
Old 05-14-2008, 12:57 AM   #7
Registered User
 
Join Date: Mar 2008
Posts: 28
Okay i need some help, with my original code using arrays i got this:

Code:
Enter the first name, to see popularity:
Justice

Justice is ranked 406 in popularity among boys.
Justice is ranked 497 in popularity among girls.
Press any key to continue . . .
Now my new code i want it to do the same thing.
Heres what i have so far.
Code:
	bool terminate = false;
	while (!terminate)
	{
		cout << "Please enter a name or type 'done' to finshes searching.\nName: ";
		string target;
		cin  >> target;
		
		tempPtr = topList;

		while ((tempPtr->boysName != target) && (tempPtr->girlsName != target) &&
			(tempPtr->link != NULL))
		{
			tempPtr = tempPtr->link;
		}
		
		if (target == "done")
			terminate = true;
			
		
		else if (tempPtr->boysName == target)
		{
			cout << target << " is ranked " << tempPtr->rank << " among boys' names.\n" << endl;
        }
        
    	else if (tempPtr->girlsName == target)
    	{
             
			cout << target << " is ranked " << tempPtr->rank << " among girls' names.\n" << endl;
        }
		else
			cout << "baby name not found in databaase\n" << endl;
	}
Obviously right now it outputs the last found name and displays its rank. But i need to have it search the list for boys names first display, then clear, and search again for girls. This is only using linked lists and pointers.

Thanks!
kordric is offline   Reply With Quote
Old 05-14-2008, 02:05 AM   #8
Kernel hacker
 
Join Date: Jul 2007
Location: Farncombe, Surrey, England
Posts: 15,686
If you are planning to search for "names that can be both boys and girls", then you could solve that by keeping track of "boy" and "girl" pointers, so when you find the name, either boy or girl, then you store that in "boy" or "girl" pointer, then continue until you've either found the end of the list or both boy and girl names.

--
Mats
__________________
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
matsp is offline   Reply With Quote
Old 05-14-2008, 10:59 AM   #9
Registered User
 
Join Date: Mar 2008
Posts: 28
How would i make it continue i can only seem to get it to go all the way through and used the last one it found.
kordric is offline   Reply With Quote
Reply

Tags
array, linked list, pointers

Thread Tools
Display Modes

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Help with linked lists/ pointers anything25 C Programming 14 06-26-2009 02:41 PM
Pointers to pointers in linked lists G4B3 C++ Programming 2 07-23-2008 03:54 AM
Double pointers and linked lists. simo_r C Programming 2 05-06-2008 04:25 AM
Linked Lists & Pointers fkheng C Programming 4 06-10-2003 07:26 AM
Problem with pointers and linked lists bsimbeck C Programming 2 02-21-2003 11:05 AM


All times are GMT -6. The time now is 01:16 PM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2009, Jelsoft Enterprises Ltd.
Search Engine Optimization by vBSEO 3.3.0 RC2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22