参考答案一、名词解释（略）
二、填空题先进后出、后进先出，后进先出，进栈，入栈，退栈，出栈初始化InitStack(S)、进栈Push(S,X),退栈Pop(S)，读栈顶Top(S),判栈空Empty(S)
下溢上溢顺序、链接栈空、下溢、栈满、上溢
sq->top=0
sq->top++,sq->data[sq->top]
sq->data[sq->top],sq->top—
sq->top= =0
sq->top= =0,sq->data[sq->top]
ls=NULL
p->data=x,ls=p
p->data,free(p)
*x=ls->data
更小的“尺度”、递归队、队尾、队头队列初始化InitQueue(Q)、入队列EnQueue(Q,X)、出队OutQueue(Q,X)、判队列空EmptyQueue(Q)、读队头ead(Q,x)
假溢出
sq->front=0
sq->front,sq->rear=(sq->rear+1)%maxsize,sq->data[sq->rear]=x
sq->rear,sq->fornt=(sq->rear+1)%maxsize,*x= sq->data[sq->rear]
sq.rear= sq.front
sq.front,(sq.front+1)%maxsize
队满、队空
lq->front=p,NULL
p->data,p,lq->rear=p
*x,s->next
lq.rear= =lq.front
p=lq.front->next,*x
n-1,读、写顺序、列序、行序、行、列特殊、稀疏
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];/*这里假定三元组的下标的起始值为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
f1(i)=
当i>j
j 当i<=j
f2 (j)=
当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; /*赋行数、列数和非0元素数*/
}
6．本题首先判断三元组A，B表示的矩阵是否行列相同，若相同才能进行矩阵的加法运算。若三元组表示的矩阵能进行相加运算，其思路如下：
若a,b表的指针均没有到表尾，重复下列步骤：
若a表元素的i 域值小于b表元素的i域值，将a表当前元素插入到c表表尾,a表指针后移。
若a表元素的i 域值大于b表元素的i域值，将b表当前元素插入到c表表尾,b表指针后移。
若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)) /*a，b为同行同列矩阵*/
{c.mu=a.mu ;c.nu=a.nu; I=1; j=1; p=0;
if (a.tu&&b.tu) /*a，b为非空矩阵*/
{cola=a.data[I].i; rowa = a.data[I],j; /*取三元组a的元素的行、列下标*/
colb= b.data[j].i; rowb =b.data[j],j; /*取三元组b的元素的行、列下标*/
while ((I<=a.tu)&&(j<=b.tu))
switch
{cola <colb,/*在c中，插入三元组a的元素*/
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; /*a元素后移*/
Cola>colb,/*在c中，插入三元组b的元素*/
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; /*b元素后移*/
Cola =colb,
P++; /*三元组 a，b的元素I域相等*/
If (rowa<rowb) /*在c中插入三元组a的元素*/
{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中插入三元组b的元素*/
{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)
/*a中的元素和b中的元素I，j的域都相等且v域的和非零*/
{c.data [p].i =a.data[I].i ;/*在c中元素*/
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++}; /*a中元素和b中元素的I，j域都相等且v 域的和为零*/
break;
} /*swith结束*/
}
if (I<=a.tu) /*b表到表尾，将a表中剩余元素插入到C表中*/
{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{ /*a表到表尾，将b表中剩余元素插入到C表中*/
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; /*c表赋非零元素个数*/
}
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。背包问题如果有解，其选择只有两种可能：一种是选择的一组物品中不包含Wn，这样Knap(S,n)的解就是Knap(S,n-1)的解，另一种是选择中包含Wn，这时Knap(S,n)的解就是Knap(S-Wn,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;}
}
二、填空题先进后出、后进先出，后进先出，进栈，入栈，退栈，出栈初始化InitStack(S)、进栈Push(S,X),退栈Pop(S)，读栈顶Top(S),判栈空Empty(S)
下溢上溢顺序、链接栈空、下溢、栈满、上溢
sq->top=0
sq->top++,sq->data[sq->top]
sq->data[sq->top],sq->top—
sq->top= =0
sq->top= =0,sq->data[sq->top]
ls=NULL
p->data=x,ls=p
p->data,free(p)
*x=ls->data
更小的“尺度”、递归队、队尾、队头队列初始化InitQueue(Q)、入队列EnQueue(Q,X)、出队OutQueue(Q,X)、判队列空EmptyQueue(Q)、读队头ead(Q,x)
假溢出
sq->front=0
sq->front,sq->rear=(sq->rear+1)%maxsize,sq->data[sq->rear]=x
sq->rear,sq->fornt=(sq->rear+1)%maxsize,*x= sq->data[sq->rear]
sq.rear= sq.front
sq.front,(sq.front+1)%maxsize
队满、队空
lq->front=p,NULL
p->data,p,lq->rear=p
*x,s->next
lq.rear= =lq.front
p=lq.front->next,*x
n-1,读、写顺序、列序、行序、行、列特殊、稀疏
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];/*这里假定三元组的下标的起始值为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
f1(i)=
当i>j
j 当i<=j
f2 (j)=
当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; /*赋行数、列数和非0元素数*/
}
6．本题首先判断三元组A，B表示的矩阵是否行列相同，若相同才能进行矩阵的加法运算。若三元组表示的矩阵能进行相加运算，其思路如下：
若a,b表的指针均没有到表尾，重复下列步骤：
若a表元素的i 域值小于b表元素的i域值，将a表当前元素插入到c表表尾,a表指针后移。
若a表元素的i 域值大于b表元素的i域值，将b表当前元素插入到c表表尾,b表指针后移。
若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)) /*a，b为同行同列矩阵*/
{c.mu=a.mu ;c.nu=a.nu; I=1; j=1; p=0;
if (a.tu&&b.tu) /*a，b为非空矩阵*/
{cola=a.data[I].i; rowa = a.data[I],j; /*取三元组a的元素的行、列下标*/
colb= b.data[j].i; rowb =b.data[j],j; /*取三元组b的元素的行、列下标*/
while ((I<=a.tu)&&(j<=b.tu))
switch
{cola <colb,/*在c中，插入三元组a的元素*/
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; /*a元素后移*/
Cola>colb,/*在c中，插入三元组b的元素*/
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; /*b元素后移*/
Cola =colb,
P++; /*三元组 a，b的元素I域相等*/
If (rowa<rowb) /*在c中插入三元组a的元素*/
{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中插入三元组b的元素*/
{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)
/*a中的元素和b中的元素I，j的域都相等且v域的和非零*/
{c.data [p].i =a.data[I].i ;/*在c中元素*/
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++}; /*a中元素和b中元素的I，j域都相等且v 域的和为零*/
break;
} /*swith结束*/
}
if (I<=a.tu) /*b表到表尾，将a表中剩余元素插入到C表中*/
{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{ /*a表到表尾，将b表中剩余元素插入到C表中*/
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; /*c表赋非零元素个数*/
}
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。背包问题如果有解，其选择只有两种可能：一种是选择的一组物品中不包含Wn，这样Knap(S,n)的解就是Knap(S,n-1)的解，另一种是选择中包含Wn，这时Knap(S,n)的解就是Knap(S-Wn,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;}
}
