2019-07-23 20:38:50 qq_45067278 阅读数 710
  • 数据结构与算法在实战项目中的应用

    该视频教程教大家将学到的数据结构与算法知识应用到实际项目开发中,真正的做到学以致用,理论联系实际,课程会从基本的数据结构算法讲起,结合着实际项目开发,由浅入深,更加贴近实战,让学习者真正的掌握算法应用,可以在工作中直接将其应用到项目开发中。

    8087 人正在学习 去看看 CSDN讲师

图:元素之间存在多对多关系(线性表的元素之间存在前驱和后继,树的元素之间存在父子关系,图的任意元素之间都有可能存在关系)。
由顶点的有穷非空集合和顶点之间边的集合组成。
在图型数据结构中,数据被称为顶点,数据之间的关系补称为边。
在图中不允许出现没有点,但可以没有边。
G(V,E),V表示顶点的集合,E表示边的集合。
各种图的定义:
无向图:顶点与顶点之间没有方向,这种边称为无向边,边用无向序偶对表示(v,v1)。
V={A,B,C,D} E={(A,B),(B,C),(C,D),(D,A),(A,C)}
在无向图中,如果任意两个顶之间都存在边,这种图称为无向完全图,那么这种图的边数为,n*(n-1)/2。

有向图:若顶点之间有方向,这种边称为有向边,也叫弧,用有序偶对表示<v,v1>,v1叫作弧头,v叫作弧尾。
注意:若不存在顶点到自身和边,也不存在重复出现的边这叫种图叫简单图,数据结构课程中讨论的都是简单图。

在有向图中如果任意两个顶点为之间存在方向相反的两条弧,这种图叫作有向完全图。

图中有很少边或弧的图叫稀疏图,反之叫稠密图。

如果图中的边或弧有相关的数据,数据称为权,这种图也叫网(带权图)。
如果G(v,E)和G1(v1,E1),存在V>=V1且,E>=E1,那么G1是G的子图。

顶点与边的关系:
顶点的度:指的是顶点相关联的边或弧的条目数,有向图又分为入出度和入度。
入度:其它顶点到该顶点的弧的条目数。
出度:从该点出发到其它顶点的弧的条目数。
顶点序列:从一个顶点到另一个顶的路径,路径长度指的是路径上的边或弧的条目数。

边通图相关术语:
在无向图中,在顶点v到v1之间有路径,则称v到v1之间是连通的,如果任意两个顶点都是连通的,那么这种图称为连通图。
无向图中的极大连通子图称为连通分量:
1、必须是子图
2、子图必须是连通的
3、连通子图含有极大的顶点数
在有向图中,任意顶点之间都存在路径,这种图叫强连通图。
有向图中的极大连通子图称为有向的强连通分量。

在有向图中如果有一个顶的入度为0,其它顶点的入度均为1,则是一棵有向树。

图的存储结构:
图的存储主要是两个方面:顶点,边
阾接矩阵:
一个一维数组(顶点)和一个两维数组(边、弧)组成。
二维数组i,i位置都是0,如果是无向图则数组对称(左上到右下的对角线为轴)。
优点:
1、非常容易判定两顶点之间是否有边
2、非常容易计算任意顶的入度和出度
3、非常容易统计阾接点
缺点:如果存储稀疏图,会在学浪费存储空间
阾接表:
由顶点表 边表组成。
顶点 下一个阾接点地址 项点下标|下一个阾接点地址
A -> [1] -> [3]-> NULL []
B -> [2]->NULL
C -> [4]-> [3]-> NULL
D
E
优点:
1、节省存储空间
2、非常容易计算出度
缺点:不方便计算入度。
十字链表:由于阾接表不能同时兼顾出度和入度,因此我们修改阾接的边表结构,使用既存储入度也存储出度,这种表就叫十字链表。
阾接多重表:由于遍历表是需要一些删除边操作,而阾接表在删除边时非常麻烦,因此就设计出的阾接多重表。
边集数组:由两个一维数组构成,一个存储顶点的信息,另一个存储边的信息(它的每个数据元素都由一条边的起点到终点的下标和权组成),这种存储结构更侧重于边的相关操作(路径、路径长度、最短路径),而统计顶的度需要扫描整个数组,效率不高。

图的遍历:
注意:图的遍历结果无论是深度优先还是广度优先都不是唯一的。
深度优先:类似树的前序遍历。
广度优先:类似树的层序遍历,与树一样也需要使用队列配合。

2019-06-28 20:48:32 weixin_41447267 阅读数 359
  • 数据结构与算法在实战项目中的应用

    该视频教程教大家将学到的数据结构与算法知识应用到实际项目开发中,真正的做到学以致用,理论联系实际,课程会从基本的数据结构算法讲起,结合着实际项目开发,由浅入深,更加贴近实战,让学习者真正的掌握算法应用,可以在工作中直接将其应用到项目开发中。

    8087 人正在学习 去看看 CSDN讲师

 实习题目与要求

  • 所选题目

大数运算——计算n的阶乘(n>=20)

 

  • 功能要求

程序需能实现一定范围内n值的阶乘计算,并且结果精确

 

 需求分析

  • 问题描述

利用链表数据结构设计程序完成n阶乘的运算及输出

  1. 累计运算的中间结果和最终的计算结果的数据类型要求是整型
  2. 需设计合适的存储结构,要求每个元素或结点最多存储数据的3位数值
  3. 基于设计的存储结构实现乘法操作,要求从键盘上输入n值;在屏幕上显示最终计算结果

 

  • 系统环境

系统:Windows 10

编译器:Visual Studio

 

 概要设计

  • 数据结构设计
  1. 逻辑结构:因为本程序希望数据成员之间是一对一的关系,以便于进行数值运算,故采用线性结构
  2. 物理结构:因为本程序所涉及数值运算较大,所以采用链式结构
  • 存储结构设计

