奇怪的Stack Overflow

picktracy

同样的数据，为什么第一次（无序）使用快排（递归）很正常
而接着再快排，就会Stack Overflow呢？
数据为一个6w多记录的数组，保存一个单链表的节点指针
数组和单链表都在堆上

同样的快排代码
对于int a[63537] = {1, 2, 3, 4, 5, ..., 63537}这样的数据
进行排序，为什么不论排几次都不会Statck Overflow？



实在受不了了，高手帮一把，快排的代码没有问题。

ps:每趟快排以第一个数据为基准

picktracy

对于1, {2, 3, 4, 5, 6, ..., 63539}
由于是有序的，每次都对{}中快排
第二趟2, {3, 4, 5, 6, ..., 63539}

如此循环往复，在9247的时候程序崩溃，调试发现Statck Overflow

picktracy

下班回家了，想出点头绪了，回到家接着讨论^_^

picktracy

对于无序的数据，平均来讲，第一趟快排后，可能将数据大体上分成了3w和3w两部分
然后对两个3w部分递归

有序后，变成对6w部分（我这里是右半部分）进行递归，所以可能对3w部分递归没问题
而对6w递归则会导致stack overflow

不过，这么解释的话，就与我试验的情况相悖了，也就是
对于a[] = {1, 2, 3, ..., 63539}进行快排，不会出现stack overflow

tyc611

LZ是在跟自己讨论吧? 要跟大家讨论请把代码贴出来, 你能保证你的代码没问题吗? 如果这样那你觉得什么地方可能出问题?

tyc611

追加一句,你的程序可能递归调用不当

picktracy

代码很长，截取部分估计。。。
大家看看吧

1. 
   
2. typedef struct tagLinkRecord {
   
3.         U16 Size;
   
4.         U16 Len;
   
5.         U32 LinkID;
   
6.         U32 Node;
   
7.         char* Name;
   
8. }LinkRec, *pLinkRec;
   
9. 
   
10. typedef struct tagLinkList {
    
11.         pLinkRec pLR;
    
12.         tagLinkList* next;
    
13. }LinkList, *pLinkList;
    
14. 
    
15. void QuickSort(pLinkList* pData, U32 left, U32 right)
    
16. {
    
17.         if(left >= right)
    
18.                 return;
    
19.         U32 i = left, j = right;
    
20.         U32 LID = pData[left]->pLR->LinkID;
    
21.         pLinkList pTemp = pData[left];
    
22. 
    
23.         while(i < j) {
    
24.                 while((pData[j]->pLR->LinkID >= LID) && (i < j))
    
25.                         j--;
    
26.                 pData[i] = pData[j];
    
27.                 while((pData[i]->pLR->LinkID <= LID) && (i < j))
    
28.                         i++;
    
29.                 pData[j] = pData[i];
    
30.         }
    
31.         pData[i] = pTemp;
    
32.         //完成一次
    
33. 
    
34.         //每一边再快排
    
35.         if(left < i - 1 && i != left)        //加上!=是为了防止i溢出
    
36.                 QuickSort(pData, left, j - 1);
    
37.         if(right > i + 1)
    
38.                 QuickSort(pData, i + 1, right);
    
39. }
    

复制代码

看看是不是ls说的递归调用不当导致的stack overflow，有意见尽管提
俺很虚心的说

softworm2005

make程序时扩大程序“初始保留栈”的大小即可，如果程序本身没问题。

ArXoR

你的quick sort对于有序序列退化了,O(n)的空间就栈溢出了

picktracy

to ls:
嗯嗯，我弄不准是不是这个问题，因为毕竟有成功的情况，程序其他部分没有大量
使用stack，并且我写过试验程序，没发现有stack overflow的情况，二者编译
时初始栈区是一样的
不过我还是44，谢了^_^