《C primer plus》第十七章编程练习倒数第二题：
本程序想要实现的功能是：
让用户输入一个文件名，程序识别文件里的所有单词，并让用户选择想要进行的操作：
1、列出所有单词和它出现的次数。
2、用户输入一个单词，程序打印它出现的次数，如果没有就打印：
No that word!
3、退出。
但是：每次到addItem()时，总是会无法malloc()
main.c
#include <stdio.h>
#include <string.h>
#include "tree.h"
void printItem(Item item)
{
printf("%-20s: %d", item.name, item.number);
}
char show()
{
char choice;
printf("Pleas choice what you want to do:\nl)ist all the words c)hoose a word\nq)uit this program\n:");
scanf("%c", &choice);
return choice;
}
void find(Tree * tree)
{
char word[20];
Item item;
Item * point;
printf("Please enter a word:");
scanf("%s", word);
if(isTreeEmpty(tree))
{
printf("No words!\n");
return;
}
strcpy(item.name, word);
if(!findItem(&item, tree))
{
printf("No that word!\n");
return;
}
while(getchar() != '\n')
continue;
point = whereIsItem(&item, tree);
printf("There is %d of that.\n", point->number);
}
void list(Tree * tree)
{
everyone(tree, printItem);
}
int main()
{
Tree words;
FILE * file;
char filename[40];
char word[20];
char choice;
Item temp;
makeTree(&words);
printf("Enter a file name:");
scanf("%s", filename);
file = fopen(filename, "r");
if(file == NULL)
{
printf("Can't open file.\n");
return 1;
}
makeTree(&words);
while(getchar() != '\n')
continue;
while(fscanf(file, "%s", word) == 1)
{
strcpy(temp.name, word);
addItem(&temp, &words);
}
choice = show();
for(int i = 0; i > -1; i++)
{
switch(choice)
{
case 'l':
list(&words);
break;
case 'c':
find(&words);
break;
case 'q':
break;
default:
printf("Pleas enter l, c or q.\n");
}
}
emptyTree(&words);
fclose(file);
printf("Bye-bye~~~\n");
return 0;
}
implement_tree.c
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
typedef struct pair
{
Node * parent;
Node * child;
} Pair;
static bool ToLeft(const Item *, const Item *);
static bool ToRight(const Item *, const Item *);
static void inOrder(const Node * node, void (*func)(Item item))
{
if(node != NULL)
{
inOrder(node->left, func);
(*func)(node->item);
inOrder(node->right, func);
}
}
static void deletAllNodes(Node * root)
{
Node * right;
if(root != NULL)
{
right = root->right;
deletAllNodes(root->left);
free(root);
deletAllNodes(right);
}
}
static void addNode(Node * new_node, Node * root)
{
if(ToLeft(&new_node->item, &root->item))
{
if(root->left == NULL)
{
root->left = new_node;
}
else
{
addNode(new_node, root->left);
}
}
else if(ToRight(&new_node->item, &root->item))
{
if(root->right == NULL)
{
root->right = new_node;
}
else{
addNode(new_node, root->right);
}
}
else
{
fprintf(stderr, "ERROR!!!!!!");
exit(1);
}
}
static bool ToLeft(const Item * item1, const Item * item2)
{
int comp1;
if((comp1 = strcmp(item1->name, item2->name)) < 0)
{
return true;
}
else if(comp1 == 0 && item1->number < item2->number)
{
return true;
}
else
{
return false;
}
}
static bool ToRight(const Item * item1, const Item * item2)
{
int comp1;
if((comp1 = strcmp(item1->name, item2->name)) > 0)
{
return true;
}
else if(comp1 == 0 && item1->number > item2->number)
{
return true;
}
else
{
return false;
}
}
static Node * makeNode(const Item * item)
{
Node * node;
node = (Node *)malloc(sizeof(Node));
if(node != NULL)
{
node->item = *item;
node->left = NULL;
node->right = NULL;
}
return node;
}
static Pair seekItem(const Item * item, const Tree * tree)
{
Pair look;
look.parent = NULL;
look.child = tree->root;
if(look.child == NULL)
{
return look;
}
while(look.child != NULL)
{
if(ToLeft(item, &(look.child->item)))
{
look.parent = look.child;
look.child = look.child->right;
}else if(ToRight(item, &(look.child->item)))
{
look.parent = look.child;
look.child = look.child->right;
}else
{
break;
}
}
return look;
}
static void deletNode(Node ** node)
{
Node * temp;
if((*node)->left == NULL)
{
temp = *node;
*node = (*node)->right;
free(temp);
}
else if((*node) ->right == NULL)
{
temp = *node;
*node = (*node)->left;
free(temp);
}
else
{
for(temp = (*node)->left; temp->right != NULL; temp = temp->right)
continue;
temp->right = (*node)->right;
temp = *node;
*node = (*node)->left;
free(temp);
}
}
/*----主要接口----*/
void makeTree(Tree * tree)
{
tree->root = NULL;
tree->size = 0;
}
bool isTreeEmpty(const Tree * tree)
{
if(tree->root == NULL)
return true;
else
return false;
}
bool isTreeFull(const Tree * tree)
{
if(tree->size == MAXITEM)
return true;
else
return false;
}
int howMany(const Tree * tree)
{
return tree->size;
}
bool addItem(const Item * item, Tree * tree)
{
Node * new_node;
if(isTreeFull(tree))
{
fprintf(stderr, "Tree is full");
return false;
}
if(seekItem(item, tree).child != NULL)
{
seekItem(item, tree).child->item.number++;
return false;
}
new_node = makeNode(item);
if(new_node == NULL)
{
fprintf(stderr, "ERROR!!!!!!!!!");
return false;
}
tree->size++;
if(tree->root == NULL)
tree->root = new_node;
else
addNode(new_node, tree->root);
return true;
}
bool findItem(const Item * item, const Tree * tree)
{
return (seekItem(item, tree).child == NULL) ? true : false;
}
Item * whereIsItem(const Item * item, const Tree * tree)
{
Node * node;
node = seekItem(item, tree).child;
if(node != NULL)
return &(node->item);
else
return NULL;
}
bool deletItem(const Item * item, Tree * tree)
{
Pair look;
look = seekItem(item, tree);
if(look.child == NULL)
{
return false;
}
if(look.parent == NULL)
{
deletNode(&tree->root);
}
else if(look.parent->left == look.child)
{
deletNode(&look.parent->left);
}
else
{
deletNode(&look.parent->right);
}
tree->size--;
return true;
}
void everyone(const Tree * tree, void (*pfun)(Item item))
{
if(tree != NULL)
{
inOrder(tree->root,pfun);
}
}
void emptyTree(Tree * tree)
{
if(tree != NULL)
{
deletAllNodes(tree->root);
}
tree->root = NULL;
tree->size = 0;
}
tree.h
#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>
#define SLEN 20
#define MAXITEM 10
typedef struct item
{
char name[SLEN];
int number;
} Item;
typedef struct node
{
Item item;
struct node * left;
struct node * right;
} Node;
typedef struct tree
{
Node * root;
int size;
} Tree;
void makeTree(Tree * tree);
bool isTreeEmpty(const Tree * tree);
bool isTreeFull(const Tree * tree);
int howMany(const Tree * tree);
bool addItem(const Item * item, Tree * tree);
bool findItem(const Item * item, const Tree * tree);
Item * whereIsItem(const Item * item, const Tree * tree);
bool deletItem(const Item * item, Tree * tree);
void everyone(const Tree * tree, void (*pfun)(Item item));
void emptyTree(Tree * tree);
#endif
