Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › C++ List Searching: Homework Help
New Posts  All Forums:Forum Nav:

C++ List Searching: Homework Help

post #1 of 18
Thread Starter 
Hey Everyone,

So I have a homework assignment on Linked Lists and their applications. In this particular case I have a linked list of movies from an input file and have created a linked list out of all of the parts of the file into different variables such as title, actor, genre, etc. Next I have to allow a user to search the linked list for any search values such as a title, an author, genre and so on. I have everything sorted out and this algorithm works but in my mind it seems VERY inefficient, I've done as best I could at optimizing it by limiting the if statements to run when the searchType is equal to a given enumeration passed in from the calling function but I still find this code inefficient but my professor has required that I do this all with one while loop. I'm clearly missing a better way to do this am I not? If not then as I said it works but OCN is all about "the pursuit of performance" and I like to put my all into these assignments.
Code:
Movie * SearchList(Movie *movie,           // List of movies - CALC
   int searchType,   // Type of item we want to search
   string searchItem = "", // If string, the string to search
   int searchInt = 0)      // If int, the int to search
{
bool found;            // Control boolean
Movie *foundList;         // List of found items
Movie *search;      // Temporary assigned list

search = new Movie;
foundList = NULL;

while(movie != NULL)
{
found = false;
if(searchType == GENRE &&
 (movie->genre == searchItem || movie->altGenre == searchItem))
{
found = true;
}
else if(searchType == TITLE &&
searchItem == movie->title)
{
found = true;
}
else if(searchType == ACTOR &&
(movie->mainChar == searchItem || movie->secChar == searchItem))
{
found = true;
}
else if(searchType == RATING && movie->rating == searchInt)
{
found = true;
}
else if(searchType == YEAR && movie->year == searchInt)
{
found = true;
}

// If we found a file, add it to our "search" list
if(found)
{
// Possible alternative
// *search = *movie

// Copy our current movie node to our search node
search->altGenre = movie->altGenre;
search->genre = movie->genre;
search->year = movie->year;
search->mainChar = movie->mainChar;
search->rating = movie->rating;
search->secChar = movie->secChar;
search->title = movie->title;

search->next = foundList;
foundList = search;

search = new Movie;
} // End if
movie = movie->next;
} // End While

delete search;

return foundList;
}

Thanks for any insight into this biggrin.gif
DeadHost
(16 items)
 
  
CPUMotherboardGraphicsRAM
Core i5 2500k 4.7 Ghz ASRock Z68 Extreme4 MSI GTX 670 PE 8 GB Crucial Ballistix 
Hard DriveHard DriveCoolingOS
1 TB WD Green Crucial M4 Antec Kuhler H20 620 Windows 7 Ultimate x86_64 SP1 
MonitorMonitorKeyboardPower
HPW23something Dell U2312HM CM Storm Quickfire Pro OCZ 600W 
CaseMouseMouse PadAudio
Fractal Design Define R4 Logitech G400 Steelseries Qck Pioneer VSX-821 
  hide details  
Reply
DeadHost
(16 items)
 
  
CPUMotherboardGraphicsRAM
Core i5 2500k 4.7 Ghz ASRock Z68 Extreme4 MSI GTX 670 PE 8 GB Crucial Ballistix 
Hard DriveHard DriveCoolingOS
1 TB WD Green Crucial M4 Antec Kuhler H20 620 Windows 7 Ultimate x86_64 SP1 
MonitorMonitorKeyboardPower
HPW23something Dell U2312HM CM Storm Quickfire Pro OCZ 600W 
CaseMouseMouse PadAudio
Fractal Design Define R4 Logitech G400 Steelseries Qck Pioneer VSX-821 
  hide details  
Reply
post #2 of 18
All in all it looks pretty good.

I would have personally used a switch statement, then assigned the stuff outside of the loop instead of searching until not null just break out once found. since you're returning after setting it anyways.
 
Play Server
(10 items)
 
NAS
(14 items)
 
CPUCPUMotherboardRAM
Intel Xeon L5640 Intel Xeon L5640 Dell R710 Mobo Hynix 144GB DDR3 ECC PC3L-10600R 
Hard DrivePowerCaseOther
Intel X25-M G2 80GB Redundant 840W PSU Dell 710 2.5" - Google Search Appliance Dell Perc H700 Raid Controller 
OtherOther
Dell iDRAC6 Enterprise Mellanox Connectx-2 10Gb SFP+ NIC 
CPUCPUMotherboardRAM
Intel Xeon E5-2670 v1 Intel Xeon E5-2670 v1 SuperMicro X9DRL-iF 64GB Kingston ECC (kvr16r11d4/16HA) 
Hard DriveHard DriveHard DriveCooling
12x 4TB HGST 5K4000 SanDisk SSD 960GB (cache) 6x 8TB WD Red Scythe AP-29 
CoolingOSPowerCase
2x Noctua U9DXi4 FreeNAS Corsair AX750 Norco RPC-4224 
OtherOther
3x LSI 9211-8i (HBA) Mellanox Connectx-2 10Gb NIC 
  hide details  
