c++ - 在数组中搜索以及搜索和遍历树

Question

努力完成本学期的最后一项作业。不是在寻找“答案”，只是在寻找一些见解。自从我上次实际编程课以来已经有很长时间了，因为这是一门数据结构课，我们不审查代码。作业:

用于在数组中搜索以及搜索和遍历树的程序。

1. Ask the user to enter the name of the input data file
2. Load 150 random ordered values from a file into an array in unsorted order. Print out the array to ensure random order is maintained.
3. Load the same 150 random ordered numbers into a binary search tree. Print out the traversal of the tree in prefix, infix and postfix order to ensure binary tree created properly.
4. Load the same 150 random number ordered numbers into an array. Use ANY sort routine you want to write to order the numbers into ascending order. Print out the array to ensure numbers are in ascending sequence.

5. Using a counting loop ask the user to enter 10 numbers – the user will enter 5 numbers that are in the list and 5 that are NOT in the list.

   • a. Search each data structure and count the number of comparisons needed to find the value or determine that the number is not in the list.

   • i. Unsorted array – use a linear search

   • ii. Binary search tree – binary search
   • iii. Sorted array – binary search

b. Print out the results in a table format for each search

• i. Value
• ii. “found”/”not found”
• iii. Number of comparisons linear search
• iv. Number of comparisons binary search tree
• v. Number of comparisons binary search array

c. Print out summary

• i. Total number of comparisons linear search
• ii. Total number of comparisons binary search tree
• iii. Total number of comparisons binary search array

到目前为止的代码，我知道我离开了:

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string>

struct bintreenode {
    int value;
    struct bintreenode* l;
    struct bintreenode* r;
} *root = NULL, *temp = NULL;

typedef struct bintreenode N;

void insert();
N* bt(int arr[], int, int);
N* new(int);

void infix(N* t);
void prefix(N* t);
void postfix(N* t);

void main() {
    ifstream inputData;
    ofstream outputData;
    string fileName;
    cout << "Enter the name of the input data file: " << endl;
    //asks user to input filename
    cin >> fileName; //inputs user input into fileName
    return 1;
    ifstream file("file.txt");
    if (file.is_open()) {
        string myArray[150];
        for (int i = 0; i < 150; ++i) {
            file >> myArray[i];
        }
    }
    int ch, i, n;
    int arr[] = {
        1, 2, 3, 4, 136, 137, 138, 139, 56, 78, 9, 10,
        16, 17, 18, 58, 59, 60, 61, 19, 20, 21, 22, 23,
        24, 118, 119, 120, 121, 25, 26, 27, 28, 29, 128,
        129, 130, 131, 33, 34, 35, 36, 37, 38, 39, 40, 41,
        42, 43, 44, 45, 46, 145, 146, 147, 148, 11, 12, 13,
        14, 15, 47, 48, 49, 55, 56, 57, 62, 63, 64, 30, 31,
        32, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 142, 143,
        144, 75, 76, 77, 78, 79, 50, 51, 52, 53, 80, 81, 82,
        83, 85, 91, 92, 96, 93, 94, 95, 97, 98, 99, 100, 101,
        102, 103, 104, 105, 54, 106, 107, 108, 109, 110, 111,
        112, 113, 114, 115, 116, 117, 122, 123, 124, 125, 126,
        127, 132, 133, 84, 86, 87 88, 89, 90, 134, 135, 140, 141,
        149, 150
    };

    n = sizeof(arr) / sizeof(arr[0]);
    printf("\n1- infix\n");
    printf("2 - postfix\n");
    printf("\nEnter 10 numbers in the list and 10 numbers not in the list : ");
    scanf("%d", &ch);
    switch (ch) {
    case 1:
        root = bt(arr, 0, n - 1);
        printf("Given infix traversal as input\n");
        for (i = 0; i <= 6; i++)
            printf("%d->", arr[i]);
        printf("\nprefix traversal of tree\n");
        prefix(root);
        printf("\ninfix traversal of tree\n");
        infix(root);
        printf("\npostfix traversal of tree\n");
        postfix(root);
        break;
    case 2:
        insert();
        printf("\nprefix traversal of tree\n");
        prefix(root);
        printf("\nInfix traversal of tree\n");
        infix(root);
        printf("\npostfix traversal of tree\n");
        postfix(root);
        break;
    default:
        printf("enter correct choice");
    }

    /* To create a binary search tree */
    N* bt(int arr[], int first, int last) {
        int mid;
        N* root = (N*)malloc(sizeof(N));
        if (first > last)
            return NULL;
        mid = (first + last) / 2;
        root = new(arr[mid]);
        root->l = bt(arr, first, mid - 1);
        root->r = bt(arr, mid + 1, last);
        return root;
    }
    /* to print infix of tree */
    void infix(N* t) {
        if (t->l != NULL)
            infix(t->l);
        printf("%d->", t->value);
        if (t->r != NULL)
            infix(t->r);
    }
    /* to print prefix traversal of tree */
    void prefix(N* t) {
        printf("%d->", t->value);
        if (t->l != NULL)
            infix(t->l);
        if (t->r != NULL)
            infix(t->r);
    }
    /* to print postfix traversal of tree */
    void postfix(N* t) {
        if (t->l != NULL)
            infix(t->l);
        if (t->r != NULL)
            infix(t->r);
        printf("%d->", t->value);
    }
    bool tree::search(int num) {
        node* temp = head;
        while (temp != NULL) {
            if (temp->data == num)
                break;
            if (num > temp->data)
                temp = temp->right;
            else
            if (num < temp->data)
                temp = temp->left;
        }
        if (temp == NULL)
            printf("Not Found");
        if (temp->data == num)
            printf("Found");
        return false;
    }
}

