2 qq 36958841 qq_36958841 于 2017.01.03 15:35 提问

数据结构问题 求大神带

求数据结构的迷宫问题和农夫过河问题 和一元稀疏矩阵的加减法问题 急

3个回答

sinat_36899414
sinat_36899414   2017.01.03 16:31
已采纳

正好我今天也是那个课设
农夫过河
#include
#include
using namespace std;
#define VertexNum 16 //最大顶点数
typedef struct // 图的顶点
{
int farmer; // 农夫
int wolf; // 狼
int sheep; // 羊
int veget; // 白菜
}Vertex;
typedef struct
{
int vertexNum; // 图的当前顶点数
Vertex vertex[VertexNum]; // 顶点向量(代表顶点)
bool Edge[VertexNum][VertexNum]; // 邻接矩阵. 用于存储图中的边,其矩阵元素个数取决于顶点个数,与边数无关
}AdjGraph; // 定义图的邻接矩阵存储结构
bool visited[VertexNum] = {false}; // 对已访问的顶点进行标记(图的遍历)
int retPath[VertexNum] = {-1}; // 保存DFS搜索到的路径,即与某顶点到下一顶点的路径
// 查找顶点(F,W,S,V)在顶点向量中的位置
int locate(AdjGraph *graph, int farmer, int wolf , int sheep, int veget)
{
// 从0开始查找
for (int i = 0; i < graph->vertexNum; i++)
{
if ( graph->vertex[i].farmer == farmer && graph->vertex[i].wolf == wolf
&& graph->vertex[i].sheep == sheep && graph->vertex[i].veget == veget )
{
return i; //返回当前位置
}
}
return -1; //没有找到此顶点
}
// 判断目前的(F,W,S,V)是否安全
bool isSafe(int farmer, int wolf, int sheep, int veget)
{
//当农夫与羊不在一起时,狼与羊或羊与白菜在一起是不安全的
if ( farmer != sheep && (wolf == sheep || sheep == veget) )
{
return false;
}
else
{
return true; // 安全返回true
}
}
// 判断状态i与状态j之间是否可转换
bool isConnect(AdjGraph *graph, int i, int j)
{
int k = 0;
if (graph->vertex[i].wolf != graph->vertex[j].wolf)
{
k++;
}
if (graph->vertex[i].sheep != graph->vertex[j].sheep)
{
k++;
}
if (graph->vertex[i].veget != graph->vertex[j].veget)
{
k++;
}
// 以上三个条件不同时满足两个且农夫状态改变时,返回真, 也即农夫每次只能带一件东西过桥
if (graph->vertex[i].farmer != graph->vertex[j].farmer && k <= 1)
{
return true;
}
else
{
return false;
}
}
// 创建连接图
void CreateG(AdjGraph *graph)
{
int i = 0;
int j = 0;
// 生成所有安全的图的顶点
for (int farmer = 0; farmer <= 1; farmer++)
{
for (int wolf = 0; wolf <= 1; wolf++)
{
for (int sheep = 0; sheep <= 1; sheep++)
{
for (int veget = 0; veget <= 1; veget++)
{
if (isSafe(farmer, wolf, sheep, veget))
{
graph->vertex[i].farmer = farmer;
graph->vertex[i].wolf = wolf;
graph->vertex[i].sheep = sheep;
graph->vertex[i].veget = veget;
i++;
}
}
}
}
}
// 邻接矩阵初始化即建立邻接矩阵
graph->vertexNum = i;
for (i = 0; i < graph->vertexNum; i++)
{
for (j = 0; j < graph->vertexNum; j++)
{
// 状态i与状态j之间可转化,初始化为1,否则为0
if (isConnect(graph, i, j))
{
graph->Edge[i][j] = graph->Edge[j][i] = true;
}
else
{
graph->Edge[i][j] = graph->Edge[j][i] = false;
}
}
}
return;
}
// 判断在河的那一边
string judgement(int state)
{
return (0 == state) ? "左岸" : "右岸" ;
}
// 输出从u到v的简单路径,即顶点序列中不重复出现的路径
void printPath(AdjGraph *graph, int start, int end)
{
int i = start;
cout << "farmer" << ", wolf" << ", sheep" << ", veget" << endl;
while (i != end)
{
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
i = retPath[i];
}
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
}
// 深度优先搜索从u到v的简单路径 //DFS--Depth First Search
void dfsPath(AdjGraph *graph, int start, int end)
{
int i = 0;
visited[start] = true; //标记已访问过的顶点
if (start == end)
{
return ;
}
for (i = 0; i < graph->vertexNum; i++)
{
if (graph->Edge[start][i] && !visited[i])
{
retPath[start] = i;
dfsPath(graph, i, end);
}
}
}
int main()
{
AdjGraph graph;
CreateG(&graph);
int start = locate(&graph, 0, 0, 0, 0);
int end = locate(&graph, 1, 1, 1, 1);
dfsPath(&graph, start, end);
if (visited[end]) // 有结果
{
printPath(&graph, start, end);
return 0;
}
return -1;
}

