question about lists

[Amanda Sedai]

I'm a computer science student who has recently started taking a UNIX course. One of the first things I'm supposed to do in this class is write a C++ program that sorts a list of numbers. If this were Visual C++ I'd just write a list class, but since I'm unfamiliar with this compiler (and the operating system in general) I want to make this as simple as possible. So, I have two questions:

-I know "iostream" works in UNIX. Is there also a pre-defined list class and if so how do I use it?

-If I can't use an already-made list header file, is there any way (other than using lists) to make an infinite array? My professor implied that there was a way to write this program without using lists.

Thanks.

[golem]

You can use vector instead of list.

For example

vector<int> array; // Define an infinite array of integers

And you add an integer, for example 5, to the vector tail by this command

array.push_back (5);

Then you can access any element of the vector by an index. For
example array[10] means eleventh element of the vector.

array[10] = 5; // Change the 11th element

Don't forget to include header

using namespace std;
#include <vector>

[elad]

the Standard Template Library does contain a predefined list class. If your compiler is not STL compliant, however, then you will need to create your own list, if that's what you want to do.

Unfortunately, the word list is used in a number of different contexts. For example, "a list of number" may mean a group of numbers stored in a list or a group of numbers stored in an array or some container other than a list (such as an array, or vector, or map, or whatever) but refered to in conversation as a list.

[hk_mp5kpdw]

Its very easy to do. The STL list container even has its own sort function built into it.

#include <list>
using namespace std;
...
list<int> IntList;  // Linked list of 'int' objects
...
IntList.push_back(500); // Add 500 to end of list->500
IntList.push_back(400); // Add 400 to end of list->500->400
IntList.push_back(300); // Add 300 to end of list->500->400->300
...
IntList.sort(); // Linked list is now magically sorted->300->400->500

Use an iterator and a for loop to output the contents for the user to view.

[blundstrom]

It sounds like you will have to read a file of integers like:
23
34
12
1
and covert them strings to int and put them in a sorted array.

I doubt that your prof wants you to learn how to call list::sort() although he/she may want you to learn about STL container classes.

To do this lab without any STL list, deques, vectors, hash or anything like that you will need a dynamic int array and then you can use an insertion sort. The dynamic array is made with a
int * int_array = new int[ARRAY_SIZE] (then deleted with delete [] int_array when finished)

Here is a class that I wrote that will handle dyamic int array sizing using new and a smallest to largest integer insertion sorting. At the end of the code is a small tester.

However, it was written in VC++ but as a standard console app, so there is no MFC MS specific stuff. The includes like stdio.h are also part of the Unix C headers. You probably won't have to change a single include. You may have to change the newlines to Unix style. TextPad will do it. It should at least get you started on the right path.

///////////////////////////////////////////////////////////////////////
// SortedIntArray.h:
//
//////////////////////////////////////////////////////////////////////

#ifndef __SORTEDINTARRAY_H
#define __SORTEDINTARRAY_H

#include <memory.h>
#include <stdio.h>	

#define DEFAULT_ARRAY_SIZE	10 // Sizes for testing, change to larger number 
#define DEFAULT_GROW_AMOUNT	5 // (eg 100 and 25)

class SortedIntArray  
{
public:
	SortedIntArray();
	virtual ~SortedIntArray();
	void insert_int(int newval);
	void PrintArray();
	int GetArraySize();

protected:
	int * i_arr;
	int ArraySize;
	int NextOpenIndex;
	void grow_array();
	int find_insert_index(int newval);
	void insert_new_val(int index, int newval);

};

#endif

///////////////////////////////////////////////////////////////////////
// SortedIntArray.cpp
//
//////////////////////////////////////////////////////////////////////

#include "SortedIntArray.h"

SortedIntArray::SortedIntArray()
{
	printf("Constructing SortedIntArray: (%d)\n", DEFAULT_ARRAY_SIZE);
	i_arr = new int[DEFAULT_ARRAY_SIZE]; // array of ints created when you create object
	
	ArraySize = DEFAULT_ARRAY_SIZE;
	NextOpenIndex = 0;
	memset( (void *)i_arr, 0, ArraySize * sizeof( int ) ); // fill with 0's
}

