数据结构中图的全部操作

#include

#include

#include

#include

#include

#include

using namespace std;

#define MAX_VERTEX_NUM 100

#define INFINITY INT_MAX

#define EXTERN 10

#define OK 1

#define ERROR -1

#define MAX -1

#define MAXW 100

typedef int Status;

typedef bool VisitIf;

typedef char VertexType;//顶点数据类型

typedef int VRType; //顶点关系(表示是否相邻) typedef int InfoType; //弧相关信息

typedef enum{DG,DN,UDG,UDN} GraphKind;//图的类型bool visited[MAX_VERTEX_NUM];

//邻接矩阵

typedef struct ArcCell{VRType adj;//权值

InfoType *info;

}ArcCell,AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef

struct{VertexType vexs[MAX_VERTEX_NUM]; //顶点向量

AdjMartix arcs; //邻接矩阵

}MGraph;

bool VexExist(MGraph G,VertexType v)//判断定点是否在图中{

int i;

for(i=0;i

if(G.vexs[i]==v)

return true;

return false;}Status CreatUDN(MGraph &G) //构造无向网{int i,j,w;

char ch;

VertexType v1,v2;

Status LocateVex(MGraph G,VertexType v); //函数声明cout<<"输入顶点数,弧数：

"<

cout<<"输入顶点（字符型）：

"<

for(i=0;i

{for(j=0;j

G.arcs[i][j].info=NULL;}}

for(i=0;i

";

cin>>ch;

if(VexExist(G,ch)) //判断是否存在{cout<<"顶点输入有误！"<

"<

cin>>v1>>v2;

cout<<"输入弧的权值：

"<

cin>>w;

if((i=LocateVex(G,v1))!=-2)//

if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj=w;//对弧写入权值

G.arcs[j][i].adj=w;//对称弧赋值

k++;

continue;

};

cout<<"顶点输入错误！";}return OK;}Status LocateVex(MGraph G,VertexType v) //若图中存在v，返回v在图中的位置{for(int

i=0;i

return i;}return -2;}//对无向图求每个顶点的度，或对有向图求每个顶点的入度和出度（5分）

