① c语言循环结构输出纯数字图形
#include<math.h>
#include<stdio.h>
int main()
{
int i,j,k,l;
for(i=0;i<7;i++)
{
for(j=i;j>=-i;j--)
{
printf("%d",abs(j));
}
for(k=1;k<14-2*i-1;k++)
printf("%c",'8');
printf("\n");
}
}
② C语言用选择结构流程图判断一个数是否为奇数
int a;//定义变量
scanf("%d",&a);//输入数字；
if(a%2)printf("该数为奇数")； //不能被2整除就是奇数
else printf("该数为偶数");
③ 数据结构(用c语言描述)，是随机快速排序算法，划红线部分那里我不懂，希望有学霸能解释一下，越详细越好
这是一个randomi的函数，作用是返回一个随机值，在1到r之间。
return后面那个公式就是返回的随机数字。
1*rand()是随机得到一个数字，在除以RAND_MAX得到的是一个随机的百分比。
RAND_MAX就是rand()的范围大小。
随机百分比得到了，在乘(r－1)就得到这个(r－1)范围内随机比例。
最后再加上1保证得到的数字是在1和r之间的。
这样就能输出一个随机数字了。
精髓是后面那个除法得到一个随机的比例，前面的乘法和加法都是为了限定范围的修修补补。
④ c语言版数据结构图的一些基本操作函数如下，有三个地方不了解，请各位帮帮忙
（1）问题三：
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
*G不是指针，是指针G所指对象，就是ALGraph类型。程序中多处使用变量G，但是不同的地方，含义不同。在void CreateGraph(ALGraph *G)里面，G是一个指针，因此，引用其所指对象，要用*G。其他情况下，ALGraph G，G不是指针。
（2）第一：这个void DFSTraverse(ALGraph G,void(*print)(char*)) 为什么不能直接调用print函数，像调用DFS函数一样？可以的，使用函数指针是为以后任意扩展输出程序，以适应不同需要，并且可以作为参数传递。
（3）第二：FirstAdjVex(G,G.vertices[v].data)为什么要用顶点，用了之后又取位置，而不直接用位置，会有什么漏洞吗？不会
int FirstAdjVex(ALGraph G,VertexType v)
{
ArcNode *p;
int v1;
v1=LocateVex(G,v);
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
利用已经定义的定位函数LocateVex直接定位顶点v，然后直接读取其firstarc，很自然的过程。
⑤ C语言数据结构求解
方法很多，可以在插入数据后再对线性表进行删改，也可以在插入前进行处理。
我这里代码是在插入前处理。
（注释掉的函数int getPNUM(struct Sqlist *st,int n);是我预留的，题2如果你想改成插入后，再对线性表素数进行查找，可以用这个函数。否则可以删除）。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LIST_INIT_SIZE 800
struct Sqlist{
int *elem;
int length;
int listsize;
};
int insert2List(struct Sqlist *st,int num,int inx);//向线性表第inx个元素的位置插入一个元素。成功返回1,失败返回0
int findNum(struct Sqlist *st,int num);//在线性表中查找指定数字，存在返回1，不存在返回0
//int getPNUM(struct Sqlist *st,int n);//查找素数，返回第几n个素数的下标。未找到返回-1
void showList(struct Sqlist *st);//打印线性表
void clearList(struct Sqlist *st);//清空线性表
int main()
{
int i,k,nums[LIST_INIT_SIZE],n,num,cnt,flag;
struct Sqlist st={nums,0,LIST_INIT_SIZE};
srand(time(NULL));
//--------------题1-----------------------------------------------------------------------
n=100;
k=1;
printf("1、随机生成100个【100,200】之间的随机数，去除重复并保存到线性表 ");
while(n--)
{
num=rand()%101+100;
printf("--%3d产生随机数%d ",k++,num);
if(findNum(&st,num))
printf("该数字已在线性表中存在，重复去除 ");
else
{
if(insert2List(&st,num,st.length+1))
printf("该随机值已保存到线性表尾部 ");
else{
printf("异常!插入失败! ");
return 1;
}
}
}
showList(&st);
clearList(&st);
//-------------题2----------------------------------------------------------------
n=20;
cnt=0;
k=1;
printf("1、随机生成20个【1,200】之间的随机数，在第一个素数后插入1个0，第二个素数后插入2个0，以此类推，最后输出所有元素 ");
while(n--)
{
num=rand()%200+1;
printf("--%3d产生随机数%d ",k++,num);
flag=1;
for(i=2;i<num;i++)
if(num%i==0)
{
flag=0;
break;
}
if(flag)
{
cnt++;
printf("该随机值是一个素数，在其尾部插入%d个0 ",cnt);
for(i=0;i<cnt;i++)
num*=10;
printf("该随机值变更为%d ",num);
}
if(insert2List(&st,num,st.length+1))
printf("该随机值已保存到线性表尾部 ");
else{
printf("异常!插入失败! ");
return 1;
}
}
showList(&st);
return 0;
}
void clearList(struct Sqlist *st)//清空线性表
{
st->length=0;
printf("线性表数据已清除 ");
}
void showList(struct Sqlist *st)//打印线性表
{
int i;
printf("当前线性表的数据为: ");
for(i=0;i<st->length;i++)
printf("%d ",st->elem[i]);
printf(" ");
}
int findNum(struct Sqlist *st,int num)//在线性表中查找指定数字，存在返回1，不存在返回0
{
int *p=st->elem;
while(p<=&st->elem[st->length-1])
if(*p++==num)
return 1;
return 0;
}
/*
int getPNUM(struct Sqlist *st,int n)//查找素数，返回第几n个素数的下标。未找到返回-1
{
int i,j,flag,cnt=0;
for(i=0;i<st->length;i++)
{
flag=1;
for(j=2;j<st->elem[i];j++)
if(st->elem[i]%j==0)
{
flag=0;
break;
}
if(flag)
cnt++;
if(cnt==n)
return i;
}
return -1;
}
*/
int insert2List(struct Sqlist *st,int num,int inx)//向线性表第inx个元素的位置插入一个元素。成功返回1,失败返回0
{
int i;
if(st->length==st->listsize)
{
printf("线性表已满，插入失败！ ");
return 0;
}
if(inx<1 && inx>st->length+1)
{
printf("插入位置无效！线性表当前数据长度为%d，插入位置必须大于1且不能大于%d！ ",st->length,st->length+1);
return 0;
}
for(i=st->length;i>=inx;i--)
st->elem[i]=st->elem[i-1];
st->elem[inx-1]=num;
st->length++;
return 1;
}
⑥ C语言数据结构具体链表学习，最好有图示
面向对象实现其实也算简单吧 你如果把类和对象理解了 就能很好的去运用面向对象思想了 我java和C#面向对象多学过 给你讲解一下吧 首先 类是一个比较抽象的概念 类是一个对象群体的概括 比如：人类就可以看成一个类 动物类也是一个类 植物类也是一个类 也就是说类是一组对象的抽象概念 而对象呢 就是一个类的特指 比如：人类是一个类 而人类里的张三 张三就是一个对象 这些能理解么？ 我再给你说说类的组成吧 类由属性、方法、构造方法等组成 属性就用来描述一个类的共有特征的 比如人类都有名字、年龄、身高、体重等 这些在类里面都用属性去定义描述，而封装就是为了避免类的使用者在不知情的时候为属性乱赋值 所以把属性私有化，为每个属性提供公有的访问和赋值的方法，也就是get和set方法；再说说方法 方法是一个类的行为 当一个类需要去完成一件事情的时候 就为其定义方法 比如：人都有吃饭的行为 所以在可以定义一个吃法的方法 继承的概念我觉得用一句话就能说清楚：老鼠的儿子会打洞，老鼠一生下来就会打洞 这就是继承自父类的 至于构造方法 那是在一个类去构造生成一个对象时用到的 java中构造一个对象语法是这样的：类名 自定义对象么 =new 类名(); 当这样去new一个对象的时候就会去调用无参构造方法
就这些吧 这都是我个人的理解 希望对你有帮助 记得加分哦 嘻嘻
⑦ 数据结构（C语言版） 图的遍历和拓扑排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等*/
#include<limits.h> /* INT_MAX 等*/
#include<stdio.h> /* EOF(=^Z 或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h 中已定义OVERFLOW 的值为3,故去掉此行*/
typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/
typedef int Boolean; Boolean 是布尔类型,其值是TRUE 或FALSE */
/* .........................*/
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置*/
struct ArcNode *nextarc; /* 指向下一条弧的指针*/
InfoType *info; /* 网的权值指针） */
}ArcNode; /* 表结点*/
typedef struct
{
VertexType data; /* 顶点信息*/
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点*/
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数*/
int kind; /* 图的种类标志*/
}ALGraph;
/* .........................*/
/* .........................*/
/*ALGraphAlgo.cpp 图的邻接表存储(存储结构由ALGraphDef.h 定义)的基本操作*/
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件: 图G 存在,u 和G 中顶点有相同特征*/
/* 操作结果: 若G 中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph &G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4 种图) */
int i,j,k;
int w; /* 权值*/
VertexType va,vb;
ArcNode *p;
printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",&(G.kind));
printf("请输入图的顶点数,边数: ");
scanf("%d,%d",&(G.vexnum),&(G.arcnum));
printf("请输入%d 个顶点的值(<%d 个字符):\n",G.vexnum,MAX_NAME);
for(i=0;i<G.vexnum;++i) /* 构造顶点向量*/
{
scanf("%s",G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
if(G.kind==1||G.kind==3) /* 网*/
printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
else /* 图*/
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for(k=0;k<G.arcnum;++k) /* 构造表结点链表*/
{
if(G.kind==1||G.kind==3) /* 网*/
scanf("%d%s%s",&w,va,vb);
else /* 图*/
scanf("%s%s",va,vb);
i=LocateVex(G,va); /* 弧尾*/
j=LocateVex(G,vb); /* 弧头*/
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if(G.kind==1||G.kind==3) /* 网*/
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 图*/
p->nextarc=G.vertices[i].firstarc; /* 插在表头*/
G.vertices[i].firstarc=p;
if(G.kind>=2) /* 无向图或网,产生第二个表结点*/
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if(G.kind==3) /* 无向网*/
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 无向图*/
p->nextarc=G.vertices[j].firstarc; /* 插在表头*/
G.vertices[j].firstarc=p;
}
}
return OK;
}
void DestroyGraph(ALGraph &G)
{ /* 初始条件: 图G 存在。操作结果: 销毁图G */
int i;
ArcNode *p,*q;
G.vexnum=0;
G.arcnum=0;
for(i=0;i<G.vexnum;++i)
{
p=G.vertices[i].firstarc;
while(p)
{
q=p->nextarc;
if(G.kind%2) /* 网*/
free(p->info);
free(p);
p=q;
}
}
}
VertexType* GetVex(ALGraph G,int v)
{ /* 初始条件: 图G 存在,v 是G 中某个顶点的序号。操作结果: 返回v 的值*/
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vertices[v].data;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* 初始条件: 图G 存在,v 是G 中某个顶点*/
/* 操作结果: 返回v 的第一个邻接顶点的序号。若顶点在G 中没有邻接顶点,则返回-1 */
ArcNode *p;
int v1;
v1=LocateVex(G,v); /* v1 为顶点v 在图G 中的序号*/
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G 存在,v 是G 中某个顶点,w 是v 的邻接顶点*/
/* 操作结果: 返回v 的(相对于w 的)下一个邻接顶点的序号。*/
/* 若w 是v 的最后一个邻接点,则返回-1 */
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v); /* v1 为顶点v 在图G 中的序号*/
w1=LocateVex(G,w); /* w1 为顶点w 在图G 中的序号*/
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1) /* 指针p 不空且所指表结点不是w */
p=p->nextarc;
if(!p||!p->nextarc) /* 没找到w 或w 是最后一个邻接点*/
return -1;
else /* p->adjvex==w */
return p->nextarc->adjvex; /* 返回v 的(相对于w 的)下一个邻接顶点的序号*/
}
Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
void(*VisitFunc)(char* v); /* 函数变量(全局量) */
void DFS(ALGraph G,int v)
{ /* 从第v 个顶点出发递归地深度优先遍历图G。算法7.5 */
int w;
VertexType v1,w1;
strcpy(v1,*GetVex(G,v));
visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
VisitFunc(G.vertices[v].data); /* 访问第v 个顶点*/
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w); /* 对v 的尚未访问的邻接点w 递归调用DFS */
}
void DFSTraverse(ALGraph G,void(*Visit)(char*))
{ /* 对图G 作深度优先遍历。算法7.4 */
int v;
VisitFunc=Visit; /* 使用全局变量VisitFunc,使DFS 不必设函数指针参数*/
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* 访问标志数组初始化*/
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); /* 对尚未访问的顶点调用DFS */
printf("\n");
}
typedef int QElemType; /* 队列类型*/
#include"LinkQueueDef.h"
#include"LinkQueueAlgo.h"
void BFSTraverse(ALGraph G,void(*Visit)(char*))
{/*按广度优先非递归遍历图G。使用辅助队列Q 和访问标志数组visited。算法7.6 */
int v,u,w;
VertexType u1,w1;
LinkQueue Q;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE; /* 置初值*/
InitQueue(Q); /* 置空的辅助队列Q */
for(v=0;v<G.vexnum;v++) /* 如果是连通图,只v=0 就遍历全图*/
if(!visited[v]) /* v 尚未访问*/
{
visited[v]=TRUE;
Visit(G.vertices[v].data);
EnQueue(Q,v); /* v 入队列*/
while(!QueueEmpty(Q)) /* 队列不空*/
{
DeQueue(Q,u); /* 队头元素出队并置为u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w 为u 的尚未访问的邻接顶点*/
{
visited[w]=TRUE;
Visit(G.vertices[w].data);
EnQueue(Q,w); /* w 入队*/
}
}
}
printf("\n");
}
void Display(ALGraph G)
{ /* 输出图的邻接矩阵G */
int i;
ArcNode *p;
switch(G.kind)
{ case DG: printf("有向图\n"); break;
case DN: printf("有向网\n"); break;
case AG: printf("无向图\n"); break;
case AN: printf("无向网\n");
}
printf("%d 个顶点：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("\n%d 条弧(边):\n",G.arcnum);
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
if(G.kind<=1) /* 有向*/
{
printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==DN) /* 网*/
printf(":%d ",*(p->info));
}
else /* 无向(避免输出两次) */
{
if(i<p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==AN) /* 网*/
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("\n");
}
}
/* .........................*/
/* .........................*/
#include "pubuse.h"
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
typedef int InfoType; /* 存放网的权值*/
typedef char VertexType[MAX_NAME]; /* 字符串类型*/
#include"ALGraphDef.h"
#include"ALGraphAlgo.h"
void print(char *i)
{
printf("%s ",i);
}
void main()
{
int i,j,k,n;
ALGraph g;
VertexType v1,v2;
printf("请选择有向图\n");
CreateGraph(g);
Display(g);
printf("深度优先搜索的结果:\n");
DFSTraverse(g,print);
printf("广度优先搜索的结果:\n");
BFSTraverse(g,print);
DestroyGraph(g); /* 销毁图*/
}
⑧ 初学c语言数据结构，求下面图片的每行程序的作用，怎么实现的，多谢
#include <stdio.h>
#include <malloc.h>
#define MAXV 100//最大顶点个数
int visited[MAXV];//全局数组
typedef int InfoType;
typedef struct
{ int edges[MAXV][MAXV];//邻接矩阵
int vexnum,arcnum; //顶点数，弧数
} MGraph;//图的邻接矩阵类型
typedef struct ANode
{ int adjvex; //该弧的终点位置
struct ANode *nextarc; //指向下一条弧的指针
InfoType info; //该弧的相关信息,这里用于存放权值 n
} ArcNode;//弧的结点结构类型
typedef struct Vnode
{ //int data; //顶点信息
ArcNode *firstarc;//指向第一条弧
} VNode;//邻接表头结点的类型
typedef struct
{
VNode adjlist[MAXV];//邻接表
int n,e;//图中顶点数n和边数e
} ALGraph;//图的邻接表类型
void init(MGraph &g);//初始化邻接矩阵
void MatToList(MGraph,ALGraph *&);//将邻接矩阵g转换成邻接表G
void DispAdj(ALGraph *);//输出邻接表G
void DFS(ALGraph *G,int v);//深搜
void BFS(ALGraph *G,int v);//广搜
void main()
{
MGraph g;
g.vexnum=11;g.arcnum=13;
init(g);//初始化邻接矩阵
ALGraph *G=(ALGraph *)malloc(sizeof(ALGraph));
MatToList(g,G);//将邻接矩阵g转换成邻接表G
DispAdj(G);//输出邻接表G
for (int i=0;i<g.vexnum;i++) visited[i]=0;
printf("深度优先生成树:");
DFS(G,3);//从顶点3开始深度搜索
printf("\n");
//////
for (i=0;i<g.vexnum;i++) visited[i]=0;
printf("广度优先生成树:");
BFS(G,3);//从顶点3开始广度搜索
}
void DFS(ALGraph *G,int v)//从顶点v开始深度搜索
{
visited[v]=1;//置已访问标记
ArcNode *p=G->adjlist[v].firstarc;//p指向顶点v的第一条弧的弧头结点
while (p!=NULL)
{
if (visited[p->adjvex]==0)//若p->adjvex顶点未访问,递归访问它
{
printf("<%d,%d> ",v,p->adjvex);//输出生成树的一条边
DFS(G,p->adjvex);//递归函数
}
p=p->nextarc;//p指向顶点v的下一条弧的弧头结点
}
}
void BFS(ALGraph *G,int v)
{
int queue[MAXV],front=0,rear=0; //定义循环队列并初始化
int visited[MAXV]; //定义存放结点的访问标志的数组
for (int i=0;i<G->n;i++) visited[i]=0; //访问标志数组初始化
visited[v]=1; //置已访问标记
queue[rear]=v;//已访问过的顶点v进队
rear=(rear+1)%MAXV;
while (front!=rear)//若队列不空时循环
{
int w=queue[front];//出队并赋给w
front=(front+1)%MAXV;
ArcNode *p=G->adjlist[w].firstarc; //找与顶点w邻接的第一个顶点
while (p!=NULL)
{
if (visited[p->adjvex]==0) //若当前邻接顶点未被访问
{
printf("<%d,%d> ",w,p->adjvex);//输出生成树的一条边
visited[p->adjvex]=1;//置该顶点已被访问的标志
queue[rear]=p->adjvex;//该顶点p的终点进队
rear=(rear+1)%MAXV;
}
p=p->nextarc;//找下一个邻接顶点
}
}
printf("\n");
}
void init(MGraph &g)
{
int i,j;
int A[MAXV][11];
for (i=0;i<g.vexnum;i++)
for (j=0;j<g.vexnum;j++)
A[i][j]=0;
A[0][3]=1;A[0][2]=1;A[0][1]=1;
A[1][5]=1;A[1][4]=1;
A[2][6]=1;A[2][5]=1;A[2][3]=1;
A[3][7]=1;
A[6][9]=1;A[6][8]=1;A[6][7]=1;
A[7][10]=1;
for (i=0;i<g.vexnum;i++)
for (j=0;j<g.vexnum;j++)
A[j][i]=A[i][j];//无向图双向路径对称
for (i=0;i<g.vexnum;i++)
for (j=0;j<g.vexnum;j++)
g.edges[i][j]=A[i][j];
}
void MatToList(MGraph g,ALGraph *&G)//将邻接矩阵g转换成邻接表G
{
int i,j;
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<g.vexnum;i++)//表头节点的指针域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<g.vexnum;i++)//对于邻接矩阵中每个元素
for (j=g.vexnum-1;j>=0;j--)
if (g.edges[i][j]!=0)//邻接矩阵的当前元素不为0---顶点i到j可以走通
{
ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode));//创建一个新的弧节点
p->adjvex=j;//弧节点的指向的终点位置
p->info=g.edges[i][j];//弧节点的长度
p->nextarc=G->adjlist[i].firstarc;//将*p链到表头后
G->adjlist[i].firstarc=p;//更新表头指针//G->adjlist[i]---表头:顶点i连通到可连通的点
}
G->n=g.vexnum;//邻接表G的节点数
G->e=g.arcnum;//弧数
}
void DispAdj(ALGraph *G)//输出邻接表G
{
printf("图G的邻接表:\n");
for (int i=0;i<G->n;i++)//
{
ArcNode *p=G->adjlist[i].firstarc;
if (p!=NULL) printf("%3d: ",i);//输出表头元素
while (p!=NULL)
{
printf("%3d",p->adjvex);//输出表头后链接的元素
p=p->nextarc;
}
printf("\n");
}
}
⑨ c语言常见的数据结构有哪些
1、线性数据结构
元素之间一般存在元素之间存在一对一关系，是最常用的一类数据结构，典型的有：数组、栈、队列和线性表。
2、树形结构
结点间具有层次关系，每一层的一个结点能且只能和上一层的一个结点相关，但同时可以和下一层的多个结点相关，称为“一对多”关系，常见类型有：树、堆。
3、图形结构
在图形结构中，允许多个结点之间相关，称为“多对多”关系。
(1)线性数据结构：元素之间一般存在元素之间存在一对一关系，是最常用的一类数据结构，典型的有：数组、栈、队列和线性表
(2)树形结构：结点间具有层次关系，每一层的一个结点能且只能和上一层的一个结点相关，但同时可以和下一层的多个结点相关，称为“一对多”关系，常见类型有：树、堆
(3)图形结构：在图形结构中，允许多个结点之间相关，称为“多对多”关系
⑩ 数据结构代码（用C语言） 图的遍历操作
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等*/
#include<limits.h> /* INT_MAX 等*/
#include<stdio.h> /* EOF(=^Z 或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h 中已定义OVERFLOW 的值为3,故去掉此行*/
typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/
typedef int Boolean; Boolean 是布尔类型,其值是TRUE 或FALSE */
/* .........................*/
#define MAX_VERTEX_NUM 20
typedef enumGraphKind; /* */
typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置*/
struct ArcNode *nextarc; /* 指向下一条弧的指针*/
InfoType *info; /* 网的权值指针） */
}ArcNode; /* 表结点*/
typedef struct
{
VertexType data; /* 顶点信息*/
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点*/
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数*/
int kind; /* 图的种类标志*/
}ALGraph;
/* .........................*/
/* .........................*/
/*ALGraphAlgo.cpp 图的邻接表存储(存储结构由ALGraphDef.h 定义)的基本操作*/
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件: 图G 存在,u 和G 中顶点有相同特征*/
/* 操作结果: 若G 中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph &G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4 种图) */
int i,j,k;
int w; /* 权值*/
VertexType va,vb;
ArcNode *p;
printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",&(G.kind));
printf("请输入图的顶点数,边数: ");
scanf("%d,%d",&(G.vexnum),&(G.arcnum));
printf("请输入%d 个顶点的值(<%d 个字符):\n",G.vexnum,MAX_NAME);
for(i=0;i<G.vexnum;++i) /* 构造顶点向量*/
{
scanf("%s",G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
if(G.kind==1||G.kind==3) /* 网*/
printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
else /* 图*/
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for(k=0;k<G.arcnum;++k) /* 构造表结点链表*/
{
if(G.kind==1||G.kind==3) /* 网*/
scanf("%d%s%s",&w,va,vb);
else /* 图*/
scanf("%s%s",va,vb);
i=LocateVex(G,va); /* 弧尾*/
j=LocateVex(G,vb); /* 弧头*/
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if(G.kind==1||G.kind==3) /* 网*/
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 图*/
p->nextarc=G.vertices[i].firstarc; /* 插在表头*/
G.vertices[i].firstarc=p;
if(G.kind>=2) /* 无向图或网,产生第二个表结点*/
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if(G.kind==3) /* 无向网*/
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 无向图*/
p->nextarc=G.vertices[j].firstarc; /* 插在表头*/
G.vertices[j].firstarc=p;
}
}
return OK;
}
void DestroyGraph(ALGraph &G)
{ /* 初始条件: 图G 存在。操作结果: 销毁图G */
int i;
ArcNode *p,*q;
G.vexnum=0;
G.arcnum=0;
for(i=0;i<G.vexnum;++i)
{
p=G.vertices[i].firstarc;
while(p)
{
q=p->nextarc;
if(G.kind%2) /* 网*/
free(p->info);
free(p);
p=q;
}
}
}
VertexType* GetVex(ALGraph G,int v)
{ /* 初始条件: 图G 存在,v 是G 中某个顶点的序号。操作结果: 返回v 的值*/
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vertices[v].data;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* 初始条件: 图G 存在,v 是G 中某个顶点*/
/* 操作结果: 返回v 的第一个邻接顶点的序号。若顶点在G 中没有邻接顶点,则返回-1 */
ArcNode *p;
int v1;
v1=LocateVex(G,v); /* v1 为顶点v 在图G 中的序号*/
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G 存在,v 是G 中某个顶点,w 是v 的邻接顶点*/
/* 操作结果: 返回v 的(相对于w 的)下一个邻接顶点的序号。*/
/* 若w 是v 的最后一个邻接点,则返回-1 */
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v); /* v1 为顶点v 在图G 中的序号*/
w1=LocateVex(G,w); /* w1 为顶点w 在图G 中的序号*/
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1) /* 指针p 不空且所指表结点不是w */
p=p->nextarc;
if(!p||!p->nextarc) /* 没找到w 或w 是最后一个邻接点*/
return -1;
else /* p->adjvex==w */
return p->nextarc->adjvex; /* 返回v 的(相对于w 的)下一个邻接顶点的序号*/
}
Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
void(*VisitFunc)(char* v); /* 函数变量(全局量) */
void DFS(ALGraph G,int v)
{ /* 从第v 个顶点出发递归地深度优先遍历图G。算法7.5 */
int w;
VertexType v1,w1;
strcpy(v1,*GetVex(G,v));
visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
VisitFunc(G.vertices[v].data); /* 访问第v 个顶点*/
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w); /* 对v 的尚未访问的邻接点w 递归调用DFS */
}
void DFSTraverse(ALGraph G,void(*Visit)(char*))
{ /* 对图G 作深度优先遍历。算法7.4 */
int v;
VisitFunc=Visit; /* 使用全局变量VisitFunc,使DFS 不必设函数指针参数*/
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* 访问标志数组初始化*/
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); /* 对尚未访问的顶点调用DFS */
printf("\n");
}
typedef int QElemType; /* 队列类型*/
#include"LinkQueueDef.h"
#include"LinkQueueAlgo.h"
void BFSTraverse(ALGraph G,void(*Visit)(char*))
{/*按广度优先非递归遍历图G。使用辅助队列Q 和访问标志数组visited。算法7.6 */
int v,u,w;
VertexType u1,w1;
LinkQueue Q;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE; /* 置初值*/
InitQueue(Q); /* 置空的辅助队列Q */
for(v=0;v<G.vexnum;v++) /* 如果是连通图,只v=0 就遍历全图*/
if(!visited[v]) /* v 尚未访问*/
{
visited[v]=TRUE;
Visit(G.vertices[v].data);
EnQueue(Q,v); /* v 入队列*/
while(!QueueEmpty(Q)) /* 队列不空*/
{
DeQueue(Q,u); /* 队头元素出队并置为u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w 为u 的尚未访问的邻接顶点*/
{
visited[w]=TRUE;
Visit(G.vertices[w].data);
EnQueue(Q,w); /* w 入队*/
}
}
}
printf("\n");
}
void Display(ALGraph G)
{ /* 输出图的邻接矩阵G */
int i;
ArcNode *p;
switch(G.kind)
{ case DG: printf("有向图\n"); break;
case DN: printf("有向网\n"); break;
case AG: printf("无向图\n"); break;
case AN: printf("无向网\n");
}
printf("%d 个顶点：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("\n%d 条弧(边):\n",G.arcnum);
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
if(G.kind<=1) /* 有向*/
{
printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==DN) /* 网*/
printf(":%d ",*(p->info));
}
else /* 无向(避免输出两次) */
{
if(i<p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==AN) /* 网*/
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("\n");
}
}
/* .........................*/
/* .........................*/
#include "pubuse.h"
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
typedef int InfoType; /* 存放网的权值*/
typedef char VertexType[MAX_NAME]; /* 字符串类型*/
#include"ALGraphDef.h"
#include"ALGraphAlgo.h"
void print(char *i)
{
printf("%s ",i);
}
void main()
{
int i,j,k,n;
ALGraph g;
VertexType v1,v2;
printf("请选择有向图\n");
CreateGraph(g);
Display(g);
printf("深度优先搜索的结果:\n");
DFSTraverse(g,print);
printf("广度优先搜索的结果:\n");
BFSTraverse(g,print);
DestroyGraph(g); /* 销毁图*/
}