图的应用 数据结构

2018-09-05 18:23:28 yeyazhishang 阅读数 190021

本文目录:

数据结构分类

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。
常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示:
这里写图片描述
每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。

1、数组

数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

int[] data = new int[100];data[0]  = 1;

优点:
1、按照索引查询元素速度快
2、按照索引遍历数组方便

缺点:
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加,删除的操作慢,因为要移动其他的元素。

适用场景:
频繁查询,对存储空间要求不大,很少增加和删除的情况。

2、栈

栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。
这里写图片描述
栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。

3、队列

队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队,示例图如下:
这里写图片描述
使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

4、链表

链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
这里写图片描述
链表的优点:
链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

缺点:
因为含有大量的指针域,占用空间较大;
查找元素需要遍历链表来查找,非常耗时。

适用场景:
数据量较小,需要频繁增加,删除操作的场景

5、树

是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  • 每个节点有零个或多个子节点;
  • 没有父节点的节点称为根节点;
  • 每一个非根节点有且只有一个父节点;
  • 除了根节点外,每个子节点可以分为多个不相交的子树;

在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树
这里写图片描述
二叉树是树的特殊一种,具有如下特点:

1、每个结点最多有两颗子树,结点的度最大为2。
2、左子树和右子树是有顺序的,次序不能颠倒。
3、即使某结点只有一个子树,也要区分左右子树。

二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

扩展:
二叉树有很多扩展的数据结构,包括平衡二叉树、红黑树、B+树等,这些数据结构二叉树的基础上衍生了很多的功能,在实际应用中广泛用到,例如mysql的数据库索引结构用的就是B+树,还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大,但算法上比较复杂,想学习的话还是需要花时间去深入的。

6、散列表

散列表,也叫哈希表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。

记录的存储位置=f(key)

这里的对应关系 f 成为散列函数,又称为哈希 (hash函数),而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,这种存储空间可以充分利用数组的查找优势来查找元素,所以查找的速度很快。

哈希表在应用中也是比较常见的,就如Java中有些集合类就是借鉴了哈希原理构造的,例如HashMap,HashTable等,利用hash表的优势,对于集合的查找元素时非常方便的,然而,因为哈希表是基于数组衍生的数据结构,在添加删除元素方面是比较慢的,所以很多时候需要用到一种数组链表来做,也就是拉链法。拉链法是数组结合链表的一种结构,较早前的hashMap底层的存储就是采用这种结构,直到jdk1.8之后才换成了数组加红黑树的结构,其示例图如下:
这里写图片描述
从图中可以看出,左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。

7、堆

堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;

  • 堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2),满足前者的表达式的成为小顶堆,满足后者表达式的为大顶堆,这两者的结构图可以用完全二叉树排列出来,示例图如下:
这里写图片描述
因为堆有序的特点,一般用来做数组中的排序,称为堆排序。

8、图

图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

按照顶点指向的方向可分为无向图和有向图:
这里写图片描述
这里写图片描述
图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构,这里不做展开,读者有兴趣可以自己学习深入。

2019-07-23 20:38:50 qq_45067278 阅读数 1051

图:元素之间存在多对多关系(线性表的元素之间存在前驱和后继,树的元素之间存在父子关系,图的任意元素之间都有可能存在关系)。
由顶点的有穷非空集合和顶点之间边的集合组成。
在图型数据结构中,数据被称为顶点,数据之间的关系补称为边。
在图中不允许出现没有点,但可以没有边。
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、非常容易计算出度
缺点:不方便计算入度。
十字链表:由于阾接表不能同时兼顾出度和入度,因此我们修改阾接的边表结构,使用既存储入度也存储出度,这种表就叫十字链表。
阾接多重表:由于遍历表是需要一些删除边操作,而阾接表在删除边时非常麻烦,因此就设计出的阾接多重表。
边集数组:由两个一维数组构成,一个存储顶点的信息,另一个存储边的信息(它的每个数据元素都由一条边的起点到终点的下标和权组成),这种存储结构更侧重于边的相关操作(路径、路径长度、最短路径),而统计顶的度需要扫描整个数组,效率不高。

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

