Untitled

 avatar
unknown
plain_text
3 years ago
11 kB
4
Indexable
////////////////////////////////////////// any problem , add comment

////////////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
#ifndef QUEUE_H
#define QUEUE_H
#include "dll.h"
#include <iostream>
using namespace std;
template <class T>
class queue {
private:
   DoublyLinkedList<T> *Q;
   float sum;
   int count;
public:
   queue() {
       Q = new DoublyLinkedList<T>;
       sum = 0;
       count = 0;
   }
   ~queue() {
       delete Q;
   }
   void enqueue(T data) {
       count++;
       sum += data;
       Q->addToDLLTail(data);
   }
   T dequeue(void) {
       count--;
       T tmp = Q->deleteFromDLLHead();
       sum -= tmp;
       return tmp;
   }
   T firstElement(void) {
       return Q->firstEl();
   }
   bool isEmpty(void) {
       return Q->isEmpty();
   }
   void Average1(void) {
       cout << "Average = " << sum / count << endl << endl;
   }
};
#endif

////////////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
#ifndef DOUBLY_LINKED_LIST
#define DOUBLY_LINKED_LIST
template<class T>
class DLLNode {
public:
   DLLNode() {
       next = prev = 0;
   }
   DLLNode(const T& el, DLLNode<T> *n = 0, DLLNode<T> *p = 0) {
       info = el; next = n; prev = p;
   }
   T info;
   DLLNode<T> *next, *prev;
};
template<class T>
class DoublyLinkedList {
public:
   DoublyLinkedList() {
       head = tail = 0;
   }
   void addToDLLTail(const T&);
   T deleteFromDLLTail();
   ~DoublyLinkedList() {
       clear();
   }
   bool isEmpty() const {
       return head == 0;
   }
   void clear();
   void setToNull() {
       head = tail = 0;
   }
   void addToDLLHead(const T&);
   T deleteFromDLLHead();
   T& firstEl();
   T* find(const T&) const;
   void print();
   DLLNode<T> *head, *tail;
};
template<class T>
void DoublyLinkedList<T>::addToDLLHead(const T& el) {
   if (head != 0) {
       head = new DLLNode<T>(el, head, 0);
       head->next->prev = head;
   }
   else head = tail = new DLLNode<T>(el);
}
template<class T>
void DoublyLinkedList<T>::addToDLLTail(const T& el) {
   if (tail != 0) {
       tail = new DLLNode<T>(el, 0, tail);
       tail->prev->next = tail;
   }
   else head = tail = new DLLNode<T>(el);
}
template<class T>
T DoublyLinkedList<T>::deleteFromDLLHead() {
   T el = head->info;
   if (head == tail) { // if only one DLLNode on the list;
       delete head;
       head = tail = 0;
   }
   else { // if more than one DLLNode in the list;
       head = head->next;
       delete head->prev;
       head->prev = 0;
   }
   return el;
}
template<class T>
T DoublyLinkedList<T>::deleteFromDLLTail() {
   T el = tail->info;
   if (head == tail) { // if only one DLLNode on the list;
       delete head;
       head = tail = 0;
   }
   else { // if more than one DLLNode in the list;
       tail = tail->prev;
       delete tail->next;
       tail->next = 0;
   }
   return el;
}
template <class T>
T* DoublyLinkedList<T>::find(const T& el) const {
   DLLNode<T> *tmp = head;
   for (; tmp != 0 && !(tmp->info == el); // overloaded ==
       tmp = tmp->next);
   if (tmp == 0)
       return 0;
   else return &tmp->info;
}
template<class T>
T& DoublyLinkedList<T>::firstEl() {
   return head->info;
}
template<class T>
void DoublyLinkedList<T>::clear() {
   for (DLLNode<T> *tmp; head != 0; ) {
       tmp = head;
       head = head->next;
       delete tmp;
   }
}
#endif

