c - 浏览链表

Question

我正在尝试创建一个稀疏(链接)结构，其中每个节点都指向其所有子节点(总共 5 个)。到目前为止，我只创建了第一个节点(称为“root”)。我正在尝试遍历链接结构，希望程序将返回“root”。它给我一个段错误。

主类

Item n;

newDirectory();
printf("Folder root has been created.");

printf("Enter the name of the directory you want to traverse: ");
scanf("%s", n.name);
browseItem(n);

我创建的结构

typedef struct Directory{
   //name of the file
   char name[16];
   //file content
   char value[80];
   _Bool isLeaf;

   //if folder status = 1, if txt status = 2, if empty status = 0
   int status;
   struct Directory *firstchild;
   struct Directory *secondchild;
   struct Directory *thirdchild;
   struct Directory *fourthchild;
   struct Directory *fifthchild;
}Item;

我也包含了结构所在的类函数

//points to the first node: node "root" 
Item *head;

//creates the first (head) node: "root"
void newDirectory(){
  head = (Item *)malloc(sizeof(Item));

  if(head == NULL){
      printf("Unable to allocate memory.");
  }else{
      strcpy(head->name,"root");
      head->status = 1;
      head->firstchild = NULL;
      head->secondchild = NULL;
      head->thirdchild = NULL;
      head->fourthchild= NULL;
      head->fifthchild = NULL;
  }
}


void browseItem(Item n) {
   //how do I find the location of n
   Item *tmp;
   tmp = (Item *)malloc(sizeof(Item));
   if(head == NULL){
       printf("List is empty!");
   }else{
      tmp = **location of n**;
      while(tmp!=NULL){
          printf("%s", tmp->name);
          tmp = tmp->firstchild;
          tmp = tmp->secondchild;
          tmp = tmp->thirdchild;
          tmp = tmp->fourthchild;
          tmp = tmp->fifthchild;
      }
   }
}

我的问题是如何首先搜索 n 的位置，以便程序从该节点开始遍历。如果我有来自根的节点越多，子节点也会被遍历吗？

非常感谢!

Answer 1

段错误通常是由数据传输不正确引起的。您的代码和逻辑存在一些问题。让我尽力回答您的所有问题:

首先，您的链表并不是真正的链表，它是一棵树。链表将指向下一个节点。这是一个单向链表，双向链表会指向下一个节点，和前一个节点。它们都是一样的，除了树只有更多的 child ，而链表只有 1 个 child ，双向链表也有一个指向父(或前一个元素)的指针。

您的第二个问题似乎是，我如何获取 root 权限？

"I am trying to traverse the linked structure, hoping that the program will return 'root'."

目前，你的代码是这样的:root--> child 1, child 2, child 3 (这是一棵树)。如果您希望您的代码改为链表，则它必须是 root--> child1 --> child2 --> child3 ... 等等。但是，你的链表是单向链表，也就是说你只能向前走，不能向后走。如果你想回到根目录，那就是null<--root--> <--child1--> <--child 2 --> <-- ... --> ，依此类推(您必须有一个指针，指向前一个节点，就像双向链表一样)。

那么对于你如何找到 n 的问题？

//how do I find the location of n

只有从 root 开始并以这种方式遍历链表才能做到这一点。使用链表来做到这一点的最简单方法是:

Item tmp = head->child1;
while (tmp != null)
{
    if (tmp -> name == n)
    {
         print "Found n!" + tmp->name
         break;
    }
    tmp = tmp -> nextChild;

}

这段代码只是为了让它看起来更简单的伪代码。

如果它是一棵树，那么就必须使用广度优先算法，或者深度优先算法来找到 n。如果您的代码试图模仿文件结构，则应使用树，而不是链表。