Thread: Search and Sort functions for a stack..

  1. #1
    blizeH
    Guest

    Search and Sort functions for a stack..

    Hi, i'm currently doing a college assignment about stacks in C++... and i'm failing miserably!! i've managed to do most of the functions, but i'm completely stumped on the search and sort functions! if anyone could help me, i'd be eternally grateful

    here's the code i have so far (i'd ignore my 'attempts' at the functions so far, they're basically copied and pasted and very slightly modified... no where near working!):

    Code:
    /* U18.01/U19.01 - Programming Concepts and Practise
    	12th January, 2002
       By Nick Drew
    
       A modular based C++ Solution which simulates the operation of a stack data
       structure.																					*/
    
    #include <iostream.h>
    #include <ctype.h>
    #include <conio.h>
    #include <stdlib.h>
    
    
    int mynumbers [10];
    int point;
    
    void push (void);
    void pull (void);
    void display (void);
    void status (void);
    void displaya (void);
    void search (void);
    void sort (void);
    void pause (void);
    
    int main (void)
    {
    	char option;
    
       point =-1;
    
       // - - - - - Display Main Menu - - - - - /
       do
       {
       	clrscr();
          cout << ".: Main Menu :.";
          cout << "\n\nA :: Push Item";
          cout << "\nB :: Pull Item";
          cout << "\nC :: Display Stack";
          cout << "\nD :: Check Stack Status";
          cout << "\nE :: Display Array";
          cout << "\nF :: Linear Search";
          cout << "\nG :: Sort";
          cout << "\nX :: Exit";
          cout << "\n\nChoose Option Now : ";
    
          cin >> option;
          option = toupper(option);
          switch (option)
          {
          	case 'A' :	push();
             				break;
             case 'B'	:	pull();
             				break;
             case 'C'	:	display();
             				break;
             case 'D' :  status();
             				break;
             case 'E'	:  displaya();
             				break;
             case 'F'	:	search();
             				break;
             case 'G'	:  sort();
             				break;
             case 'X'	:	exit(0);
           }
       }while (option!= 'X');
       // - - - - - - - - - - - - - - - - - - /
    
       return 0;
    }
    
    
    // - - - - - Push Function - - - - - //
    void push (void)
    {
      clrscr();
      if (point < 9)
      {
        point++;
        cout << ".: Push Item:.\n\n\n";
        cout << "Please Enter Number : ";
        cin >> mynumbers[point];
      }
      else
      {
        cout << "Stack is already full!";
      }
      pause();
    }
    // - - - - - - - - - - - - - - - - - //
    
    
    
    // - - - - - Pull Function - - - - - //
    void pull (void)
    {
      clrscr();
      if (point < 0)
      {
        cout << "Stack is empty!";
      }
      else
      {
        point--;
        cout << "Item Pulled!\n";
        cout << "Data" << mynumbers [point+1] << "removed";
      }
      pause();
    }
    // - - - - - - - - - - - - - - - - - //
    
    
    
    // - - -Display Stack Function- - - //
    void display (void)
    {
      int counter;
    
      clrscr();
      if (point > -1)
      {
        for (counter = point; counter >=0; counter --)
        {
          cout << "\nPosition " << counter << "contains" << mynumbers[counter];
        }
      }
      else
      {
        cout << "There are no items in the stack! Nothing to display!";
      }
      pause();
    }
    // - - - - - - - - - - - - - - - - //
    
    
    
    // - Check Stack Status Function - //
    void status (void)
    {
      int howmany;
    
      clrscr();
      if (point ==-1)
      {
        cout << "\n\nStack Empty";
      }
      else
      {
        howmany = point + 1;
        cout << "\n\nStack contains " << howmany << " elements";
      }
      pause();
    }
    // - - - - - - - - - - - - - - - - //
    
    
    
    // - - Display Array Function - - //
    void displaya (void)
    {
      int counter;
    
      clrscr();
      for (counter = -1; counter <10; counter ++)
      {
        cout << "\nPosition " << counter << "contains" << mynumbers[counter];
        cout << endl;
      }
      pause();
    }
    // - - - - - - - - - - - - - - - - //
    
    
    
    // - - - - Search Function - - - - //
    void search (void)
    {
        int iIndex;	// flag to indicate when an item has been found
        int iNot_Found;
    				// Start from element zero
        iIndex = 0;
    				// assume not found initially
        iNot_Found = 1;
    				// now loop until either the item is found or
    				// reached the end of the array
        while (    ( iNot_Found == 1     )
                && ( iIndex     <  iSize ) )
        {
    				// if a match
            if ( cArray[iIndex] == cTarget )
            {
                iNot_Found = 0;
            }
            else	// otherwise go onto next element
            {
    			iIndex = iIndex + 1;
            } // endif
        } // endwhile
    				// If not found
        if ( iNot_Found == 1 )
        {
            return -1;
        }
        else
        {
            return iIndex;
        } // endif
    } // endfunction SearchCharArray
    // - - - - - - - - - - - - - - - - //
    
    
    
    // - - - - Sort Function - - - - - //
    void sort (void)
    {
      int InsertInList (string ThisList[], string sItem, int iCurSize)
      {
        int i = iCurSize;
        iCurSize = iCurSize + 1;
        while ( ThisList[i-1] > sItem && i > 0)
        {
            ThisList[i] =ThisList[i -1]; // move each item down 1
    	i = i - 1;
       }
    
       ThisList[i] = sItem; // insert new item
    
       return iCurSize;
    }
    
    
    
    
    void pause (void)
    {
      char keypress;
    
      cout << "\n\n\n Please press any key to continue";
      keypress = getch();
    }

  2. #2
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>but i'm completely stumped on the search and sort functions!
    Maybe I'm a closet purist, but searching and sorting a stack completely defeats the purpose of using a stack, dones't it? Since you're already trying to get heap-like behavior, just use a heap. :-)
    *Cela*

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Couple of things. First off for your sort, I'd suggest looking for a small tutorial on bubble sort. Its extremely easy to implement and although it is slow this shouldn't matter at all for such a small array.

    Second, when you display the array in function displaya(), you start at -1, you should start at zero since that is where the array begins. mynumbers[-1] should give you unwanted problems.

    Last to search for something all you really need is something like:
    Code:
    for (int x=0; x<stackSize; x++)
    {
        if (stack[x]==searchItem)
            return x;
    }
    return -1;  // wasn't found in the loop, so it doesn't exist!

  4. #4
    blizeH
    Guest
    Thank you very much for your help
    I know it's defeating the object of a stack, but for some reason we HAVE to do it as part of the assignment criteria!

    Thank you very much for the help yelton, tis very much appreciated!! Now all i have to do is find something on bubble sort

  5. #5
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    Here's something on sorting algorithms:

    http://linux.wku.edu/~lamonml/algor/sort/sort.html

  6. #6
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Sorting a stack would require two temporary stacks.

    The algorithm would be similar to the
    Towers of Hanoi problem.

    Sorting a stack would be very inefficient.

    But you can of course "cheat" as demonstrated by PJYelton.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  7. #7
    blizeH
    Guest
    Gah, i spent AGES doing bubblesort (it was the only one i could do) and on the assignment sheet it says we have to show we can do quicksort... i have absolutely NO idea how to do this (i've looked up many examples, but really don't understand it anywhere near enough to implement it into my own program) so for now i will stick with the bubble sort and maybe do a seperate documentation on quicksort (probablly that one you posted shiro - thank you very much!!)

  8. #8
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    What he's using isn't even really a stack, more of a vector.

    Sorting an actual stack would just be a waste of time.

    Did your teacher lecture at all on quicksort? That is definately one of the best sorts available, but can be a real pain to understand if you've never done any sorting before.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  2. Replies: 3
    Last Post: 08-03-2007, 04:11 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Is there a way to sort or search an outfile?
    By Golffor1 in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2003, 11:15 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM