数据结构 邻接表有向图.doc

#include C:Documents and Settings中原桌面GraphLinkList.h/=/ 邻接表有向图 部分/=struct ListNode/定义图的顶点结点 每个结点包含结点vex 和一个用于存储边的链表lischar vex;/顶点元素LinkList lis;/边链表ListNode();/结点的无参构造函数ListNode(char v) vex=v;/给定顶点时构造结点void operator = (ListNode& n) vex=n.vex; lis=n.lis;/实现结点的赋值bool operator (ListNode n) return vexn.vex; /实现结点的比较bool operator = (ListNode n) return vex = n.vex; /实现结点的比较;class AdjListDirGraph/定义邻接表有向图public:int vexNum, edgeNum;/定义vexNum存储图的顶点数、和有向边数edgeNumLinkList vList;/定义以图的顶点结点构成的表AdjListDirGraph()vexNum=0; edgeNum=0;/图的构造函数 无参数时默认构造0个顶点的图AdjListDirGraph()clear();/析构函数void insetVertex(char v);/向图中插入一个顶点vvoid delVertex(char v);/在图中删除顶点vvoid setEdge(int v1, int v2);/插入从顶点v1到顶点v2的边 v1、v2为顶点对应的位置void delEdge(int v1, int v2);/删除从顶点v1到顶点v2的边 v1、v2为顶点对应的位置int getSite(char v);/获取顶点v在顶点表中的位置void setEdge(char v1, char v2) setEdge(getSite(v1), getSite(v2); /插入从顶点v1到顶点v2的边 v1、v2为顶点void delEdge(char v1, char v2) delEdge(getSite(v1), getSite(v2); /删除从顶点v1到顶点v2的边 v1、v2为顶点void showVertex();/输出图的顶点及其对应的位置void showEdge();/输出以每个顶点为起点的边int inDegree(int v);/求第v个顶点的入度int outDegree(int v);/求以顶点v为起点的边数 求第v个顶点的出度int inDegree(char v) return inDegree(getSite(v); /求顶点v的入度int outDegree(char v) return outDegree(getSite(v); /求取顶点v的出度void clear();/图清空void operator = (AdjListDirGraph& G) vexNum=G.vexNum; edgeNum=G.edgeNum; vList=G.vList;/重载运算符”=实现图的复制;void AdjListDirGraph: insetVertex(char v)int site = getSite(v);if(site = vexNum+1)ListNode e(v);/生成顶点结点vvList.TailInsert(e);/向顶点表的末位插入一个顶点结点vexNum+;void AdjListDirGraph: delVertex(char v) int site = getSite(v);if(site=1 & site=vexNum)/当顶点在 已存在顶点的表示的范围之内时进行操作for(int i=1; i=vList.Length(); i+)/i=vList的顶点数时for(int j=1; jdata.lis.Length(); j+)if(vList.GetPosP(i)-data.lis.GetPosP(j)-data = site) /第i个顶点结点表的第j个边的终点的位置为site时vList.GetPosP(i)-data.lis.DelElem(j);/删除与指向顶点的边edgeNum-;/边总数减1i-;/删除第i个元素后第i个位置为后一个元素故i应保持不动/中断for循环 因为从第i个顶点到第v个顶点最多只有一条边else if(vList.GetPosP(i)-data.lis.GetPosP(j)-data site) /第i个顶点结点表的第j个边的数据部分site 时 位置减1vList.GetPosP(i)-data.lis.GetPosP(j)-data-;vList.GetPosP(site)-data.lis.Clear();/对顶点表清空vList.DelElem(site);/删除顶点表结点vvexNum-;/顶点总数减1void AdjListDirGraph: setEdge(int v1, int v2)if(v1=1 & v2=1 & v1=vexNum & v2data.lis.TailInsert(v2);/在顶点v1的链表中插入到顶点v2的边int tmp = vList.GetPosP(v1)-data.lis.Length();/将顶点v1表的长度暂存到tmp中vList.GetPosP(v1)-data.lis.Sort();/对顶点v1表进行排序vList.GetPosP(v1)-data.lis.KillDouble();/对顶点v1表进行去重edgeNum += vList.GetPosP(v1)-data.lis.Length()-tmp;/将新增的边数加到图的总边数中void AdjListDirGraph: delEdge(int v1, int v2)if(v1=1 & v2=1 & v1=vexNum & v2= vexNum)/当要插入的边在顶点表示的范围之内时进行操作for(int i=1; idata.lis.Length(); i+)/idata.lis.GetPosP(i)-data = v2) /第v1个顶点结点表的第i个边的数据部分=v2 时vList.GetPosP(v1)-data.lis.DelElem(i);/删除从顶点v1到顶点v2的边break;int AdjListDirGraph: getSite(char v)for(int i=1; idata.vex = v) break;/当找到顶点v时 计数寻找return i;/返回顶点v在顶点表的位置 若未找到返回的值为表的顶点数加一void AdjListDirGraph: showVertex()if(vexNum) coutn图当前有vexNum个顶点n依次为 ：;for(int i=1; i=vexNum; i+)/获取顶点链表的各个顶点到e中coutdata.vex ;/输出显示各个顶点/*coutn对应位置 ;for(i=1; i=vexNum; i+)/显示各个顶点在邻接表中的对应位置couti ;*/coutendl;void AdjListDirGraph: showEdge()int tmp;if(vexNum) coutn图邻接表表示为：n;for(int i=1; i=vList.Length(); i+)coutdata.vex ;/输出显示邻接表的第i个表结点所表示的顶点for(int j=1; jdata.lis.Length(); j+)/jdata.lis.GetElem(j, tmp);/获取第i个顶点表的第j项边的数据部分到 tmp中coutdata.vex;/输出显示第tmp个顶点coutvexNum) return 0;/当给出的顶点位置超出当前的顶点数时其出度为0else return vList.GetPosP(v)-data.lis.Length();/给出的顶点在当前顶点的表示范围之内时返回对应顶点表的长度int AdjListDirGraph: inDegree(int v)int count=0;if(v=1 & v=vexNum)/当要求入度的顶点在 已存在顶点的表示的范围之内时进行操作for(int i=1; i=vList.Length(); i+)/对于所有顶点表for(int j=1; jdata.lis.Length(); j+)/对于每个顶点表的每条边if(vList.GetPosP(i)-data.lis.GetPosP(j)-data = v) /第i个顶点结点表的第j个边的终点的位置为vcount+;/第v个顶点的入度加1break;/中断for循环 因为从第i个顶点到第v个顶点最多只有一条边return count;void AdjListDirGraph: clear()while(vexNum)vList.GetPosP(1)-data.lis.Clear();/对顶点表清空vList.DelElem(1);/删除顶点表结点vvexNum-;/顶点总数减1edgeNum = 0;void GraphInputHelp()int choice=1, i;char cTmp, cTmp2;AdjListDirGraph G;while(choice)coutn-;coutn请选择相关操作：nn1.构造有向图 2.构造无向图;coutchoice;cin.get();/将输入的字符n从输入流中清除switch(choice)case 1:coutn请输入图的所有顶点 Enter结束n;docin.get(cTmp);if(cTmp!=n & cTmp!= ) G.insetVertex(cTmp);/构造图的所有顶点while(cTmp != n);G.showVertex();/输出显示已经输入的顶点coutn请输入以下各边的终点 Enter结束n;for(i=1; idata.vex;cout以cTmp2为起点的所有边：;docin.get(cTmp);if(cTmp!=n & cTmp!= ) G.setEdge(cTmp2, cTmp);/构造以cTmp2为起点的所有边while(cTmp != n);G.showEdge();/以邻接表的形式输出显示构造的图break;case 2:coutn请输入图的所有顶点 Enter结束n;docin.get(cTmp);if(cTmp!=n & cTmp!= ) G.insetVertex(cTmp);/构造图的所有顶点while(cTmp != n);G.showVertex();/输出显示已经输入的顶点coutn请输入以下各边的顶点 Enter结束n;for(i=1; idata.vex;cout与cTmp2相邻的所有顶点：;docin.get(cTmp);if(cTmp!=n & cTmp!= )/构造cTmp和cTmp2之间的边 G.setEdge(cTmp2, cTmp); G.setEdge(cTmp, cTmp2);while(cTmp != n);G.showEdge();/以邻接表的形式输出显示构造的图break;coutn-n;coutchoice;coutendlendlendl;/*/邻接表有向图到此处结束/-void main()GraphInputHelp();/*char v;AdjListDirGraph G, G2;coutn请输入图的5个顶点n;for(int i=0; iv;G.insetVertex(v);int num;char v1, v2;coutnum;G.showVertex();coutn请输入边所对应的两顶点 n;for(i=0; inum; i+)cout第i+1v1v2;G.setEdge(v1, v2);G.showEdge();G.delEdge(B, E);G.showEdge();G.delVertex(C);G.showEdge();G.insetVertex(C);G.showEdge();coutn顶点E的出度为：G.outDegree(E);coutn顶点E的入度为：G.inDegree(E);coutn顶点B的出度为：G.outDegree(B);coutn顶点B的入度为：G.inDegree(B);coutn复制功能验证：n;G2=G;G2.showEdge();G.clear();G.showEdge();coutn顶点E的出度为：G.outDegree(E);coutn顶点E的入度为：G.inDegree(E);coutn顶点B的出度为：G.outDegree(B);coutn顶点B的入度为：G.inDegree(B);*/头文件C:Documents and Settings中原桌面GraphLinkList.h部分#include/多用链表结点templatestruct DblNodeET data;/结点数据域，存储该结点的数据部分DblNode* next;/结点指针域，指示下一个节点的位置DblNode* back;/指向结点的前驱DblNode() next = NULL; back = NULL; /无参数结点构造函数，用于未给定参数时结点的初始化;/=/ 链表类 部分/=templateclass LinkListprotected:ET dataTmp;/用于临时存取数据，供成员函数使用int count, cTmp;/count用于计数表元素个数,即表长； cTmp用于临时计数用DblNode *head, *tail, *pTmp;/*head记录表头的位置； *tail记录表尾的位置； *pTmp记录每次操作结点的指针位置public:LinkList() count=cTmp=0; head = tail = pTmp = NULL;/链表构造函数LinkList() Clear();/链表析构函数/链表相关操作int Length() return count;/用于获取当前表的长度void Clear() while(count) DelHead(); /表清空void Show();/输出表中现有的所有元素void ReShow();/逆序输出表中现有的所有元素DblNode* GetPosP(int postion);/获取指向第postion个位置结点的指针void HeadInsert(ET &e);/从表头插入元素void TailInsert(ET &e);/从表尾插入元素void Insert(int position, ET &e);/向表中第postion个位置插入新的结点元素，元素总数加一void ReTailInsert(int position, ET &e);/重置表中第cTmp个位置元素的数据部分为e，元素总数不变void GetElem(int position, ET &e);/从表中获取第cTmp元素，写入e中，由e输出void DelHead();/删除表头void DelTail();/删除表尾void DelElem(int position);/删除表中第cTmp个位置的元素.元素减一void operator = (LinkList& cop);/赋值符重载函数，实现链表的复制功能void SUB(LinkList &A, LinkList &B);/实现链表相减，将仅存在于A中的元素写入当前链表void ADD(LinkList &A, LinkList &B);/实现链表相加，将表A 表B中的元素依次写入当前链表void Seprate();/奇偶分离函数，使得所有奇数均排列在偶数前void Sort();/对链表中的元素进行排序void KillDouble();/对链表中的元素进行排序去重;templatevoid LinkList:Show()cTmp = count;pTmp = head;/指向头指针的第一个后继coutendl当前链表中共有count个元素,endl0 & count0)/当表中有元素时dataTmp = pTmp-data;coutdataTmpnext;/每输出一位向后移动一位coutendl;templatevoid LinkList:ReShow()cTmp = count;pTmp = tail;/指向头指针的第一个后继coutendl当前链表中共有count个元素,endl0 & count0)/当表中有元素时dataTmp = pTmp-data;coutdataTmpback;/每输出一位向后移动一位coutendl;templateDblNode* LinkList:GetPosP(int postion)cTmp = postion;if(cTmp=1)if(cTmp=1) return head;if(cTmpcount) cTmp = cTmp % count; if(cTmp = 0) cTmp = count; /当输入位置大于元素总数时取余数得对应位置if(cTmp 1) pTmp = pTmp-next; cTmp-;else/后count/2用back指针访问cTmp = count - cTmp + 1;pTmp = tail;/不断指向下一个结点，头指针所在位置为零while(cTmp1) pTmp = pTmp-back; cTmp-;return pTmp;templatevoid LinkList:ReTailInsert(int position, ET &e)cTmp = position;if(count = 0)coutendl表当前为空，无元素可修改data = e;/重置表中元素，元素总数不变templatevoid LinkList:HeadInsert(ET &e)if(count = 0)/向表中插入第一个结点元素 head = new DblNode; tail = pTmp = head; head-data = e;count+; else head-back = new DblNode; head-back-next = head; head = head-back; head-data = e;count+;templatevoid LinkList:TailInsert(ET &e)if(count = 0)/向表中插入第一个结点元素 tail = new DblNode; head = pTmp = tail; tail-data = e;count+; else tail-next = new DblNode;pTmp = tail-next;pTmp-back = tail;tail = pTmp; tail-data = e;count+;templatevoid LinkList:Insert(int position, ET &e)/在第pos个位置插入一个新结点int pos = position;/因为此成员函数调用了获取指针位置函数GetPosP()，而该函数使用了cTmp计数区间，故需使用其他空间计数if(count = 0 ) HeadInsert(e);/当元素总数为0时elseif(poscount)/当输入位置大于元素总数时if(pos % count = 1) pos = count+1;/输入位置大于元素总数且取余后为1，将pos置为插入尾部else if(pos % count = 0) pos = count; else pos = pos % count;if(pos = 1) HeadInsert(e);else if(pos = count+1) TailInsert(e);else pTmp = GetPosP(pos-1);/获取指向第pos-1个结点的指针DblNode* posNext = pTmp-next;/获取指向第pos个结点的指针pTmp-next = new DblNode;/在pos-1后生成新结点pTmp-next-back = pTmp;/新结点前驱为第pos-1个结点pTmp-next-next = posNext;/新结点后继为原pos个结点pTmp-next-data = e;posNext-back = pTmp-next;/原pos个位置的结点前驱指向新结点count+;templatevoid LinkList:GetElem(int position, ET &e)cTmp = position;if(cTmp=1) e = GetPosP(cTmp)-data;/获取指向第cTmp个结点的数据部分templatevoid LinkList:DelHead()if(count 0)pTmp = head-next;delete head;head = pTmp;count-;templatevoid LinkList:DelTail()if(count 0)pTmp = tail-back;delete tail;tail = pTmp;count-;templatevoid LinkList:DelElem(int positon)/删除在第cTmp个位置的结点cTmp = positon;if(cTmpcount) cTmp = cTmp % count;if(count = 0)coutendl表当前为空，无元素可修改endl;else if(count = 1 | cTmp = 1)DelHead();else if(cTmp = count) DelTail();elsepTmp = GetPosP(cTmp-1);/获取指向第cTmp-1个结点的指针DblNode* pNext = pTmp-next;/获取指向第cTmp个结点的指针pTmp-next = pNext-next;/将第cTmp-1个结点的后继指向第cTmp个结点的后继pNext-next-back = pTmp;/将第cTmp+1个结点的前驱指向第cTmp-1个结点delete pNext;/将第cTmp个结点删除count-;/表元素元素总数减一templatevoid LinkList:operator = (LinkList& cop)/赋值符“ = ”重载Clear();/对当前链表先清空if(cop.count0)cTmp = cop.count;cop.pTmp = cop.head;/复制cop的头指针注意：cop.pTmp 不可换做 pTmp ？否则运行报错while(cTmp0)/当表中还有元素时dataTmp = cop.pTmp-data;/取出后继结点中的数据TailInsert(dataTmp);/生成新结点cTmp -;/计数元素总数减一cop.pTmp = cop.pTmp-next;/向后继结点移动一位templatevoid LinkList:SUB(LinkList &A, LinkList &B)Clear();/对当前链表先清空int countA=1, countB;ET elemA, elemB;DblNode* posA = A.head, * posB;while(countAdata;/依次获取A表中元素的数据部分posA = posA-next;countA+;while(countBdata;posB = posB-next;if(elemA=elemB) break;/将A中的每一个元素分别与B中的每一个元素进行比较，若相同则中断本次循环countB+;if(countBB.count) TailInsert(elemA);/若与B中所有元素均不相同时将该元素写入当前表中temp