Inserting new nodes in a sorted double linked list
EDIT: Solved the problem with my code. It works, but I would like to optimize it a little and insure that it conforms to the instructions given (my professor nitpicks!).
Use a double Linked List. Prompt the user for a file with one integer per line. The file will not be sorted.
You should then sort the file.
Next, prompt the user to add integers to the list. When the user finishes, you should ask for an output file, and then write the sorted list, one integer per line.
Anyway, here is my code:
Code:
#include <iostream>
#include <fstream>
using namespace std;
struct node
{
int key;
node* next; node* last;
};
typedef node* node_ptr;
void addNode(node_ptr &list, int x, node_ptr &head)
{
if (!list)
{
list = new node;
list->key = x;
list->next = NULL;
list->last = NULL;
head = list;
}
else
{
if(list->next == NULL)
{
node_ptr tmp = new node;
tmp->key = x;
tmp->last = list;
tmp->next = NULL;
list->next = tmp;
list = list->next;
}
else
{
list = list->next;
addNode(list, x, head);
}
}
}
void print_list(node_ptr& list, ofstream& write)
{
while(list)
{
write << list->key << endl;
list = list->next;
}
}
void insertion_sort(node_ptr &list)
{
int temp = 0;
node_ptr tmp = list;
for (tmp = tmp->next; tmp; tmp = tmp->next)
{
list = tmp;
while(list->last->key > list->key)
{
temp = list->last->key;
list->last->key = list->key;
list->key = temp;
if (!list->last->last) break;
list = list->last;
}
}
}
int main()
{
node_ptr p = NULL, head = NULL;
char inFileName[16], outFileName[16];
int num_nodes = 0, v = 0;
ifstream read; ofstream write;
/****** Ask user for input file *****/
cout << "Enter file name to be read: ";
cin >> inFileName;
/***** open file **********/
read.open(inFileName);
if (read.fail())
{
cout << "Input file opening failed!"<<endl;
//exit(1);
}
/* read digits in from file to linked list */
for (int i = 0; read >> v; i++)
{
addNode(p, v, head);
}
p = head;
insertion_sort(p); // sort the list
/* ask user for input to enter into the linked list */
cout << "How many numbers do you wish to add: ";
cin >> num_nodes;
for (int i = 0; i < num_nodes; i++)
{
cout << "enter a number: ";
cin >> v;
addNode(p, v, head);
}
p = head;
insertion_sort(p); // sort the list
cout << "Enter a file name to write the sorted list to: ";
cin >> outFileName;
write.open(outFileName);
if (write.fail())
{
cout << "Disk Error!" << endl;
}
p = head;
print_list(p, write);
return 0;
}
