数据结构图的存储结构及
- 格式:doc
- 大小:135.50 KB
- 文档页数:16
2007 C C C 语言的特点,简单的C 程序介绍,C 程序的上机步骤。
1 、算法的概念2、简单的算法举例3、算法的特性4、算法的表示(自然语言、流程图、N-S 图表示) 1 、 C 的数据类型、常量与变星、整型数据、实型数据、字符型数据、字符串常量。
2、 C 的运算符运算意义、优先级、结合方向。
3、算术运算符和算术表达式,各类数值型数据间的混合运算。
4、赋值运算符和赋值表达式。
5、逗号运算符和逗号表达式。
1 、程序的三种基本结构。
2、数据输入输出的概念及在C 语言中的实现。
字符数据的输入输出,格式输入与输出。
1 、关系运算符及其优先级,关系运算和关系表达式。
2、逻辑运算符及其优先级,逻辑运算符和逻辑表达式。
3、if语句。
if语句的三种形式,if语句的嵌套,条件运算符。
4、switch 语句. 1 、while 语句。
2、do/while 语句。
3、for 语句。
4、循环的嵌套。
5、break 语句和continue 语句。
1 、一维数组的定义和引用。
2、二维数组的定义和引用。
3、字符数组。
4、字符串与字符数组。
5、字符数组的输入输出。
6、字符串处理函数1 、函数的定义。
2、函数参数和函数的值,形式参数和实际参数。
3、函数的返回值。
4、函数调用的方式,函数的声明和函数原型。
5、函数的嵌套调用。
6、函数的递归调用。
7、数组作为函数参数。
8、局部变量、全局变量的作用域。
9、变量的存储类别,自动变星,静态变量。
1 、带参数的宏定义。
2、“文件包含”处理。
1 、地址和指针的概念。
2、变量的指针和指向变量的指针变量。
3、指针变量的定义和引用。
4、指针变量作为函数参数。
5、数组的指针和指向数组的指针变量。
6、指向数组元素的指针。
7、通过指针引用数组元素。
8、数组名作函数参数。
9、二维数组与指针。
1 0、指向字符串的指针变星。
字符串的指针表示形式,字符串指针作为函数参数。
11 、字符指针变量和字符数组的异同。
实验6.1实现图的存储和遍历一,实验目的掌握图的邻接矩阵和邻接表存储以及图的邻接矩阵存储的递归遍历。
二,实验内容6.1实现图的邻接矩阵和邻接表存储编写一个程序,实现图的相关运算,并在此基础上设计一个主程序,完成如下功能:(1)建立如教材图7.9所示的有向图G的邻接矩阵,并输出。
(2)由有向图G的邻接矩阵产生邻接表,并输出。
(3)再由(2)的邻接表产生对应的邻接矩阵,并输出。
6.2 实现图的遍历算法(4)在图G的邻接矩阵存储表示基础上,输出从顶点V1开始的深度优先遍历序列(递归算法)。
(5)利用非递归算法重解任务(4)。
(6)在图G的邻接表存储表示基础上,输出从顶点V1开始的广度优先遍历序列。
三,源代码及结果截图#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<malloc.h>#define MAX_VERTEX_NUM 20typedef char VRType;typedef int InfoType; // 存放网的权值typedef char VertexType; // 字符串类型typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网}/*建立有向图的邻接矩阵*/typedef struct ArcCell{VRType adj;//VRType是顶点关系类型,对无权图用1或0表示是否相邻;对带权图则为权值类型InfoType *info; //该弧相关信息的指针(可无)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM];//顶点向量AdjMatrix arcs;//邻接矩阵int vexnum,arcnum;;//图的当前顶点数和弧数GraphKind kind;//图的种类标志}MGraph;/* 顶点在顶点向量中的定位*/int LocateVex(MGraph &M,VRType v1){int i;for(i=0;i<M.vexnum;i++)if(v1==M.vexs[i])return i;return -1;}void CreateGraph(MGraph &M)//建立有向图的邻接矩阵{int i,j,k,w;VRType v1,v2;M.kind=DN;printf("构造有向网:\n");printf("\n输入图的顶点数和边数(以空格作为间隔):");scanf("%d%d",&M.vexnum,&M.arcnum);printf("输入%d个顶点的值(字符):",M.vexnum);getchar();for(i=0;i<M.vexnum;i++) //输入顶点向量{scanf("%c",&M.vexs[i]);}printf("建立邻接矩阵:\n");for(i=0;i<M.vexnum;i++)for(j=0;j<M.vexnum;j++){M.arcs[i][j].adj=0;M.arcs[i][j].info=NULL;}printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");for(k=0;k<M.arcnum;++k)// 构造表结点链表{cin>>w>>v1>>v2;i=LocateVex(M,v1);j=LocateVex(M,v2);M.arcs[i][j].adj=w;}}//按邻接矩阵方式输出有向图void PrintGraph(MGraph M){int i,j;printf("\n输出邻接矩阵:\n");for(i=0; i<M.vexnum; i++){printf("%10c",M.vexs[i]);for(j=0; j<M.vexnum; j++)printf("%2d",M.arcs[i][j].adj);printf("\n");}}// 图的邻接表存储表示typedef struct ArcNode{int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc; // 指向下一条弧的指针InfoType *info; // 网的权值指针)}ArcNode; // 表结点typedef struct VNode{VertexType data; // 顶点信息ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];// 头结点typedef struct{AdjList vertices;int vexnum,arcnum; // 图的当前顶点数和弧数int kind; // 图的种类标志}ALGraph;void CreateMGtoDN(ALGraph &G,MGraph &M){//由有向图M的邻接矩阵产生邻接表int i,j;ArcNode *p;G.kind=M.kind;G.vexnum=M.vexnum;G.arcnum=M.arcnum;for(i=0;i<G.vexnum;++i){//构造表头向量G.vertices[i].data=M.vexs[i];G.vertices[i].firstarc=NULL;//初始化指针}for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)if(M.arcs[i][j].adj){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.vertices[i].firstarc;p->info=M.arcs[i][j].info;G.vertices[i].firstarc=p;}}void CreateDNtoMG(MGraph &M,ALGraph &G){ //由邻接表产生对应的邻接矩阵int i,j;ArcNode *p;M.kind=GraphKind(G.kind);M.vexnum=G.vexnum;M.arcnum=G.arcnum;for(i=0;i<M.vexnum;++i)M.vexs[i]=G.vertices[i].data;for(i=0;i<M.vexnum;++i){p=G.vertices[i].firstarc;while(p){M.arcs[i][p->adjvex].adj=1;p=p->nextarc;}//whilefor(j=0;j<M.vexnum;++j)if(M.arcs[i][j].adj!=1)M.arcs[i][j].adj=0;}//for}//输出邻接表void PrintDN(ALGraph G){int i;ArcNode *p;printf("\n输出邻接表:\n");printf("顶点:\n");for(i=0;i<G.vexnum;++i)printf("%2c",G.vertices[i].data);printf("\n弧:\n");for(i=0;i<G.vexnum;++i){p=G.vertices[i].firstarc;while(p){printf("%c→%c(%d)\t",G.vertices[i].data,G.vertices[p->adjvex].data,p->info);p=p->nextarc;}printf("\n");}//for}int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)void(*VisitFunc)(char* v); // 函数变量(全局量)// 从第v个顶点出发递归地深度优先遍历图G。
数据结构的存储⽅式以及优缺点在计算机中,数据的存储结构可以采⽤如下四种⽅法来实现。
1、顺序存储⽅式:顺序存储⽅式就是在⼀块连续的存储区域⼀个接着⼀个的存放数据。
顺序存储⽅式把逻辑上相邻的节点存储在物理位置放在相邻的存储单元⾥,节点间的逻辑关系由存储单元的邻接关系来体现。
顺序存储⽅式也称为顺序存储结构,⼀般采⽤数组或结构数组来描述。
2、链接存储⽅式:链接存储⽅式⽐较灵活,不要求逻辑上相邻的节点在物理位置上相邻,节点间的逻辑关系由附加的引⽤字段来表⽰。
⼀个节点的引⽤字段往往指向下⼀个节点的存放位置。
链接存储⽅式也成为链式存储结构。
3、索引存储⽅式:索引存储⽅式是采⽤附加的索引表的⽅式来存储节点信息的⼀种存储⽅式。
索引表由若⼲索引项组成。
索引存储⽅式中索引项的⼀般形式为(关键字、地址)。
其中,关键字是能够唯⼀标识⼀个节点的数据项。
索引存储⽅式还可以细分为如下两类。
稠密索引:这种⽅式中每个节点在索引表中都有⼀个索引项,其中索引项的地址知识节点所在的存储位置。
稀疏索引:这种⽅式中⼀组节点在索引表中只对应⼀个索引项。
其中,索引项的地址指⽰⼀组节点的起始存储位置。
4、散列存储⽅式:散列存储⽅式是根据节点的关键字直接计算出该节点的存储地址的⼀种存储⽅式。
1、顺序存储优点:在结点等长时可以随机存取存储密度⾼节省存储空间⽤结点的物理次序反映结点之间的逻辑关系缺点:插⼊和删除结点时要移动⼤量的结点必须静态分配连续空间2、链接存储优点:插⼊和删除⽐较灵活,不需要⼤量移动结点动态分配空间⽐较灵活,不需要预先申请最⼤的连续空间缺点:增加指针的空间开销检索必须沿链进⾏,不能随机存取。
数据结构图的存储结构及基本操作1.实验目的通过上机实验进一步掌握图的存储结构及基本操作的实现。
2.实验内容与要求要求:⑴能根据输入的顶点、边/弧的信息建立图;⑵实现图中顶点、边/弧的插入、删除;⑶实现对该图的深度优先遍历;⑷实现对该图的广度优先遍历。
备注:单号基于邻接矩阵,双号基于邻接表存储结构实现上述操作。
3.数据结构设计逻辑结构:图状结构存储结构:顺序存储结构、链式存储结构4.算法设计#include <stdio.h> #include <string.h> #include <stdlib.h> #defineMAX_VERTEX_NU M 20 typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;}ArcNode;typedef struct VNode {char data[2]; //顶点就设置和书上V1等等一样吧ArcNode *firstarc; }VNode,AdjList[MAX _VERTEX_NUM]; typedef struct{AdjList vertices;int vexnum,arcnum; }ALGraph;typedef struct{intdata[MAX_VERTEX_ NUM+10];int front;int rear;}queue; intvisited[MAX_VERTE X_NUM];queue q;int main(){ALGraph G;intCreateUDG(ALGraph &G);intDeleteUDG(ALGraph &G);intInsertUDG(ALGraph &G);void BFSTraverse(ALGrap h G, int (*Visit)(ALGraphG,ArcNode v));intPrintElement(ALGrap h G,ArcNode v);void menu();void depthfirstsearch(ALG raph *g,int vi);voidtravel(ALGraph *g); void breadfirstsearch(ALG raph *g);int i;G.arcnum = G.vexnum = 0;while(1){menu();do{printf ( "请输入要进行的操作\n" );scanf("%d",&i);if (i<1||i>6)printf("错误数字,请重新输入\n");}while (i<1||i>6);switch (i){case 1: CreateUDG(G); system("pause"); system("cls"); break;case 2: DeleteUDG(G); system("pause"); system("cls"); break;case 3: InsertUDG(G); system("pause"); system("cls"); break;case 4: travel(&G);system("pause"); system("cls"); break;case 5: breadfirstsearch(&G); system("pause"); system("cls"); break;case 6: exit(0); break;}}return 1;}void enterqueue(int v) {q.data[q.rear]=v;q.rear++;}int deletequeue() {int t;t=q.data[q.front];q.front++;return(t);}int empty(){if(q.front==q.rear)return 1;return 0;}intLocateVex(ALGraph G,char node[2]){int i;for(i = 0 ; i < G.vexnum ; i++){if(strcmp(G.vertices[ i].data,node)==0)return i;}return -1;}intCreateUDG(ALGraph &G){intLocateVex(ALGraph G,char node[2]);voidPrintUDG(ALGraph G);int i,j,k;charnode1[2],node2[2]; ArcNode *p,*q;printf("请输入顶点数和弧数\n");printf("例如:5,6\n");scanf("%d,%d",&G .vexnum,&G.arcnum); printf("请输入各顶点\n");for(i = 0 ; i < G.vexnum ; i++){printf("第%d个\n",i+1);scanf("%s",&G.vert ices[i]);G.vertices[i].firstarc = NULL;}//这里开始构造边printf("请输入边的信息\n");printf("例如:v1 v2\n");for(i = 0 ; i < G.arcnum ; i++){printf("第%d条边\n",i+1);scanf("%s %s",&n ode1,&node2);j = LocateVex(G,node1);k = LocateVex(G,node2);p = (ArcNode *)malloc(sizeof(ArcNo de));q = (ArcNode *)malloc(sizeof(ArcNo de));p->adjvex = k;q->adjvex = j;p->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p;q->nextarc = G.vertices[k].firstarc;G.vertices[k].firstar c = q;}PrintUDG(G); return 1;}intDeleteUDG(ALGraph &G){int i,j;ArcNode *p,*q; char node[2];intLocateVex(ALGraph G,char node[2]);voidPrintUDG(ALGraph G);if(G.arcnum == 0) {printf("请先生成图\n");return 0;}printf("请输入要删除的节点\n");scanf("%s",&node) ;i = LocateVex(G,node);if(i == -1){printf("无此节点\n");return 0;}else{G.vexnum--;if((p = q = G.vertices[i].firstarc) ! = NULL){G.arcnum--;p = p->nextarc;G.vertices[i].firstarc = p;free(q);q = p;while(p != NULL){G.arcnum--;p = p->nextarc;G.vertices[i].firstarc = p;free(q);q = p;}}for(j = 0 ; j < G.vexnum ; j++ ){if(j >= i){strcpy(G.vertices[j]. data , G.vertices[j+1].data);G.vertices[j].firstarc = G.vertices[j+1].firstarc ;}if(G.vertices[j].firsta rc->nextarc != NULL){p = G.vertices[j].firstarc;q = p->nextarc;if(p->adjvex == i){G.vertices[j].firstarc = q;p = q;q = q->nextarc;continue;}elseif(p->adjvex > i)p->adjvex--;while(q != NULL){if(q->adjvex == i){p->nextarc = q->nextarc;free(q);q = p->nextarc;}elseif(q->adjvex > i)q->adjvex--;else{p = p->nextarc;q = q->nextarc;}}}elseif( (G.vertices[j].firstar c->nextarc == NULL) &&(G.vertices[j].firstarc ! = NULL) )if( G.vertices[j].first arc->adjvex == i ){G.vertices[j].firstarc = NULL;}}}PrintUDG(G); return 1;}intInsertUDG(ALGraph &G){//默认一次插入一个节点吧,不然太麻烦int i,j,k,l;charnode1[2],node2[2]; ArcNode *p,*q;intLocateVex(ALGraph G,char node[2]);voidPrintUDG(ALGraph G);if(G.arcnum == 0) {printf("请先生成图\n");return 0;}printf("请输入插入节点的名称\n"); printf("WARNING:绝不可以和之前的节点重名!\n");scanf("%s",&G.vert ices[G.vexnum].data);G.vertices[G.vexnu m].firstarc = NULL; printf("请输入需要插入的边的数目\n"); scanf("%d",&i); G.arcnum += i; G.vexnum++;printf("请输入边的信息\n");printf("例如:v6 v2\n");printf("WARNING:一定要包含刚加入的节点名称!\n");for(j = 0 ; j < i ; j++) {printf("第%d条边\n",j+1);scanf("%s %s",&n ode1,&node2);l = LocateVex(G,node1);k = LocateVex(G,node2);p = (ArcNode *)malloc(sizeof(ArcNo de));q = (ArcNode *)malloc(sizeof(ArcNo de));p->adjvex = k;q->adjvex = l;p->nextarc = G.vertices[l].firstarc;G.vertices[l].firstarc = p;q->nextarc = G.vertices[k].firstarc;G.vertices[k].firstar c = q;}PrintUDG(G); return 1;}void depthfirstsearch(ALG raph *g,int vi){ArcNode *rear;printf("%s\t",g->verti ces[vi].data);visited[vi]=1;rear=g->vertices[vi].fir starc;while((rear!=NULL)& &(!visited[rear->adjve x])){depthfirstsearch(g,rear ->adjvex);rear=rear->nextarc;}}void travel(ALGraph *g) {int v;for(v=0;v<g->vexnum; v++)if(!visited[v])depthfirstsearch(g,v); }void breadfirstsearch(ALG raph *g){int v,t,i;ArcNode *rear; for(i = 0 ; i <g->vexnum ; i++)visited[i] = 0;for(v=0;v<g->vexnum; v++){if(!visited[v]){printf("%s",g->vertic es[v].data);visited[v]=1;enterqueue(v);}while(!empty()){t=deletequeue();rear=g->vertices[t].firs tarc;while((rear!=NULL)& &(!visited[rear->adjve x])){printf("%s\t",g->verti ces[rear->adjvex].data );visited[rear->adjvex]= 1;enterqueue(rear->adjv ex);rear=rear->nextarc;}}}}void menu(){printf("******************************* **************\n"); printf("*作者:Dick *\n");printf("* 信计1001 xxxxxxxxxx*\n");printf("************ *********MENU**** ****************\n") ;printf("1 建立无向图\n");printf("2 删除图中节点\n");printf("3 插入节点\n");printf("4 深度优先遍历图\n");printf("5 广度优先遍历图\n");printf("6 退出程序\n");}voidPrintUDG(ALGraph G){int i;ArcNode *p;for(i = 0 ; i < G.vexnum ; i++){if(G.vertices[i].firsta rc != NULL){printf("与节点%s相邻的节点为:\n",G .vertices[i].dat a); p= G.vertices[i].firstarc; while(p != NULL) {printf("%s\t",G.ver tices[p->adjvex].data); p =p->nextarc; }printf("\n");}elseprintf("无与节点%s 相邻的节点\n",G .vertices[i].data); } }5. 测试结果图一:菜单项图一:菜单项。