| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
 跟大牛学C++学算法数据结构

已结贴   问题点数：30  回复次数：3

#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;

const int MAXQSIZE = 100;

template<class ElemType>
class SqQueue
{
private:
ElemType *elem;
int rear; //队尾指针
int front; //队头指针
int queueize;
int count;
public:
SqQueue(int ms = 0);
~SqQueue()
{
QueueDestroy();
}
bool QueueDestroy();
bool QueueClear( );
int StackLength() const
{
return (rear - front + queueize)%queueize;
}
bool QueueisEmpty() const
{
return count == 0;
}
bool EnQueue(ElemType &e);
bool DeQueue(ElemType &e);
void QueueTraverse() const;
};
//初始化
template<class ElemType>
SqQueue<ElemType>::SqQueue(int ms)
{
if(ms == 0) ms = MAXQSIZE;
elem = new ElemType[ms];
if(!elem) exit(1);
queueize = ms;
count = 0;
front = rear= 0;
}
//销毁
template<class ElemType>
bool SqQueue<ElemType>::QueueDestroy()
{
if(!elem) return false;
free(elem);
front = rear = 0;
queueize = 0;
count = 0;
return true;
}
//空表
template<class ElemType>
bool SqQueue<ElemType>::QueueClear( )
{
if(!elem) return false;
free(elem);
front = 0;
rear = 0;
return true;
}
//返回队头元素
template<class ElemType>
{
if(front == rear) return false;
e = elem[front];
return true;
}
//入队
template<class ElemType>
bool SqQueue<ElemType>::EnQueue(ElemType &e)
{
if((rear+1)%queueize==front)
return false;
elem[rear] = e;
rear = (rear+1)%queueize;
count++;
return true;
}
//出队
template<class ElemType>
bool SqQueue<ElemType>::DeQueue(ElemType &e)
{
if(front == rear) return false;
e = elem[front];
front = (front+1) % queueize;
count--;
return true;
}
//遍历
template<class ElemType>
void SqQueue<ElemType>::QueueTraverse() const
{
int i;
int length = (rear - front + queueize)%queueize;
for(i = front; i < length; i++)
cout << elem[i];
cout << endl;
}

int goat(int st)
{
return (st&0x01)!=0;
}
int cabbage(int st)
{
return (st&0x02)!=0;
}
int wolf(int st)
{
return (st&0x04)!=0;
}
int farmer(int st)
{
return (st&0x08)!=0;
}

int safe(int st)
{
if((goat(st)==cabbage(st))&&(goat(st)!=farmer(st)))
return 0;
if((goat(st)==wolf(st))&&(goat(st)!=farmer(st)))
return 0;
return 1;
}

void print(char*str)
{
int size = strlen(str);
int k = 4-size;
while(k)
{
cout << "0";
k--;
}
cout << str << endl;
}

template<class ElemType>
void farmerProblem(SqQueue<ElemType> &S)
{
int mover, i, st, st_new;
int route[16];
ElemType e0;
e0 = 0x00;
S.EnQueue(e0);
for(i = 0; i < 16; i++)
{
route[i] = -1;
}
route[0] = 0;
while(!S.QueueisEmpty()&&route[15]==-1)
{
S.DeQueue(e0);
for(mover = 1; mover <= 8; mover <<= 1)
{
if(farmer(st)==(0!=(st&mover)))
{
st_new = st^(0x08|mover);
}
if(route[st_new] == -1&&safe(st_new))
{
route[st_new] = st;
S.EnQueue(st_new);
}
}
}
char*str;
if(route[15] != -1)
for(st = 15; st >= 0; st = route[st])
{
itoa(st, str, 2);
print(str);
if(st == 0) break;
}
}

int main()
{
SqQueue<int> S;
farmerProblem(S);
return 0;
}
得分:0

得分:30

http://blog.yuccn.net/archives/211.html

[此贴子已经被作者于2017-11-10 15:40编辑过]

http://blog.yuccn. net
得分:0

[此贴子已经被作者于2017-11-10 17:50编辑过]

http://blog.yuccn. net
• 4
• 1/1页
• 1