Reply
 
Play Server
(10 items)
 
NAS
(14 items)
 
CPUCPUMotherboardRAM
Intel Xeon L5640 Intel Xeon L5640 Dell R710 Mobo Hynix 144GB DDR3 ECC PC3L-10600R 
Hard DrivePowerCaseOther
Intel X25-M G2 80GB Redundant 840W PSU Dell 710 2.5" - Google Search Appliance Dell Perc H700 Raid Controller 
OtherOther
Dell iDRAC6 Enterprise Mellanox Connectx-2 10Gb SFP+ NIC 
CPUCPUMotherboardRAM
Intel Xeon E5-2670 v1 Intel Xeon E5-2670 v1 SuperMicro X9DRL-iF 64GB Kingston ECC (kvr16r11d4/16HA) 
Hard DriveHard DriveHard DriveCooling
12x 4TB HGST 5K4000 SanDisk SSD 960GB (cache) 6x 8TB WD Red Scythe AP-29 
CoolingOSPowerCase
2x Noctua U9DXi4 FreeNAS Corsair AX750 Norco RPC-4224 
OtherOther
3x LSI 9211-8i (HBA) Mellanox Connectx-2 10Gb NIC 
  hide details  
Reply
post #3 of 18

Searching a linked list IS inefficient since you have to iterate over the entire list. This isn't that bad if you're just searching through a couple dozen items. This gets worse the more items you add.

 

Later you'll learn about things like binary trees which are easy and fast to search.

Underground
(14 items)
 
  
CPUMotherboardGraphicsRAM
Core i7 920 C0 ASUS P6T6 WS Revolution GTX 460 TR3X6G1600C8D 
Hard DriveOptical DriveCoolingOS
WD1001FALS SAMSUNG SH-S223F 22X DVD MULTI Corsair H50 Fedora 16 KDE x86_64 
MonitorKeyboardPowerCase
HP w19b Microsoft Comfort Curve Corsair CX600 Thermaltake Armor VA8003BWS 
MouseMouse Pad
Razer DeathAdder Black 
  hide details  
Reply
Underground
(14 items)
 
  
CPUMotherboardGraphicsRAM
Core i7 920 C0 ASUS P6T6 WS Revolution GTX 460 TR3X6G1600C8D 
Hard DriveOptical DriveCoolingOS
WD1001FALS SAMSUNG SH-S223F 22X DVD MULTI Corsair H50 Fedora 16 KDE x86_64 
MonitorKeyboardPowerCase
HP w19b Microsoft Comfort Curve Corsair CX600 Thermaltake Armor VA8003BWS 
MouseMouse Pad
Razer DeathAdder Black 
  hide details  
Reply
post #4 of 18
Your code isn't a C++ list - it's an object-oriented C list.
Akiyama Mio
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6420 @ stock, 0.98v Asus P5N-E SLI Gainward GTX 460 1GB @ 800/1600/1900 2x2GB Kingston @ 800MHz 5-5-5-15 2T 
Hard DriveOptical DriveOSMonitor
WD 250GB, 320GB SATA/3, 16MB Cache, Seagate 1TB LG GSA-H62N 18x SATA Ubuntu 9.10 x86 & Win7 x86 Asus VW222U 
KeyboardPowerCase
Logitech Classic Corsair 650HX NZXT Apollo Black 
  hide details  
Reply
Akiyama Mio
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6420 @ stock, 0.98v Asus P5N-E SLI Gainward GTX 460 1GB @ 800/1600/1900 2x2GB Kingston @ 800MHz 5-5-5-15 2T 
Hard DriveOptical DriveOSMonitor
WD 250GB, 320GB SATA/3, 16MB Cache, Seagate 1TB LG GSA-H62N 18x SATA Ubuntu 9.10 x86 & Win7 x86 Asus VW222U 
KeyboardPowerCase
Logitech Classic Corsair 650HX NZXT Apollo Black 
  hide details  
Reply
post #5 of 18
Thread Starter 
Quote:
Originally Posted by Coma View Post

Your code isn't a C++ list - it's an object-oriented C list.

Isn't a linked list just a data structure that can be applied in any language? If so I thought C++ was an extension of C that among the changes added object orientation

Quote:
Originally Posted by error10 View Post

Searching a linked list IS inefficient since you have to iterate over the entire list. This isn't that bad if you're just searching through a couple dozen items. This gets worse the more items you add.

Later you'll learn about things like binary trees which are easy and fast to search.

Unfortunately I do in fact have a large input file to process but I guess it's just a must in this case since it is in fact a homework requirement. Fortunately, however, I did get my question answered and am really grateful for the help! smile.gif
DeadHost
(16 items)
 
  
CPUMotherboardGraphicsRAM
Core i5 2500k 4.7 Ghz ASRock Z68 Extreme4 MSI GTX 670 PE 8 GB Crucial Ballistix 
Hard DriveHard DriveCoolingOS
1 TB WD Green Crucial M4 Antec Kuhler H20 620 Windows 7 Ultimate x86_64 SP1 
MonitorMonitorKeyboardPower
HPW23something Dell U2312HM CM Storm Quickfire Pro OCZ 600W 
CaseMouseMouse PadAudio
Fractal Design Define R4 Logitech G400 Steelseries Qck Pioneer VSX-821 
  hide details  
Reply
DeadHost
(16 items)
 
  
CPUMotherboardGraphicsRAM
Core i5 2500k 4.7 Ghz ASRock Z68 Extreme4 MSI GTX 670 PE 8 GB Crucial Ballistix 
Hard DriveHard DriveCoolingOS
1 TB WD Green Crucial M4 Antec Kuhler H20 620 Windows 7 Ultimate x86_64 SP1 
MonitorMonitorKeyboardPower
HPW23something Dell U2312HM CM Storm Quickfire Pro OCZ 600W 
CaseMouseMouse PadAudio
Fractal Design Define R4 Logitech G400 Steelseries Qck Pioneer VSX-821 
  hide details  
Reply
post #6 of 18
Quote:
Originally Posted by thelamacmdr View Post

Isn't a linked list just a data structure that can be applied in any language? If so I thought C++ was an extension of C that among the changes added object orientation
C++ adds support for a specific flavor object-oriented code. It allows you to define methods within a class, and protect members of the class from being accessed externally.

If you're just learning this now, then don't be alarmed. It's perfectly normal for instructors to start with what is essentially procedural code - C, even when teaching C++, just to get you in touch with basics. You just need to be aware that this isn't C++ and it would be considered very bad code if you were to write it professionally. Some teachers don't bother to mention this. If you don't end up learning how (and why) to do the following at school, and intend to be a good programmer, do some reading on polymorphism and abstraction.

If you hadn't used std::string, your code would've compiled in a C compiler. It is object-oriented code, because you have a struct (an object) - Movie that holds data about a real life object, and you have a function which receives this type and performs operations on it.

But the Movie object doesn't have any methods, and your function directly accesses its members. Also, it's not a good object, because it doesn't just describe a movie - it also describes a linked list.

