【正文】 序存儲結(jié)構(gòu)，隊采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。define sqstack_maxsize 10typedef struct sqstack{DataType data[sqstack_maxsize]。 int top。}SqStackTp。typedef struct linked_queue {DataType data。 struct linked_queue *next。 }LqueueTp。typedef struct queueptr {LqueueTp *front,*rear。 }QueptrTp。int InitStack(SqStackTp *sq) {sqtop=0。 return(1)。}void InitQueue (QueptrTp *lp) {LqueueTp *p。 p=(LqueueTp * )malloc(sizeof(LqueueTp))。 lqfront=p。 lqrear=p。( lqfront)next=NULL。}int QutQueue(QueptrTp *lp,Data Type *x) {LqueueTp *s。 if (lqfront==lqrear) {error(“隊空”)。return(0)。} else {s=(lqfront)nest。 *x=sdata。 (lqfront)next=snext。 if (snext == NULL) lqrear=llqfront。 free(s)。 return(1)。 }}int EmptyQueue(QueptrTp lq){if (==) return(1)。 return(0)。}int Push (SqStackTp *sq , DataType x) { if (sq top = =sqstack_maxsizeq) {return(0)。}else {sq top++。 sqdata[sqtop]=x。return(1)。}}void main(){ SqStackTp DC。 //DC表示渡船 QueptrtTp KE ,HE。 // KE表示客車E、HE表示貨車 Int t ,j=0。 Initstack(DC)。 Initqueue(KE)。 Initqueue(HE)。While(sqstack_maxsize) {j=o。 for (I=I。j=4。I++) //先上4輛客車 if (!emptyqueue(KE)amp。amp。( sqstack_maxsize)) { outqueue (amp。KE, amp。t)。Push (amp。DC, t )。 j++:}for (I=j。I5。I++) //再上1輛貨車或客車不足時用貨車補(bǔ)足 if (!emptyqueue(HE)amp。amp。 ( sqstack _maxsize)) {outqueue(amp。HE,amp。t)。 Push(amp。DC, t)。j++。} if (j5) for (I=j。I5。I++) // 當(dāng)貨車不足時用客車補(bǔ)足 if (!emptyqueue(KE)amp。amp。( sqstack_maxsize)) {outqueue(amp。KE,amp。t)。Push (amp。DC,t ) 。 j++} else printf (“客車、貨車合計不足10輛！”)。}} struct dustack {DataTypeelem[1:M]。 int top0 ,top1。 }dustktp void initstack (dustktp *S ) /*初始化*/ {Stop0=0。 Stop1=M+1。} void push (dustktp *S,DataType X, int I ) /*I指示是棧0或棧1入棧*/ {if (Stop0= =stop11)error(“棧滿！”)；else {if (I==0){stop0++。Selem[Stop0]=X。} else {Stop1。 Selem[Stop1]=X}}}void pop(dustktp *S, DataType *X, int I ) /*I指示是棧0或棧1入棧*/{if (I==0) {if (Stop0==0) error (“?？眨　?else {*X =Selem[Stop0]。Stop0。} }else {if (Stop1= =M+1) error(“?？?！”) else {*X =Selem[Stop1]。Stop1++。}}} initqueue(lklist *lq) /*初始化*/ {lq=malloc(size)。 lqnext=lq。 } void EnCycQueue(lklist *lq ,DataType *X) /*入隊列*/ { p=malloc(size)。pdata=X。 pnext=lqnext。 lqnext=p。 lq=p。 }void outqueue(lklist *lq ,DataType *X) /*出隊列*/{if (lqnext=lq )error(“隊空！”)。 else{p=lqnext。q=pnext。} if (q= =lq ) lq=p 。 pnext=qnext。*X=qdata。 free(q)。}4．設(shè)cycque[m]\ rear\quelen皆為全局變量viod Enqueue (DataType cycque[m], DataType X)/*入隊列*/ { if (quelen= =m+1) error(“隊滿!”)。 else {real=(real+1)%(m+1)。 cycque[real]=X。quelen++。 }}void outqueue(DataType cycque[m], DataType *X)/*出隊列*/ {if (quelen ==0) error (“隊空!”)。 else { frone =(real quelen +1+(m+1))%(m+1)。 /*計算對頭下標(biāo)*/ *X=cycque [frone]。 quelen。}}[n]中。 Void prool(A[n]) {Initstack (d)。 I=0。 flag =true。 while ((In)amp。amp。(flag)){if （(A[i]=‘(’)||(A[I]=‘[’||(A[I]=‘{’)Push (s,A[I])。 else if （(A[i]=‘)’ ）||（A[Push (s,A[I])。if (emptystack(s)) flag= false。 else{x=GetTop(s)。switch(a[I]) {case’}‘:if (x=’(’)pop (s)。 else flag =false。 break。 case’]’:if (x=’[]’) pop(s)。 else flag=false。 break。 case’}’:if (x=’{}’) pop(s)。 else flag=false。}}I++。 }} akm(int m ,int n) {if (m= =0) return(n+1)。else if (n= =0) return(akm (m1,1))。 else return(akm(m1,akm(m,n1)))。}7. int f(int m, int n ) {if (m*n= =0) return(m+n+1)。else return(f(m1,f(m,n1)))。}8. 用Knap(S,n)表示背包問題的解，這是一個布爾函數(shù)，其參數(shù)應(yīng)滿足 S0,n≥1。背包問題如果有解，其選擇只有兩種可能：一種是選擇的一組物品中不包含Wn，這樣Knap(S,n)的解就是Knap(S,n1)的解，另一種是選擇中包含Wn，這時Knap(S,n)的解就是Knap(SWn,n)的解。另外可以定義：當(dāng)S=0時，背包問題總有解，即Knap(0,n)=true ，只要不選擇任何物品放入背包即可：當(dāng)S〈0時，背包問題無解，即Knap(S,n)=false，因為無論怎樣選擇總不能使重量之和為負(fù)值，當(dāng)S0但n1時，背包問題也無解，即Knap(S,n)=false，因為不取任何東西就要使重量為正值總是辦不到的。從而，背包問題可以遞歸定義如下： ╭ | true, 當(dāng)S=0 | false, 當(dāng)S0 Knap(S,n)= false, 當(dāng) s0且 n1 | Knap(S,n1)或Knap(S ,n1)， 當(dāng)s0 且 n=1 |上述遞歸定義是確定的，因為每遞歸一次n都減1，S也可能減少 ，所以遞歸若干次以后，一定會出現(xiàn)S≤0或者 n=0，無論哪種情況都可由遞歸出口明確定值。 Int knap(int s ,int n) {if (s==0) return(1)。 else if (s0||(s0amp。amp。n1)) return(0)。 else if (knap(sw[n],n1)){printf(“%d”,w[n])。return(1)。} else return(knap(s,n1))。 }，然后再依次出棧。 Void invert (lklist head){LstackTp s。 initstack(s)。 p= head。 while (pnull) {Push (s,pdata)。p=pnext。} p=head。 while(not emptystack(s)) {pop(s,pdata)。 p=pnext。}}19