第三章         栈和队列参考答案

一、名词解释（略）

二、填空题

1、  先进后出、后进先出，后进先出，进栈，入栈，退栈，出栈

2、  初始化InitStack(S)、进栈Push(S,X), 退栈Pop(S)，读栈顶Top(S),判栈空Empty(S)

3、  下溢

4、  上溢

5、  顺序、链接

6、  栈空、下溢、栈满、上溢

7、  sq->top=0

8、  sq->top++,sq->data[sq->top]

9、  sq->data[sq->top],sq->top—

10、              sq->top= =0

11、              sq->top= =0,sq->data[sq->top]

12、              ls=NULL

13、              p->data=x,ls=p

14、              p->data,free(p)

15、              *x=ls->data

16、              更小的“尺度”、递归

17、              队、队尾、队头

18、              队列初始化InitQueue(Q)、入队列EnQueue(Q,X)、出队OutQueue(Q,X)、判队列空EmptyQueue(Q)、读队头ead(Q,x)

19、              假溢出

20、              sq->front=0

21、              sq->front,sq->rear=(sq->rear+1)%maxsize,sq->data[sq->rear]=x

22、              sq->rear,sq->fornt=(sq->rear+1)%maxsize,*x= sq->data[sq->rear]

23、              sq.rear= sq.front

24、              sq.front,(sq.front+1)%maxsize

25、              队满、队空

26、              lq->front=p,NULL

27、              p->data,p,lq->rear=p

28、              *x,s->next

29、              lq.rear= =lq.front

30、              p=lq.front->next,*x

31、              n-1,读、写

32、              顺序、列序、行序、行、列

33、              特殊、稀疏

34、              n(n+1)/2

35、         i(i-1)/2+j   当i≧j

　　　k=

j(j-1)/2+i   当i<j

36、n-t+1,(i-1)(2n-i+2)/2,j-i+1

 

 

(i-1)(2n-i+2)/2+j-i+1  当i<=j

k=

n(n+1)/2+1          当i>j

n(n+1)/2+1

37、　　　(i-1)/2+j   当i≧j

　k=

n(n+1)/2+1          当i<j

38、col<=a.nu,a.data[p].j,q++

39、col<=a.nu,cpot[col-1]+num[col-1],cpot[col]++

40、先进后出（后进先出）

41、先进先出（后进后出）

42、ls= =NULL,*x=p->info

43、2230,2374

44、n-1

45、栈

46、EA+222,EA+117

47、lq->front->next= =lq->rear

48、540,108,M[3][10]

三、单项选择题

1、④2、①3、④4、①5、③6、②7、①8、③9、④10②、

11、②12、③13、①②14、②15、④16、①17、②18、③19、④20、①

21、②22、①23、③24、①25、②26、③27、②28、②29、②30、③

31、②32、②33、③34、②35、④

四、简答及应用

1、顺序栈类型定义如下：

#define sqstack_maxsize 顺序栈的容量

typedef struct sqstack

{DataType    data[sqstack_maxsize];

int   top

}SqStackTp

它有两个域：data和top。Data为一个一维数组，用于存储栈中元素，DataType为栈元素的数据类型。Top为int型，它的实际取值范围为0~sqstack_maxsize－1。

2、链栈的类型定义如下：

typedef stuct node

{  DataType  data;

   struct      node  *next;

}LstackTp;

单链表的第一个结点就是链栈栈顶结点，链栈由栈顶指针惟一确定。栈中的其它结点通过它们的next域链接起来不。栈底结点的next域为NULL。

3、顺序队列的类型定义如下：

#define  maxsize 顺序栈的容量

typedef struct sqqueue

     {DataType    data[maxsize];

int   fornt,rear

}SqQueueTp

SqQueueTp sq;

该类型变量有三个域：data,front,rear。其中data存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量，实际取值范围为0~maxsize－1。

循环队列的类型定义如下：

#define  maxsize　　　循环队的容量

