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