answer in C Step 1: Define your Tree data structure Define the tree struct and relevant functions in an appropriately named .h file, such as tree.h. Recall, with Trees, every node in a tree is also a tree. So, like a linked list, the root of the tree is just a TreeNode, and has children that are TreeNodes (or whatever you want to call them). CreateTreeNode(char* path, char* name) AddChild(TreeNode* root, char* path, char* name) DestroyTreeNode(TreeNode*) Now that you've defined a tree node, use that to implement a Queue that holds TreeNodes. The structure and functions should be declared in a .h file, and implemented in a .c file. You'll need the following operations: Enqueue(TreeNode*) Dequeue(TreeNode*) Depending on how you implement it, you may need to include Create() and Destroy() functions. However, as noted above, if you want to just use an array defined globally, that is fine for this assignment. Implement a Stack that holds TreeNodes. The structure and functions should be declared in a .h file, and implemented in a .c file. You'll need the following operations: Push(TreeNode*) Pop(TreeNode*) Again, depending how you implement it, you may need to include Create() and Destroy() functions, but you can also utilize a globally defined array. To build this tree, the algorithm is: Create a TreeNode representing the directory you are starting at Put that root TreeNode in a queue While there are TreeNodes left in the queue, get the next TreeNode and do the following: Add all the files in the directory represented by the current tree node to that tree node If any of the files (now children) are actually directories instead of files, add that child tree node to the queue to be handled later. Step 5: Print out the Tree Now, you'll do a depth-first search to print out the tree. The algorithm looks something like this: Put the root TreeNode into your stack. While there are more TreeNodes in your stack, get the next TreeNode and do the following: Add all the children of the TreeNode to the stack Print out the current TreeNode /////////////////////////////////////////////////////////// start code - stack.c typedef struct stack{ int stack[5];//kStackSize]; int head; } Stack; //typedef struct stack Stack; const int kStackSize = 5; void push(Stack *s, int n) { if ((*s).head < kStackSize) { s->stack[s->head++] = n; } // return s; // No more call by value, so not returning. } int pop(struct stack s) { if (s.head > 0) { return s.stack[--s.head]; } return -1; // sentinel value } int peek(struct stack s) { if (s.head > 0) { return s.stack[s.head - 1]; } return -1; // Stack is empty } void PrintStack(struct stack s){ printf("%p\n", &s); for (int i = 0; i < kStackSize; i++) { printf("stack[%d]: %d\n", i, s.stack[i]); } int main() { printf("%d\n", sizeof(Stack)); printf("%d\n", sizeof(int)); struct stack s1; s1.head = 0; printf("%p\n", &s1); PrintStack(s1); // s1 = push(s1, 1); push(&s1, 1); PrintStack(s1); // s1 = push(s1, 2); // no more call by value push(&s1, 2); printf("Peek: %d\n", peek(s1)); printf("Popped: %d\n",pop(s1)); printf("Peek: %d\n", peek(s1)); PrintStack(s1); } ////////////////////////////////////////////////////////////////// start code - queue1.c #include #include #define SIZE 5 // Defining a queue based on an array. struct queueOfCustomers{ char* customers[SIZE]; int front; int rear; }; typedef struct queueOfCustomers QueueOfCustomers; // Queue Operation Prototypes char* dequeue(QueueOfCustomers*); void enqueue(char* newBook, QueueOfCustomers*); char* front(QueueOfCustomers*); char* back(QueueOfCustomers*); QueueOfCustomers* create(); void destroy(QueueOfCustomers*); // Queue Operation Implementation char* dequeue(QueueOfCustomers* queue){ // queue->front; return (queue->customers[queue->front--]); } void enqueue(char* newBook, QueueOfCustomers* queue){ if (queue->rear == 0){ // Queue is full!!! printf("Can't add another customer-- the queue is full!"); } else{ // queue->rear--; queue->customers[--queue->rear] = newBook; } } int size(QueueOfCustomers* queue){ return(queue->front - queue->rear ); } char* front(QueueOfCustomers* queue){ } char* back(QueueOfCustomers* queue){ void destroy(QueueOfCustomers* queue){ } void printQueue(QueueOfCustomers* customers){ printf("Printing the queue of customers: \n"); int i; for (i=SIZE; i>=0; i--){ if (i == customers->front ){ printf("F------>"); } if (i < SIZE){ printf("\t[%d: %25s ]", i, customers->customers[i]); } if (i == customers->rear){ printf("<------R"); } printf("\n"); } int main(){ QueueOfCustomers *queue = create(); printQueue(queue); printf("\n\n"); enqueue("Harry Potter", queue); enqueue("War and Peace", queue); enqueue("Hunger Games", queue); enqueue("There's a Right Way", queue); printQueue(queue); printf("\nThe next customer we're helping: %s\n", dequeue(queue)); printf("\n\n"); printQueue(queue); printf("\nThe next customer we're helping: %s\n", dequeue(queue)); printf("\n\n"); printQueue(queue); enqueue("Diary of a Wimpy Kid", queue); printQueue(queue); printQueue(queue); enqueue("The Goldfinch", queue); printf("\n\n The size of the queue: %d\n\n", size(queue)); destroy(queue);
answer in C
Step 1: Define your Tree data structure
Define the tree struct and relevant functions in an appropriately named .h file, such as tree.h. Recall, with Trees, every node in a tree is also a tree. So, like a linked list, the root of the tree is just a TreeNode, and has children that are TreeNodes (or whatever you want to call them).
- CreateTreeNode(char* path, char* name)
- AddChild(TreeNode* root, char* path, char* name)
- DestroyTreeNode(TreeNode*)
Now that you've defined a tree node, use that to implement a Queue that holds TreeNodes. The structure and functions should be declared in a .h file, and implemented in a .c file.
You'll need the following operations:
- Enqueue(TreeNode*)
- Dequeue(TreeNode*)
Depending on how you implement it, you may need to include Create() and Destroy() functions. However, as noted above, if you want to just use an array defined globally, that is fine for this assignment.
Implement a Stack that holds TreeNodes.
The structure and functions should be declared in a .h file, and implemented in a .c file.
You'll need the following operations:
- Push(TreeNode*)
- Pop(TreeNode*)
Again, depending how you implement it, you may need to include Create() and Destroy() functions, but you can also utilize a globally defined array.
To build this tree, the
- Create a TreeNode representing the directory you are starting at
- Put that root TreeNode in a queue
- While there are TreeNodes left in the queue, get the next TreeNode and do the following:
- Add all the files in the directory represented by the current tree node to that tree node
- If any of the files (now children) are actually directories instead of files, add that child tree node to the queue to be handled later.
Step 5: Print out the Tree
Now, you'll do a depth-first search to print out the tree. The algorithm looks something like this:
- Put the root TreeNode into your stack.
- While there are more TreeNodes in your stack, get the next TreeNode and do the following:
- Add all the children of the TreeNode to the stack
- Print out the current TreeNode
///////////////////////////////////////////////////////////
start code - stack.c
typedef struct stack{
int stack[5];//kStackSize];
int head;
} Stack;
//typedef struct stack Stack;
const int kStackSize = 5;
void push(Stack *s, int n) {
if ((*s).head < kStackSize) {
s->stack[s->head++] = n;
}
// return s; // No more call by value, so not returning.
}
int pop(struct stack s) {
if (s.head > 0) {
return s.stack[--s.head];
}
return -1; // sentinel value
}
int peek(struct stack s) {
if (s.head > 0) {
return s.stack[s.head - 1];
}
return -1; // Stack is empty
}
void PrintStack(struct stack s){
printf("%p\n", &s);
for (int i = 0; i < kStackSize; i++) {
printf("stack[%d]: %d\n", i, s.stack[i]);
}
int main() {
printf("%d\n", sizeof(Stack));
printf("%d\n", sizeof(int));
struct stack s1;
s1.head = 0;
printf("%p\n", &s1);
PrintStack(s1);
// s1 = push(s1, 1);
push(&s1, 1);
PrintStack(s1);
// s1 = push(s1, 2); // no more call by value
push(&s1, 2);
printf("Peek: %d\n", peek(s1));
printf("Popped: %d\n",pop(s1));
printf("Peek: %d\n", peek(s1));
PrintStack(s1);
}
//////////////////////////////////////////////////////////////////
start code - queue1.c
#include <stdio.h>
#include <stdlib.h>
#define SIZE 5
// Defining a queue based on an array.
struct queueOfCustomers{
char* customers[SIZE];
int front;
int rear;
};
typedef struct queueOfCustomers QueueOfCustomers;
// Queue Operation Prototypes
char* dequeue(QueueOfCustomers*);
void enqueue(char* newBook, QueueOfCustomers*);
char* front(QueueOfCustomers*);
char* back(QueueOfCustomers*);
QueueOfCustomers* create();
void destroy(QueueOfCustomers*);
// Queue Operation Implementation
char* dequeue(QueueOfCustomers* queue){
// queue->front;
return (queue->customers[queue->front--]);
}
void enqueue(char* newBook, QueueOfCustomers* queue){
if (queue->rear == 0){
// Queue is full!!!
printf("Can't add another customer-- the queue is full!");
}
else{
// queue->rear--;
queue->customers[--queue->rear] = newBook;
}
}
int size(QueueOfCustomers* queue){
return(queue->front - queue->rear );
}
char* front(QueueOfCustomers* queue){
}
char* back(QueueOfCustomers* queue){
void destroy(QueueOfCustomers* queue){
}
void printQueue(QueueOfCustomers* customers){
printf("Printing the queue of customers: \n");
int i;
for (i=SIZE; i>=0; i--){
if (i == customers->front ){
printf("F------>");
}
if (i < SIZE){
printf("\t[%d: %25s ]", i, customers->customers[i]);
}
if (i == customers->rear){
printf("<------R");
}
printf("\n");
}
int main(){
QueueOfCustomers *queue = create();
printQueue(queue);
printf("\n\n");
enqueue("Harry Potter", queue);
enqueue("War and Peace", queue);
enqueue("Hunger Games", queue);
enqueue("There's a Right Way", queue);
printQueue(queue);
printf("\nThe next customer we're helping: %s\n", dequeue(queue));
printf("\n\n");
printQueue(queue);
printf("\nThe next customer we're helping: %s\n", dequeue(queue));
printf("\n\n");
printQueue(queue);
enqueue("Diary of a Wimpy Kid", queue);
printQueue(queue);
printQueue(queue);
enqueue("The Goldfinch", queue);
printf("\n\n The size of the queue: %d\n\n", size(queue));
destroy(queue);
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
