orderedInsert help for alphabetizing entries.

J

jawdoc

I am working on alphabetizing entries in my linked list and am very
confused on how to do this. What I'm trying to do is to go through the
list and order them accordingly. The struct consists of last name,
first name, and some other stuff. I will provide the full code that is
working but will only add to the top of the list but won't alphabetize
it.

The full code is here:

/
*-----------------------------------------------------------------------
airplane.cpp
----------------
Programmer : Terry Sergeant
Last Modi : 29 Jan 2001
Course : CSCI 1063 -- Programming II
Description: Airline reservations program ... I will given them
parts of this and they will have to finish it.
Refer to the menu (or the writeup) for information
about what exactly this program is supposed to do.

-----------------------------------------------------------------------
*/
#include<iostream>
#include<string>
#include<cctype>

using namespace std;

struct SEAT {
//bool occupied; // initially, false
string first,last; // passenger name
int numBags; // max of 4
char mealType; // (r)egular, (v)egetaria, (o)ther
int row;
char col;
SEAT *next;
};

const int ROWS= 30;
const int COLS= 6;

int menuchoice();
void clearPlane(SEAT &p, bool o[][COLS]);
void showPlane(SEAT &p, bool o[][COLS]);
bool getSeat(SEAT &p, int &row, int &col, bool o[][COLS]);
void getSeatFromUser(SEAT &p, int &row, int &col, bool o[][COLS]);
void getInfo(SEAT *&s, int, int);
void showInfo(SEAT *s/*, int, int*/);
void makeReservation(SEAT &p, bool o[][COLS], SEAT *&head);
void cancelReservation(SEAT &p, bool o[][COLS]);
void viewReservations(SEAT &p, bool o[][COLS], SEAT *&head);

int main()
{
int choice; // user's menu choice
SEAT plane; // reservation info for entire plane
bool occupied[ROWS][COLS];
SEAT *head;
clearPlane(plane, occupied);
showPlane(plane, occupied);
do
{
cin.clear();
choice= menuchoice();
cin.ignore();
switch (choice) {
case 1: makeReservation(plane, occupied, head); break;
case 2: cancelReservation(plane, occupied); break;
case 3: viewReservations(plane, occupied, head); break;
case 4: break;
}
}while(choice !=4);



return 0;
}



/* menuchoice
**-----------------
** displays menu and get's user's choice
**--------------------------------------------------------------------
*/
int menuchoice()
{
int choice;

cout << endl << endl;
cout << "+------------------------+\n";
cout << "| Main Menu |\n";
cout << "+------------------------+\n";
cout << "| [1] Reserve a Seat |\n";
cout << "| [2] Cancel Reservation |\n";
cout << "| [3] List Reservations |\n";
cout << "| [4] Exit Program |\n";
cout << "+------------------------+\n";
do {
cout << "Choice: ";
cin >> choice;
if(!cin)
cin.clear();

} while (choice < 1 || choice > 4);

return choice;
}


/* showPlane
**-----------------
** displays grid showing open/taken seats
**--------------------------------------------------------------------
*/
void showPlane(SEAT &p, bool o[][COLS])
{
int i,j;
cout << " 1 2
3\n";
cout << " 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0\n";
for (j=0; j<COLS; j++) {
cout << (char) (j+65);
for (i=0; i<ROWS; i++)
if (o[j])
cout << " x";
else
cout << " ";
cout << endl;
}
}


/* clearPlane
**-----------------
** empties all reservations in airplane
**--------------------------------------------------------------------
*/
void clearPlane(SEAT &p, bool o[][COLS])
{
int i,j;
for (i=0; i<ROWS; i++)
for (j=0; j<COLS; j++)
o[j]= false;
}


