学习必备 欢迎下载
{
ListNode *p=L,*q;
if(L->next->data==X) {
printf(“值为x的结点是第一个结点，没有直接前趋结点可以删除”); return; }
For(p->next->data!=X;q=p;p=p->next);// 删除指针p所指向的结点
q->next=p->next; delete p;
}
（3） 已知一个单向链表，编写一个函数从单链表中删除自第i个结点起的k个结点。 解：
void Del(node *head,int i,int k) {
node *p,*q; int j; if(i==1)
for(j=1;j<=k;j++) // 删除前k个元素 {
p=head; // p指向要删除的结点 head=head->next;
delete p; } else {
p=head;
for(j=1;j<=i-2;j++)
p=p->next; // p指向要删除的结点的前一个结点 for(j=1;j<=k;j++) {
q=p->next; // q 指向要删除的结点 p->next=q->next;
delete q;
} } }
（4） 有一个单向链表（不同结点的数据域值可能相同），其头指针为head，编写一个函
数计算值域为x的结点个数。
解：//本题是遍历单链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下：
int counter(head) node *head； { node *p; int n=0;
学习必备 欢迎下载
p=head；
while(p!=NULL) { if(p->data==x)
n++； p=p->next; }
return(n); }
（5）有两个循环单向链表，链头指针分别为head1和head2，编写一个函数将链表head1链接到链表head2，链接后的链表仍是循环链表。
解：//本题的算法思想是：先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，使之成为循环的。函数如下：
node *link (node *head1, *head2) { node *p,*q; p=head1;
while(p->next!=head1)
p=p->next; q=head2;
while(q->next!=head2)
q=q->next; p->next=head2; q->next=head1; return (head1); }
学习必备 欢迎下载
单元练习3
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（√）（1）栈是运算受限制的线性表。
（√）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。 （ㄨ）（3）栈一定是顺序存储的线性结构。 （√）（4）栈的特点是“后进先出”。 （ㄨ）（5）空栈就是所有元素都为0的栈。
（ㄨ）（6）在C或C++语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示队满。 （√）（7）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。 （ㄨ）（8）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。 （ㄨ）（9）递归定义就是循环定义。
（√）（10）将十进制数转换为二进制数是栈的典型应用之一。
二．填空题
（1）在栈结构中，允许插入、删除的一端称为 栈顶 。 （2）在顺序栈中，当栈顶指针top=-1时，表示 栈空 。 （3）在有n个元素的栈中，进栈操作的时间复杂度为 O（1）。 （4）在栈中，出栈操作的时间复杂度为： O(1) 。 （5）已知表达式，求它的后缀表达式是 栈 的典型应用。 （6）在一个链栈中，若栈顶指针等于NULL，则表示 栈空 。
（7）向一个栈顶指针为top的链栈插入一个新结点*p时，应执行 p->next=top； 和top=p；操作。
（8）顺序栈S存储在数组 S->data[0..MAXLEN-1]中，进栈操作时要执行的语句有：
S->top ++ 。（或= S->top+1）
（9）链栈LS，指向栈顶元素的指针是 LS->next 。
（10）从一个栈删除元素时，首先取出 栈顶元素 ，然后再移动栈顶指针。 （11）由于链栈的操作只在链表的头部进行，所以没有必要设置 头 结点。 （12）已知顺序栈S，在对S进行进栈操作之前首先要判断 栈是否满 。 （13）已知顺序栈S，在对S进行出栈操作之前首先要判断 栈是否空 。 （14）若内存空间充足， 链 栈可以不定义栈满运算。 （15）链栈LS是空的条件是 LS->next=NULL 。 （16）链栈LS的栈顶元素是链表的 首 元素。 （17）同一栈的各元素的类型 相同 。
（18）若进栈的次序是A、B、C、D、E，执行三次出栈操作以后，栈顶元素为 B 。 （19）A+B/C-D*E的后缀表达式是： ABC/+DE*- 。
（20）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，x的值是 C 。
学习必备 欢迎下载
三．选择题
（1）插入和删除只能在一端进行的线性表，称为( C )。 A．队列 B．循环队列 C．栈 D．循环栈
（2）设有编号为1，2，3，4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为 ( D )
A．1234 B．1243 C．1324 D．1423 （3）如果以链表作为栈的存储结构，则出栈操作时（ B ） A．必须判别栈是否满 B．必须判别栈是否空 C．必须判别栈元素类型 D．队栈可不做任何判别 （4）元素A,B,C,D依次进栈以后，栈顶元素是（ D ） A．A B．B C．C D．D （5）顺序栈存储空间的实现使用（ B ）存储栈元素。 A．链表 B．数组 C．循环链表 D．变量
（6）在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（ A ）。 A．已固定 B．不固定 C．可以改变 D．动态变化 （7）带头结点的链栈LS的示意图如下，栈顶元素是（ A ） LS H
A．A B．B C．C D．D （8）链栈与顺序栈相比，有一个比较明显的优点是（ B ）。
A．插入操作更加方便 B．通常不会出现栈满的情况。 C．不会出现栈空的情况 D．删除操作根加方便
（9）从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 ( D )命令。
A．x=top;top=top->next; B．top=top->next;x=top->data; C．x=top->data; ( B )命令。
A．HS->next=S; B．S->next=HS->next;HS->next=S; C．S->next=HS->next;HS=S; D．S->next=HS;HS=HS->next;
（11）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，栈顶元素的值是（ B ）。
A．A B．B C．C D．D （12）元素A,B,C,D依次进栈以后，栈底元素是（ A ）。 A．A B．B C．C D．D （13）经过下列栈的运算后，再执行ReadTop(s)的值是（ A ）。
D．x=top->data;top=top->next;
（10）在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列- A B C D Λ 学习必备 欢迎下载
InitStack(s) （初始化栈）;Push(s,a);Push(s,b); Pop(s)
A．a B．b C．1 D．0 （14）经过下列栈的运算后，x的值是（ B ）。
InitStack(s) （初始化栈）;Push(s,a);Push(s,b); ReadTop(s);Pop(s,x);
A．a B．b C．1 D．0 （15）经过下列栈的运算后，x的值是（ B ）。
InitStack(s) （初始化栈）;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);
A．a B．b C．1 D．0 （16）经过下列栈的运算后，SEmpty(s)的值是（ C ）。
InitStack(s) （初始化栈）; Push(s,a); Push(s,b);Pop(s,x); Pop(s,x);
A．a B．b C．1 D．0 （17）向顺序栈中压入元素时，（ B ）。
A． 先存入元素，后移动栈顶指针 B．先移动栈顶指针，后存入元素 C．谁先谁后无关紧要 D．同时进行
（18）初始化一个空间大小为5的顺序栈S后，S->top的值是（ B ）。 A．0
B．-1 C．不再改变 D．动态变化
C．DCEAB
D．ABCDE
（19）一个栈的入栈次序ABCDE，则栈的不可能的输出序列是 ( C )。 A．EDCBA B．DECBA
（20）设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是B，D，C，F，E，A，则栈的容量至少应是 ( A )。 A．3 B．4
C．5 D． 6
四．应用题
（1）设有一个栈，元素进栈的次序为：A，B，C，D，E，用I表示进栈操作，O表示出栈操作，写出下列出栈的操作序列。
①C，B，A，D，E ②A，C，B，E，D 解：①IIIOOOIOIO
②IOIIOOIIOO
（2） 求后缀表达式 ① A^B^C/D 解：A B ^ C ^ D / ② -A+B*C+D/E
解：0 A – B C * + D E / + ③ A*(B+C)*D-E 解：A B C + * D * E - ④ (A+B)*C-E/(F+G/H)-D
解：A B + C * E F G H / + / - D -
实用数据结构基础(第三版)课后答案
