使用16位无符号整数数组在C中创建一个Maze类？

概述我正在尝试创建一个数据结构来代表C中的迷宫. 我需要关于迷宫的所有数据都可以使用按位运算以16位整数存储(以表示迷宫的每个单元格)： (来源：mazeworks.com) 16位无符号整数 所以,我想出了一个16位16位数组的数组,我很高兴能够使用我的Maze数据结构.我想保持数据结构的大小,以便我可以轻松创建very dense mazes. 因此,我需要能够在运行时动态创建一个n * m大小的 我正在尝试创建一个数据结构来代表C中的迷宫.

我需要关于迷宫的所有数据都可以使用按位运算以16位整数存储(以表示迷宫的每个单元格)：

(来源：mazeworks.com)
16位无符号整数

所以,我想出了一个16位16位数组的数组,我很高兴能够使用我的Maze数据结构.我想保持数据结构的大小,以便我可以轻松创建very dense mazes.

因此,我需要能够在运行时动态创建一个n * m大小的16位16位整数数组.在某处我读到C中的2d数组只是[n * m]大小的1d数组的合成糖,你可以通过[row col * wIDth]访问元素.

以下是我的工作尝试：

class Maze {    public:        Maze(int mazeWIDth,int mazeHeight)        {            mazeGrID = new unsigned int16_t[wIDth*height];            wIDth = mazeWIDth;            height = mazeHeight;        }        unsigned int16_t getArrayValue(int row,int col)        {            return mazeGrID[row + col*wIDth];        }        voID setArrayValue(int row,int col,unsigned int16_t value)        {            mazeGrID[row + col*wIDth] = value;        }    private:        int wIDth,height;        unsigned int16_t *mazeGrID;}

有一些C知识的人对我的迷宫课有什么建议吗？我对C很新,所以这对我来说都是一次学习经历.

解决方法 这将是一个很长的答案,因此它将触及一些编程/ c概念：封装,RAII,初始化列表,析构函数,常量,定义运算符,模板类,模板函数和位域,通过处理给定的问题.

首先,我总是从用户的角度开始设计.要为迷宫设计数据结构,用户将是想要使用数据结构的程序员(可能是您).从这个角度来看,结构是内存优化的这一事实是一个实现细节,与使用相关性较低.

使用您的知识库,我将首先更改接口,以便用户不需要关心内部结构,方法是定义一个封装位 *** 作的类,类似于此(我稍后将对其进行处理)：

