linked list sorting...

[GSXdan]

for the books linked list i need to sort the books as they are read in, and so far it isnt working too well. this is what i have now:


void library::add(char * t, long i, char ty) { //add function
Book * temp; //Declaration for temporary pointer to Book
temp = ptFirstAll;
ptFirstAll = new Book(t, i, ty); //creation of new instance of Book
//with address stored in ptFirstAll

// if the list is empty, this will add it as the first book
if(temp==0) {
temp = ptFirstAll;
return;
}


// this will check if it should be the first book, and
// if so, puts it first
if(strcmp(ptFirstAll->title, temp->title) < 0) {
temp->ptAll = ptFirstAll;
temp = ptFirstAll;
return;
}


// this checks to see where in the middle the book
// should be placed and places it accordingly
while(temp->ptAll!=0) {
cout << "Enter while loop" << endl;
if(strcmp((temp->ptAll)->title, ptFirstAll->title) > 0) {
ptFirstAll->ptAll = temp->ptAll;
temp->ptAll = ptFirstAll;
return;
}
temp = temp->ptAll;
}



it will input the first book when the list is empty, but for some reason it is going into the first book loop everytime, so it never gets past that. I know it has to do with the if condition, but the way it seems, it should be as follows(psuedocode):
if new title < first title(using strcmp)
set it as first title


what am i doing wrong?

TIA

[doctorgonzo]

You have temp and ptFirstAll backwards.

For example, you should assign the pointer of the newly-created Book to temp, not ptFirstAll, because you don't know if the new Book should be first. If ptFirstAll is null, then you assign ptFirstAll the value of temp, not the other way around.

Adding the first Book works right now because ptFirstAll will always point to the Book you create. Once ptFirstAll isn't null, however, the mistakes prevent it from working.

[GSXdan]

cool, got that part working :)

Book * temp; //Declaration for temporary pointer to Book
temp = ptFirstAll;
temp = new Book(t, i, ty); //creation of new instance of Book
//with address stored in ptFirstAll

// if the list is empty, this will add it as the first book
if(ptFirstAll==0){
ptFirstAll = temp;
return;
}




does the order of the conditions matter? ie, check if it goes first, middle, last? i think that is what is messing me up, dealing with all the conditions. assuming check first should go first, here is the code i have:


// this will check if it should be the first book, and
// if so, puts it first
if(strcmp(temp->title, ptFirstAll->title) < 0) {
temp->ptAll = ptFirstAll;
temp = ptFirstAll;
return;
}


psuedocode:
if new book is less than first book
place it there

but i guess it wouldnt need that code assuming this book list:
AbriefHistoryofTime 12345 S
HuckleberryFinn 38476 F
BigRed 98723 C
BigTree 23234 C
TheAtom 87351 S
TomSawyer 42631 F
HowToProgram 99972 S
AlicInWonderland 11192 C
AsimovsMysteries 66621 O
OldYeller 24351 C
Physics 77362 S
EinsteinSimplified 88362 O
WindInTheWillows 83741 C
ToraToraTora 73731 O
HandHandFingersThumb 10923 C
GoneWithTheWind 82813 F
Garfield 93841 C
TheClient 84721 F
Science 66333 S

since ABrief.. is the smallest string.
--------------------------------------------------------------------------------

[GSXdan]

last would have to come next wouldnt it? now with there only being one book in the list, the middle code has nothing to compare if something is bigger than it, so the check last code would have to next(i think). does that sound right?



** im just throwing out ideas to see if i can correct myself, seeing it written out helps me see errors, just incase you were wondering why i appear to be writing everything i think**

[GSXdan]

am i going to need another temp variable to traverse the list? if ptFirstAll is first, cant change
temp is the new book
i would need another variable to traverse the list right? or is there a way to do it w/o another variable?

[GSXdan]

so something like:
Book * tptr;
.
.
.


while(tptr->ptAll!=0) {
if(strcmp(temp->title, tptr->title) > 0)
tptr->ptAll = temp;
tptr=tptr->ptAll;
}



edit: is not doing anything...

[GSXdan]

bah, university server crashed. this could be really good(not turn in project till monday), or really bad(it goes back up late tonight, still need to turn it in tomorrow).

i was just starting to get somewhere too....

[doctorgonzo]

You shouldn't need separate tests. But you will probably need another variable (can't think now so can't do actual code).

Just traverse the list and stick the new book before the book that should be ahead. Say that you have books A,B,C, and T. Want to add book R. Go through the list and test. Once you get to T, since R is before T, you want C to point to R and R to point to T. If you get to the end of the list, stick it on the end. If the new book should be before the first book on the list, have ptFirstAll point to the new book, and the new book should point to the old first book.

You can do that all in one loop.

[GSXdan]

while(tptr!=0) {

// check if book should go first
if(strcmp(temp->title, ptFirstAll->title) < 0) {
temp->ptAll = ptFirstAll -> ptAll;
ptFirstAll = temp;
return;
// this checks if it should go somewhere in the middle
}else if(strcmp((tptr->ptAll)->title, temp->title) > 0) {
temp->ptAll = tptr->ptAll;
tptr->ptAll = temp;
return;
// this checks if it should go last
}else if(tptr->ptAll==0) {
tptr->ptAll = temp;
return;
}

tptr=tptr->ptAll;

}


i am getting a seg. fault, see anything wrong?

thanks

[GSXdan]

if i change while(tptr!=0) { to while(tptr->ptAll!=0) it doesnt give me the segmentation fault, but it never enters the while loop.

[GSXdan]

just had it in the wrong order. the check to see if it went last had to come first, otherwise there werent enough objects to check and it created a segmentation fault.


while(tptr->title!=NULL) {
// check if book should go first

if(tptr->ptAll==0) {
tptr->ptAll = temp;
return;

}else if(strcmp(temp->title, ptFirstAll->title) < 0) {
temp->ptAll = ptFirstAll -> ptAll;
ptFirstAll = temp;
return;
// this checks if it should go somewhere in the middle
}else if(strcmp((tptr->ptAll)->title, temp->title) > 0) {
temp->ptAll = tptr->ptAll;
tptr->ptAll = temp;
return;
// this checks if it should go last
}
tptr=tptr->ptAll;

}


}


now im about 30% done :(