数据结构实验报告： 查找 排序 图的存储与遍历 二叉树的存储与遍历
1、建立一个单链表，并从屏幕显示单链表元素列表。
2、从键盘输入一个数，查找在以上创建的单链表中是否存在该数;如果存在，显示它的位置;如果不存在，给出相应提示。
3、在上述的单链表中的指定位置插入指定的元素 4、删除上述单链表中指定位置的元素。
源程序：头文件 #include #include typedef char ElemType; typedef int Status; #define OK 1 #define ERROR 0 typedef struct LNode{ ElemType data; LNode *next; }LNode,*LinkList; void about(){ \\\/\\\/版本信息 cout<<单链表的操作 } void showmenu(){ \\\/\\\/功能列表 cout<next; \\\/\\\/从头结点开始扫描 while(p){ \\\/\\\/顺指针向后扫描，直到p->next为NULL或i=j为止 cout<data; p=p->next; } cout<next = NULL; \\\/\\\/ 先建立一个带头结点的单链表 cout<<逆序输入 n 个数据元素，建立带头结点的单链表< 0; --i) { p = new LNode; cin>>p->data; \\\/\\\/ 输入元素值 p->next = L->next; L->next = p; \\\/\\\/ 插入 } } \\\/\\\/ L是带头结点的链表的头指针，以 e 返回第 i 个元素 Status GetElem_L(LinkList L, int i, ElemType &e) { int j; LinkList p; p = L->next; j = 1; \\\/\\\/ p指向第一个结点，j为计数器 while (p && ji ) return ERROR; \\\/\\\/ 第 i 个元素不存在 e = p->data; \\\/\\\/ 取得第 i 个元素 return OK; } \\\/\\\/ 本算法在链表中第i 个结点之前插入新的元素 e Status ListInsert_L(LinkList L, int i, ElemType e) { int j; LinkList p,s; p = L; j = 0; while (p && j < i-1) \\\/\\\/ 寻找第 i-1 个结点 if (!p || j > i-1) return ERROR; \\\/\\\/ i 大于表长或者小于1 s = new LNode; \\\/\\\/ 生成新结点 if ( s == NULL) return ERROR; s->data = e; s->next = p->next; p->next = s; \\\/\\\/ 插入 return OK; } Status ListDelete_L(LinkList L, int i, ElemType &e) {LinkList p,q; int j; p = L; j = 0; while (p->next && j < i-1) \\\/\\\/ 寻找第 i 个结点，并令 p 指向其前趋 if (!(p->next) || j > i-1) return ERROR; \\\/\\\/ 删除位置不合理 q = p->next; p->next = q->next; \\\/\\\/ 删除并释放结点 e = q->data; free(q); return OK; } #includeLinkList.h void main() {LinkList L; int n,choice,i; ElemType e; about(); cout<<请输入链表中元素的个数; cin>>n; CreateList_L(L, n); showmenu(); \\\/\\\/功能列表 cin>>choice; while(choice!=5) { \\\/\\\/输入时候退出程序 switch(choice){ case 1:PrintList(L);break; \\\/\\\/1.查看输入的全部数据 case 2:{ cout<<输入你要查找的元素的位置： ; cin>>i;GetElem_L(L, i, e); cout<<第<>i; cout<>e; ListInsert_L(L, i,e); break;} \\\/\\\/3.链表插入元素 case 4: {cout<<请输入你要删除元素的位置; cin>>i; ListDelete_L(L, i, e) ; break;} \\\/\\\/4.链表删除元素 default:cout<<输入错误,请输入-5,输入重显示功能表^_^ <>choice; } }
数据结构实验报告： 查找 排序 图的存储与遍历 二叉树的存储与遍历
1、建立一个单链表，并从屏幕显示单链表元素列表。
2、从键盘输入一个数，查找在以上创建的单链表中是否存在该数;如果存在，显示它的位置;如果不存在，给出相应提示。
3、在上述的单链表中的指定位置插入指定的元素 4、删除上述单链表中指定位置的元素。
源程序：头文件 #include #include typedef char ElemType; typedef int Status; #define OK 1 #define ERROR 0 typedef struct LNode{ ElemType data; LNode *next; }LNode,*LinkList; void about(){ \\\/\\\/版本信息 cout<<单链表的操作 } void showmenu(){ \\\/\\\/功能列表 cout<next; \\\/\\\/从头结点开始扫描 while(p){ \\\/\\\/顺指针向后扫描，直到p->next为NULL或i=j为止 cout<data; p=p->next; } cout<next = NULL; \\\/\\\/ 先建立一个带头结点的单链表 cout<<逆序输入 n 个数据元素，建立带头结点的单链表< 0; --i) { p = new LNode; cin>>p->data; \\\/\\\/ 输入元素值 p->next = L->next; L->next = p; \\\/\\\/ 插入 } } \\\/\\\/ L是带头结点的链表的头指针，以 e 返回第 i 个元素 Status GetElem_L(LinkList L, int i, ElemType &e) { int j; LinkList p; p = L->next; j = 1; \\\/\\\/ p指向第一个结点，j为计数器 while (p && ji ) return ERROR; \\\/\\\/ 第 i 个元素不存在 e = p->data; \\\/\\\/ 取得第 i 个元素 return OK; } \\\/\\\/ 本算法在链表中第i 个结点之前插入新的元素 e Status ListInsert_L(LinkList L, int i, ElemType e) { int j; LinkList p,s; p = L; j = 0; while (p && j < i-1) \\\/\\\/ 寻找第 i-1 个结点 if (!p || j > i-1) return ERROR; \\\/\\\/ i 大于表长或者小于1 s = new LNode; \\\/\\\/ 生成新结点 if ( s == NULL) return ERROR; s->data = e; s->next = p->next; p->next = s; \\\/\\\/ 插入 return OK; } Status ListDelete_L(LinkList L, int i, ElemType &e) {LinkList p,q; int j; p = L; j = 0; while (p->next && j < i-1) \\\/\\\/ 寻找第 i 个结点，并令 p 指向其前趋 if (!(p->next) || j > i-1) return ERROR; \\\/\\\/ 删除位置不合理 q = p->next; p->next = q->next; \\\/\\\/ 删除并释放结点 e = q->data; free(q); return OK; } #includeLinkList.h void main() {LinkList L; int n,choice,i; ElemType e; about(); cout<<请输入链表中元素的个数; cin>>n; CreateList_L(L, n); showmenu(); \\\/\\\/功能列表 cin>>choice; while(choice!=5) { \\\/\\\/输入时候退出程序 switch(choice){ case 1:PrintList(L);break; \\\/\\\/1.查看输入的全部数据 case 2:{ cout<<输入你要查找的元素的位置： ; cin>>i;GetElem_L(L, i, e); cout<<第<>i; cout<>e; ListInsert_L(L, i,e); break;} \\\/\\\/3.链表插入元素 case 4: {cout<<请输入你要删除元素的位置; cin>>i; ListDelete_L(L, i, e) ; break;} \\\/\\\/4.链表删除元素 default:cout<<输入错误,请输入-5,输入重显示功能表^_^ <>choice; } }
数据结构中出图的二种遍历，写出算法与思想，谢谢
BFS，广度优先搜索先遍历离起点近的，再到远的，直至全图。
先遍历所有与起点距离为1的点，再到所有距离为2的点……具体实现，需要一个队列进行辅助存储。
举个例，S为起点，S到A,B,C3个点相邻。
A又与A1,A2相邻，B与B1,B2相邻，C没有与其他点相邻。
对于遍历A发生的事情，就是“发现”了A1,A2。
但是，这是不能立即遍历A1,A2，这与BFS宗旨违背，必须先遍历B,C。
而又由于B,C肯定是比A1,A2先“发现”，这就体现了一种“先进先出”的性质，因而需要队列对为扩展的结点进行暂存BFS(){queue q;q.push(s);\\\/\\\/一开始的s点while(q非空){从q中取一元素将该元素“发现”，而又未被进过q的结点入队}}DFS，深度优先搜索先选定一条路径，对路径上的点进行遍历。
然后，从路径的尽头开始，逐步回退，在每个分支再遍历其他路径及其上面的点。
具体实现，常写作递归，故可理解为通过栈辅助存储。
还是上面的距离，DFS出来的其中一种序列是S,A,A1,A2,B,B1,B2,C。
路径S,A,A1为第一选取的路径，然后回退，逐步选取其他分支，在A选取了A2作为第二路径，以此类推。
由于这样对每个点所做的操作就是“发现”，“遍历”与“回退”，操作种类相同，故常写作递归。
。
。
DFS(int target){for(target的每个发现点){DFS(该发现点)}\\\/\\\/结束函数实际上就是回退的过程}
数据结构 图的遍历
图的遍历：#include#define INFINITY 0#define MAX_VERTEX_NUM 20typedef int VRType,InfoType;typedef char VertexType;typedef struct ArcCell{VRType adj;\\\/\\\/VrType是顶点关系类型，对无权图，用1或0表示相邻否，对有权图为权值类型 InfoType *info;}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;\\\/\\\/图的当前顶点数和弧数 }MGraph;int LocateVex(MGraph G,VertexType v){int i;for(i=0;i=G.vexnum) return -1;}int CreateUDN(MGraph &G){\\\/\\\/创建无向网 int IncInfo,i,k,j,w;VertexType v1,v2;printf(开始构造一个无向网\\\ ); printf(请输入图的顶点数 边数 弧是否包含其他信息\\\ ); scanf(%d%d%d,&G.vexnum,&G.arcnum,&IncInfo);printf(输入各顶点元素); for(i=0;i数据结构 图的遍历问题
实验报告一学号:姓名:完成日期:[题目]图的遍历一.问题描述从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。
图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的过程。
图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。
试编写一个程序，完成对图的遍历。
二.算法设计2.1设计思想1．以邻接矩阵为存储结构，实现无向图的深度优先遍历和广度优先遍历。
2．分别输出每种遍历下的结点访问序列.从图中某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
它是许多图的算法的基础。
2.1.1图的遍历介绍2.1.2基本概念图的遍历:图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。
图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的过程。
图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。
2..1.3分类按照搜索途径的不同，图的遍历可分为：深度优先遍历（Depth-FirstTraverse）和广度优先遍历（Breadth-FirstTraverse）两大类。
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。
（1）深度优先遍历(Depth-FirstTraverse)特点：
数据结构 图的深度遍历算法
实验报告一学号:姓名:完成日期:[题目]图的遍历一.问题描述从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。
图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的过程。
图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。
试编写一个程序，完成对图的遍历。
二.算法设计2.1设计思想1．以邻接矩阵为存储结构，实现无向图的深度优先遍历和广度优先遍历。
2．分别输出每种遍历下的结点访问序列.从图中某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
它是许多图的算法的基础。
2.1.1图的遍历介绍2.1.2基本概念图的遍历:图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。
图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的过程。
图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。
2..1.3分类按照搜索途径的不同，图的遍历可分为：深度优先遍历（Depth-FirstTraverse）和广度优先遍历（Breadth-FirstTraverse）两大类。
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。
（1）深度优先遍历(Depth-FirstTraverse)特点：
数据结构 图的遍历问题
实验报告一学号:姓名:完成日期:[题目]图的遍历一.问题描述从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。
图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的过程。
图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。
试编写一个程序，完成对图的遍历。
二.算法设计2.1设计思想1．以邻接矩阵为存储结构，实现无向图的深度优先遍历和广度优先遍历。
2．分别输出每种遍历下的结点访问序列.从图中某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
它是许多图的算法的基础。
2.1.1图的遍历介绍2.1.2基本概念图的遍历:图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。
图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的过程。
图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。
2..1.3分类按照搜索途径的不同，图的遍历可分为：深度优先遍历（Depth-FirstTraverse）和广度优先遍历（Breadth-FirstTraverse）两大类。
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。
（1）深度优先遍历(Depth-FirstTraverse)特点：
图的遍历 数据结构
你前面一个说的遍历全图所有的点，这个就是属于图的周游，常见算法有：(1)深度优先搜索DFS;(2)广度优先搜索。
后面一个求最短路径，就涉及到了最短路径的问题，但是一般指的是选定的两个点，而不用考虑遍历全图，常见的算法有Dijkstra和Floyd算法。
本质需要遍历所有的顶点并使得边的权重最小，这个是属于最小支撑树MST；但是这个里面不要求从每个顶点出发，然后回去。
