Templates intHeap.c: /** * The functions in this module implement a Heapdata str

Question

Templates

intHeap.c:

/**
* The functions in this module implement a Heapdata structure
* of integers.
*/

/**
* heapDelete() removes the biggest integer in the heap and returns it.
*
*/

int heapDelete()
{
return 0; //A dummy return statement
}

/**
* addHeap(thing2add) adds the "thing2add" to the Heap.
*
*/
void addHeap(int thing2add)
{
}

/**
* heapSize() returns the number of items in the Heap.
*
*/
int heapSize()
{
return 0; //A dummy return statement
}

-----------------------------------------------------------------------------

intHeap.c

/**
* The functions in this module implement a Stack data structure
* of integers. (Note that chars are also integers so this
* integer Stack can be used for chars as well.)
*
* NOTE: the stack is implemented as a fixed size array (size = 100).
* Consequently, no more than 100 integers can be pushed onto
* the Stack at any given time.
*/

// Implementation hints:
// The 3 functions--push, pop and isEmpty--share information
// about the array used to implement the stack and the index
// of the "top" of the stack.
//
// You may want to make these variables global...
// ...but that would
// be a mistake (because anyone using the module would have
// to ensure that they did not use global variables with the
// same names).
//
// An alternative in C is a "static global".
// If a global variable is qualified as "static", it is global only
// within the source code file where it is declared.
// In parituclar, it cannot conflict with any other global variable.
//
// RECOMMENDATION:
// Uncomment the following 2 lines and use these static globals!
//static int top = 0;
//static int stack[100];

/**
* pop() removes the top integer on the stack and returns it.
*
* If pop() is attempted on an empty stack, an error message
* is printed to stderr and the value -1 (minus one) is returned.
*/

int pop()
{
return 0; //A dummy return statement
}

/**
* push(thing2push) adds the "thing2push" to the top of the stack.
*
* If there is no more space available on the Stack, an error
* message is printed to stderr.
*/
void push(int thing2push)
{
}

/**
* isEmpty() returns a non-zero integer (not necessarily 1) if the
* stack is empty; otherwise, it returns 0 (zero).
*
*/
int isEmpty()
{
return 0; //A dummy return statement
}

------------------------------------------------------------------------------------------

main.c

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
extern int pop();
extern void push(int);

int main(int argc, char * argv[])
{
int value;
while (scanf("%d ", &value) != EOF) {
fprintf(stderr, "READING INPUT: %d ", value);
//
  
  
  
}
exit(0);
}

----------------------------------------------------------------------------------

Can you please help me with this at least a part of it?

Theory: XML tree representation The XML language is a textual encoding of a tree data structure. The first start-tag matches the last end-tag and represents the root of the tree Everything between these tags represent the root's children (which may be empty or be trees). The table below gives some examples. Description Tree with root node only XML Tree with root node and 1 child Tree with root node and 3 children Root with 2 children, 2nd child has 1 child node> Knode> Node identification The XML tree description above does not include information about the nodes. This can be fixed by allowing start-tags to have additional information associated with them. For example, a tree with a single root node with the information "foo" associated with it can be expressed in XML as . Similarly, a tree with a root (value 5) and two children (values 2 and 7) carn be expressed in XML as: node id-"5"> (Note: this is also a valid Binary Search Tree.)

Explanation / Answer

main.c

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
extern int pop();
extern void push(int);
extern void addHeap(int);
extern void printHeap(int);
extern void buildMaxHeap();
extern int isEmpty();
extern int heapSize();
extern int heapDelete();

int main(int argc, char * argv[]){
   int value,temp;
   while (scanf("%d", &value) != EOF) {
        fprintf(stderr, "READING INPUT: %d ", value);
           addHeap(value);
   }
   buildMaxHeap();
   printHeap(1);
   printf(" ");
   printf(" The Sorted Numbers(Descending): ");
   while(heapSize()>1){
       temp=heapDelete();
       printf("%d ",temp);
       push(temp);
   }
   printf("The Sorted Numbers(Ascending): ");
   while(isEmpty()!=1){
       printf("%d ",pop());
   }
   printf(" ");
   exit(0);
}

intHeap.c

#include <stdio.h>

int heapDelete();
void addHeap(int);
int heapSize();
void heapify(int);
void printHeap(int);
void buildMaxHeap();

/**
* The functions in this module implement a Heapdata structure
* of integers.
*/

static int heap[100];
static int last=1;

/**
* heapDelete() removes the biggest integer in the heap and returns it.
*
*/

int heapDelete(){
   int max=heap[1];
   heap[1]=heap[last--];
   heapify(1);
   return max;
}

/**
* addHeap(thing2add) adds the "thing2add" to the Heap.
*
*/
void addHeap(int thing2add){
   if(last>100){
       fprintf(stderr," Heap Overflow ");
       return;
   }
   heap[last]=thing2add;
   int i=last;
   int parent=i/2;
   while(parent>0 && heap[parent]<thing2add){
       heap[i]=heap[parent];
       heap[parent]=thing2add;
       i=parent;
       parent=i/2;
   }
   last++;
}

/**
* heapSize() returns the number of items in the Heap.
*
*/
int heapSize(){
return last; //A dummy return statement
}

void heapify(int i){
   int temp;
   int largest;  
   int left=2*i;
   int right=2*i+1;
  
   if(left<=heapSize() && heap[i]<heap[left]){
       largest=left;
   }else{
       largest=i;
   }
   if(right<=heapSize() && heap[largest]<heap[right]){
       largest=right;
   }

   if(largest!=i){
       temp=heap[i];
       heap[i]=heap[largest];
       heap[largest]=temp;
       heapify(largest);
   }
}

void printHeap(int position){
   int next_position;
   printf("<node id="%d">",heap[position]);
   next_position=position*2;
   if(next_position<=heapSize()){
       printHeap(next_position);
   }

   next_position=position*2+1;
   if(next_position<=heapSize()){
       printHeap(next_position);
   }
   printf("< ode>");
}

void buildMaxHeap(){
   int j;
   for(j=heapSize()/2;j>=1;j--){
       heapify(j);
   }
}

intStack.c

#include <stdio.h>

int pop();
void push(int);
int isEmpty();

static int top = 0;
static int stack[100];

/**
* pop() removes the top integer on the stack and returns it.
*
* If pop() is attempted on an empty stack, an error message
* is printed to stderr and the value -1 (minus one) is returned.
*/

int pop(){
   if(isEmpty()==1){
       fprintf(stderr," Stack Underflow ");
       return -1;
   }else{
       return stack[--top];
   }
}

/**
* push(thing2push) adds the "thing2push" to the top of the stack.
*
* If there is no more space available on the Stack, an error
* message is printed to stderr.
*/
void push(int thing2push){
   if(top==100){
       fprintf(stderr," Stack Overflow ");
   }else{
       stack[top++]=thing2push;
   }
}

/**
* isEmpty() returns a non-zero integer (not necessarily 1) if the
* stack is empty; otherwise, it returns 0 (zero).
*
*/
int isEmpty(){
return (top==0) ? 1 : 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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