typedef struct cycqueue{

DataType   data[maxsize]

Int  front,rear

}CycqueueTp;

CycqueueTp sq;

4、typedef struct linked_queue

{  DataType data;

   struct  linked_queue *next;

}LqueueTp;

typedef struct queueptr

{  LqueueTp  *front,  *rear;

}QueptrTp;

QueptrTp  lq;

5、#define  maxnum　　　非零元素的容量

  typedef struct node

{ int   i,j ;　　

 DataType  v;　　

}NODE;

typedef struct spmatrix

{  int  mu,nu,tu;　　

   NODE data[maxnum+1];

}SpMatrixTp

6、int length(CycqueueTp sq)

{len=(sq.rear-sq.front+maxsize)%maxsize;

return(len);

}

7、1234、4321、2143、3421、3241、1324、1432、1342、1243、3214、2134、2314、2341、2431

8、      i(2n-i+1)/2   当i<=j

f₁(i)=

0                                       当i>j

         j           当i<=j

f₂ (j)=

0                                       当i>j

       -n           当i<=j

c=

n(n+1)/2+1    当i>j

9、(1)k=2i+j-2;      (i,j=1,2,…..n)

   (2)i=ceil((k+1)/3)     j=floor(k/3)+k  mod  3

10、运行结果：ABCDEFGHIJKLM

MLKJIHGFEDCBA

11、借助栈将一个带头结点的单链表倒置。

 

 

 

 

 

12-

Top->			Top->			Top->			Top->			Top->			Top->
																1	r’’’’
													2	r’’’		2	r’’’
										3	r’’		3	r’’		3	r’’
							4	r’		4	r’		4	r’		4	r’
				5	r		5	r		5	r		5	r		5	r

调用f(5)前　　调用f(5)前　　调用f(4)前    调用f(3)前     调用f(2)前     调用f(1)前

Top->			Top->			Top->			Top->			Top->
	2	r’’’
	3	r’’		3	r’’
	4	r’		4	r’		4	r’
	5	r		5	r		5	r		5	r

返回f(1)后　　　　　返回f(2)后　　　返回f(3)后　　　　返回f(4)后　　　返回f(5)后

五、算法设计

1．本程序中，将客车类定义一个队KE，货车类定义一个队HE，过江渡船定义成一个栈DC。栈采用顺序存储结构，队采用链式存储结构。

#define sqstack_maxsize 10

typedef 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)   {sq->top=0; return(1);}

void InitQueue (QueptrTp  *lp)

  {LqueueTp  *p;

   p=(LqueueTp  * )malloc(sizeof(LqueueTp));

   lq->front=p;

   lq->rear=p;

( lq->front)->next=NULL;

}

int QutQueue(QueptrTp *lp,Data Type *x)

  {LqueueTp  *s;

   if (lq->front==lq->rear)  {error(“队空”);return(0);}

   else {s=(lq->front)->nest;

         *x=s->data;

         (lq->front)->next=s->next;

         if (s->next == NULL)  lq->rear=llq->front;

         free(s);

         return(1);

       }

}

int EmptyQueue(QueptrTp lq)

{if (lq.rear==lq.front) return(1);

                  return(0);

}

