《2022年数据结构图的建立收集》由会员分享，可在线阅读，更多相关《2022年数据结构图的建立收集（8页珍藏版）》请在金锄头文库上搜索。
1、戴瑞贤计算机 13-5 班 20131401702 实验十图的建立实验目的：1)理解图的基本概念，掌握用邻接矩阵和邻接表的方法描述图的存储结构。实验内容：1)建立无向图的邻接矩阵，并实现插入、删除边的功能。2)建立有向图的邻接表，并实现插入、删除边的功能。1. /* MGraph.cc: 图的邻接矩阵存储表示和实现 */ /* 包含图类型Graph 定义；创建图；深度优先遍历；广度优先遍历 */ /* 用到引用型参数，在TC下无法通过编译， VC等 C+ 编译器可通过 */ #include #include #include /含 INT_MAX #define VType char /顶点
2、值类型#define EType int /边权值类型#define MAXVNUM 50 /最大顶点个数#define DIGRAPH 0 /有向图( 网) #define UNDIGRAPH 1 /无向图( 网) #define INVALID INT_MAX /无效权值( 最大整数表示无穷大) #define EMPTY -1 /空 顶点序号/ 定义邻接矩阵表示的图类型Graph: typedef struct VType vMAXVNUM; /顶点序列 (顶点编号从0 开始 ) EType wMAXVNUMMAXVNUM; /邻接矩阵 int vn, en; /顶点数, 边数 int
3、kind; /图的种类： =DIGRAPH 表示有向图 ( 网)，=UNDIGRAPH 表示无向图 ( 网) Graph; int visitedMAXVNUM; /访问标志数组(=1 已访问， =0 未访问 ) 。遍历时用到的全局量。/* 创建图 G 参数 Vex 是存放顶点序列的数组参数 VVW 是整数数组，以的形式依次存放各边的起止点序号(Vi,Vj)和权(Wij) ，-1 是数据结束标志参数kind=DIGRAPH 表示有向图 ( 网) ，=UNDIGRAPH 表示无向图 ( 网) */ void CreateGraph(Graph &G, VType *Vex, int VVW, i
4、nt kind) int i, j, p, n, w; n = strlen(Vex); G.vn = n; /顶点数 G.kind = kind; /图的种类 /置顶点序列 : for (i = 0; i n; i+) G.vi = Vexi; /初始化邻接矩阵 : for (i = 0; i n; i+) for (j = 0; j n; j+) G.wij = INVALID; /构造邻接矩阵 : p = 0; /VVW数组元素“指针” n = 0; /边计数器 while (VVWp != -1) /只要 p 未到结束位置便继续: i = VVWp; /边的起点序号 j = VVWp
5、+ 1; /边的终点序号名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - w = VVWp + 2; /边的权 G.wij = w; /置邻接矩阵的(i,j)位置元素 if (G.kind = UNDIGRAPH) /若是无向图 (网), G.wji = G.wij; /则置(i,j)的对称位置 (j,i) n+; /边计数器加1 p += 3; /p指向下一组 (Vi,Vj,Wij) /end while G.en = n; /
6、边数/CreateGraph /* 返回 G中顶点 i 的一个未曾访问过的邻接点 (序号 ) */ int NextAdjVex(Graph &G, int i) int j, a; a = EMPTY; /邻接点序号初始为 空 / 在邻接矩阵的第v 行找有效元素： for (j = 0; j G.vn; j+) if (G.wij = INVALID) /若当前元素是无效元素, continue; /则继续找。 if (!visitedj) /若当前有效元素未曾访问过, 则作为邻接点 a: a = j; break; /end if /end for return a; /NextAdjVe
7、x /* 访问顶点 i */ void visit(Graph &G, int i) printf(%c, G.vi); /visit /* 从第 i 个顶点出发深度优先遍历连通图 G */ /* 调用 DFS前可能需初始化数组visited */ void DFS(Graph &G, int i) int a; visit(G, i); /访问 i 顶点 visitedi = 1; /标注 i 顶点已访问 a = NextAdjVex(G, i); /找出一个 i的邻接点 a while (a != EMPTY) /只要 a 存在便继续 : if (visiteda = 0) /若 a 未曾
8、访问 , DFS(G, a); /则从 a 出发继续进行深度优先遍历。 a = NextAdjVex(G, i); /找出 i 的下一个邻接点a /end while /DFS /* 从第 i 个顶点出发深度优先遍历图G */ void DFSTrav(Graph &G, int i) int k; /初始化各顶点的访问标志为0( 未曾访问): for (k = 0; k G.vn; k+) visitedk = 0; DFS(G, i); /从 i 出发遍历 /若 G非连通图，执行一次DFS无法遍历所有顶点，还需用如下for 对尚未访问的顶点 DFS 。 /若 G是连通图，执行一次DFS就已
9、遍历所有顶点，此时如下for什么也不做，因所有 visited=1。 for (k = 0; k G.vn; k+) if (!visitedk) DFS(G, k); /对尚未访问的顶点DFS /DFSTrav / 显示图的邻接矩阵void ShowM(Graph &G) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - int row, col, n; n = G.vn; /顶点数 / 以表格形式输出数组： / 输出表头： p
10、rintf( ); for(col = 0; col n; col+) printf(%3d,col); printf(n); printf(-+); for(col = 0; col n; col+) printf(-); printf(n); / 输出表体 ( 矩阵元素 ) ： for(row = 0; row n; row+) printf(%3d|, row); for(col = 0; col n; col+) if (G.wrowcol = INVALID) printf(%3c, *); else printf(%3d, G.wrowcol); /end for col prin
11、tf(n); /end for row printf(n); /ShowM 2. #include struct node int data; node *next; ; class list public: list()head=NULL; void MakeEmpty(); int Length(); void Insert(int x,int i);/将 x插入到第 i 个结点（不含头结点）的之后 void Insertlist(int a,int b);/将节点 b 插入 a 之前 int Delete(int x); int Remove(int i); int Find(int x
12、); void Display(); private: node *head; ; void list:Display() node *current=head; while (current!=NULL) coutdatanext; coutnext; return n; int list:Find(int x)/在链表中查找数值为 x 的结点，成功返回1，否则返回 0 node *p=head; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - -
13、- - - - - while(p!=NULL&p-data!=x) p=p-next; if(p-data=x) return 1; else return 0; void list:Insert (int x,int i)/将 x 插入到第 i 个结点（不含头结点）的之后； node *p;/p中放第 i 个结点 node *q;/q中放 i 后的结点 node *h;/h中存要插入的结点 h=new node; h-data =x; p=head; if(p-next !=NULL) /链表不是只有一个结点或者空链表时候 int n=1; while(p-next !=NULL) n+;
14、 p=p-next ; / 得到链表的结点的个数 p=head;/使 p 重新等于链首 if(i=n)/i=n时，直接加在最后面就行了 while(p-next !=NULL) p=p-next; p-next=h; h-next =NULL; else if(i1)/先找到第i 个结点，用p存第 i 个结点，用q 存 i后的结点，用h 存要插入的结点 for(int j=1;jnext;/找到第 i 个结点，用p 存第 i 个结点 q=p-next;/q存 i 后的结点 p-next=h; h-next=q; else cout超出链表结点个数的范围 endl; else cout这个链表是
15、空链表或者结点位置在首位data=b; p=head; if(head=NULL)/空链表的时候 head=s; s-next=NULL; else if(p-data=a)/a在链首时候 s-next=p; head=s; else while(p-data!=a&p-next!=NULL)/使 p 指向结点 a,q 指向 a 之前的结点 q=p; p=p-next; if(p-data=a)/若有结点 a 时候 q-next=s; s-next=p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -
16、- - - - 第 4 页，共 8 页 - - - - - - - - - else/没有 a 的时候 p-next=s; s-next=NULL; int list:Delete(int x)/删除链表中值为 x 的结点，成功返回1，否则返回0； node *p,*q; p=head; if(p=NULL) return 0; if(p-data=x) head=p-next; delete p; return 1; else while(p-data!=x&p-next!=NULL) q=p; p=p-next; if(p-data=x) q-next =p-next; delete p;
17、 return 1; else return 0; int list:Remove(int i) node *p,*q; p=head; if(p!=NULL) int n=1; while(p-next !=NULL) n+; p=p-next ; /得到链表结点的个数 p=head; if(i=n)/i结点在结尾的时候 while(p-next!=NULL) q=p; p=p-next; q-next=NULL; delete p; return 1; else if(i1)/i结点在中间的时候 for(int j=1;jnext ;/p中放第 i 个结点 q-next=p-next; d
18、elete p; return 1; else if(i=1)/i结点在首位的时候 q=p-next; head=q; delete p; return 1; else return 0; else return 0; void main() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - list A; int data10=1,2,3,4,5,6,7,8,9,10; A.Insertlist(0,data0); for(in
19、t i=1;i10;i+) A.Insertlist(0,datai); A.Display(); menu:cout1. 遍历链表 t2.查找链表 t3.插入链表 endl; cout4.删除链表 t5.链表长度 t6.置空链表 endl; int m; do cout 请输入你想要进行的操作（选择对应操作前面的序号）：m; while(m6);/当输入的序号不在包括中，让他重新输入switch(m) case 1: A.Display (); goto menu; ;break; case 2: cout 请输入你想要找到的结点：c;/输入你想要找到的结点 if(A.Find (c)=1)
20、 cout可以找到 cendl; A.Display ();/重新显示出链表A else cout链表中不存在 cendl; A.Display ();/重新显示出链表A goto menu; ;break; case 3: cout 请选择你要插入的方式( 选择前面的序号进行选择）endl; cout1. 将特定的结点加入到特定的结点前 t2.将特定的结点加到特定的位置后 endl; int b1; do cout请输入你想要插入的方式（选择前面的序号进行选择）：b1; while(b12);/当输入的序号不在包括中，让他重新输入if(b1=1) cout 请输入你想要插入的数和想要插入的结
21、点（为此结点之前插入）：a1a2; A.Insertlist (a1,a2);/将 a1 插入到结点为a2 结点之前cout 此时链表为： endl; A.Display ();/重新显示出链表A else cout 请输入你想要插入的数和想要插入的位置（为此结点之后插入）：a1a2; A.Insert (a1,a2);/将 a1插入到结点位置为a2 的结点之后cout 此时链表为： endl; A.Display ();/重新显示出链表A goto menu; ;break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名
22、师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - case 4: cout 请选择你要删除的方式(选择前面的序号进行选择）endl; cout1.删除特定的结点t2.删除特定位置的结点endl; int b1; do cout请输入你想要插入的方式（选择前面的序号进行选择）：b1; while(b12);/当输入的序号不在包括中，让他重新输入 if(b1=1) cout请输入你想要删除的结点： a;/输入你想要删除的结点 if(A.Delete (a)=1) cout成功删除 aendl; cout删除后的链表为：endl; A.Display
23、 (); else cout此链表为： endl; A.Display ();/重新显示出链表A cout链表中不存在aendl; else cout请输入你想要删除的结点位置： b;/输入你想要删除的结点的位置 if(A.Remove(b)=1) cout成功删除第 b 个结点endl; cout删除后的链表为：endl; A.Display ();/重新显示出链表A else cout当前链表的结点个数为：A.Length ()endl; cout您输入的结点位置越界endl; goto menu; ;break; case 5: cout 这个链表的结点数为:A.Length ()end
24、l; goto menu; ;break; case 6: A.MakeEmpty (); cout 这个链表已经被置空endl; goto menu; ;break; 评论 (3)|1 sunnyfulin |六级采纳率46% 擅长： C/C+JAVA 相关 Windows数据结构及算法百度其它产品按默认排序 | 按时间排序其他 1 条回答2012-04-23 17:41121446881|六级我写了一个C语言的，只给你两个结构体和一个初始化函数：#include stdio.h #include malloc.h struct adjacentnext/邻接表项结构体 名师资料总结 - -
25、 -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - int element; int quanvalue; struct adjacentnext *next; ; struct adjacenthead/邻接表头结构体 char flag; int curvalue; int element; struct adjacenthead *previous; struct adjacentnext *son; ; / 初始化图，用邻接表实现struct
26、adjacenthead *mapinitialnize(int mapsize) struct adjacenthead *ahlists=NULL; struct adjacentnext *newnode=NULL; int i; int x,y,z; ahlists=malloc(sizeof(struct adjacenthead)*mapsize); if(ahlists=NULL) return NULL; for(i=0;ielement=y; newnode-quanvalue=z; newnode-next=ahlistsx-1.son; ahlistsx-1.son=ne
27、wnode; scanf(%d%d%d,&x,&y,&z); return ahlists;/返回邻接表头 经验和体会：图及其应用中，图的定义、基本运算如图的生成等起初理解有困难，但随着学习深入，对它的概念也逐步明朗起来。邻接矩阵、邻接表和逆邻接表掌握较好，而对十字链表和邻接多重表则较为陌生。感觉理解较为吃力的内容还有图的遍历（包括深度和广度优先遍历），最小生成树问题也是比较陌生的知识点。最短路径学习起来感觉比较轻松，而对于 C语言描述却又不大明白。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -
