• C

"Priority Stack" as doubly linked list

I need help writing a program that uses a priority stack(a stack in which the push operation requires that the object added to the stack sinks to its proper "priority" level).  This has to be implemented as a doubly linked list.  My stack will contain integers.  I haven't the foggiest idea how to start this!!!  This program is a matter of life or death!!!  Please can someone help me???
missqAsked:
Who is Participating?
 
alexoConnect With a Mentor Commented:
This one is quite easy.
Here's the code (not tested extensively, bugs may occur).

#include <limits.h>
#include <stdlib.h>

#define ERROR INT_MIN


typedef struct element
{
    int             item;
    int             priority;
    struct element  *pNext;
    struct element  *pPrevious;
} Element;



void Push(Element *list, int priority, int item)
{
    Element *pCurrent,
            *pNew,
            *pOld;

    /* Find position to push item to */
    for (pCurrent = list;
         pCurrent->pNext && pCurrent->pNext->priority > priority;
         pCurrent = pCurrent->pNext)
        ;

    /* Allocate new item */
    pNew = (Element*) malloc(sizeof(Element));
    pNew->priority = priority;
    pNew->item = item;

    /* Adjust pointers */
    pOld = pCurrent->pNext;
    pCurrent->pNext = pNew;
    pNew->pNext = pOld;
    pNew->pPrevious = pCurrent;
}


int Pop(Element *list)
{
    Element *pCurrent = list->pNext,
            *pOld;
    int     item;

    /* Top of stack reached? */
    if (!pCurrent)
        return ERROR;

    /* Save data of popped element */
    pOld = pCurrent->pNext;
    item = pCurrent->item;

    /* Remove popped element */
    free(pCurrent);

    /* Adjust pointers */
    list->pNext = pOld;
    list->pNext->pPrevious = list;

    return item;
}


void main()
{
    /* Dummy element to serve as the head of the list */
    Element theList = { ERROR, INT_MAX, NULL, NULL };

    int item;

    Push(&theList, 20, 20);
    Push(&theList, 10, 10);
    Push(&theList, 30, 30);

    item = Pop(&theList);
}
0
 
missqAuthor Commented:
i've tried your code on a Unix compiler,
I get this error message:

malformed input file (not rel or archive)

Any suggestions???
0
 
missqAuthor Commented:
sorry, I forgot to put the   .c  after my file name!!!  When I did that and then tried to compile, these errors followed:

