Flavedo~Y 2021-12-08 03:20 采纳率: 66.7%
浏览 135
已结题

数据结构实验不会做啊😭

分别用邻接矩阵和邻接链表两种数据结构实现图的深度优先遍历算法,输出遍历的结点序列,并分析算法的时间复杂度。

提交格式:
邻接矩阵数据结构实现void solveA(int n, int m, int e[][2], int out[])函数。
邻接链表数据结构实现void solveB(int n, int m, int e[][2], int out[])函数。
参数n为结点个数,m为边条数,e为所有边,out为输出序列。1<=n<=3000,1<=m<=100000,0<=e[i][j]<n。
遍历的起始结点为0,邻接矩阵数据结构中按行从左到右遍历邻居结点,邻接链表数据结构中按存储顺序遍历邻居结点,图为无向图。
请不要printf输出任何内容。

输入样例:
n=5,m=10,e={{2,4},{3,0},{0,2},{3,1},{4,1},{0,1},{3,4},{2,3},{1,2},{0,4}}
输出样例:
solveA:out={0,1,2,3,4}
solveB:out={0,3,1,4,2}

  • 写回答

1条回答 默认 最新

  • 五一编程 2021-12-08 03:36
    关注

    1.采用邻接矩阵表示时,设邻接矩阵有n×n阶,矩阵包含n^2个元素。对回每个顶点来说答,搜索其所有邻接点需要搜索矩阵中对应的整个一行,因此,对整个图的遍历来说,需要搜索整个矩阵,算法的时间复杂度为O(n^2)。

    img

    2.采用邻接表表示时,若邻接表有n个结点和e条边,对每个顶点来说,搜索其所有邻接点需要搜索邻接表中对应的链表的各结点,算法的时间复杂度为O(n+e)。

    #include<stdio.h>
    #include <stdlib.h>
    #include <unistd.h> 
    #include <conio.h>
    #define TRUE 1
    #define FALSE 0
    #define MAXVER 100
    /*
    Item:
    1.实现无向图邻接矩阵的创建;设计算法输无向图邻接矩阵, 并利用邻接矩阵作为存储结构实现无向图的深度优先遍历;
    2.实现无向图邻接表的创建;设计算法输无向图邻接表,并利用邻接表作为存储结构实现无向图的广度优先遍历;
    */
    
    /*Data design*/
    /*1*/
    typedef int vertype;
    typedef struct
    {
        vertype vex[MAXVER];
        int adjmatrix[MAXVER][MAXVER];
        int n,e;
    } MapGraph;
    /*2*/
    typedef struct vernode
    {
        int adjvex;
        struct vernode * next;
    } nodetype;
    typedef struct
    {
        vertype data;
        nodetype * fnext;
    } headnode;
    typedef struct
    {
        headnode maplist[MAXVER];
        int len;
    } adjlist;
    
    
    /*Function define*/
    char Meau();    /*获得选择*/
    void Help();    /*查看说明*/
    void ChangeEndFlage();  /*修改结束标志符*/
    /*1*/
    void BuildGraph(MapGraph * map);    /*建立邻接矩阵*/
    void DeepTravers(MapGraph * map);   /*借鉴教材函数实现,深度遍历函数顶点部分*/
    void DeepTreversNext(MapGraph * map,int node);  /*深度遍历函数剩下尾部部分*/
    int visit[MAXVER]= {0}; /*记录邻接矩阵深度遍历的数组*/
    /*2*/
    void BuildGraList(adjlist * adjlistmap);    /*建立邻接表*/
    void BroadTravers(adjlist * adjlistmap);    /*广度遍历邻接表*/
    
    int endflag=-999;
    int main()
    {
        system("color f5");
        system("title PhotoMap Dev Ice2Faith");
        ChangeEndFlage();
        char sel;
        do
        {
            sel=Meau();
            system("cls");
            switch(sel)
            {
            case '1':
            {
                MapGraph * map=(MapGraph *)malloc(sizeof(MapGraph));
                BuildGraph(map);
                printf("深度遍历结果:\n>/ ");
                DeepTravers(map);
                break;
            }
            case '2':
            {
                adjlist * adjlistmap=(adjlist *)malloc(sizeof(adjlist));
                BuildGraList(adjlistmap);
                printf("广度遍历结果:\n>/ ");
                BroadTravers(adjlistmap);
                break;
            }
            case '3':
            {
                Help();
                break;
            }
            case '0':
            {
                printf("正在退出程序,请稍候. . . \n\n");
                Sleep(800);
                break;
            }
            }
            if(sel!='0')
            {
                printf("\n\n");
                system("pause");
            }
    
        }
        while(sel!='0');
    
        return 0;
    }
    
    char Meau()
    {
        system("cls");
        char sel='+';
        printf("----------------------------\n\n");
        printf("\t1.邻接矩阵\n\n");
        printf("\t2.邻接表\n\n");
        printf("\t3.帮助&说明\n\n");
        printf("\t0.退出程序\n\n");
        printf("----------------------------\n\n");
        printf(">/ ");
        do
        {
            sel=getch();
        }
        while(sel<'0'||sel>'3');
        printf("%c\n",sel);
        return sel;
    }
    void Help()
    {
        printf("--------------------------------------------------------\n\n");
        printf("\t1.设计的图均是无向图,切均是面向整数(int)进行操作\n\n");
        printf("\t2.输入顶点之间的关系时本程序不负责检验是否合法\n\n");
        printf("\t3.部分函数借鉴书本参考\n\n");
        printf("\t4.请注意输入格式要求,默认结束标记 \"-999\" && \"-999+-999\"\n\n");
        printf("\t5.结束标记可支持修改\n\n");
        printf("\t6.Dev: Ice2Faith\n\n");
        printf("--------------------------------------------------------\n\n");
    
    }
    void ChangeEndFlage()
    {
        system("cls");
        printf("您即将会输入使用的结束标志为:\"%d\"  && \"%d+%d\"\n",endflag,endflag,endflag);
        printf("需要修改请输入 1 \n>/ ");
        if(getch()=='1')
        {
            printf("请输入结束标记(int):\n>/ ");
            scanf("%d",&endflag);
            printf("结束标记符已修改为:\"%d\"  && \"%d+%d\"\n\n",endflag,endflag,endflag);
            system("pause");
        }
    }
    void BuildGraph(MapGraph * map)
    {
        for(int m=0; m<MAXVER; m++)
            for(int n=0; n<MAXVER; n++) /*清空邻接矩阵*/
                map->adjmatrix[m][n]=0;
        printf("请输入所有元素,以%d结束:\n",endflag);
        int i=0;
        int tempnum;
        do
        {
            scanf("%d",&tempnum);
            if(tempnum!=endflag)
                map->vex[i++]=tempnum;
            else
                break;
        }
        while(tempnum!=endflag);   /*读入元素*/
        map->n=i;   /*记录元素个数*/
    
        printf("请输入他们的关系,以%d+%d结束:例如11+12\n",endflag,endflag);
        int line,col;
        int j;
        int e=0;
        do
        {
            scanf("%d+%d",&line,&col);
            if(line==endflag&&col==endflag)
                break;
            for(i=0; i<map->n; i++)
            {
                if(map->vex[i]==line)
                    break;
            }
            for(j=0; j<map->n; j++)
            {
                if(map->vex[j]==col)
                    break;
            }
            map->adjmatrix[i][j]=1;
            map->adjmatrix[j][i]=1;
            e++;
        }
        while(line!=endflag&&col!=endflag);   /*读写关系到矩阵*/
        map->e=e;   /*记录边数*/
    }
    
    void DeepTravers(MapGraph * map)
    {
        for(int j=0; j<MAXVER; j++) /*清空访问数组*/
            visit[j]=0;
        for(int i=0; i<map->n; i++) /*扫描每个元素*/
        {
            if(!visit[i])   /*若元素未被访问,则访问与它临街的第一个元素*/
            {
                DeepTreversNext(map,i);
            }
        }
    
    }
    void DeepTreversNext(MapGraph * map,int node)
    {
        printf("->%d",map->vex[node]);  /*输出当前未访问并记录已访问*/
        visit[node]=1;
        for(int i=0; i<map->n; i++) /*查找对应矩阵行,找到第一个未访问进行访问,递归调用*/
        {
            if(!visit[i]&&map->adjmatrix[node][i])
            {
                DeepTreversNext(map,i);
            }
        }
    }
    
    void BuildGraList(adjlist * adjlistmap)
    {
        printf("请输入顶点,以%d结束:\n",endflag);
        int tempnum;
        int i=0;
        do
        {
            scanf("%d",&tempnum);
            if(tempnum==endflag)
                break;
            adjlistmap->maplist[i].data=tempnum; /*顶点赋值并初始化第一个指针域*/
            adjlistmap->maplist[i].fnext=NULL;
            adjlistmap->len++;
            i++;
        }
        while(tempnum!=endflag);   /*获得顶点*/
        printf("顶点间的关系,例如3+5:以%d+%d结束:\n",endflag,endflag);
        int tempnum2;
        int j;
        nodetype * exnode=NULL;
        do
        {
            scanf("%d+%d",&tempnum,&tempnum2);
            if(tempnum2==endflag&&tempnum==endflag)
                break;
            nodetype * node=(nodetype *)malloc(sizeof(nodetype));
            node->next=NULL;
            nodetype * node1=(nodetype *)malloc(sizeof(nodetype));  /*创建两个节点*/
            node1->next=NULL;
            i=0;
            while(adjlistmap->maplist[i].data!=tempnum && i<adjlistmap->len)
            {
                i++;
            }
            j=0;
            while(adjlistmap->maplist[j].data!=tempnum2 && j<adjlistmap->len)   /*获得输入顶点之间关系对应的数组的下标*/
            {
                j++;
            }
    
            exnode=adjlistmap->maplist[i].fnext;
            adjlistmap->maplist[i].fnext=node;
            node->next=exnode;
            node->adjvex=j; /*对无向图一遍进行操作*/
    
            exnode=adjlistmap->maplist[j].fnext;
            adjlistmap->maplist[j].fnext=node1;
            node1->next=exnode;
            node1->adjvex=i;    /*另一边进行操作*/
    
    
        }
        while(tempnum2!=endflag&&tempnum!=endflag);   /*读入边之间的关系*/
    
    }
    
    void BroadTravers(adjlist * adjlistmap)
    {
        int visit[MAXVER]= {0};
        for(int i=0; i<=adjlistmap->len; i++) /*初始化访问数组*/
            visit[i]=0;
    
        nodetype * tempnode=NULL;
        for(int i=0; i<adjlistmap->len; i++) /*遍历每个顶点*/
        {
            if(!visit[i])
            {
                printf("->%d",adjlistmap->maplist[i].data); /*对头指针进行遍历操作*/
                visit[i]=1;
            }
            tempnode=adjlistmap->maplist[i].fnext;
            while(tempnode) /*对此头指针之后的关系进行遍历*/
            {
                if(!visit[tempnode->adjvex])
                {
                    printf("->%d",adjlistmap->maplist[tempnode->adjvex].data);
                    visit[tempnode->adjvex]=1;
                }
    
                tempnode=tempnode->next;
            }
        }
    }
    
    
    
    

    展开全部

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
编辑
预览

报告相同问题?

问题事件

  • 系统已结题 1月2日
  • 已采纳回答 12月26日
  • 创建了问题 12月8日

悬赏问题

  • ¥15 一道以太网数据传输题
  • ¥15 python 下载群辉文件
  • ¥50 代码还没怎么运行但是需要代码功能调用数据
  • ¥15 vue请求不到数据,返回状态200,数据为html
  • ¥15 访问url时不会自动调用其 Servlet的doGet()
  • ¥15 用白鹭引擎开发棋牌游戏的前端为什么这么难找
  • ¥35 哪位专业人士知道这是什么原件吗?哪里可以买到?
  • ¥15 关于#c##的问题:treenode反序列化后获取不到上一节点和下一节点,Fullpath和Handle报错
  • ¥15 一部手机能否同时用不同的app进入不同的直播间?
  • ¥20 输入import torch显示Intel MKL FATAL ERROR,系统驱动1%,: Cannot load mkl_intel_thread.dll.
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部