[原创]数据结构课程设计

[watermark]#ifdef _MSC_VER #pragma warning(disable:4786) #endif// _MSC_VER //此程序使用最小生成树Prim算法。用户输入图的输入文件名，程序读此文件，并调用MinSpanTree()为图建立 //最小生成树。输出包括树的总权及其顶点和边的列表。 #include #include #include #include using namespace std; #include "d_graph.h" int main() { ifstream graphIn; //图的输入文件 graph g, minSpan; //顶点是字符 int weight; string fileName; //图文件名 cout << "Graph input 文件: "; cin >> fileName; graphIn.open(fileName.c_str()); if (!graphIn) { cerr << "Cannot open ';" << fileName << "';" << endl; exit(1); } graphIn >> g; //输入图 weight = minSpanTree(g, minSpan); //获得最小生成树和权 cout << "MST has weight "<< weight << endl << endl; //显示最小生成树 cout << " --- MST Graph ---" << endl; cout << minSpan << endl; return 0; }[/watermark]

风灵风之子 该用户已被删除

沙发

风灵风之子发表于 2005-3-31 20:53 | 只看该作者

[原创]数据结构课程设计

#ifndef GRAPH_CLASS #define GRAPH_CLASS #include #include #include //STL 集合容器 #include //STL 映射容器 #include //STL 动态数组容器 #include //STL 线性列表容器 #include //STL 堆栈容器 #include //STL 队列容器 #include //STL 定义运算函数（代替运算符） #include "d_except.h" #include "d_pqueue.h" const int INFINITY = (int)((unsigned int)~0 >> 1); using namespace std; class neighbor { public: int dest; //包含顶点属性的vInfo向量中目标顶点的索引 int weight; //此边的权 neighbor(int d=0, int c=0): dest(d), weight(c) //构造函数 {} friend bool operator< (const neighbor& lhs, const neighbor& rhs) { return lhs.dest < rhs.dest; } friend bool operator== (const neighbor& lhs, const neighbor& rhs) { return lhs.dest == rhs.dest; } }; //维护顶点属性，包括邻接点的集合 template class vertexInfo { public: enum vertexColor { WHITE, GRAY, BLACK }; //用于图算法 typename map::iterator vtxMapLoc; //指向顶点映射中对的迭代器 set edges; //当前顶点的邻接点集合 int inDegree; //保存顶点的入度 bool occupied; //指出对象当前是否表示顶点 vertexColor color; //表示在使用图遍历算法时，是否标记出当前的图 int dataValue; //算法利用该数据项来存储相关数据 int parent; //存储其边在当前顶点终止的顶点的父接点 vertexInfo(): inDegree(0), occupied(true) //默认构造函数 {} vertexInfo(typename map::iterator iter): vtxMapLoc(iter), inDegree(0), occupied(true) //构造函数，迭代器指向映射中的一个顶点 {} }; class minInfo { public: int endV; int pathWeight; friend bool operator< (minInfo lhs, minInfo rhs) { return lhs.pathWeight < rhs.pathWeight; } }; template class graph { public: class const_iterator: public map< T, int >::const_iterator { public: const_iterator() {} const_iterator(typename map::const_iterator i) { *((map< T, int >::const_iterator *)this) = i; } const T& operator* () const { map::const_iterator p = *this; return (*p).first; } }; typedef const_iterator iterator; graph(); //构造函数 graph(const graph& g); //拷贝构造函数 graph& operator= (const graph& rhs); //重载=操作符 int numberOfVertices() const; //返回途中顶点个数 int numberOfEdges() const; //返回图章边数 bool empty() const; //如果图没有顶点返回true int getWeight(const T& v1, const T& v2) const; //返回边(v1,v2)的权；如果此边不存在返回-1 void setWeight(const T& v1, const T& v2, int w); //更改边(v1,v2)的权 int inDegree(const T& v) const; //返回终止在顶点v的边数 int outDegree(const T& v) const; //返回从顶点v开始的边数 set getNeighbors(const T& v) const; //返回与顶点v相邻的顶点集合 void insertEdge(const T& v1, const T& v2, int w); //将指定权值的边(v1,v2)加入边集合中 void insertVertex(const T& v); //将顶点v加入到顶点集合中 void eraseEdge(const T& v1, const T& v2); //从图中删除边(v1,v2) void eraseVertex(const T& v); //从图中删除顶点v void clear(); //删除图中所有的顶点和边 iterator begin(); //返回指向图中第一个顶点的迭代器 iterator end(); //返回刚越过指向图中最后一个顶点的迭代器 const_iterator begin() const; //begin()的常量版本 const_iterator end() const; //end()的常量版本 // "d_galgs.h" implements the graph algorithms using inline code. #include "d_galgs.h" private: typedef map vertexMap; vertexMap vtxMap; //在映射中存储顶点，其名称作为键，vInfo向量中对应vertexInfo对象的索引作为值 vector > vInfo; //对应于顶点的vertexInfo对象表 int numVertices; int numEdges; //图的当前大小(顶点和边) stack availStack; //存储vInfo中未使用的索引栈 int getvInfoIndex(const T& v) const; //使用vtxMap获得vInfo中v的索引 }; //vInfo中vertexInfo对象的索引 template int graph::getvInfoIndex(const T& v) const { vertexMap::const_iterator iter; int pos; iter = vtxMap.find(v); if (iter == vtxMap.end()) pos = -1; else pos = (*iter).second; return pos; } //构造函数,初始化顶点数和边数都为0 template graph::graph(): numVertices(0), numEdges(0) {} //拷贝构造函数 template graph::graph(const graph& g) { *this = g; } //重载=运算符 template graph& graph::operator= (const graph& rhs) { vertexMap::iterator mi; if (this == &rhs) return *this; //拷贝rhs到当前对象 vtxMap = rhs.vtxMap; vInfo = rhs.vInfo; numVertices = rhs.numVertices; numEdges = rhs.numEdges; availStack = rhs.availStack; for (mi=vtxMap.begin();mi != vtxMap.end();mi++) vInfo[(*mi).second].vtxMapLoc = mi; return *this; } template int graph::numberOfVertices() const { return numVertices; } template int graph::numberOfEdges() const { return numEdges; } template bool graph::empty() const { return numVertices == 0; } template int graph::getWeight(const T& v1, const T& v2) const { int pos1=getvInfoIndex(v1), pos2=getvInfoIndex(v2); if (pos1 == -1 || pos2 == -1) //如果v1或v2不是有效的顶点，则产生graphError异常 throw graphError("graph getWeight(): vertex not in the graph"); const set& edgeSet = vInfo[pos1].edges; set::const_iterator setIter; if ((setIter = edgeSet.find(neighbor(pos2))) != edgeSet.end()) return (*setIter).weight; else return -1; } template void graph::setWeight(const T& v1, const T& v2, int w) { int pos1=getvInfoIndex(v1), pos2=getvInfoIndex(v2); if (pos1 == -1 || pos2 == -1) //如果v1或v2不是有效的顶点，则产生graphError异常 throw graphError("graph setWeight(): vertex not in the graph"); set& edgeSet = vInfo[pos1].edges; set::iterator setIter; if ((setIter = edgeSet.find(neighbor(pos2))) != edgeSet.end()) (*setIter).weight = w; else throw graphError("graph setWeight(): edge not in the graph"); } template int graph::inDegree(const T& v) const { int pos=getvInfoIndex(v); if (pos != -1) return vInfo[pos].inDegree; else throw graphError("graph inDegree(): vertex not in the graph"); } template int graph::outDegree(const T& v) const { int pos=getvInfoIndex(v); if (pos != -1) return vInfo[pos].edges.size(); else throw graphError("graph outDegree(): vertex not in the graph"); } //返回集合，其中包含v的所有邻接点 template set graph::getNeighbors(const T& v) const { set adjVertices; //返回的集合 int pos = getvInfoIndex(v); //从映射中获得v的位置 if (pos == -1) //如果v不在顶点表中，则抛出异常 throw graphError("graph getNeighbors(): vertex not in the graph"); const set& edgeSet = vInfo[pos].edges; //构造顶点pos的边集的别名 set::const_iterator setIter; //使用setIter遍历边集 //对应于邻接点的vertexInfo对象的索引 int aPos; for (setIter=edgeSet.begin(); setIter != edgeSet.end(); setIter++) { aPos = (*setIter).dest; //"(*setIter).dest"是vInfo的索引 adjVertices.insert ((*vInfo[aPos].vtxMapLoc).first); //在集合中插入顶点数据。vInfo[aPos].vtxMapLoc是映射迭代器，反引用它以访问顶点 } return adjVertices; } template void graph::insertEdge(const T& v1,const T& v2, int w) { // obtain the vInfo indices int pos1=getvInfoIndex(v1), pos2=getvInfoIndex(v2); if (pos1 == -1 || pos2 == -1) //如果v1或v2不是有效的顶点，则产生graphError异常 throw graphError("graph insertEdge(): vertex not in the graph"); else if (pos1 == pos2) //如果v1==v2(自环)，则产生graphError异常 throw graphError("graph insertEdge(): self-loops are not allowed"); //尝试将边(pos2,w)插入到顶点pos1的边集 pair::iterator, bool> result = vInfo[pos1].edges.insert(neighbor(pos2,w)); //保证边没有在集合中 if (result.second) { numEdges++; //增加边数 vInfo[pos2].inDegree++; //v2的入度加1 } } //将v插入图中 template void graph::insertVertex(const T& v) { int index; pair result =vtxMap.insert(vertexMap::value_type(v,0)); if (result.second) { if (!availStack.empty()) { index = availStack.top(); availStack.pop(); vInfo[index] = vertexInfo(result.first); } else { vInfo.push_back(vertexInfo(result.first)); index = numVertices; } (*result.first).second = index; numVertices++; } else throw graphError("graph insertVertex(): vertex already in the graph"); } //从图中删除边(v1,v2) template void graph::eraseEdge(const T& v1, const T& v2) { int pos1=getvInfoIndex(v1), pos2=getvInfoIndex(v2); if (pos1 == -1 || pos2 == -1) throw graphError("graph eraseEdge(): vertex not in the graph"); set& edgeSet = vInfo[pos1].edges; set::iterator setIter; setIter = edgeSet.find(neighbor(pos2)); if (setIter != edgeSet.end()) { edgeSet.erase(setIter); //v2的入度小于1 vInfo[pos2].inDegree--; numEdges--; } else throw graphError("graph eraseEdge(): edge not in the graph"); } template void graph::eraseVertex(const T& v) { //用于从映射中查找和删除v vertexMap::iterator mIter; int pos, j; set::iterator sIter; mIter = vtxMap.find(v); //在映射中查找关键键v //如果顶点不存在，则终止删除 if (mIter == vtxMap.end()) //如果v不在顶点表中，则抛出异常 throw graphError("graph eraseVertex(): vertex not in the graph"); pos = (*mIter).second; //获得vInfo中v的索引 //从顶点映射中删除顶点，并将顶点数减1 vtxMap.erase(mIter); numVertices--; //对vInfo中，对相应的项，设置occupied字段为false,然后把索引压入可用性栈,为以后添加结点做准备 vInfo[pos].occupied = false; availStack.push(pos); //删除终止v的所有边,这些边都有(vi,v)的形式,可以通过为每个顶点vi搜索边集而找到这些边,然后删除与v //邻接的顶点,从集合中删除一条边,同时必须对私有数据成员numEdges减1 for (j=0; j < vInfo.size(); j++) //在vInfo循环中,删除所有到v的边 if (vInfo[j].occupied) //只处理已经占用的项 { set& edgeSet = vInfo[j].edges; //构造集合vInfo.edges的别名 sIter = edgeSet.begin(); while (sIter != edgeSet.end()) //在边集中循环 if ((*sIter).dest == pos) { //查找pos,从集合中删除它,并将边数减1 edgeSet.erase(sIter); numEdges--; break; } else sIter++; } numEdges -= vInfo[pos].edges.size(); //将numEdges减去顶点v的边数 //所有v顶点邻接点的入度必须减1 set& edgesFromv = vInfo[pos].edges; for (sIter=edgesFromv.begin(); sIter != edgesFromv.end(); sIter++) { j = (*sIter).dest; vInfo[j].inDegree--; } set& edgeSet = vInfo[pos].edges; //消除边集,构造vInfo[pos].edges的别名 edgeSet.erase(edgeSet.begin(), edgeSet.end()); //使用erase消除集合 } template void graph::clear() { vInfo.erase(vInfo.begin(), vInfo.end()); vtxMap.erase(vtxMap.begin(), vtxMap.end()); while(!availStack.empty()) availStack.pop(); numVertices = 0; numEdges = 0; } template typename graph::iterator graph::begin() { return graph::iterator(vtxMap.begin()); } template typename graph::iterator graph::end() { return graph::iterator(vtxMap.end()); } template typename graph::const_iterator graph::begin() const { return graph::iterator(vtxMap.begin()); } template typename graph::const_iterator graph::end() const { return graph::iterator(vtxMap.end()); } #endif