2018-01-18 20:55:42 li99yangg 阅读数 2891

//注:我这段代码预先输入好了值,图有机会贴上来

1、掌握图的各种存储结构的特点及适用范围。

2、掌握建立图的方法。(包括邻接矩阵、邻接表)

3、熟练掌握图的深度优先搜索算法和广度优先搜索算法,并能灵活运用这两个算法解决实际问题。

实现上述两个功能时要求图分别用邻接矩阵和邻接表表示。求简单路径问题,可利用图得深度优先搜索遍历算法实现,从顶点 i 出发,开始遍历,访问到顶点 j 时遍历结束。在遍历的过程中,需要将访问过的顶点压入栈,当在遍历过程中遇到一个访问过的顶点 k 时,需要依次删除栈中元素,直到栈顶为 k。遍历结束后,将栈中的顶点倒着输出即为顶点 i 到顶点 j 的简单路径。

 求最短路径问题,可利用图得广度优先搜索遍历算法实现,为实现图得广度优先搜索算法,需要用到队列。

#include <stdio.h>

#include <iostream>

#include <setjmp.h>

using namespace std;

#define MaxInt 32767//表示正无穷

#define MVNum 100//最大顶点数

#define OK 1

#define ERROR -1

#define OVERFLOW -2

jmp_buf j;

typedef int Status;

typedef char VerTexType;//假设顶点的数据类型为字符型

typedef int ArcType;//假设边的权值类型为整型

typedef int OtherInfo;

typedef struct QNode

{

    VerTexType data;

    struct QNode *next;

}QNode,*QueuePtr;

typedef struct

{

    QueuePtr front;

    QueuePtr rear;

}LinkQueue;

typedef struct

{

    VerTexType vexs[MVNum];//顶点表

    ArcType arcs[MVNum][MVNum];//邻接矩阵

    int vexnum,arcnum;//图的当前点数和边数

}AMGraph;

 

typedef struct stack

{

    VerTexType *base;

    VerTexType *top;

    int stacksize;

}SqStack;

typedef struct ArcNode

{

    int adjvex;//该边所指向的顶点的位置

    struct ArcNode *nextarc;//指向下一条边的指针

    OtherInfo info;//边的信息

}ArcNode;

typedef struct VNode

{

    VerTexType data;

    ArcNode *firstarc;//指向第一条依附该顶点的边的指针

}VNode,AdjList[MVNum];//表示邻接表类型

typedef struct

{

    AdjList vertices;//图的当前顶点数和边数

    int vexnum,arcnum;

}ALGraph;

int path[6][6];

bool isVisited[MaxInt];

SqStack S;

LinkQueue Q;

int D[6][6];

int anopath[6][6];

char PreChar[6]={'a','b','c','d','e','f'};

//void DFS_AM(AMGraph &G,VerTexType v1,VerTexType v2);

void InitQueue(LinkQueue &Q )//初始化队列

{

    Q.front = Q.rear = new QNode;

    Q.front->next = NULL;

    return;

}

 

void EnQueue( LinkQueue &Q, VerTexType x)//尾插法入队,将x存储在Q链表的尾部

{

    QNode *p = new QNode;    //申请新结点

    p->data=x; //将x存入p中的数据域

    p->next = NULL;

    Q.rear->next = p;

    Q.rear = p;

    return;

}

int DeQueue( LinkQueue &Q,VerTexType &x)//出队操作,将在最前面的元素出队

{

    if(Q.front == Q.rear)return 0;

    QNode *p=Q.front->next;//将Q的队列头元素地址赋给p

    //p 指向将要摘下的结点

    x=p->data; //保存结点中数据

    Q.front->next = p->next;//令p的下一节点指向第一个元素

    if (p==Q.rear)//如果队列为空

    {

        Q.rear = Q.front;//当队列中只有一个结点时,p 结点出队后, 要将队尾指针指向头结点

    }

    delete p;//释放被删结点

    return 1;

}

