Answered: 1. Create a generic stack and queue…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

(my question and explanation is in one of the images)

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<assert.h>

typedef struct {

void* arr;

int totalSize;

int front;

int rear;

int elemSize;

void(*freefunc)(void*);

}queue;

void queueConstruct(queue* q, int elemSize, void(*freefunc)(void*)) {

q->elemSize = elemSize;

q->freefunc = freefunc;

q->totalSize = 5;

q->arr = malloc(q->totalSize * q->elemSize);

assert(q->arr != NULL);

q->front = -1;

q->rear = -1;

}

void queueDestruct(queue* q) {

if (q->freefunc != NULL) {

for (int i = 0; i < q->rear + 1; i++) {

q->freefunc((char*)q->arr + i * q->elemSize);

}

free(q->arr);

}

void freeString(void* pos) {

free(*(char**)pos);

}

void enqueue(queue* q, void* val) {

if (q->rear == q->totalSize - 1) {

q->totalSize *= 2;

q->arr = realloc(q->arr, q->totalSize * q->elemSize);

assert(q->arr != NULL);

}

q->rear++;

void* posiQueue = (char*)q->arr + q->rear * q->elemSize;

memcpy(posiQueue, val, q->elemSize);

}

int isEmpty(queue* q) {

return q->front == q->rear;

}

void dequeue(queue* q) {

assert(!isEmpty(q));

q->front++;

}

void frontQueue(queue* q, void* copy) {

assert(!isEmpty(q));

void* source = (char*)q->arr + (q->front + 1) * q->elemSize;

memcpy(copy, source, q->elemSize);

}

//Stack

typedef struct {

void* arr;

int elemSize;

int usedLength;

int totalLength;

void(*freefunc)(void*);

}stack;

void stackConstruct(stack* s, int elemSize, void(*freefunc)(void*)) {

s->freefunc = freefunc;

s->elemSize = elemSize;

s->usedLength = 0;

s->totalLength = 10;

s->arr = malloc(10 * s->elemSize);

assert(s->arr != NULL);

}

void stackDestruct(stack* s) {

if (s->freefunc != NULL) {

for (int i = 0; i < s->usedLength; i++)

s->freefunc((char*)s->arr + i * s->elemSize);

}

free(s->arr);

}

void freeStringStack(void* pos) {

free(*(char**)pos);

}

void push(stack* s, void* val) {

if (s->usedLength == s->totalLength) {

s->totalLength *= 2;

s->arr = realloc(s->arr, s->totalLength * s->elemSize);

assert(s->arr != NULL);

}

void* posStack = (char*)s->arr + s->usedLength * s->elemSize;

memcpy(posStack, val, s->elemSize);

s->usedLength++;

}

void top(stack* s, void* copy) {

assert(s->usedLength > 0);

void* source = (char*)s->arr + (s->usedLength - 1) * s->elemSize;

memcpy(copy, source, s->elemSize);

}

void pop(stack* s) {

assert(s->usedLength > 0);

s->usedLength--;

}

int isEmptyStack(stack* s) {

return s->usedLength == 0;

}

int main() {

queue q;

queueConstruct(&q, sizeof(int), NULL);

int visited[10] = { 0 };

//ABC

int graphFigure[10][10] = { {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 0, 1, 0, 0, 1, 0, 0}, {0, 1, 0, 1, 0, 0, 0, 0, 1, 1},

// DEFG

{1, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 1, 1, 1, 0, 0} , {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 1, 0, 0, 1, 0, 0},

// HIJ

{0, 1, 0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0}

};

/*int graphFigure[10][10] = { {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, {1,0,1, 0, 1, 0, 0}, {1,1,0, 1,

0, 0, 0},

{0,0,1, 0, 0, 0, 0}, {0,1,0, 0, 0, 1, 0} , { 0,1,1, 0, 1, 0, 1 }, { 0,0,0, 0,

0, 1, 0 }

};

int i = 0;

char c = 'A';

printf("%c ", c);

visited[i] = 1;

enqueue(&q, &i);

while (!isEmpty(&q)) {

int node;

frontQueue(&q, &node);

dequeue(&q);

for (int j = 0; j < 10; j++) {

if (graphFigure[node][j] == 1 && visited[j] == 0) {

switch (j){

case 0: c = 'A';

break;

case 1: c = 'B';

break;

case 2: c = 'C';

break;

case 3: c = 'D';

break;

case 4: c = 'E';

break;

case 5: c = 'F';

break;

case 6: c = 'G';

break;

case 7: c = 'H';

break;

case 8: c = 'I';

break;

case 9: c = 'J';

break;

default: c = 'd';

break;

}

printf("%c ", c);

visited[j] = 1;

enqueue(&q, &j);

}

printf("\n");

queueDestruct(&q);

printf("\n\n");

stack s;

stackConstruct(&s, sizeof(int), NULL);

int visited1[10] = { 0 };

//ABC

int graphFigure1[10][10] = { {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 0, 1, 0, 0, 1, 0, 0}, {0, 1, 0, 1, 0, 0, 0, 0, 1, 1},

// DEFG

{1, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 1, 1, 1, 0, 0} , {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 1, 0, 0, 1, 0, 0},

// HIJ

{0, 1, 0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0}

};

int i1 = 0;

char c1 = 'A';

printf("%c ", c1);

visited1[i] = 1;

push(&s, &i1);

while (!isEmptyStack(&s)) {

int node;

top(&s, &node);

pop(&s);

for (int j = 0; j < 10; j++) {

if (graphFigure1[node][j] == 1 && visited1[j] == 0) {

switch (j) {

case 0: c1 = 'A';

break;

case 1: c1 = 'B';

break;

case 2: c1 = 'C';

break;

case 3: c1 = 'D';

break;

case 4: c1 = 'E';

break;

case 5: c1 = 'F';

break;

case 6: c1 = 'G';

break;

case 7: c1 = 'H';

break;

case 8: c1 = 'I';

break;

case 9: c1 = 'J';

break;

default: c1 = 'd';

break;

}

printf("%c ", c1);

visited[j] = 1;

push(&s, &j);

}

printf("\n");

stackDestruct(&s);

return 0;

}

I'm working on a question regarding the implementation of graph traversal algorithms in C. I'm not sure if the generic queue and depth-first search parts of my assignment are outputting the correct order of elements based on the diagram provided. The issue seems to be with the stack and breadth-first search implementation, as it repeatedly outputs the same elements endlessly.

The graph is represented as a 10x10 adjacency matrix, where each row corresponds to a vertex and the columns indicate connections with 1s (connected) and 0s (not connected). For instance, for vertex B, the row {1, 0, 1, 0, 1, 0, 0, 1, 0, 0} means B is connected to vertices A, C, E, and H.

I've included my code for reference, written in C.

**Exercise Description:**

1. **Create a Generic Stack and Queue**
- Implement a generic stack and a generic queue. Write the code in the C programming language.

2. **Graph Traversal Tasks**
- Use the following graph for the subsequent tasks. Write the code in C.

**Graph Structure:**
- The graph consists of 10 vertices labeled A to J.
- The connections between vertices are as follows:
- A is connected to D and B.
- B is connected to A, E, C, and G.
- C is connected to B, J, and I.
- D is connected to A.
- E is connected to B, F, and G.
- F is connected to E.
- G is connected to B, E, and H.
- H is connected to G.
- I is connected to C.
- J is connected to C.

3. **Traversal Techniques**
- (i) Implement Depth First Search (DFS) using the generic stack you have created. Start with vertex A.
- (ii) Implement Breadth First Search (BFS) using the generic queue you have created. Start with vertex A.

These tasks will equip you with the skills to work with data structures and algorithms, which are fundamental in computer science. By implementing these, you will gain practical experience in navigating and manipulating graph structures.

Expert Solution

Step 1: Scope of the Question

The scope of the question is to provide a complete explanation and implementation of generic stack and queue data structures in the C programming language. The question asks for code examples, explanations, and a step-by-step breakdown of how to create these data structures using linked lists for flexibility. It also covers demonstrating the usage of these data structures by pushing and popping elements in the stack and enqueuing and dequeuing elements in the queue, including different data types.

The question is specifically focused on the following aspects:

Implementing a generic stack data structure in C.
2. Implementing a generic queue data structure in C.
3. Providing code examples for creating and using these data structures.
4. Offering a step-by-step explanation of the code.

Generic Stack:

A stack is a data structure that follows the last-in-first-out (LIFO) principle, meaning the most recently added element is the first to be removed.
A generic stack allows elements of any data type to be pushed onto the stack and popped off the stack without the need to specify the data type in advance.
Generic stacks are useful for a wide range of applications, such as managing function call states, parsing expressions, and reversing sequences of data.

Generic Queue:

A queue is a data structure that follows the first-in-first-out (FIFO) principle, meaning the first element added is the first to be removed.
A generic queue allows elements of any data type to be enqueued (added to the back of the queue) and dequeued (removed from the front of the queue) without requiring prior knowledge of the data type.
Generic queues are commonly used in scenarios like task scheduling, order processing, and managing data flows where the order of processing is critical.

Both generic stack and queue data structures are highly versatile and enable programmers to work with various data types in a consistent and reusable way, simplifying code and making it adaptable to different use cases. This flexibility is particularly valuable in programming languages that support generics or templates, as it allows developers to create highly adaptable and reusable code.

Note:

"Since you have posted a multiple questions , we will provide the solution only to the first question as per our Q&A guidelines. Please repost the remaining questions separately."

Step by step

Solved in 6 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

1. Create a generic stack and queue respectively. Write code in C.