}else if( t> wｅight［k]) Pａck（ ｍ＋１，k＋1，t - wｅighｔ[ｋ] );
}
}
四、判断括号是否配对：
intCorrecｔ( sｔrinｇs )
{
Iｎiｓtack（Ｑ）;
ｆoｒ(ｉ=0；s［i］＝= ‘=’；i++ )//表达式以‘＝’结束
{
swｉｔch(s[i] )
=2n–1
所以,梵塔的移动次数为2ｎ–1次。
三、简化的背包问题：
ｖoid Pacｋ( intｍ, int i,ｉnt t）//初始值为:１１t
｛
for (k=i; k<＝ｎ;k＋＋)
{
soｌutiｏｎ[m]=ｗeighｔ[k];
if( t == weigｈｔ[k])
｛
for ( j=1;ｊ<=m；j+＋) cout<＜ｓolutｉon［j]；coｕt<<eｎdl；
｛
C=new sｔｒuct nｏｄe;Ｃ-＞neｘt=ＮUＬL；q=B->next;
Wｈｉｌe(q）
{
p＝A->ｒ= new struct node；r->ｅxｐ= p->ｅxp＋ｑ－>exp；
r-＞ｉnf＝ｐ-＞inf* q－>iｎf;PolyAｄd(C，r）；
p=p-＞next;
void Insert (ｓtriｎg S, string T, chaｒcｈ）/／设块大小为ｍ
｛
i=０; p=T;
while (（p->neｘt）&&（！i))
{
ｆｏr（ｊ＝１;j<=m;ｊ++ ) if(p->str[j]=＝ch) i=ｊ；
if (！i)p＝p->nｅxt;
｝
if (!ｉ)ｆor( j＝１；j<＝m;j＋+ )if(p->sｔr[j]==cｈ)ｉ=j；
｝
q=q－>ｎext;
｝
}
二、梵塔的移动次数:
已知移动次数迭代公式为：M (ｎ)=2M(n－1 ) + 1
初值为:Ｍ( 0 )＝0
则：M（n）＝2（2M（n-2 ) + 1) +1
=4M( n-2 )+3
=8Ｍ(n－3 )+ 7
=２iM ( n-i ) + 2i–1
若n＝ｉ，则Ｍ （n-ｎ)＝0,故：M ( n ) =2ｎM(ｎ-n）+2n–1
if (! i）p－＞neｘt=Ｓ; else／/S插在T后
{ //ch所在结点分裂,S插在Ｔ中分裂的两结点间
q= nｅｗstruｃt node; q－>str=p->ｓtr; q－＞next=p->ｎext;
ｆor(ｊ=i; j<=ｍ; j+＋）p->stｒ［ｊ]= ‘#’; p->next=S；
}
ｉｎtＥｍptyQ ( )
｛
if (Ｅｍpty (S1) &&Eｍptｙ(Ｓ2)）ｒeturn1;rｅtｕrn 0;
}
voidＥnｑueue ( eｌemtyｐeｘ)
{
if (Fuｌl(Ｓ1））if (Emｐｔy(S2））wｈiｌe（! Emｐty (S1))Ｐｕsh(S2，Poｐ(S1)）;
if (!Ｆuｌl（S1))Push（Ｓ1，x）；
rｅturn 1;
}
五、堆栈可能的输出:
123412431３2４1３４2 1423１４3２
2134２143 231４2341 241３２43１
3１２4314２３２1432413412３421
4123413242１３42３1431２432１
六、用两个堆栈实现一个队列:
intFｕllＱ（）
{
ｉf(Ｆull (Ｓ1）&&！Empｔy (S2)) rｅｔurn 1;retｕrｎ0；
for (ｊ=１; j<ｉ; j++ ) q－＞str[ｊ]= ‘#’;p=S;
ｗhｉle ( p-＞nｅxt )ｐ=p->ｎext;p->next=q;
}
}
九、上三角矩阵的存储：
ｋ=(ｉ-1)*n+j-i＊（ｉ－１)/2=（2n-ｉ+1)*i/2＋j-n
ｆ1=(2n-i+1)*ｉ/２
f2=j
c=-n
}
elemｔｙpe Dequeue( )
{
ｉf (Empty(Ｓ2)）ｗhilｅ(！Empty(Ｓ１))Ｐuｓｈ(S２,Pop(Ｓ1));
ｉf (! Emptｙ(S2))reｔurｎＰｏp（Ｓ2);
}
七、生成新串及字符第一次出现位置:
ｉntＩｎdex ( striｎg S,ｓtriｎｇT）
{
for (ｉ=1；ｉ+ Lｅｎ(T）-1<=Ｌen（Ｓ); i++ )
十、循环右移k位：
１2３45 6 78(n＝8, k＝3)
if (！Indｅx(T,cｈ）&& ! Inｄex(R,ch) )
｛Ｒ=Cｏｎcaｔ(Ｒ, ch）;P[ｊ++]=i; }
｝
}
八、块链字符串插入:
｛为避免字符串内部块间大量的数据移动,最好的方法是定义两种
字符串中不出现的字符作为空标记和串结束标记，如‘#’和‘$’;
也可只使用空标记，串结束以块尾指针为空表示,其算法如下：
{
cａsｅ‘(’:
ｃａｓｅ‘[’:
ｃase ‘｛’:
Pusｈ（Q, s［i］);ｂrｅａk;
case‘)’:
ｃaｓｅ‘]’:
casｅ‘}’:
iｆ（ Ｅmpty(Q))return0;ｔ=Pop(Ｑ);
iｆ(!Matching( t,ｓ[i]))return 0；
}
}
ｉｆ（! Eｍpｔy(Q) ) return０;
作业参考答案
一、（带头结点）多项式乘法C= A×B：
void PoｌyAdd ( list &C,liｓｔR)／／R为单个结点
{
p=C;
while(（!p-＞ｎeｘt) &＆(p->nexｔ-＞eｘp>Ｒ->eｘp)) p=p－>ｎｅｘt；
ｉf (（p->next)｜｜(ｐ->neｘt->ｅｘp<Ｒ-＞eｘp))
iｆEquaｌ( Sub ( S,Ｉ, Len（T）), T) returni；
return０;
}
vｏiｄCｒｅatNewStr (sｔｒｉngＳ, strｉngT, strinｇR, arraｎt P)
{
R=“”; j=0;
fｏr(ｉ＝1;i＜=Len(S)；i++ )
{
ch＝Sｕb( S, i, 1 );
{R－＞nｅxt=ｐ->ｎeｘｔ;p->neｘｔ=Ｒ;}ｅlse
{ｐ-＞nｅxt－＞inf +=R->inｆ;delｅteR;
if（！p－>neｘｔ-＞iｎｆ)
{ R=ｐ-＞nｅxt；p－>next=R->ｎext;deleｔe R;｝
}
}
ｖoｉｄPｏlｙMul（lｉstA, lｉst B，lｉst&C）