㈠ 数据结构实现图的基本操作
对邻接表存储的图进行深度优先搜索算法：
#include "stdio.h"
#define MAXVER 10 /* 最多顶点数 */
typedef char ElemType; /* 顶点元素类型 */
typedef struct node
{ int num;
struct node *next;
}slink; /* 边或弧的结点类型 */
typedef struct
{ struct
{ ElemType vertex;
slink *first;
}ve[MAXVER]; /* 顶点信息结构 */
int vex,edge,tag; /* 存放顶点数、边数和图的类型 */
}adjlist; /* 邻接表存储结构类型名 */
/* 建立图的邻接表存储表示。 */
void cregraph(adjlist *G,int n,int m) /* 建立邻接表. n为顶点数，m为图的类型 */
{ int i,e=0;slink *p,*q,*s;char x,y;
G->vex=n; G->tag=m;
for(i=0;i<n;i++)
{ G->ve[i].vertex=i+'A'; G->ve[i].first=NULL;} /* 初始化邻接表 */
printf("Input edges(x-->y):"); /* 用大写字母表示顶点 */
scanf("%c%c",&x,&y);
while(x!=' '&&y!=' ') /* 输入边或弧，遇空格符结束 */
{ e++; /* 统计边或弧和数目 */
s=(slink *)malloc(sizeof(slink));
s->num=y-'A'; /* 生成结点插入 */
if(G->ve[x-'A'].first==NULL)
{ G->ve[x-'A'].first=s;
s->next=NULL;
}
else
{ p=G->ve[x-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) {p=q;q=q->next;}
p->next=s;s->next=q;
}
if(!G->tag) /* m=0表示建立无向图的邻接表 */
{ s=(slink *)malloc(sizeof(slink));
s->num=x-'A';
if(G->ve[y-'A'].first==NULL)
{ G->ve[y-'A'].first=s;s->next=NULL;}
else
{ p=G->ve[y-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) { p=q;q=q->next;}
p->next=s;s->next=q;
}
}
scanf("%c%c",&x,&y);
}
G->edge=e;
}
/* 输出用邻接表存储表示的图 */
void list(adjlist *G) /* 输出邻接表 */
{ int i; slink *p;
for(i=0;i<G->vex;i++)
{ printf("%d:%c--->",i,G->ve[i].vertex);
p=G->ve[i].first;
while(p)
{ printf("%3d",p->num);
p=p->next;
}
printf("\n");
}
}
/* 对邻接表存储的图进行深度优先搜索算法 */
int visited[MAXVER+1]; /* 顶点的访问标记数组 */
dfs(adjlist *G,int v) /* v是访问的起始点的下标 */
{ slink *p;
visited[v]=1;
printf("%3c",G->ve[v].vertex);
p=G->ve[v].first;
while(p)
{ if(visited[p->num]==0) /* 从V的未访问过的邻接点出发 */
dfs(G,p->num);
p=p->next; /* 找V的下一个邻接点 */
}
}
void dfsgraph(adjlist *G)
{ int i;
for(i=0;i<G->vex;i++) if(!visited[i]) dfs(G,i);
}
main()
{ adjlist g;
int n=8;
cregraph(&g,n,0);
dfsgraph(&g);
}
对一个采用邻接表作存储结构的图进行广度优先遍历：
/*邻接表结构*/
#include "stdio.h"
#define MAXVER 10 /* 最多顶点数 */
typedef char ElemType; /* 顶点元素类型 */
typedef struct node
{ int num;
struct node *next;
}slink; /* 边或弧的结点类型 */
typedef struct
{ struct
{ ElemType vertex;
slink *first;
}ve[MAXVER]; /* 顶点信息结构 */
int vex,edge,tag; /* 存放顶点数、边数和图的类型 */
}adjlist; /* 邻接表存储结构类型名 */
/*建立邻接表*/
void cregraph(adjlist *G,int n,int m) /* n为顶点数，m为图的类型 */
{ int i,e=0;slink *p,*q,*s;char x,y;
G->vex=n; G->tag=m;
for(i=0;i<n;i++)
{ G->ve[i].vertex=i+'A'; G->ve[i].first=NULL;} /* 初始化邻接表 */
printf("Input edges(x-->y):"); /* 用大写字母表示顶点 */
scanf("%c%c",&x,&y);
while(x!=' '&&y!=' ') /* 输入边或弧，遇空格符结束 */
{ e++; /* 统计边或弧和数目 */
s=(slink *)malloc(sizeof(slink));
s->num=y-'A'; /* 生成结点插入 */
if(G->ve[x-'A'].first==NULL)
{ G->ve[x-'A'].first=s;
s->next=NULL;
}
else
{ p=G->ve[x-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) {p=q;q=q->next;}
p->next=s;s->next=q;
}
if(!G->tag) /* m=0表示建立无向图的邻接表 */
{ s=(slink *)malloc(sizeof(slink));
s->num=x-'A';
if(G->ve[y-'A'].first==NULL)
{ G->ve[y-'A'].first=s;s->next=NULL;}
else
{ p=G->ve[y-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) { p=q;q=q->next;}
p->next=s;s->next=q;
}
}
scanf("%c%c",&x,&y);
}
G->edge=e;
}
/* 输出邻接表 */
void list(adjlist *G) /* 输出用邻接表表示的图 */
{ int i; slink *p;
for(i=0;i<G->vex;i++)
{ printf("%d:%c--->",i,G->ve[i].vertex);
p=G->ve[i].first;
while(p)
{ printf("%3d",p->num);
p=p->next;
}
printf("\n");
}
}
/* 对一个采用邻接表作存储结构的图进行广度优先遍历 */
int visited[MAXVER];
void bfs(adjlist *G,int v)
{ int queue[MAXVER],front,rear,i;/* 定义一个分离队列 */
slink *p;
front=rear=0; /* 队列初始化为空 */
queue[rear++]=v; /* 初始顶点入队列 */
while(front!=rear) /* 队列不空 */
{ v=queue[front++]; /* 出队列访问 */
printf("%c->",G->ve[v].vertex);
visited[v]=1; /* 入访问表 */
p=G->ve[v].first;
while(p!=NULL)
{ for(i=0;i<rear;i++)
if(p->num==queue[i]) break;
if(i>=rear)
queue[rear++]=p->num; /* 该邻接点即没被访问过，也不在队列中，则入队列 */
p=p->next; /* 找V的下一个邻接点 */
}
}
}
void bfsgraph(adjlist *G) /* 若还有不连通的部分，则跳过去访问之 */
{ int i;
for(i=0;i<G->vex;i++)
if(!visited[i]) bfs(G,i);
}
main()
{ adjlist G;
cregraph(&G,8,0);
bfsgraph(&G);
}
最小生成树的算法：
/*求最小生成树的Kruskal算法描述*/
#define MAXE 10
struct edges
{ int bv,tv,w;}; /* 边集类型，存储一条边的起始点bv终止顶点tv和权w */
typedef struct edges edgeset[MAXE+1];
int seeks(int set[],int v)
{ int i=v;
while(set[i]>0)
i=set[i];
return i;
}
kruskal(edgeset ge,int n,int e) /* ge表示的图是按权值从小到大排列的 */
{ int set[MAXE],v1,v2,i,j;
for(i=1;i<=n;i++)
set[i]=0; /* 给set中的每个元素赋初值 */
i=1; /* i表示待获取的生成树中的边数，初值为1 */
j=1; /* j表示ge中的下标，初值为1 */
while(j<n &&i<=e) /* 按边权递增顺序，逐边检查该边是否应加入到生成树中 */
{ v1=seeks(set,ge[i].bv); /* 确定顶点v所在的边通集 */
v2=seeks(set,ge[i].tv);
if(v1!=v2) /* 当v1,v2不在同一顶点集合，确定该边应当选入生成树 */
{ printf(" (%d,%d) ",ge[i].bv,ge[i].tv);
set[v1]=v2;
j++;
}
i++;
}
}
main()
{ edgeset e={{0,0,0},{4,5,2},{3,5,3},{1,4,5},{1,2,6},{2,4,7},{2,5,8},{1,3,9},{3,4,9},{1,5,13},{2,3,14}};
kruskal(e,5,10);
}
最短路径的算法：
#define Max 10 /* 预设最多顶点数 */
#define INFINITY 1000 /* 最大值 */
typedef struct
{ int vexnum,arcnum; /* 顶点数及边或弧的数目 */
char vex[Max]; /* 存顶点信息的一维数组 */
int arc[Max][Max]; /* 存边信息的二维数组 */
}AdjMatrix;
/* 建立有向图的邻接矩阵表示 */
void Creadjm(AdjMatrix *G)
{ int i,j,k,w;
printf("Input vex&arc:");
scanf("%d%d%*c",&G->vexnum,&G->arcnum);/*输入顶点数和边数，并读掉回车符*/
printf("Input Vexinfo:");
for(k=0;k<G->vexnum;k++)
scanf("%c",&G->vex[k]); /* 输入代表顶点的字符 */
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
G->arc[i][j]=INFINITY; /* 初始化邻接矩阵 */
printf("Input %d edges:\n",G->arcnum);
for(k=0;k<G->arcnum;k++)
{ scanf("%d%d%d",&i,&j,&w); /* 输入边或弧 */
G->arc[i][j]=w;
}
}
/* 输出用邻接矩阵表示的有向图 */
void list(AdjMatrix *G)
{ int i,j;
for(i=0;i<G->vexnum;i++)
{ printf("%6c----",G->vex[i]); /* 先输出顶点信息 */
for(j=0;j<G->vexnum;j++)
printf("%4d",G->arc[i][j]); /* 再输出与该顶点有关联的边或弧的信息 */
printf("\n");
}
}
/* 计算从顶点v0到其余各点最短路径算法 */
void dijkstra(AdjMatrix *G,int n,int v0,int d[]) /* d数组存放各顶点最短路径 */
{ int s[Max] ; /* s数组存放顶点是否找到最短路径 */
int i,j,u,mindis;
for(i=0;i<n;i++)
{ d[i]=G->arc[v0][i];s[i]=0;}
s[v0]=1;
for(i=1;i<n;i++)
{ mindis=INFINITY;
for(j=0;j<n;j++)
if(s[j]==0 && d[j]<mindis) { u=j; mindis=d[j];}
s[u]=1; /* 顶点u已找到最短路径 */
for(j=1;j<=n;j++) /* 修改j的最短路径 */
if(s[j]==0&&d[j]>d[u]+G->arc[u][j]) d[j]=d[u]+G->arc[u][j];
}
}
main()
{ AdjMatrix G;
int d[Max],i;
Creadjm(&G);
list(&G);
dijkstra(&G,6,0,d);
for(i=0;i<G.vexnum;i++)
printf("%4d",d[i]);
}
㈡ 求救 急急急 数据结构 【实验目的】 （1）掌握线性表的特点 （2）掌握线性表顺序存储结构和
题主你问的这个真心懒得写 原因如下
显然是作业 而且题主你一点都没有试着解过
代码很长
很无聊的问题
综上，以后不要问类似的问题了
㈢ C语言 数据结构 （图）校园导游咨询模拟(代码相关的)
导游咨询帮实现
㈣ 实验一 顺序表的基本运算 一． 实验目的： 掌握线性表在顺序存储结构上的插入、删除运算。 二． 实验要求
问老师吧 少年
㈤ 数据结构完整版实验报告
(一)实验目的和要求
实验目的：熟练掌握线性表的基本操作在顺序存储结构上的实现。
实验要求：任选一种高级程序语言编写源程序，并调试通过，测试正确。
(二)实验主要内容
1. 建立n个元素的顺序表SqList，实现顺序表的基本操作；
2. 在SqList的元素i之后插入一个元素，实现顺序表插入的基本操作；
3. 在sqList中删除指定位置i上的元素，实现顺序表删除的操作。
4.
(三)主要仪器设备
PC机，Windows XP操作平台，Visual C++
(四)实验原理
顺序表操作：定义一个顺序表类，该类包括顺序表的存储空间、存储容量和长度，以及构造、插入、删除、遍历等操作的方法
(五)实验步骤与调试分析：
顺序表操作：先构造有四个数据的顺序表，在第4个位置插入9，再读取并删除第3个元素。
(六)实验结果与分析：
顺序表操作：
（七）附录（源程序）：
#include<iostream>
using namespace std;
const int LIST_INIT_SIZE=10; //顺序表初始长度
const int LISTINCREMENT=5; //顺序表长度增值
class SqList
{
int *L; //定义存储空间起始地址
int length; //顺序表当前长度
int listsize; //顺序表当前存储容量
bool flag; //设立标志值记录操作成败
public:
SqList(int v1,int v2,int v3,int v4); //构造函数构造并初始化顺序表
void ListInsert(int i,int e); //实现将e插入到顺序表中第i个位置
void ListDelete(int i,int &e); //实现删除顺序表第i个元素
void ListVisit(); //实现顺序表的遍历
};
SqList::SqList(int v1,int v2,int v3,int v4) //构造并初始化顺序表
{
L=new int[LIST_INIT_SIZE];
if(!L) //分配失败
{
flag=false;
cout<<"ERROR"<<endl;
}
else //分配成功，进行初始化
{
*L=v1;
*(L+1)=v2;
*(L+2)=v3;
*(L+3)=v4;
length=4;
listsize=LIST_INIT_SIZE;
flag=true;
}
}
void SqList::ListInsert(int i,int e) //插入元素
{
int *p,*q;
int t;
if(i<1||i>length+1) cout<<"ERROR"<<endl; //插入位置错误
else
{
if(length==listsize) //空间不足，增加分配
{
p=new int[listsize+LISTINCREMENT];
if(!p) cout<<"ERROR"<<endl; //分配失败
else //分配成功，复制顺序表
{
for(t=0;t<length;t++)
*(p+t)=*(L+t);
q=L;L=p;p=q;
delete q;
listsize+=LISTINCREMENT;
}
}
for(t=length;t>=i;t--)
*(L+length)=*(L+length-1);
*(L+i-1)=e;
length++; //插入成功，表长加1
}
}
void SqList::ListDelete(int i,int &e)
{
if(i<1||i>length) cout<<"ERROR"<<endl; //删除位置错误
else
{
e=*(L+i-1);
while(i<length)
{
*(L+i-1)=*(L+i);
i++;
}
length--; //删除成功表长减1
}
}
void SqList::ListVisit() //遍历
{
int i;
for(i=0;i<length;i++)
cout<<" "<<*(L+i);
cout<<endl;
}
int main()
{
int e=0;
SqList list(2,3,4,5);
list.ListVisit();
list.ListInsert(4,9);
list.ListVisit();
list.ListDelete(3,e);
list.ListVisit();
cout<<"e="<<e<<endl;
return 0;
}
㈥ 实验五、二叉树的基本操作和应用组织机构——二叉树的建立和操作
//二叉树的建立遍历完全二叉树判断
#include<iostream>
#include<queue>
usingnamespacestd;
typedefstructNode{
chardata;
Node*lchild,*rchild;
}BiNode,*BiTree;
voidCreateBiTree(BiTree&bt)//输入二叉树元素
{
charc;
cin>>c;
if(c=='#'){
bt=NULL;
}
else{
bt=newBiNode;
bt->data=c;
cout<<"输入"<<c<<"的左子树"<<endl;
CreateBiTree(bt->lchild);
cout<<"输入"<<c<<"的右子树"<<endl;
CreateBiTree(bt->rchild);
}
}
intIsCBT(BiTree&bt)
{
BiNode*p=bt;
queue<BiNode*>q;
inttag=0;
if(p==NULL)return1;
q.push(p);
while(!q.empty())
{
p=q.front();q.pop();
if(p->lchild&&!tag)q.push(p->lchild);
elseif(p->lchild)return0;
elsetag=1;
if(p->rchild&&!tag)q.push(p->rchild);
elseif(p->rchild)return0;
elsetag=1;
}
return1;
}
voidpre(BiTree&bt){
if(bt){
cout<<bt->data<<"";
pre(bt->lchild);
pre(bt->rchild);
}
}
intmain()
{
BiTreebt;
CreateBiTree(bt);
pre(bt);
cout<<endl;
if(IsCBT(bt)){
cout<<"Yes,itisaCBT"<<endl;
}
else{
cout<<"No,itisnotaCBT"<<endl;
}
system("pause");
return0;
｝
㈦ 图的基本操作与实现
看见题就复杂了