smaller－>next = (*C)－>next; (*C)－>next = smaller; }
while ( pa!=NULL)
{ smaller=pa; pa=pa－>next; smaller－>next = (*C)－>next; (*C)－>next = smaller; }
while ( pb!=NULL)
{ smaller=pb; pb=pb－>next; smaller－>next = (*C)－>next; (*C)－>next = smaller; }
< 方法2 >
LinkList merge(LinkList A; LinkList B) { ……
LinkList C；
pa=A－>next; pb=B－>next; C=A; C－>next=NULL; …… ……
return C;
while(pa||pb) {
if(pa->data
pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表 } else {
pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表 }
pre=pc; }
C=A;A->next=pc; //构造新表头 }//reverse_merge
分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.
2.9 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。
[提示]：设指针p指向s结点的前趋的前趋，则p与s有何关系？ Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱 {
p=s;
while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p p->next=s; return OK; }//Delete_Pre
2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型. {
s=L->next;
A=(CiList*)malloc(sizeof(CiLNode));p=A; B=(CiList*)malloc(sizeof(CiLNode));q=B;
C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点 while(s) {
if(isalphabet(s->data)) {
p->next=s;p=s; }
else if(isdigit(s->data)) {
q->next=s;q=s; } else {
r->next=s;r=s; } }//while
p->next=A;q->next=B;r->next=C; //完成循环链表 }//LinkList_Divide
2.11 设线性表A=(a1, a2,…,am)，B=(b1, b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得：
C= (a1, b1,…,am, bm, bm+1, …,bn) 当m≤n时； 或者 C= (a1, b1,…,an, bn, an+1, …,am) 当m>n时。
线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。
[提示]：void merge(LinkList A; LinkList B; LinkList *C) 或：LinkList merge(LinkList A; LinkList B)
void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间 {
p=A->next;q=B->next;C=A; while(p&&q) {
s=p->next;p->next=q; //将B的元素插入 if(s) {
t=q->next;q->next=s; //如A非空,将A的元素插入 }
p=s;q=t; }//while }//merge1
2.12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。 [提示]：注明用头指针还是尾指针。
void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B {
p=L->next;
A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); pa=A;pb=B; while(p!=L) {
if(p->data.exp!=2*(p->data.exp/2)) {
pa->next=p;pa=p; } else {
pb->next=p;pb=p; }
p=p->next; }//while
pa->next=A;pb->next=B; }//Divide_LinkedPoly
2.13 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算 。 [提示]：可将低位放在前面。
2.14 设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。 [提示]：float PolyValue(Polylist p; float x) {……} 第三章 栈和队列
1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴ 如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ ⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。 【解答】
（1）可能得到的出站车厢序列是：123、132、213、231、321。 (2)不能得到435612的出站序列。
因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此时按照“后进先出”的原则，出栈的顺序必须为X(2)X(1)。
能得到135426的出站序列。
因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。
2. 设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作：
（1） 输出队首元素；
（2） 把队首元素值插入到队尾； （3） 删除队首元素； （4） 再次删除队首元素。
直到队列成为空队列为止，则是否可能得到输出序列： （1） A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4） A、C、E、C [提示]：
A、B、C、D、E （输出队首元素A）
A、B、C、D、E、A （把队首元素A插入到队尾） B、C、D、E、A （删除队首元素A） C、D、E、A （再次删除队首元素B）
C、D、E、A （输出队首元素C）
C、D、E、A、C （把队首元素C插入到队尾） D、E、A、C （删除队首元素C） E、A、C （再次删除队首元素D）
3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ 【解答】