#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;
};
int add_data(struct data **root, char *name, char *tel) {
struct data *node;
if ((*root) == NULL) {
if ((node = xmalloc(sizeof(struct data))) == NULL)
return -1;
if ((node->name = xmalloc(strlen(name) + 1)) == NULL) {
xfree(node);
return -1;
}
if ((node->tel = xmalloc(strlen(tel) + 1)) == NULL) {
xfree(name);
xfree(node);
return -1;
}
strcpy(node->name, name);
strcpy(node->tel, tel);
node->left = node->right = NULL;
*root = node;
return 0;
}
if (strcmp((*root)->name, name) < 0) {
return add_data(&((*root)->left), name, tel);
} else if (strcmp((*root)->name, name) > 0) {
return add_data(&((*root)->right), name, tel);
} else {
return 0;
}
}
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);
*root = NULL; // no need;
}
}
void 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((add_data(root, p, q)) != 0) {
fprintf(stderr, "memory full, aborted\n");
exit(-1);
}
}
xfree(p);
}
}
void add_command(struct data **root) {
printf("input(to quit, input Ctrl+D): ");
add_abb(root, stdin, 1);
}
int 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;
(*listroot) = newlist;
return 0;
} else {
return -1;
}
} else {
return add_list(&((*listroot)->next), node);
}
}
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);
*listroot = NULL;
release_list(&p);
}
}
void search_data(struct data *node, char *word, struct list **listroot) {
if (node == NULL)
return;
if (strstr(node->name, word) != NULL || strcmp("all", word) == 0)
add_list(listroot, node);
search_data(node->left, word, listroot);
search_data(node->right, word, 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->right == NULL)
root->right = right;
else
delete_data2(root->right, right);
}
void delete_data(struct data **root, struct data *delnode) {
struct data *p;
if (root == NULL)
return;
if (*root == NULL)
return;
if ((*root) == delnode) {
if ((*root)->left == NULL) {
p = (*root)->right;
xfree((*root)->name);
xfree((*root)->tel);
xfree(*root);
*root = p;
return;
} else if ((*root)->right == NULL) {
p = (*root)->left;
xfree((*root)->name);
xfree((*root)->tel);
xfree(*root);
*root = p;
return;
} else {
delete_data2((*root)->left, (*root)->right);
p = (*root)->left;
xfree((*root)->name);
xfree((*root)->tel);
xfree(*root);
*root = p;
return;
}
} else {
delete_data(&((*root)->left), delnode);
delete_data(&((*root)->right), delnode);
return;
}
}
void 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) {
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);
}
delete_data(root, delnode);
}
release_list(&listroot);
} else {
printf("no data.\n");
}
}
xfree(p);
}
}
void search_command(struct data *root) {
char *p;
struct list *listroot = NULL;
printf("input: ");
if ((p = getline(stdin)) != NULL) {
if (strlen(p) > 0) {
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) {
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':
add_command(&root);
break;
case 'd':
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 */