下载文档原格式
中原工学院《数据结构》实验报告学院：计算机学院专业：计算机科学与技术班级：计科112姓名：康岩岩学号：201100814220 指导老师：高艳霞2012-11-22实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、熟练掌握图的两种遍历算法。
二、实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。
[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。
【测试数据】由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作1、掌握图的相关概念。
2、掌握图的逻辑结构和存储结构。
3、掌握图的两种遍历算法的实现。
四、实验报告要求1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果，对程序进行分析。
【设计思路】【代码整理】#include "stdafx.h"#include <iostream>#include <malloc.h>using namespace std;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW -1#define MAX_SIZE 20typedef enum{DG,DN,UDG,UDN}Kind;typedef struct ArcNode{int adjvex; //顶点位置struct ArcNode *nextarc; //下一条弧int *info; //弧信息};typedef struct{char info[10]; //顶点信息ArcNode *fistarc; //指向第一条弧}VNode,AdjList[MAX_SIZE];typedef struct{AdjList vertices;int vexnum,arcnum; //顶点数，弧数int kind; //图的种类，此为无向图}ALGraph;//这是队列的节点，仅用于广度优先搜索typedef struct Node{int num;struct Node* next;};//队列的头和尾typedef struct{Node * front;Node *rear;}PreBit;int LocateV ex(ALGraph G,char info[]);//定位顶点的位置Status addArcNode(ALGraph &G,int adjvex); //图中加入弧Status CreatGraph(ALGraph&G);//创建图的邻接表Status DFSTraverse(ALGraph G);//深度优先搜索Status BFSTraverse(ALGraph G);//广度优先搜索Status DFS(ALGraph G,int v);//深度优先搜索中的数据读取函数，用于递归bool visited[MAX_SIZE]; // 访问标志数组//初始化队列Status init_q(PreBit&P_B){P_B.front=P_B.rear=(Node*)malloc(sizeof(Node));if(!P_B.front){exit(OVERFLOW);}P_B.front->next=NULL;}//将数据入队Status en_q(PreBit & P_B,int num){Node *p=(Node*)malloc(sizeof(Node));if(!p){exit(OVERFLOW);}p->num=num;p->next=NULL;P_B.rear->next=p;P_B.rear=p;return OK;}//出队Status de_q(PreBit & P_B){if(P_B.front==P_B.rear){return ERROR;}Node* p=P_B.front->next;P_B.front->next=p->next;if(P_B.rear==p){P_B.rear=P_B.front;}free(p);return OK;}Status CreatGraph(ALGraph&G){cout<<"请输入顶点数目和弧数目"<<endl;cin>>G.vexnum>>G.arcnum;//依次输入顶点信息for(int i=0;i<G.vexnum;i++){cout<<"请输入顶点名称"<<endl;cin>>G.vertices[i].info;G.vertices[i].fistarc=NULL;}//依次输入弧信息for(int k=1;k<=G.arcnum;k++){char v1[10],v2[10]; //用于表示顶点名称的字符数组int i,j; //表示两个顶点的位置BACK: //返回点cout<<"请输入第"<<k<<"条弧的两个顶点"<<endl;cin>>v1>>v2;i=LocateV ex(G,v1); //得到顶点v1的位置j=LocateV ex(G,v2); //得到顶点v2的位置if(i==-1||j==-1){ //头信息不存在则返回重输cout<<"不存在该节点!"<<endl;goto BACK; //跳到BACK 返回点}addArcNode(G,i); //将弧的顶点信息插入表中addArcNode(G,j);}return OK;}//倒序插入弧的顶点信息Status addArcNode(ALGraph &G,int adjvex){ArcNode *p; //弧节点指针p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=adjvex;p->nextarc=G.vertices[adjvex].fistarc;//指向头结点的第一条弧G.vertices[adjvex].fistarc=p; //头结点的第一条弧指向p，即将p作为头结点的第一条弧return OK;}//定位顶点的位置int LocateV ex(ALGraph G,char info[]){for(int i=0;i<G.vexnum;i++){if(strcmp(G.vertices[i].info,info)==0){ //头结点名称与传入的信息相等，证明该头节点存在return i; //此时返回位置}}return -1;}//深度优先搜索Status DFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int i;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;i=LocateV ex(G,v1);if(i==-1){cout<<"不存在该节点!"<<endl;goto BACK;}DFS(G,i);return OK;}//深度优先搜索递归访问图Status DFS(ALGraph G,int v){visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息ArcNode *p;p=G.vertices[v].fistarc; //向头节点第一条while(p) //当弧存在{if(!visited[p->adjvex]){DFS(G,p->adjvex); //递归读取}p=p->nextarc;}return OK;}//广度优先搜索Status BFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int v;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;v=LocateV ex(G,v1);if(v==-1){cout<<"不存在该节点!"<<endl;goto BACK;}PreBit P_B;init_q(P_B);ArcNode *p;visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息en_q(P_B,v); //将头位置v入队while(P_B.front!=P_B.rear){//当队列不为空时，对其进行访问int w=P_B.front->next->num;//读出顶点位置de_q(P_B);//顶点已经访问过，将其出队列p=G.vertices[w].fistarc;//得到与顶点相关的第一条弧while(p){if(!visited[p->adjvex]){en_q(P_B,p->adjvex);//将弧入队，但不读取，只是将其放在队尾}p=p->nextarc;}}return OK;}int _tmain(int argc, _TCHAR* argv[]){ALGraph G;CreatGraph(G);cout<<"深度优先搜索图:"<<endl;DFSTraverse(G);cout<<endl;cout<<"广度优先搜索图:"<<endl;BFSTraverse(G);cout<<endl;system("pause");return 0;}。
数据结构图知识点总结高中一、线性结构1. 线性表线性表是数据结构中最基本的一种结构，它是由零个或多个数据元素构成的有限序列。
其中每个数据元素都只有一个前驱元素和一个后继元素，除了第一个和最后一个元素外，其他元素都有且仅有一个前驱和一个后继。
线性表有两种基本的存储结构，分别是顺序存储结构和链式存储结构。
顺序存储结构是利用一组地址连续的存储单元来存放线性表的数据元素，而链式存储结构是通过指针来表示数据元素之间的逻辑关系。
2. 栈栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作。
栈有一个被称为栈顶的元素，只能在栈顶进行插入和删除操作。
栈有两种经典的存储结构，分别是顺序栈和链式栈。
顺序栈是利用数组来实现栈的存储和操作，而链式栈则是利用链表来实现栈的存储和操作。
3. 队列队列也是一种特殊的线性表，它只能在表的两端进行插入和删除操作。
队列有一个被称为队头和队尾的元素，只能在队头进行删除操作，只能在队尾进行插入操作。
队列也有两种经典的存储结构，分别是顺序队列和链式队列。
顺序队列是利用数组来实现队列的存储和操作，而链式队列则是利用链表来实现队列的存储和操作。
4. 串串是线性表的一种特殊形式，它是由零个或多个字符构成的有限序列。
串的存储结构有两种常见的形式，分别是顺序存储结构和链式存储结构。
顺序存储结构是利用数组来存储串的字符序列，而链式存储结构是利用链表来存储串的字符序列。
二、非线性结构1. 树树是一种非线性结构，它是由n (n ≥ 1) 个节点组成的有限集合，这些节点之间存在着明确的层次关系。
树的存储结构通常有两种形式，分别是双亲表示法和孩子表示法。
双亲表示法通过数组来存储树的节点和节点之间的关系，而孩子表示法则通过链表来存储树的节点和节点之间的关系。
树有许多种特殊形式，如二叉树、平衡二叉树、多路查找树等。
其中，二叉树是一种特殊的树，它的每个节点最多有两个子节点，这两个子节点被称为左子树和右子树。
2. 图图是一种非线性结构，它是由一组顶点和一组边组成的数据结构。
第5章图●图的定义①图由顶点集V和边集E组成，记为G=（V，E），V(G)是图G中顶点的有穷非空集合，E(G)是图G中顶点之间变得关系集合，|V|表示顶点个数，也称图的阶，|E|表示边数（线性表和树都可以是空的，但图可以只有一个顶点没有边）②有向图：弧是顶点的有序对，记为<v,w>，v,w是顶点,v是弧尾，w是弧头，从顶点v到顶点w的弧。
无向图：边是顶点的无序对，记为(v,w)③简单图：一个图满足：不存在重复边；不存在顶点到自身的边。
多重图相对于简单图定义④完全图：无向图中，任意两顶点之间存在边，称为完全无向图。
N个顶点的无向完全图有n(n-1)/2条边。
在有向图中，任意两顶点之间存在方向相反的两条弧，称为有向完全图，N 个顶点的有向完全图有n(n-1)条边。
⑤连通图：在无向图中任意两顶点都是连通的。
无向图中的极大连通子图称为连通分量。
极大要求连通子图包含其所有的边和顶点，极小连通子图既要保持图连通，又要保持边数最少⑥在有向图中任意两顶点v,w，存在从顶点v到顶点w和从顶点w到顶点v两条路径，这种图称为强连通图。
有向图的极大强连通子图称为有向图的强连通分量。
⑦生成树：①包含图中所有顶点n，②生成树有n-1条边, ③任意两点连通。
对生成树而言，砍去一条边变成非连通图，加上一条边形成一个回路。
在非连通图中，连通分量的生成树构成了非连通图的生成森林。
⑧顶点的度：以该顶点为端点的边的数目。
无向图的全部顶点的度之和等于边数的两倍。
有向图的度等于出度和入度之和，入度是以该顶点为终点的有向边的数目，出度是以该顶点为起点的有向边的数目。
有向图的全部顶点的入度之和和出度之和相等且等于边数。
⑨图中每条边可以标上具有某种含义的数值，该数值称为边的权值。
带有权值的图称为网。
○10对于无向图G=(V, {E})，如果边(v，v’)∈E，则称顶点v，v’互为邻接点，即v，v’相邻接。
边(v，v’)依附于顶点v 和v’，或者说边(v, v’)与顶点v 和v’相关联。
数据结构的三大概念逻辑结构、存储结构和运算数据结构的三大概念：逻辑结构、存储结构和运算数据结构是计算机科学中非常重要的一个概念，它是指数据元素之间的关系以及对这些数据元素进行操作的方法。
在数据结构中，有三个核心概念，分别是逻辑结构、存储结构和运算。
这三个概念相互联系、相互作用，共同构成了数据结构的基本框架。
下面将分别对这三个概念进行详细介绍。
逻辑结构逻辑结构是指数据元素之间的逻辑关系，它独立于数据元素的存储结构。
在数据结构中，常见的逻辑结构包括线性结构、树形结构和图形结构。
1. 线性结构线性结构是最简单、最基本的逻辑结构，数据元素之间是一对一的关系。
线性结构包括线性表、栈、队列等。
其中，线性表是最为常见的线性结构，它包括顺序表和链表两种存储结构。
顺序表中的数据元素在内存中是连续存储的，而链表中的数据元素在内存中是不连续存储的，通过指针来连接各个节点。
2. 树形结构树形结构是一种重要的非线性结构，它包括二叉树、二叉搜索树、平衡二叉树等。
在树形结构中，每个节点可以有零个或多个子节点，节点之间通过边相连。
树形结构常用于表示具有层次关系的数据，如文件系统、组织结构等。
3. 图形结构图形结构是最为复杂的逻辑结构，它包括有向图和无向图。
在图形结构中，节点之间的关系是任意的，可以是一对一、一对多或多对多的关系。
图形结构常用于描述网络、社交关系等复杂系统。
存储结构存储结构是指数据结构在计算机内存中的表示方式，它决定了数据元素在内存中的存储位置以及数据元素之间的物理关系。
常见的存储结构包括顺序存储结构和链式存储结构。
1. 顺序存储结构顺序存储结构是将数据元素存储在一块连续的内存空间中，数据元素之间的物理关系与其逻辑关系一致。
顺序存储结构适合于对数据元素的随机访问，但插入和删除操作效率较低。
2. 链式存储结构链式存储结构是通过指针将数据元素存储在不连续的内存空间中，数据元素之间通过指针相连。
链式存储结构适合于频繁的插入和删除操作，但访问效率较低。
1 《数据结构》实验报告书实验内容：图的基本操作学院班级：计算机学院计算机科学与技术姓名：***学号：2011008******指导老师：高老师2前言计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。
计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。
数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。
所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。
图的基本操作实验目的1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、熟练掌握图的两种遍历算法。
实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。
[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。
以用3 户指定的结点为起点，分别输出每种遍历下的结点访问序列。
【测试数据】由学生依据软件工程的测试技术自己确定。
实验前的准备工作1、掌握图的相关概念。
2、掌握图的逻辑结构和存储结构。
3、掌握图的两种遍历算法的实现。
算法设计图的深度优先：类似树的先根遍历，初始状态所有顶点未曾被访问，则深度优先从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到，若此图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点重复上述过程直到所有的顶点都被访问。
以下2024年考研数据结构大纲供参考：
一、绪论
1. 数据结构的基本概念
2. 算法与数据结构的关系
3. 算法分析基础
二、线性表
1. 线性表的定义和基本操作
2. 线性单链表、双向链表与循环链表
3. 一维数组和广义表
三、栈和队列
1. 栈和队列的基本概念
2. 栈和队列的顺序存储及其基本操作
3. 栈和队列的链式存储及其基本操作
4. 栈和队列的应用
四、树与二叉树
1. 树的基本概念
2. 二叉树的定义及其性质
3. 二叉树的存储结构及其基本操作
4. 二叉树的遍历
5. 线索二叉树
6. 哈夫曼树及其应用
7. 平衡二叉树
8. B-树和B+树
9. 并查集
五、图
1. 图的基本概念
2. 图的存储结构及其基本操作
3. 图的遍历
4. 最小生成树(MST)
5. 最短路径问题
6. 拓扑排序
7. 关键路径
8. AOV网与拓扑排序
9. AOE网与关键路径
10. 有向无环图(DAG)及相关算法
11. 二分图匹配问题
12. 网络流问题
13. 动态规划在图论中的应用
14. 图的着色问题。
数据结构笔记基础:数据结构与算法（一）数据结构基本概念数据（data)：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称数据元素(data element）：是数据的基本单位，在计算机中通常被当做一个整体进行考虑和处理数据对象(data object）：性质相同的数据元素的集合，是数据的一个子集数据结构(data structure)：相互之间存在一种或多种特定关系的数据元素的集合4类基本结构：集合、线性结构、树形结构、图形（网状)结构数据结构的形式定义为数据结构是一个二元组Data Structure = （D,S），其中D是数据元素的有限集，S是D上关系的有限集数据结构定义中的“关系"描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构数据结构在计算机中的表示（映像)称为物理结构（存储结构）计算机中表示信息的最小单位是二进制中的一位，叫做位（bit），一到若干位组成一个位串表示一个数据元素，这个位串称为元素或结点数据结构之间关系在计算机中的表示有两种：顺序映像、非顺序映像，并由此得到两种存储结构：顺序存储、链式存储,前者运用相对位置表示数据元素间的逻辑结构，后者借助指针任何一个算法的设计取决于数据（逻辑）结构，而实现依赖于存储结构数据类型是一个值的集合和定义在这个值集上的一组操作的总称数据类型分两种:原子类型、结构类型，前者不可分解（例如int、char、float、void ），后者结构类型由若干成分按某种结构组成,可分解，成分既可以是非结构的也可以是结构的（例：数组）抽象数据类型（Abstract Data Type )：是指一个数学模型及定义在该模型上的一组操作（P8）抽象数据类型格式如下:ADT抽象数据类型名｛数据对象：<数据对象的定义>数据关系：<数据关系的定义>数据操作：〈数据操作的定义>｝ADT抽象数据类型名基本操作格式如下：基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述>多形数据类型（polymorphic data type）:是指其值得成分不确定的数据类型(P9）抽象数据类型可由固有数据类型来表示和实现（二）算法（概念）和算法分析（时、空性能）算法（algorithm）：对特定问题求解步骤的一种描述算法5特性：有穷、确定、可行、输入、输出1、有穷性:算法必须在可接受的时间内执行有穷步后结束2、确定性:每条指令必须要有确切含义，无二义性,并且只有唯一执行路径，即对相同的输入只能得相同输出3、可行性：算法中的操作都可通过已实现的基本运算执行有限次来完成4、输入：一个算法有一到多个输入，并取自某个特定对象合集5、输出：一个算法有一到多个输出，这些输出与输入有着某些特定关系的量算法设计要求(好算法）：正确性、可读性、健壮性、效率与低存储需求健壮性是指对于规范要求以外的输入能够判断出这个输入不符合规范要求，并能有合理的处理方式.算法效率的度量:（1）事后统计：程序运行结束后借助计算机内部计时功能,缺点一是必须先运行依据算法编制的程序,二是受限于计算机软硬件，导致掩盖了算法本身的优劣（2）事前分析估计：消耗时间影响因素：算法策略、问题规模、编程语言、编译程序产生的机器码质量、机器执行指令的速度撇开各种影响因素只考虑问题的规模（通常用整数量n表示），记为问题规模的函数算法时间取决于控制结构（顺序,分支，循环)和固有数据类型操作的综合效果书写格式:T（n)= O(f(n））f（n）为n的某个函数时间复杂度：算法的渐近时间复杂度(asymptotic time complexity),它表示随问题规模的增大，算法执行时间的增长率和f（n）的增长率相同以循环最深层原操作为度量基准频度：该语句重复执行的次数算法的存储空间需求：空间复杂度（space complexity）：算法所需存储空间度量，记作S（n）= O（f（n）），其中n为问题规模的大小一、线性表（一）线性表基本概念线性表（linear_list）：n个数据元素的有限序列结构特点：存在唯一的被称作“第一个”、“最后一个"的数据元素，且除了第一个以外每个元素都有唯一前驱,除最后一个以外都有唯一后继在复杂线性表中存在:数据项-〉记录-〉文件，例如每个学生情况为一个记录，它由学号、性别。
数据结构图实验报告一、实验目的本次实验的主要目的是深入理解和掌握数据结构图的基本概念、原理和操作方法，通过实际编程和操作，提高对数据结构的应用能力和解决问题的能力。
二、实验环境本次实验使用的编程语言为C+＋，开发环境为Visual Studio 2019。
三、实验内容（一）线性表1、顺序表实现顺序表的创建、插入、删除、查找等基本操作。
分析顺序表在不同操作下的时间复杂度。
2、链表实现单链表、双向链表的创建、插入、删除、查找等基本操作。
比较单链表和双向链表在操作上的优缺点。
（二）栈和队列1、栈实现顺序栈和链式栈。
用栈解决表达式求值问题。
2、队列实现顺序队列和链式队列。
用队列模拟银行排队问题。
（三）树1、二叉树实现二叉树的创建、遍历（前序、中序、后序）。
计算二叉树的深度和节点数。
2、二叉搜索树实现二叉搜索树的插入、删除、查找操作。
分析二叉搜索树的性能。
（四）图1、图的存储实现邻接矩阵和邻接表两种图的存储方式。
比较两种存储方式的优缺点。
2、图的遍历实现深度优先遍历和广度优先遍历算法。
用图的遍历解决最短路径问题。
四、实验步骤（一）线性表1、顺序表定义一个数组来存储顺序表的元素，并使用一个变量记录当前表的长度。
插入操作时，需要判断插入位置是否合法，如果合法则将插入位置后的元素依次向后移动一位，然后将新元素插入指定位置。
删除操作时，先判断删除位置是否合法，合法则将删除位置后的元素依次向前移动一位，并更新表的长度。
查找操作通过遍历数组来实现。
分析不同操作的时间复杂度，插入和删除操作在最坏情况下为O(n)，查找操作在平均情况下为 O(n/2)。
2、链表对于单链表，定义一个节点结构体，包含数据域和指向下一个节点的指针域。
通过操作指针来实现插入、删除和查找操作。
双向链表则在节点结构体中增加指向前一个节点的指针，使得操作更加灵活，但也增加了空间复杂度。
比较单链表和双向链表在插入、删除操作中指针的调整过程，得出双向链表在某些情况下更方便，但空间开销较大的结论。
存储结构常见操作方法存储结构是计算机存储数据的一种方式，常见的存储结构包括数组、链表、栈、队列和树等。
下面我将详细介绍这些存储结构的常见操作方法。
1. 数组(Array)数组是一种连续存储数据的结构，具有固定大小。
常见的操作方法包括：（1）插入操作：可以在数组中的任意位置插入一个新的元素，需要将插入位置之后的元素向后移动一位。
时间复杂度为O(n)。
（2）删除操作：可以删除数组中的任意位置的元素，需要将删除位置之后的元素向前移动一位。
时间复杂度为O(n)。
（3）查找操作：可以通过下标直接访问数组中的元素，时间复杂度为O(1)。
（4）修改操作：可以通过下标直接修改数组中的元素，时间复杂度为O(1)。
2. 链表(Linked List)链表是一种非连续存储数据的结构，由节点组成，每个节点包含数据和指向下一个节点的指针。
常见的操作方法包括：（1）插入操作：可以在链表的任意位置插入一个新的节点，需要修改前一个节点的指针，使其指向新插入的节点，同时修改新插入节点的指针，使其指向原来位置的节点。
时间复杂度为O(1)。
（2）删除操作：可以删除链表的任意位置的节点，需要修改前一个节点的指针，使其指向被删除节点的下一个节点。
时间复杂度为O(1)。
（3）查找操作：需要从链表的头节点开始遍历，直到找到目标节点或者到达链表末尾。
时间复杂度为O(n)。
（4）修改操作：需要先查找到目标节点，然后修改其数据。
时间复杂度为O(n)。
3. 栈(Stack)栈是一种先进后出的数据结构，只能在一端（栈顶）进行插入和删除操作。
常见的操作方法包括：（1）入栈操作：将一个元素压入栈顶。
时间复杂度为O(1)。
（2）出栈操作：将栈顶元素弹出。
时间复杂度为O(1)。
（3）查看栈顶元素：可以查看栈顶的元素，不改变栈的状态。
时间复杂度为O(1)。
（4）判断栈是否为空：可以判断栈是否为空。
时间复杂度为O(1)。
4. 队列(Queue)队列是一种先进先出的数据结构，可以在一端（队尾）插入元素，另一端（队头）删除元素。
第四章图4.1图的概念1．图的定义图是由一个顶点集V和一个弧集R构成的数据结构。
2.图的重要术语；（1）无向图：在一个图中，如果任意两个顶点构成的偶对（v,w）∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。
（2）有向图：在一个图中，如果任意两个顶点构成的偶对（v,w）∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。
（3）无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。
在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。
（4）有向完全图：在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。
在一个含有n个顶点的有向完全图中，有n(n-1)条边。
（5）稠密图、稀疏图：若一个图接近完全图，称为稠密图；称边数很少（e<nlogn）的图为稀疏图。
（6）顶点的度、入度、出度：顶点的度（degree）是指依附于某顶点v的边数，通常记为TD(v)。
在有向图中，要区别顶点的入度与出度的概念。
顶点v的入度是指以顶点为终点的弧的数目，记为ID(v)；顶点v出度是指以顶点v为始点的弧的数目，记为OD(v)。
TD(v)=ID(v)＋OD(v)。
（7）边的权、网图：与边有关的数据信息称为权（weight）。
在实际应用中，权值可以有某种含义。
边上带权的图称为网图或网络（network）。
如果边是有方向的带权图，则就是一个有向网图。
（8）路径、路径长度：顶点vp到顶点vq之间的路径（path）是指顶点序列vp,vi1,vi2,…,vim,vq.。
其中，（vp,vi1），(vi1,vi2)，…,(vim,.vq)分别为图中的边。
路径上边的数目称为路径长度。
（9）简单路径、简单回路：序列中顶点不重复出现的路径称为简单路径。
除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。
（10）子图：对于图G=（V，E），G’=（V’，E’），若存在V’是V的子集，E’是E的子集，则称图G’是G的一个子图。
数据结构图结构_(动态)数据结构图结构_(动态)1、概述数据结构是计算机科学中一种用于组织和存储数据的方式。
数据结构图结构是一种动态的表示方式，可以清晰地显示数据之间的依赖关系和相互作用。
本文将详细介绍数据结构图结构的各个方面，包括定义、基本概念、常见数据结构的图结构表示等。
2、定义数据结构图结构是一种以图形方式表示数据结构的方法。
它使用节点和边来表示数据元素之间的关系，使得数据之间的依赖关系和相互作用可以直观地展示出来。
数据结构图结构可以用于分析和设计各种数据结构，有助于提高程序的效率和可理解性。
3、基本概念3.1 节点（Node）：表示数据元素的基本单位，可以是一个数值、一个字符或一个对象。
3.2 边（Edge）：表示节点之间的关系，可以是有向边或无向边。
有向边表示数据元素之间的一种依赖关系，无向边表示数据元素之间的一种相互作用关系。
3.3 图（Graph）：由节点和边组成的数据结构，可以用来表示复杂的数据和逻辑关系。
3.4 有向图（Directed Graph）：所有的边都是有向边的图。
3.5 无向图（Undirected Graph）：所有的边都是无向边的图。
3.6 顶点（Vertex）：图中的节点。
3.7 权重（Weight）：边上的数值，表示两个节点之间的距离或关联程度。
3.8路径（Path）：图中从一个节点到另一个节点的边的序列。
3.9环（Cycle）：图中由若干条边连接起来的形成一个闭合回路。
4、常见数据结构的图结构表示4.1 数组（Array）数组可以用图结构表示，其中每个元素作为一个节点，相邻元素之间用边连接。
数组的图结构可以用于解决一些特定的问题，如搜索、排序等。
4.2 链表（Linked List）链表可以通过节点和指针的图结构表示，其中每个节点表示一个元素，指针连接相邻的节点。
链表的图结构可以用于优化链表的插入和删除操作。
4.3 栈（Stack）栈可以用图结构表示，其中栈顶元素作为栈顶节点，栈底元素作为栈底节点，栈中的元素通过边连接。
1.实验目的通过上机实验进一步掌握图的存储结构及基本操作的实现。
2.实验内容与要求要求：⑴能根据输入的顶点、边/弧的信息建立图；⑵实现图中顶点、边/弧的插入、删除；⑶实现对该图的深度优先遍历；⑷实现对该图的广度优先遍历。
备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。
3.数据结构设计逻辑结构：图状结构存储结构：顺序存储结构、链式存储结构4.算法设计#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAX_VERTEX_NUM 20 typedef struct ArcNode{int adjvex;struct ArcNode *nextarc; }ArcNode;typedef struct VNode{char data[2]; //顶点就设置和书上V1等等一样吧ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{AdjList vertices;int vexnum,arcnum;}ALGraph;typedef struct{int data[MAX_VERTEX_NUM+10];int front;int rear;}queue;int visited[MAX_VERTEX_NUM]; queue q;int main(){ALGraph G;int CreateUDG(ALGraph &G);int DeleteUDG(ALGraph &G);int InsertUDG(ALGraph &G);void BFSTraverse(ALGraph G, int (*Visit)(ALGraph G,ArcNode v));int PrintElement(ALGraph G,ArcNode v);void menu();void depthfirstsearch(ALGraph *g,int vi);void travel(ALGraph *g);void breadfirstsearch(ALGraph *g);int i;G.arcnum = G.vexnum = 0;while(1){menu();do{printf ( "请输入要进行的操作\n" );scanf ("%d",&i);if (i<1||i>6)printf("错误数字，请重新输入\n");}while (i<1||i>6);switch (i){case 1: CreateUDG(G);system("pause"); system("cls"); break;case 2: DeleteUDG(G); system("pause"); system("cls"); break;case 3: InsertUDG(G); system("pause"); system("cls"); break;case 4: travel(&G); system("pause"); system("cls"); break;case 5: breadfirstsearch(&G); system("pause"); system("cls"); break;case 6: exit(0); break;}}return 1;}void enterqueue(int v){q.data[q.rear]=v;q.rear++;}int deletequeue(){int t;t=q.data[q.front];q.front++;return(t);}int empty(){if(q.front==q.rear)return 1;return 0;}int LocateVex(ALGraph G,char node[2]) {int i;for(i = 0 ; i < G.vexnum ; i++){if(strcmp(G.vertices[i].data,node)= =0)return i;}return -1;}int CreateUDG(ALGraph &G){int LocateVex(ALGraph G,char node[2]);void PrintUDG(ALGraph G);int i,j,k;char node1[2],node2[2];ArcNode *p,*q;printf("请输入顶点数和弧数\n");printf("例如:5,6\n");scanf("%d,%d",&G.vexnum,&G.arc num);printf("请输入各顶点\n");for(i = 0 ; i < G.vexnum ; i++){printf("第%d个\n",i+1);scanf("%s",&G.vertices[i]);G.vertices[i].firstarc = NULL;}//这里开始构造边printf("请输入边的信息\n");printf("例如:v1 v2\n");for(i = 0 ; i < G.arcnum ; i++){printf("第%d条边\n",i+1);scanf("%s %s",&node1,&node2);j = LocateVex(G,node1);k = LocateVex(G,node2);p = (ArcNode *)malloc(sizeof(ArcNode));q = (ArcNode *)malloc(sizeof(ArcNode));p->adjvex = k;q->adjvex = j;p->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p;q->nextarc = G.vertices[k].firstarc;G.vertices[k].firstarc = q;}PrintUDG(G);return 1;}int DeleteUDG(ALGraph &G){int i,j;ArcNode *p,*q;char node[2];int LocateVex(ALGraph G,char node[2]);void PrintUDG(ALGraph G);if(G.arcnum == 0){printf("请先生成图\n");return 0;}printf("请输入要删除的节点\n");scanf("%s",&node);i = LocateVex(G,node);if(i == -1){printf("无此节点\n");return 0;}else{G.vexnum--;if((p = q = G.vertices[i].firstarc) != NULL){G.arcnum--;p = p->nextarc;G.vertices[i].firstarc = p;free(q);q = p;while(p != NULL){G.arcnum--;p = p->nextarc;G.vertices[i].firstarc = p;free(q);q = p;}}for(j = 0 ; j < G.vexnum ; j++ ){if(j >= i){strcpy(G.vertices[j].data , G.vertices[j+1].data);G.vertices[j].firstarc = G.vertices[j+1].firstarc;}if(G.vertices[j].firstarc->nextarc != NULL){p = G.vertices[j].firstarc;q = p->nextarc;if(p->adjvex == i){G.vertices[j].firstarc = q;p = q;q = q->nextarc;continue;}else if(p->adjvex > i)p->adjvex--;while(q != NULL){if(q->adjvex == i){p->nextarc = q->nextarc;free(q);q = p->nextarc;}elseif(q->adjvex > i)q->adjvex--;else{p = p->nextarc;q = q->nextarc;}}}elseif( (G.vertices[j].firstarc->nextarc == NULL) && (G.vertices[j].firstarc != NULL) )if( G.vertices[j].firstarc->adjvex == i ){G.vertices[j].firstarc = NULL;}}}PrintUDG(G);return 1;}int InsertUDG(ALGraph &G){//默认一次插入一个节点吧,不然太麻烦int i,j,k,l;char node1[2],node2[2];ArcNode *p,*q;int LocateVex(ALGraph G,char node[2]);void PrintUDG(ALGraph G);if(G.arcnum == 0){printf("请先生成图\n");return 0;}printf("请输入插入节点的名称\n");printf("WARNING:绝不可以和之前的节点重名!\n");scanf("%s",&G.vertices[G.vexnum]. data);G.vertices[G.vexnum].firstarc = NULL;printf("请输入需要插入的边的数目\n");scanf("%d",&i);G.arcnum += i;G.vexnum++;printf("请输入边的信息\n");printf("例如:v6 v2\n");printf("WARNING:一定要包含刚加入的节点名称!\n");for(j = 0 ; j < i ; j++){printf("第%d条边\n",j+1);scanf("%s %s",&node1,&node2);l = LocateVex(G,node1);k = LocateVex(G,node2);p = (ArcNode *)malloc(sizeof(ArcNode));q = (ArcNode *)malloc(sizeof(ArcNode));p->adjvex = k;q->adjvex = l;p->nextarc = G.vertices[l].firstarc;G.vertices[l].firstarc = p;q->nextarc = G.vertices[k].firstarc;G.vertices[k].firstarc = q;}PrintUDG(G);return 1;}void depthfirstsearch(ALGraph *g,int vi){ArcNode *rear;printf("%s\t",g->vertices[vi].data);visited[vi]=1;rear=g->vertices[vi].firstarc;while((rear!=NULL)&&(!visited[rear->a djvex])){depthfirstsearch(g,rear->adjvex);rear=rear->nextarc;}}void travel(ALGraph *g){int v;for(v=0;v<g->vexnum;v++)if(!visited[v])depthfirstsearch(g,v); }void breadfirstsearch(ALGraph *g) {int v,t,i;ArcNode *rear;for(i = 0 ; i <g->vexnum ; i++) visited[i] = 0;for(v=0;v<g->vexnum;v++){if(!visited[v]){printf("%s",g->vertices[v].data);visited[v]=1;enterqueue(v);}while(!empty()){t=deletequeue();rear=g->vertices[t].firstarc;while((rear!=NULL)&&(!visited[rear->a djvex])){printf("%s\t",g->vertices[rear->adjvex]. data);visited[rear->adjvex]=1;enterqueue(rear->adjvex);rear=rear->nextarc;}}}}void menu(){printf("********************************* ************\n");printf("* 作者：Dick *\n");printf("* 信计1001 xxxxxxxxxx *\n");printf("*********************MENU***** ***************\n");printf("1 建立无向图\n");printf("2 删除图中节点\n");printf("3 插入节点\n");printf("4 深度优先遍历图\n");printf("5 广度优先遍历图\n");printf("6 退出程序\n");}void PrintUDG(ALGraph G){int i;ArcNode *p;for(i = 0 ; i < G.vexnum ; i++){if(G.vertices[i].firstarc != NULL){printf("与节点%s相邻的节点为:\n",G.vertices[i].data);p = G.vertices[i].firstarc;while(p != NULL){printf("%s\t",G.vertices[p->adjvex]. data);p = p->nextarc;}printf("\n");-------------精选文档-----------------可编辑}else printf("无与节点%s 相邻的节点\n",G.vertices[i].data); }} 5. 测试结果图一：菜单项图三：插入节点图一：菜单项图二：建立图图二：建立图遍历图。
