文档介绍：习题课-2 ok
1. 设有编号为1、2、3、4的四辆列车,顺序进入一个栈式结构的站台。具体写出这四辆列车开出车站的所有可能的顺序。
共有14种可能开出顺序:
1234、1243、1324、1342、1432、
2134、2143、2314、2341、2431、
3214、3241、3421、
4321
习题-栈
4. 设计算法判断一个算术表达式的圆括号是否正确配对。(提示:对表达式进行扫描,凡遇“(”就进栈,遇“)”,就退掉的“(”,表达式被扫描完毕,栈应为空。)
习题-栈
算法实现:
int PD(char b[],int n)
{struct stack *S;
int i;
S->Top=-1
for(i=0;i<n;i++)
{if(b[i]==‘(’)
{if(S->Top>=maxsize-1) return NULL;
else{
S->Top++;
S->elements[S->Top]=b[i];}
}
if(b[i]==‘)’)
if(s->Top<=-1) return(0);
else S->Top--;
}
if(S->Top==-1) return(1);
else return(0);
}
习题-栈
要不要考虑这种情况:
a+b)+(a+c
7. 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的置空队、入队列和出队列的算法。
前面我们讲过用尾指针表示的循环链表查找开始结点和尾结点非常方便,在这里用循环链表来表示链队列就可以显示出其优点。
习题-队列
置空队:(生成空循环链表)
void SETNULL(linklist *rear)
{rear=(linklist *)malloc(sizeof(linklist));
rear->next=rear;
}
习题-队列
#
rear
入队:
INQUEUE(linklist *rear,datatype x)
{linklist *s;
s=(linklist *)malloc(sizeof(linklist));
s-data=x;
s->next=rear->next;
rear->next=s;
rear=s;
}
习题-队列
#
rear
x
…
s
①
②
③
④
⑤
出队:
长度为1
习题-队列
④
#
rear
s
①
②
③
free(s)
#
rear
…
s
①
②
③
free(s)
长度大于1
算法实现:
datatype DEQUEUE(linklist *rear,datatype x)
{linklist *s;datatype *t;