数据结构实验不会做啊😭

Question

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

提交格式：
邻接矩阵数据结构实现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}

Answer 1

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

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;
        }
    }
}