int Push (SqStackTp *sq , DataType x)

  { if (sq ->top = =sqstack_maxsize-q) {return(0);}

else {sq ->top++; sq->data[sq->top]=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(DC.top<sqstack_maxsize)

   {j=o;

 for (I=I;j<=4;I++)   //先上4辆客车

 if (!emptyqueue(KE)&&(DC.top <sqstack_maxsize))

 { outqueue (&KE, &t);Push (&DC, t );  j++:}

for (I=j;I<5;I++)   //再上1辆货车或客车不足时用货车补足

 if (!emptyqueue(HE)&& (DC.top < sqstack _maxsize))

  {outqueue(&HE,&t); Push(&DC, t);j++;}

 if (j<5) for (I=j;I<5;I++) // 当货车不足时用客车补足

 if (!emptyqueue(KE)&&(DC.top <sqstack_maxsize))

  {outqueue(&KE,&t);Push (&DC,t ) ; j++}

 else printf (“客车、货车合计不足10辆！”);

}

}

2.typedef struct dustack

  {DataTypeelem[1:M];

   int  top0 ,top1;

  }dustktp

 void initstack (dustktp *S ) 

  {S->top0=0; S->top1=M+1;}

 void push (dustktp *S,DataType X, int I )  /*I指示是栈0或栈1入栈*/

  {if (S->top0= =s->top1-1)error(“栈满！”)；

else {if (I==0){s->top0++;S->elem[S->top0]=X;}

      else {S->top1--; S->elem[S->top1]=X}

}

}

void pop(dustktp *S, DataType *X, int I )   /*I指示是栈0或栈1入栈*/

{if (I==0)

   {if  (S->top0==0) error (“栈空！”)

else {*X =S->elem[S->top0];S->top0--;}

  }

else {if (S->top1= =M+1) error(“栈空！”)

    else {*X =S->elem[S->top1];S->top1++;}

}

}

3.void initqueue(lklist *lq)      /*初始化*/

  {lq=malloc(size);

     lq->next=lq;

   }

 void EnCycQueue(lklist *lq ,DataType *X)  /*入队列*/

 { p=malloc(size);p->data=X;

 p->next=lq->next;

 lq->next=p;

 lq=p;

 }

void outqueue(lklist *lq ,DataType *X)   /*出队列*/

{if (lq->next=lq )error(“队空！”);

   else{p=lq->next;q=p->next;}

 if (q= =lq  ) lq=p ;

  p->next=q->next;*X=q->data;

 free(q);

}

4．设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);  

         *X=cycque [frone]; quelen--;

}

}

5. void trans_mat _trix(DateType a[m][n],SpMatrixTp b )

  {p=0;

  for (I=1; I<=m ; I++)

  for (j=1; j<=n;j++)

if (a[I][j])   

  {p++;            

    b.data[p].i=I;

 b.data[p].j=j;

   b.data[p].v=a[I][j];

}

b.mu=m; b.nu=n; b.tu=p;    

}

6．本题首先判断三元组A，B表示的矩阵是否行列相同，若相同才能进行矩阵的加法

运算。若三元组表示的矩阵能进行相加运算，其思路如下：

 若a,b表的指针均没有到表尾，重复下列步骤：

（1）       若a表元素的i 域值小于b表元素的i域值，将a表当前元素插入到c表表尾， a表指针后移。

（2）       若a表元素的i 域值大于b表元素的i域值，将b表当前元素插入到c表表尾， b表指针后移。

（3）       若a表元素的i域值等于b表元素的i域值，又分以下几种情况讨论：

①若a表元素的j域值小于b表元素的j域值，将a表当前元素插入到c表表尾，a表指针后移。

②若a表元素的j域值大于b表元素的j域值，将b表当前元素插入到c表表尾，b表指针后移。

③若a表元素的j域值等于b表元素的j域值，若a,b表当前元素的v域值和非零，则在c表表尾播入元素的I\j域值等于a表当前元素的I\j域 的值，域v的值等于a,b表的域值的和，将a,b表当前指针后移。

(4) 若a表的指针没到表尾，b表的指针到表尾，将a表剩余元素依次插入到c表表尾，否则，将b表剩余元素依次插入到c表表尾.

SpMaterixTp trsxsum(SpMaterixTp a, SpMaterixTp b , SpMaterixTp c)

