数据结构 用C语言描述 课后答案(5)

第三章 栈和队列

课堂习题

1、现在A、B、C、D四个元素相继进行入栈操作，下面不可能得到的入栈序列为： 1) ABCD 2) BDAC 3) CBDA 4)DCBA 【解答】2)

说明:在此选项中第一个出栈的元素为B,说明元素A必定在栈内,而第二个出栈的元素为D,则说明元素C也必定在栈内,那么A和C在栈内的位置必为C在A之上,因此元素C肯定比元素A选出栈.

2、试写一个判别表达式开、闭括号是否配对出现的算法。 【解答】

STATUS EXAMPLE(SQSTACK *S,CHAR A[]) {INT I;CHAR E;

FOR(I=0;I

IF (A[I]=='('||A[I]=='[') PUSH(S,A[I]); ELSE {IF(A[I]==')')

IF (S->TOP==S->BASE||*(S->TOP-1)=='[') RETURN 0; ELSE POP(S,&E); IF(A[I]==']')

IF (S->TOP==S->BASE||*(S->TOP-1)=='(') RETURN 0; ELSE POP(S,&E); }

IF (S->TOP==S->BASE) RETURN 1; ELSE RETURN 0; }

MAIN()

{SQSTACK S; CHAR A[80];

ELEMTYPE ELEM,E;

IF (INITSTACK(&S)==1) PRINTF(\ PRINTF(\ SCANF(\

IF (EXAMPLE(&S,A)) PRINTF(\ ELSE PRINTF(\ GETCH(); }

3、试写一算法，识别依次读入的一个以@为结束符的字符序列是否是形如“序列&序列2”的字符序列，其中序列1和序列2均不含字符&，且序列2是序列1的逆序。 【解答】

STATUS SYSERR() {INITSTACK(S); CH=GETCHAR();

WHILE (CH!='&') {IF CH=’@’ RETRUN ERROR;PUSH(S,CH);CH=GETCHAR();} CH=GETCHAR(); WHILE(CH!='@')

{IF CH='&' THEN RETURN(FALSE);

IF (S->TOP=S->BASE) THEN RETURN(FALSE); IF (*(S->TOP-1)!=CH) THEN RETURN(FALSE); POP(S);CH=GETCHAR(); }

IF S->TOP!=S->BASE THEN RETURN(FALSE); ELSE RETURN(TRUE); }

4、指出下列程序段的功能是什么？ 1)VOID DEMO1(SQSTACK *S) {INT I,ARR[64],N=0;

WHILE (!STACKEMPTY(S)) ARR[N+1]=POP(S); FOR(I=0;I

WHILE(!QUEUEEMPTY(Q)) {X=DEQUEUE(Q);PUSH(&S,X);} WHILE(!STACKEMPTY(&S)) {X=POP(&S);ENQUEUE(Q,X);} }

【解答】将队列Q中的元素序列颠倒. 3) CIRQUEUE Q1,Q2; INT X,I,M=0; ……

WHILE(!QUEUEEMPTY(&Q1)) {X=DEQUEUE(&Q1);ENQUEUE(&Q2,X);M++;} FOR(I=0;I

{X=DEQUEUE(&Q2);ENQUEUE(&Q2,X);ENQUEUE(&Q2,X);}

【解答】把队列Q1的内容复制到队列Q2中,同时队列Q1的元素位置顺移N个结点位置.

5、回文是指正读和反读均相同的字符序列，如“ABBA”和“ABDBA”等均是回文，但“GOOD”则不是回文，试写一算法判定读入的一个以\为结束符的字符串是否为回文。 【解答】

STATUS SYS5() {SQSTACK S;

LINKQUEUE Q; CHAR CH; INITSTACK(S); INITQUEUE(Q); CH=GETCHAR(); WHILE(CH!='@')

{PUSH(S,CH);ENQUEUE(Q,CH);} WHILE(!QUEUEEMPTY(Q)) {CH1=DEQUEUE(Q); CH2=POP(S);

IF (CH1!=CH2) RETURN FALSE; }

RETURN(TRUE); }

6、假设循环队定义为：以域变量REAR和LENGTH分别指示循环队列中队尾元素的位置和内含元素个数，试给出此循环队列的队满条件，并写出相应的入队和出队算法。 【解答】

#DEFINE QUQUESIZE 100 TYPEDEF CHAR DATATYPE; TYPEDEF STRUCT{

INT REAR; INT QUELEN;

DATATYPE DATA[QUEUEXIZE]; } CIRQUEUE; 置空队:

VOID INITQUEUE(CIRQUEUE *Q) {Q->REAR=0;Q->QUELEN=0;} 判队空:

INT QUEUEEMPTY(CIRQUEUE *Q) {RETURN(Q->QUELEN==0);} 判队满:

INT QUEUEFULL(CIRQUEUE *Q)

{RETURN(Q->QUELEN==QUEUESIZE);} 入队:

VOID ENQUEUE(CIRQUEUE *Q,DATATYPE X) {IF QUEUEFULL(Q)) ERROR(\ Q->QUELEN++;

Q->REAR=(Q->REAR+1)%QUEUESIZE; Q->DATA[Q->REAR]=X; }

出队:

DATATYPE DEQUEUE(CIRQUEUE *Q) {DATATYPE TEMP; INT FRONT;

IF(QUEUEEMPTY(Q)) ERROR(\ ELSE

{FRONT=(Q->REAR+QUEUESIZE-Q->QUELEN+1)%QUEUESIZE; TEMP=Q->DATA[FONRT]; Q->QUELEN--; RETURN(TEMP); } }

7、试写出双向栈的判定条件以及相应的入栈和出栈算法。 【解答】

#DEFINE STACKSIZE 100 TYPEDEF CHAR DATATYPE TYPEDEF STRUCT

{DATATYPE DATA[STACKSIZE]; INT TOP1,TOP2; }SQSTACK; 初始化,置空栈:

VOID INTISTACK(SQSTACK *S) {S->TOP1=-1;S->TOP=STACKSIZE;} 判栈满:

INT STACKFULL(SQSTACK *S) {RETURN(S->TOP2==S->TOP1+1;} 进栈:

VOID PUSH(SQSTACK *S,DATATYPE X,INT I)

{IF(STACKFULL(S)) ERROR(\ ELSE

{IF(I==0) S->DATA[++S->TOP1]=X; ELSE S->DATA[--S->TOP2]=X; } } 退栈:

DATATYPE POP(SQSTACK *S,INT I) {IF(I==0)

IF(S->TOP1>=0) RETURN S->DATA[S->TOP1--]; ELSE ERROR(\ ELSE

IF(S->TOP2DATA[S->TOP2++]; ELSE ERROR(\ }

8、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试写出相应的置空队、判队空以及入队出队的算法。 【解答】

TYPEDEF CHAR DATATYPE; TYPEDEF STRUCT QUEUENODE {DATATYPE DATA;

STRUCT QUEUENODE *NEXT; }QUEUENODE; TYPEDEF STRUCT

{QUEUENODE *FRONT,*REAR;} LINKQUEUE; 置空队:

VOID INITQUEUE(LINKQUEUE *Q)

{QUEUENODE *P=(QUEUNODE *)MALLOC(SIZEOF(QUEUENODE)); P->NEXT=P; Q->NEXT=P; }

判队空:

INT QUEUEEMPTY(LINKQUEUE *Q)

{RETURN Q->REAR==Q->REAR->NEXT;} 入队:

VOID ENQUEUE(LINKQUEUE *Q,DATATYPE X)

{QUEUENODE *P=(QUEUENODE *)MALLOC(SIZEOF(QUEUENODE)); P->DATA=X;P->NEXT=Q->REAR->NEXT; Q->REAR->NEXT=P; Q->REAR=P;} 出队:

DATATYPE DEQUEUE(LINKQUEUE *Q) {DATATYPE X; QUEUENODE *P;

IF(QUEUEEMPATY(Q)) ERROR(\ ELSE

{P=Q->REAR->NEXT->NEXT; X=P->NEXT;

Q->REAR->NEXT->NEXT=P->NEXT;

IF(P==Q->REAR) Q->REAR=Q->REAR->NEXT; FREE(P); RETURN X;}