由题目要求可知,程序将进行较大数值的计算、更新、输出等操作,所以一般数据类型无法满足运算条件,且静态存储结构也不符题意,故选择动态的双重链表数据结构

  • 算法设计

本程序的重点即在算法设计上,现以日常笔算为例介绍数值运算的主要思想

  1. 6! = 120 * 6

    2.8! = 5040 * 8

3.11! = 3628800 * 11

由图可知,每次结果的个位数是由上一次中间结果的个位数与阶乘元素的乘积决定的,同时由实际计算结果考虑是否进位,进而影响下一位的结果。所以,中间结果的每一位数都是由上一次中间结果的该位数与阶乘元素的乘积加上前一位数的进位决定的。以此,本程序设计将链表中的每个元素只存储中间运算结果的一位数,并且在不断更新中间结果的同时延长链表。

  • 模块设计

由于题目只要求输出所求数值的阶乘,故将此作为一个功能,仅设计单一函数

void Bigshu()并由主函数调用。

 详细设计

  • 函数成员设计

定义结构体struct Data 含有一整型数据,两个指向该结构体类型的指针

 

定义运算函数 void Big shu()

接收所求数值,阶乘运算,建立链表,输出结果都由该函数实现

 

主函数 int main()

负责调用运算函数 void Bigshu()

 

(二)数据成员设计

在运算数值中间结果,建立、延长链表的过程中,各数据成员结构如图所示。由于双重链表结构的特殊性,该链表的两端同时作为头结点和尾结点,两端的结点分别有一指针指向NULL并且分别有两个表头指向两端结点,而其余中间结点则含有一个元素域,两个指针域。这样的结构便于从任一一端表头将链表进行输出。

(三)界面设计

界面设计如图所示,用户输入需要计算阶乘的数值,并且可以循环调用程序

 

 调试分析

  • 设计回顾

1.一个元素存几位数值?

若要用链表进行大数值的运算,关键之处在于中间结果的存储和计算,由于题目要求,则元素存储的数值个数越多,计算范围越小。而且,当元素存储两位及以上的数值时,使用链表对其进行精确调用、计算、处理的难度较大,于是最终选择一个元素结点只存储一位数值的方式进行阶乘运算。

2.如何设计有效及时的进位?

初次调试时发现,原版的代码存在漏洞:每循环一次即为一位位数赋值,开辟一个新的元素结点,导致运算结果完全错误。而后经过对算法的重新解读才意识到,只有当前中间结果的最高位都被赋值完后仍需进位时才应再次开辟新的元素结点,以存储新位数上的值。

原版算法:

新版算法:

如此单循环体分解为两个循环体的设计才更为科学合理,更为符合实际运算过程

3.设计循环调用,增强程序实用性

在程序的开头设计一个简单的整形数据作为循环“开关”,在程序结尾处作相应处理,虽然只是一个小设计,但避免了用户需不断调用程序时进行的琐碎的操作,增强了程序的实用性。

  • 设计分析

本程序采用双重链表处理数值,以边进行阶乘运算边延长链表的方式同时对数值运算和数据结构两方面进行处理,最后在尾结点再设立表头,从尾结点到原始头结点的顺序将结果输出。现对程序总结出以下特点。

  1. 双重链表的调用

如果只是采用单链表的形式,也能实现数值的存储、运算等操作,得到最终正确的阶乘结果,可是该结果是倒序存储于链表之中,需要从尾结点至头结点反向输出各元素存储的数值才行。

如果为了顾及最终输出结果,即以尾结点存储个位数值,以头结点存储最高位数值的话,则将大大增加程序的设计难度,以另一种全新的算法方可实现;

此程序算法曾以数组形式进行过实现,同样切实可行。虽然静态数组结构的劣势在于处理阶乘范围受限,但便捷之处在于调用方便,不必像链表只能采用链式调用;

于是综上对两者之间的考虑,决定调用双重链表的数据结构,既是为了适应算法,也是为了简化程序的复杂程度。

 

     2.不采用模块化函数实现程序

由于程序算法本身的要求,对链表数值的运算和对链表结构的设计两种操作结合紧密,个人认为如果将程序功能细分,采用模块化函数实现其不同功能反而会将问题复杂化,不必为模块化处理形式而进行模块化处理。

 

  • 算法时间复杂度和空间复杂度分析

算法主要循环体如图所示

设n为输入阶乘数,m为链表算法共需开辟的结点数

时间复杂度为:T(n) = n * m!

空间复杂度为:m

 

  • 算法改进

本程序为本组能想到并能实现题目要求的最简化算法

 使用说明

用户只需输入阶乘数,而后按用户界面选择是否需要重复调用程序即可

测试结果

  1. 测试数据

20!= 2432902008176640000

30!= 265252859812191058636308480000000

如图,测试结果正确

 

2.特殊阶乘&小数阶乘

为了验证程序严整性,以特殊数“0”及各结果为个数的小数对其进行检验,结果依旧正确

  1. 更大的数

这里展现的是50!100!500!1000!的运算结果,结果依旧正确。

4.最大的数

受整型数据的处理范围限制,为了不使中间结果在计算过程中溢出,结合算法来看,3640!是理论上此程序所能计算出数值最大的且结果精确的阶乘。

 源程序代码

#include<stdio.h>
#include<stdlib.h>
#define L2 sizeof(struct Data)
	struct Data           //定义结构体Data,含整型num存储数值,两个指针next1、next2以满足双链表的链接需求
{
	int num;
	struct Data *next1;   //next1指针为正序指向
	struct Data *next2;   //next2指针为逆序指向
};

