Solved

"Priority Stack" as doubly linked list

Posted on 1998-04-17
14
268 Views
Last Modified: 2010-05-18
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???
0
Comment
Question by:missq
  • 7
  • 6
14 Comments
 
LVL 11

Accepted Solution

by:
alexo earned 170 total points
ID: 1249451
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
 

Author Comment

by:missq
ID: 1249452
i've tried your code on a Unix compiler,
I get this error message:

malformed input file (not rel or archive)

Any suggestions???
0
 

Author Comment

by:missq
ID: 1249453
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
 
LVL 84

Expert Comment

by:ozo
ID: 1249454
And after you corrected those errors what happened?
0
 
LVL 11

Expert Comment

by:alexo
ID: 1249455
The program compiles without errors or warnings.  Did you cut and paste it exactly as shown?
0
 

Author Comment

by:missq
ID: 1249456
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
 

Author Comment

by:missq
ID: 1249457
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
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 
LVL 11

Expert Comment

by:alexo
ID: 1249458
<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
 
LVL 11

Expert Comment

by:alexo
ID: 1249459
>> 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
 

Author Comment

by:missq
ID: 1249460
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
 
LVL 11

Expert Comment

by:alexo
ID: 1249461
Hey, you forgot curiosity and the good books!  :-)
0
 

Author Comment

by:missq
ID: 1249462
I didn't forget!!  You're the best!!!  thanks again!!!
0
 
LVL 11

Expert Comment

by:alexo
ID: 1249463
By the way, vicky asked a related question.  You can see it in the "previously answered" section.
0
 

Author Comment

by:missq
ID: 1249464
Thanks for the "pointer" to Vicky's question!!!
0

Featured Post

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
libcurl and C++ - Post JSON Data 8 1,064
Which checksum is this? 7 136
Adjust Mfcapp 29 154
An API detour question 7 65
Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

708 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now