东北大学：《数据结构》课程教学资源（学习资料）第三章 参考答案

第三章参考答案 、名词解释(略) 、填空题 1、先进后出、后进先出,后进先出,进栈,入栈,退栈,出栈 2、初始化 Initstack(S)、进栈Push(S,X),退栈Pop(S),读栈顶Top(S),判栈空 Empty(S) 3、下溢 4、上溢 5、顺序、链接 6、栈空、下溢、栈满、上溢 9, sq->data(sq->top), sq->top- sq->top==0, sq->data sq->topl 12 IS=NULL 13、 14、p->data,free(p) *x=Is->data 16、 更小的“尺度”、递归 队、队尾、队头 队列初始化 InitQueue(Q)、入队列 EnQueue(QX)、出队 Out Queue(Q,X)、判队列空 Empty Queue(Q、读队头eadQ,x) 假溢出 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 sq rear= sq front 24, sq front, (sq front+ 1)%maxsize 队满、队空 1q->front=p, NULL 27、p-> data,p,lq >rear-p Iq. rear==lq. front 30、p= =lq. front->next* 31 ,读、写 顺序、列序、行序、行、列 特殊、稀疏 n(n+1)/2 i(i-)/2+j当i j(-1)/2+i当i 36、nt+1,(i-1)(2n1+2)2J-i+1

1 第三章 参考答案 一、名词解释（略） 二、填空题 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-计+2)2+计+1当i nn+1)/2+1 1)/2+j当ij n(n+1)/2+1 38, colinfo 43、2230.2374 46、EA+222EA+117 47 48、540,108,M3[10 三、单项选择题 1、④2、①3、④4、①5、③6、②7、①8、③9、④10② ll、②12、③13、①②14、②15、④16、①17、②18、③19、④20、① 21、②22、①23、③24、①25、②26、③27、②28、②29、②30 四、简答及应用 1、顺序栈类型定义如下 define sqstack maxsize顺序栈的容量 typedef struct sqstack Data lype maxsize 它有两个域:data和top。Data为一个一维数组,用于存储栈中元素, DataType为栈元素的 数据类型。Top为int型,它的实际取值范围为0- sqstack maxsize-1 2、链栈的类型定义如下 typedef stuct node t DataType data; 单链表的第一个结点就是链栈栈顶结点,链栈由栈顶指针惟一确定。栈中的其它结点通过它 们的next域链接起来不。栈底结点的next域为NULL 3、顺序队列的类型定义如下 # define maxsize顺序栈的容量 typedef struct sqqueue data mansize int fornt iSqQueueTp

2 (i-1)(2n-i+2)/2+j-i+1 当 ij n(n+1)/2+1 37、 (i-1)/2+j 当 i≧j k= n(n+1)/2+1 当 iinfo 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 该类型变量有三个域:data, front rear。其中data存储队中元素的一维数组。队头指针 front 和队尾指针rear定义为整型变量,实际取值范围为0~ maxsize-1。 循环队列的类型定义如下 #define maxsize 循环队的容量 typedef struct cycqueue( Data Type data( maxsize] I CycqueueTp 4 typedef struct linked queue i Data Type data; i LqueueTp typedef struct queueptr i LqueueTp *front, *rear; P QueptrTp ueptrTp lq 5、# define maxnum 非零元素的容量 typedef struct node Int 1,;/*非零元素所在的行号、列号*/ Data lype v,/*非零元素的值* ANODE typedef struct smatrix Int mu,nu,tu,/*行数、列数、非零元素的个数 NODE data maxnum+1]}/*这里假定三元组的下标的起始值为1*/ 6、 int length( flen=(sq. rear-sq front+maxsize)%m return(len) 7、1234、4321、2143、3421、3241、1324、1432、1342、1243、3214、2134、2314、2341、 2431 1(2n-计+1)/2当i fI(i= 当 当i三j 当 n(n+1)2+1当pj 9、(1)k=2i+j-2;(iJ=1,2,…n) (2)F=ceil((k+1)/3) j=floor(k/)+k mod 3 10、运行结果: ABCDEFGHIJKLM

3 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 当 ij j 当 ij -n 当 ij 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 l1、借助栈将一个带头结点的单链表倒置 Iop>区s Top-> 调用f(5)前调用f(5)前调用f(4)前调用f(3)前调用f(2)前调用f(1)前 ToD-> 返回f(1)后 返回f(2)后返回 返回f(4)后运回f5)后 五、算法设计 1.本程序中,将客车类定义一个队KE,货车类定义一个队HE,过江渡船定义成一个栈 DC。栈采用顺序存储结构,队采用链式存储结构。 #define sqstack maxsize 10 typedef struct sqstack Data Type data( sqstack maxsize] i SqStackTp typedef struct linked queue i Data lype data; struct linked queue "next G Queue typedef struct queueptr QueptrTp int InitStack (SqStackTp *sq) (sq->top=0; return(1); void Init Queue( QueptrTp "lp) ueue p=(lqueueTp *)malloc(sizeof(lqueueTp)) lq->rear=p;