void ShowQueue(LinkQueue &Q)//显示所有元素

{

    if(Q.front->next == NULL)//如果队列中无元素

    {

        printf("无元素");

        return;

    }

    QNode* p=Q.front->next;//令p指针指向第一个元素

    do//当p遍历所有结点时

    {

        printf("%c ",p->data);//输出队列中所有元素

        p = p->next;//p指向下一元素

    }while(p!=Q.rear->next);

    getchar();

    return;

}

Status CreateUDN (AMGraph &G)//用邻接矩阵创建有向网P154 图6.10(a)

{

    G.vexnum = 6;

    G.arcnum = 10;

    cout<<"总点数为:"<<G.vexnum<<endl;

    cout<<"总边数为:"<<G.arcnum<<endl;

    cout<<"依次输入点的信息:"<<endl;

    G.vexs[0] = 'a';//v1

    G.vexs[1] = 'b';//v2

    G.vexs[2] = 'c';//v3

    G.vexs[3] = 'd';//v4

    G.vexs[4] = 'e';//v5

    G.vexs[5] = 'f';//v6

    for(int i = 0;i<G.vexnum;i++)

        cout<<G.vexs[i]<<endl;

    for(int i = 0;i<G.vexnum;i++)//初始化邻接矩阵使边的权值均为MAXINT

        for(int j = 0;j<G.vexnum;j++)

            G.arcs[i][j] = MaxInt;

    G.arcs[0][1] = 5;G.arcs[0][3] = 7;

    G.arcs[1][2] = 4;G.arcs[2][0] = 8;

    G.arcs[2][5] = 9;G.arcs[3][2] = 5;

    G.arcs[3][5] = 6;G.arcs[4][3] = 5;

    G.arcs[5][0] = 3;G.arcs[5][4] = 1;

 

    for(int i =0;i<G.vexnum;i++)

    {

        for(int j = 0;j<G.vexnum;j++)

        {

            cout<<"\t"<<G.arcs[i][j];

        }

        cout<<endl;

    }

    return OK;

}

Status InitStack (SqStack &S)

{

    S.base = new VerTexType[100];

    if(!S.base)cout<<"ERROR";

    S.top = S.base;

    S.stacksize = 100;

    return OK;

}

Status Push(SqStack &S,VerTexType e)

{

    if(S.top - S.base == S.stacksize)return ERROR;

    *S.top++ = e;

    return OK;

}

Status Pop(SqStack &S,VerTexType &e)

{

    if(S.top == S.base)return 0;

    VerTexType *temp;

    temp = S.top;

    S.top--;

    delete temp;

    e = *S.top;

    return OK;

}

void ShowStack(SqStack &S)

{

    VerTexType *top = S.top;

    while(S.base != top)

    {

        cout<<*(--top)<<" ";

    }

    cout<<"over "<<endl;

}

int GetIndex(AMGraph &G,VerTexType v)

{

    int index = -1;

    for(int i=0;i<G.vexnum;i++)

    {

        if(v == G.vexs[i]){return i;}//获取v1下标

    }

    return index;

}

void DFS_AM(AMGraph &G,VerTexType v1,VerTexType v2)

{

    Push(S,v1);

    if(v1 == v2)

    {

        longjmp(j,1);

    }

    isVisited[GetIndex(G,v1)] = true;

    for(int w = 0;w<G.vexnum;w++)

    {

        if(G.arcs[GetIndex(G,v1)][w]!=MaxInt && (isVisited[w]==false))DFS_AM(G,G.vexs[w],v2);

    }

 

}