void Bigshu ()
{
	struct Data *head1, *head2, *p, *p1, *p2, *p3;   //定义struct Data型指针,其中head1、head2为双链表两个表头
	int i, n, zhong, jin, m = 1;                     //n为阶乘数,zhong为阶乘元素与临时结果上各个位数的乘积,jin为进位
	while(m)                                         //为增强程序的实用性,以while循环体保证程序可循环调用
	{
	    printf("请输入所算阶乘:\n");
	    scanf("%d", &n);
	    head2 = head1 = NULL;            //将两表头指向NULL 
	    p3 = p1 = p2 = p = NULL;         //将其余指针也指向NULL
	    p = (struct Data *)malloc(L2);   //按结构体大小开辟存储空间即链表第一个元素,将其首地址强制转换为结构体指针类型以赋予指针p
        p1 = p2 = head1 = p;             //将链表第一个元素首地址赋予即将使用的几个指针
	    p -> num = 1;                    //该链表将按由个位到高数位的顺序,倒序存储运算结果,故首元素初始化为1
	    p -> next2 = NULL;	             //结构体中next2指针将用于反向输出结果,则首元素为输出的最后一个元素,故next2指向NULL
	    p -> next1 = NULL;               //将next1指针也指向NULL,主要用于正确输出结果为一位数的阶乘
        for(i = 2; i <= n; i++)          //外循环——从1开始依次乘积直至n为止
        {
    	    for(p1 = head1, jin = 0; p1 != NULL ; p1 = p1 -> next1)  //内层循环——将运算结果依次在不同数位上赋值
    	    {
    		    zhong = i * p1 -> num + jin;        //阶乘元素与临时结果的某数位相乘并加上上一位进位
    		    p1 -> num = zhong % 10;             //所得结果最小位数即相乘时的该位数,将该位数进行更新
    		    jin = zhong / 10;                   //接下来所得则为向上的进位数
		    }
		    while(jin)                              //临时结果的最大位数更新完后是否仍需进位
		    {
			    p3 = (struct Data *)malloc(L2);     //开辟一新元素结点,指针p3指向其首地址
			    p2 -> next1 = p3;                   //将新元素与原链表相连
			    p3 -> next2 = p2;                   //同时新元素反向指向上一个元素以形成双链表
			    p3 -> next1 = NULL;                 //正序指针next1指向NULL以控制临时结果的位数
			    p2 = p3;                            //将新元素首地址赋予p2则p3可以继续指向新元素结点
			    p2 -> num = jin % 10;               //将仍需进位的数置于新元素结点中,至此新元素结点为最高位数
			    jin = jin / 10;                     //检查是否需要再次进位
		    }	
	    }
        head2 = p2;                                      //循环结束后p2所指最后一个元素首地址赋予双链表另一表头head2
        printf("n=%d, n!=", n);                          
        for(p1 = head2 ; p1 != NULL; p1 = p1 -> next2)   //由head2所指尾结点反向输出链表
        {
    	    printf("%d", p1 -> num);
	    }
		printf("\n是否继续?\n1.是  0.否\n");            //视用户需要是否循环调用程序
		scanf("%d", &m);
	}
	printf("程序结束\n");
}

int main()                                               //主函数
{
	Bigshu();                                            //调用Bigshu函数
	system("pause");
	return 0;    
}

                                                                                                                                                                                     作者:w-彦-w

2019-10-29 18:45:53 weixin_42473228 阅读数 132
  • 数据结构与算法在实战项目中的应用

    该视频教程教大家将学到的数据结构与算法知识应用到实际项目开发中,真正的做到学以致用,理论联系实际,课程会从基本的数据结构算法讲起,结合着实际项目开发,由浅入深,更加贴近实战,让学习者真正的掌握算法应用,可以在工作中直接将其应用到项目开发中。

    8087 人正在学习 去看看 CSDN讲师

大学程序实验.数据结构.图型结构的应用一.邻接矩阵一

0 目录

5 图型结构的应用

5.1 邻接矩阵一

5.1.1 题目

1、图的建立
从键盘输入数据建立图,并打印
实验要求:在程序中定义下述函数,并实现要求的函数功能:
CreateGraph(): 按从键盘输入数据建立图
PrintGrah():打印图
实验提示:
图的存储可采用邻接矩阵或邻接表;
打印出每一个顶点信息和邻接矩阵或邻接表
注意问题:
有向图,无向图,有向网,无向网任选一种。
2、深度优先遍历以及广度优先遍历
问题描述:从键盘输入数据建立图并打印深度优先遍历序列和广度优先遍历序列。
实验提示:
图的存储可采用邻接矩阵或邻接表;
有向图,无向图,有向网,无向网任选一种。
5、求一条从顶点 v 到顶点 s 的简单路径
实验提示:图的存储可采用邻接矩阵或邻接表;

5.1.2 源码

// MGraph.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "malloc.h" 

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100
#define MAXSIZE 100
#define INFINITY INT_MAX

typedef int Status;
typedef char VertexType[10];
typedef int EdgeType;
typedef int Boolean;
typedef int QElemType;

typedef struct 
{
	VertexType vexs[MAXVEX];
	EdgeType arc[MAXVEX][MAXVEX];
	int numVertexs,numEdges;
}MGraph;

//广度遍历用队列结构体
typedef struct
{
	QElemType data[MAXSIZE];
    int front;
    int rear;
}Queue;

void CreateMGraph(MGraph *G)
{
	int i,j,k,w;
	printf("请输入顶点数和边数:\n");
	scanf("%d%d",&G->numVertexs,&G->numEdges);
	printf("\n");
	
	for(i=0;i<G->numVertexs;i++)
	{
		printf("顶点%d:",i+1);
        scanf("%s",G->vexs[i]);
	}

	for(i=0;i<G->numVertexs;i++)
	{
        for(j=0;j<G->numVertexs;j++)
		{
            G->arc[i][j]=0;//邻接矩阵初始化   
		}
	}
	printf("\n");

	for(k=0;k<G->numEdges;k++)
	{
        printf("请输入第%d条边(vi,vj)上的下标i,下标j和权w:\n",k+1);
		scanf("%d%d%d",&i,&j,&w);
		G->arc[i-1][j-1]=w;
		G->arc[j-1][i-1]=G->arc[i-1][j-1];//无向网
	}
}

