厂工数据结构Anyview（C语言版）第七、八章答案（完结）

╰半夏微凉° 2023-01-10 10:17 291阅读 0赞

### 第七、八章 ###

*  第七章
 *   *  一、试编写算法，对一棵以孩子兄弟链表表示的树统计叶子的个数
     *  二、试编写算法，求一棵以孩子兄弟链表表示的树的度
     *  三、试编写算法，对以双亲表示法存储的树计算深度
     *  四、试编写算法，对以双亲孩子表示法存储的树计算深度
     *  五、试编写算法，对以孩子-兄弟链表表示的树计算深度
     *  六、试编写非递归算法，实现并查集带路径压缩的查找操作
 *  第八章
 *   *  一、编写算法，创建有向图的邻接数组存储结构
     *  二、编写算法，在图G中，相对于k顶点的当前邻接顶点m顶点，求下一个邻接顶点
     *  三、编写算法，在图G中置顶点v到顶点w的弧或边
     *  四、编写算法，计算以邻接表方式存储的有向图G中k顶点的出度
     *  五、编写算法，计算以邻接表方式存储的有向图G中k顶点的入度
     *  六、编写算法，创建有向图的邻接表存储结构
     *  七、编写算法，创建无向图的邻接表存储结构

# 第七章 #

## 一、试编写算法，对一棵以孩子兄弟链表表示的树统计叶子的个数 ##

【题目】试编写算法，对一棵以孩子兄弟链表表示的树统计叶子的个数。

孩子兄弟链表类型定义：  
typedef struct CSTNode \{  
TElemType data;  
struct CSTNode \*firstChild, \*nextSibling;  
\} CSTNode, \*CSTree;

要求实现下列函数：  
int Leave(CSTree T); /\* 统计树T的叶子数 \*/

#include "allinclude.h"  //DO NOT edit this line
    int Leave(CSTree T){
         
        // Add your code here
        
        if(!T) return 0;
        
        //如果当前结点的左孩子为空，则该左孩子就是一个叶子；返回它右兄弟的叶子数再加上左孩子这个叶子（+1）
        if(!T->firstChild) return 1+Leave(T->nextSibling);
        
        return Leave(T->firstChild)+Leave(T->nextSibling);
    }

## 二、试编写算法，求一棵以孩子兄弟链表表示的树的度 ##

【题目】试编写算法，求一棵以孩子兄弟链表表示的树的度。

孩子兄弟链表类型定义：  
typedef struct CSTNode \{  
TElemType data;  
struct CSTNode \*firstChild, \*nextSibling;  
\} CSTNode, \*CSTree;

要求实现下列函数：  
int Degree(CSTree T); /\* 求树T的度 \*/