////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include "intSLList.h"
IntSLList::~IntSLList() {
   for (IntSLLNode *p; !isEmpty(); ) {
       p = head->next;
       delete head;
       head = p;
   }
}
void IntSLList::addToHead(int el) {
   head = new IntSLLNode(el, head);
   if (tail == 0)
       tail = head;
   size++;
}
void IntSLList::addToTail(int el) {
   if (tail != 0) { // if list not empty;
       tail->next = new IntSLLNode(el);
       tail = tail->next;
   }
   else head = tail = new IntSLLNode(el);
   size++;
}
int IntSLList::GetAt(int x) {
   IntSLLNode *tmp = head;
   for (int i = 1;i<x && tmp != NULL;i++) {
       //cout << tmp->info <<endl;
       tmp = tmp->next;
   }
   return tmp->info;
}
int IntSLList::GetSize() {
   return size;
}
int IntSLList::deleteFromHead() {
   int el = head->info;
   IntSLLNode *tmp = head;
   if (head == tail) // if only one node on the list;
       head = tail = 0;
   else head = head->next;
   delete tmp;
   size--;
   return el;
}
int IntSLList::deleteFromTail() {
   int el = tail->info;
   if (head == tail) { // if only one node on the list;
       delete head;
       head = tail = 0;
   }
   else { // if more than one node in the list,
       IntSLLNode *tmp; // find the predecessor of tail;
       for (tmp = head; tmp->next != tail; tmp = tmp->next);
       delete tail;
       tail = tmp; // the predecessor of tail becomes tail;
       tail->next = 0;
   }
   size--;
   return el;
}
void IntSLList::deleteNode(int el) {
   if (head != 0) // if non-empty list;
       if (head == tail && el == head->info) { // if only one
           delete head; // node on the list;
           head = tail = 0;
       }
       else if (el == head->info) { // if more than one node on the list
           IntSLLNode *tmp = head;
           head = head->next;
           delete tmp; // and old head is deleted;
       }
       else { // if more than one node in the list
           IntSLLNode *pred, *tmp;
           for (pred = head, tmp = head->next; // and a non-head node
               tmp != 0 && !(tmp->info == el);// is deleted;
               pred = pred->next, tmp = tmp->next);
           if (tmp != 0) {
               pred->next = tmp->next;
               if (tmp == tail)
                   tail = pred;
               delete tmp;
           }
       }
}
bool IntSLList::isInList(int el) const {
   IntSLLNode *tmp;
   for (tmp = head; tmp != 0 && !(tmp->info == el); tmp = tmp->next);
   return tmp != 0;
}
void IntSLList::printAll() const {
   for (IntSLLNode *tmp = head; tmp != 0; tmp = tmp->next)
       cout << tmp->info << " ";
   cout << endl;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
#ifndef INTDRGRAPH_H
#define INTDRGRAPH_H
#include <iostream>
#include "intSLList.h"
#include <fstream>
#include <string>
#include "queue.h"
using namespace std;
class intDrGraph {
private:
   bool error;
   IntSLList **listoflist;
   int arraysize;
public:
   intDrGraph(string filename) {

       ifstream file;
       file.open(filename.c_str());
       if (file.is_open() == false) {
           cout << "Couldn't open the file" << endl;
           error = true;
           return;
       }
       else {
           file>> arraysize;
           listoflist = new IntSLList*[arraysize];
           for (int i = 0;i < arraysize;i++) {
               listoflist[i] = new IntSLList();
           }
           int from, to;
           int i = 0;
           while (file.eof() == false) {
               file >> from;
               file >> to;
               listoflist[from - 1]->addToTail(to-1);
           }
       }

   }
   ~intDrGraph() {
       if (error == true) return;
       for (int i = 0;i<arraysize;i++) {
           delete listoflist[i];
       }
       delete[] listoflist;
   }
   void print(void) {
       cout << "\n***printAdjList***\n";
       for (int i = 0;i < arraysize;i++) {
           cout << (i + 1);
           cout << " -> ";
           IntSLList *cur = listoflist[i];
           for (int j = 1;j <= cur->GetSize();j++) {
               cout << (cur->GetAt(j)+1);
               if (j < cur->GetSize()) { cout << " -> "; }
           }
           cout << endl;
       }
   }
   void BFS(int starting_index) {
      
       bool *visited = new bool[arraysize];
       for (int i = 0; i < arraysize; i++)
           visited[i] = false;

      
       queue<int> q;

      
       visited[starting_index -1] = true;
       q.enqueue(starting_index -1);

      
       while (!q.isEmpty())
       {
          
           starting_index = q.firstElement();
           cout << (starting_index+1) << " ";
           q.dequeue();


           for (int i = 1; i <= listoflist[starting_index]->GetSize(); i++)
           {
               if (!visited[listoflist[starting_index]->GetAt(i)])
               {
                   visited[listoflist[starting_index]->GetAt(i)] = true;
                   q.enqueue(listoflist[starting_index]->GetAt(i));
               }
           }
       }
      
   }
   bool isConnected(int src, int dest) {
       bool* visited = new bool[arraysize];
       queue<int> q;


       visited[src - 1] = true;
       q.enqueue(src-1);

       while (!q.isEmpty()) {
           int v = q.firstElement();
           q.dequeue();
           if (v == dest - 1) {
               return true;
           }
           for (int i = 1; i <= listoflist[v]->GetSize(); i++)
           {
               if (!visited[listoflist[v]->GetAt(i)])
               {
                   visited[listoflist[v]->GetAt(i)] = true;
                   q.enqueue(listoflist[v]->GetAt(i));
               }
           }
       }          

      
       return false;
   }
};

#endif

////////////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
//************************ intSLList.h **************************/
// singly-linked list class to store integers

/************************ intSLList.h **************************/
// singly-linked list class to store integers
#ifndef INT_LINKED_LIST
#define INT_LINKED_LIST
#include <iostream>
using namespace std;
class IntSLLNode {
public:
IntSLLNode() {
next = 0;
}
IntSLLNode(int el, IntSLLNode *ptr = 0) {
info = el; next = ptr;
}
int info;
IntSLLNode *next;
};
class IntSLList {
public:
IntSLList() {
head = tail = 0;
size = 0;
}
~IntSLList();
int isEmpty() {
return head == 0;
}
int GetSize(void);
int GetAt(int);
void addToHead(int);
void addToTail(int);
int deleteFromHead(); // delete the head and return its info;
int deleteFromTail(); // delete the tail and return its info;
void deleteNode(int);
bool isInList(int) const;
void printAll() const;
private:
IntSLLNode *head, *tail;
int size;
};
#endif

////////////////////////////////////////////////////////////////////////////////////////////////////////////


#include<iostream>
#include "intDrGraph.h"
#include <string>
#include "queue.h"
using namespace std;
int main(void) {
   string filename;
   int src = 5;
   int dst = 11;
   int element;
   cout << "What's the filename?" << endl;
   getline(cin, filename);
   intDrGraph Gr(filename);
   cout << "Which element you'd like to start to breadth search? " << endl;
   cin >> element;
   Gr.BFS(element);
   Gr.print();
   if (Gr.isConnected(src, dst) == 1)
       cout << "there is a way from " << src << " to " << dst << endl;
   else
       cout << "there isn't any way from " << src << " to " << dst << endl;

   system("pause");
}
Editor is loading...