/* getSeat
**-----------------
** obtains desired row and column number for a seat; the seat can be
** selected by the user or can be selected automatically by the
** computer; the function return true if an open seat was found;
** false otherwise.
**--------------------------------------------------------------------
*/
bool getSeat(SEAT &p, int &row, int &col,bool o[][COLS])
{
bool allTaken; // true if all seats on plane are occupied
char method; // (a)utomatic or (m)anual seat selection

allTaken= true; // make sure at least
one
for (row=0; row<ROWS && allTaken; row++) // seat is available
for (col=0; col<COLS && allTaken; col++)
if (!o[row][col])
allTaken= false;
if (allTaken) return false; // if not return false

do {
cout << "Would you like to select a seat (a)utomatically or
(m)anually: ";
cin >> method;
} while (tolower(method)!='a' && tolower(method)!='m');

switch (tolower(method)) {
case 'a': for (row=0; row<ROWS; row++) // (a)utomatic seat
selection
for (col=0; col<COLS; col++)
if (!o[row][col])
return true;
break; // this break is redundant, we hope
case 'm': getSeatFromUser(p,row,col,o); // (m)anual seat
selection
return !o[row][col];
}

return false; // we should never get here
}


/* getSeatFromUser
**-----------------
** obtains desired row and column number for a seat; this function
** will be called from getSeat when requesting a seat for making
** reservations and will be called directly when selecting a
** seat for cancellation.
**--------------------------------------------------------------------
*/

void getSeatFromUser(SEAT &p, int &row, int &col, bool o[][COLS])
{
char let;

showPlane(p,o);
do {
cout << "Enter row (1.." << ROWS << "): ";
cin >> row;

} while (row < 1 || row > ROWS);

do {
cout << "Enter col (A.." << (char) (COLS+64) << "): ";
cin >> let;
let= toupper(let);

} while (let < 'A' || let > (COLS+64));

col= let-65;
row--;

}

/* getInfo
* --------------------------------------------------------
* Accepts the SEAT struct then the user enters in their
* information.
* ------------------------------------------------------*/
void getInfo(SEAT *&s, int row, int col, bool o[][COLS])
{
s=new SEAT;
s->row= row;
s->col= col;
cin.ignore(100,'\n');
string answer;
do{


cout<<"\nEnter in this information:\n\n";

cout<<"Enter your first name: ";

cin>>s->first;
cout<<"\n";

cout<<"Enter your last name: ";

cin>>s->last;
cout<<"\n";

cout<<"\n";
do{
cin.clear();
cout<<"How many bags will you be bringing?(limit of 4) ";
cin>>s->numBags;
cout<<"\n";
}while(s->numBags<0||s->numBags>4);

do{

cin.clear();
cout<<"What type of meal would you like?((r)egular, (v)egatarian,
or (o)ther) ";
cin>>s->mealType;
s->mealType=tolower(s->mealType);
cout<<"\n";

}while(s->mealType!='r' && s->mealType!='v' && s->mealType!= 'o');


showInfo(s/*, row, col*/);
getline(cin,answer);
do{
cout<<"Is this information correct?(yes,no)";
getline(cin,answer);
cout<<"\n";
}while(answer!="yes" && answer!="y" && answer!="no");

cin.clear();
//s->next=NULL;
}while(answer=="no");
}

/*--------------------------------------------------------
* Displays the information they just entered.
* ------------------------------------------------------*/

void showInfo(SEAT *s /*int row, int col*/)
{
string regular="Regular";
string vegetarian="Vegetarian";
string other="Other";

cout<<"\nSeat: "<<(s->row+1)<<", "<<(char)(s->col+65)<<"\n";
cout<<"Name: "<<s->first<<" "<<s->last<<"\n";
cout<<"Number of bags: " <<s->numBags<<"\n";

if(s->mealType=='r')
cout<<"Meal Type: "<<regular<<"\n\n";
if(s->mealType=='v')
cout<<"Meal Type: "<<vegetarian<<"\n\n";
if(s->mealType=='o')
cout<<"Meal Type: "<<other<<"\n\n";
}

/*--------------------------------------------------------
* Calls showPlane and then will ask what seat they want
* and will call getInfo
* ------------------------------------------------------*/

void makeReservation(SEAT &p, bool o[][COLS], SEAT *&head)
{
int row;
int col;

SEAT *temp;

do{
cout<<"\n";
getSeat(p,row, col, o);
if(o[row][col]==true)
cout<<"\nSeat is already taken.\n";
}while(o[row][col]==true);

o[row][col]=true;

getInfo(temp,row,col,o);

if( (tolower(temp->last[1]) > (tolower(head->last[1])) /* || head-
next==NULL)*/))
Click to expand...
{
temp->next=head;
head=temp;
};
// else
// head->next=temp;
}

