商业网站开发实训心得体会范文,网站 封锁右键,重庆建站,软件外包公司有哪些一#xff1a;前言
当我们考虑用邻接表储存数据的时候#xff0c;一定会拿邻接矩阵和其进行比较。邻接矩阵在储存数量较小的数据是耗费的内存是要高于邻接表的。那么我们在做题的时候如果出现内存超限#xff0c;那就要注意了#xff0c;可以考虑换用邻接表来储存数据了
…一前言
当我们考虑用邻接表储存数据的时候一定会拿邻接矩阵和其进行比较。邻接矩阵在储存数量较小的数据是耗费的内存是要高于邻接表的。那么我们在做题的时候如果出现内存超限那就要注意了可以考虑换用邻接表来储存数据了
二相关描述
1.问题利用邻接表来储存有向图的数据
2.测试数据: 输入 5 8 1 2 5 1 3 8 1 5 3 2 5 6 2 3 2 3 4 10 3 5 4 4 5 11
输出为每个顶点和其相连边的顶点以及权值 1 5 3 3 8 2 5 2 3 2 5 6 3 5 4 4 10 4 5 11 5 输出的解释说明:1 5 3 3 8 2 5 顶点1和5相连权值为3顶点1和3相连权值为8顶点1和2相连权值为5
3.分析如何建立邻接表使其输出上述数据 1:首先指出我们采取用数组模拟指针来建立链表采用结构体数组来存储每个结点的信息 2:结构体数组中的值为{顶点下标边的权值指向下一个结点的下标} 注意指向下一个结点的下标因为我们采用的是数组来模拟指针所以我们的head 和 next 都是记录结构体的数组下标而head[i] 中的 i才是真正的顶点下标 3:模拟指针为空的状况我们采用 当 next的值为0是表示为空 4:建立链表和遍历链表请看代码
4.图示邻接表 5.示例当中的邻接表和 代码中链表插入的过程
三上码 /**1.问题利用邻接表来储存有向图的数据2.测试数据: 输入 5 81 2 51 3 81 5 32 5 62 3 23 4 103 5 44 5 11输出为每个顶点和其相连边的顶点以及权值1 5 3 3 8 2 5 2 3 2 5 63 5 4 4 104 5 115 输出的解释说明:1 5 3 3 8 2 5 顶点1和5相连权值为3顶点1和3相连权值为8顶点1和2相连权值为5 3.分析如何建立邻接表使其输出上述数据1:首先指出我们采取用数组模拟指针来建立链表采用结构体数组来存储每个结点的信息2:结构体数组中的值为{顶点下标边的权值指向下一个结点的下标} 注意指向下一个结点的下标因为我们采用的是数组来模拟指针所以我们的head 和 next都是记录结构体的数组下标而head[i] 中的 i才是真正的顶点下标3:模拟指针为空的状况我们采用 当 next的值为0是表示为空4:建立链表和遍历链表请看代码
**/#includebits/stdc.h
using namespace std;
#define max 20000struct Node{int to;//到达某个点 int val;//边的权值 int next;//指向下一个结点下标
} node[max];int head[max] {0},n,m,num 0;//head为记录结构体下标num为结构体的下标 //建立链表 这个过程类似于头插法每次插入都插入到上一个结点的前面
void add(int from,int to,int val){num; node[num].to to; node[num].val val;node[num].next head[from];//指向下一个结点的下标 head[from] num;//记录结构体数组的下标下次插入的时候指向其
} int main(){cin n m;for(int i 0; i m; i){int from,to,val;cin from to val;add(from,to,val);//add(to,from,val); 这里表示的是无向图中邻接表 } //遍历邻接表for(int i 1; i n; i){//因为顶点是从1开始的cout i ;for(int j head[i]; j ! 0; j node[j].next){ //遍历顶点为i的链表 直到结构体的下标为0 cout node[j].to node[j].val ; } cout endl;} } //5 8
//1 2 5
//1 3 8
//1 5 3
//2 5 6
//2 3 2
//3 4 10
//3 5 4
//4 5 11 四书上的例子创建邻接表有亿点麻烦
//邻接表是图的一种链式存储结构对图的每个顶点建立一个单链表单链表第一个结点存放顶点信息其余存放有关边信息。
//邻接表由表头结点表和边表组成。
// (01) LGraph是邻接表对应的结构体。
// vexnum是顶点数edgnum是边数vexs则是保存顶点信息的一维数组。// (02) VNode是邻接表顶点对应的结构体。
// data是顶点所包含的数据而first_edge是该顶点所包含链表的表头指针。// (03) ENode是邻接表顶点所包含的链表的节点对应的结构体。
// ivex是该节点所对应的顶点在vexs中的索引而next_edge是指向下一个节点的
#includestdio.h
#includestdlib.h
#define Max 100
typedef struct Graph* ptrGraph;
typedef struct Edgenode* ptrEdgenode;
typedef struct Edgenode{//边结点int adjvex;//边结点位置下标struct Edgenode* next;
}edgenode;
typedef struct Vnode{//顶点int Data;struct Edgenode* firstarc;
}vnode;
typedef struct Graph{struct Vnode AdjList[Max];int Nv;int Ne;
}graph;
int locateVex(ptrGraph G,int v){//根据v点信息找到相应坐标int i;for(i0;iG-Nv;i){if(G-AdjList[i].Datav){return i;}}return -1;
}
int CreatGraph(ptrGraph G){int i,j;int V1,V2,K1,K2;ptrEdgenode p1,p2;scanf(%d%d,G-Nv,G-Ne);//输入头结点即顶点的数据for(i0;iG-Nv;i){scanf(%d,G-AdjList[i].Data);G-AdjList[i].firstarcNULL;}//输入边的两个结点for(j0;jG-Ne;j){scanf(%d%d,V1,V2);K1locateVex(G,V1);K1locateVex(G,V2);p1(ptrEdgenode)malloc(sizeof(struct Edgenode));p1-adjvexK1;p1-nextG-AdjList[K2].firstarc;//链表前插法G-AdjList[K2].firstarcp1;p2(ptrEdgenode)malloc(sizeof(struct Edgenode));p2-adjvexK2;p2-nextG-AdjList[K1].firstarc;G-AdjList[K1].firstarcp2;}return 0;}
void output_AL(ptrGraph G) //输出
{int i;for( i0;iG-Nv;i){printf(顶点%d,G-AdjList[i].Data);ptrEdgenode pG-AdjList[i].firstarc;while(p!NULL){printf(-%d,p-adjvex); //输出下标//printf(-%c,G.AdjList[p-adjvex].data); //输出顶点元素pp-next;}printf(\n);}
}int main()
{ptrGraph G;CreatGraph(G);// output_AL(G);return 0;
}
