   Linked Lists & Structures Help
  Hello everyone,I am new to the forums but I have been skimming this wonderful site every once in a while. I have an interest in eventually programming videogames. I thought it would be best to start off, though, by taking a traditional C++ course. My dad, however, doesn't really like the idea so he's not willing to pay for any classes or even books. Anyhow, I ended up borrowing a book from a friend who has some C++ books. I have so far only programmed some simple programs and am not very far in the book but my friend is going to be leaving for college soon so I have to give him the book back yesterday. Now my "problem" is basically I want to try to understand some of the exercises in the book. I wrote down a couple that I was stuck on:(From a lesson in the book on structures)Quote:Create a program with the ability to store up to 100 of your friends’ names, birthdays, and phone numbers in character string arrays. -Make sure it has a menu to give the user the choice of entering new data or printing data. Use separate functions to enter and print data. -Store all your information in a struct array. (from a lesson in the book about linked lists)Quote:Create a class that will automate the creation and deletion of objects in your linked list.  It should also have functions that will help you go through your linked list.  You should have these functions:-Class Constructor  Will set your variables to their default values.-Class Destructor  Will erase all items in your list.-void Insert(varType varName); This will add new items to your list.-void RemoveAll(); This will erase all items in your list when called.-void Reset(); This will reset your position in the list.-varType* GetNext();  Will return the address of the next item in your list. I also, ahead of time, made sure to get down some of the sample code the book gave:(structures one)#include <iostream> using namespace std;const int NUMSTUDENTS = 10; const int NAMELENGTH = 20; struct Student {char firstname[NAMELENGTH]; char lastname[NAMELENGTH]; int age; int grade; };  int main(){ Student students[NUMSTUDENTS]; // Array of studentsint iIndex; // Index number for(iIndex = 0; iIndex < NUMSTUDENTS; iIndex++)  {   cout << "Student #" << iIndex + 1 <<endl; cout << "First name: ";   cin.getline(students[iIndex].firstname, (NAMELENGTH)); cout << "Last name: ";   cin.getline(students[iIndex].lastname, NAMELENGTH);  cout << "Age: ";  cin >> students[iIndex].age;  cout << "Grade: ";  cin >> students[iIndex].grade;  }  for(iIndex = 0; iIndex < NUMSTUDENTS; iIndex++) {   cout << endl; cout << "Student #" << iIndex + 1 << endl;  cout << students[iIndex].firstname << " " << students[iIndex].lastname;  cout << " Age: " << students[iIndex].age;  cout << " Grade: " << students[iIndex].grade << endl;}system("PAUSE");return 0;}(linked list one)#include <iostream>using namespace std;const int NAMELENGTH = 20;struct Student{char firstname[NAMELENGTH];char lastname[NAMELENGTH];int age;int grade;Student* pNextStudent;};int main(){char cContinue;Student* pHeadStudent;Student* pStudent;Student* pPrevStudent = NULL;do{ pStudent = new Student; // Create new student if (pPrevStudent == NULL) // Is this the first student? pHeadStudent = pStudent; // Keep note of the first student else pPrevStudent->pNextStudent = pStudent; // Tell the last student where to find the new student // Get Student Information cout << "First name: ";  cin.getline(pStudent->firstname, NAMELENGTH); cout << "Last name: ";  cin.getline(pStudent->lastname, NAMELENGTH);  cout << "Age: ";  cin >> pStudent->age; cout << "Grade: ";  cin >> pStudent->grade;  pPrevStudent = pStudent; // This student becomes the last student cout << "Would you like to add another student? (Y/N): "; cin >> cContinue; cin.ignore(80, '\n');} while (cContinue == 'y' || cContinue == 'Y');pPrevStudent->pNextStudent = NULL;pStudent = pHeadStudent; // Start at the beginningdo // Print out student entries{ cout << endl; cout << pStudent->firstname << " " << pStudent->lastname << endl;  cout << " Age: " << pStudent->age << endl; cout << " Grade: " << pStudent->grade << endl;  pStudent = pStudent->pNextStudent;  // Get Next Student} while (pStudent != NULL);pStudent = pHeadStudent;do // Delete all student entries{ pPrevStudent = pStudent; // Remember address of current student pStudent = pStudent->pNextStudent; // Get next student address delete pPrevStudent; // Delete current student} while (pStudent != NULL);system("PAUSE");return 0; }I, however didn't get a chance to copy down the finished programs for each. I was wondering if anyone had the time, and if it isn't too much trouble, if you could draw up the programs for these exercises for me to examine. I still want to learn so I want to print them out to look over during vacation(despite whatever my dad says about programming I think its pretty fun). I know this is also a bit jerky but I'm leaving around mid-day tomorrow so if you could get it to me before then I would really appreciate it. I won't have access to a computer but at least I'll be able to print it out and look it over during vacation. It would serve me well till I get some money of my own to buy some books myself.This would seriously be a big help. I'm hoping that if I get good enough and start making and being able to understand some more complex programs that my dad may be okay with me taking a programming course or even majoring in computer science for college. Thank you very much in advance,electricmassEDIT: I just realized that maybe I should have posted this in the beginners section. I am really sorry if this is in the wrong place.   
  I'd hate to just spoil it for you by giving you the answers :) . It seems to me by reading your post that you aren't programming but trying to understand the code. I could be wrong but that's my impression.My first piece of advice is to download Microsoft's Visual C++ Express 2009. It's free. Then the fun (and long) part comes..... tinkering with code and seeing what happens.As for a book to buy.... I personally like books that cut out the fluff and get straight to it. There isn't much humor or other distracting material. It's all about C++. To be honest it's my favorite programming book because it takes you from beginner C to intermediate/adv C++ and gets into all the nitty-gritty nuances as you go along.http://www.amazon.com/Ivor-Hortons-Beginning-Complete-Compliant/dp/186100012X/ref=sr_1_2?ie=UTF8&s=books&qid=1244747359&sr=1-2It's $5 new + s/h.... I'm going to buy myself another copy lol since I lost my first one. That book will not leave your side (unless you lose it like me).Then it's time for data structures (linked list, queues, stacks, graphs, etc). I think the WROX book had some material on that as well. Definitely not as much as a book dedicated to data structures. You'll also want a book on algorithm fundamentals and computer architecture. I have no recommendations on any of those.... haven't really used any besides the ones that I got in college.Architecture may not seem important but it's good to know how things work "under the hood." You can tweak your code accordingly. A good operating systems book might be good too... perhaps better then an architecture book if you had to choose, as it deals with data structures and algortithms, memory management, etc. Things more directly applicable to programming.But to start buy the $5 book, download VC++ Express '09, surf the web for tutorials and have fun :)   ;  Thank you very much for the recommendation, Robione. I will definitely check out the book when I get back from vacation. I also may just try out learning from online tutorials after I get done learning these two.I know it kind of seems like I just want the code as opposed to actually programming but the way I was learning was basically by looking at the finished programs and first trying to understand how they work then I would go and try to program the same thing but on my own. It's made programming much easier for me to grasp. I got up to the structures and linked lists lessons in the book but now that I don't have the book I can't really follow along. So I was looking to see if anyone had the time to write up the exercises as that would really help me out. It's really been eating at me that I don't have anything to follow along with and I really want to try to understand and be able to program things as in these two lessons. I guess my learning plan for things is kind of weird but I really have been able to learn better with the source for each part of the lesson in the book in front of me. I hope you can indulge me. :)And thanks again, Robione. As I said, I will make sure to check that book out.   ;  I;m not touching the class/linked list example.... mainly because it's a lesson on two things and not one. But here is some code to get your started on the structure example.The only thing looking at this that I'm going to criticize myself for is that I define ACTION_xxxx constants and they are used for comparison but it's not clear from skimming the code where the cAction variable gets assigned these values. Secondly I use the old school c-style functions mainly. For some reason my scanf was pretty much ignored (and I entered an infinite loop) after the first iteration of the loop and as a "bandaid" I just used cin. It would be better to stick with one library or the other... but you get to see both this way :)#include <cstdio>#include <iostream>#include <memory.h>using namespace std;#define ACTION_MENU 0#define ACTION_ADD'a'#define ACTION_DISP'd'#define ACTION_QUIT'q'#define MAX_FRIENDS100#define SIZE_FNAME16#define SIZE_LNAME21#define SIZE_DATE11#define SIZE_TEL11//Assumes all your friends are in an area that uses the North American system.//Format is 1-xxx-xxx-xxxx. Omit 1 and -'s when entering value//Something to remember... a character string must end in 0. You must account for that when declaring the size.struct Friend {char szFname[SIZE_FNAME];char szLname[SIZE_LNAME];char szTel[SIZE_TEL];char szBDay[SIZE_DATE];Friend() {::memset(this,0,sizeof(*this));}//A struct in c++ is a class with all public members. This function I believe would cause a C compiler to fail.//All variables unless initialized have an "undefined" value. Unfortunately the "undefined" value is actually a//valid value. So to be safe I initialize all my variables when declared or w/i the first few lines.};void main(void) {char cAction = ACTION_MENU;//Menu ActionFriend vRolodex[MAX_FRIENDS];//Constructor defined in Friend zero's out the entire arrayint i = 0,//Array index    h = 0, l = 0, t = 0;//Range for displaying entries, t is tempdo {switch(cAction) {case ACTION_MENU:::printf("\n\n\t(A)dd a friend to your list.\n""\t(D)isplay entries between a range.\n""\t(Q)uit\n\nEnter your choice: ");cin >> cAction;break;case ACTION_ADD:if(i >= MAX_FRIENDS)::printf("\n\nSorry your Rolodex is full"); else {::printf("\n\nEnter your friend's first and last name: ");::scanf("%s %s",vRolodex.szFname,vRolodex.szLname);::printf("\nEnter your friend's telephone number: ");::scanf("%s",vRolodex.szTel);::printf("\nEnter your friend's birthday: ");::scanf("%s",vRolodex.szBDay);++i;}cAction = ACTION_MENU;break;case ACTION_DISP:::printf("\nEnter the first and last entry you would like the range to span: ");::scanf("%d %d",&l,&h);putc('\n',stdout);if(h<l) {t=l;l=h;h=t;}if(l<0) l = 0;if(h>i) h = i;for(;l<h;++l)::printf("%d: %s %s %s %s\n",l+1,vRolodex[l].szFname,vRolodex[l].szLname,vRolodex[l].szTel,vRolodex[l].szBDay);cAction = ACTION_MENU;}} while(cAction != ACTION_QUIT);};  Here you go... new and improved version with a few logic bugs fixed:#include <stdio.h>/**** Original Headers *****/#include <memory.h>#define ACTION_MENU 0#define ACTION_ADD'a'#define ACTION_DISP'd'#define ACTION_QUIT'q'#define MAX_FRIENDS100#define SIZE_FNAME16#define SIZE_LNAME21#define SIZE_DATE11#define SIZE_TEL11//Assumes all your friends are in an area that uses the North American system.//Format is 1-xxx-xxx-xxxx. 1 and -'s ommited when entering value//Something to remember... a character string must end in 0. You must account for that when declaring the size.struct Friend {char szFname[SIZE_FNAME];char szLname[SIZE_LNAME];char szTel[SIZE_TEL];char szBDay[SIZE_DATE];Friend() {::memset(this,0,sizeof(*this));}//A struct in c++ is a class with all public members. This function I believe would cause a C compiler to fail.//All variables unless initialized have an "undefined" value. Unfortunately the "undefined" value is actually a//valid value. So to be safe I initialize all my variables when declared or w/i the first few lines.};void main(void) {char cAction = ACTION_MENU;//Menu ActionFriend vRolodex[MAX_FRIENDS];//Constructor defined in Friend zero's out the entire arrayint i = 0,//Array index    h = 0, l = 0, t = 0;//Range for displaying entries, t is tempdo {switch(cAction) {case ACTION_MENU:::printf("\n\n\t(A)dd a friend to your list.\n""\t(D)isplay entries between a range.\n""\t(Q)uit\n\nEnter your choice: ");::fflush(stdin);/***** For whatever reason a linefeed character caused the infinite loop. Flushing the buffer fixes that *****/::scanf("%c",&cAction); /***** Original implemtation *****/break;case ACTION_ADD:if(i >= MAX_FRIENDS)::printf("\n\nSorry your Rolodex is full"); else {::printf("\n\nEnter your friend's first and last name: ");::scanf("%s %s",vRolodex.szFname,vRolodex.szLname);::printf("\nEnter your friend's telephone number: ");::scanf("%s",vRolodex.szTel);::printf("\nEnter your friend's birthday: ");::scanf("%s",vRolodex.szBDay);++i;}cAction = ACTION_MENU;break;case ACTION_DISP:::printf("\nEnter the first and last entry you would like the range to span(1-%d): ",i+1>MAX_FRIENDS?MAX_FRIENDS:i+1);/****** Shows user valid range *****/::scanf("%d %d",&l,&h);putc('\n',stdout);--h;--l;/****** Arrays are 0 indexed based ********/if(h<l) {t=l;l=h;h=t;}if(l<0) l = 0;if(h>i) h = i;for(;l<=h;++l)::printf("%d: %s %s %s %s\n",l+1,vRolodex[l].szFname,vRolodex[l].szLname,vRolodex[l].szTel,vRolodex[l].szBDay);cAction = ACTION_MENU;break;/****** Otherwise would run over into default case *****/default:cAction = ACTION_MENU;/***** In case the user enters something other than 'a', 'd', or 'q' *****/}} while(cAction != ACTION_QUIT);};  Thank you so much, Robione! I didn't get to look over the code yet as I'm getting ready to leave but I'm going to print it out so I can look through it. I think I'll be bringing my laptop so I may even get a chance to actually try to program based on this myself. Thank you very much, it is much appreciated.   ;Quote:Original post by RobioneHere you go... new and improved version with a few logic bugs fixed:*** Source Snippet Removed ***I'm no expert, but as far as I can tell, except for the scope operators and constructor, that's C, not C++. const variables are better than #defines (for what you're using them for), and C++ streams are better than C I/O functions, being typesafe, difficult to crash, and just generally really convenient. Why is cin a "band-aid" when it is clear it is the more stable solution?   ;  ......... What the hell is everyone in this thread doing to C++? Whatever reference the OP is reading from is evidently unbelievably out of date.In modern C++, the program would look something more like #include <iostream>#include <sstream>#include <string>#include <vector>#include <algorithm>const char ADD = 'a';const char DISPLAY = 'd';const char QUIT = 'q';class Friend {std::string first_name;std::string last_name;std::string phone_number;std::string birthday;public:Friend(const std::string& first_name, const std::string& last_name,const std::string& phone_number, const std::string& birthday):first_name(first_name), last_name(last_name),phone_number(phone_number), birthday(birthday) {}friend std::ostream& operator<<(std::ostream& os, const Friend& f) {return os << f.first_name << ' ' << f.last_name << ' ' << f.phone_number << ' ' << f.birthday;}};int main() {char action;std::string rest_of_line;std::vector<Friend> rolodex;do {std::cout << "\n\n\t(A)dd a friend to your list.\n"   "\t(D)isplay entries between a range.\n"   "\t(Q)uit\n\nEnter your choice: ";std::cin >> action;std::getline(std::cin, rest_of_line);switch (action) {case ADD: {std::cout << "\n\nEnter your friend's first and last name: ";std::string first_name, last_name;std::cin >> first_name >> last_name;std::getline(std::cin, rest_of_line);std::cout << "\nEnter your friend's telephone number: ";std::string phone_number;std::getline(std::cin, phone_number);std::cout << "\nEnter your friend's birthday: ";std::string birthday;std::getline(std::cin, birthday);rolodex.push_back(Friend(first_name, last_name, phone_number, birthday));}break;case DISPLAY:size_t first, last;while (true) {std::cout << "\nEnter the first and last entry you would like the range to span (1-" << rolodex.size() << "): ";std::string line;std::getline(std::cin, line);std::stringstream parser(line);if (parser >> first >> last) { break; }}std::cout << '\n';size_t end = std::min(last, rolodex.size());for (size_t i = std::max(first, size_t(1)) - 1; i < end; ++i) {std::cout << (i + 1) << ": " << rolodex;}break;}} while (action != QUIT);}and would not have any of the arbitrary limits mentioned on array sizes or string lengths.   ;Quote:Original post by theOcelotI'm no expert, but as far as I can tell, except for the scope operators and constructor, that's C, not C++. const variables are better than #defines (for what you're using them for), and C++ streams are better than C I/O functions, being typesafe, difficult to crash, and just generally really convenient. Why is cin a "band-aid" when it is clear it is the more stable solution?I'm mainly a hobbyist as far as programming goes. I just never really got into using streams and I know everything you say about them is true. The things I took with me from C++ was pretty much everything regarding classes. I don't do much console programming, plus it's a habit for me to start new people off with printf/scanf from my TA days.  Forces people to be thinking of data types. Other then that I was just trying to stick with the style of the book he was using. IMHO it's easier for a new person to digest something they've been exposed to already. I only say cin was a band-aid in my first program because it is "out of theme" with the rest of the code and inserted just to get it to work in a jiffy. If anything it shows how it's easier to deal with streams :)Ocelot I have a question. 'Cause I live in my own little "coding world" as a hobbyist your statement about the const vs #define has me asking why? Cause I really don't know. The thinking for me is that you don't take up x-number of bytes in memory for values that you already know won't change. The only con I see is if your code starts spanning hundreds of files and you forget which file the define is in that you need to change..... but I use the "Find in Files..." for that. Having a const essentially flips the pros and cons... easy to find (i.e. in VC++ class browser) but takes up space.... also depending on how big the program is and the spatial locality of the data you're accessing couldn't it result in potential cache misses?==================================================Well I was eager to find out the answer to my question and see how VC++ 6 handles it so I made two globals a constant (g_ci) and plain ol' int (g_i) and see that the compiler uses the value as an immediate. Isn't possible though that the compiler might not use it as an immediate value?51:   int i = 5;00402338   mov    dword ptr [ebp-14h],552:   i = g_ci;0040233F   mov    dword ptr [ebp-14h],0Ah53:   i = g_i;00402346   mov    eax,[g_i (0041b714)]0040234B   mov    dword ptr [ebp-14h],eax==================================================Yes, Zahlman's program is the modern C++ but if the student is brand new why expose them to vectors and strings (and classes) right off the bat? I'm not sure what aspects of the language the original poster has a grasp on but based on the first program it seems like s/he is relatively new (which is why I didn't get into pointers or classes for the second program). On the other hand the OP now has a taste of what their code could look like in the future :)[Edited by - Robione on June 20, 2009 1:30:52 AM];Quote:Original post by RobioneOcelot I have a question. 'Cause I live in my own little "coding world" as a hobbyist your statement about the const vs #define has me asking why? Cause I really don't know. The thinking for me is that you don't take up x-number of bytes in memory for values that you already know won't change. The only con I see is if your code starts spanning hundreds of files and you forget which file the define is in that you need to change..... but I use the "Find in Files..." for that. Having a const essentially flips the pros and cons... easy to find (i.e. in VC++ class browser) but takes up space.... also depending on how big the program is and the spatial locality of the data you're accessing couldn't it result in potential cache misses?Const variables cooperate with C++'s scoping and type system. More details. Read 29.8, too.Regarding code efficiency, const variables will often be inlined like #defines. The compiler will probably do a good job of deciding when this is a good idea.   