/*--------------------------------------------------------
* User enters in a seat row and column and if it is empty
* it will display that. If it is occupied then it will
* make the array empty.
* ------------------------------------------------------*/

void cancelReservation(SEAT &p, bool o[][COLS])
{
int row;
int col;
getSeatFromUser(p, row, col, o);
if(o[row][col]==false)
cout<<"\nThe reservation is empty.";
else
o[row][col]=false;

}

/*--------------------------------------------------------
* For loop that will go through each seat and if it is
* occupied it will display the SEAT struct for that one
* then move on.
* ------------------------------------------------------*/

void viewReservations(SEAT &p, bool o[][COLS], SEAT *&head)
{
SEAT *view;
view=head;
int i;
int n;
while(view->next!=NULL)
{
showInfo(view/*, i, n*/);
view=view->next;
}

}
 
A

alasham.said

I am working on alphabetizing entries in my linked list and am very
confused on how to do this. What I'm trying to do is to go through the
list and order them accordingly. The struct consists of last name,
first name, and some other stuff. I will provide the full code that is
working but will only add to the top of the list but won't alphabetize
it.

The full code is here:

/
*-----------------------------------------------------------------------
airplane.cpp
----------------
Programmer : Terry Sergeant
Last Modi : 29 Jan 2001
Course : CSCI 1063 -- Programming II
Description: Airline reservations program ... I will given them
parts of this and they will have to finish it.
Refer to the menu (or the writeup) for information
about what exactly this program is supposed to do.

-----------------------------------------------------------------------
*/
#include<iostream>
#include<string>
#include<cctype>

using namespace std;

struct SEAT {
//bool occupied; // initially, false
string first,last; // passenger name
int numBags; // max of 4
char mealType; // (r)egular, (v)egetaria, (o)ther
int row;
char col;
SEAT *next;

};

const int ROWS= 30;
const int COLS= 6;

int menuchoice();
void clearPlane(SEAT &p, bool o[][COLS]);
void showPlane(SEAT &p, bool o[][COLS]);
bool getSeat(SEAT &p, int &row, int &col, bool o[][COLS]);
void getSeatFromUser(SEAT &p, int &row, int &col, bool o[][COLS]);
void getInfo(SEAT *&s, int, int);
void showInfo(SEAT *s/*, int, int*/);
void makeReservation(SEAT &p, bool o[][COLS], SEAT *&head);
void cancelReservation(SEAT &p, bool o[][COLS]);
void viewReservations(SEAT &p, bool o[][COLS], SEAT *&head);

int main()
{
int choice; // user's menu choice
SEAT plane; // reservation info for entire plane
bool occupied[ROWS][COLS];
SEAT *head;
clearPlane(plane, occupied);
showPlane(plane, occupied);
do
{
cin.clear();
choice= menuchoice();
cin.ignore();
switch (choice) {
case 1: makeReservation(plane, occupied, head); break;
case 2: cancelReservation(plane, occupied); break;
case 3: viewReservations(plane, occupied, head); break;
case 4: break;
}
}while(choice !=4);

return 0;

}

/* menuchoice
**-----------------
** displays menu and get's user's choice
**--------------------------------------------------------------------
*/
int menuchoice()
{
int choice;

cout << endl << endl;
cout << "+------------------------+\n";
cout << "| Main Menu |\n";
cout << "+------------------------+\n";
cout << "| [1] Reserve a Seat |\n";
cout << "| [2] Cancel Reservation |\n";
cout << "| [3] List Reservations |\n";
cout << "| [4] Exit Program |\n";
cout << "+------------------------+\n";
do {
cout << "Choice: ";
cin >> choice;
if(!cin)
cin.clear();

} while (choice < 1 || choice > 4);

return choice;

}

/* showPlane
**-----------------
** displays grid showing open/taken seats
**--------------------------------------------------------------------
*/
void showPlane(SEAT &p, bool o[][COLS])
{
int i,j;
cout << " 1 2
3\n";
cout << " 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0\n";
for (j=0; j<COLS; j++) {
cout << (char) (j+65);
for (i=0; i<ROWS; i++)
if (o[j])
cout << " x";
else
cout << " ";
cout << endl;
}

}

