@skyword 2017-06-03T02:59:46.000000Z 字数 7048 阅读 176

# 第十一次上机报告

### 问题描述

1. 实现基本函数和测试函数，以8-17为例
2. 设计邻接表存图下的DFS,BFS函数
3. 编写删除结点的函数

### 处理思路

DFS：深度优先搜索，在每个结点，沿每条路径向内遍历并输出，没有后继结点时回溯
BFS：队列实现

### 代码设计

• typedef struct node //存储邻接表下的边
• typedef struct Adj_List_Ele//存储邻接表下的各个结点元素
• typedef struct Adj_Graph //图

main.cpp 测试主程序

### 程序代码

#ifndef ADJD_H_INCLUDED#define ADJD_H_INCLUDED#include <cstdio>#include <iostream>#include <queue>using namespace std;#define Max_V 20typedef struct node{    int head;    node* nxt;} edge; //for edge in adj_graphtypedef struct{    char val;    int start;    edge* adj;//head node of adj list for each node} Adj_List_Ele;typedef struct{    int V;    int E;    Adj_List_Ele L[Max_V];    void Adj_Graph_Init();    void Adj_Destroy();    void print();    void print_vertex(int index, int type);    void Adj_Delete_Vertex(int index);} Adj_Graph;void Adj_Graph::Adj_Graph_Init(){    this->E = 0;    this->V = 0;    for(int i = 0; i < Max_V; i++)//that is, we number vertex from 0    {        this->L[i].adj = NULL;        this->L[i].start = i;    }}void Adj_Graph::Adj_Destroy(){    edge* p,* q;    for(int i = 0; i < this->V; i++)    {        p = this->L[i].adj;        while(p != NULL)        {            q = p->nxt;            free(p);            p = q;        }    }}void Adj_Insert_Vertex(Adj_Graph* G, int index, char val)//add a vertex whose value = val, numbered index.{    if(index >= 0 && index < Max_V)    {        G->L[index].val = val;        G->V ++;    }    else printf("Add vertex failed. Its index should between 0 ~ %d.\n",Max_V-1);}void Adj_Insert_Edge(Adj_Graph* G, int s, int t)//add an edge from s to t{    if(s < 0 || t < 0 || s >= G->V || t >= G->V)    {        printf("Add edge failed. The index of these two vertex should between 0 ~ %d.\n",(G->V)-1);        return;    }    edge* p;    p = (edge*)malloc(sizeof(edge));    p->head = t;    p->nxt = G->L[s].adj;    G->L[s].adj = p;    G->E ++;}void Adj_Delete_Edge(Adj_Graph* G, int s, int t, int type)//delete edge from s to t//Here, type is operation type; type = 0 means using this function manually, type = 1 means using this function by other functions{    if(s < 0 || t < 0 || s >= G->V || t >= G->V)    {        printf("Delete edge failed. The index of these two vertex should between 0 ~ %d.\n",(G->V)-1);        return;    }    edge* pre, *now;    pre = NULL;    now = G->L[s].adj;    while(now != NULL && now->head != t)    {        pre = now;        now = now->nxt;    }    if(now != NULL && pre == NULL && now->head == t)//pre is null means t is the first link-node of v1    {        G->L[s].adj = now->nxt;        free(now);        G->E --;    }    else if(now != NULL && now->head == t)//we find t, but t is not the first link-node of v1    {        pre->nxt = now->nxt;//jump off "now"        free(now);        G->E --;    }    else    {        if(type == 0)printf("There isn't an edge from %d to %d, though graph G has these two vertexes in it.\n",s,t);    }}int Adj_GetFirst(Adj_Graph* G, int index)//get the first node of v{    if(index < 0 || index >= G->V)printf("The index should between 0 and %d.\n",(G->V)-1);    edge* p;    p = G->L[index].adj;    if(p == NULL)return -1;    else return p->head;}int Adj_GetSecond(Adj_Graph* G, int index1, int index2){    if(index1 < 0 || index1 >= G->V || index2 < 0 || index2 >= G->V)    {        printf("The index should between 0 and %d.\n",(G->V)-1);        return 0;    }    edge* p;    p = G->L[index1].adj;    while(p->head != NULL)    {        if(p->head != index2)        {            p = p->nxt;        }        else break;    }    p = p->nxt;    if(p != NULL)return p->head;    else return -1;}void Adj_Graph::Adj_Delete_Vertex(int index)//delete single vertex in graph{    if(index < 0 || index >= this->V)    {        printf("The index should between 0 and %d.\n",(this->V)-1);        return;    }    edge* e;    e = this->L[index].adj;    while(e != NULL)    {        Adj_Delete_Edge(this, index, e->head, 1);        e = e->nxt;    }    //cout<<"****"<<endl;    for(int i = 0; i < this->V; i++)    {        if(i == index)continue;        e = this->L[i].adj;        while(e != NULL)        {            if(e->head != index)                e = e->nxt;            else            {                Adj_Delete_Edge(this, i, e->head, 1);                break;            }        }    }    this->L[index].val='#';    /*    for(int i = 0; i < this->V; i++)    {        if(i != index)continue;        //now i == index        else        {            for(int j = i+1; j < this->V; j++)            {                this->L[j-1] = this->L[j];                //int now = this->L[j-1].adj->nxt->head;                //printf("****%c ",this->L[now].val);            }            break;        }    }    */    //this->V--;}void Adj_Graph::print()//print graph by order following: print each link-node for each node ordered by index{    for(int i = 0; i < this->V; i++)    {        if(this->L[i].val == '#')continue;        printf("Vertex #%d : %c \n",i,this->L[i].val);        printf("It's suffix vertex: ");        edge* n;        n = (edge*)malloc(sizeof(edge));        n = this->L[i].adj;        int cnt = 0;        while(n != NULL)        {            cnt++;            int now = n->head;            n = n->nxt;            printf("%c ",this->L[now].val);        }        if(cnt == 0)printf("empty.");        printf("\n");    }}void Adj_Graph::print_vertex(int index, int type)//print single vertex of graph, type = 0 means manually using, type = 1 means by other functions{    char c = this->L[index].val;    if(c == '#')return;    else printf("%c",this->L[index].val);    if(type == 0)printf("\n");    else printf(" ");}//Search by DFS and BFSvoid Adj_DFS(Adj_Graph* G, int v, int vis[]){    int nxt;    vis[v] = 1;    G->print_vertex(v, 1);    nxt = Adj_GetFirst(G, v);    while(nxt != -1)    {        if(vis[nxt] == 0) Adj_DFS(G, nxt, vis);        nxt = Adj_GetSecond(G, v, nxt);    }}void Adj_BFS(Adj_Graph* G, int v, int vis[]){    int u,w;    queue<int>q;    vis[v] = 1;    G->print_vertex(v, 1);    q.push(v);    while(!q.empty())    {        u = q.front();        q.pop();        w = Adj_GetFirst(G, u);        while(w != -1)        {            if(vis[w] == 0)            {                vis[w] = 1;                G->print_vertex(w, 1);                q.push(w);            }            w = Adj_GetSecond(G, u, w);        }    }}#endif // ADJD_H_INCLUDED

