万星星@豌豆荚 欢迎加入我们
一个吃软饭的男人!!!!!我只想写程序####
微博:http://weibo.com/wanlianwen
posts - 172,  comments - 1253,  trackbacks - 0

一个学期课程结束,接着去公司改bug。以前做的一个网格控件老是出问题,于是下狠心重新实现一个!

准备实现一个网格数据结构,来存储网格控件数据。为了以后也可以使用,写了一个模板类,基本思想是写3个类:

/********************************************************************
 created: 2006/01/12
 created: 12:1:2006   14:30
 filename:  E:\MyProject\WLWLib\WLWGrid\WLWGrid.h
 file path: E:\MyProject\WLWLib\WLWGrid
 file base: WLWGrid
 file ext: h
 author:  万连文
 
 purpose: 为了存储二维网格m×n数据,实现插入删除访问
    用链表实现,适合大数据量(非海量数据)频繁插入删除使用
    不适合稀疏矩阵使用,不适合海量数据,因为稀疏矩阵会浪费
    很多单元格,海量数据会浪费很多单元格里面的指针
*********************************************************************/

// 网格单元类,存储数据,记录方位
template<class T>
class WLWGridCell
{
public:
 WLWGridCell(T xData, WLWGridCell* pLeft=0, WLWGridCell* pUp=0, WLWGridCell* pRight=0, WLWGridCell* pDown=0)
 {
  SetData(xData);
  SetLeft(pLeft);
  SetRight(pRight);
  SetUp(pUp);
  SetDown(pDown);
  m_lReserve = 0;
 }
 ~WLWGridCell()
 {
  SetLeft(0);
  SetRight(0);
  SetUp(0);
  SetDown(0);
 }
 // 设置数据
 void   SetData(T xData);

 // 获得数据
 T    GetData();

 // 设置保留数据
 void   SetReserve(long lReserve);

 // 获得保数据
 long   GetReserve();
 
 // 设置上方单元
 void   SetUp(WLWGridCell* pUp);

 // 获得上方单元
 WLWGridCell* GetUp();

 // 设置下方单元
 void   SetDown(WLWGridCell* pDown);

 // 获得下方单元
 WLWGridCell* GetDown();

 // 设置左方单元
 void   SetLeft(WLWGridCell* pLeft);

 // 获得左方单元
 WLWGridCell* GetLeft();

 // 设置右方单元
 void   SetRight(WLWGridCell* pRight);

 // 获得右方单元
 WLWGridCell* GetRight();
private:
 WLWGridCell* m_pUp;  // 上方单元
 WLWGridCell* m_pDown; // 下方单元
 WLWGridCell* m_pLeft; // 左方单元
 WLWGridCell* m_pRight; // 右方单元

 T    m_xData; // 存储数据
 long   m_lReserve; // 保留数据
};

// 网格行类,存储一行数据
template<class T>
class WLWGridRow
{
public:
 WLWGridRow(WLWGridRow<T>* pUp=0, WLWGridRow<T>* pDown=0)
 {
  m_pHead  = 0;
  m_pTail  = 0;
  m_pCurr  = 0;
  m_lReserve = 0;
  m_pUp  = pUp;
  m_pDown  = pDown;
 }
 ~WLWGridRow()
 {
  // 销毁所有网格
  Empty();
 }

 // 获得当前的行头指针
 WLWGridCell<T>* GetHead();

 // 获得当前的行尾指针
 WLWGridCell<T>* GetTail();

 // 设置上一行
 void   SetUpRow(WLWGridRow<T>* pUp);

 // 获得上一行
 WLWGridRow<T>* GetUpRow();

 // 设置下一行
 void   SetDownRow(WLWGridRow<T>* pDown);

 // 获得下一行
 WLWGridRow<T>* GetDownRow();

 // 获得当前的游标指针
 WLWGridCell<T>* GetCurrent();

 // 按照索引获得单元格
 WLWGridCell<T>* GetCellByIndex(int iIndex);

 // 按照单元格获得索引,失败返回-1
 int    GetIndexByCell(WLWGridCell<T>* pCell);

 // 当前指针右移
 void   MoveNext();

 // 当前指针左移
 void   MoveBack();

 // 当前指针行头
 void   MoveHead();

 // 当前指针行尾
 void   MoveTail();

 // 判断是否有下一个
 bool   HasNext();

 // 判断是否有上一个
 bool   HasBack();

 // 判断是否为空
 bool   IsEmpty();

 // 清空行数据
 void   Empty();

 // 设置保留数据
 void   SetReserve(long lReserve);

 // 获得保数据
 long   GetReserve();

 // 添加一个单元格,bRight=true表示添加在pos后面
 // 可能修改m_pHead、m_pTail
 // 返回<0表示添加失败;=0表示已存在;>0表示成功
 int    AddCell(WLWGridCell<T>* pCell, WLWGridCell<T>* pPos, bool bRight=true);
 
 // 添加一个单元格,iIndex是索引,bRight=true表示添加在iIndex后面
 // 可能修改m_pHead、m_pTail
 // 返回<0表示添加失败;=0表示已存在;>0表示成功
 int    AddCell(WLWGridCell<T>* pCell, int iIndex, bool bRight=true);

 // 删除指定单元格,可能修改m_pHead、m_pTail、m_pCurr
 void   DelCell(WLWGridCell<T>* pCell);

 // 删除指定单元格,iIndex是索引,表示单元格的位置
 // 可能修改m_pHead、m_pTail、m_pCurr
 void   DelCell(int iIndex);

 // 查找指定值的单元格,失败返回-1,否则返回索引
 int    Find(T x);

 // 重载[]运算符
 WLWGridCell<T>* operator[](int iIndex);
private:
 WLWGridCell<T>* m_pHead; // 记录一行的头
 WLWGridCell<T>* m_pTail; // 记录一行的尾
 WLWGridCell<T>* m_pCurr; // 当前游标位置,遍历的时候使用

 WLWGridRow<T>* m_pUp;  //上一行
 WLWGridRow<T>* m_pDown; //下一行
 long   m_lReserve; // 保留数据
};

// 网格类,实现二维表格结构
template<class T>
class WLWGrid
{
public:
 WLWGrid()
 {
  m_pHead  = 0;
 }
 ~WLWGrid()
 {
  Empty();
 }
 // 获得头行
 WLWGridRow<T>* GetHead();

 // 获得列数
 int    GetCols();

 // 获得行数
 int    GetRows();

 // 判断是否为空
 bool   IsEmpty();

 // 清空表格
 void   Empty();

 // 按照索引获得行
 WLWGridRow<T>* GetRowByIndex(int iIndex);

 // 按照行获得索引,失败返回-1
 int    GetIndexByRow(WLWGridRow<T>* pRow);
 
 // 指定位置添加一行,bRight=true表示添加在pos后面
 // 可能修改m_pHead
 // 注意行的单元格数目必须等于Grid的列数,否则不添加
 // 返回<0添加失败,0已存在,>0添加成功
 int    AddRow(WLWGridRow<T>* pRow, WLWGridRow<T>* pPos, bool bDown=true);
 
 // 指定位置添加一行,iIndex是索引,bRight=true表示添加在pos后面
 // 可能修改m_pHead
 // 注意行的单元格数目必须等于Grid的列数,否则不添加
 // 返回<0添加失败,0已存在,>0添加成功
 int    AddRow(WLWGridRow<T>* pRow, int iIndex, bool bDown=true);

 // 指定位置添加值为xData的一行,bRight=true表示添加在pos后面
 // 可能修改m_pHead
 void   AddRow(T xData, WLWGridRow<T>* pPos, bool bDown=true);
 
 // 指定位置添加值为xData的一行,iIndex是索引,bRight=true表示添加在pos后面
 // 可能修改m_pHead
 void   AddRow(T xData, int iIndex, bool bDown=true);
 
 // 删除指定行,可能修改m_pHead
 void   DelRow(WLWGridRow<T>* pRow);

 // 删除指定索引的行,可能修改m_pHead
 void   DelRow(int iIndex);

 // 指定位置添加值为xData的一列,bRight表示在iIndex索引右面添加,否则在左面添加
 // 添加成功返回true
 bool   AddCol(T xData, int iIndex, bool bRight=true);

 // 删除下标为iIndex的一列
 void   DelCol(int iIndex);

 // 重载[]运算符
 WLWGridRow<T>* operator[](int iIndex);
private:
 WLWGridRow<T>* m_pHead; // 头行

 // 更新行单元格的指针,确保两行长度一致,否则会导致非预期结果(0指针除外)
 void   UpdateRowCellPtr(WLWGridRow<T>* pUp, WLWGridRow<T>* pDown);
};

