I want to know more about singly linked lists, so I decided to write a program: it would read some integers from a file, store them in linked list (*root) and sort them (and store sorted list in *sorted). This program is working, but I think it's not very readable and also I have found some problems:
In while loop (!fin.eof()) equals 1, when the input file is emty. It equals 0 only after reading from empty file, so my program creates one more node than is required, and I have to destroy it (using variable badnode and code around it..)
How I can read data (and store them in linked list) better, without problems with eof?
Also the sorting part isn't enough readable because of a great amount of if-else statements, and I think I don't need them.. I will think about it and I'll try to rewrite it
Do you know about some good tutorial about linked lists, binary trees and such things(for example 'halda', I don't know how it is called in English, maybe 'heap'..) ?
Code:
#include <iostream.h>
#include <fstream.h>
#include <process.h>
struct NodeT {
int value;
NodeT *next;
};
void printlist(NodeT *root)
{
cout << ": ";
while (root != NULL) {
cout << root->value << ' ';
root = root->next;
}
cout << endl;
}
int main(void)
{
/**** reading data: ****/
ifstream fin("x.x");
NodeT *root, *sorted, *p, *badnode;
p = root = sorted = NULL; badnode = NULL;
while (!fin.eof()) {
if (root == NULL) { // zaciatok
p = root = new NodeT;
}
else {
badnode = p;
p->next = new NodeT;
p = p->next;
}
fin >> p->value;
p->next = NULL;
}
if (badnode == NULL) {
delete root;
root = NULL;
}
else {
delete badnode->next;
badnode->next = NULL;
}
p = NULL;
// **** sort: ****
NodeT *lastsortednode, *min;
while (root != NULL) {
cout << "root "; printlist(root);
cout << "sorted "; printlist(sorted);
min = p = root;
while (p != NULL) {
if (p->value < min->value)
min = p;
p = p->next;
} // najde minimum min->value
if (min == root) {
if (sorted == NULL) {
lastsortednode = sorted = root;
}
else {
lastsortednode->next = root; // adds node with minimal value to sorted list
lastsortednode = lastsortednode->next;
}
root = root->next;
lastsortednode->next = NULL;
}
else {
p = root;
while (p != NULL) {
if (p->next == min)
break;
p = p->next;
} // finds node before minimum (p->next = min)
if (sorted == NULL) {
lastsortednode = sorted = p->next;
}
else {
lastsortednode->next = p->next; // adds node with minimal value to sorted list
lastsortednode = lastsortednode->next;
}
p->next = min->next; // throws min out of unsorted part of list
lastsortednode->next = NULL;
} // else (min == root)
} // while root
cout << "root "; printlist(root);
cout << "sorted "; printlist(sorted);
fin.close();
system("pause");
return 0;
}