Answer 1

以下是我发现的一些问题:

不要越过溪流

    #include <stdio.h>  
    #include <iostream>
    #include <fstream>

使用 C 或 C++ 流；更喜欢 C++ 流。如果您需要来自 stdio.h 的定义我们<cstdio> .
不要使用 cout和 printf .决定;非此即彼。

编码风格:标识符中的单词区分

使用允许读者分隔标识符中隐藏名称的编码风格。差:

struct bintreenode

更好:

struct bin_tree_node
struct binTreeNode
struct BinTreeNode

编码风格:名称不是单个字母标识符的名称优先于单个字母:
差:

struct bintreenode *l;
struct bintreenode *r;

更好:

struct bintreenode *left_subtree;
struct bintreenode *right_subtree;

使用更具描述性的标识符对您的可执行文件没有影响，对构建过程的影响可以忽略不计。它对阅读您的代码的人(包括您)有很大的积极影响。

使用来自用户的数据

您提示用户输入文件名，但您硬编码了一个:

cout << "Enter the name of the input data file: " << endl;
//asks user to input filename
cin >> fileName; //inputs user input into fileName
return 1;

ifstream file("file.txt");

另外，return 1以上将导致执行在该点停止。不再执行，因此文件永远不会打开。

不要以变量的结构来命名变量。差:

int arr[] = {1, /*...*/, 150};
n = sizeof(arr) / sizeof(arr[0]);

更好:

static const int test_values[] = {1, /* ... */, 150};
static const unsigned int quantity_test_values =
    sizeof(test_values) / sizeof(test_values[0]);

如果struct的内容不会被修改，优先使用const前缀。
如果变量不是全局变量，最好添加 static声明。

用换行符终止你的输出

您的文本可能无法完整打印，因为某些文本可能位于缓冲区中。通常打印换行符 ('\n') 或 std::endl将刷新缓冲区并打印剩余的文本。

使用调试器

在此处发布“为什么它不起作用”的问题之前，请使用调试器并单步执行每个语句。检查变量的正确值。
添加打印语句(又名 cout )以打印出值。