Please complete the void remVertex(Vertex*& vHead, char label); . Be sure to use
ID: 3917227 • Letter: P
Question
Please complete the void remVertex(Vertex*& vHead, char label);. Be sure to use the function header as written.
Remember, that you have to remove all the incoming and outgoing arcs in the data structure along with the vertex itself. Feel free to use the remArc function we wrote in the video to make your life easier. Think about what parameters it needs as input and how you might use it in the function.
For completeness's sake, also write the Vertex* findVertex(Vertex* vHead, char key); function. As mentioned in the video, the code itself has already been written and can be copied from other functions. For extra credit, replace that code in the other functions with this search function.
#IFNDEF VERTEX_H
#DEFINE VERTEX_H
struct Vertex;
struct Arc;
struct Vertex{
char data;
Vertex* vNext;
Arc*ahead;
};
struct Arc
{
Vertex* dest;
Arc* aNext;
};
void addVertex(Verex* vhead, char label);
void rmVertex(Vertex* vhead, char label); /// to remove Vertex
vod addArc(Vertex *vHead, char from, char to);
void rmArc(Vertex * vHead, char from, char to);
Vertex* findVertex(Vertex* vHead, char key);
void printGraph(Vertex* vHead);
#ENDIF
void rmArc(Vertex *vHead, char from, char to)
{
Vertex* fromVer = vhead;
while(fromVer != nullptr && fromVer-> data < from)
{
fromVer = fromVer->vNext;
}
if(fromVer == nullptr || fromVer-> data > from)
{
cout << "Starting vertex is not in the list. ";
return;
}
Arc* curArc = fromVer->aHead;
if (curArc == nullptr && curArc -> dest-> data > to)
{
cout << "There is no connection between these vertices ";
return;
}
while(curArc->aNext != nullptr && curArc -> dest -> data < to)
{
curArc = curArc -> aNext;
}
if(curArc ->aNext == nullptr || curArc-> aNext-> dest-> data > to){
cout << "There is no connection: ";;
return;
}
else{
Arc* dltPtr = curArc -> aNext;
curArc -> aNext = curArc -> aNext -> aNext;
delete dltPtr;
}
}
Explanation / Answer
#include "vertex.h"
#include<iostream>
using namespace std;
void rmVertex(Vertex * vhead, char label)
{
Vertex* curr = vhead;
//We used the rmArc to remove arc from each vertex
while (curr != nullptr)
{
rmArc(curr, curr->data, curr->ahead->dest->data);
curr = curr->vNext;
}
}
void rmArc(Vertex *vHead, char from, char to)
{
Vertex* fromVer = vHead;
while (fromVer != nullptr && fromVer->data < from)
{
fromVer = fromVer->vNext;
}
if (fromVer == nullptr || fromVer->data > from)
{
cout << "Starting vertex is not in the list. ";
return;
}
Arc* curArc = fromVer->ahead;
if (curArc == nullptr && curArc->dest->data > to)
{
cout << "There is no connection between these vertices ";
return;
}
while (curArc->aNext != nullptr && curArc->dest->data < to)
{
curArc = curArc->aNext;
}
if (curArc->aNext == nullptr || curArc->aNext->dest->data > to) {
cout << "There is no connection: ";;
return;
}
else {
Arc* dltPtr = curArc->aNext;
curArc->aNext = curArc->aNext->aNext;
delete dltPtr;
}
}
Vertex * findVertex(Vertex * vHead, char key)
{
Vertex* fromVer = vHead;
while (fromVer != nullptr && fromVer->data < key)
{
fromVer = fromVer->vNext;
}
if (fromVer == nullptr || fromVer->data > key)
{
cout << "Starting vertex is not in the list. ";
return nullptr;
}
if (fromVer != nullptr || fromVer->data == key)
{
return fromVer;
}
Arc* curArc = fromVer->ahead;
if (curArc == nullptr && curArc->dest->data > key)
{
cout << "There is no connection between these vertices ";
return nullptr;
}
if (curArc == nullptr && curArc->dest->data == key)
{
return curArc->dest;
}
while (curArc->aNext != nullptr && curArc->dest->data < key)
{
curArc = curArc->aNext;
}
if (curArc->aNext == nullptr || curArc->aNext->dest->data > key) {
cout << "There is no connection: ";;
return nullptr;
}
if (curArc->aNext != nullptr || curArc->aNext->dest->data == key)
{
return curArc->aNext->dest;
}
return nullptr;
}
Test this program with your driver function.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.