C语言 二叉树,一个猜动物的小游戏
1. 此项目用到的知识点: 二叉树, struct, 文件读写。
2. 其中最复杂的地方是:复制一个指针的内容,参考:https://stackoverflow.com/questions/39938648/copy-one-pointer-content-to-another
1. 头文件 "node_utils.h"
#define BOOL int
#define TRUE 1
#define FALSE 0
//This is the NODE type definition.
//The field question_or_animal contains
//either an animal name if the node is a leaf
//or a question used to descend into the tree.
//The left child represents the node to descend
//to if the answer to the question is "yes", the
//right child represents the node to descend to
//if the answer is "no".
typedef struct node {
char question_or_animal[200];
struct node *left;
struct node *right;
} NODE;
//This reads a line from the standard input.
//It returns true if a line was actually read.
//It returns false if end-of-file was encountered
//before any data could be read.
BOOL read_line(char *p);
//Recursively performs a pre-order traversal of the
//tree starting at node p, printing the question_or_animal field to
//the file specified by the file pointer.
void write_tree(NODE *p, FILE *f);
//Reads the file specified by the file pointer and
//creates a tree based on the contents of the file.
//Returns a pointer to the root node of the tree.
NODE *read_tree(FILE *f);
2. 二叉树节点相关的函数 node_utils.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "node_utils.h"
#define BOOL int
#define TRUE 1
#define FALSE 0
BOOL read_line(char *p)
{
char c = getchar();
if (c == EOF)
return FALSE;
while ((c == '\n') || (c == ' ') || (c == '\t')) //ignore leading whitespace
c = getchar();
while (c != '\n') {
*p++ = c;
c = getchar();
}
*p = 0;
return TRUE;
}
void write_tree(NODE *p, FILE *f)
{
if (p == NULL)
fprintf(f,"NULL\n");
else {
fprintf(f,"%s\n", p->question_or_animal);
write_tree(p->left,f);
write_tree(p->right,f);
}
}
NODE *read_tree(FILE *f)
{
char s[200];
int i;
NODE *n;
char c;
//attempt to read the first character of the line
c = getc(f);
//if end-of-file has been reached, then it means
//that the input wasn't structured correctly.
if (c == EOF) {
printf("Error: Wrong number of entries in file\n");
exit(1);
}
i = 0;
for(i=0; (c != EOF) && (c != '\n'); i++) {
s[i] = c;
c = getc(f);
}
s[i] = 0;
if(!strcmp(s,"NULL"))
return NULL;
n = (NODE *) malloc(sizeof(NODE));
strcpy(n->question_or_animal, s);
n->left = read_tree(f);
n->right = read_tree(f);
return n;
}
3. 主函数 animals.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "node_utils.h"
#define BOOL int
#define TRUE 1
#define FALSE 0
NODE *root = NULL;
BOOL yes_response() {
char response[10];
while (TRUE) {
fgets(response, 11, stdin);
response[strcspn(response, "\n")] = 0; // remove leading newline
if (strcasecmp(response, "yes") == 0) {
return TRUE;
} else if (strcasecmp(response, "y") == 0) {
return TRUE;
} else if (strcasecmp(response, "no") == 0) {
return FALSE;
} else if (strcasecmp(response, "n") == 0) {
return FALSE;
} else {
printf("You answered neither yes nor no!\n");
}
}
}
NODE *new_node(char *s) {
NODE *newNode = (NODE *) malloc(sizeof(NODE));
char *s2;
s2 = malloc(sizeof(char) * (strlen(s) + 1));
strcpy(s2, s);
strcpy(newNode->question_or_animal, s2);
newNode->left = NULL;
newNode->right = NULL;
free(s2);
return newNode;
}
void guess_animal() {
if (!root) {
printf("What animal were you thinking of? > ");
char *animal_name;
fgets(animal_name, 200, stdin);
animal_name[strcspn(animal_name, "\n")] = 0; // remove leading newline
root = new_node(animal_name);
} else {
NODE *current_node = new_node(root->question_or_animal);
*current_node = *root;
while (current_node->left && current_node->right) {
printf("%s (yes/no) > ", current_node->question_or_animal);
if (yes_response()) {
current_node = current_node->left;
} else {
current_node = current_node->right;
}
}
printf("I'm guessing: %s\n", current_node->question_or_animal);
printf("Am I right? >");
if (yes_response()) {
printf("I win ! \n");
return;
}
// ask 3 questions
printf("\noops. What animal were you thinking of? > ");
char new_animal_name[200];
fgets(new_animal_name, 200, stdin);
new_animal_name[strcspn(new_animal_name, "\n")] = 0; // remove leading newline
printf("Enter a yes/no question to distinguish a %s and a %s > ", new_animal_name,
current_node->question_or_animal);
char new_question[200];
fgets(new_question, 200, stdin);
new_question[strcspn(new_question, "\n")] = 0; // remove leading newline
printf("What is the answer of a %s (yes or no) > ", new_animal_name);
BOOL yes_no_to_new_question = yes_response();
// create 2 nodes
char *new_animal_name_ptr = new_animal_name;
NODE *newAnimalNode = new_node(new_animal_name_ptr); // yes
NODE *oldAnimalNode = new_node(current_node->question_or_animal);
// set relations
char *question;
question = malloc(sizeof(char) * (strlen(new_question) + 1));
strcpy(question, new_question);
strcpy(current_node->question_or_animal, question);
if (yes_no_to_new_question) {
current_node->left = newAnimalNode;
current_node->right = oldAnimalNode;
} else {
current_node->left = oldAnimalNode;
current_node->right = newAnimalNode;
}
if (root->left && root->right) {
if (yes_no_to_new_question) {
root->left = current_node;
} else {
root->right = current_node;
}
} else {
*root = *current_node;
}
free(question);
}
}
//This code is complete. Just add comments where indicated.
int main() {
int i;
BOOL done = FALSE;
//insert comment here: read a data file "data.dat", assign to a pointer
FILE *datafile = fopen("data.dat", "r");
if (datafile == NULL) {
printf("data.dat not found\n");
exit(1);
}
//insert comment here: read the backup file.
FILE *backupfile = fopen("data.dat.bak", "w");
//insert comment here: find the root of a binary tree
root = read_tree(datafile);
//call write_tree() to write the initial tree to the
//backup file (i.e. to back up the tree data)
write_tree(root, backupfile);
//close both files (for now)
fclose(backupfile);
fclose(datafile);
printf("Welcome to the animal guessing game (like 20 questions).\n");
do {
printf("\nThink of an animal...\n");
guess_animal(); // insert comment here: run the main game
printf("\nDo you want to play again? (yes/no) >");
} while (yes_response()); // keep ask user input if the response always is yes
//now open the "data.dat" file for writing
datafile = fopen("data.dat", "w");
//insert comment:
// call write_tree() to write the full binary tree to a data file (data.dat).
// this will overwrite the original content.
write_tree(root, datafile);
//close the data.dat file
fclose(datafile);
}
编译命令:
# 编译此项目
gcc -o A1 animals.c node_utils.c
原文地址:https://blog.csdn.net/waterHBO/article/details/140436631
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!