//PART A: Complete the code below (do not use any standard libraries). //PART B

Question

//PART A: Complete the code below (do not use any standard libraries). //PART B For each public method, provide a big-oh bound on the worst case //run-time for that method in terms of the number of items 'n' contained in //the data structure at the time of the method call Justify your bound in each case class priorityQueueLL private: class node public: //put what you need here.. public: priorityQueue () //your code here priorityqueue () /your code here //return true if empty, false if not bool empty () /your code here //add item void insert (int x) /your code here //remove and return smallest item int extractMin () /your code here

Explanation / Answer

001 #include 002 #include 003 #include 004 005 struct node 006 { 007     int number; 008     int priority; 009     struct node *link; 010 } *front = NULL; 011 012 013 void insert(int tempNum, int tempPriority) 014 { 015     struct node *temp; 016     struct node *queue; 017 018     temp = (struct node *)malloc(sizeof(struct node)); 019 020     temp -> number = tempNum; 021     temp -> priority = tempPriority; 022 023     if(front == NULL || tempPriority > front -> priority) 024     { 025         temp -> link = front; 026         front = temp; 027     }else 028         { 029             queue = front; 030             while(queue -> link != NULL && queue -> link -> priority link; 032             temp -> link = queue -> link; 033             queue -> link = temp;        034         } 035 } 036 037 void pop() 038 { 039     struct node *temp; 040 041     if(front == NULL) 042     { 043         printf("-1"); //Nothing in the queue 044     }else 045         { 046             temp = front; 047             printf("%d ",temp -> number); //Printing number being popped from queue 048             front = front -> link; 049             free(temp); 050         } 051 052 } 053 054 void display() 055 { 056     struct node *ptr; 057       058     ptr = front; 059       060     if (front == NULL) 061     { 062         printf("Queue is empty"); 063     }else 064         { 065             printf("Queue is: "); 066             printf("Priority item "); 067             while(ptr != NULL) 068             { 069                 printf("%d %d ", ptr -> number, ptr -> priority); 070                 ptr = ptr -> link; 071             } 072         } 073 } 074 075 main() 076 { 077     char s[20]; //Stores the line to be read 078     char c; //Checks first char (I or P) 079     int current = 0; 080 081     int tempNum, tempPriority; 082 083     while(1) 084     { 085         c=''; 086         scanf("%c",&c); 087 088         if (c=='P') 089         { 090             pop(); 091             scanf("%s ",s); 092             continue; 093         } 094         else 095 096         if (c=='I') 097         { 098             scanf("%s %d %d ",s,&tempNum, &tempPriority); 099             insert(tempNum, tempPriority); 100             continue; 101         } 102         else 103         break; 104     } 105 106     display(); 107 108 }

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.