精华内容
下载资源
问答
  • 压缩包中为 十字链表法创建图的 C 文件源文件,及对应的PPT 博客《【经典算法实现 30】图的创建 --- 十字链表法》 链接:https://blog.csdn.net/Ciellee/article/details/108199838
  • 对于压缩存储稀疏矩阵,无论是使用图 1 十字链表示意图可以看到,使用十字链表压缩存储稀疏矩阵时,矩阵中的各行各列都各用一各链表存储,与此同时,所有行链表的表头存储到一个数组(rhead),所有列链表的表头存储到...

    对于压缩存储稀疏矩阵,无论是使用

    3f8036b7ebfab3106d783e0471975c69.png

    图 1 十字链表示意图

    可以看到,使用十字链表压缩存储稀疏矩阵时,矩阵中的各行各列都各用一各链表存储,与此同时,所有行链表的表头存储到一个数组(rhead),所有列链表的表头存储到另一个数组(chead)中。

    因此,各个链表中节点的结构应如图 2 所示:

    ca1b3fe64d3a7ab0e74ca2f7f15dfc6f.png

    图 2 十字链表的节点结构

    两个指针域分别用于链接所在行的下一个元素以及所在列的下一个元素。

    链表中节点的 C 语言代码表示应为:

    typedef struct OLNode{

    int i,j;//元素的行标和列标

    int data;//元素的值

    struct OLNode * right,*down;//两个指针域

    }OLNode;

    同时,表示十字链表结构的 C 语言代码应为:

    #include

    #include

    typedef struct OLNode

    {

    int i, j, e; //矩阵三元组i代表行 j代表列 e代表当前位置的数据

    struct OLNode *right, *down; //指针域 右指针 下指针

    }OLNode, *OLink;

    typedef struct

    {

    OLink *rhead, *chead; //行和列链表头指针

    int mu, nu, tu; //矩阵的行数,列数和非零元的个数

    }CrossList;

    CrossList CreateMatrix_OL(CrossList M);

    void display(CrossList M);

    int main()

    {

    CrossList M;

    M.rhead = NULL;

    M.chead = NULL;

    M = CreateMatrix_OL(M);

    printf("输出矩阵M:\n");

    display(M);

    return 0;

    }

    CrossList CreateMatrix_OL(CrossList M)

    {

    int m, n, t;

    int i, j, e;

    OLNode *p, *q;

    printf("输入矩阵的行数、列数和非0元素个数:");

    scanf("%d%d%d", &m, &n, &t);

    M.mu = m;

    M.nu = n;

    M.tu = t;

    if (!(M.rhead = (OLink*)malloc((m + 1) * sizeof(OLink))) || !(M.chead = (OLink*)malloc((n + 1) * sizeof(OLink))))

    {

    printf("初始化矩阵失败");

    exit(0);

    }

    for (i = 1; i <= m; i++)

    {

    M.rhead[i] = NULL;

    }

    for (j = 1; j <= n; j++)

    {

    M.chead[j] = NULL;

    }

    for (scanf("%d%d%d", &i, &j, &e); 0 != i; scanf("%d%d%d", &i, &j, &e)) {

    if (!(p = (OLNode*)malloc(sizeof(OLNode))))

    {

    printf("初始化三元组失败");

    exit(0);

    }

    p->i = i;

    p->j = j;

    p->e = e;

    //链接到行的指定位置

    if (NULL == M.rhead[i] || M.rhead[i]->j > j)

    {

    p->right = M.rhead[i];

    M.rhead[i] = p;

    }

    else

    {

    for (q = M.rhead[i]; (q->right) && q->right->j < j; q = q->right);

    p->right = q->right;

    q->right = p;

    }

    //链接到列的指定位置

    if (NULL == M.chead[j] || M.chead[j]->i > i)

    {

    p->down = M.chead[j];

    M.chead[j] = p;

    }

    else

    {

    for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down);

    p->down = q->down;

    q->down = p;

    }

    }

    return M;

    }

    void display(CrossList M) {

    for (int i = 1; i <= M.nu; i++)

    {

    if (NULL != M.chead[i])

    {

    OLink p = M.chead[i];

    while (NULL != p)

    {

    printf("%d\t%d\t%d\n", p->i, p->j, p->e);

    p = p->down;

    }

    }

    }

    }

    运行结果:

    输入矩阵的行数、列数和非0元素个数:3 3 3

    2 2 3

    2 3 4

    3 2 5

    0 0 0

    输出矩阵M:

    2       2       3

    3       2       5

    2       3       4

    展开全文
  • 对于压缩存储稀疏矩阵,无论是使用三元组顺序,还是使用行逻辑链接的顺序,归根结底是使用数组存储稀疏矩阵。介于数组 “不利于插入和删除数据” 的特点,以上两种压缩存储方式都不适合解决类似 “向矩阵中添加...

    原文链接:http://data.biancheng.net/view/186.html

    对于压缩存储稀疏矩阵,无论是使用三元组顺序表,还是使用行逻辑链接的顺序表,归根结底是使用数组存储稀疏矩阵。介于数组 “不利于插入和删除数据” 的特点,以上两种压缩存储方式都不适合解决类似 “向矩阵中添加或删除非 0 元素” 的问题。
    例如,A 和 B 分别为两个矩阵,在实现 “将矩阵 B 加到矩阵 A 上” 的操作时,矩阵 A 中的元素会发生很大的变化,之前的非 0 元素可能变为 0,而 0 元素也可能变为非 0 元素。对于此操作的实现,之前所学的压缩存储方法就显得力不从心。
    本节将学习用十字链表存储稀疏矩阵,该存储方式采用的是 “链表+数组” 结构,如图 1 所示。
    在这里插入图片描述

    图 1 十字链表示意图

    可以看到,使用十字链表压缩存储稀疏矩阵时,矩阵中的各行各列都各用一各链表存储,与此同时,所有行链表的表头存储到一个数组(rhead),所有列链表的表头存储到另一个数组(chead)中。
    因此,各个链表中节点的结构应如图 2 所示:
    在这里插入图片描述

    图 2 十字链表的节点结构

    两个指针域分别用于链接所在行的下一个元素以及所在列的下一个元素。

    链表中节点的 C 语言代码表示应为:

    typedef struct OLNode{
        int i,j;//元素的行标和列标
        int data;//元素的值
        struct OLNode * right,*down;//两个指针域
    }OLNode;
    

    同时,表示十字链表结构的 C 语言代码应为:

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct OLNode
    {
        int i, j, e; //矩阵三元组i代表行 j代表列 e代表当前位置的数据
        struct OLNode *right, *down; //指针域 右指针 下指针
    }OLNode, *OLink;
    typedef struct
    {
        OLink *rhead, *chead; //行和列链表头指针
        int mu, nu, tu;  //矩阵的行数,列数和非零元的个数
    }CrossList;
    CrossList CreateMatrix_OL(CrossList M);
    void display(CrossList M);
    int main()
    {
        CrossList M;
        M.rhead = NULL;
        M.chead = NULL;
        M = CreateMatrix_OL(M);
        printf("输出矩阵M:\n");
        display(M);
        return 0;
    }
    CrossList CreateMatrix_OL(CrossList M)
    {
        int m, n, t;
        int i, j, e;
        OLNode *p, *q;
        printf("输入矩阵的行数、列数和非0元素个数:");
        scanf("%d%d%d", &m, &n, &t);
        M.mu = m;
        M.nu = n;
        M.tu = t;
        if (!(M.rhead = (OLink*)malloc((m + 1) * sizeof(OLink))) || !(M.chead = (OLink*)malloc((n + 1) * sizeof(OLink))))
        {
            printf("初始化矩阵失败");
            exit(0);
        }
        for (i = 1; i <= m; i++)
        {
            M.rhead[i] = NULL;
        }
        for (j = 1; j <= n; j++)
        {
            M.chead[j] = NULL;
        }
        for (scanf("%d%d%d", &i, &j, &e); 0 != i; scanf("%d%d%d", &i, &j, &e)) {
            if (!(p = (OLNode*)malloc(sizeof(OLNode))))
            {
                printf("初始化三元组失败");
                exit(0);
            }
            p->i = i;
            p->j = j;
            p->e = e;
            //链接到行的指定位置
            if (NULL == M.rhead[i] || M.rhead[i]->j > j)
            {
                p->right = M.rhead[i];
                M.rhead[i] = p;
            }
            else
            {
                for (q = M.rhead[i]; (q->right) && q->right->j < j; q = q->right);
                p->right = q->right;
                q->right = p;
            }
            //链接到列的指定位置
            if (NULL == M.chead[j] || M.chead[j]->i > i)
            {
                p->down = M.chead[j];
                M.chead[j] = p;
            }
            else
            {
                for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down);
                p->down = q->down;
                q->down = p;
            }
        }
        return M;
    }
    void display(CrossList M) {
        for (int i = 1; i <= M.nu; i++)
        {
            if (NULL != M.chead[i])
            {
                OLink p = M.chead[i];
                while (NULL != p)
                {
                    printf("%d\t%d\t%d\n", p->i, p->j, p->e);
                    p = p->down;
                }
            }
        }
    }
    

    运行结果:

    输入矩阵的行数、列数和非0元素个数:3 3 3
    2 2 3
    2 3 4
    3 2 5
    0 0 0
    输出矩阵M:
    2 2 3
    3 2 5
    2 3 4

    展开全文
  • 数据结构——十字链表法(C语言实现) 直接上代码 //十字链表 十字链表只能存储有向图 #include "stdio.h" #include "stdlib.h" #define max 100 //弧结点 typedef struct ArcBox { int headvex, tailvex; //...

    数据结构——十字链表法(C语言实现)

    • 直接上代码
    //十字链表 十字链表只能存储有向图 
    #include "stdio.h"
    #include "stdlib.h"
    #define max 100
    //弧结点
    typedef struct ArcBox {
    	int  headvex, tailvex; //起点和终点在顺序表中的索引
    	struct ArcBox *hlink, *tlink; //起点或终点相同的弧
    //	int info; 						//权 
    }ArcBox;
    //顶点结点 
    typedef struct VexNode {
    	ArcBox *firstin, *firstout; //出边和入边链表
    	int data;			//数据 
    }VexNode;
    //图 
    typedef struct {
    	VexNode xlist[max];			
    	int vexnum, arcnum;			//顶点个数和边的个数 
    }OLGraph;
    //定义邻接矩阵 
    typedef struct {
    	int existbool;
    	ArcBox *node;
    }Arr;
    int main()
    {
    	OLGraph graph;
    	printf("请输入图的顶点个数与边的个数:\n");
    	scanf("%d %d",&graph.vexnum,&graph.arcnum);
    	int i,j,k,flag;
    	printf("请输入顶点数据:\n"); 
    	//初始化顶点 
    	for (i = 0;i < graph.vexnum;i++)
    	{
    		scanf("%d", &graph.xlist[i].data);
    		graph.xlist[i].firstin = NULL;
    		graph.xlist[i].firstout = NULL;
    	}
    	Arr a[max][max];
    	//利用邻接矩阵初始化十字链表 
    	printf("请输入十字链表的邻接矩阵:\n");
    	//分配内存 
    	//初始化矩阵 
    	for (i = 0;i < graph.vexnum;i++)
    	{
    		for (j = 0;j < graph.vexnum;j++)
    		{
    			scanf("%d", &a[i][j].existbool);
    			if (a[i][j].existbool == 0)
    				continue;
    			a[i][j].node = (ArcBox*)malloc(sizeof(ArcBox));
    			a[i][j].node->headvex = j;
    			a[i][j].node->tailvex = i;
    			a[i][j].node->hlink = NULL;
    			a[i][j].node->tlink = NULL;
    		}
    	}
    	for (i = 0;i < graph.vexnum;i++)
    	{
    		flag = 0;
    		for (j = 0;j < graph.vexnum;j++)
    		{
    			if (a[i][j].existbool == 0)
    				continue;
    			for (k = j + 1;k < graph.vexnum;k++)
    			{
    				if (a[i][k].existbool == 1)
    					break;
    			}
    			if (k >= graph.vexnum)
    				a[i][j].node->tlink = NULL;
    			else
    				a[i][j].node->tlink = a[i][k].node;
    			if (flag == 0)
    				graph.xlist[i].firstout = a[i][j].node;
    			flag = 1;
    		}
    	}
    	for (i = 0;i < graph.vexnum;i++)
    	{
    		flag = 0;
    		for (j = 0;j < graph.vexnum;j++)
    		{
    			if (a[j][i].existbool == 0)
    				continue;
    			for (k = j + 1;k < graph.vexnum;k++)
    			{
    				if (a[k][i].existbool == 1)
    					break;
    			}
    			if (k >= graph.vexnum)
    				a[j][i].node->hlink = NULL;
    			else
    				a[j][i].node->hlink = a[k][i].node;
    			if (flag == 0)
    				graph.xlist[i].firstin = a[j][i].node;
    			flag = 1;
    		}
    	}
    	printf("十字链表初始化完成!\n");
    	printf("图中有%d个结点,%d条边\n",graph.vexnum,graph.arcnum);
    	int count;
    	ArcBox* s;
    	for (i = 0;i < graph.vexnum;i++)
    	{
    		printf("关于第[%d]个结点[%d],指出的边信息如下:\n",i+1,graph.xlist[i].data); 
    		count = 0;
    		s = graph.xlist[i].firstout;
    		while (s != NULL)
    		{
    			count++;
    			printf("第%d条:指向第[%d]个结点[%d]\n", count, s->headvex + 1, graph.xlist[s->headvex].data);
    			s = s->tlink;
    		}
    		count = 0;
    		printf("指入的边信息如下:\n");
    		s = graph.xlist[i].firstin;
    		while(s != NULL)
    		{
    			count++;
    			printf("第%d条:被第[%d]个结点[%d]指入\n",count,s->tailvex+1,graph.xlist[s->tailvex].data);
    			s = s->hlink;
    		}
    	}
    	return 0;
    }
    

    中间多次循环代码冗杂,可优化,初学轻喷。

    展开全文
  • AOI之十字链表法

    千次阅读 2018-05-29 20:35:22
    1. 简介AOI主要有九宫格、灯塔和十字链表的算法实现。本文阐述十字链表的实现2. 基本原理若是二维地图,将地图内的对象按照坐标值,从小到大分在x轴和y轴两个链表上。如果是三维地图,则还需要维护多一个z轴的链表3...

    1. 简介

    AOI主要有九宫格、灯塔和十字链表的算法实现。本文阐述十字链表的实现

    2. 基本原理

    若是二维地图,将地图内的对象按照坐标值,从小到大分在x轴和y轴两个链表上。如果是三维地图,则还需要维护多一个z轴的链表

    3. 基本接口

     Add:对象进入场景

    Move:对象在场景内移动

    Leave:对象离开场景

    4. 代码如下,注释非常详尽

    scene.h

    #ifndef __CScene_H__
    #define __CScene_H__
    #include <map>
    #include <list>
    using namespace std;
    
    // 注意:本示例的AOI范围指的是以对象为中心的正方形
    
    // 地图内的对象
    class CEntity 
    {
    public:
    	int x;			// X坐标
    	int y;			// Y坐标
    	int id;			// 对象的唯一ID
    	int radius;		// 对象的AOI半径
    
    	list<CEntity*>::iterator	x_pos;	// X链上的指针
    	list<CEntity*>::iterator	y_pos;	// Y链上的指针
    
    	CEntity(int _id, int _x, int _y, int _radius) : id(_id), x(_x), y(_y), radius(_radius) 
    	{
    	}
    };
    
    typedef map<int, CEntity*>	EntityMap;
    typedef list<CEntity*>		EntityList;
    
    // 场景
    class CScene 
    {
    public:
        CScene();
        ~CScene();
    
    	// 添加一个新的对象插入到指定坐标(x,y)
        void Add(int id, int x, int y, int distance = 2);
    
    	// 移动一个对象,新位置点(x,y)
        void Move(int id, int x, int y);
    
    	// 删除一个对象
        void Leave(int id);
    
    private:
    	// 获取指定对象的AOI对象列表
    	void GetRangeSet(CEntity* pEntity, EntityMap* pEntityMap);
    
    	// 更新对象CEntity到坐标(x,y)
        void UpdateEntityPosition(CEntity* pEntity, int x, int y);
    
    private:
    	EntityMap		m_mapEntity;	// 本场景所有的对象
    	EntityList		m_listXEntity;	// X链
    	EntityList		m_listYEntity;	// Y链
    };
    
    #endif  // __CScene_H__
    

    scene.cpp

    #include <math.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include "scene.h"
    
    CScene::CScene() 
    {
    }
    
    CScene::~CScene() 
    {
    	// 删除场景内的所有对象
        EntityMap::iterator tmp;
        for (EntityMap::iterator iter = m_mapEntity.begin(); iter != m_mapEntity.end(); ) 
    	{
            tmp = iter;
            ++iter;
            delete tmp->second;
        }
    }
    
    // 添加一个新的对象插入到指定坐标(x,y)
    void CScene::Add(int id, int x, int y, int distance) 
    {
    	// 已经存在该ID,直接返回
        if (m_mapEntity.find(id) != m_mapEntity.end()) 
    	{
            return;
        }
    
    	// 新创建一个对象
        CEntity* pEntity = new CEntity(id, x, y, distance);
        m_mapEntity[pEntity->id] = pEntity;
    
    	EntityList::iterator iter;
    
    	// 在X链上找到插入位置	
    	for (iter = m_listXEntity.begin(); iter != m_listXEntity.end();iter++)
    	{
    		if ((*iter)->x > x)
    		{
    			break;
    		}
    	}
    	
    	// 在iter位置前面插入,同时记录下在X链上的位置
    	pEntity->x_pos = m_listXEntity.insert(iter,pEntity);
    
    	// 在Y链上找到插入位置	
    	for (iter = m_listYEntity.begin(); iter != m_listYEntity.end();iter++)
    	{
    		if ((*iter)->y > y)
    		{
    			break;
    		}
    	}
    
    	// 在iter位置前面插入,同时记录下在Y链上的位置
    	pEntity->y_pos = m_listYEntity.insert(iter,pEntity);
    
    	// 获取AOI列表
    	EntityMap newMap;
    	GetRangeSet(pEntity, &newMap);
    
    	// 1. 把pEntity的进入AOI消息通知他们 
    	// 2. 通知pEntity,他们进入了AOI
    	for (EntityMap::iterator iter = newMap.begin(); iter != newMap.end(); ++iter) 
    	{
    		printf("send [%d:(%d,%d)]\t ENTER msg to obj [%d:(%d,%d)]\n",pEntity->id, pEntity->x, pEntity->y,iter->first, iter->second->x, iter->second->y);
    		printf("send [%d:(%d,%d)]\t ENTER msg to obj [%d:(%d,%d)]\n",iter->first, iter->second->x, iter->second->y,pEntity->id, pEntity->x, pEntity->y);
    	}
    }
    
    // 更新对象CEntity到坐标(x,y)
    void CScene::UpdateEntityPosition(CEntity* pEntity, int x, int y) 
    {
    	// 原来的坐标
        int old_x = pEntity->x;
        int old_y = pEntity->y;
    
    	// 新坐标
        pEntity->x = x;
        pEntity->y = y;
    
        EntityList::iterator iter;
    
    	// 查找新的X坐标
    	
    	// 如果新坐标的x比旧坐标的x大,就往后面遍历
        if (pEntity->x > old_x) 
    	{
            if (pEntity->x_pos != m_listXEntity.end()) 
    		{
    			// 取得原X指针位置
                iter = pEntity->x_pos;
    
    			// 往后面移动一个节点,作为搜索起始节点
                ++iter;
                
    			// 删除X链的旧节点
    			m_listXEntity.erase(pEntity->x_pos);
    
    			// 往后面遍历
                while (iter != m_listXEntity.end()) 
    			{
    				// 找到第一个x值大于新坐标x指的节点
                    if ((*iter)->x > pEntity->x) 
    				{
                        break;
                    }
                    ++iter;
                }
    
    			// X链新位置上插入,并记录位置
    			pEntity->x_pos = m_listXEntity.insert(iter, pEntity);
            }
        } 
    	else if (x < old_x)  // 如果新坐标的x比旧坐标的x小,就往前面遍历
    	{
            if (pEntity->x_pos != m_listXEntity.begin()) 
    		{
    			// 取得原X指针位置
                iter = pEntity->x_pos;
    
    			// 往前面移动一个节点,作为搜索起始节点
                --iter;
    
    			// 删除旧节点
                m_listXEntity.erase(pEntity->x_pos);
    
    			// 往前面遍历
                while (iter != m_listXEntity.begin()) 
    			{
    				// 找到第一个x值小于新坐标x指的节点
                    if ((*iter)->x < pEntity->x) 
    				{
    					// 要指向该节点的下一个节点,因为iter是第一个比pEntity的x值小的,那么后面一个节点才是大于等于x值的,应该插在这个节点前面才对
                        ++iter;
                        break;
                    }
                    --iter;
                }
    
    			// X链新位置上插入,并记录位置
    			pEntity->x_pos = m_listXEntity.insert(iter, pEntity);
            }
    		else
    		{
    			// 不需处理,因为已经是最前面了,x,y坐标改了就行
    		}
        }
    
        // 如果新坐标的y值比旧坐标的y值大,就往后面遍历
        if (y > old_y) 
    	{
            if (pEntity->y_pos != m_listYEntity.end()) 
    		{
    			// 取得原y指针位置
                iter = pEntity->y_pos;
    
    			// 往后面移动一个节点,作为搜索起始节点
                ++iter;
    
    			// 删除Y链的旧节点
                m_listYEntity.erase(pEntity->y_pos);
    
    			// 往后面遍历
                while (iter != m_listYEntity.end()) 
    			{
    				// 找到第一个y值大于新坐标y值的节点
                    if ((*iter)->y > pEntity->y) 
    				{
                        break;
                    }
                    ++iter;
                }
    
    			// Y链新位置上插入,并记录位置
    			pEntity->y_pos = m_listYEntity.insert(iter, pEntity);
            }
        } 
    	else if (y < old_y) // 如果新坐标的x比旧坐标的x小,就往前面遍历
    	{
            if (pEntity->y_pos != m_listYEntity.begin()) 
    		{
    			// 取得原y指针位置
                iter = pEntity->y_pos;
    
    			// 往前面移动一个节点,作为搜索起始节点
                --iter;
    
    			// 删除Y链的旧节点
                m_listYEntity.erase(pEntity->y_pos);
    
    			// 往前面遍历
                while (iter != m_listYEntity.begin()) 
    			{
    				// 找到第一个y值小于新坐标y值的节点
                    if (pEntity->y - (*iter)->y > 0) 
    				{
    					// 要指向该节点的下一个节点,因为iter是第一个比pEntity的y值小的,那么后面一个节点才是大于等于y值的,,应该插在这个节点前面才对
    					++iter;
                        break;
                    }
                    --iter;
                }
    
    			// Y链新位置上插入,并记录位置
    			pEntity->y_pos = m_listYEntity.insert(iter, pEntity);
            }
        }
    }
    
    // 移动一个对象,新位置点(x,y)
    void CScene::Move(int id, int x, int y) 
    {
    	// 在对象列表中查找该对象
        EntityMap::iterator iterEntity = m_mapEntity.find(id);
        if (iterEntity == m_mapEntity.end()) 
    	{
            return;
        }
    
    	// 该对象指针
        CEntity* pEntity = iterEntity->second;
        
    	// 旧AOI列表,新AOI列表
    	EntityMap oldMap, newMap;
    
        // 获取旧的AOI列表
        GetRangeSet(pEntity, &oldMap);
    
        // 更新对象位置到新坐标(x,y)
        UpdateEntityPosition(pEntity, x, y);
    
        // 获取新的AOI列表
        GetRangeSet(pEntity, &newMap);
    
    	// 遍历旧AOI列表里面的对象
    	// 若在新AOI列表里面存在,说明该对象是两次AOI列表里面的交集,把pEntity的移动消息通知他们
    	// 若在新AOI列表里面不存在,则说明是要删除的对象(操作如下 1.把pEntity的离开AOI消息通知他们 2. 通知pEntity,他们离开了AOI)
        for (EntityMap::iterator iter = oldMap.begin(); iter != oldMap.end(); ++iter) 
    	{
            if (newMap.find(iter->first) != newMap.end()) 
    		{
    			printf("send [%d:(%d,%d)]\t MOVE msg to obj [%d:(%d,%d)]\n",pEntity->id, pEntity->x, pEntity->y, iter->first, iter->second->x, iter->second->y);
            }
    		else
    		{
    			printf("send [%d:(%d,%d)]\t LEAVE msg to obj [%d:(%d,%d)]\n",pEntity->id, pEntity->x, pEntity->y,iter->first, iter->second->x, iter->second->y);
    			printf("send [%d:(%d,%d)]\t LEAVE msg to obj [%d:(%d,%d)]\n",iter->first, iter->second->x, iter->second->y,pEntity->id, pEntity->x, pEntity->y);
    		}
        }
    
        // 遍历新AOI列表里面的对象
    	// 若在交集move_set中不存在,则说明是新添加的对象(操作如下 1.把pEntity的进入AOI消息通知他们 2. 通知pEntity,他们进入了AOI)
        for (EntityMap::iterator iter = newMap.begin(); iter != newMap.end(); ++iter) 
    	{
            if (oldMap.find(iter->first) == oldMap.end()) 
    		{
    			printf("send [%d:(%d,%d)]\t ENTER msg to obj [%d:(%d,%d)]\n",pEntity->id, pEntity->x, pEntity->y,iter->first, iter->second->x, iter->second->y);
    			printf("send [%d:(%d,%d)]\t ENTER msg to obj [%d:(%d,%d)]\n",iter->first, iter->second->x, iter->second->y,pEntity->id, pEntity->x, pEntity->y);
            }
        }
    }
    
    // 获取指定对象的AOI对象列表
    void CScene::GetRangeSet(CEntity* pEntity, EntityMap* pEntityMap) 
    {
    	if (pEntity == NULL || pEntityMap == NULL)
    	{
    		return;
    	}
    
    	// X链上的AOI范围内的对象,注意:并不是最终的AOI对象,因为还要检测Y链上的位置是否在AOI范围内
        EntityMap x_map;
    
    
        EntityList::iterator iter;
        
    	// X链上往后面遍历
    	iter = pEntity->x_pos;
    	while(iter != m_listXEntity.end())
    	{
    		++iter;
    		
    		// 到了最后,跳出
    		if (iter == m_listXEntity.end()) 
    		{
    			break;
    		}
    
    		// 正向距离已经超过半径,跳出
    		if ((*iter)->x - pEntity->x > pEntity->radius) 
    		{
    			break;
    		}
    
    		// 添加进X方向的AOI集合
    		x_map[(*iter)->id] = *iter;
    	}
    
    	// X链上往前面遍历
    	iter = pEntity->x_pos;
    	while(iter != m_listXEntity.begin())
    	{
    		--iter;
    
    		// 负向距离已经超过半径,跳出
    		if (pEntity->x - (*iter)->x > pEntity->radius) 
    		{
    			break;
    		}
    
    		// 添加进X方向的AOI集合
    		x_map[(*iter)->id] = *iter;
    
    		// 到了最前面,跳出,注意:不能放在加入AOI集合的前面,因为begin()位置也是有效对象
    		if (iter == m_listXEntity.begin()) 
    		{
    			break;
    		}
    	}
    	
    	// Y链上往后面遍历
    	iter = pEntity->y_pos;
    	while(iter != m_listYEntity.end())
    	{
    		++iter;
    
    		// 到了最后,跳出
    		if (iter == m_listYEntity.end()) 
    		{
    			break;
    		}
    
    		// 正向距离已经超过半径,跳出
    		if ((*iter)->y - pEntity->y > pEntity->radius) 
    		{
    			break;
    		}
    
    		// X方向AOI集合中存在的,则添加该对象到最终的AOI列表中
    		if (x_map.find((*iter)->id) != x_map.end()) 
    		{
    			(*pEntityMap)[(*iter)->id] = *iter;
    		}
    	}
    
    
    	// Y链上往前面遍历
    	iter = pEntity->y_pos;
    	while(iter != m_listYEntity.begin())
    	{
    		--iter;
    
    		// 负向距离已经超过半径,跳出
    		if (pEntity->y  - (*iter)->y > pEntity->radius) 
    		{
    			break;
    		}
    
    		// X方向AOI集合中存在的,则添加该对象到最终的AOI列表中
    		if (x_map.find((*iter)->id) != x_map.end()) 
    		{
    			(*pEntityMap)[(*iter)->id] = *iter;
    		}
    
    		// 到了最前面,跳出,注意:不能放在加入AOI集合的前面,因为begin()位置也是有效对象
    		if (iter == m_listYEntity.begin()) 
    		{
    			break;
    		}
    	}
    }
    
    // 删除一个对象
    void CScene::Leave(int id) 
    {
    	// 对象列表中是否存在该ID
        EntityMap::iterator iterEntity = m_mapEntity.find(id);
        if (iterEntity == m_mapEntity.end()) 
    	{
            return;
        }
    
    	// 找到该对象
        CEntity* pEntity = iterEntity->second;
    
        // 获取该对象的AOI列表
    	EntityMap leaveMap;
        GetRangeSet(pEntity, &leaveMap);
    
    	// 通知AOI列表中的每个对象,pEntity要离开了
    	// 通知pEntity,你看不到AOI列表中的每个对象了
    	for (EntityMap::iterator iter = leaveMap.begin(); iter != leaveMap.end(); ++iter) 
    	{
    		printf("send [%d:(%d,%d)]\t LEAVE msg to obj [%d:(%d,%d)]\n",pEntity->id, pEntity->x, pEntity->y,iter->first, iter->second->x, iter->second->y);
    		printf("send [%d:(%d,%d)]\t LEAVE msg to obj [%d:(%d,%d)]\n",iter->first, iter->second->x, iter->second->y,pEntity->id, pEntity->x, pEntity->y);
    	}
    
    	// X链,Y链上删除
        m_listXEntity.erase(pEntity->x_pos);
        m_listYEntity.erase(pEntity->y_pos);
    
    	// 对象列表中删除
        m_mapEntity.erase(iterEntity);
    
    	// 释放对象
        delete pEntity;
    }

    测试代码test.cpp

    #include <stdlib.h>
    #include <stdio.h>
    #include <time.h>
    #include "scene.h"
    
    int main() 
    {
    	// 新建一个场景
        CScene scene;
    
        printf("步骤一:添加5个对象\n");
    	scene.Add(1,1,5);	// 对象1,坐标(1,5)
    	scene.Add(2,2,2);	// 对象2,坐标(2,2)
    	scene.Add(3,3,1);	// 对象3,坐标(3,1)
    	scene.Add(4,5,3);	// 对象4,坐标(5,3)
    	scene.Add(5,6,6);	// 对象5,坐标(6,6)
    
        printf("步骤二:添加一个新的对象到坐标(3,3)\n");
    	scene.Add(6,3,3);	// 对象6,坐标(3,3)
    
    	printf("步骤三:把对象3移动到坐标(4,4)\n");
    	scene.Move(6,4,4);
    
        printf("步骤四:移除这6个对象\n");
        for (int i = 1; i <= 6; ++i) 
    	{
            scene.Leave(i);
        }
    
    	system("pause");
        return 0;
    }

    分析:

    步骤一完成后结果如下:


    步骤二完成后结果如下(红色框表示AOI范围):


    步骤三完成后结果如下(红色框表示移动后的AOI范围):


    笔者这里的结果打印如下:


    展开全文
  • 图的存储结构:十字链表法十字链表的定义:十字链表法的代码定义: 十字链表法的定义: 顶点节点: 1、data:顶点数据域 2、firstin:入边单链表头指针 3、firstout:出边单链表头指针 边节点: 1、tailvex:尾域...
  • AOI主要有九宫格、灯塔和十字链表的算法实现。本文阐述十字链表的实现 目前就考虑的是二维坐标,若是二维地图,将地图内的对象按照坐标值,从小到大分在x轴和y轴两个链表上。如果是三维地图,则还需要维护多一个z轴...
  • Python 十字链表法实现的AOI
  • 文章目录三元组顺序行逻辑链接的顺序表十字链表 三元组顺序   稀疏矩阵由于其自身的稀疏特性,通过压缩可以大大节省稀疏矩阵的内存代价。具体操作是:将非零元素所在的行、列以及它的值构成一个三元组(i,j...
  • #include<stdio.h>...//十字链表法 存储 稀疏矩阵 //普通节点 typedef struct OLNode{ int col,row; float value; struct OLNode *right,*down; }OLNode; //总头结点–存放:行数,列数,非0元数(k...
  • //释放十字链表空间 int main() {  pList L = Init();  int count = 1;  while (count <= L->num)  {  Insert(L);  count++;  }  puts("按行打印三元组");  Ptint1(L);  puts("按列打印三元...
  • 个人理解: 可以设想一个场景,一个矩阵是从左往右,从上往下,按左上角到右下角的方向生成的。在每个行和列交叉的节点上存储数据。那这些数据间有何种联系,采用何种方式可以方便的对任意节点的数据进行读写操作?...
  • 图的十字链表存储详解

    千次阅读 2020-04-15 12:38:45
    前面介绍了图的邻接存储,本节继续讲解图的另一种链式存储结构——十字链表法。 与邻接不同,十字链表法仅适用于存储有向图和有向网。不仅如此,十字链表法还改善了邻接计算图中顶点入度的问题。 十字链表...
  • 图的存储结构——十字链表法 (1)定义结构体 #define MaxVertexNum 30 typedef int VexLocalType; //结点位序 typedef char VertexType; //结点类型 typedef int WeighType; //权值类型 typedef struct ArcNode {...
  • 【经典算法实现 30】十字链表实现图的保存一、十字链表法1.1 画出所有顶点1.2 画出所有的边1.3 完善边与顶点的出边关系1.4 完善边与顶点的入边关系二、十字链表代码实现 之前写了这么多树的文章,本文要开始学习图了...
  • 此稀疏矩阵我们打算采用十字链表进行存储。 代码实现及结果测试: ... 稀疏矩阵的十字链表法实现方式 */ //十字链表的元素结点 typedef struct OLNode{ int i,j,value; //i行标 j列标 value元素值 struc...
  • 用C++编写的稀疏矩阵乘法运算,稀疏矩阵采用十字链表存储及计算
  • 十字链表法表示矩阵例如,用十字链表表示矩阵 A ,为:图2 矩阵用十字链表表示由此可见,采用十字链表表示矩阵时,矩阵的每一行和每一个列都可以看作是一个单独的链表,而之所以能够表示矩阵,是因...
  • 重点记住节点说明
  • #pragma once #include "pch.h" namespace map { typedef class map10listarc { public: int tail, head;//弧尾节点序号,头节点序号 int info;...//相同头,尾节点的弧域 }arc; typedef cl...
  • (六)图的十字链表存储详解

    千次阅读 2019-03-20 16:46:51
    与邻接不同,十字链表法仅适用于存储有向图和有向网。不仅如此,十字链表法还改善了邻接计算图中顶点入度的问题。 十字链表存储有向图(网)的方式与邻接有一些相同,都以图(网)中各顶点为首元节点建立多条...
  • 数据结构稀疏矩阵实验课程设计 /********function definition********/ int init_matrix(crosslist &one) {//initialization one.row_size=0; one.colum_size=0; one.non_zero_amount=0; one.rhead=NULL;...
  • 十字链表:有向图 邻接多重:无向图
  • 数据结构——十字链表(C语言实现)

    千次阅读 多人点赞 2020-11-09 17:22:26
    十字链表是将邻接和逆邻接结合在一起的一种有向图的数据结构 十字链表的节点结构体表示的是一个节点到另一个节点的边,并且此由指出节点(from)和指入节点(to)共同使用,因此大大节省了内存。 先直观感受一下...
  • 十字链表实现稀疏矩阵 1.问题描述 用十字链表存储和表示稀疏矩阵,并实现如下功能 2.基本要求 初始化:创建十字链表并从文件中读取稀疏矩阵数据(文件数据可以是三元组结构); 在十字链表上设置坐标为(i,j...
  • 十字链表存储稀疏矩阵算法,实现两个矩阵的乘法运算
  • 什么是十字链表

    千次阅读 2020-08-05 18:05:15
    十字链表是一种存储稀疏矩阵的方法,该存储方式采用的是 "链表+数组" 结构,如图 1 所示。 图 1 十字链表示意图 可以看到,使用十字链表压缩存储稀疏矩阵时,矩阵中的各行各列都各用一各链表存储,与此同时,...
  • 十字链表-稀疏矩阵 C++ 代码 十字链表-稀疏矩阵 C++ 代码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,499
精华内容 2,199
关键字:

十字链表法

友情链接: GVAR_Order_Flow.zip