#include "allinclude.h"  //DO NOT edit this line
    int Degree(CSTree T){
         
        // Add your code here
        
        if(!T) return 0;
        
        CSTree p;
        int sum1,sum2,sum;
        
        sum1 = 0;
        sum = 0;
        sum2 = 0;
        
        p = T->firstChild;
        
        while(p){
        
          
          sum1++;
          
          sum2 = Degree(p);
          
          //sum记录每个结点的子树的度中的最大值
          sum = sum>sum2?sum:sum2;
          
          p = p->nextSibling;
        
        //返回当前结点的度与子树中的最大度中的较大值
        return sum1>sum?sum1:sum;
    }

## 三、试编写算法，对以双亲表示法存储的树计算深度 ##

【题目】试编写算法，对以双亲表示法存储的树计算深度。

树的双亲表示法的类型定义如下：  
typedef struct \{  
TElemType data;  
int parent; // 双亲位置  
\} PTNode; // 结点类型  
typedef struct \{  
PTNode nodes\[MAX\_TREE\_SIZE\]; // 结点存储空间  
int n, r; // 结点数和根的位置  
\} PTree;

要求实现以下函数：  
int PTreeDepth(PTree T); /\* 求树T的深度 \*/

#include "allinclude.h"  //DO NOT edit this line
    int PTreeDepth(PTree T){
         
        // Add your code here
      
        int i,j,dep,depmax = 0;
        
        for(i = 0;i < T.n;i++){
        
          
          //用dep记录到当前层的深度-1（除根结点）
          dep = 0;
          
          for(j = i;j > 0;j = T.nodes[j].parent) dep++;
          
          //与上一个结点的深度比较，取最大值
          depmax = dep>depmax?dep:depmax;
        }
        
        return depmax+1;//加上根节点那一层！
    }

## 四、试编写算法，对以双亲孩子表示法存储的树计算深度 ##

【题目】试编写算法，对以双亲孩子表示法存储的树计算深度。

孩子链表类型定义：  
typedef struct ChildNode \{ // 孩子结点  
int childIndex;  
struct ChildNode \*nextChild;  
\} ChildNode; // 孩子结点类型  
typedef struct \{  
TElemType data;  
int parent; // 双亲位置  
struct ChildNode \*firstChild; // 孩子链表头指针  
\} PCTreeNode; // 结点类型  
typedef struct \{  
PCTreeNode \*nodes; // 结点存储空间  
int n, r; // 结点数和根的位置  
\} PCTree;

要求实现下列函数：  
int PCTreeDepth(PCTree T); /\* 求树T的深度 \*/

#include "allinclude.h"  //DO NOT edit this line
    int Depth(PCTree T, int pos){
         //构造一个可以由任意结点位置计算出深度的函数
        // Add your code here
        
        if(!T.nodes[pos].firstChild) return 1;
        
        ChildNode *temp = T.nodes[pos].firstChild;
        int depth,max;
        
        depth = 1;
        max = 1;
        
        //遍历每一个结点的孩子
        while(temp){
        
          
          //递归算出以每个结点为根结点的树的深度，并找出深度最大值，用max记住
          if(T.nodes[temp->childIndex].firstChild){
        
            
            depth = Depth(T,temp->childIndex);
            
            max = max>depth?max:depth;
            
          }
            
            temp = temp->nextChild;
        }
        
        return max+1;
    } 
    
    int PCTreeDepth(PCTree T){
        
      
      return Depth(T,T.r);
    }

## 五、试编写算法，对以孩子-兄弟链表表示的树计算深度 ##

【题目】试编写算法，对以孩子-兄弟链表表示的树计算深度。

孩子兄弟链表类型定义：  
typedef struct CSTNode \{  
TElemType data;  
struct CSTNode \*firstChild, \*nextSibling;  
\} CSTNode, \*CSTree;

要求实现下列函数：  
int TreeDepth(CSTree T);  
/\* 求树T的深度 \*/

#include "allinclude.h"  //DO NOT edit this line
    int TreeDepth(CSTree T){
         
        // Add your code here
        
        if(!T) return 0;
        
        int dep1,dep2;
        
        dep1 = TreeDepth(T->firstChild);
        dep2 = TreeDepth(T->nextSibling);
        
        return dep1+1>dep2?dep1+1:dep2;
    }

## 六、试编写非递归算法，实现并查集带路径压缩的查找操作 ##

【题目】试编写非递归算法，实现并查集带路径压缩的查找操作。

并查集的类型定义如下：  
typedef struct \{  
int \*parent;  
int n;  
\} MFSet;

实现下列函数：  
int find(MFSet S, int i);  
/\* 并查集带路径压缩的查找的非递归实现 \*/

#include "allinclude.h"  //DO NOT edit this line
    int find(MFSet S, int i){
         
        // Add your code here
        
        if(i < 0||i >= S.n) return -1;
        
        int k,j;
        
        j = i;
        
        //用j记住根节点的位置
        while(S.parent[j] >= 0) j = S.parent[j];
        
        while(i != j){
        
          
          k = S.parent[i];//用k记住当前结点的父结点
          S.parent[i] = j;//把父结点换成根结点
          
          i = k;//转到原父结点重复操作
        }
        
        return j;
    }

# 第八章 #

## 一、编写算法，创建有向图的邻接数组存储结构 ##

【题目】编写算法，创建有向图的邻接数组存储结构。

图的邻接数组存储结构的类型定义如下：  
\#define UNVISITED 0  
\#define VISITED 1  
\#define MAX\_VEX\_NUM 4  
\#define INFINITY MAXINT // 计算机允许的整数最大值，即∞  
typedef int VRType;  
typedef char InfoType;  
typedef char VexType;  
typedef enum \{DG,DN,UDG,UDN\} GraphKind; // 有向图,有向网,无向图,无向网  
typedef struct \{  
VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；  
// 对带权图，则为权值类型  
InfoType \*info; // 该弧相关信息的指针(可无)  
\}ArcCell;//,AdjMatrix\[MAX\_VERTEX\_NUM\]\[MAX\_VERTEX\_NUM\];  
typedef struct \{  
ArcCell arcs\[MAX\_VEX\_NUM\]\[MAX\_VEX\_NUM\]; // 关系数组  
VexType vexs\[MAX\_VEX\_NUM\]; // 顶点数组  
int n, e; // 顶点数和边（弧）数  
GraphKind kind; // 图的类型  
\} MGraph; // 邻接数组类型  
typedef struct \{  
VexType v, w;  
int inf;  
\} ArcInfo;

可调用以下基本操作：  
Status InitGraph(MGraph &G, GraphKind kind, int n);  
// 初始化含n个顶点空间的kind类的空图G  
int LocateVex(MGraph G, VexType v); // 查找顶点v在图G中的位序

要求实现以下函数：  
Status CreateDG(MGraph &G, VexType \*vexs, int n,  
ArcInfo *arcs, int e);  
/* 创建含n个顶点和e条边的有向图G，vexs为顶点信息，arcs为边信息 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status CreateDG(MGraph &G, VexType *vexs, int n,
                               ArcInfo *arcs, int e){
         
        // Add your code here
        
        //初始化一个n个顶点空间的有向空图
        InitGraph(G,DG,n);
        
        int i,j,k,m;
        
        //赋值
        G.n = n;
        G.e = e;
        
        //构建顶点数组
        for(m = 0;m < n;m++){
        
          
          G.vexs[m] = vexs[m];
        }
        
        //构建邻接数组
        for(k = 0;k < G.e;k++){
        
          
          /*找到两个邻接顶点
          外部传入的arcs是一维数组，里面存储的是两个链接顶点的相关信息*/
          i = LocateVex(G,arcs[k].v);
          j = LocateVex(G,arcs[k].w);
          
          if(i < 0||j < 0) return ERROR;
          
          G.arcs[i][j].adj = 1;//有关系置位为1
          //G.arcs[i][j].info = arcs[k].inf;
        }
        
        return OK;
    }