/* clearPlane
**-----------------
** empties all reservations in airplane
**--------------------------------------------------------------------
*/
void clearPlane(SEAT &p, bool o[][COLS])
{
int i,j;
for (i=0; i<ROWS; i++)
for (j=0; j<COLS; j++)
o[j]= false;

}

/* getSeat
**-----------------
** obtains desired row and column number for a seat; the seat can be
** selected by the user or can be selected automatically by the
** computer; the function return true if an open seat was found;
** false otherwise.
**--------------------------------------------------------------------
*/
bool getSeat(SEAT &p, int &row, int &col,bool o[][COLS])
{
bool allTaken; // true if all seats on plane are occupied
char method; // (a)utomatic or (m)anual seat selection

allTaken= true; // make sure at least
one
for (row=0; row<ROWS && allTaken; row++) // seat is available
for (col=0; col<COLS && allTaken; col++)
if (!o[row][col])
allTaken= false;
if (allTaken) return false; // if not return false

do {
cout << "Would you like to select a seat (a)utomatically or
(m)anually: ";
cin >> method;
} while (tolower(method)!='a' && tolower(method)!='m');

switch (tolower(method)) {
case 'a': for (row=0; row<ROWS; row++) // (a)utomatic seat
selection
for (col=0; col<COLS; col++)
if (!o[row][col])
return true;
break; // this break is redundant, we hope
case 'm': getSeatFromUser(p,row,col,o); // (m)anual seat
selection
return !o[row][col];
}

return false; // we should never get here

}

/* getSeatFromUser
**-----------------
** obtains desired row and column number for a seat; this function
** will be called from getSeat when requesting a seat for making
** reservations and will be called directly when selecting a
** seat for cancellation.
**--------------------------------------------------------------------
*/

void getSeatFromUser(SEAT &p, int &row, int &col, bool o[][COLS])
{
char let;

showPlane(p,o);
do {
cout << "Enter row (1.." << ROWS << "): ";
cin >> row;

} while (row < 1 || row > ROWS);

do {
cout << "Enter col (A.." << (char) (COLS+64) << "): ";
cin >> let;
let= toupper(let);

} while (let < 'A' || let > (COLS+64));

col= let-65;
row--;

}

/* getInfo
* --------------------------------------------------------
* Accepts the SEAT struct then the user enters in their
* information.
* ------------------------------------------------------*/
void getInfo(SEAT *&s, int row, int col, bool o[][COLS])
{
s=new SEAT;
s->row= row;
s->col= col;
cin.ignore(100,'\n');
string answer;
do{

cout<<"\nEnter in this information:\n\n";

cout<<"Enter your first name: ";

cin>>s->first;
cout<<"\n";

cout<<"Enter your last name: ";

cin>>s->last;
cout<<"\n";

cout<<"\n";
do{
cin.clear();
cout<<"How many bags will you be bringing?(limit of 4) ";
cin>>s->numBags;
cout<<"\n";
}while(s->numBags<0||s->numBags>4);

do{

cin.clear();
cout<<"What type of meal would you like?((r)egular, (v)egatarian,
or (o)ther) ";
cin>>s->mealType;
s->mealType=tolower(s->mealType);
cout<<"\n";

}while(s->mealType!='r' && s->mealType!='v' && s->mealType!= 'o');

showInfo(s/*, row, col*/);
getline(cin,answer);
do{
cout<<"Is this information correct?(yes,no)";
getline(cin,answer);
cout<<"\n";
}while(answer!="yes" && answer!="y" && answer!="no");

cin.clear();
//s->next=NULL;
}while(answer=="no");

}

/*--------------------------------------------------------
* Displays the information they just entered.
* ------------------------------------------------------*/

void showInfo(SEAT *s /*int row, int col*/)
{
string regular="Regular";
string vegetarian="Vegetarian";
string other="Other";

cout<<"\nSeat: "<<(s->row+1)<<", "<<(char)(s->col+65)<<"\n";
cout<<"Name: "<<s->first<<" "<<s->last<<"\n";
cout<<"Number of bags: " <<s->numBags<<"\n";

if(s->mealType=='r')
cout<<"Meal Type: "<<regular<<"\n\n";
if(s->mealType=='v')
cout<<"Meal Type: "<<vegetarian<<"\n\n";
if(s->mealType=='o')
cout<<"Meal Type: "<<other<<"\n\n";

}