TOP

风灵风之子 该用户已被删除

板凳

风灵风之子发表于 2005-3-31 20:56 | 只看该作者

[原创]数据结构课程设计

#ifndef EXCEPTION_CLASSES #define EXCEPTION_CLASSES #include #include using namespace std; class baseException { public: baseException(const string& str = ""): msgString(str) { if (msgString == "") msgString = "Unspecified exception"; } string what() const { return msgString; } protected: string msgString; }; class underflowError: public baseException { public: underflowError(const string& msg = ""): baseException(msg) {} }; //在图类中的错误 class graphError: public baseException { public: graphError(const string& msg = ""): baseException(msg) {} }; //在文件流中的错误 class fileError: public baseException { public: fileError(const string& msg = ""): baseException(msg) {} }; #endif

TOP

风灵风之子 该用户已被删除

地板

风灵风之子发表于 2005-3-31 21:02 | 只看该作者

[原创]数据结构课程设计

#ifndef MINI_PRIORITY_QUEUE_CLASS #define MINI_PRIORITY_QUEUE_CLASS #include #include "d_heap.h" #include "d_except.h" using namespace std; template > class miniPQ { public: miniPQ(); //构造函数 int size() const; //返回优先级队列长度 bool empty() const; //判断优先级队列是否为空 void push(const T& item); //向优先级队列中插入一个元素 void pop(); //从优先级队列中删除有先级最大的元素 T& top(); //返回具有最高优先级的元素的引用 const T& top() const; //常量版的top private: vector pqList; //pqList容纳优先级队列元素 Compare comp; //比较使用的函数对象 }; //构造函数,初始化空优先级队列 template miniPQ::miniPQ() {} template int miniPQ::size() const { return pqList.size(); } template bool miniPQ::empty() const { return pqList.empty(); } template void miniPQ::push(const T& item) { pqList.push_back(item); pushHeap(pqList,pqList.size(), comp); } template void miniPQ::pop() { if (pqList.empty()) //检查是否为空优先级队列,是则抛出异常 throw underflowError("miniPQ pop(): empty list"); popHeap(pqList, pqList.size(), comp); pqList.pop_back(); } template T& miniPQ::top() { if (pqList.empty()) throw underflowError("miniPQ top(): empty list"); return pqList[0]; } template const T& miniPQ::top() const { if (pqList.empty()) throw underflowError("miniPQ top(): empty list"); return pqList[0]; } #endif

