呢图网站场建设封面,贵州seo和网络推广,18款禁用软件app排行,崇明装修公司哪家好最初是做2004年某期《程序员》杂志上的一道题#xff0c;叫“洞穴探险”#xff0c;结果写着写着就做到公交换乘的思路上去了。看来做GIS做久了#xff0c;都成习惯了。后来工作忙#xff0c;就扔下了。最近翻看以前自娱自乐时写的东东#xff0c;看到了这段代码#xff…最初是做2004年某期《程序员》杂志上的一道题叫“洞穴探险”结果写着写着就做到公交换乘的思路上去了。看来做GIS做久了都成习惯了。后来工作忙就扔下了。最近翻看以前自娱自乐时写的东东看到了这段代码索性贴出来共享抛砖引玉吧。文中使用的queue_alloc和queue_free函数是洒家自己设计的“简易空间配置器”的C 语言实现版本关于简易空间配置器的详细信息请参考《简易空间配置器》(http://blog.csdn.net/bfbd/archive/2004/06/22/22743.aspx)一文。#include stdafx.h#include #include #include using namespace std;const _BUF_SIZE_ 100;// C版本的搜索函数extern C{typedef struct Q_NODE{int id; //节点编码Q_NODE *father; //父节点的地址} Q_NODE;/*队列由多段缓冲区组成每段缓冲区为连续的多个节点。id大于0时表示节点的编码值。father为正常的内存地址时表示本节点的父节点所在的内存id为0表示当前节点为缓冲区末尾节点其father指向下一个缓冲区段的起点。father为空表示当前节点为队列末尾节点father为-1表示当前节点为树的根节点*/void dumpMap(int n, int *ph, int *pl){int _i;printf(ph[]: );for (_i0; _iprintf(%d , ph[_i]);printf(\n);printf(pl[]: );for (_i0; _iprintf(%d , pl[_i]);printf(\n);}void dumpDeep(int n, int *pd){int _i;printf(pd[]: );for (_i0; _iprintf(%d , pd[_i]);printf(\n);}void dumpQueue(Q_NODE *Qs){Q_NODE *_pQ;printf(Q: );for ( _pQQs; (_pQ-father _pQ-id); _pQ ){printf(%d-%d , _pQ-id,((-1!(int)_pQ-father) (_pQ-father)) ? (_pQ-father-id) : 0);if ( 0_pQ-id )_pQ _pQ-father;}printf(\n);}Q_NODE* queue_alloc(int size)// 为队列申请新的空间// size: 申请的空间大小// return: 申请空间的起始地址{Q_NODE *Qb new Q_NODE[size];//初始化对列缓冲区memset(Qb, 0, sizeof(Q_NODE) * size);for (int i 0; i size - 1; i)Qb[i].father (Qb[i1]);Qb[size-1].father NULL;return Qb;}void queue_free(Q_NODE* pQ, int size)// 释放对列所占的内存// pQ: 队列起始地址// return:{if (NULL ! pQ){Q_NODE* p;while (NULL ! pQ){p pQ;pQ pQ[size-1].father;delete[] p;}}}void search_change(int n, int *ph, int *pl, int *pd)// 搜索换乘路径// n: 节点个数// *ph: 邻接压缩表描述序列(长度为n1)// *pl: 邻接压缩表序列(长度为ph[n])// *pd: 换乘深度(长度为n1,pd[0]不用)0 表示未达站点1 表示出发站-1 表示终点站。// return:{#ifdef _DEBUGdumpMap(n, ph, pl);dumpDeep(n, pd);#endif //_DEBUGassert(n 2);int i; //循环计数器Q_NODE *Qs, //队列头部*Qe, //队列尾部*pQ1, //队列元素指示器*pQ2;Qs Qe queue_alloc(_BUF_SIZE_);//出发节点加入队列for (i 1; i n 1; i){if (1 pd[i]){if (NULL Qe-father){Qe-id 0;Qe-father queue_alloc(_BUF_SIZE_); //扩充队列Qe Qe-father; //跳过缓冲区末尾的节点/*缓冲区末尾的节点id为0(一个不可能出现的节点编码)表示本节点的father指针指向下一个缓冲区的起始地址而不是本节点的父节点地址。*/}pQ2 Qe-father;Qe-id i;Qe-father (Q_NODE *)-1; //一个不可能出现的内存空间地址但不可用NULLQe pQ2;}}#ifdef _DEBUGdumpQueue(Qs);dumpDeep(n, pd);#endif //_DEBUG//路径搜索int w, //父节点的idu; //子节点的idpQ1 Qs;// 利用队列进行层级遍历while (Qe ! pQ1){if ( 0 pQ1-id )pQ1 pQ1-father;w pQ1-id;// 遍历w的子节点for (i ph[w-1]; i ph[w]; i){u pl[i];if (-1 pd[u]) // 找到换乘通路{// ... 输出换乘通路printf((%d), pd[w]);printf(%d, u);Q_NODE *path pQ1;while ((Q_NODE *)-1 ! path){printf( - %d, path-id);path path-father;}printf(\n);}else if (0 pd[u] //未到达节点|| pd[w] 1 pd[u] ) //已达但属同一层{if (NULL Qe-father) //扩充队列{Qe-id 0;Qe-father queue_alloc(_BUF_SIZE_);Qe Qe-father; //跳过缓冲区末尾的节点}//添加节点pQ2 Qe-father;Qe-id u;Qe-father pQ1;Qe pQ2;//标记换乘深度pd[u] pd[w] 1;}}#ifdef _DEBUGdumpQueue(Qs);dumpDeep(n, pd);#endif //_DEBUG//步进到下一节点pQ1;}//释放队列queue_free(Qs, _BUF_SIZE_);}int main(int argc, char* argv[]){// 打开输入文件FILE *in;if (argc 2)in fopen(Input.txt, r);elsein fopen(argv[1], r);if (NULL in){fprintf(stderr, Cannot open input file.\n);return 1;}// 读取输入文件到邻接压缩表中int num_node;vector h; //邻接压缩表描述序列vector l; //邻接压缩表序列即可直达站点列表vector mark; //节点到达标记序列if (fscanf(in, %d\n, num_node)){assert(num_node2);h.resize(num_node1);h[0] 0;for (int i0; i{int num_arrival;fscanf(in, %d, num_arrival);assert(num_arrival0);h[i1] num_arrival h[i];l.resize(h[i1]);for (int jh[i]; j{int id_node;fscanf(in, %d, id_node);l[j] id_node-1;}}}// 关闭输入文件fclose(in);// 调用函数搜索可行路径{int n h.size() - 1;int *ph new int[h.size()];int *pl new int[l.size()];copy(h.begin(), h.end(), ph);copy(l.begin(), l.end(), pl);for (int i0; ipl[i] pl[i] 1;// search_change(n, ph, pl, 1, 10);// search_change(n, ph, pl, 5, 10);printf(\n);int *pd new int[h.size()];memset(pd, 0, h.size() * 4);pd[1] 1;pd[5] 1;pd[10] -1;search_change(n, ph, pl, pd);delete[] pd;delete[] ph;delete[] pl;}// 搜索可行路径int n_start 0; //出发节点int n_end 11; //目的节点// 打开输出文件FILE *out;out fopen(./Output.txt, w);// 算法{mark.resize(h.size()-1);{for (int i0; ivector pair Q; //队列存储路径搜索树记录节点序号和父节点在本队列中的位置mark[n_start] 0;Q.push_back(make_pair(n_start,-1));for (int i0; i{int w Q[i].first;// 遍历w的直达节点for (int jh[w]; j{int u l[j];if (u n_end) { //存在换乘通路// 输出换乘通路//利用w的父节点在队列中的位置进行上溯找到换乘路径fprintf(out, %d: %d,%d,%d,%d,%d\n,mark[w] 1, u,w,Q[Q[i].second].first);//Q[Q[Q[i].second].second].first,Q[Q[Q[Q[i].second].second].second].first);}else if (mark[u] -1) { //未到达节点Q.push_back(make_pair(u,i)); //子节点入栈并记录其父节点在队列中的位置mark[u] mark[w] 1; //记录当前换乘深度}else if (mark[u] mark[w] 1) {Q.push_back(make_pair(u,i));}}}}// 测试输入部分的正确性#ifdef _DEBUG{assert( out ! NULL );fprintf(out, %d\n, h.size()-1);for (int i0; i{fprintf(out, (%d) , i 1);for (int jh[i]; jfprintf(out, %d , l[j] 1);fprintf(out, \n);}}#endif// 关闭输出文件fclose(out);return 0;}} // extern C《Input.txt》124 3 4 2 52 8 12 9 72 6 113 8 2 32 9 102 10 111 122 10 121 121 122 5 8《output.txt》3: 11,8,2,0,03: 11,10,3,0,03: 11,7,1,0,03: 11,7,4,0,04: 11,9,8,0,04: 11,9,6,0,04: 11,9,5,0,0
