#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define xmalloc malloc
#define xfree free
#define xrealloc realloc
#define BUFFSIZE 3
char *getline(FILE *fp)
{
static char inbuff[BUFFSIZE];
char *outbuff_malloc, *tmpbuff;
char *p;
int fEOL;
if ((outbuff_malloc = xmalloc(1)) == NULL)
return NULL;
*outbuff_malloc = '\0';
fEOL = 0;
do {
if (fgets(inbuff, BUFFSIZE, fp) == NULL) {
if (strlen(outbuff_malloc) == 0) {
xfree(outbuff_malloc);
outbuff_malloc = NULL;
}
break;
}
for (p = inbuff; *p != '\0'; p++)
;
if (*(p - 1) == '\n') {
*(p - 1) = '\0';
fEOL = 1;
}
if ((tmpbuff = xrealloc(outbuff_malloc, strlen(outbuff_malloc) + strlen(inbuff) + 1)) == NULL) {
xfree(outbuff_malloc);
return NULL;
}
strcat(tmpbuff, inbuff);
outbuff_malloc = tmpbuff;
} while (!fEOL);
return outbuff_malloc;
}
struct data {
char *name;
char *tel;
struct data *left;
struct data *right;
};
struct list {
struct data *node;
struct list *next;
};
struct data *add_data(struct data *root, char *name, char *tel) {
struct data *node;
if (root == NULL) {
if ((node = xmalloc(sizeof(struct data))) == NULL)
return NULL;
if ((node->name = xmalloc(strlen(name) + 1)) == NULL) {
xfree(node);
return NULL;
}
if ((node->tel = xmalloc(strlen(tel) + 1)) == NULL) {
xfree(name);
xfree(node);
return NULL;
}
strcpy(node->name, name);
strcpy(node->tel, tel);
node->left = node->right = NULL;
return node;
}
if (strcmp(root->name, name) < 0) {
root->left = add_data(root->left, name, tel);
return root;
} else if (strcmp(root->name, name) > 0) {
root->right = add_data(root->right, name, tel);
return root;
} else {
return root;
}
}
void writefile(struct data *root, FILE *fp) {
if (root != NULL) {
fprintf(fp, "%s %s\n", root->name, root->tel);
xfree(root->name);
xfree(root->tel);
writefile(root->left, fp);
writefile(root->right, fp);
xfree(root);
}
}
struct data *add_abb(struct data *root, FILE *fp, int sw) {
char *p;
while ((p = getline(fp)) != NULL) {
char *q;
if (sw > 0) {
printf("add data: %s\n", p);
}
if (strlen(p) > 0) {
for (q = p; !isdigit(*q) && *q != '\0'; q++)
;
*(q - 1) = '\0';
if((root = add_data(root, p, q)) == NULL) {
fprintf(stderr, "memory full, aborted\n");
exit(-1);
}
}
xfree(p);
}
return root;
}
struct data *add_command(struct data *root) {
printf("input(to quit, input Ctrl+D): ");
return add_abb(root, stdin, 1);
}
struct list *add_list(struct list *listroot, struct data *node) {
struct list *newlist;
if (listroot == NULL) {
if ((newlist = xmalloc(sizeof(struct list))) != NULL) {
newlist->node = node;
newlist->next = NULL;
}
return newlist;
} else {
listroot->next = add_list(listroot->next, node);
return listroot;
}
}
void vomit_list(struct list *listroot, int n) {
if (listroot != NULL) {
printf("%d: %s %s\n", n, listroot->node->name, listroot->node->tel);
vomit_list(listroot->next, n + 1);
}
}
void release_list(struct list *listroot) {
struct list *p;
if (listroot != NULL) {
p = listroot->next;
xfree(listroot);
release_list(p);
}
}
struct list *search_data(struct data *node, char *word, struct list *listroot) {
if (node == NULL)
return listroot;
if (strstr(node->name, word) != NULL || strcmp("all", word) == 0)
listroot = add_list(listroot, node);
listroot = search_data(node->left, word, listroot);
listroot = search_data(node->right, word, listroot);
return listroot;
}
struct data *vector_list(struct list *listnode, int n) {
if (listnode == NULL)
return NULL;
if (n <= 1)
return listnode->node;
return vector_list(listnode->next, n - 1);
}
void delete_data2(struct data *root, struct data *right) {
if (root->left == NULL)
root->left = right;
else
delete_data2(root->left, right);
}
struct data *delete_data(struct data *root, struct data *delnode) {
struct data *p;
if (root == NULL)
return NULL;
if (root == delnode) {
if (root->left == NULL) {
p = root->right;
xfree(root->name);
xfree(root->tel);
xfree(root);
return p;
} else if (root->right == NULL) {
p = root->left;
xfree(root->name);
xfree(root->tel);
xfree(root);
return p;
} else {
delete_data2(root->left, root->right);
p = root->left;
xfree(root->name);
xfree(root->tel);
xfree(root);
return p;
}
} else {
root->left = delete_data(root->left, delnode);
root->right = delete_data(root->right, delnode);
return root;
}
}
struct data *delete_command(struct data *root) {
struct data *delnode;
char *p, *q;
int n;
struct list *listroot = NULL;
printf("input: ");
if ((p = getline(stdin)) != NULL) {
if (strlen(p) > 0) {
listroot = search_data(root, p, listroot);
if (listroot != NULL) {
vomit_list(listroot, 1);
printf("which data to delete? :");
if (strlen(q = getline(stdin)) > 0) {
n = atof(q);
xfree(q);
delnode = vector_list(listroot, n);
if (delnode == NULL) {
printf("index is out of range.\n");
} else {
printf("delete: %s %s\n", delnode->name, delnode->tel);
}
root = delete_data(root, delnode);
}
release_list(listroot);
} else {
printf("no data.\n");
}
}
xfree(p);
}
return root;
}
void search_command(struct data *root) {
char *p;
struct list *listroot = NULL;
printf("input: ");
if ((p = getline(stdin)) != NULL) {
if (strlen(p) > 0) {
listroot = search_data(root, p, listroot);
if (listroot != NULL) {
vomit_list(listroot, 1);
release_list(listroot);
} else {
printf("not found.\n");
}
}
xfree(p);
}
}
int main(int argc, char *argv[]) {
struct data *root = NULL;
char c;
FILE *fp;
if (argc != 2) {
fprintf(stderr, "usage: %s <data-file>\n", argv[0]);
exit(-1);
}
if ((fp = fopen(argv[1], "rt")) != NULL) {
root = add_abb(root, fp, 1);
fclose(fp);
}
do {
char *p;
printf("command (\'a\'dd, \'d\'elete, \'s\'earch, \'q\'uit): ");
p = getline(stdin);
c = *p;
switch (c) {
case 'a':
root = add_command(root);
break;
case 'd':
root = delete_command(root);
break;
case 's':
search_command(root);
break;
case 'q':
break;
default:
break;
}
xfree(p);
} while (c != 'q');
if ((fp = fopen(argv[1], "wt")) != NULL) {
writefile(root, fp);
fclose(fp);
}
return 0;
}
/* end */