数据结构A：实验--图的基本运算方法
一、实验目的和要求
1.掌握在图的邻接矩阵和邻接表存储结构实现图的基本运算的算法。学习使用图算法解决应用问题的方法。
(1). 验证教材中关于在邻接矩阵和邻接表两种不同存储结构上实现图的基本运算的算法
（2）在邻接矩阵和邻接表存储结构上实现图的深度和宽度优先遍历算法。
（3）在两种储存结构上面分别实现Dijkstra、prim、Floyd算法2. 飞机最少换乘次数问题。
二、实验环境(实验设备)
PC计算机，Windows 7操作系统，
IDE: Codeblocks 16.01
编译器: GNU GCC Compiler
、实验原理及内容
程序一：邻接矩阵表示的图的运算
本程序包含邻接矩阵表示的图的基本运算，包括插入边，移除边，判断边是否存在，深度优先遍历DFS，宽度优先遍历BFS，单源最短路Dijkstra算法，多源最短路Floyd算法，以及最小生成树prim算法。
程序定义了一个图类包含三个数据成员，分别是指向二维数据的指针T **a,记录顶点数的n和记录边数量的e。
构造函数负责申请二维数组动态空间，析构函数负责释放空间。
类的声明：
template
class MGraph
{
public:
MGraph(int mSize);
~MGraph();
bool Insert(int u,int v,int w);
bool Remove(int u,int v);
bool Exist(int u,int v)const;
void DFS();
void BFS();
void Dijkstra(int v,T *d,int *path);
void Floyd(int d[][Size],int path[][Size]);
void prim(int k,int *nearest,T* lowcost);
protected:
int Choose(int *d,bool *s);
void DFS(int v,bool *visited);
void BFS(int v,bool *visited);
T **a;
int n,e;
};
（1）深度优先遍历DFS算法
图的深度优先遍历重载了两个DFS函数，分别是面向用户的
DFS()和私有成员DFS(int v,bool *visited)。面向用户的不带参数版本，首先定义一个一位数组visited来标记当前已经访问过的结点，并初始化为false。为了防止图不是一个连通图，在外层DFS中，要通过一个循环一遍一遍的调用带参数版本的
DFS(i,visited)，如果图是一个连通图，那么在第一次调用之后，所以的visited都变成true，后续就不再调用，如果图不是一个
连通图，那么还要多次调用带参数版本DFS（i,visited）
通过这个方法，也可以用来判断图是不是一个连通图。
代码：
template
void MGraph
{
int i;
bool *visited=new bool[n];
for(i=0;i visited[i]=false; for(i=0;i { if(visited[i]==false) { DFS(i,visited); } } cout< delete []visited; } template void MGraph { visited[v]=true; printf(" %d ",v); for(int u=0;u { if(a[v][u]!=INF && visited[u]== false) { DFS(u,visited); } } } 算法分析：深度优先遍历，没嵌套调用一次，实际是对一个顶点v查看所有的邻接点，设图有n个顶点，时间复杂度是O(n^2) 空间复杂度：由于要定义一个临时数组标记访问过的顶点，所 以空间复杂度是O(n)。 （2）宽度优先遍历BFS 图的宽度优先遍历BFS重载了两个版本，一个是面向用户的不带参数版本，一个是带参数版本。不带参数版本的作用主要是为了防止图不是一个连通图，导致不能访问所有顶点，所有通过一个循环来一遍一遍调用带参数版本BFS，与DFS类似，如果图是一个连通图，那么第一次调用就能访问所有顶点，如果不是连通图，得多次调用，通过此方法也可以判断是不是连通图。 带参数版本BFS通过队列来实现宽度优先遍历，首先将第一个顶点加入队列，然后，每次从队列取出一个顶点，并将与之相邻并且还没有访问过的顶点加入到队列，直到队列为空停止。 为了代码简洁，队列使用了STL库的queue头文件。 代码： template void MGraph { int i; bool *visited=new bool[n]; for(i=0;i visited[i]=false; for(i=0;i { if(visited[i]==false) { BFS(i,visited); } } cout< delete []visited; } template void MGraph { queue visited[v]=true; Q.push(v); while(!Q.empty()) { v=Q.front(); Q.pop(); cout< for(int i=0;i { if(visited[i]==false&&a[v][i]!=INF) { visited[i]=true; Q.push(i); } } } } 算法分析：每个顶点只进入一次队列，对于每个从队列取走的点，都查看其所有的邻接点，设顶点数是n，边数是e，时间复杂度是O(n^2) 空间复杂度：同样需要定义临时数组标记访问过的顶点，队列中元素个数不超过n个，所以空间复杂度是O(n)。 （3）p rim最小生成树算法 prim算法的整体思路为，首先加入一个顶点到生成树中，然后，每次加入一条代价最小的边，边的一个顶点已被加入生成树，一个顶点未被加入生成树，然后标记这个边的顶点，表示将这个顶点也加入，加入之后更新其lowcost数组，然后继续选边，直到所有顶点都被标记。定义三个临时数组，mark数组来实现 上述标记，lowcost[j]记录与顶点j相接的边中最小的权值(边的另一个顶点未被标记)，nearest[j]表示顶点j上述最小权值边的另一个顶点。主函数打印最小生成树的边集(nearest[j],j,lowcost[j]) 代码： template void MGraph { bool *mark=new bool[n]; if(k<0||k>n-1) { printf("out of bounds\n"); return; } for(int i=0;i { nearest[i]=-1; lowcost[i]=INF; mark[i]=false; } lowcost[k]=0; nearest[k]=k; mark[k]=true; int cnt=n-1; while(cnt--) { for(int i=0;i { if(a[k][i]!=INF) { if((!mark[i])&&(lowcost[i]>a[k][i])) { lowcost[i]=a[k][i]; nearest[i]=k; } } } T minn=INF; for(int j=0;j { if((!mark[j])&&(lowcost[j] { minn=lowcost[j]; k=j; } } mark[k]=true; } } 算法分析：由于要加入n个顶点，每次加入都要找最小边和更新lowcost，所以时间复杂度是O(n^2)。 空间复杂度：定义两个一维数组，空间复杂度是O(n) （4）D ijkstra单源最短路算法 Dijkstra的整体思路是，首先加入起点到s集合中，然后更新与之相邻的顶点的数组d的值，然后每次选择不在s中并且d[j]最小的顶点，将顶点加入到s集合，并更新与这个顶点相邻的顶点d[j]的值，然后再选择不在s中并且d[j]最小的顶点，如此重复n-1次，将所有顶点都加入s中。利用s[]数组来标记是不是在集合s中，调用choose函数来选择不在s中且d最小的顶点，每次更新d的时候也要更新path数组来记录路径。 代码： template void MGraph { int i,k,w; if(v<0||v>n-1) { cout<<"out of bounds!"< return; } bool *s=new bool[n]; for(i=0;i { s[i]=false; d[i]=a[v][i]; if(i!=v&&d[i] path[i]=v; else path[i]=-1; } s[v]=true; d[v]=0; for(i=1;i { k=Choose(d,s); s[k]=true; for(w=0;w { if(!s[w]&&d[k]+a[k][w] { d[w]=d[k]+a[k][w]; path[w]=k; } } } } 算法复杂度：要加入n-1个顶点，每次加入都要调用choose函 数，choose函数时间复杂度是O(n)，综上，时间复杂度是O(n^2)。 空间复杂度：定义path数组，d数组，和s数组，都是一维数 组，空间复杂度是O(n)。 （5）F loyd多源最短路算法 Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定 的加权图中多源点之间最短路径的算法 其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}； map[i,j]表示i到j的最短距离，K是穷举i,j的断点，map[n,n] 初值应该为0，或者按照题目意思来做。 算法过程为，首先，从任意一条单边路径开始。所有两点之间 的距离是边的权，如果两点之间没有边相连，则权为无穷大。 然后，对于每一对顶点u 和v，看看是否存在一个顶点w 使 得从u 到w 再到v 比已知的路径更短。如果存在则更新它。 代码： template void MGraph { int i,j,k; for(int i=0;i { for(int j=0;j { d[i][j]=a[i][j]; if(i!=j&&a[i][j] { path[i][j]=i; } else { path[i][j]=-1; } } } for(k=0;k { for(i=0;i { for(j=0;j { if(d[i][k]+d[k][j] { d[i][j]=d[i][k]+d[k][j]; path[i][j]=path[k][j]; } } } } } 算法分析：时间复杂度是O(n^3)，用二维数组保存结果，空间复杂度是O(n^2)。 程序测试：输入课本179页下方图 结果正确 程序测试:176页上方图 结果正确。 程序二：邻接表表示的图的基本运算 本程序包含邻接表表示的图的基本运算，包括插入边，移除边，判断边是否存在，深度优先遍历DFS，宽度优先遍历BFS，单源最短路Dijkstra算法，多源最短路Floyd算法，以及最小生成树prim算法。程序定义了一个图类包含三个数据成员，分别是指向vector的数组的指针,记录顶点数的n和记录边数量的e。 构造函数负责申请n个vector数组，M[i]为一个vector数组，存放顶点i相接的边，相当于链表，为了代码的简洁，程序用STL库的vector代替了链表。析构函数负责释放空间。 Vector的元素类型为定义的结构体表示的边，边上有两个属性，分别是边的另一侧的顶点值，和边的权值。 表示边的结构体： struct edge { int to; int cost; edge(int x,int y) { to=x; cost=y; } }; 表示边的图例说明： 类的声明： template class LGraph { private: vector int n; int e; void DFS(int u,bool *vis); void BFS(int v,bool *vis); public: LGraph(int mSize); ~LGraph(); bool Insert(int u,int v,int w); bool Exist(int u,int v); bool Remove(int u,int v); void Dijkstra(int v,T *d,int *path); void prim(int k,int *nearest,T* lowcost); void Floyd(int d[][Size],int path[][Size]); void DFS(); void BFS(); }; 类的图例说明: （1）构造函数负责申请n个vector数组，用来存放邻接边代码： template LGraph { M=new vector n=mSize; e=0; } （2）插入函数Insert Insert函数首先判断插入的边是否存在，如果存在返回false， 不存在则插入边，插入的时候首先构造一个边，然后调用 vector的push_back函数插入。 代码： template bool LGraph { int i; if(u<0||u<0||v>n-1||u>n-1) return false; for(i=0;i { if(M[u][i].to==v) { return false; } } edge tmp(v,w); M[u].push_back(tmp); e++; return true; } （3）Remove移除边 移除边首先要判断参数合理性，然后搜索这条边是否存在， 如果存在移除，不存在返回false 代码：template bool LGraph { int i; if(u<0||v<0||u>n-1||v>n-1) return false; for(i=0;i { if(M[u][i].to==v) { M[u].erase(M[u].begin()+i); return true; } } return false; } （4）深度优先遍历DFS 与上面邻接矩阵的DFS类似，邻接表由于直接记录与当前 顶点相邻的顶点，所有循环的时候不需要遍历所有顶点判断 INF，循环的时间复杂度更加低。思路与邻接矩阵类似，但 是由于邻接表在插入的时候没有考虑顺序，导致每个顶点后 面接的顶点不一定按照从小到大的顺序排列，而邻接矩阵循 环是从0到n-1按照从小到大的顺序来的，所以为了保持和 邻接矩阵的一致性，在DFS的时候第一步首先将每个vector 进行排序，将vector中元素按照边的另一头顶点从小到大的 顺序排列，调用STL中的 数参数cmp cmp定义： int cmp(edge a,edge b) { return a.to } DFS代码： template void LGraph { for(int i=0;i { sort(M[i].begin(),M[i].end(),cmp); } int i; bool *vis=new bool[n+1]; for(i=0;i { vis[i]=false; } for(i=0;i { if(vis[i]==false) { DFS(i,vis); } } delete []vis; cout< } template void LGraph { vis[v]=true; printf("%d ",v); int i; for(i=0;i { int t=M[v][i].to; if(vis[t]==false) { DFS(t,vis); } } } 算法分析：深度优先遍历，没嵌套调用一次，实际是对一个 顶点v查看所有的邻接点，设图有n个顶点，时间复杂度是 O(n+e)。空间复杂度是O(n)。 （5）宽度优先遍历BFS BFS与邻接矩阵类似，重载了两个版本，一个是面向用户的不带参数版本，一个是带参数版本。不带参数版本的作用主要是为了防止图不是一个连通图，导致不能访问所有顶点，所有通过一个循环来一遍一遍调用带参数版本BFS，与DFS类似，如果图是一个连通图，那么第一次调用就能访问所有顶点，如果不是连通图，得多次调用，通过此方法也可以判断是不是连通 图。 带参数版本BFS通过队列来实现宽度优先遍历，首先将第一个顶点加入队列，然后，每次从队列取出一个顶点，并将与之相邻并且还没有访问过的顶点加入到队列，直到队列为空停止。 为了代码简洁，队列使用了STL库的queue头文件。 代码： template void LGraph { int i; bool *vi=new bool[n]; for(i=0;i { vi[i]=false; } for(i=0;i { if(vi[i]==false) { BFS(i,vi); } } cout< delete []vi; } template void LGraph { int i; vi[v]=true; queue Q.push(v); while(!Q.empty()) { v=Q.front(); printf("%d ",v); Q.pop(); for(i=0;i { int t=M[v][i].to; if(vi[t]==false) { Q.push(t); vi[t]=true; } } } } 算法分析：每个顶点只进入一次队列，对于每个从队列取走的 点，都查看其所有的邻接点，设顶点数是n，边数是e，时间复 杂度是O(n+e)。空间复杂度：队列中元素个数不超过n个，同 时需要定义数组标记已访问过的顶点，所以空间复杂度是O(n)。 （6）prim最小生成树算法 邻接表的prim算法与邻接矩阵类似，只是在循环的时候稍 有不同，要注意邻接点是edge中的to元素。算法的整体思 路为，首先加入一个顶点到生成树中，然后，每次加入一条 代价最小的边，边的一个顶点已被加入生成树，一个顶点未 被加入生成树，然后标记这个边的顶点，表示将这个顶点也 加入，加入之后更新其lowcost数组，然后继续选边，直到 所有顶点都被标记。定义三个临时数组，mark数组来实现上 述标记，lowcost[j]记录与顶点j相接的边中最小的权值(边的 另一个顶点未被标记)，nearest[j]表示顶点j上述最小权值边 的另一个顶点。主函数打印最小生成树的边集 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 第二章基本数据结构及其运算 一、单项选择题 1．数据的基本单位是( B ) A．数据B．数据元素C．数据项D．数据结构 2．在数据结构中，构成数据元素的最小单位称为（D）A．字符B．关键字C．数据元素 D．数据项 3．数据在计算机内的存储形式称为数据的（ D ）A．算法描述B．数据类型 C．逻辑结构D．物理结构 4．数据的逻辑结构可分为（C） A．顺序结构和链式结构B．简单结构和复杂结构C．线性结构和非线性结构D．动态结构和静态结构5．顺序表中的每个元素占m个字节，第一个元素的存储地址为LOC(1)，则任意1个元素i的地址为( B ) A．LOC(1)+i*m B．LOC(1)+(i-1)*m C．LCO(1)+(i+1)*m D．(i-1)*m 6．线性表若采用链表存储，其（D） A．所有结点的地址必须是连续的 B．部分结点的地址必须是连续的 C．所有结点的地址一定不连续 D．所有结点的地址连续、不连续都可以 7．线性表在采用链式存储时，其地址（ C ）A．必须是连续的B．一定是不连续的 C．连续不连续都可以D．部分是连续的 8．下列不属于线性结构的是( C )。 A．单链表B．队列 C．二叉树D．数组 9．链表不具有的特点是( A) A．可随机访问任一元素B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与线性表的长度成正比 10．数据结构反映了数据元素之间的结构关系，链表是一种( D)。 A．顺序存储线性表B．非顺序存储非线性表 C．顺序存储非线性表D．非顺序存储线性表 11．在单链表表示的线性表中，可以从( A )。 A．第一个结点访问到所有结点 B．某个结点访问到所有结点 C．某个结点访问到该结点的所有前趋结点 D．最后一个结点访问到所有结点 12．在一个单链表中，已知指针q所指向的结点是指针p所指向的结点的前驱结点，若在指针q和p所指向的两个结点之间插入指针s指向的结点，则执行( C )。 A．s->link=p->link; p->link=s; B．p->link=s->link; s->link=p; C．q->link=s; s->link=p; D．p->link=s; s->link=q; 13．长度为n的顺序存储的线性表，设在任何位置上删除一个元素的概率相等，则删除一个元素时平均要移动的元素 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 第二章地理信息系统空间数据结构 2.1 地理空间数据及其特征 【学时安排】 1 学时 【目的要求】 1、掌握地理信息系统的数据类型； 2、理解地理信息系统的数据来源； 3、掌握空间数据的特点。 【重点难点】 地理信息系统的数据类型与特征。 【教学方法与手段】 示例式教学方法，多媒体教学手段。 一、GIS空间数据的来源与类型 空间数据是GIS的核心，也有人称它是GIS的血液，因为GIS的操作对象是空间数据，因此设计和使用GIS 的第一步工作就是根据系统的功能，获取所需要的空间数据，并创建空间数据库。 1、地理数据的来源 GIS中的数据来源和数据类型繁多，概括起来主要有以下几种来源： ⑴地图数据。来源于各种类型的普通地图和专题地图，这些地图的内容丰富，图上实体间的空间关系直观，实体的类别或属性清晰，实测地形图还具有很高的精度，是地理信息的主要载体，同时也是地理信息系统最重要的信息源。 ⑵影像数据。主要来源于卫星遥感和航空遥感，包括多平台、多层面、多种传感器、多时相、多光谱、多角度和多种分辨率的遥感影像数据，构成多源海量数据，也是GIS的最有效的数据源之一。 ⑶地形数据。来源于地形等高线图的数字化，已建立的数字高程模型( DEM和其他实 测的地形数据等。 ⑷属性数据。来源于各类调查报告、实测数据、文献资料、解译信息等。 ⑸元数据。来源于由各类纯数据通过调查、推理、分析和总结得到的有关数据的数据，例如数据来源、数据权属、数据产生的时间、数据精度、数据分辨率、源数据比例尺、数据转换方法等。 2、空间数据的类型 空间数据根据表示对象的不同，又具体分为七种类型(图2-1) ，它们各表示的具体内容 如下： (1) 类型数据。例如考古地点、道路线、土壤类型的分布等。 (2) 面域数据。例如随机多边形的中心点，行政区域界线、行政单元等。 (3) 网络数据。例如道路交点、街道、街区等。 (4) 样本数据。例如气象站、航线、野外样方分布区等。 (5) 曲面数据。例如高程点、等高线、等值区域等。 (6) 文本数据。例如地名、河流名称、区域名称等。 (7) 符号数据。例如点状符号、线状符号、面状符号(晕线) 等。 2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 解： int InsList(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf("表已满无法插入！")； return(ERROR); } while(i<=L->last&&L->elem[i] } } 2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。 解： int Delete(Linklist,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) { printf("参数不合法！"); return ERROR; } else { while(p->next->data<=mink) p=p->next; q=p->next; while(q->data 实验五图的遍历及其应用实现 一、实验目的 1．熟悉图常用的存储结构。 2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。 3．会用图的遍历解决简单的实际问题。 二、实验内容 [题目一] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。 提示： 输入示例 上图的顶点和边的信息输入数据为： 5 7 DG A B C D E AB AE BC CD DA DB EC [题目二]：在图G中求一条从顶点 i 到顶点 s 的简单路径 [题目三]：寻求最佳旅游线路（ACM训练题） 在一个旅游交通网中，判断图中从某个城市A到B是否存在旅游费用在s1-s2元的旅游线路，为节省费用，不重游故地。若存在这样的旅游线路则并指出该旅游线路及其费用。 输入： 第一行：n //n-旅游城市个数 第2行：A B s1 s2 //s1,s2-金额数 第3行---第e+2行 ( 1≤e≤n(n-1)/2 ) 表示城市x,y之间的旅行费用，输入0 0 0 表示结束。 输出： 第一行表示 A到B的旅游线路景点序列 第二行表示沿此线路，从A到B的旅游费用 设计要求： 1、上机前，认真学习教材，熟练掌握图的构造和遍历算法,图的存储结 构也可使用邻接矩阵等其他结构. 2、上机前，认真独立地写出本次程序清单，流程图。图的构造和遍历算法 分别参阅讲义和参考教材事例 图的存储结构定义参考教材 相关函数声明： 1、/* 输入图的顶点和边的信息,建立图*/ void CreateGraph(MGraph &G) 2、/* 深度优先搜索遍历图*/ void DFSTraverse(Graph G, int v) 3、/*广度优先搜索遍历图 */ void BFSTraverse(Graph G, int v)4、 4、/* 其他相关函数 */…… 三、实验步骤 ㈠、数据结构与核心算法的设计描述 ㈡、函数调用及主函数设计 （可用函数的调用关系图说明） ㈢程序调试及运行结果分析 ㈣实验总结 四、主要算法流程图及程序清单 1、主要算法流程图： 2、程序清单 （程序过长，可附主要部分） 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 第2章自测卷答案姓名班级 一、填空（每空1分，共13分） 1. 【严题集 2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 2. 线性表中结点的集合是有限的，结点间的关系是一对一的。 3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 5. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 二、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分）（×）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。 例如，双向链表中的结点可以含有两个指针域，分别存放指向其 直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。 错，链表的存储结构特点是无序，而链表的示意图有序。 （×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 错，链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序 表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 实现顺序表的各种基本运算 一、实验目的 了解顺序表的结构特点及有关概念，掌握顺序表的各种基本操作算法思想及其实现。 二、实验内容 编写一个程序，实现顺序表的各种基本运算： 1、初始化顺序表； 2 、顺序表的插入； 3、顺序表的输出； 4 、求顺序表的长度 5 、判断顺序表是否为空； 6 、输出顺序表的第i位置的个元素； 7 、在顺序表中查找一个给定元素在表中的位置； 8、顺序表的删除； 9 、释放顺序表 三、算法思想与算法描述简图 主函数main 四、实验步骤与算法实现 #in clude 第二章空间数据结构和空间数据库本章概述：地理信息系统的操作对象是空间地理实体，建立一个地理信息系统的首要任务是建立空间数据库，即将反映地理实体特性的地理数据存储在计算机中，这需要解决地理数据具体以什么形式在计算机中存储和处理即空间数据结构问题和如何描述实体及其相互关系即空间数据库模型问题。本章重点介绍主要的空间数据结构和空间数据库模型。 §2.1 地理实体及其描述 介绍地理实体的概念，地理实体需要描述的内容，实体的空间特征和实体间的空间关系。 §2.2 矢量数据结构 讲述矢量数据的图形表示、获取方式和表示(即矢量编码方法)。§2.3 栅格数据结构 讲述栅格数据的图形表示、栅格数据的组织、栅格结构的建立和栅格数据的表示。 §2.4 矢量栅格一体化数据结构 针对矢量栅格数据结构互为优缺点状况，介绍集两者优点为一体的矢量栅格一体化数据结构的概念和具体数据结构设计方法。 §2.5 三维数据结构 主要阐述基于栅格的八叉树三维数据结构的基本原理和存储结构。在矢量结构方面，介绍常用的三维边界表示法的方法原理、特点和应用。§2.6 空间数据模型 首先介绍数据库有关基础知识，传统数据模型如何存储图形数据及其局限性，重点阐述面向对象技术、面向对象模型和用于地理信息系统的空间数据库管理系统的类型。 §2.7 空间数据库的设计、建立和维护 介绍空间数据库的设计的内容、建立过程和维护方法。 您可能还想看前贴【GIS原理学习（一）】【GIS原理学习（二）】【GIS 原理学习（三）】【GIS原理学习（四）】 §2.1 地理实体及其描述 地理信息系统是以地理实体作为描述、反映现实世界中空间对象的单体。在地理信息系统中需要描述地理实体的名称、位置、形状、功能等内容，这些内容反映了地理实体的时间、空间和属性三种特性，其中空 第二章习题 1. 描述以下三个概念的区别：头指针，头结点，首元素结点。 2. 填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4. 设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5. 写一算法，从顺序表中删除自第i个元素开始的k个元素。 6. 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7. 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8. 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 2007 C C C 语言的特点，简单的C 程序介绍，C 程序的上机步骤。1 、算法的概念2、简单的算法举例3、算法的特性4、算法的表示（自然语言、流程图、N-S 图表示） 1 、 C 的数据类型、常量与变星、整型数据、实型数据、字符型数据、字符串常量。2、 C 的运算符运算意义、优先级、结合方向。3、算术运算符和算术表达式，各类数值型数据间的混合运算。4、赋值运算符和赋值表达式。5、逗号运算符和逗号表达式。 1 、程序的三种基本结构。2、数据输入输出的概念及在C 语言中的实现。字符数据的输入输出，格式输入与输出。 1 、关系运算符及其优先级，关系运算和关系表达式。2、逻辑运算符及其优先级，逻辑运算符和逻辑表达式。3、if语句。if语句的三种形式，if语句的嵌套，条件运算符。4、switch 语句. 1 、while 语句。2、do/while 语句。3、for 语句。4、循环的嵌套。5、break 语句和continue 语句。1 、一维数组的定义和引用。2、二维数组的定义和引用。3、字符数组。4、字符串与字符数组。5、字符数组的输入输出。6、字符串处理函数1 、函数的定义。2、函数参数和函数的值，形式参数和实际参数。3、函数的返回值。4、函数调用的方式，函数的声明和函数原型。5、函数的嵌套调用。 6、函数的递归调用。 7、数组作为函数参数。 8、局部变量、全局变量的作用域。 9、变量的存储类别，自动变星，静态变量。1 、带参数的宏定义。2、“文件包含”处理。1 、地址和指针的概念。2、变量的指针和指向变量的指针变量。3、指针变量的定义 和引用。4、指针变量作为函数参数。5、数组的指针和指向数组的指针变量。6、指向数组元素的指针。7、通过指针引用数组元素。8、数组名作函数参数。9、二维数组与指针。 1 0、指向字符串的指针变星。字符串的指针表示形式，字符串指针作为函数参数。11 、字符指针变量和字符数组的异同。1 2、返回指针值的函数。1 3、指针数组。1 、定义结构体类型变星的方法。2、结构体变量的引用。3、结构体变量的初始化。4、结构体数组5、指向结构体类型数据的指针。6、共用体的概念，共用体变量的定义和引用，共用体类型数据的特点。typedef 1 、数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。2、数据结构的两大类逻辑结构和常用的存储表示方法。3、算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。 1 、线性表的逻辑结构特征。2、线性表上定义的基本运算。3、顺序表的特点，即顺序表如何反映线性表中元素之间的逻辑关系。4、顺序表上的插入、删除操作及其平均时间性能分析。5、链表如何表示线性表中元素之间的逻辑关系。6、链表中头指针和头结点的使用。7、单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。8、顺序表和链表的主要优缺点。9、针对线性表上所需的主要操作，选择时空性能优越的存储结构。 1 、栈的逻辑结构特点．栈与线性表的异同。2、顺序栈和链栈实现的进栈、退栈等基本算法。3、栈的空和栈满的概念及其判定条件。4、队列的逻辑结构特点，队列与线性表的异同。5、顺序队列(主要是循 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接 矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方 法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的深度优先搜索 3.图的广度优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "" #include "" #define MAXSIZE 30 typedef struct { char vertex[MAXSIZE]; ertex=i; irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int visited[MAXSIZE]; ertex); irstedge; ertex=i; irstedge=NULL; irstedge;irstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } typedef struct node { int data; struct node *next; }QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q }数据结构实验报告
数据结构与算法基础知识总结
基本数据结构及其运算习题
数据结构实验十一：图实验
数据结构实验---图的储存与遍历
地理信息系统空间数据结构
数据结构第二章课后习题题解
数据结构 图的基本操作实现
数据结构实验报告图实验
(完整版)非常实用的数据结构知识点总结
数据结构 第二章自测题答案
数据结构实验
数据结构实现顺序表的各种基本运算(20210215233821)
第二章 空间数据结构和空间数据库
数据结构课后习题及解析第二章
数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系
数据结构实验报告图实验
数据结构图实验报告
相关主题
文本预览