## 二、编写算法，在图G中，相对于k顶点的当前邻接顶点m顶点，求下一个邻接顶点 ##

【题目】编写算法，在图G中，相对于k顶点的当前邻接顶点m顶点，求下一个邻接顶点。

要求实现以下函数：  
int NextAdjVex(MGraph G, int k, int m);  
/\* 在图G中，相对于k顶点的当前邻接顶点m顶点，求下一个邻接顶点 \*/

#include "allinclude.h"  //DO NOT edit this line
    int NextAdjVex(MGraph G, int k, int m){
         
        // Add your code here
        
        //没有顶点时，返回0
        if(G.n == 0&&k == 0&&m == 0) return 0;
        
        for(int i = m+1;i < G.n;i++)
          if(G.arcs[k][i].adj == 1 ) return i;
        
        //没有找到目标顶点，返回-1
        return -1;
    }

## 三、编写算法，在图G中置顶点v到顶点w的弧或边 ##

【题目】编写算法，在图G中置顶点v到顶点w的弧或边。

可调用以下基本操作：  
int LocateVex(MGraph G, VexType v); // 查找顶点v在图G中的位序

要求实现以下函数：  
Status SetArc(MGraph &G, VexType v, VexType w, ArcCell info);  
/\* 在图G中置顶点v到顶点w的弧或边 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status SetArc(MGraph &G, VexType v, VexType w, ArcCell info){
         
        // Add your code here
        
        if(v == w) return ERROR;//若两个顶点相等，则不能产生关系
        
        int i,j;
        
        i = LocateVex(G,v);
        j = LocateVex(G,w);
        
        if(i < 0||j <0) return ERROR;
        
        //当v和w没关系时再生成边，已经有关系就直接返回OK
        if(!G.arcs[i][j].adj){
        
          
          G.arcs[i][j] = info;
        
          G.e++;
        }
        
        return OK;
    }

## 四、编写算法，计算以邻接表方式存储的有向图G中k顶点的出度 ##

【题目】编写算法，计算以邻接表方式存储的有向图G中k顶点的出度。

