Sqlite数据库存储目录结构邻接表的实现2-目录树的构建

目录

 一、概述

二、数据库存储目录结构邻接表

三、目录树的构建

1、数据结构

2、代码实现构建树

四、QTreeWidget显示目录树

---

 一、概述

        存储目录结构（树）是一个常见的问题，有多种解决方案。方法主要有邻接表、进阶邻接列表、改进的前序树遍历、递归查询、枚举路径、嵌套集、闭包表等。

二、数据库存储目录结构邻接表

        我们将尝试的第一种也是最优雅的方法叫做“邻接表模型”或“递归方法”。这是一个很好的方法，因为你只需要一个简单的函数来遍历你的树。在我们的食品商店中，邻接表看起来像这样:

​         如你所见，在邻接表方法中，你保存了每个节点的“父节点”。我们可以看到‘Pear’是‘Green’的子，是‘Fruit’的子等等。根节点“Food”没有父值。为了简单起见，我使用“title”值来标识每个节点。当然，在真实的数据库中，您将使用每个节点的数字id。

三、目录树的构建

1、数据结构

     最近想在数据库的某一字段里面设置多个字符串信息，如何截取其中的某个字符串？需要在数据库获取parentID这个属性进行相应的操作。

struct dirpro
{
    char type;
    char opType;
    char parentID[32];
    char rerserved[128-32-1-1];
    
};

struct DirProNode
{
    int id;
    std::string name;
    std::string parId;
    QLinkedList<DirProNode> children;
};

struct DirInfo
{
    int id;
    std::string name;
    dirpro pro;
};

2、代码实现构建树

DirProNode getTree()
{

   std::vector<DirInfo> vInfos =getdirproFromDb();//从数据库中读取所有的目录信息
   
   DirProNode root;//根节点
   root.id=-1; 
   root.parId="NULL";
   root.name="root";
   int nsize=vInfos.size();
   std::map<std::string,DirProNode*> mapDirThink;
   std::vector<bool> vecMark;
   vecMark.resize(nsize);
   for(int i=0;i<nsize;++i)
   {
     vecMark[i]=false;
   }

  while(true)
  {
   int ncount=0;
    for(int i=0;i<nsize;++i)
   {  
    if(vecMark[i])
     {continue;}
     DirProNode dirproNode;
     if(convert(vInfos[i],dirproNode)
     {
       
       if(dirproNode.parId=="NULL" || dirproNode.parId.isEmpty())
       {
         root.children.push)back(dirproNode);
         mapDirThink[QString::number(dirproNode.id).c_str()]=&(root.children.back());
         ncount++;
         vecMark[i]=true;
       }
       else
       {
         mapDirThink[dirproNode.parId]->children.push_back(dirproNode);
         mapDirThink[QString::number(dirproNode.id).c_str()]=&(root.children.back());
         ncount++;
         vecMark[i]=true;
  
       }
      
     }
     else
     {
       vecMark[i]=false;
     }
     }
     if(ncount==0)
     {break;}
  }
   
    return root;
}

四、QTreeWidget显示目录树

         有了DirProNode这个数据结构，我们就可以使用先序遍历构建目录结构并在QTreeWidget中进行显示。