返回列表 发帖

[原创+整理]数据结构的一些笔记

//图的邻接顶点 #ifndef H_linkedListGraph #define H_linkedListGraph #include"linkedlist.h" using namespace std; template struct nodeType1 { vType vertex;//顶点 nodeType *link; }; template class linkedListGraph:public linkedListType { public: void getAdjacentVertices(vType adjacenyList[],int& length) //返回邻接顶点 { nodeType1 *current; length=0; current=first; while (current!=NULL) { adjacenyList[length++]=current->info; current=current->link; } } }; #endif

TOP

[原创+整理]数据结构的一些笔记

//图(使用的是深度优先算法) #ifndef H_graphType #define H_graphType #include #include #include"linkedListGraph.h" using namespace std; const int infinity=10000000; template class graphType { public: bool isEmpty() {return (gSize==0);} void createGraph(); void clearGraph(); void printGraph() const; void depthFirstTraversal();//深度优先算法 void dftAtVertex(vertexType vertex); graphType();//默认构造函数 ~graphType();//析构函数 protected: int maxSize; int gSize;//当前顶点 linkedListGraph *graph; private: void dft(vertexType v,bool visited[]); }; template void graphType::createGraph() { ifstream infile; char fileName[50]; vType vertex; vType adjacentVertex; if (gSize!=0) clearGraph(); cout<<"Enter the input file name: "; cin>>fileName; cout<>gSize; for (int index=0;index>vertex; infile>>adjacentVertex; while (adjacentVertex !=-999) { graph[vertex].insertLast(adjacentVertex); infile>>adjacentVertex; } } infile.close(); } template void graphType::clearGraph() { int index; for (index=0;index void graphType::printGraph() const { int index; for (index=0;index graphType::graphType() { maxSize=size; gSize=0; graph=new linkedListGraph[maxSize]; } template graphType::~graphType() { clearGraph(); delete[] graph; } template void graphType::dft(vType v,bool visited[]) { vType w; vType *adjacencyList; adjacencyList=new vType[gSize]; int alLength=0; visited[v]=true; cout<<" "< void graphType::depthFirstTraversal() { bool *visited; visited=new bool[gSize]; int index; for (index=0;index void graphType::dftAtVertex(vertexType vertex) { bool *visited; visited=new bool[gSize]; for (int index=0;index

TOP

[原创+整理]数据结构的一些笔记

//无向网的最小生成树 #ifndef H_meTreeType #define H_msTreeType #include"graphType.h" using namespace std; template class msTreeType:public graphType//最小生成树,使用Prim算法 { public: void createSpanningGraph();//创建图及加权矩阵 void minimalSpanning(vType sVertex);//实现Prim算法 void printTreeAndWeight(); protected: vType source; int weights[size][size]; int edges[size]; int edgeWeight[size]; };//因为没有使用指针所以不需要使用默认构造函数和析构函数 template void msTreeType::createSpanningGraph() { source.createGraph(); for (j=0;j void msTreeType::minimalSpanning(vType sVertex) { int i,j,k; vType startVertex,endVertex; int minWeight; source=sVertex; bool mstv[size]; for (j=0;j) { for (k=0;k void msTreeType::printTreeAndWeight() { int treeWeight=0; cout<<"Source Vertex: "<

TOP

返回列表 回复 发帖