当前位置：文档之家› 数据结构图基本算代码

数据结构图基本算代码

————————————————————————————————作者：————————————————————————————————日期：

#include"iostream"

#include"LGraph.h"

#include"seqqueue.h"

#include"MGraph.h"

#define INFTY 1000

template

struct ENode

{

ENode()

{nextArc=NULL;}

ENode(int vertex,T weight,ENode *next)

{

adjVex=vertex;

w=weight;

nextArc=next;

}

int adjVex;

T w;

ENode* nextArc;

};

template

class ExtLGraph:public LGraph

{

public:

ExtLGraph(int mSize):LGraph(mSize){} void DFS();

void BFS();

void TopoSort(int *order);

private:

void CalInDegree(int *InDegree);

void DFS(int v,bool *visited);

void BFS(int v,bool *visited);

};

template

void ExtLGraph::DFS()

{

bool *visited=new bool[n];

for(int i=0;i

visited[i]=false;

for(i=0;i

if(!visited[i]) DFS(i,visited);

delete []visited;

}

template

void ExtLGraph::DFS(int v,bool *visited)

{

visited[v]=true;

cout<<" "<

for(ENode *t=a[v];t;t=t->nextArc)

if(!visited[t->adjVex])

DFS(t->adjVex,visited);

}

template

void ExtLGraph::BFS()

{

bool *visited=new bool[n];

for(int i=0;i

visited[i]=false;

for(i=0;i

if(!visited[i]) BFS(i,visited);

delete []visited;

}

template

void ExtLGraph::BFS(int v,bool *visited)

{

SeqQueueq(Vertices());

visited[v]=true;

cout<<" "<

q.EnQueue(v);

while(!q.IsEmpty())

{

q.Front(v);

q.DeQueue();

for(ENode *t=a[v];t;t=t->nextArc)

if(!visited[t->adjVex]){

visited[t->adjVex]=true;

cout<<" "<adjVex;

}

q.EnQueue(t->adjVex);

}

template

void ExtLGraph::CalInDegree(int *InDegree) //计算所有顶点的入度

for(int i=0;i

InDegree[i]=0;

for(i=0;i

for(ENode* p=a[i];p;p=p->nextArc)

InDegree[p->adjVex]++;

}

template

void ExtLGraph::TopoSort(int *order)

{

int *InDegree=new int[n];

int i,j,k,top=-1;

CalInDegree(InDegree);

for(i=0;i

if(!InDegree[i])

{

InDegree[i]=top;

top=i;

}

for(i=0;i

{

if(top==-1)

{

cout<<"Has cycle!"<

return;

}

else

{

j=top;

top=InDegree[top];

order[i]=j;

cout<

for(ENode* p=a[j];p;p=p->nextArc){

k=p->adjVex;

InDegree[k]--;

if(!InDegree[k]){

InDegree[k]=top;

top=k;

}

template

class ExtMGraph:public MGraph

{

public:

ExtMGraph(int mSize,const T&noedg):MGraph(mSize,noedg){} void DFS();

void BFS();

void DFS(int v);

void BFS(int v);

int Choose(int *d,bool *s);

void Dijkstra(int v,T *d,int *path);

void ShowDijkstra(int v,int flag);

void DijkstraForHomework(int v);//用于作业，该段代码与实验无关void Floyd(T **d,int **path);

void FloydForHomework(int v);//用于作业，该段代码与实验无关private:

void DFS(int v,bool *visited);

void BFS(int v,bool *visited);

};

template

void ExtMGraph::DFS(int v)

{

bool *visited=new bool[n];

for(int i=0;i

visited[i]=false;

for(i=v;i

if(!visited[i]) DFS(i,visited);

}

for(i=0;i

if(!visited[i]) DFS(i,visited);

}

delete [] visited;

}

template

void ExtMGraph::DFS()

{

bool *visited=new bool[n];

for(int i=0;i

visited[i]=false;

for(i=0;i

if(!visited[i]) DFS(i,visited);

delete []visited;

}

template

void ExtMGraph::DFS(int v,bool *visited) {

visited[v]=true;

cout<<" "<

for(int t=0;t

if(a[v][t]!=noEdge&&!visited[t])

DFS(t,visited);

}

template

void ExtMGraph::BFS(int v)

{

bool *visited=new bool[n];

for(int i=0;i

visited[i]=false;

for(i=v;i

if(!visited[i]) BFS(i,visited);

for(i=0;i

if(!visited[i]) BFS(i,visited);

delete [] visited;

}

template

void ExtMGraph::BFS()

{

bool *visited=new bool[n];

for(int i=0;i

visited[i]=false;

for(i=0;i

if(!visited[i]) BFS(i,visited);

delete []visited;

}

template

void ExtMGraph::BFS(int v,bool *visited) {

SeqQueueq(Vertices());

visited[v]=true;

cout<<" "<

q.EnQueue(v);

while(!q.IsEmpty())

{

q.Front(v);

q.DeQueue();

for(int j=0;j

if(a[v][j]!=noEdge&&visited[j]!=true)

{

cout<<" "<

visited[j]=true;

q.EnQueue(j);

}

template

int ExtMGraph::Choose(int *d,bool *s)

{

int i,minpos;

T min;

min=INFTY;

minpos=-1;

for(i=0;i

if(d[i]

{

min=d[i];

minpos=i;

}

return minpos;

}

template

void ExtMGraph::Dijkstra(int v,T *d,int *path) {

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=0;i

{

k=Choose(d,s);

if(k==-1) break; //若找不出下一个可连通的定点说明源点也无法到达别的定点，算法结束

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;

}

// showDandPath(k,n,d,path);

}

delete [] s;

}

template

void showDandPath(int newS,int n,T *d,int *path)//用于作业，该段代码与实验无关

{

cout<<"--------S: "<

for(int i=0;i

cout<<"d["<

cout<

for(i=0;i

cout<<"path["<

cout<

}

template

void ExtMGraph::DijkstraForHomework(int v)//用于作业，该段代码与实验无关

{

T *d=new T[n];

int *path=new int[n];

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;

showDandPath(0,n,d,path);

for(i=0;i

{

k=Choose(d,s);

if(k==-1) break; //若找不出下一个可连通的定点说明源点也无法到达别的定点，算法结束

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;

}

showDandPath(k,n,d,path);

}

delete []d;

delete []path;

}

template

void ExtMGraph::ShowDijkstra(int v,int flag)

{

T * dd=new T [n];

int * ppath=new int [n];

int temp;

Dijkstra(v,dd,ppath);

for(int ii=0;ii

{

cout<

if(ii==v)

cout<<"Source Point"<

else{

if(ppath[ii]==-1)

cout<<"No path exist"<

else

{

cout<

temp=ppath[ii];

while(ppath[temp]!=-1){

cout<

temp=ppath[temp];

}

if(flag==0)

cout<

else{

if(flag==1)

cout<

else

if(flag==2)

cout<

}

delete []dd;

delete []ppath;

}

template

void ExtMGraph::Floyd(T **d,int **path)

{

int i,j,k;

for(i=0;i

for(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

d[i][j]=d[i][k]+d[k][j];

path[i][j]=path[k][j];

}

template

void ExtMGraph::FloydForHomework(int v)//用于作业，该段代码与实验无关

{

//初始化

T **d=new T*[n];

int **path=new int*[n];

for(int i=0;i

{

d[i]=new T[n];

path[i]=new int[n];

}

//以下是Floyd算法，但是在“开始插入处”与“结束插入处”之间加入显示代码以写出二维树组d和path在执行算法的过程中各步的状态

int k;

for(i=0;i

for(int t=0;t

d[i][t]=a[i][t];

if(i!=t&&a[i][t]

path[i][t]=i;

else path[i][t]=-1;

}

for(k=0;k

{

//zzq

for(i=0;i

for(int t=0;t

d[i][t]=d[i][k]+d[k][t];

path[i][t]=path[k][t];

}

//开始插入处

cout<<"--------S: "<

cout<<"d"<

for(i=0;i

{

for(int j=0;j

{

cout<

}

cout<

}

cout<<"------------------------------"<

cout<<"path"<

for(i=0;i

{

for(int j=0;j

{

cout<

}

cout<

}

cout<<"------------------------------"<

//释放资源

for(i=0;i

{

delete []d[i];

delete []path[i];

}

delete []d;

delete []path;

}

void main()

{

int weight=3;

int noEdge=1000;

// Test of MGraph

/* MGraph mGraph(7,noEdge);

int matrix[7][7]={0,1,0,0,0,0,1,

0,0,0,1,1,0,0,

0,0,0,0,0,0,0,

0,0,0,0,0,1,1,

0,0,0,0,0,0,0};

for(int i=0;i<7;i++)

{

for(int j=0;j<7;j++)

cout<

}

mGraph.BuildforTest(*matrix,7,7);

mGraph.OutputforTest(cout);

mGraph.DeleteforTest();

mGraph.OutputforTest(cout);

showResultCode(mGraph.Insert(3,1,weight));

showResultCode(mGraph.Insert(6,2,weight));

mGraph.OutputforTest(cout);

showResultCode(mGraph.Remove(3,1));

// Test of LGraph and ExtLGraph

/* LGraph lGraph(7);

int matrix[7][7]={0,1,0,0,0,0,1,

0,0,0,1,1,0,0,

0,0,0,0,0,0,0,

0,0,0,0,0,1,1,

0,0,0,0,0,0,0};

for(int i=0;i<7;i++)

{

for(int j=0;j<7;j++)

cout<

}

lGraph.BuildforTest(*matrix,7,7);

lGraph.OutputforTest(cout);

lGraph.DeleteforTest();

lGraph.OutputforTest(cout);

showResultCode(lGraph.Insert(3,1,weight));

showResultCode(lGraph.Insert(6,2,weight));

lGraph.OutputforTest(cout);

// Test of DFS in ExtMGraph

ExtMGraph extMGraph(8,noEdge);

showResultCode(extMGraph.Insert(0,1,weight));

showResultCode(extMGraph.Insert(0,6,weight));

showResultCode(extMGraph.Insert(1,3,weight));

showResultCode(extMGraph.Insert(1,4,weight));

showResultCode(extMGraph.Insert(2,5,weight));

showResultCode(extMGraph.Insert(6,2,weight));

showResultCode(extMGraph.Insert(7,0,weight));

cout<<"DFS"<

extMGraph.DFS();

cout<

extMGraph.DFS(7);

cout<

extMGraph.DFS(6);

cout<

extMGraph.DFS(5);

extMGraph.DFS(4);

cout<

extMGraph.DFS(3);

cout<

extMGraph.DFS(2);

cout<

extMGraph.DFS(1);

cout<

cout<<"BFS"<

extMGraph.BFS();

cout<

extMGraph.BFS(7);

cout<

extMGraph.BFS(6);

cout<

extMGraph.BFS(5);

cout<

extMGraph.BFS(4);

cout<

extMGraph.BFS(3);

cout<

extMGraph.BFS(2);

cout<

extMGraph.BFS(1);

cout<

// Test of BFS in ExtMGraph

ExtMGraph extMGraph2(8,noEdge); showResultCode(extMGraph2.Insert(0,2,weight)); showResultCode(extMGraph2.Insert(1,3,weight)); showResultCode(extMGraph2.Insert(2,4,weight)); showResultCode(extMGraph2.Insert(3,5,weight)); showResultCode(extMGraph2.Insert(5,6,weight)); showResultCode(extMGraph2.Insert(6,7,weight)); showResultCode(extMGraph2.Insert(7,0,weight)); cout<<"BFS"<

extMGraph2.BFS();

cout<

extMGraph2.BFS(7);

cout<

extMGraph2.BFS(6);

cout<

extMGraph2.BFS(5);

extMGraph2.BFS(4);

cout<

extMGraph2.BFS(3);

cout<

extMGraph2.BFS(2);

cout<

extMGraph2.BFS(1);

cout<

cout<<"DFS"<

extMGraph2.DFS();

cout<

extMGraph2.DFS(7);

cout<

extMGraph2.DFS(6);

cout<

extMGraph2.DFS(5);

cout<

extMGraph2.DFS(4);

cout<

extMGraph2.DFS(3);

cout<

extMGraph2.DFS(2);

cout<

extMGraph2.DFS(1);

cout<

}

数据结构课程设计图的遍历和生成树求解

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 6014389 题目: 图的遍历和生成树求解实现年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日完成时间: 2012 年 12 月 26 日课程设计成绩：指导教师签名：年月日

目录摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26)

摘要《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：计算机；图；算法。

数据结构与算法基础知识总结

数据结构与算法基础知识总结 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、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理二、实验内容： 1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3、深度优先遍历第一步中构造的图G，输出得到的节点序列 4、广度优先遍历第一部中构造的图G，输出得到的节点序列三、实验要求： 1、无向图中的相关信息要从终端以正确的方式输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、程序算法作简短的文字注释。四、程序实现及结果： 1、邻接矩阵： #include #include #define VERTEX_MAX 30 #define MAXSIZE 20 typedef struct { int arcs[VERTEX_MAX][VERTEX_MAX] ; int vexnum,arcnum; } MGraph; void creat_MGraph1(MGraph *g) { int i,j,k; int n,m; printf("请输入顶点数和边数:"); scanf("%d%d",&n,&m); g->vexnum=n; g->arcnum=m; for (i=0;iarcs[i][j]=0;

基本数据结构及其运算习题

第二章基本数据结构及其运算一、单项选择题 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．设完全无向图的顶点个数为n，则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。

数据结构实验---图的储存与遍历

学号：姓名：实验日期： 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 #include #include V0 V1 V4 V3 V2 ??? ? ??? ? ????????=010000000101010 1000100010A 1 0 1 0 3 3 4

#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;in;i++) scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1])); for (i = 0;in;i++) for (j = 0;jn;j++) GA->edge[i][j] = 0; for (k = 0;ke;k++) { printf ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：",k+1); scanf ("%d,%d,%d",&i,&j,&w); GA->edge[i][j] = w; } return(GA); } void dfs(Graph *GA, int v) { int i; printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;

数据结构：图子系统

/* *题目：编写按键盘输入的数据建立图的邻接矩阵存储 * 编写图的深度优先遍历程序 * 编写图的广度优先遍历程序 * 设计一个选择式菜单形式如下： * 图子系统 * *********************************** * * 1------更新邻接矩阵* * * 2------深度优先遍历* * * 3------广度优先遍历* * * 0------ 返回* * *********************************** * 请选择菜单号（0--3）： */ #include #include #define GRAPHMAX 30 #define QUEUEMAX 30 typedef struct //图的邻接表的结构体 { char value[GRAPHMAX]; //记录图中的点值 int data[GRAPHMAX][GRAPHMAX]; //记录图中的边的关系int n, e; //记录图中的点的个数及边的个数 }pGraph; typedef struct //队列结构体 { int queueData[QUEUEMAX]; int front, rear, count; //队头，队尾，数目 }grQueue; void createCraph(pGraph *G); void DFSTraverse(pGraph *G); void BFSTraverse(pGraph *G); void DFS(pGraph *G, int i); void BFS(pGraph *G, int i); void initQueue(grQueue *Q); int queueEmpty(grQueue *Q); int queueFull(grQueue *Q); int outQueue(grQueue *Q); void inQueue(grQueue *Q, int i);

数据结构图的遍历

#include"stdlib.h" #include"stdio.h" #include"malloc.h" #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc; typedef struct arccell_hc {int adj; int*info; }arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc; typedef struct arcnode_hc {int adjvex; struct arcnode_hc *nextarc; int*info; }arcnode_hc; typedef struct vnode_hc {char data; arcnode_hc *firstarc; }vnode_hc,adjlist_hc[MAX_VERTEX_NUM]; typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc; int locatevex_hc(mgraph_hc*g,char v) {int i,k=0; for(i=0;ivexnum;i++) if(g->vexs[i]==v){k=i;i=g->vexnum;} return(k);}

(完整版)非常实用的数据结构知识点总结

数据结构知识点概括第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。

数据结构课程设计之图的遍历和生成树求解

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 2011.6.20 指导教师:

2010—2011年度第 2 学期一、需求分析 1.问题描述：图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。 2.基本功能 1) 先任意创建一个图； 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树（两个算法）的实现，求连通分量的实现 4) 要求用邻接矩阵、邻接表等多种结构存储实现 3.输入输出

输入数据类型为整型和字符型，输出为整型和字符二、概要设计 1.设计思路： a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。 b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。 c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。 d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。 e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计： ADT Queue{ 数据对象：D={a i | a i ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| a i-1 ,a i ∈D,i=1,2,3,……，n} 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 QueueEmpty(Q) 初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。 EnQueue(&Q,e) 初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q,e) 初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue