Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!zaphod.mps.ohio-state.edu!mips!cs.uoregon.edu!ogicse!intelhf!ichips!inews!pima!bhoughto
From: bhoughto@pima.intel.com (Blair P. Houghton)
Newsgroups: comp.lang.c
Subject: Re: Alphabetizing stacks
Message-ID: <3938@inews.intel.com>
Date: 21 Apr 91 20:43:07 GMT
References: <1991Apr21.121232.2659@jack.sns.com>
Sender: news@inews.intel.com
Organization: Intel Corp, Chandler, AZ
Lines: 40

In article <1991Apr21.121232.2659@jack.sns.com> jtanner@jack.sns.com (Jason Tanner) writes:
>
>  I have been faced with an interesting dilema. in a
>program I am writing I need to alphabetize a Stack (of any
>length). The alphabetizing will occur after the stack is
>entered (push) and before I start removing things from it
>(pop).  The only pointers in the stack are ptrtop (top of
>stack) and ptrnext(used to point to each members next
>member) and ptrnew but this is used just for pushing on new
>members of the stack.  Any ideas on aplhabetizing stacks
>please post here.  If anyone has actuall example sourc-code
>of this please send it via private mail

What you need to do is create more stacks and solve
the Generalized, Infinite-Disc Tower of Hanoi problem. :-)

Actually, if you can't alphabetize it while entering elements,
and you can't use qsort(3) (which you can't do because you
have a linked-list and not an array), you'll have to create
another list, pop from the stack and enter into the list in
reverse-alphabetic order, then run through the list pushing
the elements onto the stack (reversing them back to alphabetical
order).

What I don't get is why there's a "ptrnew".  If it's a holder
for the newly-malloc'ed stack member _before_ you've pushed
it onto the stack, then it makes sense.  Otherwise it's got
to be redundant for something (barring the fact that what you
have isn't really a stack).

Here's one for the final exam:
If you're allowed to abuse ptrnew (not by casting, but
by using it for elements already in the middle of the
stack), can you alphabetize the stack in-situ?

When all else fails, get a copy of Knuth's _Searching_and_Sorting_
or _Sorting_and_Searching_, or vol. III, or whatever...

				--Blair
				  "I may be smiling, but I'm not kidding."