qq_36958841
qq_36958841 回复攻城猿bilibili: 做过迷宫吗?
一年多之前 回复
sinat_36899414
sinat_36899414   2017.01.03 16:32

头文件是#include

sinat_36899414
sinat_36899414   2017.01.03 16:37

一发送就自动没了iostream

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
fifo to uart
VHDL 带fifo的uart 源代码,求大神帮忙修改。
易语言钓鱼源码
求大神买走 求大神买走 易语言钓鱼源码
求最大子序列和问题(读《数据结构与算法分析——C语言描述》有感)
根据《数据结构与算法分析——C语言描述》中的“最大子序列和”问题来看如何分析算法。
【数据结构】求节点的哈夫曼的带权路径长度
题目来源:北航14级6系数据结构作业 【问题描述】  已知输入一串正整数,正整数之间用空格键分开,请建立一个哈夫曼树,以输入的数字为叶节点,求这棵哈夫曼树的带权路径长度。 【输入形式】  首先输入正整数的个数,然后接下来为接下来的正整数,正整数个数不超过10个 【输出形式】  输出相应的权值 【样例输入】  5 4 5 6 7 8 【样例输出】  69
数据结构看书笔记(十)—— 求最短路径问题之--迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法
最短路径: 对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点是源点,最后一个顶点是终点。 对于非网图来说,完全可以理解为所有边的权值都为1的网。 两种算法:迪杰斯特拉(Dijkstra)算法,弗洛伊德(Floyd)算法。 /*迪杰斯特拉算法实现*/ #define MAXVEX 9 #define INFINITY 65535 t
[数据结构]求解迷宫最短路径问题
一、问题概述        之前,我们了解了如何实现迷宫问题(对于迷宫只有一个出口可以通的情况),事实上我们的迷宫有多个出口,对于每条路径来说,有长有短,所以在这里,我们讨论一下迷宫的最短路径,即迷宫路径的最优解问题。 二、解决方案        对于这样一个迷宫:        注:数字为0的表示可以通过,数字为1的表示不可
求最大子列和问题(浙江大学数据结构)
问题陈述:   给定N个整数的序列{A1, A2, ... , AN},求函数ƒ(i, j) = max{0, Ai + Ai+1 + ... + Aj}(1   问题分析:   求给定数列的最大子列和。 方法一:暴力求解  :遍历每个子序列。时间复杂度T(N)=N3。 int MaxSubseqSum1(int A[],int n) { int i,j
【数据结构】递归求解迷宫问题
数据结构 递归求解迷宫问题 参考代码如下: /* 名称:递归求解迷宫问题 编译环境:VC++ 6.0 日期: 2014年4月1日 */ #include #include // 迷宫坐标位置类型 struct PosType { int x; // 行值 int y; // 列值 }; #define MAXLENGTH 25 // 设迷宫的最大行列为25 typedef
数据结构实践——“求两集合交集”的一个错解分析
本文点评一位学生对基于线性表存储集合,然后对集合进行求并运算的错解,供学习者参考。【项目 - 求集合并集】   假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即线性表中的数据元素即为集合中的成员。设计算法,用函数unionList(List LA, List LB, List &LC )函数实现该算法,求一个新的集合C=A∪B,即将两个集合的并集放在线性表LC中。 提示
数据结构---图(求关节点)
// Find Articulation Point.cpp : Defines the entry point for the console application. /*-----CODE FOR FUN--------------- -------CREATED BY Dream_Whui------ -------2015-2-13--------------------*/ #inc