//NOTE: FEEL FREE TO USE AND/OR DISTRIBUTE THIS CODE AS YOU LIKE
//THIS IS NOT COPYRIGHTED MATERIAL
#include
#include
using namespace std;
struct Node
{
string name;
Node * next;
};
struct List
{
Node * front;
Node * back;
};
void displayList(List L)
//PURPOSE: display contents of list
//PRECONDITIONS: L must be a valid list
//POSTCONDITIONS: list L display on screen
{
Node * n;
// traverse list and display contents
cout << "Beginning of List" << endl;
n = L.front;
while (n != NULL) {
cout << "\t" << n->name << endl;
n = n->next;
}
cout << "End of List" << endl << endl;
}
Node * searchList(List L, string str)
//PURPOSE: search list L for place to insert str
//PRECONDITIONS: L must be a valid list
//POSTCONDITIONS: returns pointer to previous node of first
// node with value >= str
{
Node * n;
Node * prev;
// traverse list to find node that contains str
n = L.front;
prev = NULL;
while (n != NULL) {
if (n->name >= str) {
return prev;
}
prev = n;
n = n->next;
}
// goes at end of list
return prev;
}
void insert(List &L, Node * n)
//PURPOSE: insert new node in a list
// keepping list ordered
//PRECONDITIONS: L must be a valid list
//POSTCONDITIONS: List L has new node inserted
{
Node * after; // insert new node after this node
// find where to insert node
after = searchList(L, n->name);
// handle NULL list
if (L.front == NULL) {
L.front = n;
L.back = n;
n->next = NULL;
}
// handle insert at front of list
else if (after == NULL) {
n->next = L.front;
L.front = n;
}
// handle insert in middle or end of list
else {
n->next = after->next;
after->next = n;
if (n->next == NULL) {
L.back = n;
}
}
}
void deleteNode(List &L, Node * n)
{
Node * del;
if(n==NULL){
del=L.front;
L.front=del->next;
n = L.front;
if(n->next==NULL){
L.back=n;
}
delete del;
}
else{
del=n->next;
n->next = del->next;
if(n->next==NULL){
L.back=n;
}
delete del;
}
}
int main()
//PURPOSE: create a list of words in alphabetical order
//PRECONDITIONS: none
//POSTCONDITIONS: displays list of words in alphabetical order
{
string s; // word from user
List L; // list of words
Node * n; // list node
//initialize list L
L.front = NULL;
L.back = NULL;
// prompt user for words and insert them into list
// in alphabetical order
cout << "Enter next word (! to stop): ";
cin >> s;
while (s != "!") {
n = new Node;
n->name = s;
insert(L, n);
cout << "Enter next word (! to stop): ";
cin >> s;
}
// display words in alphabetical order
displayList(L);
// prompt user for words to delete from the list
cout << "Enter word to delete (! to stop): ";
cin >> s;
while(s != "!") {
n = searchList(L, s);
deleteNode(L, n);
cout << "Enter word to delete (! to stop): ";
cin >> s;
}
// display list with words deleted
displayList(L);
return 0;
}