王道课后习题
顺序表
- 从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
代码实现
bool Del_Min(SqList &L, ElemTYpe &value){
if(L.length == 0)
return false
value = L.data[0];
int pos = 0;
for(int i = 0; i<L.length; i++){
if(value>L.data[i]){
value = L.data[i];
pos = i;
}
}
L.data[pos] = L.data[L.length-1]
return true
}- 设计一个高效算法，将顺序表 L 的所有元素逆置，要求算法的空间复杂度为 O(1)。
代码实现
void Reverse(SeqList &L){
ElemType temp;
for(int i=0; i<L.length/2; i++){
temp = L.data[i];
L.data[i] = L.data[L.length-i-1];
L.data[L.length-i-1]=temp;
}
}3. 对长度为 n 的顺序表 L，编写一个时间复杂度为 O(n)、空间复杂度为 O(1) 的算法，该算法删除线性表中所有值为 x 的数据元素。
// 解法 1
void del_x_1(SqList &L, ElemType x){
int k = 0;
for(int i=0; i< L.length; i++){
if(L.data[i] != x){
L.data[k] = L.data[i];
k++
}
L.length = k;
}
}
// 解法 2
void del_x_1(SqList &L, ElemType x){
int k=0, i=0;
while(i<L.length){
if(L.data[i]==x){
k++;
}
else{
L.data[i-k] = L.data[i];
i++;
}
}
L.length = L.length-k;
}4. 从有序顺序表（无特别说明，通常是指 “递增有序”）中删除其值在给定值 s 与 t 之间（要求 s < t）的所有元素，若 s 或 t 不合理或顺序表为空，则显示出错信息并退出运行。
bool Del_s_t(SqList &L, ElemType s, ElemType t){
int i, j;
if(s>=t || L.length==0)
return false;
for(i=0; i<L.length&&L.data[i]<s;i++);
if(i>=L.length)
return false;
for(j=i; i<L.length&&L.data[j]<=t;j++);
for(; j<L.length; i++,j++){
L.data[i]=L.data[j];
}
L.length=i;
return true
}5. 从顺序表中删除其值在给定值 s 与 t 之间（包含 s 和 t，要求 s<t）的所有元素，若 s 或 t 不合理或顺序表为空，则显示出错信息并退出运行。
bool Del_s_t(SqList &L, ElemType s, ElemType t){
int i,k=0;
if(L.length==0 || s>=t)
return false;
for(i=0; i<L.length; i++){
if(L.data[i]>=s && L.data[i]<=t)
k++;
else
L.data[i-k] = L.data[i];
}
L.length-=k;
return true;
}6. 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
bool Delete_Same(SqList &L){
if(L.length == 0)
return false;
int i, j;
for(i=0,j=1; j<L.length; j++)
if(L.data[i] !=L.data[j])
L.data[++i]=L.data[j];
L.length = i+1;
return true;
}7. 将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
bool Merge(SeqList A, SeqList B, SeqList &C){
if(A.Length+B.length>C.maxSize)
return false;
int i=0, j=0, k=0;
while(i<A.length && j<B.length){
if(A.data[i]<=B.data[j])
C.data[k++]=A.data[i++];
else
C.data[k++]=B.data[j++];
}
while(i<A.length){
C.data[k++]=A.data[i++];
}
while(j<B.length){
C.data[k++]=B.data[j++];
}
C.length=k;
return true;
}8. 已知在一维数组
tyedef int DataType;
void Reverse(DataType A[], int left, int right, int arraySize){
if(left>=right || right>arraysize)
return false;
int mid = (left+right)/2;
for(int i=0; i<=mid-left; i++){
DataType temp = A[left+i];
A[left+i] = A[right-i];
A[right-i] = temp;
}
}
void Exchange(DataType A[], int m, int n, int arraySize){
Reverse(A,0,m+n-1,arraySize);
Reverse(A,0,n-1,arraySize);
Reverse(A,n,m+n-1,arraySize);
}9. 线性表
void SearchExchangeInsert(ElemType A[], ElemType x){
int low=0, high=n-1, mid;
while(low<=high){
mid = (low+high)/2;
if(A[mid]==x) break;
else if(A[mid]<x) low=mid+1;
else high=mid-1;
}
if(A[mid]==x && mmid!=n-1){
t = A[mid];
A[mid] = A[mid+1];
A[mid+1] = t;
}
if(low>high){
for(i=n-1; i>high; i--)
A[i+1] = A[i];
A[i+1] = x;
}
}链表
1. 设计一个递归算法，删除不带头结点的单链表 L 中 所有值为 x 的结点。
void Del_X_3(LinkList &L,ElemType x){
LNode *p; // p指向待删除结点
if(L==NULL) // 递归出口
return;
if(L->data==x){ // 若L所指结点的值为x
p=L; // 删除*L，并让L指向下一结点
L=L->next;
free(p);
Del_X_3(L,x); // 递归调用
}
else{ // 若L所指结点的值不为x
Del_X_3(L->next,x); // 递归调用
}
}2. 在带头结点的单链表 L 中，删除所有值为 x 的结点，并释放其空间，假设值为 x 的结点不唯一，试编写算法实现上述操作。
【解答】
解法 1：用 p 从头至尾扫描单链表，pre 指向 *p 结点的前驱。若 p 所指结点的值为 x，则删除，并让 p 移向下一个结点，否则 pre、p 指针同步后移一个结点。
void Del_X_1(LinkList &L, ElemType x){
LNode *p=L->next, *pre=L,*q; // 置p和pre的初始值
while(p!=NULL){
if(p->data==x){
q=p; // q指向被删结点
p=p->next;
pre->next=p; // 将*q结点从链表中断开
free(q); // 释放*q结点的空间
}
else{ // 否则，pre和p同步后移
pre=p;
p=p->next;
}
}
}解法 2：采用尾插法建立单链表。用 p 指针扫描 L 的所有结点，当其值不为 x 时，将其链接到 L 之后，否则将其释放。
void Del_X_2(LinkList &L, ElemType x){
LNode *p=L->next,*r=L,*q; // r指向尾结点，其初值为头结点
while(p!=NULL){
if(p->data!=x){ // *p结点值不为x时将其链接到L尾部
r->next=p;
r=p;
p=p->next; // 继续扫描
}
else{ // *p结点值为x时将其释放
q=p;
p=p->next; // 继续扫描
free(q); // 释放空间
}
}
r->next=NULL; // 插入结束后置尾结点指针为NULL
}上述两个算法扫描一遍链表，时间复杂度为
3. 设 L 为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。
void R_Print(LinkList L){
if(L->next!=NULL){
R_Print(L->next); // 递归
}
if(L!=NULL) print(L->data); // 输出函数
}
void R_Ignore_Head(LinkList L){
if(L->next!=NULL) R_Print(L->next);
}4. 试编写在带头结点的单链表 L 中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。
【解答】算法思想：用 p 从头至尾扫描单链表，pre 指向 *p 结点的前驱，用 minp 保存值最小的结点指针（初值为 p），minpre 指向 *minp 结点的前驱（初值为 pre）。一遍扫描，一遍比较，若 p->data 小于 minp->data，则将 p、pre 分别赋值给 minp、minpre。当 p 扫描完毕时，minp 指向最小值结点。minpre 指向最小值结点的前驱结点，再将 minp 所指结点删除即可。
LinkList Delete_Min(LinkList &L){
LNode *pre=L,*p=pre->next; // p为工作指针，pre指向其前驱
LNode *minpre=pre,*minp=p; // 保存最小值结点及其前驱
while(p!=NULL){
if(p->data<minp->data){
minp=p; // 找到比之前找到的最小值结点更小的结点
minpre=pre;
}
pre=p; // 继续扫描下一个结点
p=p->next;
}
minpre->next=minp->next; // 删除最小值结点
free(minp);
return L;
}算法需要从头至尾扫描链表，时间复杂度为
5. 试编写算法将带头结点的单链表就地逆置，所谓 “就地” 是指辅助空间复杂度为
【解答】
解法 1：将头结点摘下，然后从第一结点开始，依次插入到头结点的后面（头插法建立单链表），直到最后一个结点为止，这样就实现了链表的逆置。
LinkList Reverse_1(LinkList &L){
LNode *p, *r; // p为工作指针，r为p的后继，以防断链
p=L->next; // 从第一个元素结点开始
L->next=NULL; // 先将头结点的L的next域置为NULL
while(p!=NULL){ // 依次将元素结点摘下
r=p->next; // 暂存p的后继
p->next=L->next; // 将p结点插入到头结点之后
L->next=p;
p=r;
}
return L;
}解法 2：指针反转
LinkList Reverse_2(LinkList &L){
LNode *pre,*p=L->next,*r=p->next;
p->next=NULL; // 处理第一个结点
while(r!=NULL){ // r为空，则说明p为最后一个结点
pre=p; // 依次继续遍历
p=r;
r=r->next;
p->next=pre; // 指针反转
}
L->next=p; // 处理最后一个结点
return L;
}上述两个算法的时间复杂度为
6. 有一个带头结点的单链表 L，设计一个算法使其元素递增有序。
【解答】算法思想：采用直接插入排序算法的思想，先构成只含一个数据结点的有序单链表，然后依次扫描单链表中剩下的结点 *p（直至 p==NULL 为止），在有序表中通过比较查找插入 *p 的前驱结点 *pre，然后将 *p 插入到 *pre 之后。
void Sort(LinkList &L){
LNode *p=L->next,*pre;
LNode *r=p->next; // r保持*p后继结点指针，以保证不断链
p->next=NULL; // 构造只含一个数据结点的有序表
p=r;
while(p!=NULL){
r=p->next; // 保存*p的后继结点指针
pre=L;
while(pre->next!=NULL&&pre->next->data<p->data)
pre=pre->next; // 在有序表中查找插入*p的前驱结点*pre
p->next=pre->next; // 将*p插入到*pre之后
pre->next=p;
p=r; // 扫描原单链表中剩下的结点
}
}细心的读者会发现该算法的时间复杂度为
7. 设在一个带头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值（作为函数参数给出）之间的元素的元素（若存在）。
【解答】因为链表是无序的，所以只能逐个结点进行检查，执行删除。
void RangeDelete(LinkList &L, int min, int max){
LNode *pr=L;*p=L->link; // p是检测指针，pr是其前驱
while(p!=NULL)
if(p->data>min && p->data<max){ // 寻找到被删结点，删除
pr->link=p->link;
free(p);
p=pr->link;
}
else{ // 否则继续寻找被删结点
pr=p;
p=p->link;
}
}8. 给定两个单链表，编写算法找出两个链表的公共结点。
【解答】两个单链表有公共结点，即两个链表从某一结点开始，它们的 next 都指向同一个结点。由于每个单链表结点只有一个 next 域，因此从第一个公共结点开始，之后它们所有的结点都是重合的，不可能再出现分叉。所以两个有公共结点而部分重合的单链表，拓扑形状看起来像 Y，而不可能像 X。
本题极容易联想到 “蛮” 方法：在第一个链表上顺序遍历每个结点，每遍历一个结点，在第二个链表上顺序遍历所有结点，若找到两个相同的结点，则找到了它们的公共结点。显然，该算法的时间复杂度为
接下来我们试着寻找一个线性时间复杂度的算法。先把问题简化：如何判断两个单向链表有没有公共结点？应注意到这样一个事实：若两个链表有一个公共结点，则该公共结点之后的所有结点都是重合的，即它们的最后一个结点必然是重合的。因此，我们判断两个链表是不是有重合的部分时，只需要分别遍历两个链表到最后一个结点。若两个尾结点是一样的，则说明它们有公共结点，否则两个链表没有公共结点。
然而，在上面的思路中，顺序遍历两个链表到尾结点时，并不能保证在两个链表上同时到达尾结点。这时因为两个链表长度不一定一样。但假设一个链表比另一个链表长 k 个结点，我们先在长的链表上遍历 k 个结点，之后再同步遍历，此时我们就能保证同时到达最后一个结点。由于两个链表从第一个公共结点开始到链表的尾结点，这一部分是重合的，因此它们肯定也是同时到达第一公共结点的。于是在遍历中，第一个相同的结点就是第一个公共的结点。
根据这一思路中，我们先要分别遍历两个链表得到它们的长度，并求出两个长度之差。在长的链表上先遍历长度之差个结点之后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。此时，该方法的时间复杂度为
LinkList Search_lst_Common(LinkList L1; LinkList L2){
int dist;
int len1=Length(L1),len2=Length(L2); // 计算两个链表的表长
LinkList longList,shortList; // 分别指向表长较长和较短的链表
if(len1>len2){ // L1表长较长
longList=L1->next;
shortList=L2->next;
dist=len1-len2; // 表长之差
}
else{ // L2表长较长
longList=L2->next;
shortList=L1->next;
dist=len2-len1; // 表长之差
}
while(dist--){ // 表长的链表先遍历到第dist个结点，然后同步
longList=longList->next;
}
while(longList!=NULL){ // 同步寻找共同结点
if(LongList==shortList) // 找到第一个公共结点
return longList;
else{ // 继续同步寻找
longList=longList->next;
shortList=shortList->next;
}
}
return NULL;
}9. 给定一个带表头结点的单链表，设 head 为头指针，结点结构为 (data,next)，data 为整型元素，next 为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间）。
【解答】算法思想：对链表进行遍历，在每次遍历中找出整个链表的最小值元素，输出并释放结点所占空间；再查找次笑值元素，输出并释放空间，如此下去，直至链表为空，最后释放头结点所占存储空间。该算法的时间复杂度为
void Min_Delete(LinkList &head){
while(head->next!=NULL){ // 循环到仅剩头结点
LNode *pre=head; // pre为元素最小值结点的前驱结点的指针
Lnode *p=pre->next; // p为工作指针
LNode *u; // 指向被删除结点
while(p->next!=NULL){
if(p->next->data<pre->next->data)
pre=p; // 记住当前最小值结点的前驱
p=p->next;
}
print(pre->next->data); // 输出元素最小值结点的数据
u=pre->next; // 删除元素值最小的结点，释放结点空间
pre->next=u->next;
free(u);
}
free(head); // 释放头结点
}10. 将一个带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B，使得 A 表中含有原表中序号为奇数的元素，而 B 表中含有原表中序号为偶数的元素，且保持其相对顺序不变。
【解答】算法思想：设置一个访问序号变量（初值为 0），每访问一个结点序号自动加 1，然后根据序号的奇偶性将结点插入到 A 表或 B 表中。重复以上操作直到表尾。
LinkList DisCreat_1(LinkLIst &A){
int i=0; // i记录表A中结点的序号
LinkList B=(LinkList)malloc(sizeof(LNode)); // 创建B表表头
B->next=NULL; // B表的初始化
LNode *ra=A,*rb=B,*p; // ra和rb将分别指向将创建的A表和B表的尾结点
p=A->next; // p为链表工作指针，指向待分解的结点
A->next=NULL; // 置空新的A表
while(p!=NULL){
i++; // 序号加1
if(i%2==0){ // 处理序号为偶数的链表结点
rb->next=p; // 在B表尾插入新结点
rb=p; // rb指向新的尾结点
}
else{ // 处理原序号为奇数的结点
ra->next=p; // 在A表尾插入新结点
ra=p;
}
p=p->next; // 将p恢复为指向新的待处理结点
}// while
ra->next=NULL;
rb->next=NULL;
return B;
}为了保持原来结点中的顺序，本题采用尾插法建立单链表。此外，本算法完全可以不用设置序号变量。while 循环中的代码改为将结点插入到表 A 中并将下一结点插入到表 B 中，这样 while 中第一处理的结点就是奇数号结点，第二处理的结点就是偶数号结点。
11. 设 $C={a_1,b_1,a_2,b_2,\cdots,a_n,b_n} $为线性表，采用带头结点的单链表存放，设计一个就地算法，将其拆分为两个线性表，使得
【解答】算法思想：采用上题的思路，不设序号变量。二叉的差别仅在于对 B 表的建立不采用尾插法，而是采用头插法。
LinkList DisCreat_2(LinkList &A){
LinkList B=(LinkList)malloc(sizeof(LNode)); // 创建B表表头
B->next=NULL; // B表的初始化
LNode *p=A->next,*q; // p为工作指针
LNode *ra=A; // ra始终指向A的尾结点
while(p!=NULL){
ra->next=p;ra=p; // 将*p链到A的表尾
p=p->next;
if(p!=NULL){
q=p->next; // 头插后，*p将断链，因此用q记忆*p的后继
p->next=B->next; // 将*p插入到B的前端
B->next=p;
p=q;
}
}
ra->next=NULL; // A尾结点的next域置空
return B;
}12. 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素，例如 (7,10,10,21,30,42,42,42,51,70) 将变为 (7,10,21,30,42,51,70)。
【解答】算法思想：由于是有序表，所有相同值域的结点都是相邻的。用 p 扫描单链表 L，若 *p 结点的值域等于其后继结点的值域，则删除后者，否则 p 移向下一个结点。
void Del_Same(LinkList &L){
LNode *p=L->next,*q; // p为扫描工作指针
if(p==NULL)
return;
while(p->next!=NULL){
q=p->next; // q指向*p的后继结点
if(p->data==q->data){ // 找到重复值的结点
p->next=q->next; // 释放*q结点
free(q); // 释放相同元素值的结点
}
else
p=p->next;
}
}本算法的时间复杂度为
本题也可采用尾插法，将头结点摘下，然后从第一个结点开始，依次与已经插入结点的链表的最后一个结点比较，若不等则直接插入，否则将当前遍历的结点删除并处理下一个结点，直到最后一个结点为止。
13. 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【解答】算法思想：两个链表已经按元素递增次序排序，将其合并时，均从第一个结点起进行比较，将小的结点链入链表中，同时后移工作指针。该问题要求结果链表按元素值递减次序排列，故新链表的建立应该采用头插法。比较结束后，可能会有一个链表非空，此时头插法将剩下的结点依次插入新链表中即可。
void MergeList(LinkList &La, LinkList &Lb){
LNode *r,*pa=La->next,*pb=Lb->next; // 分别是表La和表Lb的工作指针
La->next=NULL; // La作为结果链表的头指针，先将结果链表初始化为空
while(pa && pb){ // 当两链表均不为空时，循环
if(pa->data<=pb->data){
r=pa->next; // r暂存pa的后继结点指针
pa->next=La->next;
La->next=pa; // 将pa结点链于结果表中 ，同时逆置（头插法）
pa=r; // 恢复pa为当前待比较结点
}
else{
r=pb->next; // r暂存pb的后继结点指针
pb->next=La->next;
La->next=pb; // 将pb结点链于结果表中 ，同时逆置（头插法）
pb=r; // 恢复pb为当前待比较结点
}
}
if(pa)
pb=pa; // 通常情况下会剩下一个链表非空，处理剩下的部分
while(pb){ // 处理剩下的一个非空链表
r=pb->next; // 依次插入到La中（头插法）
pb->next=La->next;
La->next=pb;
pb=r;
}
free(Lb);
}14. 设 A 和 B 是两个单链表（带头结点），其中元素递增有序。设计一个算法从 A 和 B 中的公共元素产生单链表 C，要求不破坏 A、B 的结点。
【解答】算法思想：表 A、B 有序，可以从第一个元素其依次比较 A、B 两表的元素，若元素值不等，则值小的指针往后移，若元素相等，则创建一个值等于两结点的元素值的新结点，使用尾插法插入到新的链表中，并将两个原表指针后移一位，直到其中一个链表遍历到表尾。
void Get_Common(LinkList A, LinkList B){
LNode *p=A->next, *q=B->next,*r, *s;
LinkList C=(LinkList)malloc(sizeof(LNode)); // 建立表C
r=C; // r始终指向C的尾结点
while(p!=NULL && q!=NULL){ // 循环跳出条件
if(p->data<q->data)
p=p->next; // 若A的当前元素较小，后移指针
else if(p->data>q->data)
q=q->next; // 若B的当前元素较小，后移指针
else{ // 找到公共元素结点
s=(LNode *)malloc(sizeof(LNode));
s->Data=p->data; // 复制产生结点*s
r->next=s; // 将*s链接到C上（尾插法）
r=s;
p=p->next; // 表A和B继续向后扫描
q=q->next;
}
}
r->next=NULL; // 置C尾结点指针为空
}15. 已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。编制函数，求 A 与 B 的交集，并存放于 A 链表中。
【解答】算法思想：采用归并的思想，设置两个工作指针 pa 和 pb，对两个链表进行归并扫描，只有同时出现在两集合中的元素才链接到结果表中且仅保留一个，其他结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点。
LinkList Union(LinkList &La, LinkList &Lb){
LNode *pa=La->next; // 设工作指针分别为pa和pb
LNode *pb=Lb->next;
LNode *u,*pc=La; // 结果表中当前合并结点的前驱指针pc
while(pa && pb){
if(pa->data==pb->data){ // 交集并入结果表中
pc->next=pa; // A中结点链接到结果表
pc=pa;
pa=pa->next;
u=pb; // B中结点释放
pb=pb->next;
free(u);
}
else if(pa->data<pb->data){ // 若A中当前结点值小于B中当前结点值
u=pa;
pa=pa->next; // 后移指针
free(u); // 释放A中当前结点
}
else{ // 若B中当前结点值小于A中当前结点值
u=pb;
pb=pb->next; // 后移指针
free(u); // 释放B中当前结点
}
}
while(pa){ // B已遍历完，A未完
u=pa;
pa=pa->next;
free(u); // 释放A中剩余结点
}
while(pb){ // A已遍历完，B未完
u=pb;
pb=pb->next;
free(u); // 释放B中剩余结点
}
pc->next=NULL; // 置结果链表尾指针为NULL
free(lb); // 释放B表的头结点
return La;该算法的时间复杂度为
16. 两个整数序列
【解答】算法思想：因为两个整数序列已存入两个链表中，操作从两个链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则 A 链表从上次开始比较结点的后继开始，B 链表仍从第一个结点开始比较，直到 B 链表到表尾表示匹配成功。A 链表到尾而 B 链表未到尾表示失败。操作中应记住 A 链表每次的开始结点，以便下次匹配时好从其后继开始。
int Pattern(LinkList A, LinkList B){
LNode *p=A; // p为A链表的工作指针，本题假定A和B均无头结点
LNode *pre=p; // pre记住每趟比较中A链表的开始结点
LNode *q=B; // q是B链表的工作指针
while(p && q)
if(p->data==q->data){ // 结点值相同
p=p->next;
q=q->next;
}
else{
pre=pre->next;
p=pre; // A链表新的开始比较结点
q=B; // q从B链表第一个结点开始
}
if(q=NULL) // B已经比较结束
return 1; // 说明B是A的子序列
else
return 0; // B不是A的子序列
}17. 设计一个算法用于判断带头结点的循环双链表是否对称。
【解答】算法思想：让 p 从左向右扫描，q 从右向左扫描，直到它们指向同一结点（p==q，当循环双链表中结点个数为奇数时）或相邻（p->next==q 或 q->prior==p，当循环双链表中结点个数为偶数时）为止，若它们所指结点值相同，则继续进行下去，否则返回 0。若比较全部相等则返回 1。
int Symmetry(DLinkList L){
DNode *p=L->next,*q=L->prior; // 两头工作指针
while(p!=q && q->next!=p) // 循环跳出条件
if(p->data==q->data){ // 所指结点值相同则继续比较
p=p->next;
q=q->prior;
}
else
return 0; // 否则，返回0
return 1; // 比较结束后返回1
}18. 有两个循环单链表，链表头指针分别为 h1 和 h2，编写一个函数将链表 h2 链接到链表 h1 之后，要求链接后的链表仍保持循环链表形式。
【解答】算法思想：先找到两个链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，再使之成为循环的。
LinkList Link(LinkList &h1, LinkList &h2){
// 将循环链表h2链接到循环链表h1之后，使之仍保持为循环链表的形式
LNode *p,*q; // 分别指向两个链表的尾结点
p=h1;
while(p->next!=h1) // 寻找h1的尾结点
p=p->next;
q=h2;
while(p->next!=h2) // 寻找h2的尾结点
q=q->next;
p->next=h2; // 将h2链接到h1之后
q->next=h1; // 令h2的尾结点指向h1
return h1;
}19. 设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点。
【解答】对于循环单链表 L，在不空时循环：每循环一次查找一个最小结点（由 minp 指向最小值结点，minpre 指向其前驱结点）并删除它。最后释放头结点。
void Del_All(LinkList &L){
LNode *p,*pre,*minp,*minpre;
while(L->next!=L){ // 表不空，循环
p=L->next; pre=L; // p为工作指针，pre指向其前驱
minp=p;minpre=pre; // minp指向最小值结点
while(p!=L){ //循环一趟，找到最小值结点
if(p->data<minp->data){
minp=p; // 找到值更小的结点
minpre=pre;
}
pre=p; // 查找下一个结点
p=p->next;
}
printf("%d",minp->data); // 输出最小值结点元素
minpre->next=minp->next; // 最小值结点从表中“断”开
free(minp); // 释放空间
}
free(L); // 释放头结点
}20. 设头指针为 L 的带有表头结点的非循环双向链表其每个结点中除有 pre（前驱指针）、data（数据）和 next（后继指针）域外，还有一个访问频度域 freq。在链表被启用前，其值均初始化为零。每当在链表中进行一次 Locate(L,x) 运算时，令元素值为 x 的结点中 freq 域的值增 1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点前面，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate(L,x) 运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
【解答】算法思想：首先在双向链表中查找数据值为 x 的结点，查到后，将结点从链表上摘下，然后顺着结点的前驱链查找该结点的插入位置（频度递减，且排在同频度的第一个，即向前找到第一个比它的频度大的结点，插入位置为该结点之后），并插入到该位置。
DLinkList Locate(DLinkList &L, ElemType x){
DNode 8p=L->next,*q; // p为工作指针，q为p的前驱，用于查找插入位置
while(p && p->data!=x)
p=p->next; // 查找值为x的结点
if(!p)
exit(0); // 不存在值为x的结点
else{
p->freq++; // 令元素值为x的结点的freq域加1
if(p->pre==L||pre->freq>p->freq)
return p; // p是链表首结点，或freq值小于前驱
if(p->next!=NULL)
p->next->pre=p->pre;
p->pre->next=p->next; // 将p结点从链表上摘下
q=p->pre; // 以下查找p结点的插入位置
while(q!=L && q->freq<=p->freq)
q=q->pre;
p->next=q->next;
if(q->next!=NULL)
q->next->pre=p; // 将p结点排在同频率的第一个
p->pre=q;
q->next=p;
}
return p; // 返回值为x的结点的指针
}21. 单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点（通常单链表的最后一个结点的指针域是空的）。试编写算法判断单链表是否存在环。
1）给出算法的基本设计思想：
2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
【解答】
1）算法的基本设计思想
设置快慢两个指针分别为 fast 和 slow，初始时都指向链表头 head。slow 每次走一步，即 slow=slow->next；fast 每次走两步，即 fast=fast->next->next。由于 fast 比 slow 走得快，如果有环，那么 fast 一定会先进入环，而 slow 后进入环。当两个指针都进入环后，经过若干操作后两个指针定能在环上相遇。这样就可以判断一个链表是否有环。
如下图所示，当 slow 刚进入环时，fast 早已进入环，因为 fast 每次比 slow 多走一步且 fast 与 slow 的距离小于环的长度，所以 fast 与 slow 相遇时，slow 所走的距离不超过环的长度。
如下图所示，设头结点到环的入口欧点的距离为 a，环的入口沿着环的方向到相遇点的距离为 x，环长为 r，相遇时， fast 绕过了 n 圈。
则有 2(a+x)=a+n*r+x，即 a=n*r-x。显然从头结点到环的入口点的距离等于 n 倍的环长减去环的入口点到相遇点的距离。因此可设置两个指针，一个指向 head，一个指向相遇点，两个指针同步移动（均为一次走一步），相遇点即为环的入口点。
2）本题代码如下：
LNode* FindLoopStart(LNode *head){
LNode *fast=head,*slow=head; // 设置快慢两个指针
while(fast!=NULL && fast->next!=NULL){
slow=slow->next; // 每次走一步
fast=fat->next->next; // 每次走两步
if(show==fast) break; // 相遇
}
if(fast==NULL || fast->next==NULL)
return NULL; // 没有环，返回 NULL
LNode *p1=head,*p2=slow; // 分别指向开始点、相遇点
while(p1!=p2){
p1=p1->next;
p2=p2->next;
}
return p1; // 返回入口点
}3）当 fast 与 slow 相遇时，slow 肯定没有遍历完链表，故算法的时间复杂度为
栈
1. 假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列，可以操作的序列称为合法序列，否则称为非法序列。写出一个算法，判定所给的操作序列是否合法。若合法，返回 true，否则返回 false（假定被判定的操作序列已存入一维数组中）。
【解答】算法的基本设计思想：依次逐一扫描入栈出栈序列，，每扫描至任意一个位置均需检查出栈次数是否小于入栈次数，若大于则为非法序列。扫描结束后，再判断入栈和出栈次数是否相等，若不相等则不合题意，为非法序列。
bool Judge(char A[]){
int i=;
int j=k=0; // i为下标，j和k分别为字母I和O的个数
while(A[i]!='\0'){ // 未到字符数组尾
switch(A[i]){
case 'I':j++;break; // 入栈次数增1
case 'O':k++;
if(k>j){printf("序列非法\n");exit(0)}
}
i++; //不论A[i]是"I"或"O"，指针i均后移
}
if(j!=k){
printf("序列非法\n");
return false;
}else{
printf("序列合法\n");
return true;
}
}2. 设单链表的表头指针为 L，结点结构由 data 和 next 两个域构成，其中 data 域为字符型。试设计算法判断该链表的全部 n 个字符是否中心对称。例如 xyx，xyyx 都是中心对称。
【解答】算法思想：使用栈来判断链表中的数据是否中心对称。让链表的前一半元素一次进栈。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两个元素比较，若相等，则将链表的下一个元素与栈中再弹出的元素比较，直至链表到尾。这时若栈是空栈，则 得出链表中心对称的结论；否则，当链表中的一个元素中弹出元素不等时，结论为链表非中心对称，结束算法的执行。
int dc(LinkList L, int n){
int i;
char s[n/2]; // s字符栈
LNode *p=L->next; // 工作指针p，指向待处理的当前元素
for(i=0; i<n/2; i++){ // 链表前一半元素进栈
s[i]=p->data;
p=p->next;
}
i--; // 恢复最后的i值
if(n%2==1) //若n是奇数，后移过中心结点
p=p->next;
while(p!=NULL && s[i]==p->data){ // 检测是否中心对称
i--; // i充当栈顶指针
p=p->next;
}
if(i==-1) // 栈为空栈
return 1; // 链表中心对称
else
return 0; // 链表中心不对称
}3. 设有两个栈 s1、s2 都采用顺序栈方式，并共享一个存储区 [0,...,maxsize-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式。试设计 s1、s2 有关入栈和出栈的操作算法。
【解答】两个栈共享向量空间，将两个栈的栈底设在向量两端，初始时，s1 栈顶指针为 -1，s2 栈顶指针为 maxsize。两个栈顶指针相邻时为栈满。两个栈顶相向、迎面增长，栈顶指针执行指定元素。
# define maxsize 100 // 两个栈共享顺序存储空间所能达到的最多元素数，初始化为100
# define elemtp int // 假设元素类型为整型
typedef struct{
elemtp stack stack[maxsize]; // 栈空间
int top[2]; // top 为两个栈顶指针
}stk;
stk s; // s是如上定义的结构类型变量，为全局变量本题的关键在于，两个栈入栈和退栈时得栈顶指针的计算。s1 栈是通常意义下的栈；而 s2 栈入栈操作时，其栈顶指针左移（减 1），退栈时，栈顶指针右移（加 1）。
此外，对于所有栈的操作，都要注意 “入栈判满，出栈判空” 的检查。
（1）入栈操作
int push(int i, elemtp x){
// 入栈操作。i为栈号，i=0表示左边的s1栈，i=1表示右边的s2栈，x是入栈元素
// 入栈成功返回1，否则返回0
if(i<0 || i>1){
printf("栈号输入不对");
exit(0);
}
if(s.top[1]-s.top[0]==1){
printf("栈已满\n");
return 0;
}
switch(i){
case 0:s.stack[++s.top[0]]=x; return 1; break;
case 1:s.stack[--s.top[1]]=x; return 1;
}
}（2）退栈操作
elemtp pop(int i){
// 退栈算法。i代表栈号，i=0时为s1栈，i=1时为s2栈
// 退栈成功返回退栈元素，否则返回-1
if(i<0 || i>1){
printf("栈号输入错误\n");
exit(0);
}
switch(i){
case 0:
if(s.top[0]==-1){
printf("栈空\n");
return -1;
}
else
return s.stack[s.top[0]--];
break;
case 1:
if(s.top[1]==maxsize){
printf("栈空\n");
return -1;
}
else
return s.stack[s.top[1]++];
break;
}
}队列
1. 若希望循环队列中的元素都能得到利用，则需设置一个标志域 tag，并以 tag 的值为 0 或 1 来区分队头指针 front 和队尾指针 rear 相同时的队列状态是 “空” 还是 “满”。试编写与此结构相应的入队和出队算法。
【解答】在循环队列的类型结构中，增设一个 tag 的整型变量，进队时置 tag 为 1，出队时置 tag 为 0（因为只有入队操作可能导致队满，也只有出队操作可能导致队空）。队列 Q 初始时，置 tag=0、front=rear=0.这样队列的 4 要素如下：
队空条件：Q.front==Q.rear 且 Q.tag=0。
队满条件：Q.front==Q.rear 且 Q.tag=1。
进队操作：Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;Q.tag=1。
出队操作：x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;Q.tag=0。
1）设 ”tag“ 法的循环队列入队算法
int EnQueuel(SqQueue &Q, ElemType x){
if(Q.front==Q.rear && Q.tag==1) // 两个条件都满足时则队满
return 0;
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%MaxSize;
Q.tag=1; // 可能队满
return 1;
}2）设 “tag” 法的循环队列出队算法
int DeQUeuel(SqQueue &Q, ElemType &x){
if(Q.front==Q.rear && Q.tag==1) // 两个条件都满足时则队满
return 0;
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize;
Q.tag=0; // 可能队空
return 1;
}栈、队列的应用
假设一个算术表达式中包含圆括号、方括号和花括号 3 种类型的括号，编写一个算法来判别表达式中的括号是否配对，以字符 "\0" 作为算术表达式的结束符。
【解答】算法的基本思想是扫描每个字符，遇到花、中、圆的左括号时进栈，遇到花、中、圆的右括号时检查栈顶元素是否为相应的左括号，若是，退栈，否则配对错误。最后栈若不为空也为错误。
bool BracketsCheck(char *str){
InitStack(S); // 初始化栈
int i=0;
while(str[i]!='\0'){
switch(str[i]){
// 左括号入栈
case '(':Push(S,'(');break;
case '[':Push(S,'[');break;
case '{':Push(S,'{');break;
// 遇到右括号，检测栈顶
case ')':
Pop(S,e);
if(e!='(') return false;
break;
case ']':
Pop(S,e);
if(e!='[') return false;
break;
case '}':
Pop(S,e);
if(e!='{') return false;
break;
default;
break;
}
i++;
}
if(!IsEmpty(S)){
printf("括号不匹配\n");
return false;
}
else{
printf("括号匹配\n");
return true;
}
}2. 按下图所示铁道进行车厢调度（注意，两侧铁道均为单向行驶道，火车调度站有一个用于调度的 “栈道”），火车调度站的入口处有 n 节硬座和软座车厢（分别用 H 和 S 表示）等待调度，试编写算法，输出对这 n 节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软座车厢都被调整到硬座车厢之前。
【解答】两侧的铁道均为单向行驶道，且两侧不相通。所有车辆都必须通过 “栈道” 进行调度。算法的基本设计思想：所有车厢依次前进并逐一检查，若为硬座车厢则入栈，等待最后调度。检查完后，所有的硬座车厢已全部入栈道，车道中的车厢均为软座车厢，此时将栈道的车厢调度出来，调整到软座车厢之后。算法的实现如下：
void Train_Arrange(char *train){
// 用字符串train表示火车，H表示硬座，S表示软座
char *p=train,*1=train,c;
stack s;
InitStack(S); // 初始化栈结构
while(*p){
if(*p=='H')
Push(s,*p); // 把H存入栈中
else
*(q++)=*p;
p++;
}
while(!StackEmpty(s)){
Pop(s,c);
*(q++)=c; // 把H接在后部
}
}3. 利用一个栈实现以下递归函数的非递归计算：
【解答】算法思想：设置一个栈用于保存 n 和对应的
double p(int n, double x){
struct stack(
int no; // 保存n
double val; // 保存Pn(x)值
)st[MaxSize];
int top=-1,i; // top为栈st的下标值变量
double fv=1,fv2=2*x; // n=0，n=1时得初值
for(i=n;i>=2;i--){
top++;
st[top].no=i;
} // 入栈
while[top>=0]{
st[top].val=2*x*fv-2*(st[top].no-1)*fv1;
fv1=fv2;
fv2=st[top].val;
top--; // 出栈
}
if(n==0){
return fv1;
}
return fv2;
}4. 某汽车轮渡口，过江渡船每次能载 10 辆汽车过江。过江车辆分为客车类和货车类，上渡船有如下规定：同类车先到先上船；客车先于货车上船，且每上 4 辆客车，才允许放上 1 辆货车；若等待客车不足 4 辆，则以货车代替；若无货车等待，允许客车都上船。试设计一个算法模拟渡口管理。
【解答】算法思想：假设数组 q 的最大下标为 10，恰好是每次载渡的最大量。假设客车的队列为 q1，货车的队列为 q2,。若 q1 充足，则每取 4 个 q1 元素后再取一个 q2 元素，直到 q 的长度为 10。若 q1 不充足，则直接用 q2 补齐。算法的实现如下：
Queue q; // 过江渡船载渡队列
Queue q1; // 客车队列
Queue q2; // 货车队列
void manager(){
int i=0, j=0; // j表示渡船上的总车辆数
while(j<10){ // 不足10辆时
if(!QueueEmpty(q1)&&i<4){ // 客车队列不为空，且未上足4辆
DeQueue(q1,x); // 从客车队列出队
EnQueue(q,x); // 客车上渡船
i++; // 客车数加1
j++; // 渡船上的总车辆数加1
}
else if(i==4 && !QueueEmpty(q2)){ // 客车已上足4辆
DeQueue(q2,x); // 从货车队列出队
EnQueue(q,x); // 货车上渡船
j++; // 渡船上的总车辆数加1
i=0; // 每上一辆货车，i重新计数
}
else{
while(j<10 && i<4 && !QueueEmpty(q2)){ // 空车队列为空
DeQueue(q2,x); // 从货车队列出队
EnQueue(q,x); // 货车上渡船
i++; // i计数，当i>4时，退出本循环
j++; // 渡船上的总车辆数+1
}
i=0;
}
}
if(QueueEmpty(q1) && QueueEmpty(q2)){
j=11; // 若货车和客车加起来不足10辆
}
}树
已知一棵二叉树按顺序存储结构进行存储，设计一个算法，求编号分别为 i 和 j 的两个结点的最近的公共祖先结点的值。
【解答】
首先必须明确二叉树中任意两个结点必然存在最近的公共祖先结点，最坏的情况下是根结点（两个结点分别在根结点的左右分支中），而且从最近的公共祖先结点到根结点的全部祖先结点都是公共 。由二叉树顺序存储的性质可知，任意一个结点 i 的双亲结点的编号为 i/2。求解 i 和 j 最近公共祖先结点的算法步骤如下（设从数组下标 1 开始存储）：
1）若 i > j，则结点 i 所在层次大于或等于结点 j 所在层次。结点 i 的双亲结点为结点 i/2，若 i/2=j，则结点 i/2 是源结点 i 和结点 j 的最近公共祖先结点，若 i/2≠j，则令 i=i/2，即以该结点 i 的双亲结点为起点，采用递归的方法继续查找。
2）若 j > i，则结点 j 所在层次大于或等于结点 i 所在层次。结点 i 的双亲结点为结点 j/2，若 j/2=i，则结点 j/2 是源结点 i 和结点 j 的最近公共祖先结点，若 j/2≠i，则令 j=j/2。
重复上述过程，直到找到它们最近的公共祖先结点为止。
ElemType Comm_Ancestor(SqTree T, int i, int j){
// 本算法在二叉树中查找结点i和结点j的最近公共祖先结点
if(T[i]!='#' && T[j]!='#'){ // 结点存在
while(i!=j){ // 两个编号不同时循环
if(i>j)
i=i/2; // 向上找i的祖先
else
j=j/2; // 向上找j的祖先
}
return T[i];
}
}编写后序遍历二叉树的非递归算法
【解答】算法思想：后序非递归遍历二叉树是先访问左子树，再访问右子树，最后访问根结点。结合下图分析：① 沿着根的左孩子，依次入栈，直到左孩子为空。此时栈内元素依次为 A B D。② 读栈顶元素：若其右孩子不空且未被访问过，将右子树转执行 ①；否则，栈顶元素出栈并访问。栈顶 D 的右孩子为空，出栈并访问，它是后序序列的第一个结点；栈顶 B 的右孩子不空且未被访问过，E 入栈，栈顶 E 的左右孩子均为空，出栈并访问；栈顶 B 的右孩子不空但已被访问，B 出栈并访问；栈顶 A 的右孩子不空且未被访问过，C 入栈，C 入栈，栈顶 C 的左右孩子均为空，出栈并访问；栈顶 A 的右孩子不空但已被访问，A 出栈并访问。由此得到后序序列 D E B C A。
在上述思想的第 ② 步中，必须分清返回时是从左子树返回的还是从右子树返回的，因此设定一个辅助指针 r，用于指向最近访问过的结果。也可在结点中增加一个标志域，记录是否已被访问。
void PostOrder(BiTree T){
InitStack(S);
BiTNode *p=T;
BiTNode *r=NULL;
while(p||!IsEmpty(S)){
if(p){ // 走到最左边
push(S,p);
p=p->lchild;
}
else{ // 向右
GetTop(S,p); // 读栈顶结点（非出栈）
if(p->rchild && p->rchild!=r) // 若右子树存在，且未被访问过
p=p->rchild; // 转向右
else{ // 否则，弹出结点并访问
pop(S,p); // 将结点弹出
visit(p->data); // 访问该结点
r=p; // 记录最近访问过的结点
p=NULL; // 结点访问完后，重置p指针
}
}
}
}试给出二叉树的自下而上、从右到左的层次遍历算法。
【解答】一般的二叉树层次遍历是自下而上、从左到右，这里的遍历顺序恰好相反。算法思想：利用原有的层次遍历算法，出队的同时将各结点指针入栈，在所有结点入栈后再从栈顶开始依次访问即为所求的算法。具体如下：
1）把根结点入队列。
2）把一个元素出队列，遍历这个元素。
3）依次把这个元素的左孩子、右孩子入队列。
4）若队列不空，则跳到 2），否则结束。
算法实现如下：
void InvertLevel(BiTree bt){
Stack S;Queue Q;
if(bt!=NULL){
InitStack(s); // 栈初始化，栈中存放二叉树结点的指针
InitQueue(Q); // 队列初始化，队列中存放二叉树的结点指针
Enqueue(Q,bt);
while(ISEmpty(Q)==false){ // 从上而下层次遍历
DeQueue(Q,p);
Push(s,p); // 出队，入栈
if(p->lchild)
Enqueue(Q,p->lchild); // 若左子女不空，则入队列
if(p->rchild)
Enqueue(Q,p->rchild) // 若右子女不空，则入队列
}
while(IsEmpty(s)==false){
Pop(s,p);
visit(p->data);
} // 自下而上、从右到左的层次遍历
}
}假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。
【解答】采用层次遍历的算法，设置变量 Level 记录当前结点所在的层数，设置变量 last 指向当前层的最右结点，每次层次遍历出队时与 last 指针比较，若两者相等，则层数加 1，并让 last 指向下一层的最右结点，直到遍历完成。level 的值即为二叉树的高度。
算法实现如下：
int Btdepth(BiTree T){
// 采用层次遍历的非递归方法求解二叉树的高度
if(!T)
return 0; // 树空，高度为0
int front=-1,rear=-1;
int last=0,level=0; // last指向当前层的最右结点
BiTree Q[MaxSize]; // 设置队列Q，元素是二叉树结点指针且容量足够
Q[++rear]=T; // 将根结点入队
BiTree p;
while(front<rear){ // 队不空，则循环
p=Q[++front]; // 队列元素出队，即正在访问的结点
if(p->lchild)
Q[++rear]=p->lchild; // 左孩子入队
if(p->rchild)
Q[++rear]=p->rchild; // 右孩子入队
if(front==last){ // 处理该层的最右结点
level++; // 层数增1
last=rear; // last指向下层
}
}
return level;
}求某层的结点个数、每层的结点个数、树的最大宽度等，都可采用与此题类似的思想。当然，此题可编写为递归算法，其实现如下：
int Btdepth2(BiTree T){
if(T==NULL)
return 0; // 空树，高度为0
ldep=Btdepth2(T->lchild); // 左子树高度
rdep=Btdepth2(T->rchild); // 右子树高度
if(ldep>rdep)
return ldep+1; // 树的高度为子树最大高度加根结点
else
return rdep+1;
}设一棵二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组
【解答】由先序序列和中序序列可以唯一确定一棵二叉树，算法的实现步骤如下：
1）根据先序序列确定树的根结点。
2）根据根结点在中序序列中划分出二叉树的左、右子树包含哪些结点，然后根据左、右子树结点在先序序列中的次序确定子树的根结点，即回到步骤 1）。
如此重复上述步骤，直到每棵子树仅有一个结点（该子树的根结点）为止。
算法实现如下：
BiTree PreInCreat(ElemType A[], ElemType B[], int l1, int h1, int l2, int h2){
// l1，h1为先序的第一个和最后一个结点下标，l2，h2为中序的第一个和最后一个结点下标
// 初始调用时，l1=l2=1，h1=h2=n
root=(BiTNode =)malloc(sizeof(BiTNode)); // 建根结点
root->data=A[l1]; // 根结点
for(i=l2;B[i]!=root->data;i++); // 根结点在中序序列中的划分
int llen=i-l2; // 左子树长度
int rlen=h2-i; // 右子树长度
if(llen) // 递归建立左子树
root->lchild=PreInCreat(A,B,l1+1,l1+llen,l2,l2+llen-1);
else // 左子树为空
root->lchild=NULL;
if(rlen) // 递归建立右子树
root->rchild=PreInCreat(A,B,h1-rlen+1,h1,h2-rlen+1,h2);
else // 右子树为空
root->rchild=NULL;
return root; // 返回根结点指针
}二叉树按二叉链表形式存储，试编写一个判别给定二叉树是否是完全二叉树的算法。
【解答】根据完全二叉树的定义，具有 n 个结点的完全二叉树与满二叉树中编号从 1~n 的结点一一对应。算法思想：采用层次遍历算法，将所有结点加入队列（包括空结点）。遇到空结点时，查看其后是否有非空结点。若有，则二叉树不是完全二叉树。
算法实现如下：
bool IsComplete(BiTree T){
// 本算法判断给定二叉树是否为完全二叉树
InitQueue(Q);
if(!T)
return 1; // 空树为满二叉树
EnQueue(Q,T);
while(!IsEmpty(Q)){
DeQueue(Q,p);
if(p){ // 结点非空，将其左、右子树入队列
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild);
}
else // 结点为空，检查其后是否有非空结点
while(!IsEmpty(Q)){
DeQueue(Q,p);
if(p) // 结点非空，则二叉树为非完全二叉树
return 0;
}
}
return 1;
}假设二叉树采用二叉链表存储结构存储，试设计一个算法，计算一棵给定二叉树的所有双分支结点个数。
【解答】计算一棵二叉树 b 中所有双分支结点个数的递归模型 f(b) 如下：
f(b)=0 若 b=NULL
f(b)=f(b->lchild)+f(b->rchild)+1 若 *b 为双分支结点
f(b)=f(b->lchild)+f(b->rchild) 其他情况（*b 为单分支结点或叶结点）
具体算法实现如下：
int DsonNodes(Bitree b){
if(b==NULL)
return 0;
else if(b->lchild!=NULL && b->rchild!=NULL) // 双分支结点
return DsonNodes(b->lchild)+DsonNodes(b->rchild)+1;
else{
return DsonNodes(b->lchild)+DsonNodes(b->rchild);
}
}设树 B 是一棵采用链式结构存储的二叉树，编写一个把树 B 中所有结点的左、右子树进行交换的函数。
【解答】采用递归算法实现交换二叉树的左、右子树，首先交换 b 结点的左孩子的左、右子树，然后交换 b 结点的右孩子的左、右子树，最后交换 b 结点的左、右孩子，当结点为空时递归结束（后序遍历的思想）。算法实现如下：
void swap(BiTree b){
// 本算法递归地交换二叉树的左、右子树
if(b){
swap(b->lchild); // 递归地交换左子树
swap(b->rchild); // 递归地交换右子树
temp=b->lchild; // 交换左、右孩子结点
b->lchild=b->rchild;
b->rchild=temp;
}
}假设二叉树采用二叉链存储结构存储，设计一个算法，求先序遍历序列中第 k(1≤k≤ 二叉树中结点个数)个结点的值。
【解答】设置一个全局变量 i（初值为 1）来表示进行先序遍历时，当前访问的是第几个结点。然后可以借用先序遍历的代码模型，先序遍历二叉树。当二叉树 b 为空时，返回特殊字符 '#'；当 k==i 时，该结点即为要找的结点，返回 b->data；当 k≠i 时，递归地在左子树中查找，若找到则返回该值，否则继续递归地在右子树中查找，并返回其结果。
int i=1; // 遍历序号的全局变量
ElemType PreNode(BiTre b, int k){
// 本算法查找二叉树先序遍历序列中第k个结点的值
if(b==NULL) // 空结点，则返回特殊字符
return '#';
if(i==k) // 相等，则当前结点即为第k个结点
return b->data;
i++; // 下一个结点
ch=PreNode(b->lchild,k); // 左子树中递归寻找
if(ch!='#') // 在左子树中，则返回该值
return ch;
ch=PreNode(b->rchild,k); // 在右子树中递归寻找
return ch;
}已知二叉树以二叉链表存储，编写算法完成：对于树中每个元素值为 x 的结点，删除以它为根的子树，并释放相应的空间。
【解答】删除以元素值 x 为根的子树，只要能删除其左、右子树，就可以释放值为 x 的根结点，因此宜采用后序遍历。算法思想：删除值为 x 的结点，意味着应将其父结点的左（右）子女指针置空，用层次遍历易于找到某结点的父结点。本题要求删除树中每个元素值为 x 的结点的子树，因此要遍历完整棵二叉树。算法实现如下：
void DeleteXTree(BiTree &bt){ // 删除以bt为根的子树
if(bt){
DeleteXTree(bt->lchild);
DeleteXTree(bt->rchild); // 删除bt的左子树、右子树
free(bt); // 释放被删结点所占的存储空间
}
}
// 在二叉树上查找所有以x为元素值的结点，并删除以其为根的子树
void Search(BiTree bt, ElemType x){
BiTree Q[]; // Q是存放二叉树结点指针的队列，容量足够大
if(bt){
if(bt->data==x){ // 若根结点值为x，则删除整棵树
DeleteXTree(bt);
exit(0);
}
InitQueue(Q);
EnQueue(Q,bt);
while(!IsEmpty(Q)){
DeQueue(Q,p);
if(p->lchild) // 若左子女非空
if(p->lchild->data==x){ // 左子树符合则删除左子树
DeleteXTree(p->lchild);
p->lchild=NULL;
} // 父结点的左子女置空
else
EnQueue(p->lchild); // 左子树入队列
if(p->rchild) // 若右子女非空
if(p->rchild->data==x){ // 右子女符合则删除右子树
DeleteXTree(p->rchild);
p->rchild=NULL; // 父结点的右子女置空
}
else
EnQueue(Q,p->rchild); // 右子女入队列
}
}
}在二叉树中查找值为 x 的结点，试编写算法（用 C 语言）打印值为 x 的结点的所有祖先，假设值为 x 的结点不多于一个。
【解答】算法思想：采用非递归后序遍历，最后访问根结点，访问到值为 x 的结点时，栈中所有元素均为该结点的祖先，依次出栈打印即可。算法实现如下：
typedef struct{
BiTree t;
int tag;
}stack; // tag=0表示左子女被访问，tag=1表示右子女被访问
void Search(BiTree bt, ElemType x){
stack s[]; // 栈容量足够大
top=0;
while(bt!=NULL || top>0){
while(bt!=NULL && bt->data!=x){ // 结点入栈
s[++top].t=bt;
s[top].tag=0;
bt=bt->lchild; // 沿左分支向下
}
if(bt!=NULL && bt->data==x){
printf("所查结点的所有祖先结点的值为：\n"); // 找到x
for(i=1;i<top;i++)
printf("%d",s[i].t->data); // 输出祖先值后结束
exit(1);
}
while(top!=0 && s[top].tag==1)
top--; // 退栈（空遍历）
if(top!=0){
s[top].tag=1;
bt=s[top].t->rchild; // 沿右分支向下遍历
}
}
}因为查找的过程就是后序遍历的过程，所以使用的栈的深度不超过数的深度。
设一棵二叉树的结点结构为 {LLINK,INFO,RLINK}，ROOT 为指向该二叉树根结点的指针，p 和 q 分别为指向该二叉树中任意两个结点的指针，试编写算法 ANCESTOR(ROOT,p,q,r)，找到 p 和 q 的最近公共祖先结点 r。
【解答】后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。本题要找 p 和 q 的最近公共祖先结点 r，不失一般性，设 p 在 q 的左边。算法思想：采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。后序遍历必然先遍历到结点 p，栈中元素均为 p 的祖先。先将栈复制到另一辅助栈中。继续遍历到结点 q 时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点 p 和 q 的最近公共祖先。算法实现如下：
typefeef struct{
BiTree t;
int tag;// tag=0表示左子女已被访问，tag=1表示右子女已被访问
}stack;
stakc s[], s1[]; // 栈，容量足够大
BiTree Ancestor(BiTree ROOT,BiTNode *p, BiTNode *q){
// 本算法求二叉树中p和q指向结点的最近公共结点
top=0;bt=ROOT;
while(bt!=NULL || top>0){
while(bt!=NULL){
s[++top].t=bt;
s[top].tag=0;
bt=bt->lchild;
} // 沿左分支向下
while(top!=0 && s[top].tag==1){
// 假定p在q的左侧，遇到p时，栈中元素均为p的祖先
if(s[top].t==p){
for(i=1;i<=top;i++)
s1[i]=s[i];
top1=top;
} // 将栈s的元素转入辅助栈s1保存
if(s[top].t==q) // 找到q结点
for(i=top;i>0;i--){ // 将栈中元素的结点到s1中去匹配
for(j=top1;j>0;j--)
if(s1[j].t==s[i].t)
return s[i].t; // p和q的最近公共祖先已找到
}
top--; // 退栈
}
if(top!=0){
s[top].tag=1;
bt=s[top.t]->rchild; // 沿右分支向下遍历
}
}
return NULL; // p和q无公共祖先
}假设二叉树采用二叉链表存储结构，设计一个算法，求非空二叉树 b 的宽度（即具有结点数最多的那一层的结点个数）。
【解答】采用层次遍历的方法求出所有结点的层次，并将所有结点和对应的层次放在一个队列中。然后通过扫描队列求出各层的结点总数，最大的层结点总数即为二叉树的宽度。算法实现如下：
typedef struct{
BiTree data[MaxSize]; // 保存队列中的结点指针
int level[MaxSize]; // 保存data中相同下标结点的层次
int front,rear;
}Qu;
int BTWidth(BiTree b){
BiTree p;
int k,max,i,n;
Qu.front=Qu.rear=-1, // 队列为空
Qu.rear++;
Qu.data[Qu.rear]=b; // 根结点指针入队
Qu.level[Qu.rear]=1; // 根结点层次为 1
while(Qu.front<Qu.rear){
Qu.front++; // 出队
p=Qu.data[Qu.front]; // 出队结点
k=Qu.level[Qu.front]; // 出队结点的层次
if(p->lchild!=NULL){ // 左孩子进队列
Qu.rear++;
Qu.data[Qu.rear]=p->lchild;
Qu.level[Qu.rear]=k+1;
}
if(p->rchild!=NULL){ // 右孩子进队列
Qu.rear++;
Qu.data[Qu.rear]=p->rchild;
Qu.level[Qu.rear]=k+1;
}
}
max=0;i=0; // max保存同一层最多的结点个数
k=1; // k表示从第一层开始查找
while(i<=Qu,rear){ // i扫描堆中所有元素
n=0; // n统计第k层的结点个数
while(i<=Qu.rear && Qu.level[i]==k){
n++;
i++;
}
k=Qu.level[i];
if(n>max) max=n; // 保留最大的n
}
return max;
}注意：本题队列中的结点，在出队后仍需要保留在队列中，以便求出二叉树的宽度，所以设置的队列采用非环形队列，否则在出队后可能被其他结点覆盖，无法再求二叉树的宽。
设有一棵满二叉树（所有结点值均不同），已知其先序序列为 pre，设计一个算法求其后续序列 post。
【解答】对一般二叉树，仅根据先序或后序序列，不能确定另一个遍历序列。但对满二叉树，任意一个结点的左、右子树均含有相等的结点数，同时，先序序列的第一个结点作为后序序列的最后一个结点，由此得到将先序序列 pre[l1..h1] 转换为后序序列 post[l2..h2] 的递归模型如下：
f(pre,l1,h1,post,l2,h2)=不做任何事情 h1<l1 时
f(prel1,h1,post,l2,h2)=post[h2]=pre[l1] 其他情况
取中间位置 half=(h1-l1)/2;
将 pre[l1+1,l1+half] 左子树转换为 post[l2,l2+half-1]，
即 f(pre,l1+1,l1+half,post,l2,l2+half-1);
将 pre[l1+half+1,h1] 右子树转换为 post[l2+half,h2-1]，
即 f(pre,l1+half+1,h1,post,l2+half,h2-1);。
其中，post[h2]=pre[l1] 表示后序序列的最后一个结点（根结点）等于先序序列的第一个结点（根结点）。相应的算法实现如下：
void PreToPost(ElemType pre[], int l1, int h1, ElemType post[], int l2, int h2){
int half;
if(h1>=l1){
post[h2]=pre[l1];
half=(h1-l1)/2;
PreToPost(pre,l1+1,l1+half,post,l2,l2+half-1); // 转换左子树
PreToPost(pre,l1+half+1,h1,post,l2+half,h2-1); // 转换右子树
}
}例如，有以下代码
ElemType *pre="ABCDEFG";
ElemType post[MaxSize];
PreToPost(pre,0,6,post,0,6);
printf("后序序列：");
for(int i=0;i<=6,i++)
printf("%c",post[i]);
printf("\n");
// 后序序列：C D B F G E A设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指针为 head。二叉树按二叉链表方式存储，链接时用叶结点的右指针来存放单链表指针。
【解答】通常使用的先序、中序和后序遍历对于叶结点的访问顺序都是从左到右，这里选择中序递归遍历。算法思想：设置前驱结点指针 pre，初始为空。第一个叶结点由指针 head 指向，遍历到叶结点时，就将它前驱的 rchild 指针指向它，最后一个叶结点的 rchild 为空。算法实现如下：
LinkedList head, pre=NULL; // 全局变量
LinkedList InOrder(BiTree bt){
if(bt){
InOrder(bt->lchild); // 中序遍历左子树
if(bt->lchild==NULL && bt->rchild==NULL) // 叶结点
if(pre==NULL){
head=bt;
pre=bt;
} // 处理第一个叶结点
else{
pre->rchild=bt;
pre=bt;
} // 将叶结点链入链表
InOrder(bt->rchild); // 中序遍历右子树
pre->rchild=NULL; // 设置链表尾
}
return head;
}上述算法的时间复杂度为
试设计判断两棵二叉树是否相似的算法。所谓二叉树 T1 和 T2 相似，指的是 T1 和 T2 都是空的二叉树或都只有一个根结点；或者 T1 的左子树和 T2 的左子树是相似的，且 T1 的右子树和 T2 的右子树是相似的。
【解答】本题采用递归的思想求解，若 T1 和 T2 都是空树，若有一个为空另一个不为空，则必然不相似；否则递归地比较它们的左、右子树是否相似。递归函数的定义如下：
1）f(T1,T2)=1; 若 T1 == T2 == NULL。
2）f(T1,T2)=0; 若 T1 和 T2 之一为 NULL，另一个不为 NULL。
3）f(T1,T2)=f(T1->lchild,T2->lchild)&&f(T1->rchild,T2->rchild); 若 T1 和 T2 均不为 NULL。
因此，算法的实现如下：
int similar(BiTree T1, BiTree T2){
// 采用递归的算法判断两棵二叉树是否相似
int leftS, rightS;
if(T1==NULL && T2==NULL)
return 1;
else if(T1==NULL || T2==NULL)
return 0;
else{
leftS=similar(T1->lchild,T2->lchild);
rightS=similar(T1->rchild,T2->rchild);
return leftS&&rightS;
}
}写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法。
【解答】算法思想：在后序序列中，若结点 p 有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点 p 左、右子女均无，设其中序左线索指向某祖先结点 f（p 是 f 右子树中按中序遍历的第一个结点），若 f 有左子女 ，则其左子女是结点 p 在后序下的前驱；若 f 无左子女，则顺其前驱找到双亲的双亲，一直找到双亲有左子女（这时左子女是 p 的前驱）。还有一种情况，若 p 是中序遍历的第一个结点，则结点 p 在中序和后序下均无前驱。
算法代码如下：
BiThrTree InPostPre(BiThrTree t, BiThrTree p){
// 在中序线索二叉树t中，求指定结点p在后序下前驱结点q
BiThrTree q;
if(p->rtag==0) // 若p有右子女，则右子女是其后序前驱
q=p->rchild;
else if(p->ltag==0) // 若p有左子女，则左子女是其后序前驱
q=p->lchild;
else if(p->lchild==NULL)
q=NULL; // p是中序序列的第一个结点，无后序前驱
else{ // 顺左线索向上找p祖先，若存在，再找祖先的左子女
while(p->ltag==1 && lchild!=NULL)
p=p->lchild;
if(p->ltag==0) // p结点的祖先左子女是其后序前驱
q=p->lchild;
else
q=NULL; // 仅有单支树（p是叶子），已到根结点，p无后序前驱
}
return q;
}编程求以孩子兄弟表示法存储的森林的叶结点数。
【解答】当森林（树）以孩子兄弟表示法存储时，若结点没有孩子（fch=NULL），则它必是叶子，总的叶结点个数是孩子子树（fch）上的叶子数和兄弟子树（nsib）上的叶结点个数之和。
typedef struct node{
ElemType data; // 数据域
struct node *fch,*nsib; // 孩子与兄弟域
}*Tree;
int Leaves(Tree t){ // 计算以孩子兄弟表示法存储的森林的叶子数
if(t==NULL)
return 0; // 树空返回0
if(t->fch==NULL) // 若结点无孩子，则该结点必是叶子
return 1+Leaves(t->nsib); //返回叶结点和其兄弟子树中的叶结点数
else // 孩子子树和兄弟子树中叶子数之和
return Leaves(t->fch)+Leaves(t-nsib);
}以孩子兄弟链表为存储结构，请设计递归算法求树的深度。
【解答】由孩子兄弟链表表示的树，求高度的算法思想如下：采用递归算法，若树为空，高度为零；否则，高度为第一子女树高度加 1 和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。算法代码如下：
int Height(CsTree bt){
// 递归求以孩子兄弟链表表示的树的深度
int hc,hs;
if(bt==NULL)
return 0;
else{ // 否则，高度取子女高度+1和兄弟子树高度的大者
hc=Height(bt->firstchild); // 第一子女树高
hs=Height(bt->nextsibling); // 兄弟树高
if(hc+1>hs)
return hc+1;
else
return hs;
}
}已知一棵树的层次序列及每个结点的度，编写算法构造此树的孩子-兄弟链表。
【解答】本题与树的层次序列有关。可设立一个辅助数组 pointer[] 存储新建树的各结点的地址，再根据层次序列与每个结点的度，逐个链接结点。算法描述如下：
#define maxNodes 15
void createCSTree_Degree(CSTree &T,DataType e[],int degree[], int n){
// 根据树结点的层次序列e[]和各结点的度degree[]构造树的孩子-兄弟链表
// 参数n是树结点个数
CSNode *pointer=new CSNode[maxNodes];// 判断pointer[i]为空的语句未写
int i,j,d,k=0;
for(i=0,i<n;i++){// 初始化
pointer[i]->data=e[i];
pointer[i]->lchild=pointer[i]->rsibling=NULL;
}
for(i=0;i<n;i++){
d=degree[i]; // 结点i的度数
if(d){
k++; // k为子女结点序号
pointer[i]->lchild=pointer[k]; // 建立i与子女k间的链接
for(j=2;j<=d;j++){
k++;
pointer[k-1]->rsibling=pointer[k];
}
}
}
T=pointer[0];
delete [] pointer;
}图
写出从图的邻接表表示转换成邻接矩阵表示的算法
【解答】算法的基本思想：设图的顶点分别存储在数组 v[n] 中。首先初始化邻接矩阵。遍历邻接表，在依次遍历顶点 v[i] 的边链表时，修改邻接矩阵的第 i 行的元素值。若链表边结点的值为 j，则置 arcs[i][j]=1。遍历完邻接表时，整个转换过程结束。此算法对于无向图、有向图均使用。
算法实现如下：
void Convert(ALGraph &G, int arcs[M][N]){
// 此算法将邻接表方式的图G转换为邻接矩阵arcs
for(i=0;i<n;i++){ // 依次遍历各顶点表结点为头的边链表
p=(G.v[i]).firstarc; // 取出顶点i的第一条出边
while(p!=NULL){ // 遍历边链表
arcs[i][p->adjvex]=1;
p=p->nextarc; // 取下一条出边
}
}
}试设计一个算法，判断一个无向图 G 是否为一棵树。若是一棵树，则算法返回 true，否则返回 false。
【解答】一个无向图 G 是一棵树的条件是，G 必须是无回路的连通图或有 n-1 条边的连通图。这里采用后者作为判断条件。对连通的判定，可以用能否一次遍历全部顶点来实现。可以采用深度优先搜索算法在遍历图的过程中统计可能访问到的顶点个数和边的条数，若一次遍历就能访问到 n 个顶点和 n-1 条边，则可断定此图是一棵树。算法实现如下：
bool isTree(Graph &G){
for(i=1;i<=G.vexnum;i++)
visited[i]=FALSE; // 访问标记visited[]初始化
int Vnum=0,Enum=0; // 记录顶点数和边数
DFS(G,1,Vnum,Enum,visited);
if(Vnum==G.vexnum && Enum==2*(G.vexnum-1))
return true; // 符合树的条件
else
return false; // 不符合树的条件
}
void DFS(Graph &G, int v, int &Vnum, int &Enum, int visited[]){
// 深度优先遍历图G，统计访问过的顶点数和边数，通过Vnum和Enum返回
visited[v]=TRUE;Vnum++; // 作访问标记，顶点计数
int w=FirstNeighbor(G,v); // 取v的第一个邻接顶点
while(w!=-1){ // 当邻接顶点存在
Enum++; // 边存在，边计数
if(![visited[w]]) // 当该邻接顶点为访问过
DFS(G,w,Vnum,Enum,visited);
w=NextNeighbor(G,v,w);
}
}写出图的深度优先搜索 DFS 算法的非递归算法（图采用邻接表形式）。
【解答】在深度优先搜索的非递归算法中使用了一个栈 S 来记忆下一步可能访问的顶点，同时使用了一个访问标记数组 visited[i] 来记忆第 i 个顶点是否存在栈内或曾经在栈内，若是则它以后不能再进栈。图采用邻接表形式，算法的实现如下：
void DFS_Non_RC(AGrph &G, int y){
// 从顶点v开始进行深度优先搜索，一次遍历一个连通分量的所有顶点
int w; // 顶点序号
InitStack(S); // 初始化栈S
for(i=0;i<G.vexnum;i++)
visited[i]=FALSE; // 初始化visited
Push(S,v);visited[v]=TRUE; // v入栈并置visited[v]
while(!IsEmpty(S)){
k=Pop(S); // 栈中退出一个顶点
visit(k); // 先访问，再将其子结点入栈
for(w=FisrtNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w)) // k所有邻接点
if(!visited[w]){ // 未进过栈的顶点进栈
Push(S,w);
visited[w]=true; // 作标记，以免再次入栈
}
}
}分别采用基于深度优先遍历和广度优先遍历算法判别以邻接表方式存储的有向图中是否存在由顶点 vi 到顶点 vj 的路径（i≠j）。注意，算法中涉及的图的基本操作必须在此存储结构上实现。
【解答】两个不同的遍历算法都采用从顶点 vi 出发，依次遍历图中每个顶点，直到搜索到顶点 vj，若能够搜索到 vj，则说明存在由顶点 vi 到顶点 vj 的路径。
深度优先遍历算法的实现如下：
int visited[MAXSIZE]=0; // 访问标记数组
void DFS(ALGraph G,int i,int j,bool &can_reach){
// 深度优先判断有向图G中顶点vi到顶点vj是否有路径，用can_reach来标识
if(i==j){
can_reach=true;
return; // i就是j
}
visited[i]=1; // 置访问标记
for(int p=FirstNeiighbor(G,i);p>=0;p=NextNeighbor(G,i,p))
if(!visited[p]&&!can_reach) // 递归检测邻接点
DFS(G,p,j,can_reach);
}广度优先遍历算法的实现如下：
int visited[MAXSIZE]=0; // 访问标记数组
void BFS(ALGraph G,int i,int j){
// 广度优先判断有向图G中顶点vi到顶点vj是否有路径，是则返回1，否则返回0
InitQueue(Q);EnQueue(Q,i); // 顶点i入队
while(!isEmpty(Q)){ // 非空循环
DeQueue(Q,u); // 队头顶点出队
visited[u]=1; // 置访问标记
if(u==j) return 1;
for(int p=FirstNeighbor(G,u);p;p=NextNeighbor(G,u,p)){ // 检查所有邻接点
if(p==j) // 若p==j，则查找成功
return 1;
if(!visited[p]){ // 否则，顶点p入队
EnQueue(Q,p);
}
}
}
return 0;
}本题也可以这样解答：调用以 i 为参数的 DFS(G,i) 或 BFS(G,i)，执行结束后判断 visited[j] 是否为 TRUE，若是则说明 vj 已被遍历，图中必存在由 vi 到 vj 的路径。但此种解法每次都耗费最坏时间复杂度对应的时间，需要遍历与 vi 连通的所有顶点。
假设图用邻接表表示，设计一个算法，输出从顶点 Vi 到顶点 Vj 的所有简单路径。
【解答】本题采用基于递归的深度优先遍历算法，从结点 u 出发，递归深度优先遍历图中的结点，若访问到结点 v，则输出该搜索路径上的结点。为此，设置一个 path 数组来存放路径上的结点（初始为空），d 表示路径长度（初始为 -1）。查找从顶点 u 到 v 的简单路径过程说明如下（假设查找函数名为 FindPath()）：
1）FindPath(G,u,v,path,d):d++;path[d]=u：若找到 u 的未访问过的相邻结点 u1，则继续下去，否则置 visited[u]=0 并返回。
2）FindPath(G,u1,v,path,d):d++;path[d]=u1：若找到 u1 的未访问过的相邻结点 u2，则继续下去，否则置 visited[u1]=0。
3）以此类推，继续上述递归过程，直到 ui = u，输出 path。
算法实现如下：
void FindPath(AGraph *G,int u,int v,int path, int d){
int w;
ArcNode *p;
d++; // 路径长度增1
path[d]=u; // 将当前顶点添加到路径中
visited[u]=1; // 置已访问标记
if(u==v) // 找到一条路径则输出
print(path[]); // 输出路径上的结点
p=G->adjlist[u].firstarc; // p指向u的第一个相邻点
while(p!=NULL){
w=p->adjvex; // 若顶点w未访问，递归访问它
if(visited[w]==0)
FindPath(G,w,v,path,d);
p=p->nextarc; // p指向u的下一个相邻点
}
visited[u]=0; // 恢复环境，使该顶点可重新使用
}