TOP

风灵风之子 该用户已被删除

5楼

风灵风之子发表于 2005-3-31 21:08 | 只看该作者

[原创]数据结构课程设计

#ifndef HEAP_FUNCTIONS #define HEAP_FUNCTIONS #include #include using namespace std; template void pushHeap(vector& v, int last, Compare comp); template void adjustHeap(vector& v, int first, int last, Compare comp); template void popHeap(vector& v, int last, Compare comp); template void makeHeap(vector& v, Compare comp); //[0,last-1]范围中的向量元素是一个堆。将v[last-1]元素插入到堆中,使[0,last]是一个堆。使用函数对象comp进行比较 template void pushHeap(vector& v, int last, Compare comp) { //假设新项的位置为v[last-1],而且v[0]到v[i-2]的元素以堆的顺序排列 int currentPos, parentPos; T target; //currentPos是用于遍历父结点路径的索引。target是hlist值,需要在路径中重新定位 currentPos = last-1; parentPos = (currentPos-1)/2; target = v[last-1]; //遍历父结点的路径直到根 while (currentPos != 0) { if (comp(target,v[parentPos])) //比较target和父结点值 { v[currentPos] = v[parentPos]; currentPos = parentPos; parentPos = (currentPos-1)/2; } else break; } v[currentPos] = target; //正确位置已被发现，并将其赋值为target } //在索引范围[first,last)中，下移向量元素v[first] template void adjustHeap(vector& v, int first, int last, Compare comp) { int currentPos, childPos; T target; currentPos = first; target = v[first]; //计算左子结点的索引,开始向下扫描子结点的路径,表尾终止 childPos = 2 * currentPos + 1; while (childPos <= last-1) { //右子结点的索引为childPos+1。比较两个子结点,如果comp(v[childPos+1]), //v[childPos]为真,则改变childPos if ((childPos+1 <= last-1) && comp(v[childPos+1], v[childPos])) childPos = childPos + 1; //将所选子结点与target进行比较 if (comp(v[childPos],target)) { //comp(selected child, target)为真。将所选子结点移到父结点； //现在所选子结点的位置突出 v[currentPos] = v[childPos]; //更新索引以便继续扫描 currentPos = childPos; childPos = 2 * currentPos + 1; } else break; } v[currentPos] = target; } template void popHeap(vector& v, int last, Compare comp) { T temp; temp = v[0]; v[0] = v[last-1]; v[last-1] = temp; adjustHeap(v, 0, last-1, comp); } //将向量元素安排到堆中。使用函数对象comp进行比较 template void makeHeap(vector& v, Compare comp) { int heapPos, lastPos; lastPos = v.size(); heapPos = (lastPos - 2)/2; //从0开始,并恢复堆的顺序 while (heapPos >= 0) { adjustHeap(v,heapPos, lastPos, comp); heapPos--; } } #endif

