基本数据结构(图)
。。。
#include <iostream>using namespace std;//我们这个图的数据结构 认为：//1. 图是由很多节点(VERTEX)构成的, 因此图结构是由一个VERTEX的链表构成的, 每个VERTEX则需要有一个id,也就是start, 取start是为了跟LINE更直观地结合。//2. 每个节点关联着很多(LINE)构成,因此每个VERTEX由很多LINE构成, LINE不需要id, 但是它有3 要素: (start, end, weight), start不必说,取VERTEX中的即可,因此需要end和weight2种.注意: 每个VERTEX中都有一个LINE链表哦..//3. 因此,图的结构如下所示:/*Graph{ Vertex1{line1->line2->line3} | Vertex2{line1->line2->line3} . . . Vertexn{line1->line2->line3}}*///图的边struct LINE{ int end;//尾端点 int weight;//权重 LINE *next;//所有LINE的链表 LINE(int e, int w){ end = e; weight = w; next = 0; cout<<"LINE:"<<end<<","<<weight<<" created"<<endl; }};struct VERTEX{ int start;//起始点 int lineNums;//LINE的数量 LINE *first;//与点相关联的边的链表 VERTEX *next;//所有VERTEX的链表 VERTEX(int s){ start = s; lineNums = 0; first = 0; next = 0; cout<<"Vertex:"<<start<<" created"<<endl; } void visit(){ cout<<start<<" "; }};//最小生成树的Line结构struct MinTreeLine{ int start; int end;//尾端点 int weight;//权重 MinTreeLine *next;//所有LINE的链表 MinTreeLine(int s, int e, int w){ start = s; end = e; weight = w; next = 0; }};//最小生成树结构struct MinTree{ int start; int vn, ln; int weight; MinTreeLine*first; VERTEX* list; MinTree(int s){ start = s; vn = 1; ln = 0; weight = 0; first = 0; list = 0; } void insertVertex(int start){ if(list){ VERTEX * tmp = list; while(tmp->next){ tmp = tmp->next; } tmp->next = new VERTEX(start); }else{ list = new VERTEX(start); } } void deleteVertex(int start){ if(list){ VERTEX* tmp = list; if(tmp->start == start){ delete tmp; list = 0; return; }else{ while(tmp->next){ if(tmp->start ==start){ VERTEX* t = tmp; tmp = tmp->next; delete t; } } } } } MinTreeLine* getLast(){ MinTreeLine* l = first; if(l){ while(l->next){ l = l->next; } return l; }else{ return 0; } } MinTreeLine* getFormer(MinTreeLine* l){ MinTreeLine* line = first; while(line){ if(line->next && line->next->end == l->end){ break; }else{ line = line->next; } } return line; } void insertLine(MinTreeLine* l){ if(first){ getLast()->next = l; }else{ first = l; } ln++; vn++; //cout<<"加入line: "<<l->end<<"####ln=="<<ln<<", vn =="<<vn<<endl; } void rmLine(MinTreeLine*l){//不用delete，因为Line是在graph中的。 MinTreeLine * f = getFormer(l); if(f){ MinTreeLine*d = f->next; f->next = d->next; delete d; }else{ MinTreeLine*d = first; first = first->next; delete d; } } ~MinTree(){ while(first){ MinTreeLine* tmp = first; first = first->next; rmLine(tmp); } } void print(){ int p = start; MinTreeLine*l = first; while(l){ cout<<"["<<l->start<<"]---"<<l->weight<<"---["<<l->end<<"]"; l = l->next; } cout<<endl; }};struct GRAPH{ enum Kind{DG, NG, DN, NN}; Kind kind; int count; VERTEX* first; bool *visitDFSArr; GRAPH(): count(0), first(0){ kind = DG; visitDFSArr = 0; } GRAPH(Kind k): count(0), first(0){ kind = k; visitDFSArr = 0; } GRAPH(Kind k, int start, int end, int weight){ kind = k; visitDFSArr = 0; addVertexWithLine(start, end, weight); } ~GRAPH(){ while(first){ VERTEX* v = first; first = first->next; deleteVertex(v->start); } if(visitDFSArr) delete visitDFSArr; } //建立一条新的Line LINE* createNewLine(int end, int weight){//建立一个新LINE return new LINE(end,weight); } //建立一个新的Vertex VERTEX* createNewVertex(int start){//创建新Vertex return new VERTEX(start); } //在图中查找一个Vertex, 如果找到p返回的就是该vertex否则返回最后一个节点。 VERTEX* findVertex(VERTEX** p, int start){//寻找Vertex在graph中 VERTEX* tmp = first; if(p)*p = 0; while(tmp){ if(tmp->start == start) return tmp; if(p)*p = tmp; tmp = tmp->next; } return 0; } //从某一个Vertex的Line表中，查找一个Line, 如果找到, p返回的就是该Line否则返回最后一个Line。 LINE* findLine(LINE**p, LINE*first, int end){ LINE* tmp = first; if(p) *p = 0; while(tmp){ if(tmp->end == end) return tmp; if(p)*p = tmp; tmp = tmp->next; } return 0; } //增加一个Vertex到图中 VERTEX* addVertexToGraph(int start){ VERTEX*f = 0; if(!findVertex(&f, start)){ if(f){ f->next = createNewVertex(start); count++; return f->next; }else{ first = createNewVertex(start); count++; return first; } } return 0; } LINE* addLineToVertex(LINE *l, VERTEX*v){//前提:l和v必须都存在. LINE* vl = v->first; LINE *p = v->first; if(!vl){ v->first = l; }else{ while(vl){ p = vl; vl = vl->next; } p->next = l; } } //增加一条线到Vertex LINE* addLineToVertex(int start, int end, int weight){ VERTEX *v; LINE* resLine = 0; if(findVertex(&v, start)){ LINE* f = 0; if(v){ v = v->next; }else{ v = first; } if(!findLine(&f, v->first, end)){ if(f){ f->next = createNewLine(end,weight); resLine = f->next; }else{ v->first = createNewLine(end,weight); resLine = v->first; } if(kind == NG){//如果是无向图还需要反向来一次的说,这个不会形成无限递归的. addLineToVertex(end, start, weight); } } } return resLine; } //增加一个带有一条Line的节点, 只有带边的点，和孤独的点，却没有孤独的边。因此没有类似的addLine的函数。 void addVertexWithLine(int start, int end, int weight){ if(addVertexToGraph(start)){ if(addLineToVertex(start, end, weight)){ cout<<"addVertexWithLine sucess!"<<endl; }else{ cout<<"addVertexWithLine error1"<<endl; } }else{ cout<<"addVertexWithLine error2!"<<endl; } } //删除一条线，首先，在LINE中的链表中删除，然后在Vertex中删除 void deleteLine(int start, int end){//只有知道边的2个端点才能唯一确定一条边 //首先找到顶点 VERTEX *v; if(findVertex(&v, start)){ if(v){ v = v->next; }else{ v = first; } } deleteLine(v, end); } //删除一条线，首先，在LINE中的链表中删除，然后在Vertex中删除 void deleteLine(VERTEX*v, int end){//只有知道边的2个端点才能唯一确定一条边 LINE*l; if(findLine(&l, v->first, end)){ if(l){ delete l->next; l->next = l->next->next; }else{ LINE*f = v->first; v->first = f->next; delete f; } v->lineNums--; } } void deleteAllLine(VERTEX*v){//只有知道边的2个端点才能唯一确定一条边 LINE*l = v->first; while(l){ LINE*tmp = l; l = l->next; delete tmp; } v->first = 0; v->lineNums = 0; } void deleteAllLine(int start){//只有知道边的2个端点才能唯一确定一条边 //首先找到顶点 VERTEX *v; if(findVertex(&v, start)){ if(v){ v = v->next; }else{ v = first; } } deleteAllLine(v); } void deleteVertex(int start){ VERTEX*v; if(findVertex(&v, start)){ //首先删除从start点出发的LINE deleteAllLine(start); //然后删除节点 VERTEX*tmp = v->next; v->next = v->next->next; delete tmp; count--; //删除以start为终点的Lines. VERTEX* f = first; while(f){ deleteLine(f, start); f = f->next; } } } //深度优先遍历。 void DFS(VERTEX*v){ v->visit(); visitDFSArr[v->start] = true; LINE * l = v->first; while(l){ VERTEX* pv; findVertex(&pv, l->end); if(pv){ pv = pv->next; }else{ pv = first; } if(!visitDFSArr[pv->start]) DFS(pv); l = l->next; } } void DFSTraversal(){ delete visitDFSArr; visitDFSArr = new bool[count];//泄漏 for(int i = 0; i < count; i++){ visitDFSArr[i] = false; } VERTEX*v = first; while(v){ if(!visitDFSArr[v->start]) DFS(v); v = v->next; } cout<<endl; } //广度优先遍历。广度优先遍历选择一个队列辅助操作还是比较合理的。略 //最小生成树 //prim算法: 条件是加权连通图。找出图的最小生成树。 MinTree getPrimMinTree(int start){ MinTree p(start); if(visitDFSArr){ delete []visitDFSArr; visitDFSArr = 0; } visitDFSArr = new bool[count]; for(int i = 0; i < count; i++){ visitDFSArr[i] = false; } p.insertVertex(start);//起点加入p.list visitDFSArr[start] = true; while(p.list){//如果list为空则结束。每次循环增加一条线 VERTEX* vlist = p.list; VERTEX* vp =0;//遍历当前list表找出最短的line MinTreeLine* shortest = 0;//最短line while(vlist){//遍历p.list中的所有的点，在所有点中找到一个最短的路径。 vp = findVertex(0, vlist->start); LINE* bianli = vp->first;//遍历line while(bianli){//遍历该点上的所有line if(!visitDFSArr[bianli->end]){//这条LINE是合法的。if里面是判断它是否最短 if(shortest){//如果shortest已经有值了。则判断 if(bianli->weight < shortest->weight){ shortest->start = vlist->start; shortest->end = bianli->end; shortest->weight = bianli->weight; } }else{//如果没有值，shortest被赋值为合法值 shortest = new MinTreeLine(vlist->start, bianli->end, bianli->weight); } } bianli = bianli->next; } if(!shortest){//这说明，某个点上没有找到可以用的LINE,那就应该删除这个点。 p.deleteVertex(vp->start); } vlist = vlist->next;//下一个点 } if(shortest){ //cout<<"加入: "<<shortest->start<<"-"<<shortest->end<<"("<<shortest->weight<<")"<<endl<<endl; p.insertLine(shortest); p.insertVertex(shortest->end); visitDFSArr[shortest->end] = true; shortest = 0; }else{ //cout<<"结束"<<endl; //break; } } if(visitDFSArr){ delete []visitDFSArr; visitDFSArr = 0; } return p; }};//希望在构造图的时候应该先构造所有的点.int main(){ //GRAPH g(GRAPH::DG); GRAPH g(GRAPH::NG); //使用维基百科上prim词条中的图 g.addVertexToGraph(1); g.addVertexToGraph(2); g.addVertexToGraph(3); g.addVertexToGraph(4); g.addVertexToGraph(5); g.addVertexToGraph(6); g.addVertexToGraph(7); g.addLineToVertex(1, 2, 7); g.addLineToVertex(1, 4, 5); g.addLineToVertex(2, 3, 8); g.addLineToVertex(2, 4, 9); g.addLineToVertex(2, 5, 7); g.addLineToVertex(3, 5, 5); g.addLineToVertex(4, 5, 15); g.addLineToVertex(4, 6, 6); g.addLineToVertex(5, 6, 8); g.addLineToVertex(5, 7, 9); g.addLineToVertex(6, 7, 11); cout<<g.count<<endl; g.DFSTraversal(); /*g.deleteVertex(2); g.deleteVertex(3); g.DFSTraversal(); */ //生成树 MinTree p = g.getPrimMinTree(5); p.print(); cout<<p.ln<<" "<<p.vn<<endl;}没有考虑优化问题，有内存泄漏的可能。
有时空复杂度不佳的可能。