void PrintMGraph(MGraph G)
{
	int i,j;
	printf("图的顶点为:\n");
	for(i=0;i<G.numVertexs;i++)
	{
        printf("顶点%d:%s\n",i+1,G.vexs[i]);
	}
    printf("\n");
    
	printf("邻接矩阵为:\n");
	for(i=0;i<G.numVertexs;i++)
	{ 
        for(j=0;j<G.numVertexs;j++)
		{
            printf(" %d",G.arc[i][j]);//打印图
		}
		printf("\n");
	}
}


Boolean visited[MAXSIZE];

void DFS(MGraph G,int i)//深度优先
{
    int j;
	visited[i]=TRUE;
	printf(" %s",G.vexs[i]);
	
	for(i=0;i<G.numVertexs;i++)
	{
        if(G.arc[i][j]==1&&!visited[j])
		{
             DFS(G,j);
		}
	}
}

void DFSTraverse(MGraph G)
{
	int i;
	for(i=0;i<G.numVertexs;i++)
	{
        visited[i]=FALSE;
	}

	for(i=0;i<G.numVertexs;i++)
	{
        if(!visited[i])
		{
            DFS(G,i);
		}
	}
}


//队列
Status InitQueue(Queue *Q)
{
    Q->front=0;
	Q->rear=0;
	return OK;
}

Status EnQueue(Queue *Q,QElemType e)
{
    if((Q->rear+1)%MAXSIZE==Q->front)
	{
		return ERROR;
	}
	Q->data[Q->rear]=e;
	Q->rear=(Q->rear+1)%MAXSIZE;

	return OK;
}

Status DeQueue(Queue *Q,QElemType *e)
{
    if(Q->front==Q->rear)
	{
        return ERROR;
	}

	*e=Q->data[Q->front];
	Q->front=(Q->front+1)%MAXSIZE;

	return OK;
}

Status QueueEmpty(Queue *Q)
{
	if(Q->front==Q->rear)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}

void BFSTraverse(MGraph G)
{
    int i,j;
	Queue Q;

	for(i=0;i<G.numVertexs;i++)
	{
        visited[i]=FALSE;
	}

	//初始化队列
	InitQueue(&Q);

	for(i=0;i<G.numVertexs;i++)
	{
        if(!visited[i])
		{
            visited[i]=TRUE;
			printf(" %s",G.vexs[i]);
			EnQueue(&Q,i);
			while(!QueueEmpty(&Q))
			{  
                DeQueue(&Q,&i);
				for(j=0;j<G.numVertexs;j++)
				{
                    if(G.arc[i][j]==1&&!visited[j])
					{
                        visited[j]=TRUE;
						printf(" %s",G.vexs[j]);
						EnQueue(&Q,j);
					}
				}
			}
		}
	}
}

Status DFS_FindSimPath(MGraph G,VertexType *Path,int v,int s,int value)
{
    int i;
    visited[v]=TRUE;
	strcpy(Path[value],G.vexs[v]);//将顶点值存放数组中
	value++;

	if(v==s)
	{
		for(i=0;i<value;i++)
		{
            if(strcmp(Path[i],"\0")!=0)//比较字符串
			{
                printf("%s ",Path[i]);
			}
		}
		printf("\n");
	}
	else
	{
		for(i=0;i<G.numVertexs;i++)
		{
            if(G.arc[v][i]!=0&&G.arc[v][i]!=INFINITY&&!visited[i])
			{
                DFS_FindSimPath(G,Path,i,s,value);
			}
		}
	}
	visited[v]=FALSE;
	value--;

	return OK;
}

Status MGraphMenu()
{ 
    int value;
    
    printf("\n");
    printf(" ________图的操作________ \n");
    printf("|                        |\n");
    printf("|  1.打印顶点与邻接矩阵  |\n");
	printf("|  2.深度优先遍历打印    |\n");
	printf("|  3.广度优先遍历打印    |\n");
	printf("|  4.求v-s的简单路径     |\n");
	printf("|  5.退出                |\n");
	printf("|________________________|\n");
    printf("请输入你要进行的操作:");
    
	scanf("%d",&value); 
	return value;
}  

Status main()
{
	MGraph G;int RET;

	CreateMGraph(&G);
	printf("\n"); 
	
	label:
	RET=MGraphMenu();
	
	if(RET==1)
	{
		PrintMGraph(G);
		printf("\n");
		goto label; 
	}
	else if(RET==2)
	{
	    printf("\n");
 	    printf("深度优先遍历:\n");
	    DFSTraverse(G);
	    printf("\n");
	    goto label;
	}
	else if(RET==3)
	{
		printf("\n");
		printf("广度优先遍历:\n");
	    BFSTraverse(G);
	    printf("\n");
	    goto label;
	}
    else if(RET==4)
	{
	    int i,v,s,value;
	    VertexType a,b;
	    VertexType Path[G.numVertexs];
    	printf("请输入出发顶点:\n");
    	scanf("%s",a);
    	printf("请输入到达顶点:\n");
    	scanf("%s",b);
    	value=0;
	
    	for(i=0;i<G.numVertexs;i++)
    	{
            if(strcmp(G.vexs[i],a)==0)
    		{
    			v=i;
    		}
    		if(strcmp(G.vexs[i],b)==0)
    		{   
                s=i;
    		}
    	}

        for(i=0;i<G.numVertexs;i++)
    	{
            visited[i]=FALSE;
    	}
    	for(i=0;i<G.numVertexs;i++)
    	{ 
            strcpy(Path[i],"\0");
    	}
        DFS_FindSimPath(G,Path,v,s,value);
		goto label;	
    }
	else
	{
		printf("退出!\n");
	}
	
	return OK;
}