{if ( (a .mu=b. mu)&&(a.nu=b.mu))               

  {c.mu=a.mu ;c.nu=a.nu; I=1; j=1; p=0;

if (a.tu&&b.tu)                           

  {cola=a.data[I].i; rowa = a.data[I] .j; 

   colb= b.data[j].i; rowb =b.data[j] .j; 

  while ((I<=a.tu)&&(j<=b.tu))

     switch

        {cola <colb:   

           p++; c.data [p] .i=a.data [I] .i;

           c.data [p].j= a.data [I].j;

           c.data [p] .v= a.data[I].v;

           I++; break;  

         Cola>colb:     

          P++;c.data[p] .i=b.data [j] .i;

           c.data [p].j= b.data [j].j;

           c.data [p] .v= b.data[j].v;

           j++; break;  

         Cola =colb :

           P++;        

           If (rowa<rowb)           

             {c.data[p].j=a.data [I].j;

              c.data[p].j=a.data[j].j;

              c.data[p].v=a.data[I].v; I++;

}

else if (rowa>rowb) 

   {c.data[p].i=b.data[j].i;

    c.data[p].j=b.data[j].j;

    c.data[p].v= b.data[j].v; j++;

    }

else if (a.data[I].v +b.data[j].v)

 

 {c.data [p].i =a.data[I].i ;

  c.data[p].j=a.data[j].j;

  c.data[p].v=a.data[I].v+b.data[j].v;

  I++; j++;

} else {p--;I++;j++}; 

           break;

        }  

}

if (I<=a.tu)                   

  {p++; c.data[p].i =a.data[p].i; c.data[p].j=a.data[p].j;

   c.data[p].v=a.data[p].v; I++;

   else{                   

         p++; c.data[p].i=b.data[j].i; c.data[p].j=b.data[j].j;

         c.data[p].v=b.data[j].v; j++;}

}c.tu=p;                     

}

7.设表达式已存入字符数组A[n]中。

  Void prool(A[n])

  {Initstack (d); I=0; flag =true;

   while ((I<n)&&(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++;

  }

}

8.int akm(int m ,int n)

  {if (m= =0) return(n+1);

else if (n= =0) return(akm (m-1,1));

   else return(akm(m-1,akm(m,n-1)));

}

9. int f(int m, int n )

   {if (m*n= =0) return(m+n+1);

else return(f(m-1,f(m,n-1)));

}

10. 用Knap(S,n)表示背包问题的解，这是一个布尔函数，其参数应满足 S>0,n≥1。背包问题如果有解，其选择只有两种可能：一种是选择的一组物品中不包含W_n，这样Knap(S,n)的解就是Knap(S,n-1)的解，另一种是选择中包含W_n，这时Knap(S,n)的解就是Knap(S-W_n,n)的解。另外可以定义：当S=0时，背包问题总有解，即Knap(0,n)=true ，只要不选择任何物品放入背包即可：当S〈0时，背包问题无解，即Knap(S,n)=false，因为无论怎样选择总不能使重量之和为负值，当S>0但n<1时，背包问题也无解，即Knap(S,n)=false，因为不取任何东西就要使重量为正值总是办不到的。从而，背包问题可以递归定义如下：

                     ╭

                     | true,    当S=0

                     | false,   当S<0  

        Knap(S,n)=  <   false,     当 s>0且 n<1

                     |  Knap(S,n-1)或Knap(S- ,n-1)，      当s>0 且 n>=1

                     |

上述递归定义是确定的，因为每递归一次n都减1，S也可能减少   ，所以递归若干次以后，一定会出现S≤0或者  n=0，无论哪种情况都可由递归出口明确定值。

   Int knap(int s ,int n)

    {if (s==0) return(1);

     else if (s<0||(s>0&&n<1)) return(0);

  else if (knap(s-w[n],n-1)){printf(“%d”,w[n]);return(1);}

    else return(knap(s,n-1));

    }

11.方法是先依次让单链表上的元素进栈，然后再依次出栈。

   Void invert (lklist head)

{LstackTp s;

 initstack(s);

 p= head;

  while (p<>null)

   {Push (s,p->data);p=p->next;}

   p=head;

  while(not emptystack(s))

   {pop(s,p->data); p=p->next;}

}