Hi!
I'm a fellow that has big problems on starting this next datastructure lab in c++. I have so much in my mind right now and I don't know if I'm gonna complete this lab on time.
So i'm wondering if there are someone that could help me with this lab?
We use at the school visual studio 6.0
Here's the lab description:
A) Hash table
Now your going to make an article-storage were the articles will be saved in a hash-table for fast prompt accessible. For every article saves the information of the article-number, article-type and the amount articles in the storage.
You should be able to “hash” on the article-number( i.e article-number is the key). You should be able to ADD, SEEK and LIST the articles in the storage.
The programme shall handle collision with "Separate Chaining” i.e create linked list at collisions. You shall therefore make an array of pointers that initiate to NULL, afterward you should be able to seek and add articles that are missing.
At collision you do your linked list. Use here as said a linked list and a string class.
Remember when you add an article for the first time to the index, you have to move the NULL-pointer to point at the new post and then link the article last in the list.
If an article with that article-number already exist in the list, the numbers on the storage should increase on the one that already existed.
Does’nt the articlename correspond, then you could yourself decide how it’s gonna be solved in your programme.
Assume from these files(must use)
1. Hash.h
2. Hash.cpp
3. Article.h
B) Sorting
This task goes out on that you have to implement 3 optional sorting-algorithms. The algorithms shall be choosed so an algorithm works with O(n2), next with O(n log n) and the last one with O(n).
Write a programme that at random takes number-values to a file. This file shall be used as indata for sorting. After the sorting, shall the result be written out into a result-file. The result-file shall also be used as indata for sorting, to see how the algorithms works on the already sorted or almost sorted data ( if some values changes).
You shall have to create data-files with 5 different quantity of numbers to sort. These values shall be used as indata to respective algorithm. Run the algorithm with indata that is both sorted and unsorted.
You shall use these following numbers: 100 000, 200 000, 400 000, 800 000 and 1 600 000 values. Same computer must be used to check all values to have a more fair result and the computer may not work with other things during the process of the sorting.
Is it so that your computer makes the sorting too quick or too slow, you may have to change some numbers so you get a better result, NOTE that the quantity of the numbers shall double for each sorting.
Every algorithm shall have two variables, compare and swap, that counts how many comparision and copies of values has been made during the sort. These two variables shall be used in comparision between the different algorithms.
Registrate also the time the algorithms take when they are used, by using following class:
1. Timer.h
2. Timer.cpp
Do a table with your results that contains these facts:
• Run with an unsorted and a sorted data
• Values for compare and swap for respective run
• Time-consumption for respective run
Here comes the code for the following files.
That's all. You can send me the programme by mail if you finished the lab. That would be awesome!Code:Code Tags added by Kermi3
1. Hash.h
#ifndef _HASH_H
#define _HASH_H
#include "LinkedList.h"
class Hash
{
public:
Hash();
~Hash();
//...
private:
const int TABLESIZE;
LinkedList *m_table;
};
#endif
2. Hash.cpp
#include "Hash.h"
Hash::Hash() : TABLESIZE(11)
{
m_table = new LinkedList[TABLESIZE];
}
Hash::~Hash()
{
delete[] m_table;
}
3. Article.h
#ifndef _ARTICLE_H
#define _ARTICLE_H
#include "String.h"
class Article
{
public:
Article(int i_key, int i_number, String i_type);
//...
private:
int m_key;
int m_number;
String m_type; //Använd din strängklass
};
#endif
4. Timer.h
#ifndef TIMER_H
#define TIMER_H
class Timer
{
public:
Timer(){ m_startTime = 0; m_stopTime = 0; }
int startTimer(); //Returnerar 0 om timern inte kunde initieras
double stopTimer(); //Returnerar tiden (ms) som förlöpt mellan start och stop
double getTime(); //Hämtar sista tidtagningen i millisekunder
private:
double m_startTime;
double m_stopTime;
double m_frequence;
};
#endif
5. Timer.cpp
#include
#include "timer.h"
int Timer::startTimer()
{
LARGE_INTEGER start, freq;
if(!QueryPerformanceFrequency(&freq))
return 0;
m_frequence = (double) freq.QuadPart;
QueryPerformanceCounter(&start);
m_startTime = (double)start.QuadPart;
return 1;
}
double Timer::stopTimer()
{
LARGE_INTEGER end;
QueryPerformanceCounter(&end);
m_stopTime = (double)end.QuadPart;
return (m_stopTime-m_startTime) * 1000.0 / m_frequence;
}
double Timer::getTime()
{
return (m_stopTime-m_startTime) * 1000.0 / m_frequence;
}
Code Tags added by Kermi3
THANK U ALL!
email: [email protected]
