int* queue = calloc(n, sizeof(int)); 有“void*”类型的值不能用于初始化“int“类型的实体的错误
时间: 2023-08-15 20:06:46 浏览: 52
这个错误是因为 `calloc` 函数返回的是 `void*` 类型的指针,需要进行强制类型转换成 `int*` 类型的指针才能进行赋值。可以将代码修改为:
```
int* queue = (int*)calloc(n, sizeof(int));
```
或者使用 `malloc` 函数进行内存分配,因为 `malloc` 返回的是 `void*` 类型的指针,不需要进行强制类型转换。代码如下:
```
int* queue = malloc(n * sizeof(int));
```
相关问题
优先队列求0-1背包c语言输出最优解
以下是使用优先队列求解0-1背包问题并输出最优解的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 优先队列结构体
typedef struct {
int value; // 节点价值
int weight; // 节点重量
int level; // 节点层数
} Node;
// 用于比较节点优先级的函数
int cmp(const void* a, const void* b) {
const Node* nodeA = (const Node*)a;
const Node* nodeB = (const Node*)b;
double priorityA = (double)nodeA->value / nodeA->weight;
double priorityB = (double)nodeB->value / nodeB->weight;
if (priorityA < priorityB) {
return 1;
} else if (priorityA > priorityB) {
return -1;
} else {
return 0;
}
}
// 求解0-1背包问题并输出最优解
void knapsack(int n, int capacity, int* values, int* weights) {
// 初始化优先队列
Node* queue = (Node*)malloc(n * sizeof(Node));
for (int i = 0; i < n; i++) {
queue[i].value = values[i];
queue[i].weight = weights[i];
queue[i].level = 0;
}
qsort(queue, n, sizeof(Node), cmp);
// 初始化最优解
int bestValue = 0;
int* bestItems = (int*)calloc(n, sizeof(int));
// 迭代搜索
while (1) {
// 取出队首节点
Node node = queue[0];
if (node.level == n) { // 搜索到叶子节点
if (node.value > bestValue) {
bestValue = node.value;
for (int i = 0; i < n; i++) {
bestItems[i] = (node.weight >> i) & 1;
}
}
} else {
// 扩展左儿子节点(不选当前物品)
Node left = node;
left.level = node.level + 1;
left.weight -= weights[left.level - 1];
queue[0] = left;
qsort(queue, n, sizeof(Node), cmp);
// 扩展右儿子节点(选当前物品)
Node right = node;
right.level = node.level + 1;
queue[n - 1] = right;
qsort(queue, n, sizeof(Node), cmp);
}
// 判断是否需要终止搜索
if (queue[0].value + (capacity - queue[0].weight) * (double)queue[0].value / queue[0].weight <= bestValue) {
break;
}
}
// 输出最优解
printf("Best value: %d\n", bestValue);
printf("Best items: ");
for (int i = 0; i < n; i++) {
printf("%d ", bestItems[i]);
}
printf("\n");
// 释放内存
free(queue);
free(bestItems);
}
// 测试
int main() {
int n = 5;
int capacity = 10;
int values[] = {6, 3, 5, 4, 6};
int weights[] = {2, 2, 6, 5, 4};
knapsack(n, capacity, values, weights);
return 0;
}
```
该代码使用优先队列来实现分支限界搜索,利用贪心算法对节点进行排序,每次取出优先级最高的节点进行扩展。在搜索过程中,维护当前最优解,并在搜索结束后输出最优解。
用C++完整代码解决:有一个含n个顶点(顶点编号为0~n-1)的带权图,用邻接矩阵数组A表示,采用分枝限界法求从起点s到目标点t的最短路径长度,以及具有最短路径长度的路径条数
### 回答1:
以下是使用C++实现的代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 100;
int n, s, t;
int A[MAXN][MAXN];
int dis[MAXN];
int cnt[MAXN];
bool vis[MAXN];
struct Node {
int u, d;
bool operator < (const Node &rhs) const {
return d > rhs.d;
}
};
int dijkstra() {
memset(dis, INF, sizeof(dis));
memset(cnt, 0, sizeof(cnt));
memset(vis, false, sizeof(vis));
dis[s] = 0;
cnt[s] = 1;
priority_queue<Node> q;
q.push({s, 0});
while (!q.empty()) {
Node cur = q.top();
q.pop();
int u = cur.u;
if (vis[u]) continue;
vis[u] = true;
for (int v = 0; v < n; v++) {
if (A[u][v] == INF) continue;
if (dis[v] > dis[u] + A[u][v]) {
dis[v] = dis[u] + A[u][v];
cnt[v] = cnt[u];
q.push({v, dis[v]});
} else if (dis[v] == dis[u] + A[u][v]) {
cnt[v] += cnt[u];
}
}
}
return dis[t];
}
int main() {
cin >> n >> s >> t;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> A[i][j];
if (A[i][j] == -1) A[i][j] = INF;
}
}
int ans = dijkstra();
cout << ans << endl;
cout << cnt[t] << endl;
return 0;
}
```
其中,`dis[i]`表示起点到点i的最短路径长度,`cnt[i]`表示起点到点i的最短路径条数。在Dijkstra算法中,如果当前节点u的最短路径长度加上边权比dis[v]小,则更新dis[v]和cnt[v];如果相等,则将cnt[u]加到cnt[v]上。最终,dis[t]即为起点到目标点的最短路径长度,cnt[t]即为具有最短路径长度的路径条数。
### 回答2:
分枝限界法是一种用来解决最优化问题的算法,在求解图的最短路径问题时也可以采用。下面是使用C语言编写的完整代码,可以求解带权图中从起点s到目标点t的最短路径长度,并统计具有最短路径长度的路径条数。
```c
#include <stdio.h>
#define MAX 100
#define INF 99999
int n; // 图的顶点数量
int A[MAX][MAX]; // 邻接矩阵表示的图
int s, t; // 起始点和目标点
int visited[MAX]; // 记录顶点是否被访问
int minLen; // 最短路径长度
int count; // 记录具有最短路径长度的路径条数
void branchAndBound(int u, int len) {
int i;
visited[u] = 1; // 标记当前节点已经被访问
if (u == t) { // 当前节点是目标节点
if (len < minLen) {
minLen = len;
count = 1;
} else if (len == minLen) {
count++;
}
} else {
for (i = 0; i < n; i++) {
if (A[u][i] != INF && !visited[i]) { // 当前节点能够到达的未访问过的节点
if (len + A[u][i] < minLen) { // 优化:剪枝操作
branchAndBound(i, len + A[u][i]);
}
}
}
}
visited[u] = 0; // 回溯,恢复节点的未访问状态
}
int main() {
int i, j;
printf("请输入图的顶点数量:");
scanf("%d", &n);
printf("请输入图的邻接矩阵:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &A[i][j]);
if (A[i][j] == 0) { // 0 表示不可达
A[i][j] = INF;
}
}
}
printf("请输入起点和目标点的编号:");
scanf("%d %d", &s, &t);
for (i = 0; i < n; i++) {
visited[i] = 0; // 初始化visited数组
}
minLen = INF;
count = 0;
branchAndBound(s, 0);
printf("最短路径长度为:%d\n", minLen);
printf("具有最短路径长度的路径条数为:%d\n", count);
return 0;
}
```
该代码使用递归的方式实现了分枝限界法,其中使用了剪枝操作来提高算法效率。首先输入图的顶点数和邻接矩阵,然后输入起点和目标点的编号,最后通过调用branchAndBound函数求解最短路径长度和路径条数。输出结果即为所求的最短路径长度和具有最短路径长度的路径条数。
### 回答3:
首先,我们需要定义一个结构体,用来表示图的边的信息:
```c
typedef struct {
int start; // 边的起点
int end; // 边的终点
int weight; // 边的权重
} Edge;
```
接下来,我们可以使用以下函数来实现分枝限界法来求解从起点s到目标点t的最短路径长度和路径条数:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_INT 99999
int n; // 顶点个数
int s; // 起点
int t; // 目标点
int minDistance; // 最短路径长度
int minPathCount; // 具有最短路径长度的路径条数
int **graph; // 邻接矩阵数组
void dfs(int current, int distance, int pathCount, int *visited) {
if (current == t) {
// 当前节点为目标节点
if (distance < minDistance) {
// 更新最短路径长度和路径条数
minDistance = distance;
minPathCount = pathCount;
} else if (distance == minDistance) {
// 更新路径条数
minPathCount += pathCount;
}
return;
}
for (int i = 0; i < n; i++) {
if (graph[current][i] != MAX_INT && !visited[i]) {
// 未访问过的相邻节点
visited[i] = 1;
dfs(i, distance + graph[current][i], pathCount, visited);
visited[i] = 0;
}
}
}
void shortestPath() {
int *visited = (int *)calloc(n, sizeof(int));
visited[s] = 1;
dfs(s, 0, 1, visited);
free(visited);
}
int main() {
n = 5; // 顶点个数
s = 0; // 起点
t = 4; // 目标点
graph = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
graph[i] = (int *)malloc(n * sizeof(int));
for (int j = 0; j < n; j++) {
graph[i][j] = MAX_INT; // 初始化邻接矩阵
}
}
// 添加图的边的信息
Edge edges[] = {{0, 1, 2}, {0, 2, 4}, {1, 2, 1}, {1, 3, 2}, {2, 3, 1}, {2, 4, 4}, {3, 4, 3}};
int num_edges = sizeof(edges) / sizeof(edges[0]);
for (int i = 0; i < num_edges; i++) {
graph[edges[i].start][edges[i].end] = edges[i].weight;
}
minDistance = MAX_INT;
minPathCount = 0;
shortestPath();
printf("最短路径长度:%d\n", minDistance);
printf("具有最短路径长度的路径条数:%d\n", minPathCount);
for (int i = 0; i < n; i++) {
free(graph[i]);
}
free(graph);
return 0;
}
```
以上代码会输出从起点s到目标点t的最短路径长度和具有最短路径长度的路径条数。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)