如何搜索和排序名称（字符串）BST？通过队列和缩进印刷？ [英] How to search and sort BST by name(string)? Printing by queue and indented?

问题描述

我必须写一个程序，读取一个txt文件到树上，然后允许它执行特定的操作。我卡在那里，我需要按名称排序树，按名称搜索以及部分，任何输入将是真棒。
所以，我的输入文件的格式为：

I have to write a program that reads a .txt file into the tree and then it allows to perform specific operations with it. I'm stuck on the part where I need to sort tree by names and search by name as well, any input would be awesome. So, my input file is in the format :

3800 Lee, Victor; 2.8 
3000 Brown, Joanne; 4.0

所以，我的二叉树是在格式为：

So, my binary tree is in the format of:

 typedef struct
 {
 int   id;
 char  name[MAX_NAME_LEN];
 float gpa;
 } STUDENT;

typedef struct node
{
 STUDENT*        dataPtr;
 struct node* left;
 struct node* right;
} NODE;

typedef struct
{
 int   count;
 int  (*compare) (void* argu1, void* argu2); // Was provided by teacher, not really sure how this works
 NODE*  root;
} BST_TREE;

阅读文件，并插入功能工作得很好，但我不知道如何实现由名称（字符串）的搜索。将strcmp的工作？如果是的话，我将如何使用它？我有一个工作的搜索功能，但它的优化来搜索编号（整数），它不与字符串工作。
下面是搜索功能的一部分：

Read file and insert functions are working just fine, but I dont know how to implement search by name(string). Will strcmp work? If so, how would I use it? I have a working search function, but it's optimized to search for id(integer) and it doesn't work with strings. Here is a part of search function:

/*  ===================== _retrieve =====================
Searches tree for node containing requested key
and returns its data to the calling function.
   Pre     _retrieve passes tree, dataPtr, root
           dataPtr is pointer to data structure
              containing key to be located
   Post    tree searched; data pointer returned
   Return  Address of data in matching node
           If not found, NULL returned
 */
 static void* _retrieve (BST_TREE* tree,
              void* dataPtr, NODE* root)
 {
if (root){
     if (tree->compare(dataPtr, root->dataPtr) < 0)
         return _retrieve(tree, dataPtr, root->left);
     else if (tree->compare(dataPtr, root->dataPtr) > 0)
         return _retrieve(tree, dataPtr, root->right);
     else
         // Found equal key
         return root;
}  // if root
else
    // Data not in tree
    return NULL;
 }// _retrieve

另外，我怎么排序的BST？我特别将如何通过名称是字符串，由两部分组成（姓和名）排序呢？我应该仅由第一个字符排序呢？我在想不知何故下降姓氏的一部分，使它更容易被名字只能看，因为我的老师并没有真正指明她是怎么想完成这件事的。她从来没有告诉我们有关非整数值排序BST，所以我迷路了。

Also, how do I sort the BST? Especially how would I sort it by name which is string and consists of 2 parts (first and last name)? Should I sort it only by the first character? I was thinking of dropping the last name part somehow and making it easier to look only by first names since my teacher didn't really specify how she wants this done. She never told us about sorting BST by non-integer values, therefore I'm lost.

一件事是，这棵树就需要通过打印：水平（队列），为缩进列表和只长叶子。
    缩进打印清单的例子：

One more thing is that this tree would need to be printed by: level(queue), as indented list and by leaves only. Example of indented printed list:

  1.50
   2.70
     3.80
     3.90
   2.60
     3.30

我真的AP preciate关于执行这些任务的任何建议。

I would really appreciate any suggestions on implementing those tasks.

感谢您

推荐答案

没有，的strcmp（）因为比较传递两者不会直接合作，学生* 值（伪装成无效* 。所以你必须编写解包的指针比较，然后调用的strcmp（）：

No, strcmp() won't work directly, because the comparator is passed two STUDENT * values (disguised as void *. So you will have to write a comparator that unpackages the pointers and then calls strcmp():

int cmp_by_name(const void *v1, const void *v2)
{
    const STUDENT *s1 = (STUDENT *)v1;
    const STUDENT *s2 = (STUDENT *)v2;

    return strcmp(s1->name, s2->name);
}

有将是那些谁说铸件不是绝对必要的。将会有那些谁观察到的变量可以通过在呼叫使用稍微复杂一点的前pressions到 STRCMP被忽略（）。但是，如果你决定，你需要在GPA或身份证号比较过，然后有局部变量会更干净。编译器可能会消除反正变量作为常规的优化，所以这样做，在手动清晰的成本是'premature优化的情况。

There will be those who say the casts are not absolutely necessary. There will be those who observe that the variables could be omitted by using slightly more complex expressions in the call to strcmp(). However, if you decide that you need to compare on GPA or ID number too, then having the local variables will be cleaner. The compiler will probably eliminate the variables anyway as a routine optimization, so doing that manually at the cost of clarity is a case of 'premature optimization'.

由于您正在使用的模板不包括常量在比较类型的声明，则可能需要忽略常量从函数定义行。

Because the templates you are working with don't include const in the declaration of the comparator type, you may have to omit const from the function definition line.

您不需要排序的BST;该数据已经被存储在排序顺序。你可以用树的中序遍历打印出来的排序顺序。

You don't need to sort the BST; the data is already stored in a sorted order. You can print it out in sorted order with an in-order traversal of the tree.

您只需设置比较元素的 BST_TREE 到 cmp_by_name ：

BST_TREE root = { 0, cmp_by_name, 0 };

您再打电话给你的功能与＆放大器;根作为树的根。这是代替你提供比较功能。你应该建立和比较单一的功能搜索树;使用在不同的时间，不同的比较会引起混乱。

You then call your functions with &root as the root of the tree. This is instead of the comparison function you were provided with. You should build and search the tree with a single comparison function; using different comparators at different times will cause chaos.

您不需要扎普逗号，如果您使用的是ISO 8859 $ C $账套，如8859-15，或者如​​果你使用的Uni code。逗号排序比任何信件较早，所以这些名字依次是：

You don't need to zap the comma if you're using an ISO 8859 code set such as 8859-15, or if you're using Unicode. The comma sorts earlier than any letters, so these names are in order:

Lee, James
Lee, Kirk
Leeds, Shaw
Left, Right

你不得不问题的唯一情况是如果数据不是一致的：

The only time you'd have problems is if the data is not consistent:

Lee James
Lee, Brady

这就是排序顺序;你可能会想本末倒置。

That's the sorted order; you'd probably want the order reversed.

这篇关于如何搜索和排序名称（字符串）BST？通过队列和缩进印刷？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！