4 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) ULL. int Qut Queue( QueptrTp *lp, Data Type*x) queueT if(lq→ front==lq>rear){eror(“队空”); return(O), else (s=(lq->front)->nest (1q->front)->next=s->next; if(s->next== NULL) lq->rear=llq->front free(s) return(1); int Empty Queue(Queptr Tp Iq) fif(lq. rear=lq front )return(1) int Push(SqStackTp *sq, Data Type x) f if(sq->top==sqstack maxsize-q)(return(0) else (sq->top++; sq->data(sq->top=x return(1); i oid maino SqStackTp DO,∥DC表示渡船 QueptrtTp KE,H;∥KE表示客车E、HE表示货车 Intt j=0 Initstack(DC) While(dc. top<sqstack maxsize) for(=j<=4I++)∥先上4辆客车 if (lemptyqueue(KE)&&(DC. top <sqstack maxsize) f outqueue(&KE, &t); Push(&DC, t ) ;j++ for(l=j<5,++)再上1辆货车或客车不足时用货车补足 if (lemptyqueue(HE)&&(DC. top< sqstack maxsize) foutqueue(&HE, &t); Push(&DC, t); j++ f(<5)for(1=j<5,I++)∥当货车不足时用客车补足 f(lemptyqueue( KE)&&(DC. top <sqstack maxsize)) foutqueue(&Ke, &t); Push( &DC, t); j++ else printf(“客车、货车合计不足10辆!”); 2. typedef struct dustack Data Typeelem[1: MI

5 ( 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 topO, topl void initstack( dustup*S)/初始化* void push( dustup*S, Data Type X,intI)/"指示是栈0或栈1入栈* if(S->topO==s>topl-l)eror(“栈满!”) else if(1==0)(s->top++; S->elem((S->topOFX else (S->top1--; S->elem[S->topl=X) void pop( dustktp*S, Data Type"X,intI)/I指示是栈0或栈1入栈* if(S->top0=0)eror(“栈空!”) [ s->topo] s->top0- else{if(S->tpl==M+l)eror(“栈空!”) else *X=S->elem[S->top1]: S->top1++ 3 void initqueue( list*1q)/初始化* Ig->next=l it+lq, Data Type*X)/*入队列*/ i p=malloc(size); p->data=X lq= void outqueuel( list*lq, Data Type*X)/出队列* if(lq->next=q)eror(“队空!”) xt; q=p->next; i 4.设 cycque(m rearlquelen皆为全局变量 viod enqueue(Data lype cycquelm Data lype X) if( quelen==m+1)eror(“队满!”) cquelreal=X; q void outqueue( Data lype cycquem Data Type * X)

6 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)eror(“队空!”); else{ frone=(real- quelen+1+(m+1)%m+1),/计算对头下标* X-cycque frone]; quelen 5. void trans mat trix(Date lype a[mJ[n], SpMatrix Tp b) for(I=1; I<=m; 1++) for(=l; j<=n:j++) f(aj)/*非零元素 /*给三元组赋值* b. datalp b data[p]=j b. datalp]. v=alll bmu=m;bnu=n;b.tu=p,/*赋行数、列数和非0元素数* 6.本题首先判断三元组A,B表示的矩阵是否行列相同,若相同才能进行矩阵的加法 运算。若三元组表示的矩阵能进行相加运算,其思路如下: 若ab表的指针均没有到表尾,重复下列步骤: (1)若a表元素的ⅰ域值小于b表元素的i域值,将a表当前元素插入到c表表尾,a 表指针后移。 (2)若a表元素的ⅰ域值大于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表表尾播入元素的IU域值等于a表当前元素的I域的值,域v的值等于a,b表 的域值的和,将a,b表当前指针后移 (4)若a表的指针没到表尾,b表的指针到表尾,将a表剩余元素依次插入到c表表尾 否则,将b表剩余元素依次插入到c表表尾 SpMaterixTp trsxsum(SpMaterixTp a, SpMaterixTp b, SpMaterixTp c lif((a. mu=b. mu)&&(a nu=b mu)) /*a,b为同行同列矩阵*/ Ic mu=a. mu :c nu=a. nu: I=l: j=l: p=0 f(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的元素的行、列下标* hile((I<=a tu)&&(j<=b tu)) cola<colb:/*在c中,插入三元组a的元素*/ p++:c data [p].i=. data [I].i

7 /*出队列*/ {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 表的指针均没有到表尾，重复下列步骤： （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)) /*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] I++; break;/*a元素后移*/ /*在c中,插入三元组b的元素*/ P++;Cdata[]. i=b data [j Lp].j=b data [j].j c data [p],v= b data [j]v j+; break;/*b元素后移*/ la =colb /*三元组a,b的元素I域相等 If (rowarowb)/*在c中插入三元组b的元素*/ Ic. datalp] i=b. dataljl c. data [p]. j=b. data[j].j: c. datalp] v= b data[j]v:j++ else if (a data[l]v +b data] v) /*a中的元素和b中的元素I,j的域都相等且v域的和非零*/ c.data[p].i=a.data[I].i;/在c中元素* C. data[p]. j=a data[j]. j c. datalp] v=a data[l. v+b. dataLj]v }else{p-;I++;j++};/*a中元素和b中元素的I,j域都相等且v 域的和为零*/ break /* swith结束* if (I<=a tu /*b表到表尾,将a表中剩余元素插入到C表中*/ Ip++: c. datalp] i =a data lp].i: c data lp]. j=a. datalp c. datalp] v=a. datalp]v:I++ else( /*a表到表尾,将b表中剩余元素插入到C表中*/ p++c. data [p]. i=b. data[]. i: c data lp]. j=b. datalj] c. datalp]v=b. datalj] 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[={)Push(s,A[I]); else if((A[i]=“)’)|1(A[Push(s,A[I])

8 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 (rowarowb) /*在 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=Get Top(s) switch(a[I]) if(x=’(’)pop(s) else flag =fal case’]’:if(x=[]’)pop(s) else flag=false break case e’}’:if(x={}’)pop(s) else flag=false 8. int akm (int m, int n) fif (m==0)return(n+1); else if(n==0)return(akm(m-1, 1)) else return(akm(m-1, akm(m, n-I)) 9. int f(int m, int n fif(m*n==)return(m+n+1); else return(f(m-1, f(m, n-1)) } 10.用Knap(S,n)表示背包问题的解,这是一个布尔函数,其参数应满足S0,n≥1。背包问 题如果有解,其选择只有两种可能:一种是选择的一组物品中不包含Wn,这样Knap(S.n) 的解就是Knap(S,n1)的解,另一种是选择中包含Wn,这时Knap(S.n)的解就是Knap(S-Wan) 的解。另外可以定义:当S=0时,背包问题总有解,即 Knap(O,n)=true,只要不选择任何 物品放入背包即可:当S(0时,背包问题无解,即Knap(S,n)= false,因为无论怎样选择总 不能使重量之和为负值,当S>0但n0且n0且n>=1 上述递归定义是确定的,因为每递归一次n都减1,S也可能减少,所以递归若干 次以后,一定会出现S≤0或者n=0,无论哪种情况都可由递归出口明确定值 Int knap int s, int n lif (s==0) return( else if (s0&&n<1))return(0) else if (knap(s-w[n], n-1))printf( "%d",wn]); return(1): I else return(knap(s, n-1))

9 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 但 n0 且 n0 且 n>=1 | 上述递归定义是确定的，因为每递归一次 n 都减 1，S 也可能减少 ，所以递归若干 次以后，一定会出现 S≤0 或者 n=0，无论哪种情况都可由递归出口明确定值。 Int knap(int s ,int n) {if (s==0) return(1); else if (s0&&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 nitstack(s hile (p>null) (Push (s, p->data); p=p-next: I p=head while(not emptystack(s)) pop (s, p->data); p=p->next: I

10 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;} }