1.1.3 下载

链接地址: 5.1_MGRAPH.CPP

2 下一章

博客地址: 大学数据结构实验(五.图型结构的应用二)

2019-10-29 18:48:39 weixin_42473228 阅读数 92
  • 数据结构与算法在实战项目中的应用

    该视频教程教大家将学到的数据结构与算法知识应用到实际项目开发中,真正的做到学以致用,理论联系实际,课程会从基本的数据结构算法讲起,结合着实际项目开发,由浅入深,更加贴近实战,让学习者真正的掌握算法应用,可以在工作中直接将其应用到项目开发中。

    8087 人正在学习 去看看 CSDN讲师

大学程序实验.数据结构.图型结构的应用二.邻接矩阵二

0 目录

5 图型结构的应用

5.2 邻接矩阵二

5.2.1 题目

1、图的建立
从键盘输入数据建立图,并打印
实验要求:在程序中定义下述函数,并实现要求的函数功能:
CreateGraph(): 按从键盘输入数据建立图
PrintGrah():打印图
实验提示:
图的存储可采用邻接矩阵或邻接表;
打印出每一个顶点信息和邻接矩阵或邻接表
注意问题:
有向图,无向图,有向网,无向网任选一种。
2、深度优先遍历以及广度优先遍历
问题描述:从键盘输入数据建立图并打印深度优先遍历序列和广度优先遍历序列。
实验提示:
图的存储可采用邻接矩阵或邻接表;
有向图,无向图,有向网,无向网任选一种。
5、求一条从顶点 v 到顶点 s 的简单路径
实验提示:图的存储可采用邻接矩阵或邻接表;

5.2.2 源码

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 //最大顶点数 
#define INFINITY INT_MAX
#define MAXSIZE 100//用于广度优先遍历的队列的初始分配量 

typedef int Status;
typedef char VertexType[10];
typedef int EdgeType;
typedef int Boolean;
typedef struct
{
	VertexType vexs[MAXVEX];//顶点表 
	EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵 
	int numVertexs,numEdges;//图中的顶点数和边数 
	int kind;//图的种类 
}MGraph;

typedef struct//顺序存贮结构的队列 
{
	int data[MAXSIZE];
	int front;
	int rear;
 }Queue;

Status InitQueue(Queue &Q)
{
	Q.front = 0;
	Q.rear = 0;
	return OK;
}

Status EnQueue(Queue &Q,int e)
{
	if((Q.rear+1)%MAXSIZE == Q.front)//队满的标志 
	    return ERROR;
	Q.data[Q.rear] = e;
	Q.rear = (Q.rear+1)%MAXSIZE;//队尾指针后移一位 
	
	return OK;
}

Status DeQueue(Queue &Q,int &e)
{
	if(Q.front == Q.rear)//队空 
	    return ERROR;
	e = Q.data[Q.front];
	Q.front = (Q.front+1)%MAXSIZE;//队头指针后移 
	
	return OK;
}

Status QueueEmpty(Queue &Q)
{
	if(Q.front == Q.rear)
	    return TRUE;
	else
	    return FALSE;
 } 

void CreateMGraph(MGraph &G)
{
	int i,j,k,w;
	printf("请输入顶点数和边数:\n");
    scanf("%d%d",&(G.numVertexs),&(G.numEdges));
    printf("输入图的种类:0-有向图 1-无向图  2-有向网  3-无向网\n");
    scanf("%d",&(G.kind));
    getchar();
    for(i = 0;i < G.numVertexs;i++)//建立顶点表 
    {
    	printf("请输入第%d个顶点信息:\n",i+1);
    	scanf("%s",(G.vexs[i]));
	}
    for(i = 0;i < G.numVertexs;i++)
        for(j = 0;j < G.numVertexs;j++)
            if(G.kind == 0 || G.kind == 1)
                G.arc[i][j] = 0;//邻接矩阵初始化 
            else
                G.arc[i][j] = INFINITY;//邻接矩阵初始化 
    for(k = 0;k < G.numEdges;k++)//建立邻接矩阵 
    {
    	if(G.kind == 0 || G.kind == 1)
    	{
    		printf("请输入第%d条边(vi,vj)的下标i,下标j:\n",k+1);
    		scanf("%d%d",&i,&j);
    		w = 1;
		}
		else
		{
			printf("请输入第%d条边(vi,vj)的下标i,下标j和权值w:\n",k+1);
			scanf("%d%d%d",&i,&j,&w);
		}
		G.arc[i-1][j-1] = w;
		if(G.kind == 1 || G.kind == 3)//无向图矩阵对称 
		    G.arc[j-1][i-1] = G.arc[i-1][j-1];
	}
}

void PrintGraph(MGraph G)
{
	int i,j;
	for(i = 0;i < G.numVertexs;i++)//打印顶点信息 
	    printf("第%d个顶点信息:%s\n",i+1,G.vexs[i]);
	printf("邻接矩阵为:\n");
	for(i = 0;i < G.numVertexs;i++)//打印邻接矩阵信息 
	{
		for(j = 0;j < G.numVertexs;j++)
	        printf("%d",G.arc[i][j]);
	    printf("\n");
	}
	    
 } 
 
 Boolean visited[MAXVEX];//访问标志数组
 
 void DFS(MGraph G, int i)//深度优先递归算法 
 {
 	int j;
 	visited[i] = TRUE;
 	printf("%s",G.vexs[i]);//打印顶点信息
	for(j = 0;j < G.numVertexs;j++)
	    if(G.arc[i][j] != 0&&G.arc[i][j] != INFINITY && !visited[j])
		    DFS(G,j); 
 	
  } 
  
  void DFSTraverse(MGraph G)//深度优先遍历 
  {
  	int i;
  	for(i = 0;i < G.numVertexs;i++)
  	    visited[i] = FALSE;
  	for(i = 0;i < G.numVertexs;i++)
  	    if(!visited[i])
  	        DFS(G,i);
  }
  
  void BFSTraverse(MGraph G)
  {
  	int i,j;
  	Queue Q;
  	for(i = 0;i < G.numVertexs;i++)
  	    visited[i] = FALSE;
  	InitQueue(Q);//初始化队列
	for(i = 0;i < G.numVertexs;i++)
	{
		if(!visited[i])//若未访问过 
		{
			visited[i] = TRUE;//设置成访问过 
			printf("%s",G.vexs[i]);//打印顶点信息 
			EnQueue(Q,i);
			while(!QueueEmpty(Q))
			{
				DeQueue(Q,i);
				for(j = 0;j < G.numVertexs;j++)
				{
					//判断当前顶点的邻接顶点是否访问过 
					if(G.arc[i][j] != 0&&G.arc[i][j] != INFINITY&&!visited[j])
					{//若未访问过进行操作 
						visited[j] = TRUE;
						printf("%s",G.vexs[j]);
						EnQueue(Q,j);
					}
				}
			}
		}
	 } 
  	
   } 
 
 Status CountDegree(MGraph G)
 {
 	int i,j,count;
 	count = 0;
 	for(i = 0;i < G.numVertexs;i++)
 	{
 		for(j = 0;j < G.numVertexs;j++)
 		{
 			if(G.arc[i][j] != 0&&G.arc[i][j] != INFINITY)
 			    count++;
		 }
		 printf("第%d个顶点的度为%d\n",i+1,count);
		 count = 0;
	 }
	 
	 return OK;
 }

 Status CountOutDegree(MGraph G)
 {
 	int i,j,count;
 	count = 0;
 	for(i = 0;i < G.numVertexs;i++)
 	{
 		for(j = 0;j < G.numVertexs;j++)
 		{
 			if(G.arc[i][j] != 0&&G.arc[i][j] != INFINITY)
 			    count++;
		 }
		 printf("第%d个顶点的出度为%d\n",i+1,count);
		 count = 0;
	 }
	 
	 return OK;
 }

Status CountInDegree(MGraph G)
 {
 	int i,j,count;
 	count = 0;
 	for(i = 0;i < G.numVertexs;i++)
 	{
 		for(j = 0;j < G.numVertexs;j++)
 		{
 			if(G.arc[j][i] != 0&&G.arc[j][i] != INFINITY)
 			    count++;
		 }
		 printf("第%d个顶点的入度为%d\n",i+1,count);
		 count = 0;
	 }
	 
	 return OK;
 }

//用深度优先遍历求 V-S 简单路径 
Status DFS_SimplePath(MGraph G,VertexType *PATH,int v,int s,int num)
{
	int i;
	visited[v] = TRUE;
	strcpy(PATH[num],G.vexs[v]);
	num++;
	
	if(v == s)
	{
		printf("两点间的一条简单路径为:");
		for(i = 0;i < num;i++) 
		    if(strcmp(PATH[i],"\0") != 0)
		        printf("%s-",PATH[i]);
		printf("\n"); 
	}
	else
	{
		for(i = 0;i < G.numVertexs;i++)
		    if(G.arc[v][i] != 0&&G.arc[v][i] != INFINITY&&!visited[i])
		        DFS_SimplePath(G,PATH,i,s,num);
	}
	visited[v] = FALSE;//回溯 
	num--;
	
	return OK;   	
}

int main()
{
	MGraph G;
	CreateMGraph(G);
	PrintGraph(G);
	
	printf("深度遍历结果:\n");
	DFSTraverse(G);
	printf("\n");
	printf("广度遍历结果:\n");
	BFSTraverse(G);
	printf("\n");
	
	if(G.kind == 1) 
	    CountDegree(G);
	if(G.kind == 0)
	{
		CountOutDegree(G);
		printf("\n");
	    CountInDegree(G);
	    printf("\n");
	}
	    
	
	int i,v,s,num;
	VertexType a,b;
	VertexType PATH[G.numVertexs];//存放路径中顶点信息 
	printf("请输入要求简单路径的出发顶点的信息:\n");
	scanf("%s",a);
	printf("请输入要求简单路径的到达顶点的信息:\n");
	scanf("%s",b);
	num = 0;
	for(i = 0;i < G.numVertexs;i++)
	{
		if(strcmp(G.vexs[i],a) == 0)
	        v = i;
	    if(strcmp(G.vexs[i],b) == 0)
	        s = i;
	}
	for(i = 0;i < G.numVertexs;i++)
	    visited[i] = FALSE;
	for(i = 0;i < G.numVertexs;i++)
	    strcpy(PATH[i],"\0");
	DFS_SimplePath(G,PATH,v,s,num);
	
	return 0;
}

1.1.3 下载

链接地址: 5.2_MGRAPH1.CPP

2 下一章

博客地址: 大学数据结构实验(六.查找算法的应用一)

2016-06-08 06:43:37 zhangchen124 阅读数 6774
  • 数据结构与算法在实战项目中的应用

    该视频教程教大家将学到的数据结构与算法知识应用到实际项目开发中,真正的做到学以致用,理论联系实际,课程会从基本的数据结构算法讲起,结合着实际项目开发,由浅入深,更加贴近实战,让学习者真正的掌握算法应用,可以在工作中直接将其应用到项目开发中。

    8087 人正在学习 去看看 CSDN讲师

视频课:https://edu.csdn.net/course/play/7621 

       在游戏的编写中,不可避免的出现很多应用数据结构的地方,有些简单的游戏,只是由几个数据结构的组合,所以说,数据结构在游戏编程中扮演着很重要的角色。
  本文主要讲述数据结构在游戏中的应用,其中包括对链表、顺序表、栈、队列、二叉树及图的介绍。读者在阅读本文以前,应对数据结构有所了解,并且熟悉C/C++语言的各种功用。好了,现在我们由链表开始吧!

1
、链表
  在这一节中,我们将通过一个类似雷电的飞机射击游戏来讲解链表在游戏中的应用。在飞机游戏中,链表主要应用在发弹模块上。首先,飞机的子弹是要频繁的出现,消除,其个数也是难以预料的。链表主要的优点就是可以方便的进行插入,删除操作。我们便将链表这一数据结构引入其中。首先,分析下面的源代码,在其中我们定义了坐标结构和子弹链表。

struct CPOINT
{
int x; // X轴坐标
int y; // Y轴坐标
};

struct BULLET
{
struct BULLE* next; //指向下一个子弹
CPOINT bulletpos; //子弹的坐标
int m_ispeed; //子弹的速度
};

  接下来的代码清单是飞机类中关于子弹的定义:

class CMYPLANE
{
public:
void AddBullet(struct BULLET*); //加入子弹的函数,每隔一定时间加弹
void RefreshBullet(); //刷新子弹
privated:
struct BULLET *st_llMyBullet; //声明飞机的子弹链表
};

  在void AddBullet(struct BULLET*),我们要做的操作只是将一个结点插入链表中,并且每隔一段时间加入,就会产生连续发弹的效果。
  这是加弹函数主要的源代码:

void AddBullet(struct BULLET*)
{
struct BULLET *st_llNew,*st_llTemp; //定义临时链表
st_llNew=_StrucHead; //链表头(已初始化)
st_llNew->(BULLET st_llMyBullet*)malloc(sizeof(st_llMyBullet));// 分配内存
st_llTemp= =_NewBullet; //临时存值
st_llNew->next=st_llTemp->next;st_llTemp->next=st_llNew;
}

  函数Void RefreshBullet(),我们只要将链表历遍一次就行,将子弹的各种数据更新,其中主要的源代码如下:

while(st_llMyBullet->next!=NULL)
{
// 查找
st_llMyBullet->bulletpos.x-=m_ispeed;//更新子弹数据
………
st_llMyBullet=st_llMyBullet->next; //查找运算
}

  经过上面的分析,在游戏中,链表主要应用在有大规模删除,添加的应用上。不过,它也有相应的缺点,就是查询是顺序查找,比较耗费时间,并且存储密度较小,对空间的需求较大。
  如果通过对游戏数据的一些控制,限定大规模的添加,也就是确定了内存需求的上限,可以应用顺序表来代替链表,在某些情况下,顺序表可以弥补链表时间性能上的损失。当然,应用链表,顺序表还是主要依靠当时的具体情况。那么,现在,进入我们的下一节,游戏中应用最广的数据结构顺序表。

2
、顺序表
  本节中,我们主要投入到RPG地图的建设中,听起来很吓人,但是在RPG地图系统中(特指砖块地图系统),却主要使用数据结构中最简单的成员顺序表。
  我们规定一个最简单的砖块地图系统,视角为俯视90,并由许多个顺序连接的图块拼成,早期RPG的地图系统大概就是这样。我们这样定义每个图块:

struct TILE//定义图块结构
{
int m_iAcesse; //纪录此图块是否可以通过
……// 其中有每个图块的图片指针等纪录
};

  当m_iAcesse=0,表示此图块不可通过,1表示能通过。
  我们生成如下地图:

TILE TheMapTile[10][5];

  并且我们在其中添入此图块是否可以通过,可用循环将数值加入其中,进行地图初始化。
  如图表示:
0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1 0
2 0 0 0 0 0 1 1 1 1 0
3 0 0 0 0 0 1 1 1 1 0
4 1 1 1 1 1 1 1 1 1 1

1


  从上图看到这个地图用顺序表表示非常直接,当我们控制人物在其中走动时,把人物将要走到的下一个图块进行判断,看其是否能通过。比如,当人物要走到(1,0)这个图块,我们用如下代码判断这个图块是否能通过:

int IsAcesse(x,y)
{
return TheMapTile[x,y].m_iAcesse; //返回图块是否通过的值
}

  上述只是简单的地图例子,通过顺序表,我们可以表示更复杂的砖块地图,并且,现在流行的整幅地图中也要用到大量的顺序表,在整幅中进行分块。
  好了,现在我们进入下一节:

3
、栈和队列
  栈和队列是两种特殊的线性结构,在游戏当中,一般应用在脚本引擎,操作界面,数据判定当中。在这一节中,主要通过一个简单的脚本引擎函数来介绍栈,队列和栈的用法很相似,便不再举例。
  我们在设置脚本文件的时候,通常会规定一些基本语法,这就需要一个解读语法的编译程序。这里列出的是一个语法检查函数,主要功能是检查“()”是否配对。实现思想:我们规定在脚本语句中可以使用“()”嵌套,那么,便有如下的规律,左括号和右括号配对一定是先有左括号,后有右括号,并且,在嵌套使用中,左括号允许单个或连续出现,并与将要出现的有括号配对销解,左括号在等待右括号出现的过程中可以暂时保存起来。当右括号出现后,找不到左括号,则发生不配对现象。从程序实现角度讲,左括号连续出现,则后出现的左括号应与最先到来的右括号配对销解。左括号的这种保存和与右括号的配对销解的过程和栈中后进先出原则是一致的。我们可以将读到的左括号压入设定的栈中,当读到右括号时就和栈中的左括号销解,如果在栈顶弹不出左括号,则表示配对出错,或者,当括号串读完,栈中仍有左括号存在,也表示配对出错。
  大致思想便是这样,请看代码片断:

