Untitled
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...