數(shù)據(jù)結(jié)構(gòu)中n個(gè)數(shù)據(jù)依次入棧，出棧順序有多少種？誰(shuí)能幫忙證明下？棧內(nèi)和棧外N個(gè)數(shù)據(jù)個(gè)數(shù)的遞推公式如下：F（N）=∑（F（N-1-k）*FK），其中k從0到N-1已知，F(xiàn)0=1，F(xiàn)1=F0*F0=1f2=

數(shù)據(jù)結(jié)構(gòu)中n個(gè)數(shù)據(jù)依次入棧，出棧順序有多少種？誰(shuí)能幫忙證明下？

棧內(nèi)和棧外N個(gè)數(shù)據(jù)個(gè)數(shù)的遞推公式如下：F（N）=∑（F（N-1-k）*FK），其中k從0到N-1已知，F(xiàn)0=1，F(xiàn)1=F0*F0=1f2=F1*F0*F1=2f3=F2*F0，F(xiàn)1*F1*F0*F2=5，如果證明，對(duì)于N個(gè)數(shù)據(jù)，我只看第一個(gè)數(shù)據(jù)進(jìn)出堆棧的順序：第一個(gè)數(shù)據(jù)可以包含0、1、2n-1數(shù)據(jù)進(jìn)出堆棧。相應(yīng)地，在第一個(gè)數(shù)據(jù)出棧之后，有n-1、n-2、2、1、0個(gè)數(shù)據(jù)需要放在棧上和棧下。根據(jù)組合數(shù)學(xué)中的乘法原理，我們需要將第一個(gè)數(shù)據(jù)放在堆棧上前后的數(shù)據(jù)數(shù)相乘。根據(jù)加法原理，我們需要把所有的N種方式的第一個(gè)數(shù)據(jù)放在堆棧上和放在堆棧下，從而得到遞歸公式。然而，似乎很難找到一個(gè)公式來(lái)直接計(jì)算FN。

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之棧的順序存儲(chǔ)表示與實(shí)現(xiàn)？

使用top指示順序堆棧的頂部指針。如果top=-1，則堆棧為空，否則，堆棧的元素?cái)?shù)為top。下面是順序堆棧的結(jié)構(gòu)定義?define maxsize 20/*存儲(chǔ)空間的初始分配*/typedef int selemtype/*selemtype。類型取決于實(shí)際情況。這里我們假設(shè)它是int type*//*sequential stack structure*/typedef struct{selemtype}Data[maxsize]int top/*用于棧頂指針*/}sqstack/*來(lái)構(gòu)造空棧s*/status initstack（sqstack*s）{s->top=-1//將棧頂指針設(shè)置為-1，這意味著順序堆棧是空的。返回OK}