文件系統(tǒng)-多叉樹(shù)與二叉樹(shù)的轉(zhuǎn)化

在這一節(jié)中，我們來(lái)學(xué)習(xí)如何使用程序來(lái)實(shí)現(xiàn)一棵文件樹(shù)。在上一節(jié)中，我們了解到使用文件樹(shù)的方式來(lái)整合計(jì)算機(jī)中所有的資源，而這一棵文件樹(shù)則是一棵多叉樹(shù)。也就是說(shuō)，樹(shù)上的每一個(gè)節(jié)點(diǎn)都可能有多個(gè)子節(jié)點(diǎn)。

而這樣的一棵多叉樹(shù)在計(jì)算機(jī)中來(lái)實(shí)現(xiàn)是較為復(fù)雜的，使用起來(lái)也不方便。例如我們想要為節(jié)點(diǎn)1增加一個(gè)子節(jié)點(diǎn)2，之后再為節(jié)點(diǎn)1增加一個(gè)子節(jié)點(diǎn)3，之后再為節(jié)點(diǎn)1增加一個(gè)子節(jié)點(diǎn)4。整個(gè)過(guò)程如下圖：

由于這是一棵多叉樹(shù)，因此節(jié)點(diǎn)1可能具有多個(gè)子節(jié)點(diǎn)。這樣一來(lái)，在為節(jié)點(diǎn)1分配內(nèi)存時(shí)，我們就無(wú)法確定的為其分配指定大小，由于樹(shù)型結(jié)構(gòu)的特點(diǎn)，我們需要使用一個(gè)指針變量用于指向其一個(gè)子節(jié)點(diǎn)，而如果其具有2個(gè)子節(jié)點(diǎn)，則需要2個(gè)指針變量，如果其具有3個(gè)子節(jié)點(diǎn)，則需要3個(gè)指針變量。

于是對(duì)于多叉樹(shù)來(lái)說(shuō)，當(dāng)一個(gè)節(jié)點(diǎn)增加一個(gè)子節(jié)點(diǎn)時(shí)，當(dāng)前節(jié)點(diǎn)也需要發(fā)生變化，也就是需要重新申請(qǐng)一個(gè)較大的內(nèi)存空間用于存放更多的指針變量。同樣的，當(dāng)一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)被刪除時(shí)，也需要重新申請(qǐng)內(nèi)存，釋放多余的指針變量。這對(duì)于編程實(shí)現(xiàn)多叉樹(shù)來(lái)說(shuō)，是很復(fù)雜的，也是低效的。因此我們有必要尋找一種簡(jiǎn)潔的辦法來(lái)處理多叉樹(shù)的實(shí)現(xiàn)問(wèn)題。

我們知道，使用計(jì)算機(jī)編程來(lái)實(shí)現(xiàn)一個(gè)二叉樹(shù)是非常簡(jiǎn)單的，每一個(gè)節(jié)點(diǎn)除了實(shí)際數(shù)據(jù)區(qū)域外只需要額外兩個(gè)指針用于存放其左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)即可，而且其內(nèi)存申請(qǐng)和釋放都很簡(jiǎn)潔。二叉樹(shù)就是每一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)最多不能超過(guò)2個(gè)節(jié)點(diǎn)，如下圖則是一個(gè)二叉樹(shù)：

為了解決多叉樹(shù)的問(wèn)題，我們自然想到是否能將一個(gè)多叉樹(shù)轉(zhuǎn)化為一個(gè)二叉樹(shù)，并使用計(jì)算機(jī)程序來(lái)實(shí)現(xiàn)呢？答案是肯定的！其實(shí)，每一棵多叉樹(shù)都可以轉(zhuǎn)化為一個(gè)等價(jià)的二叉樹(shù)。進(jìn)而可以將一個(gè)具有多個(gè)多叉樹(shù)的森林轉(zhuǎn)化為一個(gè)與之等價(jià)的二叉樹(shù)。

具體轉(zhuǎn)化的過(guò)程是這樣的：我們可以定義一個(gè)二叉樹(shù)的節(jié)點(diǎn)，并定義兩個(gè)指針變量，這兩個(gè)指針變量分別為指向其“子節(jié)點(diǎn)”（child）和其“兄弟節(jié)點(diǎn)”（sibling），也就是說(shuō)，一個(gè)二叉樹(shù)的兩個(gè)叉，左側(cè)表示其孩子，而右側(cè)表示其兄弟。于是我們就可以將一個(gè)多叉樹(shù)轉(zhuǎn)化一個(gè)二叉樹(shù)，具體轉(zhuǎn)化過(guò)程如下：

上圖中的多叉樹(shù)和二叉樹(shù)是等價(jià)的，這兩棵樹(shù)所表示的內(nèi)容完全一致，只是在結(jié)構(gòu)上不同而已。也就是說(shuō)這棵多叉樹(shù)可以轉(zhuǎn)化為二叉樹(shù)，二叉樹(shù)也可以轉(zhuǎn)化為多叉樹(shù)，本質(zhì)上講它們二者是可以相互轉(zhuǎn)化的，而沒(méi)有任何的不同。

