473,326 Members | 2,061 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Need help implementing an ordered-list:storage structure is linked-list using 2arrays

I need help with a program. I have implemented that following header file with an unordered list using one array, but i need to be able to use an ordered list and 2 arrays (one for the links and one to use as an index to the freearray cells).
Here is the exact problem specifications:
Create an ordered list template class named OLType to implement an ordered list with operations of insert, remove, print, empty, full, size. The storage structure is to be a linked-list emulation using dynamic arrays. It will require a minimum of two arrays, one for the data and one for the 'next' links. The 'free' list can be incorporated into the 'next' links array if done correctly. The 'public' portion of your class file must be as follows:
public:
OLType(size_t n=100);
~OLType();
void insert(const T& item);
void remove(const T& item);
void print() const;
size_t size() const;
bool empty() const;
bool full() const;

Here is the code I have so far:

#ifndef OLType_H
#define OLType_H

#include <iostream>

using namespace std;

template <class T>
class OLType {
public:
OLType(size_t n=100);
~OLType();
void insert(const T& item);
void remove(const T& item);
void print() const;
size_t size() const;
bool empty() const;
bool full() const;
private:
size_t MAX_LENGTH;
size_t n; // max number that can be stored in the list
int count; // number of elements in the list
T *data; // pointer to the array that holds the list elements
};

template <class T>
OLType<T>::OLType(size_t n) {
MAX_LENGTH = n;
count = 0;
data = new T[MAX_LENGTH];
}

template <class T>
OLType<T>::~OLType() {
delete [] data;
}

template <class T>
void OLType<T>::insert(const T& item) {
data[count] = item;
count++;
}

template <class T>
void OLType<T>::remove(const T& item) {
int i = 0;
while (i<count && item != data[i])
i++;
if (i<count) {
data[i] = data[count-1];
count--;
}
}

template <class T>
void OLType<T>::print() const {
int i;
for(i=0; i<count; ++i)
cout << data[i] << " ";
}

template <class T>
size_t OLType<T>::size() const {
return count;
}

template <class T>
bool OLType<T>::empty() const {
return (count == 0);
}

template <class T>
bool OLType<T>::full() const {
return (count == MAX_LENGTH);
}

#endif

Any help with solving this problem would be greatly appreciated. I am not that strong of a programmer and just cannot seem to find the correct way to do this problem. Thank you.
Sep 12 '06 #1
1 3301
Banfa
9,065 Expert Mod 8TB
Well I personally would not normally implement a linked list as 2 arrays, I would use a single array of structures.

However it is possible.

You next step is to set up the array of "next" pointers. However rather than pointers I think these will need to be an integer type. This array will need the same number of entries as data. Assuming that this array of ints is called nextIndex then for any given current index IX

data[IX] = the value at this index
nextIndex[IX] = the next index in the list

You will need 3 other things

1. A special value (#defined or static const) indicating the end of the list

2. A data member recording the first index in the list

3. A data member recording the first index in the free list

Since any given index can only be used (exclusive) or not used (i.e. can't be used and not used then the same array of indexes can be used to hold the list of free entries. As I have stated in 3 above all you need is a new starting point.
Sep 12 '06 #2

Sign in to post your reply or Sign up for a free account.

Similar topics

6
by: Kevin Altis | last post by:
Does anyone have experience running Python from a USB storage device? Whether it is the need for doing a demo of your application, doing a bit of consulting, or just showing off Python, it would be...
1
by: adeleinandjeremy | last post by:
I am taking a second programming course in Java and am currently attempting to apply what I have learned using Python instead. One thing that is puzzling me is how to use an iterator. I am...
2
by: JTrigger | last post by:
I am rather new to the XML and XSD world and was wondering what the code would look like to write the following XSD items as classes in C# with all the proper XML attributes to make them...
2
by: fumanchu | last post by:
I need to insert records into a Sybase database via a linked table. I have a valid, tested DSN ODBC connection to the Sybase database named 'SBA9link'. I also have created a link to a table in...
10
by: Duncan M Gunn | last post by:
Hi, I need to store the following matrix of values: T U V A 2 1 1 B 2 - - C - - 2 Where (-) is an empty cell.
3
by: Dongsheng Ruan | last post by:
Not quite related with Python. But my Data Structure course is experiemented on python and there is no data structure group, So I have to post here: Write a procedure (in pseudocode!) to increase...
1
by: hmoundekar | last post by:
actually i want to generate a tree structure on client side, the application is simple web based, and need to display the data extracted from the database to client in tree structure. but the problem...
1
by: a Wellner | last post by:
I have a Database stored on the server, and a replica on a laptop, used for data collection in the field. The laptop is only connected to the network during synchronization. I am linking to tables...
3
by: dkultasev | last post by:
Hello, I have database, which contains the list of laptop companies and some information about them. Some laptop models, have series, sub series, family's and so on. for example. Acer Aspire...
2
by: e2point | last post by:
i need to create a storage module which can store any thing the user wants. I want it to handle almost any storage requirement, so that clients can define their own key classes derived from the...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.