SortedIntArray::~SortedIntArray()
{	
	printf("Destructor, deleting i_arr[] (%d)\n", ArraySize);
	delete [] i_arr; // Cleanup when object falls out of scope
}

int SortedIntArray::GetArraySize()
{	return ArraySize;}

void SortedIntArray::insert_int(int newval)
{
	int insert_index = 0;

	if( NextOpenIndex == 0 )
	{
		i_arr[0] = newval;
		printf("inserting %d at 0\n", newval);
		NextOpenIndex++;
		return; // nothing left to do, bail out
	}
	if ( NextOpenIndex > (ArraySize - 1) ) // Nowhere to put new number
		grow_array();
	
	//
	// An insert sort is when you check all the elements for the correct position
	// of (in this case) a number.  It means that all your elements are sorted as they
	// go into the array.  This process gets increasingly slower are your array grows
	// in size.  You can, after 3 or more elements, begin to use a binary sort, which is
	// many times faster.... but you have to implement it.
	//

	insert_index = find_insert_index(newval);
	printf("inserting %d at %d\n", newval, insert_index);
	insert_new_val(insert_index, newval);
}

void SortedIntArray::PrintArray()
{
	printf("\nPrinting used part of array\n----------------------------------\n");
	for( int i = 0; i < NextOpenIndex; i++)
	{
		printf("%d ", i_arr[i]);
		//printf("%d:\t%d\n", i, i_arr[i]);
	}
	printf("\n----------------------------------\n\n");
}


int SortedIntArray::find_insert_index(int newval)
{
	
	int ret = 0;
	bool found_index = false;
	
	for (int i = NextOpenIndex - 1; i >= 0; i--) // backwards loop
	{
		if( newval > i_arr[i] )
			return (i + 1); 
	}
	if( !found_index ) // number is less than entire list, it goes first
		ret = 0;

	return ret;
}

void SortedIntArray::insert_new_val(int index, int newval)
{
	if( index == NextOpenIndex )
	{
		i_arr[index] = newval;
		NextOpenIndex++;
		return;  // leave
	}
	// OR
	// move all of the elements from the insert index up one
	for( int i = NextOpenIndex; i >= index; i--) // backwards
	{
		if ( i > 0 )
			i_arr[i] = i_arr[i - 1]; 
	}
	// Insert new value;
	i_arr[index] = newval;
	NextOpenIndex++; // move position
}

//-----------------------------------------
//	Grow Array while preserving data.
//-----------------------------------------
void SortedIntArray::grow_array()
{
	int * temp, * new_arr;
	int new_size = 0;
	
	temp = i_arr; // point temp a original array for later deletion
	
	new_size = ArraySize + DEFAULT_GROW_AMOUNT;
	printf("Growing array form %d to %d...\n", ArraySize, new_size);
	new_arr = new int[new_size]; // make new array.
	memset( (void *)new_arr, 0, new_size * sizeof( int ) ); // fill with zeros
	memcpy( (void*)new_arr, (void *)i_arr, ArraySize * sizeof( int ) ); // copy data
	
/*
	// Afraid of memcpy and what it is doing? Then use this:
	for( int i = 0; i < ArraySize; i++ )
		new_arr[i] = i_arr[i];
*/
	i_arr = new_arr; // i_arr is now pointing at new_arr
	ArraySize = new_size;
	delete []temp; // release original array's resources
}

//////////////////////////////////////////////////
//  Tester - main.cpp
//////////////////////////////////////////////////
#include "SortedIntArray.h"
int main()
{
SortedIntArray si_arr;
	si_arr.insert_int(10);
	si_arr.insert_int(34);
	si_arr.insert_int(12);
	si_arr.insert_int(6);
	si_arr.insert_int(11);
	si_arr.insert_int(10);
	si_arr.insert_int(15);
	si_arr.insert_int(9);
	si_arr.insert_int(7);
	si_arr.insert_int(10);
	si_arr.insert_int(81);
	si_arr.insert_int(8);
	si_arr.insert_int(10); // 10 is our repeating number
	si_arr.insert_int(2);
	si_arr.insert_int(1);
	si_arr.insert_int(5);
	si_arr.insert_int(4);
	si_arr.insert_int(3);
	si_arr.insert_int(10);
	
	si_arr.PrintArray();

	return 0;
}