question about lists

This is a discussion on question about lists within the C++ Programming forums, part of the General Programming Boards category; I'm a computer science student who has recently started taking a UNIX course. One of the first things I'm supposed ...

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    1

    question about lists

    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.

  2. #2
    Registered User
    Join Date
    Dec 2001
    Posts
    70
    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>

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    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.

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,803
    Its very easy to do. The STL list container even has its own sort function built into it.
    Code:
    #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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    Registered User
    Join Date
    Oct 2001
    Posts
    13
    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.

    Code:
    ///////////////////////////////////////////////////////////////////////
    // 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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Exam Question - Possible Mistake?
    By Richie T in forum C++ Programming
    Replies: 15
    Last Post: 05-08-2006, 03:44 PM
  2. One more question about linked lists?
    By shaeng in forum C Programming
    Replies: 2
    Last Post: 06-24-2003, 07:36 AM
  3. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 08:22 PM
  4. Question about linked lists.
    By cheeisme123 in forum C++ Programming
    Replies: 6
    Last Post: 02-25-2003, 12:36 PM
  5. Replies: 2
    Last Post: 01-18-2003, 12:32 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21