TOP

风灵风之子 该用户已被删除

6楼

风灵风之子发表于 2005-3-31 21:13 | 只看该作者

[原创]数据结构课程设计

#ifdef __BORLANDC__ #pragma warn -8027 #endif //输入图类重载>>操作符 friend istream& operator>> (istream& istr, graph& g) { int i, nVertices, nEdges; T v1, v2; int weight; if (g.numVertices > 0) g.clear(); istr >> nVertices; for (i = 0; i < nVertices; i++) { istr >> v1; g.insertVertex(v1); } istr >> nEdges; for (i = 0; i < nEdges; i++) { istr >> v1; istr >> v2; istr >> weight; g.insertEdge(v1,v2,weight); } return istr; } //输出图类 friend ostream& operator<< (ostream& ostr, const graph& g) { vertexInfo vtxInfo; set::iterator setIter; int i; for (i = 0; i < g.vInfo.size(); i++) { vtxInfo = g.vInfo; if (vtxInfo.occupied) { ostr << (*(vtxInfo.vtxMapLoc)).first << ": in-degree " << vtxInfo.inDegree << " out-degree " << (vtxInfo.edges).size() << endl; ostr << " Edges: "; set& edgeSet = vtxInfo.edges; for (setIter = edgeSet.begin(); setIter != edgeSet.end(); setIter++) { ostr << (*(g.vInfo[(*setIter).dest].vtxMapLoc)).first << " (" << (*setIter).weight << ") "; } ostr << endl; } } return ostr; } //使用图g和生成树MST作为参数,创建MST,并返回最小生成树总权值 friend int minSpanTree(graph& g, graph& MST) { miniPQ > minTreePQ; minInfo vertexData; set adj; set::iterator adjIter; int minSpanTreeSize = 0, i; int pos_sVertex = -1, currPos, destPos, parentPos; int minSpanTreeWeight = 0; for (i = 0;i < g.vInfo.size(); i++) { if (g.vInfo.occupied) { if (pos_sVertex == -1) pos_sVertex = i; g.vInfo.color = vertexInfo::WHITE; g.vInfo.dataValue = INFINITY; } } vertexData.endV = pos_sVertex; vertexData.pathWeight = 0; g.vInfo[pos_sVertex].dataValue = 0; g.vInfo[pos_sVertex].parent = pos_sVertex; minTreePQ.push(vertexData); for (;;) { //删除优先级队列项 vertexData = minTreePQ.top(); minTreePQ.pop(); currPos = vertexData.endV; //如果新图的一部分(未访问),则对树的总权数增加该边的权,并增加树中的顶点数 if (g.vInfo[currPos].color == vertexInfo::WHITE) { minSpanTreeWeight += vertexData.pathWeight; minSpanTreeSize++; //如果已经跨越了所有顶点,则中断 if (minSpanTreeSize == g.numberOfVertices()) break; //将顶点标记为BLACK,则以后可以不用再查看它了 g.vInfo[currPos].color = vertexInfo::BLACK; //查找顶点所有未标记的邻接点。adjIter是集合迭代器, //指向对应于具有索引currPos和destPos的顶点的边 adj = g.vInfo[currPos].edges; for(adjIter = adj.begin();adjIter != adj.end();adjIter++) { destPos = (*adjIter).dest; //如果邻接点未标记,则进行查看是否对树增加新边要好于使用当前的边 if (g.vInfo[destPos].color == vertexInfo::WHITE) { if ((*adjIter).weight < g.vInfo[destPos].dataValue) { //如果新边更好,则为新顶点生成minInfo对象。 //更新vertexInfo中的dataValue和父变量 vertexData.endV = destPos; vertexData.pathWeight = (*adjIter).weight; g.vInfo[destPos].dataValue = (*adjIter).weight; g.vInfo[destPos].parent = currPos; minTreePQ.push(vertexData); }//end of if }//end of if }//end of for }//end of if }//end of for T vA, vB; MST.clear(); for(i = 0; i < g.vInfo.size(); i++) if (g.vInfo.occupied) MST.insertVertex((*(g.vInfo).vtxMapLoc).first); //把边加到最小生成书中 for (i = pos_sVertex+1; i < g.vInfo.size(); i++) if (g.vInfo.occupied) { parentPos = g.vInfo.parent; vA = (*(g.vInfo[parentPos]).vtxMapLoc).first; vB = (*(g.vInfo).vtxMapLoc).first; MST.insertEdge(vA,vB, g.getWeight(vA,vB)); } return minSpanTreeWeight; }