class cell {public:   voID setBacktrace( unsigned int value ); // value must be between 0-15  unsigned int getBacktrace() const;  // same for all other fIEldsprivate:  uint16_t data;};

现在用户不需要关心低级细节.调用者代码可以简单地写：

cell c;c.setBacktrace( 5 ); // set the backtrace value to 5std::cout << c.getBacktrace() << std::endl;

现在,迷宫是一个围绕细胞物体的容器.正如其他人所指出的,您可以使用std :: vector来简化 *** 作,也可以定义自己的容器.既然我认为你正在学习,我们将遵循漫长的道路：

class maze {public:   maze( size_t wIDth,size_t height );   ~maze();   cell getCell( size_t row,size_t col ) const;   voID setCell( size_t row,size_t col,cell c );private:   size_t wIDth_;   size_t height_;   cell * data_;};

代码中接口的更改是：添加析构函数.它将负责释放构造函数请求的资源,遵循RAII惯用法.单元格元素的访问器标记为const,因为它只返回一个值而不更改结构.这是您应该从一开始就使用的另一个概念：将所有非变异方法标记为const.

现在来实施：

// Constructor and destructormaze::maze( size_t wIDth,size_t height )    : wIDth_( wIDth ),height_( height ),data_( new cell[wIDth*height] ){}maze::~maze(){   delete [] data_;}

使用初始化列表定义构造函数.在初始化列表中,字段wIDth_,height_和data_的字段构造函数被称为传递宽度,高度和新句子的返回指针作为参数.

使用初始化列表而不是在构造函数块({})中添加等效代码有两个原因.初始化列表比括号内的等效代码更有效(不是那么重要),但主要允许您调用特定的构造函数或初始化引用,这两者都不能在构造函数块内完成.

我添加了一个析构函数来释放你获得的数据.如果不向类中添加析构函数,编译器将提供一个默认的析构函数,该析构函数将调用类中所有属性的析构函数.在您的情况下,默认析构函数不会释放在构造期间获取的内存.

我不会详细介绍其他方法.到目前为止我们从用户的角度来看：

int main() {  maze m( 10,50 ); // Consctruct the maze  cell c;  c.setBacktrace( 5 );  m.setCell( 3,4,c);  // Store c in the container  assert( m.getCell( 3,4 ).getBacktrace() == 5 );}

通过改变一点界面,我们可以使这个代码更加用户友好.如果我们提供一个带有两个索引并返回对一个单元元素的引用的operator(),则使用将更简单(C++ FAQ lite on array-of-array interface)：

class maze {    // most everything as before,changing set/get to:public:   cell const & operator()( size_t row,size_t col ) const;   cell & operator()( size_t row,size_t col ); };

然后使用会更简单：

int main(){   maze m( 10,10 );   m( 3,4 ).setBacktrace( 5 );   assert( m( 3,4 ).getBacktrace() == 5 );}

不需要构造单元对象并对其应用更改然后存储对象,我们可以直接修改存储的对象.现在实施：

cell const & maze::operator()( size_t row,size_t col ) const{   return *data_[ row + col*wIDth_ ];}cell & maze::operator()( size_t row,size_t col ){   return *data_[ row + col*wIDth_ ];}

两个实现都是相似的,唯一的区别是第一个实现告诉编译器它不会改变迷宫的内容,并返回一个常量引用来保证调用者不会更改单元格.

在处理迷宫类之后,您会注意到唯一使它成为迷宫的是存储的数据是一个单元格,但所有逻辑都只是普通的2D数组.我们可以利用它并将其重新定义为模板类,以便我们可以在不同情况下重用代码,并使用不同的存储类型定义：

template <typename T> // stored dataclass array_2d{public:   array_2d( size_t wIDth,size_t height );   ~array_2d();   T const & operator()( size_t row,size_t col ) const;   T & operator()( size_t row,size_t col );private:   size_t wIDth_;   size_t height_;   T* data_;};

用法将是：

int main(){   array_2d<cell> maze( 10,10 );   maze( 3,4 ).setBacktrace( 5 );}

定义实现将略有不同,但不是更复杂：

template <typename T>array_2d<T>::array_2d( size_t wIDth,size_t height )   : wIDth_( wIDth ),data_( new T[ wIDth*height ] ){}

同样在定义每个方法的实现时.不是那么难,是吗？

最后,我们可以回到单元格的定义,并使其更自然地使用.我们拥有一组访问器方法,它们将执行按位 *** 作以与四个内部字段(回溯,解决方案,边界,墙壁)中的每一个进行交互.该单元格只是一个POD(普通旧数据)结构,存储四个整数字段,类似于：

struct big_cell{   unsigned int backtrack;   unsigned int solution;   unsigned int borders;   unsigned int walls;};

这可以用作：

int main(){   array_2d<big_cell> maze( 10,4 ).backtrack = 5;   assert( maze( 3,4 ).backtrack == 5 );}

但是这种结构将占用比我们要求更多的空间.存储实现细节迫使我们改变了类的用法.让我们尝试一下.将无符号整数更改为无符号字符会将结构的大小减小到32位(而不是完全优化结构的16位)：

struct medium_cell{   unsigned char backtrack;   unsigned char solution;   unsigned char borders;   unsigned char walls;};

这个解决方案每个单元只浪费2个字节,这可能不会太多(空间要求加倍,但现在内存很便宜).这也可以在32位处理器中更快地执行.一些32位架构需要更长的时间来检索和 *** 作16位元素.

无论如何,如果您仍然对完全紧凑的内存模型感兴趣,可以在C：位字段中使用一个不为人知的功能.它们允许您定义结构中的某些字段只需要多个位：

struct small_cell {   uint16_t backtrack : 4; // take 4 bits from the uint16_t   uint16_t solution : 4;   uint16_t borders : 4;   uint16_t walls : 4;};

并且ussage将是：

int main() {   small_cell c;   c.solution = 5;    c.backtrack = 3;}

现在这个结构只需要16位内存,可以像前两个结构一样使用.由于迷宫现在只是模板化的2d阵列,因此您可以非常轻松地测试这三种结构.您可以为测试定义模板函数.

#include <time.h>// templated for comparissons with cell typestemplate <typename CellStruct>voID test(){   array_2d< CellStruct > maze;   // Test operations...}voID print_test( std::string const & test,clock_t ticks ){   std::cout << "Test: " << test << " took " << ticks       << " ticks,or " << ticks / CLOCKS_PER_SEC << " seconds."       << std::endl;}int main(){   clock_t init = clock();   test< big_cell >();   clock_t after_big = clock();   test< medium_cell >();   clock_t after_med = clock();   test< small_cell >();   clock_t end = clock();   print_result( "big_cell",after_big - init );   print_result( "medium_cell",after_med - after_big );   print_result( "small_cell",end - after_med );}

测试函数仅被模板化,因此可以使用不同的单元实现来执行.一旦您知道哪种实现最适合您的问题域,您就可以制作将使用特定单元类型的特定代码.

@H_403_154@ 总结

以上是内存溢出为你收集整理的使用16位无符号整数数组在C中创建一个Maze类？全部内容，希望文章能够帮你解决使用16位无符号整数数组在C中创建一个Maze类？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。