数据结构——C语言描述课后答案 下载本文

DelTree(bt->LChild, x); DelTree(bt->RChild, x); } }

[方法2]:(1)先序查找;(2)直接查看当前根结点(3)用指针参数; [方法3]:(1)先序查找;(2)直接查看当前根结点 (3)通过函数值,返回删除后结果; (参示例程序)

14.分别写函数完成:在先序线索二叉树T中,查找给定结点*p在先序序列中的后继。在后序线索二叉树T中,查找给定结点*p在后序序列中的前驱。 [提示]:

(1)先查看线索,无线索时用下面规律:

(2)结点*p在先序序列中的后继为其左子或右子; (3)结点*p在后序序列中的前驱也是其左子或右子。

15.分别写出算法,实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。(参例题)

16.编写算法,对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 [提示]:

(1)可将孩子-兄弟链表划分为根、首子树、兄弟树,递归处理。 (2)可利用返回值,或全局变量。

17.对以孩子-兄弟链表表示的树编写计算树的深度的算法。 18.已知二叉树按照二叉链表方式存储,利用栈的基本操作写出后序遍历非递归的算法。 (参课本)

19.设二叉树按二叉链表存放,写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指:在二叉树中不存在子树个数为1的结点。 [提示]:可利用任何递归、非递归遍历算法。

20.计算二叉树最大宽度的算法。二叉树的最大宽度是指:二叉树所有层中结点个数的最大值。 [提示]: [方法一]:

(1)利用队列,初值为根

(2)出队访问,并将左、右子入队,直到队空 (3)记录每一层中最后一个结点在队中的位置

(4)第i层最后一个结点的右子,必是第i+1层的最后一个结点 (5)第1层最后一个结点在队中的位置为0

[方法二]:利用层号和全局数组,任意遍历、统计 21.已知二叉树按照二叉链表方式存储,利用栈的基本操作写出先序遍历非递归形式的算法。

22. 证明:给定一棵二叉树的前序序列与中序序列,可唯一确定这棵二叉树; 给定一棵二叉树的后序序列与中序序列,可唯一确定这棵二叉树; 23. 二叉树按照二叉链表方式存储,编写算法将二叉树左右子树进行交换。 第七章 图

7.1 已知如图所示的有向图,请给出该图的: (1) 每个顶点的入度、出度; (2) 邻接矩阵; (3) 邻接表; (4) 逆邻接表; (5) 十字链表; (6) 强连通分量。

7.2 已知如图所示的无向图,请给出该图的: (1) 邻接多重表;(要求每个边结点中第一个顶点号小于第二个顶点号,且每个顶点的各邻接边的链接顺序,为它所邻接到的顶点序号由小到大的顺序。) (2) 从顶点1开始,深度优先遍历该图所得顶点序列和边的序列;(给出深度优先搜索树)

(3) 从顶点1开始,广度优先遍历该图所得顶点序列和边的序列。(给出广度优先搜索树)

7.3 已知如图7.31所示的AOE-网,试求:

(1) 每个事件的最早发生时间和最晚发生时间; (2) 每个活动的最早开始时间和最晚开始时间; (3) 给出关键路径。

7.4 已知如图7.30所示的有向网,试利用Dijkstra算法求顶点1到其余顶点的最短路径,并给出算法执行过程中各步的状态。

7.5 编写算法,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 {

InitALGraph(G); scanf(\

if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\

if(a<0) return ERROR; //边数不能为负 G.arcnum=a;

for(m=0;m

G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++)

{

t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR;

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode));

if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else {

for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; }

p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList

7.6 试在邻接矩阵存储结构上实现图的基本操作:InsertVertex(G,v); InsertArc(G, v, w); DeleteVertex(G,v)和DeleteArc(G, v, w)。

//本题中的图G均为有向无权图,其余情况容易由此写出

Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v {

if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex

Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[i][j].adj) {

G.arcs[i][j].adj=1; G.arcnum++; }

return OK; }//Insert_Arc

Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v {

n=G.vexnum;

if((m=LocateVex(G,v))<0) return ERROR;

G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点 for(i=0;i

{

G.arcs[i][m]=G.arcs[i][n];

G.arcs[m][i]=G.arcs[n][i]; //将边的关系随之交换 }

G.arcs[m][m].adj=0; G.vexnum--; return OK; }//Delete_Vex

分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加.

Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) {

G.arcs[i][j].adj=0; G.arcnum--; }

return OK; }//Delete_Arc

7.7 试对邻接表存储结构重做题6。

//为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出.

Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;p->nextarc=NULL;

if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p; else {

for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j) return ERROR; //边已经存在 q->nextarc=p; }

G.arcnum++; return OK; }//Insert_Arc

7.8 试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中,是否存在由顶点vi到顶点vj的路径(i≠j)。注意:算法中涉及的图的基本操作必须在此存储结构上