小甲鱼在栈这一讲解中的一个漏洞
本帖最后由 my_angel 于 2013-10-23 15:42 编辑大家好，我想在这一板块的鱼友们应该都看过小甲鱼出品的《数据结构与算法》这一视屏讲解。
甲鱼哥的视频非常不错，这一点是毋容置疑的，甚至比某些大学高校的讲师还要尽善尽美（比如我的学校）。
但是，在视频的过程中还是有一些小问题（这个我想比较细心的朋友们还是能够发现的，不过问题不大）。
不过今天我在栈这一讲解中（具体是25-进制转化），发现了一个逻辑上的问题。
具体问题的代码如下： void Push(SqStack *s,ElemType e) //入栈
{
if(StackLength(*s) >= s->StackSize )
{
s->base = (ElemType *)realloc(s->base , (s->StackSize + STACK_INCREMENT)*sizeof(ElemType) );
if(!s->base){
exit(ERROR);
}
}
*(s->top) = e;
s->top++;
}
继续学下去发现“甲鱼胸”在后面课程给出的代码中已经是解决了这个问题，所以就不再隐藏了。。。
这段代码其实在一般情况下是没有问题的，但是如果STACK_INIT_SIZE容量不足时进行realloc时就很有可能发生问题了。
这里我的测试如下：
#define STACK_INIT_SIZE 2 //初始化容量
#define STACK_INCREMENT 1 //后续增量
这样比较快进行扩容。。。。
这里其实产生问题的是realloc这个函数。。。
realloc语法：
指针名=（数据类型*）realloc（要改变内存大小的指针名，新的大小）。
//新的大小一定要大于原来的大小，不然的话会导致数据丢失！
注意：假如原来的内存后面还有足够多剩余内存的话，realloc的内存<原来的内存+剩余内存,realloc还是返回原来内存的地址;
但是，假如原来的内存后面没有足够多剩余内存的话，realloc将申请新的内存，然后把原来的内存数据拷贝到新内存里，原来的内存将被free掉,realloc返回新内存的地址。
因此，也就是说上述代码s->base的指向很可能已经变了，而s->top没有做出相应的改变。所以继续执行同样的代码就会发生错误了。
因此，我们要对相应的s->top进行修改。同样的，不要忘记对s->StackSize进行修改哦。。。
代码如下：
Status Push(SqStack *s,ElemType e) //入栈
{
if(StackLength(*s) >= s->StackSize )
{
s->base = (ElemType *)realloc(s->base , (s->StackSize + STACK_INCREMENT)*sizeof(ElemType) );
if(!s->base){
printf("Push Failed:cannot realloc space.\n");
exit(ERROR);
}
s->top = s->base + s->StackSize; //realloc后，s->base地址变了,因此s->top的地址也要对应的进行修改
s->StackSize += STACK_INCREMENT; //当前栈最大容量改变
}
*(s->top) = e;
s->top++;
return TRUE;
}
好久没发贴了，自己给自己顶一个。。。 有点好奇喔 很用心，向你学习，抓紧学习去咯 支持一下不错的，好好学习 我只是路过打酱油的。 楼主 钻研精神哦 表示完全看不懂，看到栈我以为是汇编代码了。 这个是C语言的代码还是？ 这是哪里的内容啊？ 较真，精神加分。:lol: 是不是啊，这么吊 什么漏洞？ 之前总看到这个函数，也知道它的作用。
但是在实际应用中就忘掉了...
感谢这位同学的帖子，向你学习。
页:
[1]