Answer to Question #233312 in C for Arup

Question

Write a menu driven program to perform the following operations in a double linked list by

using suitable user defined functions for each case.

a) Traverse the list forward

b) Traverse the list backward

c) Check if the list is empty

d) Insert a node at the certain position (at beginning/end/any position)

e) Delete a node at the certain position (at beginning/end/any position)

f) Delete a node for the given key

g) Count the total number of nodes

h) Search for an element in the linked list

Verify & validate each function from main method.

Answer 1

 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX 5 void primarymenu(); void secondarymenu(); struct Vertex { char label; bool visited; }; typedef struct node { struct node *next; int vertex; }node; node *G[20]; int visited[20]; char listver[MAX]; //stack variables int stack[MAX]; int top = -1; //graph variables //array of vertices struct Vertex* lstVertices[MAX]; //adjacency matrix int adjMatrix[MAX][MAX]; //vertex count int vertexCount = 0; //stack functions void push(int item) { stack[++top] = item; } int pop() { return stack[top--]; } int peek() { return stack[top]; } bool isStackEmpty() { return top == -1; } //graph functions //add vertex to the vertex list void addVertex(char label) { struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex)); vertex->label = label; vertex->visited = false; lstVertices[vertexCount++] = vertex; } //add edge to edge array void addEdge(int start,int end) { adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; } //display the vertex void displayVertex(int vertexIndex) { printf("%c ",lstVertices[vertexIndex]->label); } //get the adjacent unvisited vertex int getAdjUnvisitedVertex(int vertexIndex) { int i; for(i = 0; i < vertexCount; i++) { if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) { return i; } } return -1; } void depthFirstSearch() { int i; //mark first node as visited lstVertices[0]->visited = true; //display the vertex displayVertex(0); //push vertex index in stack push(0); while(!isStackEmpty()) { //get the unvisited vertex of vertex which is at top of the stack int unvisitedVertex = getAdjUnvisitedVertex(peek()); //no adjacent vertex found if(unvisitedVertex == -1) { pop(); } else { lstVertices[unvisitedVertex]->visited = true; displayVertex(unvisitedVertex); push(unvisitedVertex); } } //stack is empty, search is complete, reset the visited flag for(i = 0;i < vertexCount;i++) { lstVertices[i]->visited = false; } } void insert(int vi,int vj) { node *p,*q;     //acquire memory for the new node       q=(node*)malloc(sizeof(node)); q->vertex=vj; q->next=NULL; //insert the node in the linked list number vi if(G[vi]==NULL) G[vi]=q; else { //go to end of the linked list p=G[vi];                 while(p->next!=NULL)         p=p->next; p->next=q; } } void DFS(int i) { node *p;      printf("%c\t",listver[i]); p=G[i]; visited[i]=1; while(p!=NULL) { i=p->vertex;        if(!visited[i]) DFS(i); p=p->next; } } void secondarymenuadjmat() { char op; char val; int estart,efinal; for(;;) { printf("*****************Secondary Menu*************************\n"); printf("1.Insert node\n"); printf("2.InsertEdge\n"); printf("3.Depth-First Traversal\n"); printf("4.Go back to the Main Menu\n"); printf("Enter your choice(value between 1-4)\n"); scanf("%c",&op); switch(op) { case '1':printf("Enter the node to be inserted\n"); scanf(" %c",&val); addVertex(val); break; case '2':printf("Enter the edge to be inserted\n"); scanf("%d%d",&estart,&efinal); addEdge(estart,efinal); break; case '3':printf("Depth First Search: "); depthFirstSearch(); printf("\n"); break; case '4':primarymenu(); break; } } } void secondarymenuadjlist() { char op; char val; int vi,vj,verind=0; for(;;) { printf("*****************Secondary Menu*************************\n"); printf("1.Insert node\n"); printf("2.InsertEdge\n"); printf("3.Depth-First Traversal\n"); printf("4.Go back to the Main Menu\n"); printf("Enter your choice(value between 1-4)\n"); scanf(" %c",&op); switch(op) { case '1':printf("Enter the node to be inserted\n"); scanf(" %c",&val); listver[verind]=val; visited[verind]=0; G[verind]=NULL; verind++; break; case '2': printf("Enter an edge(u,v):");                          scanf("%d%d",&vi,&vj);                          insert(vi,vj);                          break; case '3':printf("Depth First Search: "); DFS(0); printf("\n"); break; case '4':primarymenu(); break; } } } void primarymenu() { int ch; printf("*****************Primary Menu*************************\n"); printf("Choose the fundamental structure for building a graph\n"); for(;;) { printf("1.Building a graph using adjacency Matrix\n"); printf("2.Building a graph using adjacency List\n"); printf("3.Exit\n"); printf("Enter your choice(value between 1-3)\n"); scanf("%d",&ch); switch(ch) { case 1: secondarymenuadjmat(); break; case 2: secondarymenuadjlist(); break; case 3: exit(1); break; } } } int main() { int i, j,ch; for(i = 0; i < MAX; i++) // set adjacency { for(j = 0; j < MAX; j++) // matrix to 0 adjMatrix[i][j] = 0; primarymenu(); return 0; }