1、为其定义一个名称,就叫【StackEmpty】。
2、接下来在参数中传递一个Top表过来。
3、好了后就可以定义他的返回类型,空表时返回1,非空返回0,因此为整形。
6、然后就能写上这样的一段判断语句。
6、为了遵循一个出口,不建议程序中有两个return语句,建议定义一个变量。
6、然后返回这变量,这样就能更好的提高程序的可读性。运行就可以了。
深度优先搜索。
http://www.cnblogs.com/dzkang2011/p/bfs_dfs.html
#include <iostream>#include <cstdio>
using namespace std
#define maxn 100 //最大顶点个数
int n, m //顶点数,边数
struct arcnode //边结点
{
int vertex //与表头结点相邻的顶点编号
int weight = 0 //连接两顶点的边的权值
arcnode * next //指向下一相邻接点
arcnode() {}
arcnode(int v,int w):vertex(v),weight(w),next(NULL) {}
arcnode(int v):vertex(v),next(NULL) {}
}
struct vernode //顶点结点,为每一条邻接表的表头结点
{
int vex //当前定点编号
arcnode * firarc //与该顶点相连的第一个顶点组成的边
}Ver[maxn]
void Init() //建立图的邻接表需要先初始化,建立顶点结点
{
for(int i = 1 i <= n i++)
{
Ver[i].vex = i
Ver[i].firarc = NULL
}
}
void Insert(int a, int b, int w) //尾插法,插入以a为起点,b为终点,权为w的边,效率不如头插,但是可以去重边
{
arcnode * q = new arcnode(b, w)
if(Ver[a].firarc == NULL)
Ver[a].firarc = q
else
{
arcnode * p = Ver[a].firarc
if(p->vertex == b) //如果不要去重边,去掉这一段
{
if(p->weight < w)
p->weight = w
return
}
while(p->next != NULL)
{
if(p->next->vertex == b) //如果不要去重边,去掉这一段
{
if(p->next->weight < w)
p->next->weight = w
return
}
p = p->next
}
p->next = q
}
}
void Insert2(int a, int b, int w) //头插法,效率更高,但不能去重边
{
arcnode * q = new arcnode(b, w)
if(Ver[a].firarc == NULL)
Ver[a].firarc = q
else
{
arcnode * p = Ver[a].firarc
q->next = p
Ver[a].firarc = q
}
}
void Insert(int a, int b) //尾插法,插入以a为起点,b为终点,无权的边,效率不如头插,但是可以去重边
{
arcnode * q = new arcnode(b)
if(Ver[a].firarc == NULL)
Ver[a].firarc = q
else
{
arcnode * p = Ver[a].firarc
if(p->vertex == b) return //去重边,如果不要去重边,去掉这一句
while(p->next != NULL)
{
if(p->next->vertex == b) //去重边,如果不要去重边,去掉这一句
return
p = p->next
}
p->next = q
}
}
void Insert2(int a, int b) //头插法,效率跟高,但不能去重边
{
arcnode * q = new arcnode(b)
if(Ver[a].firarc == NULL)
Ver[a].firarc = q
else
{
arcnode * p = Ver[a].firarc
q->next = p
Ver[a].firarc = q
}
}
void Show() //打印图的邻接表(有权值)
{
for(int i = 1 i <= n i++)
{
cout << Ver[i].vex
arcnode * p = Ver[i].firarc
while(p != NULL)
{
cout << "->(" << p->vertex << "," << p->weight << ")"
p = p->next
}
cout << "->NULL" << endl
}
}
void Show2() //打印图的邻接表(无权值)
{
for(int i = 1 i <= n i++)
{
cout << Ver[i].vex
arcnode * p = Ver[i].firarc
while(p != NULL)
{
cout << "->" << p->vertex
p = p->next
}
cout << "->NULL" << endl
}
}
#define INF 999999
bool visited[maxn] //标记顶点是否被考察,初始值为false
int parent[maxn] //parent[]记录某结点的父亲结点,生成树,初始化为-1
int d[maxn], time, f[maxn] //时间time初始化为0,d[]记录第一次被发现时,f[]记录结束检查时
void dfs(int s) //深度优先搜索(邻接表实现),记录时间戳,寻找最短路径
{
cout << s << " "
visited[s] = true
time++
d[s] = time
arcnode * p = Ver[s].firarc
while(p != NULL)
{
if(!visited[p->vertex])
{
parent[p->vertex] = s
dfs(p->vertex)
}
p = p->next
}
time++
f[s] = time
}
void dfs_travel() //遍历所有顶点,找出所有深度优先生成树,组成森林
{
for(int i = 1 i <= n i++) //初始化
{
parent[i] = -1
visited[i] = false
}
time = 0
for(int i = 1 i <= n i++) //遍历
if(!visited[i])
dfs(i)
cout << endl
}
int main()
{
int a, b
cout << "Enter n and m:"
cin >> n >> m
Init()
while(m--)
{
cin >> a >> b //输入起点、终点
Insert2(a, b) //插入操作
}
Show2() //邻接表
dfs_travel() //遍历
int cnt = 0 //连通图个数
for(int i = 1 i <= n i++)
if(parent[i] == -1)
cnt++
printf("%d\n", cnt)
return 0
}
#include <stdio.h>#include<stdlib.h>
typedef struct ArcNode {
int adjvex// 该弧所指向的顶点的位置
struct ArcNode *nextarc// 指向下一条弧的指针
int *info// 该弧相关信息的指针
}ArcNode
typedef struct VNode {
int data// 顶点信息
ArcNode *firstarc// 指向第一条依附该顶点的弧
}VNode, AdjList[50]
typedef struct {
AdjList vertices
int vexnum, arcnum// 图的当前顶点数和弧数
}ALGraph
int locateALG(ALGraph g,int v){
for(int i=0i<g.vexnumi++){
if(g.vertices[i].data==v)
return i
}
return -1
}
int CreateADG(ALGraph &g){
int i,j,k,l
ArcNode *p
int v1,v2
int c
printf("请输入有向图的顶点数:")
scanf("%d",&g.vexnum)
while(g.vexnum>50){
printf("\n请输入有向图的顶点数:")
scanf("%d",&g.vexnum)
}
i=g.vexnum*(g.vexnum-1)
printf("请输入有向图的边数:")
scanf("%d",&g.arcnum)
while(g.arcnum>i){
printf("\n请输入有向图的边数:")
scanf("%d",&g.arcnum)
}
getchar()
printf("请依次输入有向图的各个顶点:")
for(i=0i<g.vexnumi++){//输入顶点信息
scanf("%d",&c)
l=locateALG(g,c)
if(l>=0){
printf("输入的顶点重复,请重新输入\n")
i--
continue
}
g.vertices[i].data=c
g.vertices[i].firstarc=NULL
}
for(k=0k<g.arcnumk++){//输入边的信息
printf("请输入第%d条弧的起点与终点(用逗号分隔):",k+1)
scanf("%d,%d",&v1,&v2)
i=locateALG(g,v1)
j=locateALG(g,v2)
if(i<0||j<0||i==j||(g.vexnum<0)){
k--
continue
}
p=(ArcNode*)malloc(sizeof(ArcNode))//建立结点
if(!p) return -1
p->adjvex=j
p->nextarc=g.vertices[i].firstarc//顶点i的链表
g.vertices[i].firstarc=p//添加到最左边
}
printf("有向图的邻接表创建成功\n")
return 1
}
void printGra(ALGraph G){
ArcNode *p
int i
printf("图中有%d个顶点,%d条弧:\n",G.vexnum,G.arcnum)
for(i=0i<G.vexnumi++){
p=G.vertices[i].firstarc
printf("%d\t",G.vertices[i].data)
while(p){
printf("<%d,%d>",G.vertices[i].data,G.vertices[p->adjvex].data)
p=p->nextarc
}
printf("\n")
}
}
int main(void)
{
ALGraph g
CreateADG(g)
printGra(g)
return 0
}