mios.rar_大数据

#include <iostream.h> #include "ASearch.h" // 定义结点间关系 ArcNode AZ={19,75}; ArcNode AS={15,140}; ArcNode AT={16,118}; ArcNode BF={5,211}; ArcNode BP={13,101}; ArcNode BG={6,90}; ArcNode BU={17,85}; ArcNode CD={3,120}; ArcNode CR={14,148}; ArcNode CP={13,138}; ArcNode DC={2,120}; ArcNode DM={10,75}; ArcNode EH={7,86}; ArcNode FB={1,211}; ArcNode FS={15,99}; ArcNode GB={1,90}; ArcNode HE={4,86}; ArcNode HU={17,98}; ArcNode IN={11,87}; ArcNode IV={18,92}; ArcNode LT={16,111}; ArcNode LM={10,70}; ArcNode ML={9,70}; ArcNode MD={3,75}; ArcNode NI={8,87}; ArcNode OZ={19,71}; ArcNode OS={15,151}; ArcNode PR={14,97}; ArcNode PC={2,138}; ArcNode PB={1,101}; ArcNode RP={13,97}; ArcNode RC={2,146}; ArcNode RS={15,80}; ArcNode SA={0,140}; ArcNode SO={12,151}; ArcNode SF={5,99}; ArcNode SR={14,80}; ArcNode TA={0,118}; ArcNode TL={9,111}; ArcNode UB={1,85}; ArcNode UH={7,98}; ArcNode UV={18,142}; ArcNode VI={8,92}; ArcNode VU={17,142}; ArcNode ZA={0,75}; ArcNode ZO={12,71}; CASearch::CASearch() { m_cityNodes = new CNode[20]; m_h = new int[20]; step = 1; } CASearch::~CASearch() { if (m_cityNodes != NULL) { delete []m_cityNodes; m_cityNodes = NULL; } if (m_h != NULL) { delete []m_h; m_h = NULL; } } void CASearch::SetDatas(CNode citNodes[], int h[]) { for (int i = 0; i < 20; i++) { m_cityNodes[i] = citNodes[i]; } for (int j = 0; j < 20; j++) { m_h[j] = h[j]; } } void CASearch::SetStartCityNode(int startCityNumber) { m_startNode.adjvex = startCityNumber; m_startNode.cost = 0; m_startNode.nextarc = NULL; m_startNode.perarc =NULL; } void CASearch::Init() { m_cityNodes[0].firstarc=&AZ; AZ.nextarc=&AS; AS.nextarc=&AT; m_cityNodes[1].firstarc=&BF; BF.nextarc=&BP; BP.nextarc=&BG; BG.nextarc=&BU; m_cityNodes[2].firstarc=&CD; CD.nextarc=&CR; CR.nextarc=&CP; m_cityNodes[3].firstarc=&DC; DC.nextarc=&DM; m_cityNodes[4].firstarc=&EH; m_cityNodes[5].firstarc=&FB; FB.nextarc=&FS; m_cityNodes[6].firstarc=&GB; m_cityNodes[7].firstarc=&HE; HE.nextarc=&HU; m_cityNodes[8].firstarc=&IN; IN.nextarc=&IV; m_cityNodes[9].firstarc=&LT; LT.nextarc=&LM; m_cityNodes[10].firstarc=&ML; ML.nextarc=&MD; m_cityNodes[11].firstarc=&NI; m_cityNodes[12].firstarc=&OZ; OZ.nextarc=&OS; m_cityNodes[13].firstarc=&PR; PR.nextarc=&PC; PC.nextarc=&PB; m_cityNodes[14].firstarc=&RP; RP.nextarc=&RC; RC.nextarc=&RS; m_cityNodes[15].firstarc=&SA; SA.nextarc=&SO; SO.nextarc=&SF; SF.nextarc=&SR; m_cityNodes[16].firstarc=&TA; TA.nextarc=&TL; m_cityNodes[17].firstarc=&UB; UB.nextarc=&UH; UH.nextarc=&UV; m_cityNodes[18].firstarc=&VI; VI.nextarc=&VU; m_cityNodes[19].firstarc=&ZA; ZO.nextarc=&ZA; } void CASearch::Search() { Init(); TreeNode *headNode = &m_startNode; //搜索头结点 cout<<"开始结点 :"<<m_cityNodes[m_startNode.adjvex].city<<endl<<"路径搜索..."<<endl<<endl; while (headNode->adjvex!=1) { ArcNode *p=m_cityNodes[headNode->adjvex].firstarc; //以头结点开始查找p用于查找 cout<<"步骤"<<step<<": 扩展"<<"结点 : "<<m_cityNodes[headNode->adjvex].city<<endl; int g = headNode->cost; TreeNode* nodeExpand = headNode; //记录扩展的结点 headNode = headNode->nextarc; //删除头结点 while (p!=NULL) //遍历头结点的邻边 { if(headNode==NULL) //插入新增结点在空链表中 { headNode = NewNode(p->adjvex, p->cost+g, nodeExpand, NULL); cout<<"结点 :"<<m_cityNodes[headNode->adjvex].city<<" G="<<headNode->cost<<" H="<<m_h[headNode->adjvex]<<" F="<<headNode->cost+m_h[headNode->adjvex]<<endl; } else { int gCost = headNode->cost ; int hCost = m_h[headNode->adjvex]; int fCost = gCost + hCost; if((p->cost+g+m_h[p->adjvex]) < fCost) //插入新增结点在表头 { headNode = NewNode(p->adjvex, p->cost+g, nodeExpand, headNode); cout<<"结点 :"<<m_cityNodes[headNode->adjvex].city<<" G="<<gCost<<" H="<<hCost<<" F="<<fCost<<endl; } else { TreeNode *q=headNode; if(q->nextarc!=NULL) { while((p->cost+g+m_h[p->adjvex])>(q->nextarc->cost+m_h[q->nextarc->adjvex])) //插入新增结点在表中或表尾 { q=q->nextarc; if(q->nextarc==NULL) break; } TreeNode* n = NewNode(p->adjvex, p->cost+g, nodeExpand, q->nextarc); q->nextarc = n; cout<<"结点 :"<<m_cityNodes[n->adjvex].city<<" G="<<n->cost<<" H="<<m_h[n->adjvex]<<" F="<<n->cost+m_h[n->adjvex]<<endl; } else { TreeNode *n= NewNode(p->adjvex, p->cost+g, nodeExpand, NULL); q->nextarc= n; cout<<"结点 :"<<m_cityNodes[n->adjvex].city<<" G="<<n->cost<<" H="<<m_h[n->adjvex]<<" F="<<n->cost+m_h[n->adjvex]<<endl; }; }; }; p=p->nextarc; } step = step + 1; }; TreeNode *pNode=headNode; int index=0; char path[20]; cout<<"搜索结束, 搜索路径为:"<<endl; while(pNode!=NULL) { path[index] = m_cityNodes[pNode->adjvex].city; pNode = pNode->perarc; index++; } for (; index>0; index--) { cout<<path[index-1]; if(index-1>0) cout<<"->"; else cout<<endl; } cout<<"总距离为 :"<<headNode->cost<<"."<<endl; } TreeNode* CASearch::NewNode(int adjvex, int cost, TreeNode* perarc, TreeNode* nextarc) { TreeNode *node = new TreeNode; node->adjvex = adjvex; node->cost = cost; node->perarc = perarc; node->nextarc = nextarc; return node; }