/*--------------------------------------------------------
* Calls showPlane and then will ask what seat they want
* and will call getInfo
* ------------------------------------------------------*/

void makeReservation(SEAT &p, bool o[][COLS], SEAT *&head)
{
int row;
int col;

SEAT *temp;

do{
cout<<"\n";
getSeat(p,row, col, o);
if(o[row][col]==true)
cout<<"\nSeat is already taken.\n";
}while(o[row][col]==true);

o[row][col]=true;

getInfo(temp,row,col,o);

if( (tolower(temp->last[1]) > (tolower(head->last[1])) /* || head->next==NULL)*/))

{
temp->next=head;
head=temp;
};
// else
// head->next=temp;

}

/*--------------------------------------------------------
* User enters in a seat row and column and if it is empty
* it will display that. If it is occupied then it will
* make the array empty.
* ------------------------------------------------------*/

void cancelReservation(SEAT &p, bool o[][COLS])
{
int row;
int col;
getSeatFromUser(p, row, col, o);
if(o[row][col]==false)
cout<<"\nThe reservation is empty.";
else
o[row][col]=false;

}

/*--------------------------------------------------------
* For loop that will go through each seat and if it is
* occupied it will display the SEAT struct for that one
* then move on.
* ------------------------------------------------------*/

void viewReservations(SEAT &p, bool o[][COLS], SEAT *&head)
{
SEAT *view;
view=head;
int i;
int n;
while(view->next!=NULL)
{
showInfo(view/*, i, n*/);
view=view->next;
}

}
Click to expand...


You probably need something like so (barring mistakes):

void makeReservation( SEAT &p, bool o[][COLS], SEAT *head )
{

/* ... */

SEAT* temp;

for( temp = head; temp->next != 0 && ( temp->next->first <
p.first ); temp = temp->next )
;

SEAT* swp = temp->next;
temp->next = &p;
p.next = swp;
}

However, I strongly recommend that you should consider using standard
library structures, like std::list.

Regards.
 
J

jawdoc

Thank you that helped me a lot. Now I have my linked lists working and
cancelling well. The only problem is my algorithm for my orderedInsert
is not very good. I have two that I have tried and both seem to bring
errors or leave something wrong behind. If you could look at these and
give me some suggestions towards making these work I would greatly
appretiate it.


Alg #1:

int row;
int col;

SEAT *temp;
SEAT *j, *q, *newSEAT;

do{
cout<<"\n";
getSeat(p,row, col, o);
if(o[row][col]==true)
cout<<"\nSeat is already taken.\n";
}while(o[row][col]==true);

o[row][col]=true;

getInfo(temp,row,col,o);

(head==NULL || temp->last[0] <= head->last[0])
{
newSEAT->next=head;
head=newSEAT;
}

else{
j=head;
while(j !=NULL && j->last[0] < temp->last[0])
{
q=j;
j=j->next;
}
newSEAT->next =j;
q->next=newSEAT;
}


Alg #2:

int row;
int col;

SEAT *temp;
SEAT *j, *q, *newSEAT;

do{
cout<<"\n";
getSeat(p,row, col, o);
if(o[row][col]==true)
cout<<"\nSeat is already taken.\n";
}while(o[row][col]==true);

o[row][col]=true;

getInfo(temp,row,col,o);

for(temp = head; temp->next !=0 && temp->next->last[0] < head-
last[1]; temp = temp->next)
Click to expand...
{
SEAT *swp= temp->next;
temp->next = head;
head->next = swp;
}

I am trying to alphabetize it phonebook style and it will go through
the lists till it reaches null and alphabetizes the names.

thanks
jawdoc
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Alphabetizing Linked List data 1
I Need Fix In Code 1
I need help 1
Lexical Analysis on C++ 1
Need help in debugging tic tac toe (Beginner) 0
Need help in debugging tic tac toe (beginner) 2
help 17
Why is this WordPress comments form not submitting? 1

Members online

Total: 61 (members: 4, guests: 57)
Robots: 429

Forum statistics

Threads
473,982
Messages
2,570,185
Members
46,736
Latest member
AdolphBig6

Latest Threads

Top