A good C++ OO implementation for this would be like this:
- A List template interface class that defines a common interface for all Lists, for any type T.
- A LinkedList class that implements the List interface, that implements a linked list (on memory) for any type T.
- A Movie class which represents a movie and allows you to query its properties (if this was something more complex, you might have defined an interface and Movie would've been MovieImpl)
- A MovieDatabase class which holds a LinkedList object and can search it for movies by a specific property.

Note that each object has only one role.

Also, the use of interfaces allows you to easily replace the implementation and allow polymorphism to do the hard work. For example, you might replace LinkedList with a list that stores the Movies in a MySQL database, and getting the next movie actually causes it to construct a Movie object from the data in the next result from the result set.
Edited by Coma - 11/18/11 at 3:54pm
Akiyama Mio
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6420 @ stock, 0.98v Asus P5N-E SLI Gainward GTX 460 1GB @ 800/1600/1900 2x2GB Kingston @ 800MHz 5-5-5-15 2T 
Hard DriveOptical DriveOSMonitor
WD 250GB, 320GB SATA/3, 16MB Cache, Seagate 1TB LG GSA-H62N 18x SATA Ubuntu 9.10 x86 & Win7 x86 Asus VW222U 
KeyboardPowerCase
Logitech Classic Corsair 650HX NZXT Apollo Black 
  hide details  
Reply
Akiyama Mio
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6420 @ stock, 0.98v Asus P5N-E SLI Gainward GTX 460 1GB @ 800/1600/1900 2x2GB Kingston @ 800MHz 5-5-5-15 2T 
Hard DriveOptical DriveOSMonitor
WD 250GB, 320GB SATA/3, 16MB Cache, Seagate 1TB LG GSA-H62N 18x SATA Ubuntu 9.10 x86 & Win7 x86 Asus VW222U 
KeyboardPowerCase
Logitech Classic Corsair 650HX NZXT Apollo Black 
  hide details  
Reply
post #7 of 18
Thread Starter 
....This makes me wish I had paid more attention to my C# and Java classes. But I did ask my professor about the advantages of using a struct over a class and she gave me a reasonable answer I guess but your explanation of it gives way to the fact that OOP was created for a reason!
DeadHost
(16 items)
 
  
CPUMotherboardGraphicsRAM
Core i5 2500k 4.7 Ghz ASRock Z68 Extreme4 MSI GTX 670 PE 8 GB Crucial Ballistix 
Hard DriveHard DriveCoolingOS
1 TB WD Green Crucial M4 Antec Kuhler H20 620 Windows 7 Ultimate x86_64 SP1 
MonitorMonitorKeyboardPower
HPW23something Dell U2312HM CM Storm Quickfire Pro OCZ 600W 
CaseMouseMouse PadAudio
Fractal Design Define R4 Logitech G400 Steelseries Qck Pioneer VSX-821 
  hide details  
Reply
DeadHost
(16 items)
 
  
CPUMotherboardGraphicsRAM
Core i5 2500k 4.7 Ghz ASRock Z68 Extreme4 MSI GTX 670 PE 8 GB Crucial Ballistix 
Hard DriveHard DriveCoolingOS
1 TB WD Green Crucial M4 Antec Kuhler H20 620 Windows 7 Ultimate x86_64 SP1 
MonitorMonitorKeyboardPower
HPW23something Dell U2312HM CM Storm Quickfire Pro OCZ 600W 
CaseMouseMouse PadAudio
Fractal Design Define R4 Logitech G400 Steelseries Qck Pioneer VSX-821 
  hide details  
Reply
post #8 of 18
Quote:
Originally Posted by Coma View Post

A good C++ OO implementation for this would be like this:
- A List template interface class that defines a common interface for all Lists, for any type T.
- A LinkedList class that implements the List interface, that implements a linked list (on memory) for any type T.
- A Movie class which represents a movie and allows you to query its properties (if this was something more complex, you might have defined an interface and Movie would've been MovieImpl)
- A MovieDatabase class which holds a LinkedList object and can search it for movies by a specific property.
+1 (or ++, in this case biggrin.gif)
As Coma stated, that may be able to be compiled in C++, but that's not object oriented. It really depends what your professor wants. If they want you to do something object oriented, you'll have to define your linked list class and it's methods (i.e. search functions), then instantiate it. Seriously, Coma gave a great basic outline there. Otherwise, if your professor is just teaching you C++ syntax right now, he may not care. But a linked list is really one of the first structures you'll learn about with object oriented programming, so...

As for all the if/else stuff, use a switch on searchType. Also, your while condition isn't all that elegant., though it works. When in doubt...http://msdn.microsoft.com/en-us/library/k0t5wee3%28v=vs.80%29.aspx. Switch statement example, complete with a while loop that auto-increments every iteration. thumb.gif
post #9 of 18
Thread Starter 
Hmm switch statement is more efficient, I have no idea why that escaped my mind O_O when they say c = *buffer++ , what exactly does ++ increment in that case?
DeadHost
(16 items)
 
  
CPUMotherboardGraphicsRAM
Core i5 2500k 4.7 Ghz ASRock Z68 Extreme4 MSI GTX 670 PE 8 GB Crucial Ballistix 
Hard DriveHard DriveCoolingOS
1 TB WD Green Crucial M4 Antec Kuhler H20 620 Windows 7 Ultimate x86_64 SP1 
MonitorMonitorKeyboardPower
HPW23something Dell U2312HM CM Storm Quickfire Pro OCZ 600W 
CaseMouseMouse PadAudio
Fractal Design Define R4 Logitech G400 Steelseries Qck Pioneer VSX-821 
  hide details  
Reply
DeadHost
(16 items)
 
  
CPUMotherboardGraphicsRAM
Core i5 2500k 4.7 Ghz ASRock Z68 Extreme4 MSI GTX 670 PE 8 GB Crucial Ballistix 
Hard DriveHard DriveCoolingOS
1 TB WD Green Crucial M4 Antec Kuhler H20 620 Windows 7 Ultimate x86_64 SP1 
MonitorMonitorKeyboardPower
HPW23something Dell U2312HM CM Storm Quickfire Pro OCZ 600W 
CaseMouseMouse PadAudio
Fractal Design Define R4 Logitech G400 Steelseries Qck Pioneer VSX-821 
  hide details  
Reply
post #10 of 18
char *buffer = "Any character stream";

So they set the buffer variable to a character string. Then:

while ( c = *buffer++ )

They assign the char variable c to the next character value in buffer. Literally, they are checking each character one at a time.

Edit: Not sure why this stuck in my head, but more to the point of your question, char *buffer is basically a pointer to the string, not a true character array (sorry for any confusion there). The ++ is just incrementing what the pointer is pointing at. So when the while condition is checked, the pointer is incremented to the next character, then that value is assigned to the variable c. Hopefully that makes a bit more sense with what your actual question was.
Edited by jmaertens - 11/19/11 at 10:03am
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › C++ List Searching: Homework Help