Status GetDegree(MGraph G,VertexType v){int i=0;

int degree=0;

i=LocateVex(G,v);////若图中存在v，返回v在图中的位置if(i!=-2)//如果存在

for(int j=0;j

if(G.arcs[i][j].adj>0) degree++;

if(i==-2){cout<<"顶点输入有误！"<

return ERROR;}return degree;}//完成插入顶点和边（或弧）的功能（5分）

Status InsertVex(MGraph &G,VertexType v) //{int k=G.vexnum;

if(G.vexnum

G.vexnum++;

for(int i=0;i

G.arcs[k][i].info=NULL;

G.arcs[i][k].adj=MAX;

G.arcs[i][k].info=NULL;}cout<<"插入成功！"<

i=LocateVex(G,v1);

j=LocateVex(G,v2);

if(i!=-2)

if(j!=-2)

{//cout<<"输入弧的权值：

";

cin>>w;

G.arcs[i][j].adj=w;

G.arcs[j][i]=G.arcs[i][j];

return OK;}cout<<"输入有误,插入失败！";

return ERROR;}//完成删除顶点和边（或弧）的功能（5分）

Status DelVex(MGraph &G,VertexType v) //{int i,j;

i=LocateVex(G,v);

if(i!=-2){for(j=0;j

G.vexs[i+j]=G.vexs[i+j+1];图中删除顶点//顶点的删除

if(i

{for(j=0;j

for(int k=0;k

G.arcs[i+j][k].info=G.arcs[i+j+1][k].info;}for(j=0;j

for(int k=0;k

G.arcs[k][i+j].info=G.arcs[k][i+j+1].info;}G.vexnum--;

return OK;}G.vexnum--;}return ERROR;}Status DelArc(MGraph &G,VertexType v1,VertexType v2) //删除弧{int i,j;

i=LocateVex(G,v1);

j=LocateVex(G,v2);

if(i!=-2)

if(j!=-2){G.arcs[i][j].adj=MAX;

G.arcs[j][i].adj=MAX;

G.arcs[i][j].info=NULL;

G.arcs[j][i].info=NULL;

cout<<"删除成功！";

return OK;}return ERROR;}void ScanAll(MGraph G)//显示图的所有信息{int i; cout<<"图中顶点信息如下：

"<

for(i=0;i

cout<

cout<<"邻接矩阵如下：

"<

cout<

(5)<<"矩阵：

";

for(i=0;i

cout<

(5)<

cout<

for(i=0;i

(6)<

for(int j=0;j

cout<

(5)<

cout<

//////////////////////////////////////////////////////////////////////////////////// ///////////

//定义图的邻接多重表结构

typedef struct Ebox{VisitIf mark; //访问标志

int ivex,jvex;//该边依附的两个顶点位置

int weight;

struct Ebox *ilink,*jlink;//分别指向依附这两个顶点的下一条边

InfoType info; //弧信息指针

}Ebox;

typedef struct VexBox//顶点定义{VertexType data;

Ebox *firstedge;//指向第一条依附该顶点的边

}VexBox;

typedef struct//图定义{VexBox vexes[MAX_VERTEX_NUM];

int vexnum,edgenum;//无向图的当前顶点数和边数}UdGraph;

//////////////////////////////////////////////////////////////////////////////////// //////////

//以邻接多重表创建无向网

Status CreatUdGraph(UdGraph &G){int i;

int m,n,w;

VertexType v1,v2;

Status UdGLocateVex(UdGraph &G,VertexType v);//声明cout<<"输入图顶点的个数和边的数目：

"<

cin>>G.vexnum>>G.edgenum;

for(i=0;i

";

cin>>G.vexes[i].data;

G.vexes[i].firstedge=NULL;}for(i=0;i

cout<<"共"<

";

cin>>v1>>v2;

cout<<"输入权值：

";

cin>>w;

if((m=UdGLocateVex(G,v1))!=-2)

if((n=UdGLocateVex(G,v2))!=-2){p=(Ebox*)malloc(sizeof(Ebox));

if(!p) return ERROR;

p->ivex=m;

p->weight=w;

p->ilink=G.vexes[m].firstedge; //插入顶点m表头

G.vexes[m].firstedge=p;

p->jlink=G.vexes[n].firstedge; //插入顶点n的表头

G.vexes[n].firstedge=p;};}return OK;}Status UdGLocateVex(UdGraph &G, VertexType v) //v在图G中的位置{for(int

i=0;i

return i;}return -2;}Status UdGInsertVex(UdGraph &G) //

{返回插入顶点if(G.vexnum

";

cin>>G.vexes[G.vexnum].data;

G.vexnum++;

G.vexes[G.vexnum-1].firstedge=NULL;

return OK;}return ERROR;}StatusUdGInsertEadge(UdGraph&G,VertexType

v2,int w) //插入边{int m,n;

m=UdGLocateVex(G,v1);

n=UdGLocateVex(G,v2);

Ebox *p;

if(m!=-2)//如果点v1存在，并返回值给m

if(n!=-2)

{v1,VertexTypep=(Ebox*)malloc(sizeof(Ebox));//申请一个结点

if(!p) return ERROR;

p->ivex=m;

p->jvex=n;

p->weight=w;

p->ilink=G.vexes[m].firstedge; //

m表头

G.vexes[m].firstedge=p;

p->jlink=G.vexes[n].firstedge; //

n的表头

G.vexes[n].firstedge=p;

return OK;

};

cout<<"边信息输入有误！";

return ERROR;}Status UdGGetDegree(UdGraph G,VertexType v) // 度数

{插入顶点返回v的int degree=0;

int i;

Ebox *p;

if((i=UdGLocateVex(G,v))==-2){cout<<"输入的顶点信息有误！"; return ERROR;}p=G.vexes[i].firstedge;

while(p){degree++;

if(p->ivex==i) p=p->ilink;

else p=p->jlink;}return degree;}Status UdGFirstVex(UdGraph G,int i) //点{返回v的第一个邻接if(i>G.vexnum||i<0){cout<<"输入的顶点有误！";

return ERROR;}if(G.vexes[i].firstedge==NULL) return -2; //接点

if(G.vexes[i].firstedge->ivex==i)

G.vexes[i].firstedge->jvex; //返回邻接点

else return G.vexes[i].firstedge->ivex;}//返回i相对于j的下一个邻接点

Status UdGNextVex(UdGraph G,int i,int j){Ebox *p;

if(i>G.vexnum||i<0||j>G.vexnum||j<0){cout<<"输入的两个顶点有误！";

return ERROR;}p=G.vexes[i].firstedge;没有邻

returnwhile(p){if(p->ivex==j){p=p->jlink;

break;}if(p->jvex==j){p=p->ilink;

break;}if(p->ivex==i) p=p->ilink;

else p=p->jlink;}if(!p) return -2; //没有邻接点

if(p->ivex==i) return p->jvex;

else return p->ivex;}//邻接多重表转换为邻接矩阵

MGraph StructTransform(UdGraph G1){int i,j;

MGraph G;

Ebox *p;

G.vexnum=G

1.vexnum;

for(i=0;i

1.vexnum;i++){G.vexs[i]=G

1.vexes[i].data; //复制顶点数组}

for(i=0;i

for(i=0;i

1.vexnum;i++)

visited[i]=false; //访问标记初始化

for(i=0;i

1.vexnum;i++) //邻接矩阵赋值{p=G

1.vexes[i].firstedge;

while(p){G.arcs[p->ivex][p->jvex].adj=G.arcs[p->jvex][p->ivex].adj=p->weight; if(p->ivex==i) p=p->ilink;

else p=p->jlink;}}

return G;}//邻接矩阵转换为邻接多重表

UdGraph StructTransform(MGraph G1){int i,j;

UdGraph G;

//顶点数组的复制

G.vexnum=G

1.vexnum;

for(i=0;i

1.vexnum;i++)

G.vexes[i].data=G

1.vexs[i];

for(i=0;i

G.vexes[i].firstedge=NULL;

//根据邻接矩阵构造边

for(i=0;i

for(j=i+1;j

if(G

1.arcs[i][j].adj>0)

UdGInsertEadge(G,G.vexes[i].data,G.vexes[j].data,G

1.arcs[i][j].adj);

return G;}/********二叉树*******/

typedef struct CSNode{VertexType v;

CSNode *lchild;

CSNode *nextsibling;

} CSNode,*CSTree;

//输出图的深度优先遍历序列或广度优先遍历序列（5分）Status DFSTraverse(UdGraph G) //返回连通分量{int i;

int count=0;

void DFS(UdGraph G,int i);

for(i=0;i

visited[i]=false; //访问标志初始化cout<<"深度优先遍历结果："<

for(i=0;i

cout<

return count;}void DFS(UdGraph G,int i){int w;

visited[i]=true;

cout<

for(w=UdGFirstVex(G,i);w!=-2;w=UdGNextVex(G,i,w))if(!visited[w])

DFS(G,w);}Status ScanUdGraph(UdGraph G)//输出无向网{int i;

Ebox *p;

cout<<"图中顶点信息：

"<

for(i=0;i

cout<<"编号

"<

if(!p){cout<<"没有与该顶点相关的边";

continue;}cout<<"与顶点"<

"<

while(p){cout<ivex<<"-"<jvex<<"权值：

"<weight<

if(p->ivex==i) p=p->ilink;

else p=p->jlink;}}

return OK;}//求图的深度优先或广度优先的生成树（或生成森林）（存储结构为孩子-兄弟链表），并对生成树进行遍历（15分）

//xx优先遍历生成树

void DFSForest(UdGraph G,CSTree &T){int v;

T=NULL;

CSTree p=NULL;

CSTree q=NULL;

void DFSTreeSet(UdGraph G,int v,CSTree &T);

for(v=0;v

visited[v]=false;

for(v=0;v

if(!visited[v]){p=(CSTree)malloc(sizeof(CSNode));

if(!p){cout<<"内存分配失败";

return;}p->v=G.vexes[v].data;

p->lchild=p->nextsibling=NULL;

if(!T) T=p;

else q->nextsibling=p;

q=p;

DFSTreeSet(G,v,p);}}

void DFSTreeSet(UdGraph G,int v,CSTree &T){int w;

bool first;

visited[v]=true;

first=true;

CSTree p,q=T->lchild;

for(w=UdGFirstVex(G,v);w!=-

2;w=UdGNextVex(G,v,w))if(!visited[w]){p=(CSTree)malloc(sizeof(CSNode));

if(!p){cout<<"内存分配失败！";

return;}p->v=G.vexes[w].data;

p->lchild=p->nextsibling=NULL;

if(first){T->lchild=p;

first=false;}else{q->nextsibling=p;}q=p;

DFSTreeSet(G,w,q);}}

//xx优先遍历孩子兄弟链表

Status DFSTree(CSTree T){if(!T) return OK;

cout<v<<" ";

if(T->lchild) DFSTree(T->lchild);

if(T->nextsibling) DFSTree(T->nextsibling);

return OK;}//判断图中有没有环

bool UdGLoopJudge(UdGraph G){int VD[ MAX_VERTEX_NUM];

bool flag=false; //数组中点空标志

int i,j,m;

int count; //记录数组中为-1的数目

Ebox *p;

//VexDegree VD[MAX_VEX_NUM];

for(i=0;i

while(!flag){count=1;

for(j=0;j

if(VD[j]==1){VD[j]=-1;

m=j;

break;}if(VD[j]==-1) count++;

if(j==G.vexnum-1)

m=-1;}//cout<<"-1点：

"<

if(m==-1){if(count==G.vexnum) break;

flag=true;

break;}p=G.vexes[m].firstedge;

while(p){if(p->ivex==m){if(VD[p->jvex]<0) p=p->ilink;

else{VD[p->jvex]--;

p=p->ilink;}}

else{if(VD[p->ivex]<0) p=p->jlink;

else{VD[p->ivex]--;

p=p->jlink;}}}}

return flag;}//普利姆算法求最小生成树

void MiniSpanTree(MGraph G,VertexType u){int k;

int j,i;

int count=0,min;

struct{VertexType adjvex;

int lowcost;

}closedge[ MAX_VERTEX_NUM];

k=LocateVex(G,u);

for(j=0;j

if(j!=k){closedge[j].adjvex=u;

closedge[j].lowcost=G.arcs[k][j].adj;

};

closedge[k].lowcost=0;

count=1;

cout<<"最小生成树的各个边信息如下：

"<

while(count!=G.vexnum){min=1000;

for(i=0;i

if(closedge[i].lowcost

k=i;}}

//cout<<"花费最小边对应点：

"<

cout<

"<

//输出生成树上一条边

closedge[k].lowcost = 0; //第k顶点并入U集count++;

for (i=0; i

//修改其它顶点的最小边{if(closedge[i].lowcost==-1){closedge[i].adjvex = G.vexs[k];

closedge[i].lowcost = G.arcs[k][i].adj;continue;}if(closedge[i].lowcost==0) continue;

if (G.arcs[k][i].adj ==-1 ) continue;

if(G.arcs[k][i].adj

closedge[i].adjvex = G.vexs[k];

closedge[i].lowcost = G.arcs[k][i].adj;continue;}}}}

//

10、求顶点u到v的一条简单路径（10分）

//m到n的简单路径

char path[100];

int count1=0;

int flag=false;

int easy_way(UdGraph G,int m,int n){int i;

int DFSway(UdGraph g,int m,int n);

for(i=0;i<100;i++) //路径设为空

path[i]=' ';

count1=0;

flag=false;

for(i=0;i

DFSway(G,m,n);

if(!flag) return -1;

for(i=0;i

cout<

return 0;}int DFSway(UdGraph g,int m,int n){//从第m个顶点出发递归地深度优先遍历图G

int w;

int i=1;

visited[m]=true;

path[count1]=g.vexes[m].data;

for(w=UdGFirstVex(g,m);w>=0;w=UdGNextVex(g,m,w)){

if(!visited[w]){i++;

if(w==n)

flag=true;

count1++;

if(!flag){DFSway(g,w,n);//对未被访问的邻接顶点w递归调用

DFS}}}if(!flag){if(i==UdGGetDegree(g,g.vexes[m].data))

path[count1]=' ';

count1--;}return flag;}//求两点的简单路径

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构作业系统第七章答案

7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 实现下列函数： Status DfsReachable(ALGraph g, int i, int j); /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ 图的邻接表以及相关类型和辅助变量定义如下：Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { V ertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ { int k; ArcNode *p; visited[i]=1; for(p=g.vertices[i].firstarc;p;p=p->nextarc) { if(p) { k=p->adjvex; if(k==j)return 1; if(visited[k]!=1)

数据结构实验十一：图实验

一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 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]; //定义表头结点数组

数据结构作业电子版

1数据结构课程研究的主要内容包括（）（）（） 2一个完整的算法应该具有_____ _____ ______ ______ ______五个特性 3数据的逻辑结构可分为_____ ______两大类 4数据的逻辑结构是指而存储结构是指 5逻辑上相邻的数据元素在物理位置上也相邻是存储结构的特点之一 6为了实现随机访问线性结构应该采用存储结构 7链式存储结构的主要特点是 8算法分析主要从和这两个方面对算法进行分析 （1）数据 （2）数据元素 （3）数据类型 （4）数据结构 （5）逻辑结构 （6）存储结构 （7）线性结构 （8）非线性结构 第二章作业 一、判断题(在你认为正确的题后的括号中打√，否则打X)。 1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 二、单项选择题。 1．线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3．线性表采用链式存储时，其地址( ) 。

数据结构图习题

第七章图：习题 习题 一、选择题 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．会用图的遍历解决简单的实际问题。 二、实验内容 [题目一] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。 提示： 输入示例 上图的顶点和边的信息输入数据为： 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.边集（Edge ）：a. 有向图，有向边，弧，弧头，弧尾，权值 b. 无向图，无向边(v, w)，权值 2.顶点集（Vertices ）：a. 无向图：度(TD(v)) b. 有向图：出度(ID(v))，入度(OD(v))，度(TD(v) = ID(v) + OD(v)) 无向完全图：n 个顶点，(1)2 n n -条边 有向完全图：n 个顶点，(1)n n -条边 网：带权图 连通分量：无向图中的极大连通子图（多个），无向完全图的连通分量就是本身（一个） 强连通分量：有向图中的极大连通子图，其中i v 到j v 以及j v 到i v 都有路径 生成树：图的极小连通子图，含有图的全部n 个顶点，只有n-1条边，少一条则不能连通， 多一条则形成回路 生成森林：不完全图中的各个连通分量的生成树，构成图的生成森林 二、存储结构 顶点：可采用链表或数组存储顶点列表，一般采用链表存储 边：1. 邻接矩阵（数组） a. 无向图：对称阵，可采用矩阵压缩存储方式。A[i][j] = 0表示i v 和j v 没有连接； A[i][j] = 1表示i v 和j v 有边连接；第i 行的和表示顶点i v 的度 b. 有向图：不对称阵。,[][]i j A i j w =表示顶点i v 到j v 的有向弧的权值；[][]A i j =∞ 表示表示顶点i v 到j v 没有弧连接或者i = j 2. 邻接表（链表，有向无向都可用） 边结点：adjvex （邻接点），nextarc （下一条边），info （权值） 顶点结点：data （顶点数据），firstarc （第一条边） 3. 十字链表（Othogonal List ） 弧结点：tailvex （弧尾结点），headvex （弧头结点），tlink （弧尾相同的下一条弧），hlink （弧头相同的下一条弧），info （权值） 顶点结点：data （顶点数据），firstin （第一条入弧），firstout （第一条出弧） 三、图的遍历（每个顶点只被访问一次） 1. 深度优先遍历（类似树的先根遍历） 基本思想：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶 点v 出发，访问此结点，然后依次从v 的未被访问的邻接点出发深度优先遍 历图，直至图中所有和v 有路径相通的顶点都被访问到；若此时图中尚有顶 点未被访问（非连通图），则另选图中一个未曾被访问的顶点作起始点，重 复上述过程，直至图中所有顶点都被访问到为止。

数据结构：图子系统

/* *题目：编写按键盘输入的数据建立图的邻接矩阵存储 * 编写图的深度优先遍历程序 * 编写图的广度优先遍历程序 * 设计一个选择式菜单形式如下： * 图子系统 * *********************************** * * 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);

数据结构实验报告图实验

邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph（DataType a[], int n, int e）; ~MGraph（）{ void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; }

int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: " cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

数据结构-图习题

第8章 图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n-1)/2。 【解答】 【证明】 在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1条边与其他n-1个顶点相连，总计n 个顶点有n(n-1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n-1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】 点，它不是强连通的有向图。各个顶点自成强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A 1个顶点的 无向完全图 2个顶点的 无向完全图 3个顶点的 无向完全图 4个顶点的 无向完全图 5个顶点的 无向完全图 A D

????????? ?????? ?????=01 00000001001010000 010*********Edge →D →B →C →F 。 从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。 从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。 从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。 从顶点E 出发，到其他各个顶点的简单路径无。 从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 A D

数据结构实验

实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include main() { intn,m,i=0,j=0,k=0,a[5],b[5],c[10];/* 必须设个m做为数组的输入的计数器，不能用i ，不然进行到while 时i 直接为5*/ for(m=0;m<=4;m++)scanf("%d",&a[m]);// 输入数组a for(m=0;m<=4;m++)scanf("%d",&b[m]);// 输入数组b while(i<5&&j<5) {if(a[i]b[j]){c[k]=b[j];k++;j++;} else{c[k]=a[i];k++;i++;j++;}// 使输入的两组数组中相同的数只输出一 个 } if(i<5) for(n=i;n<5;n++) {c[k]=a[n];k++;} elseif(j<5) for(n=j;n<5;n++) {c[k]=b[n];k++;} for(i=0;i

求A QB #include main() { inti,j,k=0,a[5],b[5],c[5];//A=a[5],B=b[5],A n B=c[5] for(i=0;i<5;i++)scanf("%d",&a[i]);// 输入a 数组 for(i=0;i<5;i++)scanf("%d",&b[i]);〃输入b 数组 for(i=0;i<5;i++) {for(j=0;j<5;j++) if(a[i]==b[j]){c[k]=a[i];k++;}// 当有元素重复时，只取一个放入 c 中} for(i=0;i #defineN4 main() { inti,j,m,k,a[N+1];//k 为最后输出数组的长度变量

数据结构实验图的基本操作

浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十三/十四图的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期2014/06/09 一.实验目的和要求 1、掌握图的主要存储结构。 2、学会对几种常见的图的存储结构进行基本操作。 二.实验内容 1、图的邻接矩阵定义及实现： 建立头文件test13_AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test13.cpp（以下图为例），编译并调试程序，直到正确运行。 2、图的邻接表的定义及实现： 建立头文件test13_AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test13.cpp中调用这些函数进行验证（以下图为例）。

3、填写实验报告，实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc到BB。 注: 下载p256_GraphMatrix.cpp(邻接矩阵)和 p258_GraphAdjoin.cpp(邻接表)源程序，读懂程序完成空缺部分代码。 三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路） 四. 实验结果与分析 （包括运行结果截图、结果分析等）

五.心得体会

程序比较难写，但是可以通过之前的一些程序来找到一些规律 （记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。） 【附录----源程序】 256: //p-255 图的存储结构以数组邻接矩阵表示, 构造图的算法。 #include #include #include #include typedef char VertexType; //顶点的名称为字符 const int MaxVertexNum=10; //图的最大顶点数 const int MaxEdgeNum=100; //边数的最大值 typedef int WeightType; //权值的类型 const WeightType MaxValue=32767; //权值的无穷大表示 typedef VertexType Vexlist[MaxVertexNum]; //顶点信息，定点名称 typedef WeightType AdjMatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵typedef enum{DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网typedef struct{ Vexlist vexs; // 顶点数据元素 AdjMatrix arcs; // 二维数组作邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 } MGraph; void CreateGraph(MGraph &G, GraphKind kd)// 采用数组邻接矩阵表示法，构造图G {//构造有向网G int i,j,k,q; char v, w; G.kind=kd; //图的种类 printf("输入要构造的图的顶点数和弧数：\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等：\n"); for (i=0; i

数据结构中图的全部操作

#include #include #include #include #include #include using namespace std; #define MAX_VERTEX_NUM 100 #define INFINITY INT_MAX #define EXTERN 10 #define OK 1 #define ERROR -1 #define MAX -1 #define MAXW 10000 typedef int Status; typedef bool VisitIf; typedef char VertexType;//顶点数据类型 typedef int VRType; //顶点关系( 表示是否相邻) typedef int InfoType; //弧相关信息

typedef enum{DG,DN,UDG,UDN} GraphKind;//图的类型 bool visited[MAX_VERTEX_NUM]; //邻接矩阵 typedef struct ArcCell { VRType adj;//权值 InfoType *info; }ArcCell,AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMartix arcs; //邻接矩阵 int vexnum,arcnum; //图当前顶点数,弧数 GraphKind Kind; //图的类型 }MGraph; bool VexExist(MGraph G,VertexType v)//判断定点是否在图中{

数据结构实验报告图实验

图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif #include using namespace std; #include "" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0;

数据结构图实验报告

数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 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 }

(完整版)数据结构详细教案——图

数据结构教案第七章图

第7章图 【学习目标】 1．领会图的类型定义。 2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。 3．熟练掌握图的两种遍历算法。 4．理解各种图的应用问题的算法。 【重点和难点】 图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。 【知识点】 图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 【学习指南】 离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。 【课前思考】 1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图？ 2. 如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？ 同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC)

数据结构实验—图实验报告

精品文档数据结构 实 验 报 告

目的要求 １．掌握图的存储思想及其存储实现。 ２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。 实验内容 １．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。 3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。 6．采用邻接表存储实现无向图的广度优先遍历。 7．在主函数中设计一个简单的菜单，分别调试上述算法。 源程序： 主程序的头文件：队列 #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int QElemType; typedef struct QNode{ //队的操作 QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; void InitQueue(LinkQueue &Q){ //初始化队列 Q.front =Q.rear =(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); //存储分配失败 Q.front ->next =NULL; } int EnQueue(LinkQueue &Q,QElemType e) //插入元素e为Q的新的队尾元素{ QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e;

《数据结构》基本操作指导

目录 指导一、单链表的操作----------------------------------------------------- 2指导二、栈及其应用------------------------------------------------------- 10指导三、串的基本操作---------------------------------------------------- 16指导四、二叉树的基本操作---------------------------------------------- 21指导五、图的存储和遍历------------------------------------------------- 31指导六、查找--------------------------------------------------------------- 41 指导七、排序--------------------------------------------------------------- 49

指导一、单链表的操作 一、指导目的 1、掌握线性表的链式存储结构。 2、掌握利用链式存储结构实现线性表的基本操作。 3、掌握链式存储结构中的算法实现。 二、指导内容 1、建立带头结点的单链表，并输出该单链表。 2、实现带头结点的单链表上的插入、删除、查找、修改操作。 三、操作指导 1、定义单链表的结点结构 单链表的结点结构可为一个结构体类型(slnodetype)，其成员是数据域和指针域，数据域可以是整数。 2、模块划分和程序控制流程 根据实验要完成的各功能，设置初始化、建立单链表、输出单链表、插入、删除、查找、修改和主函数8个模块，对于要完成的各功能，采用适当的人机界面，用循环和分支结构构成菜单进行选择。 3、初始化模块int initiate(slnodetype **h) 该模块中产生一个只有头结点的空单链表，用指针h作为函数的参数返回，因为h是指针变参，所以在函数的参数位置要以二级指针出现。在函数里，申请一个头结点空间。 4、建立单链表模块int createlink(slnodetype *h) 该模块中建立有若干个结点的单链表，用循环控制输入若干个整数，申请相应的结点空间，以输入的整数作为结点中的数据，依次链接到初始只有头结点的单链表h中，可以把输入0作为建立链表的结束。 5、输出单链表模块void display(slnodetype *h) 对于传入的单链表h，依次输出单链表中的结点(数据)。 6、插入结点模块int inserti(slnodetype *h) 设在第i个结点前插入数据为data的结点。在该函数模块中输入i和数据data，对于传入的单链表h，先查找是否存在插入的位置(单链表h中至少要有i-1个结点)，若不存在插入位置，则不做任何操作；若存在插入位置，则申请一个结点，其数据为data，挂在第i-1个结点的后面。 7、删除结点模块int delete(slnodetype *h) 在该函数模块中，首先可以调用输出模块输出传入的单链表h，以便选择要删除的结点，然后输入要删除结点的数据data，再查找是否存在要删除的结点，若不存在要删除的结点，则显示相应的信息；若存在要删除的结点，则删除该结点(包括删除该结点空间)。 8、查找模块int search(slnodetype *h)