void CreateAdjList(ALGraph &G)

 {

     G.vexnum = 6;G.arcnum=10;

     for(int i =0;i<G.vexnum;i++)

     {

            G.vertices[i].data = PreChar[i];//输入顶点值

            G.vertices[i].firstarc = NULL;

            G.vertices[i].firstarc = new ArcNode;G.vertices[i].firstarc->nextarc = new ArcNode;G.vertices[i].firstarc->nextarc->nextarc = new ArcNode;G.vertices[i].firstarc->nextarc->nextarc->nextarc = new ArcNode;G.vertices[i].firstarc->nextarc->nextarc->nextarc->nextarc = new ArcNode;

     }

    G.vertices[0].firstarc->adjvex = 1;G.vertices[0].firstarc->info = 3;G.vertices[0].firstarc->nextarc->adjvex = 4;G.vertices[0].firstarc->nextarc->info = 4;G.vertices[0].firstarc->nextarc->nextarc = NULL;

    G.vertices[1].firstarc->adjvex = 0;G.vertices[1].firstarc->info = 3;G.vertices[1].firstarc->nextarc->adjvex = 4;G.vertices[1].firstarc->nextarc->info = 9;G.vertices[1].firstarc->nextarc->nextarc->adjvex = 5;G.vertices[1].firstarc->nextarc->nextarc->info = 5;G.vertices[1].firstarc->nextarc->nextarc->nextarc->adjvex = 2;G.vertices[1].firstarc->nextarc->nextarc->nextarc->info = 4;G.vertices[1].firstarc->nextarc->nextarc->nextarc->nextarc = NULL;

    G.vertices[2].firstarc->adjvex = 3;G.vertices[2].firstarc->info = 2;G.vertices[2].firstarc->nextarc->adjvex = 5;G.vertices[2].firstarc->nextarc->info = 7;G.vertices[2].firstarc->nextarc->nextarc->adjvex = 1;G.vertices[2].firstarc->nextarc->nextarc->info = 4;G.vertices[2].firstarc->nextarc->nextarc->nextarc = NULL;

    G.vertices[3].firstarc->adjvex = 2;G.vertices[3].firstarc->info = 2;G.vertices[3].firstarc->nextarc->adjvex = 5;G.vertices[3].firstarc->nextarc->info = 6;G.vertices[3].firstarc->nextarc->nextarc->adjvex = 4;G.vertices[3].firstarc->nextarc->nextarc->info = 2;G.vertices[3].firstarc->nextarc->nextarc->nextarc = NULL;

    G.vertices[4].firstarc->adjvex = 0;G.vertices[4].firstarc->info = 4;G.vertices[4].firstarc->nextarc->adjvex = 1;G.vertices[4].firstarc->nextarc->info = 9;G.vertices[4].firstarc->nextarc->nextarc->adjvex = 3;G.vertices[4].firstarc->nextarc->nextarc->info = 2;G.vertices[4].firstarc->nextarc->nextarc->nextarc->adjvex = 5;G.vertices[4].firstarc->nextarc->nextarc->nextarc->info = 2;G.vertices[4].firstarc->nextarc->nextarc->nextarc->nextarc = NULL;

    G.vertices[5].firstarc->adjvex = 1;G.vertices[5].firstarc->info = 5;G.vertices[5].firstarc->nextarc->adjvex = 2;G.vertices[5].firstarc->nextarc->info = 7;G.vertices[5].firstarc->nextarc->nextarc->adjvex = 3;G.vertices[5].firstarc->nextarc->nextarc->info = 6;G.vertices[5].firstarc->nextarc->nextarc->nextarc->adjvex = 4;G.vertices[5].firstarc->nextarc->nextarc->nextarc->info = 2;G.vertices[5].firstarc->nextarc->nextarc->nextarc->nextarc = NULL;

 

     for(int i = 0;i<G.vexnum;i++)

    {

        cout<<i<<"\t"<<G.vertices[i].data<<"\t->";

        ArcNode *p = G.vertices[i].firstarc;

        while(p!=NULL)

        {

            cout<<"\t"<<p->adjvex<<"\t"<<p->info<<"\t";

            p = p->nextarc;

 

        }

        cout<<endl;

    }

 

}

//a->e  最短4 最长3+9 = 12

int GetIndex1(ALGraph G,VerTexType v)

{

    for(int i = 0 ;i<G.vexnum;i++)

    {

        if(G.vertices[i].data == v)return i;

    }

    cout<<"wrong index";

}

Status CreateMatrix (ALGraph &G)

{

    for( int i = 0;i<G.vexnum;i++)

    {

        ArcNode *p = G.vertices[i].firstarc;

        while(p!=NULL)

        {

            int j = p->adjvex;

            path[i][j] = p->info;

//            cout<<"path"<<i<<j<<"="<<path[i][j];

            p = p->nextarc;

        }

 

    }

    cout<<endl;

 

 

}

 

void ShortertPath_Floyd(ALGraph &G)

{

for(int i = 0;i<G.vexnum;i++)

    {

        for(int j = 0;j<G.vexnum;j++)

            {

                if(i!=j&&path[i][j]==0)path[i][j]=100;

            }

        cout<<endl;

    }

    for(int  i =0;i<G.vexnum;i++)

        {

            for(int j=0;j<G.vexnum;j++)

            {

                D[i][j] = path[i][j];

                if(D[i][j]<100&&i!=j)anopath[i][j]= i;

                else anopath[i][j] = -1;

            }

        }

//    for(int i = 0;i<G.vexnum ;i++)

//    {

//        for(int j = 0;j<G.vexnum;j++)

//            cout<<anopath[i][j]<<"\t";

//            cout<<endl;

//    }

    for(int k = 0;k<G.vexnum;++k)

        {

            for(int i = 0;i<G.vexnum;++i)

            for(int j = 0;j<G.vexnum ;++j)

            {

                if(D[i][k]+D[k][j]<D[i][j])

                    {

//                        cout<<D[i][j];

                        D[i][j] = D[i][k]+D[k][j];

//                        cout<<D[i][j]<<endl;

                    anopath[i][j] = anopath[k][j];

                    }

            }

 

        }

 

}

 

 

 

int main()

{

    //邻接矩阵部分

    InitQueue (Q) ;

    AMGraph G;

    InitStack(S);

    CreateUDN(G);

 

    if(setjmp(j) == 0)

    {

        DFS_AM(G,G.vexs[1],G.vexs[0]);

    }

    else

    {

    }

    char ch[100];

    int flag = 0;

    cout<<"从"<<*S.base<<"到"<<*(S.top-1)<<"的路径为:";

    while(S.top!=S.base)

    {

        Pop(S,ch[flag]);

    //        cout<<ch[flag]<<" ";

        flag++;

    }

 

    for(int i = flag;i>=0;i--)

    {

        cout<<ch[i]<<" ";

    }

    cout<<endl;

    //邻接表部分

    for(int i = 0;i<10;i++)//初始化isvisited数组

    {

        isVisited[i]=false;

    }

    ALGraph GG;

    CreateAdjList(GG);

    for(int i = 0;i<GG.vexnum;i++)

    {

        cout<<i<<"\t"<<GG.vertices[i].data<<"\t->";

        ArcNode *p = GG.vertices[i].firstarc;

        while(p!=NULL)

        {

            cout<<"\t"<<p->adjvex<<"\t"<<p->info<<"\t";

            p = p->nextarc;

        }

        cout<<endl;

    }

    CreateMatrix(GG);

 

    ShortertPath_Floyd(GG);

                cout<<"D[i][j]图如下:"<<endl;

    for(int i = 0;i<G.vexnum ;i++)

    {

        for(int j = 0;j<G.vexnum;j++)

            cout<<D[i][j]<<"\t";

            cout<<endl;

    }

    int i = 1,j = 5;

    cout<<"从"<<i+1<<"到"<<j+1<<"的最短路径长度为:"<<D[i][j];

    return 0;

 

}



2017-04-13 07:42:17 z84616995z 阅读数 8064

通用数据结构

可以简单的按照速度将通用数据结构划分为:数组和链表(最慢),树(较快),哈希表(最快)。增、删、改、查是四大常见操作,不过其实可以浓缩为两个操作:增和查。删除操作和和修改操作都是建立在查找操作上的,所以完美的数据结构应该是具有较高的插入效率和查找效率。

通用数据结构关系

可以根据下图选择合适的通用数据结构:

数组

使用场景

数组在以下三个情形下很有用:

1)数据量较小。

2)数据规模已知。

3)随机访问,修改元素值。

如果插入速度很重要,选择无序数组。如果查找速度很重要,选择有序数组,并使用二分查找。

缺点

1)需要预先知道数据规模

2)插入效率低,因为需要移动大量元素。

链表

解决的问题

链表的出现解决了数组的两个问题:

1)需要预先知道数据规模

2)插入效率低

使用场景

1)数据量较小

2)不需要预先知道数据规模

3)适应于频繁的插入操作

缺点

1)有序数组可以通过二分查找方法具有很高的查找效率(O(log n)),而链表只能使用顺序查找,效率低下(O(n))。

二叉查找树

解决的问题

1)有序数组具有较高的查找效率(O(log n)),而链表具有较高的插入效率(头插法,O(1)),结合这两种数据结构,创建一种貌似完美的数据结构,也就是二叉查找树。

使用场景

1)数据是随机分布的

2)数据量较大

3)频繁的查找和插入操作(可以提供O(log n)级的查找、插入和删除操作)

缺点

1)如果处理的数据是有序的(升序/降序),那么构造的二叉查找树就会只有左子树(或右子树),也就是退化为链表,查找效率低下(O(log n))。

平衡树

解决的问题

1)针对二叉查找树可能会退化为链表的情况,提出了平衡树,平衡树要求任意节点的左右两个子树的高度差不超过1,避免退化为链表的情况。

使用场景

1)无论数据分布是否随机都可以提供O(log n)级别的查找、插入和删除效率

2)数据量较大

缺点

1)平衡树的实现过于复杂。

哈希表

解决的问题

同平衡树一样,哈希表也不要求数据分布是否随机,不过哈希表的实现比平衡树要简单得多。

使用场景

1)不需要对最大最小值存取。

2)无论数据分布是否随机,理想情况下(无冲突)可以提供O(1)级别的插入、查找和删除效率。

3)数据量较大

缺点

1)由于是基于数组的,数组(哈希表)创建后难以扩展,使用开放地址法的哈希表在基本被填满时,性能下降的非常严重。

2)不能对最大最小值存取。

通用数据存储结构

专用数据结构

顺序栈

优点

1)在输入数据量可预知的情形下,可以使用数组实现栈,并且数组实现的栈效率更高,出栈和入栈操作都在数组末尾完成。

缺点

1)如果对数组大小创建不当,可能会产生栈溢出的情况

链栈

优点

1)不会发生栈溢出的情况

2)输入数据量未知时,使用链栈。通过头插法实现入栈操作,头删法实现出栈操作。出栈和入栈均是O(1)。

缺点

1)由于入栈时,首先要创建插入的节点,要向操作系统申请内存,所以链栈没有顺序栈效率高。

队列

如果数据量已知就使用数组实现队列,未知的话就使用链表实现队列。出队和入队均是O(1)。

数据结构 优点 缺点
数组 插入快 查找慢、删除慢、大小固定
有序数组 查找快 插入慢、删除慢、大小固定
后进先出 存取其他项很慢
队列 先进先出 存取其他项很慢
链表 插入、删除快 查找慢
二叉树 查找、插入、删除快 算法复杂(删除算法)
红黑树 查找、插入、删除快 算法复杂
hash表 存取极快(已知关键字)、插入快 删除慢、不知关键字时存取很慢、对存储空间使用不充分
插入快、删除快、对大数据项存取快 对其他数据项存取慢
依据现实世界建模 算法有些复杂
AVL树 查找、插入、删除快 算法复杂

转自:常见数据结构应用场景

2016-06-08 06:43:37 zhangchen124 阅读数 7113

视频课: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*算法就是以此数据结构为基础,人工智能,也需要它的基础。