#include "../utilities/List.h"
#include<stack>
#include<cstdio>
void PrintReveringly_Iteratively(ListNode * pHead)
{
std::stack<int> snode;
ListNode * pnode = pHead;
if(pHead == nullptr)
{
return ;
}
while(pnode!=nullptr)
{
snode.push(pnode->m_nvalue);
pnode = pnode->m_pnext;
}
while(snode.size()!=0)
{
int node = snode.top();
snode.pop();
printf("%d\n", node);
}
}
void test1()
{
ListNode * node1=CreateNode(10);
ListNode * node2=CreateNode(120);
ListNode * node3=CreateNode(130);
ListNode * node4=CreateNode(140);
ConnectionList(node1,node2);
ConnectionList(node2,node3);
ConnectionList(node3,node4);
PrintReveringly_Iteratively(node1);
DestoryLists(node1);
}
int main()
{
test1();
}
以上是函数体
以下是函数调用的构建节点,连接节点的函数,以及最后的销毁函数.
ListNode* CreateNode(int value)
{
ListNode *node = new ListNode();
node->m_nvalue = value;
node->m_pnext = nullptr;
printf("ssss\n");
return node;
}
void ConnectionList(ListNode *cur, ListNode *pNext)
{
if(cur!= nullptr){
while(cur->m_pnext != nullptr)
{
cur = cur->m_pnext;
}
if(cur != nullptr && pNext != nullptr)
{
cur->m_pnext = pNext;
cur = pNext;
}
}
}
void DestoryLists(ListNode *pHead)
{
ListNode * pH = pHead;
while(pH !=nullptr)
{
ListNode * pnode = pH;
if(pHead->m_pnext == nullptr)
pH =nullptr;
else
pH = pH->m_pnext;
printf("\n\n%d",pnode->m_nvalue);
delete pnode;
}
}
运行结果没有问题,
但是当使用valgrind进行内存检测的时候,总是有一个块好像没有被释放.第一次用valgrin的不是很理解到底是哪里没有释放?
==30168== Memcheck, a memory error detector
==30168== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==30168== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==30168== Command: ./reverselist
==30168==
ssss
ssss
ssss
ssss
140
130
120
10
==30168== Invalid read of size 8
==30168== at 0x4025CF: DestoryLists(ListNode*) (List.cpp:54)
==30168== by 0x400BD6: test1() (reverselist.cpp:41)
==30168== by 0x400BE2: main (reverselist.cpp:45)
==30168== Address 0x5ab6c88 is 8 bytes inside a block of size 16 free'd
==30168== at 0x4C2F24B: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30168== by 0x402610: DestoryLists(ListNode*) (List.cpp:59)
==30168== by 0x400BD6: test1() (reverselist.cpp:41)
==30168== by 0x400BE2: main (reverselist.cpp:45)
==30168== Block was alloc'd at
==30168== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30168== by 0x4024A1: CreateNode(int) (List.cpp:4)
==30168== by 0x400B57: test1() (reverselist.cpp:31)
==30168== by 0x400BE2: main (reverselist.cpp:45)
==30168==
10
120
130
140==30168==
==30168== HEAP SUMMARY:
==30168== in use at exit: 72,704 bytes in 1 blocks
==30168== total heap usage: 10 allocs, 9 frees, 74,944 bytes allocated
==30168==
==30168== LEAK SUMMARY:
==30168== definitely lost: 0 bytes in 0 blocks
==30168== indirectly lost: 0 bytes in 0 blocks
==30168== possibly lost: 0 bytes in 0 blocks
==30168== still reachable: 72,704 bytes in 1 blocks
==30168== suppressed: 0 bytes in 0 blocks
==30168== Reachable blocks (those to which a pointer was found) are not shown.
==30168== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==30168==
==30168== For counts of detected and suppressed errors, rerun with: -v
==30168== ERROR SUMMARY: 3 errors from 1 contexts (suppressed: 0 from 0)
谢谢
10 个解决方案
#1
我是这样检查是否有内存泄露的：
//将c:\\tmp文件夹下的所有文件的内容全部放到用malloc分配的内存中
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <io.h>
struct FB {
char fn[256];
size_t fl;
char *b;
struct FB *next;
struct FB *prev;
} *fh,*fb,*ft;
char ln[256];
char fpn[256];
FILE *af;
FILE *f;
int L,n;
int main() {
system("dir /b /a-d c:\\tmp\\*.* >c:\\allfn.txt");
af=fopen("c:\\allfn.txt","r");
if (NULL==af) {
printf("Can not open file c:\\allfn.txt!\n");
return 1;
}
fh=NULL;
fb=NULL;
n=0;
while (1) {
if (NULL==fgets(ln,256,af)) break;
L=strlen(ln);
if ('\n'==ln[L-1]) ln[L-1]=0;
printf("read %s\n",ln);
strcpy(fpn,"c:\\tmp\\");
strcat(fpn,ln);
ft=(struct FB *)malloc(sizeof(struct FB));
if (NULL==ft) {
printf("Can not malloc ft!\n");
fclose(af);
return 2;//之前的malloc在main退出后由操作系统自动free
}
printf("ft[%d]==%p\n",n,ft);
strcpy(ft->fn,fpn);
f=fopen(fpn,"rb");
if (NULL==f) {
printf("Can not open file %s!\n",fpn);
fclose(af);
return 3;//之前的malloc在main退出后由操作系统自动free
}
ft->fl=_filelength(fileno(f));
ft->b=malloc(ft->fl);
if (NULL==ft->b) {
printf("Can not malloc ft->b!\n");
fclose(f);
fclose(af);
return 4;//之前的malloc在main退出后由操作系统自动free
}
printf("ft[%d]->b==%p\n",n,ft->b);
if (ft->fl!=fread(ft->b,1,ft->fl,f)) {
printf("fread error!\n");
fclose(f);
fclose(af);
return 5;//之前的malloc在main退出后由操作系统自动free
}
fclose(f);
ft->next=NULL;
if (NULL==fh) {
ft->prev=NULL;
fh=ft;
} else {
fb->next=ft;
ft->prev=fb;
}
fb=ft;
n++;
}
fclose(af);
printf("-----list-----\n");
for (ft=fh;NULL!=ft;ft=ft->next) {
printf("%8d %s\n",ft->fl,ft->fn);
if (NULL!=ft) fb=ft;
}
printf("-----free-----\n");
n--;
if (NULL!=fh) {
for (ft=fb->prev;NULL!=ft;ft=ft->prev) {
if (NULL!=ft->next->b) {
printf("ft[%d]->b==%p\n",n,ft->next->b);
free(ft->next->b);
}
if (NULL!=ft->next) {
printf("ft[%d]==%p\n",n,ft->next);
free(ft->next);
}
n--;
}
if (NULL!=fh->b) {
printf("ft[0]->b==%p\n",fh->b);
free(fh->b);
}
printf("ft[0]==%p\n",fh);
free(fh);
}
return 0;
}
//C:\tmp\tmp\Debug>dir /a-d c:\tmp
// 驱动器 C 中的卷是 C_HD5_1
// 卷的序列号是 1817-D526
//
// c:\tmp 的目录
//
//找不到文件
//
//C:\tmp\tmp\Debug>tmp
//找不到文件
//-----list-----
//-----free-----
//
//C:\tmp\tmp\Debug>dir /a-d c:\tmp
// 驱动器 C 中的卷是 C_HD5_1
// 卷的序列号是 1817-D526
//
// c:\tmp 的目录
//
//2011-06-30 18:04 44,840 my_c.rar
//2011-06-30 17:18 1,036 err.frm
//2011-06-30 14:32 14,243 出租.txt
//2011-06-28 12:08 23,681 MSDN98书签.txt
// 4 个文件 83,800 字节
// 0 个目录 17,041,870,848 可用字节
//
//C:\tmp\tmp\Debug>tmp
//read my_c.rar
//ft[0]==00421800
//ft[0]->b==00520068
//read err.frm
//ft[1]==00421670
//ft[1]->b==0052AFC0
//read 出租.txt
//ft[2]==00421530
//ft[2]->b==00378F28
//read MSDN98书签.txt
//ft[3]==004213F0
//ft[3]->b==0052B3F8
//-----list-----
// 44840 c:\tmp\my_c.rar
// 1036 c:\tmp\err.frm
// 14243 c:\tmp\出租.txt
// 23681 c:\tmp\MSDN98书签.txt
//-----free-----
//ft[3]->b==0052B3F8
//ft[3]==004213F0
//ft[2]->b==00378F28
//ft[2]==00421530
//ft[1]->b==0052AFC0
//ft[1]==00421670
//ft[0]->b==00520068
//ft[0]==00421800
//
//C:\tmp\tmp\Debug>
#2
void ConnectionList(ListNode **cur, ListNode *pNext)
{
if((*cur) != nullptr && pNext != nullptr)
(*cur)->m_pnext = pNext;
}
如果按照你的逻辑将链表串起来，需要将ConnectionList函数定义成如上的形式。
原因是，如果单纯传递一重指针，则不能将cur的下一个节点的内容和前一个节点连起来。
#3
第29行: if(pHead->m_pnext == nullptr)
其中的 pHead 是否应该是 pH
其中的 pHead 是否应该是 pH
#4
这里确实有问题, 会导致有些结点不在链表里, 所以没有被释放
#5
感谢赵老师给的例子.
#6
感谢您的关注. 是否能再讲解的细节一点.我试了一下还是不行. 个人理解,只传入一重指针是没有问题的,
cur只是一个指针,如果根据入栈规则首先对它进行压栈,那么保存的只是它的值,即指向ListNode的指针,而指针本身已经存在了节点.进去只是改变它的指向内容的值,应该没有影响把?
void ConnectionList(ListNode *cur, ListNode *pNext)
{
if(cur!= nullptr){
while(cur->m_pnext != nullptr)
{
cur = cur->m_pnext;
}
if(cur != nullptr && pNext != nullptr)
{
cur->m_pnext = pNext;
cur = pNext;
}
}
}
#7
感谢你的回答. 这句话应该改成pH更好,逻辑上这句语句并没有起到作用.
#8
我不清楚压栈的问题，但从链表的角度上考虑，传一重指针到 ConnectionList是不能建立一个完整的链表的
这是两个问题，在压栈之前，首先你可以打印一下你的链表，看看是否4个节点都串起来了。
#10
仔细看了一下代码, 看起来是没问题的. ListNode 是怎么定义的, 里面有包含别的指针吗?
#1
我是这样检查是否有内存泄露的：
//将c:\\tmp文件夹下的所有文件的内容全部放到用malloc分配的内存中
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <io.h>
struct FB {
char fn[256];
size_t fl;
char *b;
struct FB *next;
struct FB *prev;
} *fh,*fb,*ft;
char ln[256];
char fpn[256];
FILE *af;
FILE *f;
int L,n;
int main() {
system("dir /b /a-d c:\\tmp\\*.* >c:\\allfn.txt");
af=fopen("c:\\allfn.txt","r");
if (NULL==af) {
printf("Can not open file c:\\allfn.txt!\n");
return 1;
}
fh=NULL;
fb=NULL;
n=0;
while (1) {
if (NULL==fgets(ln,256,af)) break;
L=strlen(ln);
if ('\n'==ln[L-1]) ln[L-1]=0;
printf("read %s\n",ln);
strcpy(fpn,"c:\\tmp\\");
strcat(fpn,ln);
ft=(struct FB *)malloc(sizeof(struct FB));
if (NULL==ft) {
printf("Can not malloc ft!\n");
fclose(af);
return 2;//之前的malloc在main退出后由操作系统自动free
}
printf("ft[%d]==%p\n",n,ft);
strcpy(ft->fn,fpn);
f=fopen(fpn,"rb");
if (NULL==f) {
printf("Can not open file %s!\n",fpn);
fclose(af);
return 3;//之前的malloc在main退出后由操作系统自动free
}
ft->fl=_filelength(fileno(f));
ft->b=malloc(ft->fl);
if (NULL==ft->b) {
printf("Can not malloc ft->b!\n");
fclose(f);
fclose(af);
return 4;//之前的malloc在main退出后由操作系统自动free
}
printf("ft[%d]->b==%p\n",n,ft->b);
if (ft->fl!=fread(ft->b,1,ft->fl,f)) {
printf("fread error!\n");
fclose(f);
fclose(af);
return 5;//之前的malloc在main退出后由操作系统自动free
}
fclose(f);
ft->next=NULL;
if (NULL==fh) {
ft->prev=NULL;
fh=ft;
} else {
fb->next=ft;
ft->prev=fb;
}
fb=ft;
n++;
}
fclose(af);
printf("-----list-----\n");
for (ft=fh;NULL!=ft;ft=ft->next) {
printf("%8d %s\n",ft->fl,ft->fn);
if (NULL!=ft) fb=ft;
}
printf("-----free-----\n");
n--;
if (NULL!=fh) {
for (ft=fb->prev;NULL!=ft;ft=ft->prev) {
if (NULL!=ft->next->b) {
printf("ft[%d]->b==%p\n",n,ft->next->b);
free(ft->next->b);
}
if (NULL!=ft->next) {
printf("ft[%d]==%p\n",n,ft->next);
free(ft->next);
}
n--;
}
if (NULL!=fh->b) {
printf("ft[0]->b==%p\n",fh->b);
free(fh->b);
}
printf("ft[0]==%p\n",fh);
free(fh);
}
return 0;
}
//C:\tmp\tmp\Debug>dir /a-d c:\tmp
// 驱动器 C 中的卷是 C_HD5_1
// 卷的序列号是 1817-D526
//
// c:\tmp 的目录
//
//找不到文件
//
//C:\tmp\tmp\Debug>tmp
//找不到文件
//-----list-----
//-----free-----
//
//C:\tmp\tmp\Debug>dir /a-d c:\tmp
// 驱动器 C 中的卷是 C_HD5_1
// 卷的序列号是 1817-D526
//
// c:\tmp 的目录
//
//2011-06-30 18:04 44,840 my_c.rar
//2011-06-30 17:18 1,036 err.frm
//2011-06-30 14:32 14,243 出租.txt
//2011-06-28 12:08 23,681 MSDN98书签.txt
// 4 个文件 83,800 字节
// 0 个目录 17,041,870,848 可用字节
//
//C:\tmp\tmp\Debug>tmp
//read my_c.rar
//ft[0]==00421800
//ft[0]->b==00520068
//read err.frm
//ft[1]==00421670
//ft[1]->b==0052AFC0
//read 出租.txt
//ft[2]==00421530
//ft[2]->b==00378F28
//read MSDN98书签.txt
//ft[3]==004213F0
//ft[3]->b==0052B3F8
//-----list-----
// 44840 c:\tmp\my_c.rar
// 1036 c:\tmp\err.frm
// 14243 c:\tmp\出租.txt
// 23681 c:\tmp\MSDN98书签.txt
//-----free-----
//ft[3]->b==0052B3F8
//ft[3]==004213F0
//ft[2]->b==00378F28
//ft[2]==00421530
//ft[1]->b==0052AFC0
//ft[1]==00421670
//ft[0]->b==00520068
//ft[0]==00421800
//
//C:\tmp\tmp\Debug>
#2
void ConnectionList(ListNode **cur, ListNode *pNext)
{
if((*cur) != nullptr && pNext != nullptr)
(*cur)->m_pnext = pNext;
}
如果按照你的逻辑将链表串起来，需要将ConnectionList函数定义成如上的形式。
原因是，如果单纯传递一重指针，则不能将cur的下一个节点的内容和前一个节点连起来。
#3
第29行: if(pHead->m_pnext == nullptr)
其中的 pHead 是否应该是 pH
其中的 pHead 是否应该是 pH
#4
这里确实有问题, 会导致有些结点不在链表里, 所以没有被释放
#5
感谢赵老师给的例子.
#6
感谢您的关注. 是否能再讲解的细节一点.我试了一下还是不行. 个人理解,只传入一重指针是没有问题的,
cur只是一个指针,如果根据入栈规则首先对它进行压栈,那么保存的只是它的值,即指向ListNode的指针,而指针本身已经存在了节点.进去只是改变它的指向内容的值,应该没有影响把?
void ConnectionList(ListNode *cur, ListNode *pNext)
{
if(cur!= nullptr){
while(cur->m_pnext != nullptr)
{
cur = cur->m_pnext;
}
if(cur != nullptr && pNext != nullptr)
{
cur->m_pnext = pNext;
cur = pNext;
}
}
}
#7
感谢你的回答. 这句话应该改成pH更好,逻辑上这句语句并没有起到作用.
#8
我不清楚压栈的问题，但从链表的角度上考虑，传一重指针到 ConnectionList是不能建立一个完整的链表的
这是两个问题，在压栈之前，首先你可以打印一下你的链表，看看是否4个节点都串起来了。
#9
数据结构对单链表进行数据排序
http://bbs.csdn.net/topics/392201633
#10
仔细看了一下代码, 看起来是没问题的. ListNode 是怎么定义的, 里面有包含别的指针吗?