對(duì)于這棵二叉樹(shù)來(lái)講，其“左叉”表示其孩子節(jié)點(diǎn)，而“右叉”表示其兄弟節(jié)點(diǎn)。而二叉樹(shù)在計(jì)算機(jī)程序中是比較容易實(shí)現(xiàn)的。接下來(lái)我們就定義這樣一棵二叉樹(shù)，用于表示其原有的多叉樹(shù)：

typedef struct vfs_node_s
{
  struct vfs_node_s *child;
  struct vfs_node_s *sibling;
  char name[200];
} vfs_node_s;

我們簡(jiǎn)單的定義name屬性為表示這個(gè)節(jié)點(diǎn)的數(shù)據(jù)內(nèi)容，而左叉child為其子節(jié)點(diǎn)，而右叉sibling為其兄弟節(jié)點(diǎn)。然后實(shí)現(xiàn)兩函數(shù)用于初始化和銷毀這個(gè)虛擬文件樹(shù)：

int vfs_init(void)
{
  vfs = malloc(sizeof(vfs_s));
  vfs- >root = malloc(sizeof(vfs_node_s));
  strncpy(vfs- >root- >name, "/", NODE_NAME_SIZE);
  vfs- >root- >child = NULL;
  vfs- >root- >sibling = NULL;


  return 0;
}


int vfs_destory(void)
{
  vfs_destory_r(&vfs- >root);
  free(vfs);
  return 0;
}

完成初始化和銷毀虛擬文件樹(shù)之后我們?cè)賮?lái)實(shí)現(xiàn)對(duì)任意節(jié)點(diǎn)進(jìn)行的插入和刪除操作，也就是說(shuō)針對(duì)虛擬文件樹(shù)，我們?cè)谥付ㄎ恢貌迦胍粋€(gè)新的節(jié)點(diǎn)：

int vfs_insert_node(char *path, file_operations_s ops)
{
  if (path[0] != '/')
  {
    return -1;
  }
  //插入子節(jié)點(diǎn)，調(diào)用遞歸函數(shù)
  int ret = vfs_insert_node_r(&vfs- >root- >child, &path[1], ops);
  return ret;
}


int vfs_insert_node_r(vfs_node_s **node, char *abs_path, file_operations_s ops)
{
  if (node == NULL)
  {
    return -1;
  }
  if (abs_path == NULL)
  {
    return -1;
  }
  if (abs_path[0] == 0)
  {
    return -1;
  }
  char node_name[NODE_NAME_SIZE] = {0};
  //找到虛擬文件樹(shù)上的指定路徑
  char *p = abs_path;
  for (int i = 0; *p != '/' && *p != 0 && i < NODE_NAME_SIZE; i++)
  {
    node_name[i] = *p++;
  }
  if (*p == '/' && *p != 0)
  {
    p++;
  }
  //查找其所有兄弟節(jié)點(diǎn)
  while (*node != NULL)
  {
    //找到兄弟節(jié)點(diǎn)
    if (strcmp((*node)- >name, node_name) == 0)
    {
      //遞歸執(zhí)行其子節(jié)點(diǎn)插入操作
      return vfs_insert_node_r(&(*node)- >child, p, ops);
    }
    node = &(*node)- >sibling;
  }


  //最后生成一個(gè)新節(jié)點(diǎn)
  vfs_node_s *node_new = malloc(sizeof(vfs_node_s));
  strncpy(node_new- >name, node_name, NODE_NAME_SIZE);
  node_new- >child = NULL;
  node_new- >sibling = NULL;
  *node = node_new;
  //將新節(jié)點(diǎn)插入
  if (*p != 0)
  {
    return vfs_insert_node_r(&node_new- >child, p, ops);
  }
  return 0;
}

這樣，我們就完成了二叉樹(shù)的創(chuàng)建、銷毀與插入功能，當(dāng)然還應(yīng)該實(shí)現(xiàn)針對(duì)指定節(jié)點(diǎn)的刪除功能，這里我們不再給出具體實(shí)現(xiàn)代碼，請(qǐng)讀者自行完成。這樣的二叉樹(shù)就可以完整的表示我們計(jì)算機(jī)中的虛擬文件系統(tǒng)（根節(jié)點(diǎn)是虛擬節(jié)點(diǎn)，并非是實(shí)際存在的，Linux系統(tǒng)中的根節(jié)點(diǎn)是實(shí)際的硬盤分區(qū)，因此Linux的文件系統(tǒng)不是虛擬文件系統(tǒng)）。

此后我們就可以用這一棵二叉樹(shù)來(lái)表示計(jì)算機(jī)中的所有資源了，具體方式則是將資源抽象成一個(gè)文件，掛載到文件系統(tǒng)中，成為文件系統(tǒng)中的一個(gè)節(jié)點(diǎn)，這樣就可以方便用戶管理和使用這些資源了。