图的邻接表存储结构的类型定义如下：  
\#define UNVISITED 0  
\#define VISITED 1  
\#define INFINITY MAXINT // 计算机允许的整数最大值，即∞  
typedef char VexType;  
typedef enum \{DG,DN,UDG,UDN\} GraphKind; // 有向图,有向网,无向图,无向网  
typedef struct AdjVexNode \{  
int adjvex; // 邻接顶点在顶点数组中的位序  
struct AdjVexNode \*next; // 指向下一个邻接顶点（下一条边或弧）  
int info; // 存储边（弧）相关信息，对于非带权图可不用  
\} AdjVexNode, \*AdjVexNodeP; // 邻接链表的结点类型  
typedef struct VexNode \{  
VexType data; // 顶点值，VexType是顶点类型，由用户定义  
struct AdjVexNode \*firstArc; // 邻接链表的头指针  
\} VexNode; // 顶点数组的元素类型  
typedef struct \{  
VexNode \*vexs; // 顶点数组，用于存储顶点信息  
int n, e; // 顶点数和边（弧）数  
GraphKind kind; // 图的类型  
int \*tags; // 标志数组  
\} ALGraph; // 邻接表类型

要求实现下列函数：  
int outDegree(ALGraph G, int k);  
/\* 求有向图G中k顶点的出度。若k顶点不存在，则返回-1 \*/

#include "allinclude.h"  //DO NOT edit this line
    int outDegree(ALGraph G, int k){
         
        // Add your code here
        
        if(k > G.n||k < 0) return -1;
        
        AdjVexNode *p = G.vexs[k].firstArc;
        int sum = 0;
        
        while(p){
        
          
          sum++;
          
          p = p->next;
        }
        
        return sum;
    }

## 五、编写算法，计算以邻接表方式存储的有向图G中k顶点的入度 ##

【题目】编写算法，计算以邻接表方式存储的有向图G中k顶点的入度。

要求实现下列函数：  
int inDegree(ALGraph G, int k);  
/\* 求有向图G中k顶点的入度。若k顶点不存在，则返回-1 \*/

#include "allinclude.h"  //DO NOT edit this line
    int inDegree(ALGraph G, int k){
         
        // Add your code here
        
        if(k > G.n||k < 0) return -1;
        
        int sum = 0;
        AdjVexNode *p;
        
        for(int i = 0;i < G.n;i++){
        
          
          p = G.vexs[i].firstArc;
          
          while(p){
        
            
            if(p->adjvex == k) sum++;
            
            p = p->next;
          }
        }
        
        return sum;
    }

## 六、编写算法，创建有向图的邻接表存储结构 ##

【题目】编写算法，创建有向图的邻接表存储结构。

图的邻接表存储结构的类型定义如下：  
\#define UNVISITED 0  
\#define VISITED 1  
\#define MAX\_VEX\_NUM 4  
\#define INFINITY MAXINT // 计算机允许的整数最大值，即∞  
typedef char VexType;  
typedef enum \{DG,DN,UDG,UDN\} GraphKind; // 有向图,有向网,无向图,无向网  
typedef struct AdjVexNode \{  
int adjvex; // 邻接顶点在顶点数组中的位序  
struct AdjVexNode \*next; // 指向下一个邻接顶点（下一条边或弧）  
int info; // 存储边（弧）相关信息，对于非带权图可不用  
\} AdjVexNode, \*AdjVexNodeP; // 邻接链表的结点类型  
typedef struct VexNode \{  
VexType data; // 顶点值，VexType是顶点类型，由用户定义  
struct AdjVexNode \*firstArc; // 邻接链表的头指针  
\} VexNode; // 顶点数组的元素类型  
typedef struct \{  
VexNode vexs\[MAX\_VEX\_NUM\]; // 顶点数组，用于存储顶点信息  
int n, e; // 顶点数和边（弧）数  
GraphKind kind; // 图的类型  
int \*tags; // 标志数组  
\} ALGraph; // 邻接表类型

可调用以下基本操作：  
int LocateVex(ALGraph G, VexType v); // 查找顶点v在图G中的位序

