top=top–M; } } }
（2）设计一个算法，要求判别一个算术表达式中的圆括号配对是否正确。 解：//设表达式在字符数组a[ ]中，使用一堆栈S来帮助判断。 int correct (char a[ ]) {
stack s ;
InitStack (s); //调用初始化栈函数 for (i=0; i if (a[i]= =’)’) { if StackEmpty (s) //调用判栈空函数 return 0; //若栈为空返回0；否则出栈 else Pop(s); } if (StackEmpty (s) ) //调用判栈空函数 printf (“配对正确！”); //若栈空，说明配对正确，并返回1 else printf (“配对错误！”); //配对错误返回0 } （3） 设计一个将十进正整数转换为十进制数的算法，并要求上机调试通过。 解： #include typedef struct stacknode { int data; struct stacknode *next; }stacknode; typedef struct { stacknode *top; //定义栈顶的指针 //栈的应用：十——十六进制转换 }linkstack; void Conversion(int n) { linkstack s; int x; s.top=NULL; do 17 //定义栈的存储结构 //置栈空 { x=n; //取余数 n= n/16 ; //取新的商 stacknode *p=new stacknode; //申请新结点 p->next=s.top ; //修改栈顶指针 s.top=p; s.top->data=x; //余数入栈 } while(n); printf(\转换后的十六进制数值为：\ while (s.top) { if(s.top->data<10); printf(\ else switch(s.top->data) { case 10: printf(\case 11: printf(\case 12: printf(\case 13: printf(\case 14: printf(\case 15: printf(\} stacknode *p=s.top; s.top=s.top->next; free(p) ; } printf(\} void main() { int n; printf(\请输入一个十进制正整数：\scanf(\Conversion(n); } 18 //出栈处理 //出栈一个余数，收回一个结 单元练习4 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ） （√）（1）队列是限制在两端进行操作的线性表。 （√）（2）判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。 （×）（3）在链队列上做出队操作时，会改变front指针的值。 （√）（4）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。 （×）（5）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。 （√）（6）链队列在一定范围内不会出现队满的情况。 （×）（7）在循环链队列中无溢出现象。 （×）（8）栈和队列都是顺序存储的线性结构。 （×）（9）在队列中允许删除的一端称为队尾。 （×）（10）顺序队和循环队关于队满和队空的判断条件是一样的。 二．填空题 （1） 在队列中存取数据应遵循的原则是 先进先出 。 （2） 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删 除运算的线性表。 （3） 在队列中，允许插入的一端称为 队尾 。 （4） 在队列中，允许删除的一端称为 队首（或队头） 。 （5） 队列在进行出队操作时，首先要判断队列是否为 空 。 （6） 顺序队列在进行入队操作时，首先要判断队列是否为 满 。 （7） 顺序队列初始化后，front=rear= -1 。 （8） 解决顺序队列“假溢出”的方法是采用 循环队列 。 （9） 循环队列的队首指针为front，队尾指针为rear，则队空的条件为 front == rear 。 （10） 链队列LQ为空时，LQ->front->next= NULL 。 （11） 设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间 复杂度为 O（n）。 （12） 设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间 复杂度为 0（1） 。 （13） 在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为 空 。 （14） 设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一 个空闲元素，队列的最大空间为MAXLEN，则队满标志为： front==(rear+1)%MAXLEN 。 （15） 在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只 有一个结点的条件为： front==rear && front !NULL 。 19 ( 或 front==rear && front <>NULL ) （16） 向一个循环队列中插入元素时，首先要判断 队尾指针 ，然后再向指 针所指的位置写入新的数据。 （17） 读队首元素的操作 不改变（或不影响） 队列元素的个数。 （18）设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19，则循环队列中还有 8 个元素。 （L= (N＋rear－front)% N=（40＋19－11）% 40=8） （19）队列Q，经过下列运算：InitQueue(Q)(初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是 0 。 （20）队列Q经过InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b); ReadFront(Q,x)后，x的值是 a 。 三．选择题 （1）队列是限定在（ D ）进行操作的线性表。 A．中间 A．不变的 B．队首 B．可变的 C．队尾 C．任意的 D．端点 D．0 D．不限制 D．非 （2）队列中的元素个数是( B )。 （3）同一队列内各元素的类型( A )。 A．必须一致 B．不能一致 C．可以不一致 （4）队列是一个( C )线性表结构。 A．不加限制的 B．推广了的 C．加了限制的 （ B ）。 A．n-2 B．n-1 C．n D．n+1 C．不能固定 D．动态变化 C．不能连续 D．可以不连续 （6）一个循环队列一旦说明，其占用空间的大小（ A ）。 A．已固定 B．可以变动 （7）循环队列占用的空间( A )。 A．必须连续 ( B )。 A．0..10 B．0..9 A．B，C，D，A C．A，B，C，D A． A C． C C．1..9 D．1..10 B．A，C，B，D D．C，B，D，A B． B D． D （9）若进队的序列为：A，B，C，D，则出队的序列是（ C ）。 B．不必连续 （8）存放循环队列元素的数组data有10个元素，则data数组的下标范围是（5）当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为 （10）四个元素按：A，B，C，D顺序连续进队Q，则队尾元素是（ D ）。 （11）四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q)操作后，队 20