struct// 定义栈结构
{
int m_iData[100]; //数据段
int m_iTop; //通常规定栈底位置在向量低端
}SeqStack;

int Check(SeqStack *stack)//语法检查函数
{
char sz_ch;
int boolean; Push(stack,'# '); //压栈,#为判断数据
sz_ch=getchar(); //取值
boolean=1;
while(sz_ch!='\n'&&boolean)
{
if(sz_ch= ='(')
Push(stack,ch);
if(sz_ch= =')')
if(gettop(stack)= ='#') //读栈顶
boolean=0;
else
Pop(stack); //出栈
sz_ch=getchar();
}
if(gettop(stack)!='#') boolean=0;
if(boolean)cout<<"right"; //输出判断信息
else
cout<<"error";

  这里只是介绍脚本的读取,以后,我们在图的介绍中,会对脚本结构进行深入的研究。
  总之,凡在游戏中出现先进后出(),先进先出(队列)的情况,就可以运用这两种数据结构,例如,《帝国时代》中地表中间的过渡带。

4
、二叉树
  树应用及其广泛,二叉树是树中的一个重要类型。在这里,我们主要研究二叉树的一种应用方式:判定树。其主要应用在描述分类过程和处理判定优化等方面上。
  在人工智能中,通常有很多分类判断。现在有这样一个例子:设主角的生命值d,在省略其他条件后,有这样的条件判定:当怪物碰到主角后,怪物的反应遵从下规则:



  根据条件,我们可以用如下普通算法来判定怪物的反应:

if(d<100) state=嘲笑,单挑;
else if(d<200) state=单挑;
else if(d<300) state=嗜血魔法;
else if(d<400) state=呼唤同伴;
else state=逃跑;

  上面的算法适用大多数情况,但其时间性能不高,我们可以通过判定树来提高其时间性能。首先,分析主角生命值通常的特点,即预测出每种条件占总条件的百分比,将这些比值作为权值来构造最优二叉树(哈夫曼树),作为判定树来设定算法。假设这些百分比为:




  构造好的哈夫曼树为:





  对应算法如下:

if(d>=200)&&(d<300)state=嗜血魔法;
else if(d>=300)&&(d<500)state=呼唤同伴;
else if(d>=100)&&(d<200)state=单挑;
else if(d<100) state=嘲笑,单挑;
else state=逃跑;

  通过计算,两种算法的效率大约是2:3,很明显,改进的算法在时间性能上提高不少。
  一般,在即时战略游戏中,对此类判定算法会有较高的时间性能要求,大家可以对二叉树进行更深入的研究。现在,我们进入本文的最后一节:图的介绍,终于快要完事了。

5
、图
  在游戏中,大多数应用图的地方是路径搜索,即关于A*算法的讨论。由于介绍A*算法及路径搜索的文章很多,这里介绍图的另一种应用:在情节脚本中,描述各个情节之间的关系。
  在一个游戏中,可能包含很多分支情节,在这些分支情节之间,会存在着一定的先决条件约束,即有些分支情节必须在其他分支情节完成后方可开始发展,而有些分支情节没有这样的约束。
  通过分析,我们可以用有向图中AOV(Activity On Vertex Network)来描述这些分支情节之间的先后关系。好了,现在假如我们手头有这样的情节:

情节编号情节先决条件
C1
遭遇强盗
C2
受伤 C1
C3
买药 C2
C4
看医生 C2
C5
治愈 C3,C4

  注意:AOV网中,不应该出现有向环路,否则,顶点的先后关系就会进入死循环。即情节将不能正确发展。我们可以采取拓扑派序来检测图中是否存在环路,拓扑排序在一般介绍数据结构的书中,都有介绍,这里便不再叙述。
  那么以上情节用图的形式表现为(此图为有向图,先后关系在上面表格显示):



 现在我们用邻接矩阵表示此有向图,请看下面代码片断:

struct MGRAPH
{
int Vexs[MaxVex]; //顶点信息
int Arcs[MaxLen][MaxLen]; //邻接矩阵
……
};

  顶点信息都存储在情节文件中。
  将给出的情节表示成邻接矩阵:

0 1 0 0 0
0 0 1 1 0
0 0 0 0 1
0 0 0 0 1
0 0 0 0 0

4


  我们规定,各个情节之间有先后关系,但没有被玩家发展的,1表示。当情节被发展的话,就用2表示,比如,我们已经发展了遭遇强盗的情节,那么,C1C2顶点之间的关系就可以用2表示,注意,并不表示C2已经发展,只是表示C2可以被发展了。
  请看下面的代码:

class CRelation
{
public:
CRelation(char *filename); //构造函数,将情节信息文件读入到缓存中
void SetRelation(int ActionRelation); //设定此情节已经发展
BOOL SearchRelation(intActionRelation); // 寻找此情节是否已发展
BOOL SaveBuf(char *filename); //保存缓存到文件中
……
privated:
char* buf; //邻接矩阵的内存缓冲
……
};

  在这里,我们将表示情节先后关系的邻接矩阵放到缓冲内,通过接口函数进行情节关系的修改,BOOL SearchRelation(intActionRelation)函数中,我们可以利用广度优先搜索方法进行搜索,介绍这方面的书籍很多,代码也很长,在这里我就不再举例了。
  我们也可以用邻接链表来表示这个图,不过,用链表表示会占用更多的内存,邻接链表主要的优点是表示动态的图,在这里并不适合。
  另外,图的另一个应用是在寻路上,著名的A*算法就是以此数据结构为基础,人工智能,也需要它的基础。

没有更多推荐了,返回首页