我要投稿
投稿指南
RSS订阅文中使用的queue_alloc和queue_free函数是洒家自己设计的“简易空间配置器”的C 语言实现版本，关于简易空间配置器的详细信息，请参考《简易空间配置器》(http://blog.csdn.net/bfbd/archive/2004/06/22/22743.aspx)一文。
#include "stdafx.h"
#include <assert.h>
#include <vector>
#include <stack>
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 (_i=0; _i<n+1; _i++)
printf("%d ", ph[_i]);
printf("\n");
printf("pl[]: ");
for (_i=0; _i<ph[n]; _i++)
printf("%d ", pl[_i]);
printf("\n");
}
void dumpDeep(int n, int *pd)
{
int _i;
printf("pd[]: ");
for (_i=0; _i<n+1; _i++)
printf("%d ", pd[_i]);
printf("\n");
}
void dumpQueue(Q_NODE *Qs)
{
Q_NODE *_pQ;
printf("Q: ");
for ( _pQ=Qs; (_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[i+1]);
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: 邻接压缩表描述序列(长度为n+1)
// *pl: 邻接压缩表序列(长度为ph[n])
// *pd: 换乘深度(长度为n+1,pd[0]不用)，0 表示未达站点，1 表示出发站，-1 表示终点站。
// return:
{
#ifdef _DEBUG
dumpMap(n, ph, pl);
dumpDeep(n, pd);
#endif //_DEBUG
assert(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; //一个不可能出现的内存空间地址，但不可用NULL
Qe = pQ2;
}
}
#ifdef _DEBUG
dumpQueue(Qs);
dumpDeep(n, pd);
#endif //_DEBUG
//路径搜索
int w, //父节点的id
u; //子节点的id
pQ1 = 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 _DEBUG
dumpQueue(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");
else
in = fopen(argv[1], "r");
if (NULL == in)
{
fprintf(stderr, "Cannot open input file.\n");
return 1;
}
// 读取输入文件到邻接压缩表中
int num_node;
vector<int> h; //邻接压缩表描述序列
vector<int> l; //邻接压缩表序列，即可直达站点列表
vector<int> mark; //节点到达标记序列
if (fscanf(in, "%d\n", &num_node))
{
assert(num_node>2);
h.resize(num_node+1);
h[0] = 0;
for (int i=0; i<num_node; ++i)
{
int num_arrival;
fscanf(in, "%d", &num_arrival);
assert(num_arrival>0);
h[i+1] = num_arrival + h[i];
l.resize(h[i+1]);
for (int j=h[i]; j<h[i+1]; ++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 i=0; i<l.size(); i++)
pl[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 i=0; i<mark.size(); mark[i]=-1, ++i);}
vector< pair<int,int> > Q; //队列，存储路径搜索树，记录节点序号和父节点在本队列中的位置
mark[n_start] = 0;
Q.push_back(make_pair(n_start,-1));
for (int i=0; i<Q.size(); ++i)
{
int w = Q[i].first;
// 遍历w的直达节点
for (int j=h[w]; j<h[w+1]; ++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 i=0; i<h.size()-1; ++i)
{
fprintf(out, "(%d) ", i + 1);
for (int j=h[i]; j<h[i+1]; ++j)
fprintf(out, "%d ", l[j] + 1);
fprintf(out, "\n");
}
}
#endif
// 关闭输出文件
fclose(out);
return 0;
}
} // extern "C"
《Input.txt》
12
4 3 4 2 5
2 8 1
2 9 7
2 6 11
3 8 2 3
2 9 10
2 10 11
1 12
2 10 12
1 12
1 12
2 5 8
《output.txt》
3: 11,8,2,0,0
3: 11,10,3,0,0
3: 11,7,1,0,0
3: 11,7,4,0,0
4: 11,9,8,0,0
4: 11,9,6,0,0
4: 11,9,5,0,0
