L.Elem[k]=L.Elem[k+1];
length--;
j--;//移动元素后，由于少了一个元素，因此要减1
}
}//endif
If（L.Elem[j]>L.Elem[i]）break;//第二小问添加此句
}//endfor
}//endwhile
}//endfunctoion
2.8已知线性表L采用链式结构存放。
对两种不同情况分别写出算法，删除L中值相同的多余元素，使得L中没有重复元素：
（1）L中数据元素无序排列；
（2）L中数据元素非递减有序排列。
（1）L中数据元素无序排列；
思路：
由于是无序排列，需要线性表中每个元素都要相互进行比较。
StatusListDelete（Linklist&L）//L是带头结点的线性表
{
ElemType*p,*q;
p==L->next;q=p->next;//设定p变化较慢，q变化较快
while（p->next）{
while（q）{
if（p->data!
=q->data）
q=q->next;
else{
q=q->next;
p->next=q;
}//else
}//while
p=p->next;q=p->next;//开始后一结点的寻找
returnOK；
}//ListDelete
（2）L中数据元素非递减有序排列。
思路：
由于是有序的，遍历一次线性表就行了
StatusListDelete（LinkList&L）
{
ElemType*p,*q;
p=L->next;q=p->next;
while（p->next）
{
if（p->data!
=q->data）{
p=p->next;//和第一问不同地方
q=p->next;
}//if
else{
while（p->data==q->data）
q=q->next;//多个连续的重复值
}//else
p->next=q;p=q;q=p->next;//删除值重复的结点，并修改相应的指针
returnOK；
}//ListDelete
2.9设有两个非递减有序的单链表A,B。
请写出算法，将A和B就地归并成一个按元素值非递增有序的单链表。
//将合并逆置后的结果放在C表中，并删除B表
StatusListMergeOppose_L（LinkList&A,LinkList&B,LinkList&C）
{
LinkListpa,pb,qa,qb;
pa=A;
pb=B;
qa=pa;//保存pa的前驱指针
qb=pb;//保存pb的前驱指针
pa=pa->next;
pb=pb->next;
A->next=NULL;
C=A;
while（pa&&pb）{
if（pa->datadata）{
qa=pa;
pa=pa->next;
qa->next=A->next;//将当前最小结点插入A表表头
A->next=qa;
}
else{
qb=pb;
pb=pb->next;
qb->next=A->next;//将当前最小结点插入A表表头
A->next=qb;
}
}
while（pa）{
qa=pa;
pa=pa->next;
qa->next=A->next;
A->next=qa;
}
while（pb）{
qb=pb;
pb=pb->next;
qb->next=A->next;
A->next=qb;
}
pb=B;
free（pb）;
returnOK;
}
2.13设以带头结点的双向循环链表表示的线性表L=（a1,a2,a3,...,an）。
试写一时间复杂度为O（n）的算法，将L改造为L=（a1,a3,...,an,...,a4,a2）。
voidReform（DuLinkedList&L）//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点
{
p=L.next;
while（p->next!
=L&&p->next->next!
=L）
{
p->next=p->next->next;
p=p->next;
}//p指向最后一个奇数结点
if（p->next==L）//结点个数是奇数，使最后一个奇数结点next指向最后一个偶数结点
p->next=L->pre->pre;
else//结点个数是偶数，使最后一个奇数结点next指向最后一个偶数结点
p->next=L->pre;
p=p->next;//此时p指向最后一个偶数结点
while（p->pre->pre!
=L）
{
p->next=p->pre->pre;
p=p->next;
}
p->next=L;//最后一个结点next指向头结点
//调整了next链的结构,此时pre链仍为原状
//调整pre链的结构
for（p=L;p->next!
=L;p=p->next）p->next->pre=p;
L->pre=p;//头结点的pre指向a2结点
}//Reform
第三章栈和队列
3.6试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。
其中，序列1和序列2中都不包含字符‘&’,且序列2是序列1的逆序。
例如，“a+b&b+a”是属于该模式的字符序列，而“1＋3&3－1”则不是。
算法：
intSeqReverse（）//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0
{
InitStack（s）;
while（（e=getchar（））!
='&'）
{
if（e==’@’）
return0;//不允许在’&’之前出现’@’
push（s,e）;
}//序列1输入完毕
while（（e=getchar（））!
='@'）
{
if（StackEmpty（s））
return0;
pop（s,c）;
if（e!
=c）
return0;
}
if（!
StackEmpty（s））
return0;//序列1元素还有剩余
return1;
}//IsReverse
3.7假设一个算术表达式中可以包含三种符号：
圆括号“（”和“）”、方括号“[”和“]”、花括号“{”和“}”，且这三种括号可按任意次序嵌套使用。
编写判别给定表达式中所含的括号是否正确配对的算法（已知表达式已存入数据元素为字符的顺序表中）。
算法：
StatusBracketTest（char*str）//判别表达式中三种括号是否匹配
{
InitStack（s）;
for（p=str;*p;p++）
{
if（*p=='（'||*p=='['||*p=='{'）
push（s,*p）;
else
if（*p=='）'||*p==']'||*p=='}'）
{
if（StackEmpty（s））
returnERROR;
pop（s,c）;
if（*p=='）'&&c!
='（'）returnERROR;
if（*p==']'&&c!
='['）returnERROR;
if（*p=='}'&&c!
='{'）returnERROR;//必须与当前栈顶括号匹配
}//if
}//for
if（!
StackEmpty（s））returnERROR;//进栈的符号还有剩余，Error
returnOK;
}//BracketTest
3.8设表达式由单字母变量、双目运算符和圆括号组成（如:
“（a*（b+c）-d）/e）”。
试写一个算法，将一个书写正确的表达式转换为逆波兰式。
思路：
1.遇到数字直接发送2.遇到’（’直接入栈3.遇到’）’则将栈元素发送直至遇到’（’4.栈空则直接入栈5.栈非空时若优先级大于栈则入栈，否则栈元素出栈
intRankOfOperator（charc）{
switch（c）{
case'#':
return-1;
case'（':
return0;
case'+':
case'-':
return1;
case'*':
case'/':
case'）':
return2;
}
}
intPrecede（charc,charch）{
returnRankOfOperator（c）>RankOfOperator（ch）;
}
voidExpressionTOPolandStyle（charsuffix[],char*exp）{
Stacks;InitStack（s,100）;inti=0;charc;
while（*exp）{
if（isdigital（*exp））
suffix[i++]=*exp;
else{
switch（*exp）{
case'（':
push（s,'（'）;
case'）':
while（（c=pops（s））!
='（'）
suffix[i++]=c;
break;
default:
if（IsEmpty（s））
push（s,*exp）;
else{
suffix[i++]=pop（s）;
exp--;
//与后面的exp++相抵消，使得栈优先级大于等于栈外的都出栈
}
}//endswitch
}//endelse
exp++;
}//endwhile
while（!
IsEmpty（s））suffix[i++]=pop（s）;suffix[i]=0;
}
3.10假设以带头结点的单循环链表表示队列，只设一个尾指针指向队尾元素，不设头指针。
试编写相应的队列初始化、入队和出队算法（在出队算法中要传回队头元素的值）
要点：
定义好数据类型，带头结点的单循环链表，只有尾指针，注意删除元素时只有一个元素的特殊性
typedefintDataType
structNode{
DataTypedata;
Node*next;
};
structCycleListQueue{
Node*tail;
};
voidInitCycleListQueue（CycleListQueue&L）{
L.tail=newNode;
L.tail->next=L.tail;
}
voidEnterQueue（CycleListQueue&L,DataTypevalue）{
Node*p=newNode;
p->data=value;
p->next=L.tail->next;
L.tail->next=p;
L.tail=p;
}
voidDeparQueue（CycleListQueue&L,DataType&d）{
if（L.tail->next!
=L.tail->next->next）{
Node*p=L.tail->next->next;
L.tail->next->next=p->next;
d=p->data;
if（p==L.tail）L.tail=p->next;
deletep;
returnd;
}
}
3.11假设将循环队列定义为：
以rear和length分别指示队尾元素和队列长度。
试给出此循环队列的队满条件，并写出相应的入队和出队算法（在出队算法中要传递回队头元素的值）。
此循环队列的队满条件：
Q.length==MAXQSIZE;
入队算法：
StatusEnCyQueue（CyQueue&Q,intx）//带length域的循环队列入队算法
{
if（Q.length==MAXSIZE）returnOVERFLOW;
Q.rear=（Q.rear+1）%MAXSIZE;
Q.base[Q.rear]=x;//rear指向队尾元素
Q.length++;
returnOK;
}//EnCyQueue
出队算法：
StatusDeCyQueue（CyQueue&Q,int&x）//带length域的循环队列出队算法，用x返回队头元素的值
{
if（Q.length==0）returnError;//空队列，错误
head=（Q.rear-Q.length+1）%MAXSIZE;//head指向队头
x=Q.base[head];
Q.length--;
returnOK；
}//DeCyQueue
3.12试写一个算法：
判别读入的一个以‘@’为结束符的字符序列是否是“回文”（所谓“回文”是指正读和反读都相同的字符序列，如“xxyzyxx”是回文，而“abcab”则不是回文）。
StatusTest（）//判别输入的字符串是否回文序列,是则返回1,否则返回0
{
InitStack（S）;
InitQueue（Q）;
while（（c=getchar（））!
='@'）
{
Push（S,c）;
EnQueue（Q,c）;//同时使用栈和队列两种结构
}
while（!
StackEmpty（S））
{
Pop（S,a）;
DeQueue（Q,b）;
if（a!
=b）returnERROR;
}
returnOK;
}//Test
第五章多维数组
5.4设有一个准对角矩阵
按以下方式存于一维数组B[4m]中：
0
1
2
3
4
5
6
k
4m-2
4m-1
a11
a12
a21
a22
a33
a34
a43
...
aij
...
a2m-1,2m
a2m,2m
写出由一对下标（i,j）求k的转换公式。
因为i行前有2（i-1）个元素。
现考虑i行情况，当j是奇数，i行有1个元素,k=2（i-1）+1-1=2（i-1）；否则i行有2个元素，k=2（i-1）+2-1=2i-1。
故：
k=
或若i为奇数，k=2（i-1）+j-i=i+j-2;当i为偶数时，k=2i-（i-j）-1=i+j-1
k=
5.5已知稀疏矩阵A4×5如下：
（1）用三元组表作为存储结构，绘出相应的三元组表示意图；
（2）用十字链表作为存储结构，绘出相应的十字链表示意图。
（1）三元组表：
i
j
v
1
2
1
1
5
5
2
1
2
2
2
3
2
4
6
4
2
4
4
5
7
（2）十字链表
第六章数和二叉树
6.5已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，...，nk个度为k的结点，问该树中有多少个叶子结点？
设叶子结点有x个，则树的结点总数为n1+n2+…nk+x;
同时除了根结点外，每个结点都指向一个结点，所有从这个角度考虑树的结点总数为：
n1+2•n2+…k•nk+1;
n1+n2+…nk+x=n1+2•n2+…k•nk+1,可得x=
6.8已知一棵树如图6-1所示，画出与该树对应的二叉树，并写出该树的先根遍历序列和后根遍历序列。
先根遍历：
ABCEIJFGKHD
后根遍历：
BIJEFKGHCDA
对应的二叉树：
6.9将如图6-2所示的森林转化为对应的二叉树。
K
图6-2
A
C
D
E
B
F
G
H
J
I
L
M
N
O
树对应的二叉树
森林对应的二叉树：
6.11已知某二叉树的中序序列为DCBGEAHFIJK，后序序列为DCEGBFHKJIA。
请画出该二叉树。
6.14假设某个电文由（a,b,c,d,e,f,g,h）8个字母组成，每个字母在电文中出现的次数分别为（7,19,2,6,32,3,21,10），试解答下列问题：
（1）画出出huffman树；
1000
2c
3f
5
11
G
28
7a
17
32e
60
6d
19b
21g
40
10h
（2）写出每个字母的huffman编码；
a:
1010b:
00c:
10000d:
1001e:
11f:
10001g:
01h:
1011
（3）在对该电文进行最优二进制编码处理后，电文的二进制位数。
4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=261
6.17写出按层次遍历二叉树的算法。
思路：
用队列存储结构，并用递归方法
StatusLevelOrderTraverse（BitTreeT,Status（*Visit）（TElemTypee）//层序遍历二叉树
{
InitQueue（Q）;//初始化队列
if（!
T）returnError;//空树，直接返回
EnQueue（Q,T）;//根结点入队
BiTNode*p;
while（!
QueueEmpty（Q））
{
DeQueue（Q,p）;
Visit（p->data）;
if（p->lchild）EnQueue（Q,p->lchild）;
if（p->rchild）EnQueue（Q,p->rchild）;
}//while
returnOk;
}//LevelOrderTraverse
6.19写出判断两棵给定二叉树是否相似的算法。
（注：
两棵二叉树B1和B2相似是指：
B1和B2皆空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似。
）
思路：
采用递归进行比较判断
boolBiTreeSimilar（BiTreeT1,BiTreeT2）
{
if（T1==Null&&T2==Null）
return1;
elseif（T1==Null||T2==Null）
return0;
else
return（BiTreeSilimar（T1->lchild,T2->lchild）&&BiTreeSimilar（T1->rchild,T2->rchild））;
}
6.21写出统计树中叶子结点个数的算法，树用孩子兄弟链表表示。
思路：
在孩子兄弟链表中，若结点的firstchild为Null，则为叶子结点；采用递归方法。
intCountLeaves（TreeT，int&num）//num传递的初值为0
{
if（T->nextsibling!
=Null）
num+=CountLeaves（T->nextsibling）;
if（T->firstchild!
=Null）
num+=CountLeaves（T->firstchild）;
else
num+=1;//firstchild域为空，则为叶子结点
returnnum;
}
图7-1
V5
V4
V2
V3
V1
V6
第七章图
7.1已知有向图如图7-1所示，
请给出该图的
（1）邻接矩阵示意图
（2）邻接表示意图
（3）逆邻接表
（4）所有强连通分量
升级会员 