main.cpp

#include <malloc.h>#include <cstdio>#include <iostream>#include <cstring>#include "ADJD.h"using namespace std;int vis[20]={0};int main(){    Adj_Graph* G;    G = (Adj_Graph*)malloc(sizeof(Adj_Graph));    G->Adj_Graph_Init();    //Insert 6 vertexes as the graph described.    for(int i = 0; i < 6; i++)    {        char c = 'A'+i;        Adj_Insert_Vertex(G, i, c);    }    Adj_Insert_Edge(G, 5, 0); Adj_Insert_Edge(G, 4, 0); Adj_Insert_Edge(G, 0, 1);    Adj_Insert_Edge(G, 2, 1); Adj_Insert_Edge(G, 3, 2); Adj_Insert_Edge(G, 1, 3);    Adj_Insert_Edge(G, 3, 4); Adj_Insert_Edge(G, 5, 4); Adj_Insert_Edge(G, 1, 5);    Adj_Insert_Edge(G, 2, 5); Adj_Insert_Edge(G, 3, 5);    G->print();    //Illegally adding vertex    Adj_Insert_Vertex(G, 21, 'd');    //Illegally adding edge    Adj_Insert_Edge(G, 5, 9);    //Delete an edge,legally and illegally    //printf("Delete edge from 0 to 1.\n");    //Adj_Delete_Edge(G, 0, 1, 0);    //G->print();    //Adj_Delete_Edge(G, 0, 1, 0);    //Adj_Delete_Edge(G, 0, 9, 0);    //printf("**%d",Adj_GetFirst(G, 0));    printf("DFS-order of G: \n");    Adj_DFS(G, 0, vis);    printf("\n");    memset(vis, 0 , sizeof(vis));    printf("BFS-order of G: \n");    Adj_BFS(G, 0, vis);    printf("\n");    G->Adj_Delete_Vertex(0);    G->print();}

### 测试结果

Vertex #0 : AIt's suffix vertex: BVertex #1 : BIt's suffix vertex: F DVertex #2 : CIt's suffix vertex: F BVertex #3 : DIt's suffix vertex: F E CVertex #4 : EIt's suffix vertex: AVertex #5 : FIt's suffix vertex: E AAdd vertex failed. Its index should between 0 ~ 19.Add edge failed. The index of these two vertex should between 0 ~ 5.Delete edge from 0 to 1.Vertex #0 : AIt's suffix vertex: empty.Vertex #1 : BIt's suffix vertex: F DVertex #2 : CIt's suffix vertex: F BVertex #3 : DIt's suffix vertex: F E CVertex #4 : EIt's suffix vertex: AVertex #5 : FIt's suffix vertex: E AThere isn't an edge from 0 to 1, though graph G has these two vertexes in it.Delete edge failed. The index of these two vertex should between 0 ~ 5.

Vertex #0 : AIt's suffix vertex: BVertex #1 : BIt's suffix vertex: F DVertex #2 : CIt's suffix vertex: F BVertex #3 : DIt's suffix vertex: F E CVertex #4 : EIt's suffix vertex: AVertex #5 : FIt's suffix vertex: E ADFS-order of G:A B F E D CBFS-order of G:A B F D E CProcess returned 0 (0x0)   execution time : 0.034 sPress any key to continue.

Delete vertex FVertex #0 : AIt's suffix vertex: BVertex #1 : BIt's suffix vertex: DVertex #2 : CIt's suffix vertex: BVertex #3 : DIt's suffix vertex: E CVertex #4 : EIt's suffix vertex: AProcess returned 0 (0x0)   execution time : 0.022 sPress any key to continue.

• 私有
• 公开
• 删除