第五次数据结构上机实验报告

1、

题目： 1．编程实现书P156  ADT Graph 基本操作13个，用邻接矩阵存储结构实现；

算法思想：以邻接矩阵的形式实现操作

源程序：#define INFINITY INT_MAX                    //最大值为无穷大

#define MAX_VERTEX_NUM 20                   //最大顶点个数

#include

using namespace std;

typedef enum {DG,DN,AG,AN}GraphKind;        //{有向图，有向网，无向图，无向网}

typedef int Status;

typedef int VRType;

typedef char InfoType;

typedef struct ArcCell{

    VRType adj;                             //表示顶点关系，对于无向图有向图用0和1表示是否相邻，对于有向图有向网用权值类型表示

    InfoType* info;                         //该弧相关信息的指针

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {//点的值

    char name;

    char* data;

}VertexType[MAX_VERTEX_NUM]; 

typedef struct{

    VertexType vexs;        //顶点向量

    AdjMatrix arcs;                         //邻接矩阵

    int vexnum;                             //图的当前顶点数

    int arcnum;                             //图的当前弧数

    GraphKind kind;                         //图的种类标志

}MGraph;

//***********************以下操作默认是无向网，即Kind = AG**************************

//***********************顶点是名称字母。书上的是数字，例如v************************

Status LocateVex(MGraph G,char u){

    if(G.vexnum == 0) return -1;      //图不存在

    int i;

    for(i = 0;i < G.vexnum;i++)

        if(G.vexs[i].name == u)

            return i;

    return -2;                        //图中不存在与u相等的点

}

Status CreateGraph(MGraph& G){

    int i,j,k;

    VRType w;                      

    char v1,v2;

    char data[50];

    cout << "你想要创建几个顶点？ " << endl;

    cin >> G.vexnum;

    cout << "你想要创建几条弧？ " << endl;

    cin >> G.arcnum;

    cout << "依次输入顶点名称:" << endl;

    for(i = 0;i < G.vexnum;i++)

        cin >> G.vexs[i].name;                  //构造顶点向量

    for(i = 0;i < G.vexnum;i++)

        for(j = 0;j < G.vexnum;j++){

            G.arcs[i][j].adj = INFINITY;       //初始化邻接矩阵

            G.arcs[i][j].info = NULL;

        }

    for(k = 0;k < G.arcnum;k++){ //构造邻接矩阵

        cout << "输入一条边依附的两个顶点: ";

        cin >> v1 >> v2;

        cout << "输入这条边的权值: " << endl;

        cin >> w;

        cout << "输入这条边的信息: " << endl;

        cin >> data;

        i = LocateVex(G,v1);

        j = LocateVex(G,v2);

        G.arcs[i][j].adj = w;                  

        G.arcs[i][j].info = data;

        G.arcs[j][i] = G.arcs[i][j];

    }

    return 1;

}

Status DestroyGraph(MGraph& G){

    G.vexnum = NULL;

    G.arcnum = NULL;

    return 1;

}

char* GetVex(MGraph G,char v){

    if(G.vexnum == 0) return NULL;

    int i;

    i = LocateVex(G,v);

    if(i >= 0) //判断是否是图上的顶点，后面的函数省略了这一步

        return G.vexs[i].data;

    else 

        return NULL;

}

Status PutVex(MGraph& G,char v,char* value){

    if(G.vexnum == 0) return 0;

    int i;

    i = LocateVex(G,v);

    G.vexs[i].data = value;

    return 1;

}

//VertexType FirstAdjVex(MGraph G,char v) {}//返回第一个邻接顶点，邻接表操作

//VertexType NextAdjVex(MGraph G,char v,char w) {}          //邻接表操作

Status InsertVex(MGraph& G,char v){

    if(G.vexnum == 0) return 0;

    int i;

    G.vexs[G.vexnum].name = v;

    G.vexnum++;

    for(i = 0;i < G.vexnum;i++){

        G.arcs[i][G.vexnum - 1].adj = INFINITY;

        G.arcs[G.vexnum - 1][i].adj = INFINITY;

    }

    return 1;

}

Status DeleteVex(MGraph& G,char v){

    if(G.vexnum == 0) return 0;

    int i,j,k;

    k = LocateVex(G,v);

    for(i = 0,j = 0;i < G.vexnum;i++)

        if(G.arcs[i][k].adj != INFINITY)

            j++;

    for(i = k;i < G.vexnum - 1;i++)

        G.vexs[i] = G.vexs[i+1];

    G.vexs[i].name = NULL;

    G.vexs -> data = NULL;

    G.vexnum--;

    G.arcnum = G.arcnum - j;

    return 1;

}

Status InsertArc(MGraph& G,char v,char w){

    if(G.vexnum == 0) return 0;

    int i,j;

    VRType q;

    char data[50];

    i = LocateVex(G,v);

    j = LocateVex(G,w); 

    cout << "输入这条边的权值: " << endl;

    cin >> q;

    cout << "输入这条边的信息: " << endl;

    cin >> data;    

    G.arcs[i][j].adj = q;

    G.arcs[i][j].info = data;

    G.arcs[j][i] = G.arcs[i][j];

    G.arcnum = G.arcnum + 2;

    return 1;

}

Status DeleteArc(MGraph& G,char v,char w){

    if(G.vexnum == 0) return 0;

    int i,j;

    i = LocateVex(G,v);

    j = LocateVex(G,w);

    G.arcs[i][j].adj = INFINITY;

    G.arcs[i][j].info = NULL;

    G.arcs[j][i] = G.arcs[i][j];

    G.arcnum = G.arcnum - 2;

    return 1;

}

Status Print(MGraph G){

    int i,j;

    for(i = 0;i < G.vexnum ;i++){

        for(j = 0;j < G.vexnum ;j++)

            cout << G.arcs [i][j].adj << " ";

        cout << endl;

    }

    return 1;

}

int main()

{

    int j;

    char i,c,d;

    MGraph G;

    CreateGraph(G);

    cout << "此时矩阵为: " << endl;

    Print(G);

    cout << "输入i：:";

    cin >> i;

    j = LocateVex(G,i);

    cout << "i为第"<< j+1 << "个顶点" << endl;

    cout << "为两个点添加边，输入添加边的两个顶点: " << endl;

    cin >> c >> d;

    InsertArc(G,c,d);

    cout << "此时矩阵为: " << endl;

    Print(G);

    DeleteArc(G,c,d);

    cout << "添加顶点V；" << endl;

    cout << "此时矩阵为: " << endl;

    Print(G);

    c = 'V';

    InsertVex(G,c);

    cout << "此时矩阵为: " << endl;

    Print(G);

    cout << "删除顶点B；" << endl;

    d = 'B';

    DeleteVex(G,d);

    cout << "此时矩阵为: " << endl;

    Print(G);

    DestroyGraph(G);

    return 0;

}

运行结果：

2、

题目：2. 哈夫曼树的建立。

算法思想：(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

源程序：#include

#define MAXVALUE 100000

using namespace std;

const int n=4;//叶子节点个数 

//构造哈夫曼树结点 

typedef struct{

int weight;//权值 

int parent;//父节点 

int lchild;//左子树 

int rchild;//右子树 

}HNodeType;

HNodeType HFMTree[2*n-1];//结点数 

//构造哈夫曼编码数组

typedef struct{

int bit[n];

int start;

}HCodeType;

HCodeType HFMCode[n];

//创建哈夫曼树 

void createHFMTree(HNodeType HFMTree[],int n){

int m1,x1,m2,x2;

int i,j;

//初始化

for(i=0;i<2*n-1;i++){

   HFMTree[i].weight=0;

   HFMTree[i].parent=-1;

   HFMTree[i].lchild=-1;

   HFMTree[i].rchild=-1;

}

cout<<"请输入结点权值："<for(i=0;i cin>>HFMTree[i].weight;

}

for(i=0;i   x1=x2=MAXVALUE;

   m1=m2=0;

for(j=0;j if(HFMTree[j].parent==-1&&HFMTree[j].weight     x2=x1;

     m2=m1;

     x1=HFMTree[j].weight;

     m1=j;

    }

    else if(HFMTree[j].parent==-1&&HFMTree[j].weight     x2=HFMTree[j].weight;

     m2=j;

    }

   }

   HFMTree[m1].parent=n+i;HFMTree[m2].parent=n+i;

   HFMTree[n+i].weight=HFMTree[m1].weight+HFMTree[m2].weight;

   HFMTree[n+i].lchild=m1;

   HFMTree[n+i].rchild=m2;

}

}

//转化编码 

void createHFMCode(HNodeType HFMTree[],HCodeType HFMCode[]){

HCodeType cd;

int i,j,c,p;

for(i=0;i   cd.start=n-1;

   c=i;

   p=HFMTree[c].parent;

   while(p!=-1)

   {

    if(HFMTree[p].lchild==c)cd.bit[cd.start]=0;

    else cd.bit[cd.start]=1;

    cd.start--;

    c=p;

    p=HFMTree[c].parent;

   }

for(j=cd.start+1;j    HFMCode[i].bit[j]=cd.bit[j];

   HFMCode[i].start=cd.start+1;

}

}

//主函数 

int main()

{

int i,j;

//创建树 

createHFMTree(HFMTree,n);

//转码 

createHFMCode(HFMTree,HFMCode);

cout<for(i=0;i{

for(j=HFMCode[i].start;j<=n-1;j++)

   {

cout<   }

cout<}

return 0;

}

运行结果：