stack.c:4: undefined or invalid # directive
stack.c: In function `Push':
stack.c:18: `pNew' undeclared (first use this function)
stack.c:18: (Each undeclared identifier is reported only once
stack.c:18: for each function it appears in.)
stack.c:19: `pOld' undeclared (first use this function)
stack.c:22: structure has no member named `pnext'
stack.c: In function `Pop':
stack.c:37: `pOld' undeclared (first use this function)
stack.c:38: parse error before `int'
stack.c:41: `ERROR' undeclared (first use this function)
stack.c:44: `item' undeclared (first use this function)
stack.c: In function `main':
stack.c:56: `ERROR' undeclared (first use this function)  
0
Simplify Active Directory Administration

Administration of Active Directory does not have to be hard.  Too often what should be a simple task is made more difficult than it needs to be.The solution?  Hyena from SystemTools Software.  With ease-of-use as well as powerful importing and bulk updating capabilities.

 
ozoCommented:
And after you corrected those errors what happened?
0
 
alexoCommented:
The program compiles without errors or warnings.  Did you cut and paste it exactly as shown?
0
 
missqAuthor Commented:
I cut and pasted and tried to compile again, resulting in the following errors:

stack2.c:1: parse error before `.'
stack2.c: In function `Pop':
stack2.c:50: `INT_MIN' undeclared (first use this function)
stack2.c:50: (Each undeclared identifier is reported only once
stack2.c:50: for each function it appears in.)
stack2.c: In function `main':
stack2.c:70: `INT_MIN' undeclared (first use this function)
stack2.c:70: `INT_MAX' undeclared (first use this function)      

I am having such a difficult time with C programming!!  Why does it come so easy for some and i just can't get it!!!??
0
 
missqAuthor Commented:
I have narrowed the errors down to the Push function but I don't understand what they mean when they say (first use this function): (I'll be in my C books all afternoon trying to figure out how to correct what appears to be minor errors--please have patience with me!!)

stack2.c: In function `Push':
stack2.c:20: `pNew' undeclared (first use this function)
stack2.c:20: (Each undeclared identifier is reported only once
stack2.c:20: for each function it appears in.)
stack2.c:21: `pOld' undeclared (first use this function)

      1 #include<limits.h>
      2 #include <stdlib.h>
      3
      4      #define ERROR INT_MIN
      5
      6
      7      typedef struct element
      8      {
      9          int             item;
     10          int             priority;
     11          struct element  *pNext;
     12          struct element  *pPrevious;
     13      } Element;
     14
     15
     16
     17      void Push(Element *list, int priority, int item)
     18      {
     19          Element *pCurrent;
     20                  *pNew;
     21                  *pOld;
     22
23 /* Find position to push item to */
     24          for (pCurrent = list;
     25               pCurrent->pNext && pCurrent->pNext->priority > priority;
     26               pCurrent = pCurrent->pNext)
     27              ;
     28
     29          /* Allocate new item */
     30          pNew = (Element*) malloc(sizeof(Element));
     31          pNew->priority = priority;
     32          pNew->item = item;
     33
     34          /* Adjust pointers */
     35          pOld = pCurrent->pNext;
     36          pCurrent->pNext = pNew;
     37          pNew->pNext = pOld;
     38          pNew->pPrevious = pCurrent;
     39      }
     40
     41
     42      int Pop(Element *list)
     43      {
     44          Element *pCurrent = list->pNext,
     45                  *pOld;
     46          int     item;
     47
     48          /* Top of stack reached? */
     49          if (!pCurrent)
     50              return ERROR;
     51
     52          /* Save data of popped element */
     53          pOld = pCurrent->pNext;
     54          item = pCurrent->item;
     55
     56          /* Remove popped element */
     57          free(pCurrent);
     58
     59          /* Adjust pointers */
     60          list->pNext = pOld;
     61          list->pNext->pPrevious = list;
     62
     63          return item;
     64      }
     65
     66
     67      void main()
     68      {
69 /* Dummy element to serve as the head of the list */
     70          Element theList = { ERROR, INT_MAX, NULL, NULL };
     71
     72          int item;
     73
     74          Push(&theList, 20, 20);
     75          Push(&theList, 10, 10);
     76          Push(&theList, 30, 30);
     77
     78          item = Pop(&theList);
     79      }
     80
 

























 




















































0
 
alexoCommented:
<Grumble> <Grumble> <Grumble> <Sigh>...

     19          Element *pCurrent;
     20                  *pNew;

Change the semicolons to commas:

Element *pCurrent,
     *pNew,
     *pOld;

May I suggest a good C programming book "The C programming language 2nd edition".

0
 
alexoCommented:
>> I am having such a difficult time with C programming!!  Why does it come so easy for some and i just get it!!!??

In no particular order:
- Curiosity
- Patience
- Experience
- Some good books

0
 
missqAuthor Commented:
I finally got it!!!  Thanks so much for your help, I'd never get through this if it weren't for people like you, alexo.  Thanks again for your time, knowledge and patience!!  missq
0
 
alexoCommented:
Hey, you forgot curiosity and the good books!  :-)
0
 
missqAuthor Commented:
I didn't forget!!  You're the best!!!  thanks again!!!
0
 
alexoCommented:
By the way, vicky asked a related question.  You can see it in the "previously answered" section.
0
 
missqAuthor Commented:
Thanks for the "pointer" to Vicky's question!!!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.