化了接近一天时间写完,并经过简单测试,没有发现内存泄漏问题。

看测试截图  表现网格结构

下载网格数据结构及测试代码

希望大家下载使用,提出建议,报告bug,最重要是内存泄漏问题,谢谢!

posted on 2006-01-13 17:12 万连文 阅读(1276) 评论(4)  编辑 收藏 引用 所属分类: 乱七八糟

FeedBack:
# re: 数据结构之网格实现
2006-01-16 10:36 | 小明
意见来了。

看一个库的接口好坏,从使用者上看是一个好的角度

你的测试代码
m_aRow = new WLWGridRow<int>();
m_aRow->AddCell(new WLWGridCell<int>(1), m_aRow->GetTail());
if(m_aGrid.AddRow(m_aRow, m_aGrid.GetHead()) < 0)


1.为什么要new WLWGridCell<int>(0)
这样是不是更好
m_aRow->AddCell(1, m_aRow->GetTail());

2.如果使用者这样写
WLWGridRow<int> wl;
if(m_aGrid.AddRow(&wl, m_aGrid.GetHead()) < 0)
程序会崩溃吧,两次delete,STL容器使用的方法普遍是copy in,copy out,效率是要付出一些,但是很稳定可靠

如果一定是使用指针传入,建议可以使用这样声明的方式
Class WLWGrid
...
int AddRow(WLWGridRow<T>* &pRow, WLWGridRow<T>* pPos, bool bDown=true)
{
pRow = 0; //avoid delete twice
}

WLWGridRow<T>* &pRow声明成指针引用的形式,表明你是要代替使用者来管理节点类的生命周期

3.其实使用vector< vector<type*> > 就能很好的实现你的需要,简单可靠

4.不要把template的实现放在cpp文件中



  回复  更多评论
  
# re: 数据结构之网格实现
2006-01-16 20:26 | 万连文
非常感谢批评!!
对于1建议非常好,当时由于时间以及个人主观因素没有实现
对于2由于现在在公司,没法看,但是有可能是自己代码有问题。里面的小技巧很少用,呆会研究一下,谢谢共享技术
对于3我则不认同,如果vector< vector<type*> >可以方便实现我的需求的话我不会花费那么大代价了。其实一般获取数据是可以满足的,但是在插入和删除数据时会非常麻烦(不在尾部的话)。还考虑到移动数据的原因所以采用链表实现,其实可以采用list实现,处于一个想学数据结构的朋友的建议才自己动手的
对于4其实我是违背了模板的思想,强制把实现放入cpp,可能会误导他人,当时只是为了玩玩,原以为可以show一下,没想到贻笑大方了
再次感谢小明兄,技术可见厉害。  回复  更多评论
  
# re: 数据结构之网格实现
2006-01-16 22:12 | 万连文
问题一已经修改,添加两个接口函数
// 添加一个单元格,bRight=true表示添加在pos后面
// 可能修改m_pHead、m_pTail
// 返回<=0表示添加失败;>0表示成功
int AddCell(T xData, WLWGridCell<T>* pPos, bool bRight=true);

// 添加一个单元格,iIndex是索引,bRight=true表示添加在iIndex后面
// 可能修改m_pHead、m_pTail
// 返回<=0表示添加失败;>0表示成功
int AddCell(T xData, int iIndex, bool bRight=true);
问题二无法修改,因为不想拷贝,使用的时候必须要交付内存管理权限否则无法正确运行,必须注意。  回复  更多评论
  
# re: 数据结构之网格实现
2006-01-17 20:48 | 万连文
针对以上建议做如下修改:
2006-1-16
WLWGridRow类添加两个函数接口以方便用户使用:
int AddCell(T xData, WLWGridCell<T>* pPos, bool bRight=true);
int AddCell(T xData, int iIndex, bool bRight=true);

2006-1-17
WLWGridRow类和WLWGrid类接口传递指针方式改为传递指针引用,
为了避免用户传入栈地址导致两次析构,如:
int AddCell(WLWGridCell<T>* pCell, int iIndex, bool bRight=true);
改为:
int AddCell(WLWGridCell<T>*& pCell, int iIndex, bool bRight=true);

2006-1-17
WLWGridRow类添加一个拷贝构造函数  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


简历下载
联系我

<2006年1月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(66)

随笔分类

随笔档案

相册

搜索

  •  

最新评论

阅读排行榜

评论排行榜