要求实现下列函数：  
Status CreateDG(ALGraph &G, VexType \*vexs, int n,  
ArcInfo *arcs, int e);  
/* 创建含n个顶点和e条边的有向图G，vexs为顶点信息，arcs为边信息 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status CreateDG(ALGraph &G, VexType *vexs, int n, ArcInfo *arcs, int e){
         
        // Add your code here
        
        int i,j,k,m;
        AdjVexNode *p;
        
        G.n = n;
        G.e = e;
        
        G.tags = (int *)malloc(n*sizeof(int));
        
        for(m = 0;m < n;m++){
        
          
          G.tags[m] = UNVISITED;//标志数组用于遍历
          G.vexs[m].data = vexs[m];
          G.vexs[m].firstArc = NULL;//别漏了这个初始化！
        }
        
        for(k = 0;k < e;k++){
        
          
          i = LocateVex(G,arcs[k].v);
          j = LocateVex(G,arcs[k].w);
          
          if(i < 0||j < 0) return ERROR;
          
          p = (AdjVexNode *)malloc(sizeof(AdjVexNode));
          
          if(!p) return ERROR;
          
          //每次都把w对应的结点插到v对应数组头结点的下一个结点
          p->adjvex = j;
          p->next = G.vexs[i].firstArc;
          G.vexs[i].firstArc = p;
        }
        
        return OK;
    }

## 七、编写算法，创建无向图的邻接表存储结构 ##

【题目】编写算法，创建无向图的邻接表存储结构。

图的邻接表存储结构的类型定义如下：  
\#define UNVISITED 0  
\#define VISITED 1  
\#define MAX\_VEX\_NUM 4  
\#define INFINITY MAXINT // 计算机允许的整数最大值，即∞  
typedef char VexType;  
typedef enum \{DG,DN,UDG,UDN\} GraphKind; // 有向图,有向网,无向图,无向网  
typedef struct AdjVexNode \{  
int adjvex; // 邻接顶点在顶点数组中的位序  
struct AdjVexNode \*next; // 指向下一个邻接顶点（下一条边或弧）  
int info; // 存储边（弧）相关信息，对于非带权图可不用  
\} AdjVexNode, \*AdjVexNodeP; // 邻接链表的结点类型  
typedef struct VexNode \{  
VexType data; // 顶点值，VexType是顶点类型，由用户定义  
struct AdjVexNode \*firstArc; // 邻接链表的头指针  
\} VexNode; // 顶点数组的元素类型  
typedef struct \{  
VexNode vexs\[MAX\_VEX\_NUM\]; //\*vexs; 顶点数组，用于存储顶点信息  
int n, e; // 顶点数和边（弧）数  
GraphKind kind; // 图的类型  
int \*tags; // 标志数组  
\} ALGraph; // 邻接表类型

可调用以下基本操作：  
int LocateVex(ALGraph G, VexType v); // 查找顶点v在图G中的位序

要求实现下列函数：  
Status CreateUDG(ALGraph &G, VexType \*vexs, int n,  
ArcInfo *arcs, int e);  
/* 创建含n个顶点和e条边的无向图G，vexs为顶点信息，arcs为边信息 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status CreateUDG(ALGraph &G, VexType *vexs, int n, ArcInfo *arcs, int e){
         
        // Add your code here
    
        int i,j,k,m;
        AdjVexNode *p,*q;
        
        G.n = n;
        G.e = e;
    
        G.tags = (int *)malloc(n*sizeof(int));
        
        for(m = 0;m < n;m++){
        
          
          G.tags[m] = UNVISITED;
          G.vexs[m].data = vexs[m];
          G.vexs[m].firstArc = NULL;//别漏了这个初始化！
        }
        
        for(k = 0;k < e;k++){
        
          
          i = LocateVex(G,arcs[k].v);
          j = LocateVex(G,arcs[k].w);
          
          if(i < 0||j < 0) return ERROR;//假若i，j不存在
          
          p = (AdjVexNode *)malloc(sizeof(AdjVexNode));
          if(!p) return OVERFLOW;
          p->adjvex = j;
          p->next = G.vexs[i].firstArc;
          G.vexs[i].firstArc = p;
          
          q = (AdjVexNode *)malloc(sizeof(AdjVexNode));
          if(!q) return OVERFLOW;
          q->adjvex = i;
          q->next = G.vexs[j].firstArc;
          G.vexs[j].firstArc = q;
        }
        
        return OK;
    }