指针的内存泄漏的指针 [英] Memory leak of pointer to pointer
本文介绍了指针的内存泄漏的指针的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我使用的是Dijkstra算法用邻接表<一个href=\"http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-re$p$psentation/\"相对=本网页nofollow的>。因为我想建立不同的图形和计算最短路径很多次，我添加一些免费命令来释放内存。但是，内存使用量仍增加多次迭代后
下面是我修改code：
// C / C ++程序邻接Dijkstra的最短路径算法
图形//列表重新presentation＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆limits.h中GT;//一个结构重新present在邻接表的节点
结构AdjListNode
{
INT DEST;
诠释权重;
结构AdjListNode *接下来的;
};//一个结构重新present邻接LIAT
结构AdjList
{
结构AdjListNode *头; //指针头名单的节点
};//一个结构重新present图。有图有邻接表的数组。
//数组的大小将V（图中的顶点数）
结构图
{
INT伏;
结构AdjList *阵列;
};//一个效用函数来创建一个新的邻接表节点
结构AdjListNode * newAdjListNode（INT DEST，诠释重量）
{
结构AdjListNode * newNode =
（结构AdjListNode *）malloc的（的sizeof（结构AdjListNode））;
newNode-＆GT; DEST = DEST;
newNode-＆GT;体重=体重;
newNode-＆gt;接着= NULL;
返回newNode;
}//创建V顶点的图的实用功能
结构图* createGraph（INT V）
{
结构图*图=（结构图*）malloc的（的sizeof（结构图））;
graph-＆GT; V =; //创建邻接列表的阵列。阵列的大小将为V
graph-＆GT;数组=（结构AdjList *）malloc的（V *的sizeof（结构AdjList））; //初始化每个邻接表通过使头部NULL作为空
的for（int i = 0; I＆LT;伏; ++ I）
graph-＆GT;阵列[我]。头= NULL; 返回图;
}//添加一个边无向图
无效addEdge（图结构图*，诠释SRC，诠释DEST，诠释重量）
{
//添加边缘从src复制到dest中。一个新节点被添加到邻接
// SRC的列表。节点是在开始时加入
结构AdjListNode * newNode = newAdjListNode（DEST，重量）;
newNode-＆gt;接下来= graph-＆GT;阵[来源]。头;
graph-＆GT;阵[来源]。头= newNode; //由于是无向图，从DEST添加边缘也为src
newNode = newAdjListNode（SRC，重量）;
newNode-＆gt;接下来= graph-＆GT;阵[地址]。头;
graph-＆GT;阵[地址]。头= newNode;
}//结构重新present最小堆节点
结构MinHeapNode
{
INT伏;
INT DIST;
};//结构重新present最小堆
结构MinHeap
{
INT大小; //堆节点present数当前
INT能力; //最小堆容量
INT * POS; //这是需要decreaseKey（）
结构MinHeapNode **阵列;
};//一个效用函数来创建一个新的最小堆节点
结构MinHeapNode * newMinHeapNode（INT V，INT DIST）
{
结构MinHeapNode * minHeapNode =
（结构MinHeapNode *）malloc的（的sizeof（结构MinHeapNode））;
minHeapNode-＆GT; V =;
minHeapNode-＆GT; DIST = DIST;
返回minHeapNode;
}//一个效用函数来创建一个最小堆
结构MinHeap * createMinHeap（INT容量）
{
结构MinHeap * minHeap =
（结构MinHeap *）malloc的（的sizeof（结构MinHeap））;
minHeap-＆GT; POS =（INT *）malloc的（容量*的sizeof（INT））;
minHeap-＆GT;大小= 0;
minHeap-＆GT;容量=能力;
minHeap-＆GT;数组=
（结构MinHeapNode **）的malloc（容量*的sizeof（结构MinHeapNode *））;
返回minHeap;
}//一个效用函数来交换最小堆的两个节点。需要分钟heapify
无效swapMinHeapNode（结构MinHeapNode **一，结构MinHeapNode ** B）
{
结构MinHeapNode * T = *一个;
* A = * B;
* B = T;
}//一个标准功能heapify在给定的IDX
//他们交换时，此功能还更新节点的位置。
//需要为位置decreaseKey（）
无效minHeapify（结构MinHeap * minHeap，INT IDX）
{
诠释最小，左，右;
最小= IDX;
左= 2 * IDX + 1;
右= 2 * IDX + 2; 如果（左＆LT; minHeap-＆GT;大小和放大器;＆安培;
minHeap-＆GT;阵[左] - ＆GT;＆DIST LT; minHeap-＆GT;阵[最小] - ＆GT; DIST）
最小=左; 如果（右LT; minHeap-＆GT;大小和放大器;＆安培;
minHeap-＆GT;阵[右] - ＆GT;＆DIST LT; minHeap-＆GT;阵[最小] - ＆GT; DIST）
最小=权利; 如果（最小！= IDX）
{
//节点在最小堆被交换
MinHeapNode * smallestNode = minHeap-＆GT;阵[最小];
MinHeapNode * idxNode = minHeap-＆GT;阵列[IDX]; //交换位置
minHeap-＆GT; POS [smallestNode-＆GT; V] = IDX;
minHeap-＆GT; POS [idxNode-＆GT; V] =最小; //交换节点
swapMinHeapNode（安培; minHeap-＆GT;阵[最小]和安培; minHeap-＆GT;阵列[IDX]）; minHeapify（minHeap，最小的）;
}
}//检查一个效用函数如果给定的minHeap是ampty与否
INT的isEmpty（结构MinHeap * minHeap）
{
返回minHeap-＆GT;大小== 0;
}//标准函数提取堆最低点
结构MinHeapNode * extractMin（结构MinHeap * minHeap）
{
如果（的isEmpty（minHeap））
返回NULL; //存储根节点
结构MinHeapNode *根= minHeap-＆GT;阵[0]; //替换最后一个节点根节点
结构MinHeapNode * lastNode = minHeap-＆GT;阵[minHeap-＆GT;大小 - 1];
minHeap-＆GT;数组[0] = lastNode; //最后一个节点的位置更新
minHeap-＆GT; POS [根 - ＆GT; V] = minHeap-＆GT;大小-1;
minHeap-＆GT; POS [lastNode-＆GT; V] = 0; //减少堆大小和heapify根
--minHeap-＆GT;大小;
minHeapify（minHeap，0）; 返回根;
}//函数来decreasy一个给定的顶点v的DIST值。该功能
//使用POS []分钟堆得到节点的最小堆目前指数
无效decreaseKey（结构MinHeap * minHeap，INT V，INT DIST）
{
//获取诉堆数组的索引
INT I = minHeap-＆GT; POS [V] //获取节点，并更新其测距值
minHeap-＆GT;阵[I] - ＆GT; DIST = DIST; //旅行了，而完整的树没有hepified。
//这是一个O（LOGN）循环
而（I和;＆安培; minHeap-＆GT;阵[I] - ＆GT;＆DIST LT; minHeap-＆GT;阵列[（I - 1）/ 2] - ＆GT; DIST）
{
//交换与其父这个节点
minHeap-＆GT; POS [minHeap-＆GT;阵[Ⅰ] - GT; V] =（I-1）/ 2;
minHeap-＆GT; POS [minHeap-＆GT;阵列[（I-1）/ 2] - GT; V] = I;
swapMinHeapNode（安培; minHeap-＆GT;阵列[我]，和放大器; minHeap-＆GT;阵列[（I - 1）/ 2]）; //移动到父索引
I =（I - 1）/ 2;
}
}//一个效用函数来检查，如果给定的顶点
//'V'是最小堆还是不
布尔isInMinHeap（结构MinHeap * minHeap，INT V）
{
如果（minHeap-＆GT; POS [V]＆LT; minHeap-＆GT;大小）
返回true;
返回false;
}//那calulates的最短路径的距离从SRC的所有主要功能
//顶点。这是一个O（ELogV）函数
无效的Dijkstra（图结构图*，诠释SRC）
{
INT V = graph-＆GT;伏; //获取图形顶点数量
INT DIST [V]; // DIST值用来挑斩最小重量边缘 // minHeap重新presents集E
结构MinHeap * minHeap = createMinHeap（V）; //初始化最小堆所有顶点。所有顶点的DIST值
为（中间体V = 0; V族伏; ++ⅴ）
{
DIST [V] = INT_MAX;
minHeap-＆GT;阵[V] = newMinHeapNode（V，DIST [V]）;
minHeap-＆GT; POS [V] = V;
} //使SRC顶点DIST值作为0，以便它首先抽取
minHeap-＆GT;阵[来源] = newMinHeapNode（SRC，DIST [来源]）;
minHeap-＆GT; POS [来源] = SRC;
DIST [SRC] = 0;
decreaseKey（minHeap，SRC，DIST [来源]）; //最初最小堆的大小等于V
minHeap-＆GT;大小= V; //在跟随着循环，分堆包含所有节点
//它的最短距离尚未最终确定。
而（！的isEmpty（minHeap））
{
//提取具有最小距离值的顶点
结构MinHeapNode * minHeapNode = extractMin（minHeap）;
INT U = minHeapNode-＆GT;伏; //存储提取顶点号 //到U所有相邻顶点移动（提取
//顶点），并更新其距离值
结构AdjListNode * pCrawl = graph-＆GT;阵[U]。头;
而（pCrawl！= NULL）
{
INT V = pCrawl-＆GT; DEST; //如果到v最短的距离还没有最终确定，并于v的距离
//通过u是低于其previously计算的距离
如果（isInMinHeap（minHeap，V）及和放大器; DIST [U] = INT_MAX和放大器;！＆安培;
pCrawl-＆GT;重量+ DIST [U]＆LT; DIST [V]）
{
DIST [V] = DIST [U] + pCrawl-＆GT;权重; 在最小堆也//更新的距离值
decreaseKey（minHeap，V，DIST [V]）;
}
pCrawl = pCrawl-＆gt;接下来，
}
} 免费（minHeap-＆GT; POS） 的for（int i = 0; I＆LT; minHeap-＆GT;大小;我++）{
免费（minHeap-＆GT;阵列[我]）;
} 免费（minHeap-＆GT;数组）;
免费（minHeap）;
}
//驱动程序来测试上述功能
诠释的main（）
{
//创建上面给出fugure图
INT V = 10000，T = 0;
而（T！= 10）{
结构图*图形= createGraph（V）;
的for（int i = 0; I＆LT; 5000;我++）{
对于（INT J = 5000; J＆LT; 10000; J ++）{
addEdge（图，0，I，I）;
addEdge（图中，I，J，I + J）;
}
}
迪杰斯特拉（曲线图中，0）; 免费（graph-＆GT;数组）;
免费（图）
Ť++;
} 返回0;
}
解决方案
您必须在年底这三行的主：
免费（graph-＆GT;数组）;
免费（图）
Ť++;
您需要释放前阵来释放阵列（邻接列表）的元素。三大行之前添加这个循环：
为（INT D = 0; D＆LT; graph-＆GT;伏;Ð++）
{
AdjListNode * P1 = graph-＆GT;阵[D]。。头，* P2;
而（p1）为
{
P2 = P1;
P1 = P 1 - ＆gt;接下来，
免费（P2）;
}
}
I am using the Dijkstra Algorithm with Adjacency List in this webpage. Since I want to build up different graphs and compute shortest paths many times, I add some "free" command to free the memory. However, the memory usage still increase after many iterations
Here are my modified code:
// C / C++ program for Dijkstra's shortest path algorithm for adjacency
// list representation of graph
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// A structure to represent a node in adjacency list
struct AdjListNode
{
int dest;
int weight;
struct AdjListNode* next;
};
// A structure to represent an adjacency liat
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};
// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
int V;
struct AdjList* array;
};
// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest, int weight)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}
// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by making head as NULL
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest, int weight)
{
// Add an edge from src to dest. A new node is added to the adjacency
// list of src. The node is added at the begining
struct AdjListNode* newNode = newAdjListNode(dest, weight);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// Since graph is undirected, add an edge from dest to src also
newNode = newAdjListNode(src, weight);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// Structure to represent a min heap node
struct MinHeapNode
{
int v;
int dist;
};
// Structure to represent a min heap
struct MinHeap
{
int size; // Number of heap nodes present currently
int capacity; // Capacity of min heap
int *pos; // This is needed for decreaseKey()
struct MinHeapNode **array;
};
// A utility function to create a new Min Heap Node
struct MinHeapNode* newMinHeapNode(int v, int dist)
{
struct MinHeapNode* minHeapNode =
(struct MinHeapNode*) malloc(sizeof(struct MinHeapNode));
minHeapNode->v = v;
minHeapNode->dist = dist;
return minHeapNode;
}
// A utility function to create a Min Heap
struct MinHeap* createMinHeap(int capacity)
{
struct MinHeap* minHeap =
(struct MinHeap*) malloc(sizeof(struct MinHeap));
minHeap->pos = (int *)malloc(capacity * sizeof(int));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array =
(struct MinHeapNode**) malloc(capacity * sizeof(struct MinHeapNode*));
return minHeap;
}
// A utility function to swap two nodes of min heap. Needed for min heapify
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)
{
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
// A standard function to heapify at given idx
// This function also updates position of nodes when they are swapped.
// Position is needed for decreaseKey()
void minHeapify(struct MinHeap* minHeap, int idx)
{
int smallest, left, right;
smallest = idx;
left = 2 * idx + 1;
right = 2 * idx + 2;
if (left < minHeap->size &&
minHeap->array[left]->dist < minHeap->array[smallest]->dist )
smallest = left;
if (right < minHeap->size &&
minHeap->array[right]->dist < minHeap->array[smallest]->dist )
smallest = right;
if (smallest != idx)
{
// The nodes to be swapped in min heap
MinHeapNode *smallestNode = minHeap->array[smallest];
MinHeapNode *idxNode = minHeap->array[idx];
// Swap positions
minHeap->pos[smallestNode->v] = idx;
minHeap->pos[idxNode->v] = smallest;
// Swap nodes
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
// A utility function to check if the given minHeap is ampty or not
int isEmpty(struct MinHeap* minHeap)
{
return minHeap->size == 0;
}
// Standard function to extract minimum node from heap
struct MinHeapNode* extractMin(struct MinHeap* minHeap)
{
if (isEmpty(minHeap))
return NULL;
// Store the root node
struct MinHeapNode* root = minHeap->array[0];
// Replace root node with last node
struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];
minHeap->array[0] = lastNode;
// Update position of last node
minHeap->pos[root->v] = minHeap->size-1;
minHeap->pos[lastNode->v] = 0;
// Reduce heap size and heapify root
--minHeap->size;
minHeapify(minHeap, 0);
return root;
}
// Function to decreasy dist value of a given vertex v. This function
// uses pos[] of min heap to get the current index of node in min heap
void decreaseKey(struct MinHeap* minHeap, int v, int dist)
{
// Get the index of v in heap array
int i = minHeap->pos[v];
// Get the node and update its dist value
minHeap->array[i]->dist = dist;
// Travel up while the complete tree is not hepified.
// This is a O(Logn) loop
while (i && minHeap->array[i]->dist < minHeap->array[(i - 1) / 2]->dist)
{
// Swap this node with its parent
minHeap->pos[minHeap->array[i]->v] = (i-1)/2;
minHeap->pos[minHeap->array[(i-1)/2]->v] = i;
swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);
// move to parent index
i = (i - 1) / 2;
}
}
// A utility function to check if a given vertex
// 'v' is in min heap or not
bool isInMinHeap(struct MinHeap *minHeap, int v)
{
if (minHeap->pos[v] < minHeap->size)
return true;
return false;
}
// The main function that calulates distances of shortest paths from src to all
// vertices. It is a O(ELogV) function
void dijkstra(struct Graph* graph, int src)
{
int V = graph->V;// Get the number of vertices in graph
int dist[V]; // dist values used to pick minimum weight edge in cut
// minHeap represents set E
struct MinHeap* minHeap = createMinHeap(V);
// Initialize min heap with all vertices. dist value of all vertices
for (int v = 0; v < V; ++v)
{
dist[v] = INT_MAX;
minHeap->array[v] = newMinHeapNode(v, dist[v]);
minHeap->pos[v] = v;
}
// Make dist value of src vertex as 0 so that it is extracted first
minHeap->array[src] = newMinHeapNode(src, dist[src]);
minHeap->pos[src] = src;
dist[src] = 0;
decreaseKey(minHeap, src, dist[src]);
// Initially size of min heap is equal to V
minHeap->size = V;
// In the followin loop, min heap contains all nodes
// whose shortest distance is not yet finalized.
while (!isEmpty(minHeap))
{
// Extract the vertex with minimum distance value
struct MinHeapNode* minHeapNode = extractMin(minHeap);
int u = minHeapNode->v; // Store the extracted vertex number
// Traverse through all adjacent vertices of u (the extracted
// vertex) and update their distance values
struct AdjListNode* pCrawl = graph->array[u].head;
while (pCrawl != NULL)
{
int v = pCrawl->dest;
// If shortest distance to v is not finalized yet, and distance to v
// through u is less than its previously calculated distance
if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX &&
pCrawl->weight + dist[u] < dist[v])
{
dist[v] = dist[u] + pCrawl->weight;
// update distance value in min heap also
decreaseKey(minHeap, v, dist[v]);
}
pCrawl = pCrawl->next;
}
}
free(minHeap->pos);
for (int i=0;i<minHeap->size;i++) {
free(minHeap->array[i]);
}
free(minHeap->array);
free(minHeap);
}
// Driver program to test above functions
int main()
{
// create the graph given in above fugure
int V = 10000,t=0;
while (t!=10) {
struct Graph* graph = createGraph(V);
for (int i=0; i<5000; i++) {
for(int j=5000;j<10000;j++){
addEdge(graph, 0, i, i);
addEdge(graph, i, j, i+j);
}
}
dijkstra(graph, 0);
free(graph->array);
free(graph);
t++;
}
return 0;
}
解决方案
You have these three lines at the end of your main:
free(graph->array);
free(graph);
t++;
You need to free the elements of the array (the adjacency lists) before freeing the array. Add this loop before the three lines:
for(int d=0; d<graph->V; d++)
{
AdjListNode *p1=graph->array[d].head, *p2;
while(p1)
{
p2=p1;
p1=p1->next;
free(p2);
}
}
这篇关于指针的内存泄漏的指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
