} BiTNode, *BiTree;
6.44④ 编写递归算法：求二叉树中以元素值为x的结点为根的子树的深度。 要求实现下列函数：
int Depthx(BiTree T, TElemType x);
/* 求二叉树中以值为x的结点为根的子树深度 */ 二叉链表类型定义： typedef struct BiTNode { TElemType data;
BiTNode *lchild, *rchild; } BiTNode, *BiTree;
6.46③ 编写复制一棵二叉树的非递归算法。 要求实现下列函数：
void CopyBiTree(BiTree T, BiTree &TT); /* 基于层次遍历的非递归复制二叉链表 */ 二叉链表类型定义：
typedef char TElemType; // 设二叉树的元素为char类型 typedef struct BiTNode { TElemType data;
BiTNode *lchild, *rchild; } BiTNode, *BiTree;
可用队列类型Queue的相关定义：
int sprintf(char *buffer, char *format [, argument, ...]); char *strcat(char *dest, char *src);
6.49④ 编写算法判别给定二叉树是否为完全二叉树。 要求实现下列函数：
Status CompleteBiTree(BiTree bt);
/* judge if the binary tree whose root is bt */ /* is a complete tree. */ 二叉链表类型定义： typedef struct BiTNode { TElemType data;
BiTNode *lchild, *rchild; } BiTNode, *BiTree;
可用队列类型Queue的相关定义：
typedef BiTree QElemType; // 设队列元素为二叉树的指针类型 Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, QElemType e); Status DeQueue(Queue &Q, QElemType &e); Status GetHead(Queue Q, QElemType &e); Status QueueEmpty(Queue Q);
6.65④ 已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。 要求实现以下函数：
typedef BiTree QElemType; // 设队列元素为二叉树的指针类型 void BuildBiTree(BiTree &bt, int ps, char *pre, Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, QElemType e); Status DeQueue(Queue &Q, QElemType &e); Status GetHead(Queue Q, QElemType &e); Status QueueEmpty(Queue Q);
6.47④ 编写按层次顺序(同一层自左至右)遍历二叉树的算法。 要求实现下列函数：
void LevelOrder(BiTree bt, char *ss);
/* travel BiTree bt by level, Return result by ss. */ 二叉链表类型定义：
typedef char TElemType; // 设二叉树的元素为char类型 typedef struct BiTNode { TElemType data;
BiTNode *lchild, *rchild; } BiTNode, *BiTree;
可用队列类型Queue的相关定义： Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, QElemType e); Status DeQueue(Queue &Q, QElemType &e); Status GetHead(Queue Q, QElemType &e); Status QueueEmpty(Queue Q);
提示：可将遍历元素的值（字符）依次置入ss，并最后以'\\0'结尾。也可以用下列字符串函数产生ss：
int is, char *ino, int n); /* 当前要建立的子树bt的元素总数为n，*/ /* 元素在前序序列pre的起始位置为ps，*/ /* 元素在中序序列ino的起始位置为is */ 二叉链表类型定义： typedef char TElemType; typedef struct BiTNode { TElemType data;
BiTNode *lchild, *rchild; } BiTNode, *BiTree;
7.22③ 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。 注意：算法中涉及的图的基本操作必须在此存储结构上实现。 实现下列函数：
Status DfsReachable(ALGraph g, int i, int j);
/* Judge if it exists a path from vertex 'i' to */
typedef BiTree QElemType; // 设队列元素为二叉树的指针类型 /* vertex 'j' in digraph 'g'. */
/* Array 'visited[]' has been initialed to 'false'.*/ 图的邻接表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex;
struct ArcNode *nextarc;
- 9 -
} ArcNode;
typedef struct VNode { VertexType data; ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph;
void visit(char v);
Status InitStack(SStack &s);
Status Push(SStack &s, SElemType x); Status Pop(SStack &s, SElemType &x); Status StackEmpty(SStack s);
Status GetTop(SStack s, SElemType &e);
7.27④ 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。 实现下列函数：
7.23③ 同7.22题要求。试基于图的广度优先搜索策略写一算法。 Status SinglePath(ALGraph g, VertexType sv, VertexType tv, 实现下列函数：
Status BfsReachable(ALGraph g, int i, int j);
/* Determine whether it exists path from vertex i to */ /* vertex j in digraph g with Breadth_First Search. */ /* Array 'visited' has been initialed to 'false'. */ 图的邻接表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex;
struct ArcNode *nextarc; } ArcNode;
typedef struct VNode { VertexType data; ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph;
Status InitQueue(Queue &q); Status EnQueue(Queue &q, int e); Status DeQueue(Queue &q, int &e); Status QueueEmpty(Queue q); Status GetFront(Queue q, int &e);
7.24③ 试利用栈的基本操作编写，按深度优先搜索策略遍历一
int k, char *sp);
//Judge whether it exists a path from sv to tv with length k // in graph g, return path using string sp if exists. 图的邻接表以及相关类型、函数和辅助变量定义如下： Status visited[MAX_VERTEX_NUM];
typedef char StrARR[100][MAX_VERTEX_NUM+1]; typedef char VertexType; typedef struct ArcNode { int adjvex;
struct ArcNode *nextarc; } ArcNode;
typedef struct VNode { VertexType data; ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph;
int Loc_Vertex(Graph g, VertexType v); void inpath(char *&path, VertexType v); /* Add vertex 'v' to 'path' */
void depath(char *&path, VertexType v); /* Remove vertex 'v' from 'path' */
7.28⑤ 已知有向图和图中两个顶点u和v，试编写算法求有向图中从u到v的所有简单路径。
个强连通图的非递归形式的算法。算法中不规定具体的存储结构，实现下列函数： 而将图Graph看成是一种抽象的数据类型。 实现下列函数：
void Traverse(Graph dig, VertexType v0,
void(*visit)(VertexType));
/* Travel the digraph 'dig' with Depth_First Search. */ 图以及相关类型、函数和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; int Loc_Vertex(Graph g, VertexType v); VertexType Get_Vertex(Graph g, int i); int First_Adj(Graph g, int v); int Next_Adj(Graph g, int v, int w); - 10 -
void AllPath(ALGraph g, VertexType sv, VertexType tv, StrARR &path, int &i);
/* Get all the paths from vertex sv to tv, save them */ /* into Array path which contains string components. */ /* Return the number of path using i */ 图的邻接表以及相关类型、函数和辅助变量定义如下： Status visited[MAX_VERTEX_NUM];
typedef char StrARR[100][MAX_VERTEX_NUM+1]; typedef char VertexType; typedef struct ArcNode { int adjvex;
struct ArcNode *nextarc; } ArcNode;
typedef struct VNode { VertexType data; ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph;
int Loc_Vertex(Graph g, VertexType v); void inpath(char *path, VertexType v); /* Add vertex 'v' to 'path' */ void depath(char *path, VertexType v); /* Remove vertex 'v' from 'path' */
7.29⑤ 试写一个算法，在以邻接矩阵方式存储的有向图G中求顶点i到顶点j的不含回路的、长度为k的路径数。 实现下列函数：
int SimplePath(MGraph G, int i, int j, int k);
/* 求有向图G的顶点i到j之间长度为k的简单路径条数 */ 图的邻接矩阵存储结构的类型定义如下： typedef enum { DG,DN,AG,AN } GraphKind;
// 有向图,有向网,无向图,无向网
typedef struct {
VRType adj; // 顶点关系类型。
// 对无权图，用1(是)或0(否)表示相邻否；
// 对带权图，则为权值类型 InfoType *info; // 该弧相关信息的指针(可无) }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {
AdjMatrix arcs; // 邻接矩阵
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 int vexnum,arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 }MGraph;
7.31③ 试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。 实现下列函数：
typedef struct ArcBox { int tailvex,headvex;
struct ArcBox *hlink,*tlink; } ArcBox;
typedef struct VexNode { VertexType data;
ArcBox *firstin,*firstout; } VexNode; typedef struct {
VexNode xlist[MAX_VERTEX_NUM]; int vexnum, arcnum; } OLGraph;
◆9.25③ 假设顺序表按关键字自大至小有序，试改写教科书9.1.1节中的顺序查找算法，将监视哨设在高下标端。然后画出描述此查找过程的判定树，分别求出等概率情况下查找成功和不成功时的平均查找长度。 实现下列函数：
int Search(SSTable s, KeyType k); /* Index the element which key is k */ /* in StaticSearchTable s. */ /* Return 0 if x is not found. */ 静态查找表的类型SSTable定义如下： typedef struct { KeyType key;
... ... // 其他数据域 } ElemType; typedef struct { ElemType *elem; int length; } SSTable;
9.26② 试将折半查找算法改写成递归算法。 实现下列函数：
int BinSearch(SSTable s, int low, int high, KeyType k); /* Index the element which key is k */ /* in StaticSearchTable s. */ /* Return 0 if x is not found. */ 静态查找表的类型SSTable定义如下： typedef struct {
void StronglyConnected(OLGraph dig, StrARR &scc, int &n); KeyType key;
/* Get all the strongly connected components in the digraph ... ... // 其他数据域 dig, */
} ElemType;
/* and put the ith into scc[i] which is a string. typedef struct { */
图的十字链表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; int finished[MAX_VERTEX_NUM];
ElemType *elem; int length; } SSTable;
typedef char StrARR[MAX_VERTEX_NUM][MAX_VERTEX_NUM+1]; // 9.31④ 试写一个判别给定二叉树是否为二叉排序树的算法，设记录各强连通分量
此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。
- 11 -
实现下列函数：
Status IsBSTree(BiTree t);
/* 判别给定二叉树t是否为二叉排序树。*/ /* 若是，则返回TRUE，否则FALSE */ 二叉树的类型BiTree定义如下： typedef struct { KeyType key;
... ... // 其他数据域 } ElemType;
typedef struct BiTNode { ElemType data;
BiTNode *lchild,*rchild; }BiTNode, *BiTree;
9.33③ 编写递归算法，从大到小输出给定二叉排序树中所有关键字不小于x的数据元素。要求你的算法的时间复杂度为O(log2n+m)，其中n为排序树中所含结点数，m为输出的关键字个数。
实现下列函数：
void OrderOut(BiTree t, KeyType x,
void(*visit)(TElemType));
/* Output is to use visit(t->data); */ 二叉树的类型BiTree定义如下： typedef struct { KeyType key;
... ... // 其他数据域 } ElemType;
typedef struct BiTNode { ElemType data;
BiTNode *lchild,*rchild; }BiTNode, *BiTree;
9.44④ 已知某哈希表的装载因子小于1，哈希函数H(key)为关键字(标识符)的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。 实现下列函数：
void PrintKeys(HashTable ht, void(*print)(StrKeyType)); /* 依题意用print输出关键字 */ 哈希表的类型HashTable定义如下： #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1 typedef char StrKeyType[4]; typedef struct { StrKeyType key; void *any; } HElemType;
int hashsize[] = { 7,11,17,23,29,37,47 }; typedef struct { - 12 -
HElemType elem[MAXLEN]; int count; int sizeindex; } HashTable;
9.45③ 假设哈希表长为m，哈希函数为H(x)，用链地址法处理冲突。试编写输入一组关键字并建造哈希表的算法。 实现下列函数：
int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]); /* 直接调用下列函数 */ /* 哈希函数： */ /* int Hash(ChainHashTab H, HKeyType k); */ /* 冲突处理函数： */ /* int Collision(ChainHashTab H, HLink &p); */ 哈希表的类型ChainHashTab定义如下： #define NUM 7 #define NULLKEY -1 #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1 typedef char HKeyType; typedef struct HNode { HKeyType data; struct HNode* next; }*HLink;
typedef struct {
HLink *elem; // 指针存储基址，动态分配数组 int count; // 当前表中含有的记录个数 int cursize; // 哈希表的当前容量 }ChainHashTab; // 链地址哈希表 int Hash(ChainHashTab H, HKeyType k) { // 哈希函数
return k % H.cursize; }
Status Collision(ChainHashTab H, HLink &p) { // 求得下一个探查地址p if (p && p->next) { p = p->next; return SUCCESS; } else return UNSUCCESS; }
10.23② 试以L.r[k+1]作为监视哨改写教材10.2.1节中给出的直接插入排序算法。其中，L.r[1..k]为待排序记录且k void InsertSort(SqList &L); 顺序表的类型SqList定义如下： typedef struct { KeyType key; ...
