forked from sysprog21/phonebook
-
Notifications
You must be signed in to change notification settings - Fork 0
/
phonebook_bst.c
66 lines (53 loc) · 1.46 KB
/
phonebook_bst.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdlib.h>
#include <string.h>
#include "phonebook_bst.h"
/* FILL YOUR OWN IMPLEMENTATION HERE! */
int Length(entry *head)//用來算list總長度
{
int count = 0;
entry *current = head;
while (current != NULL) {
count++;
current = current -> pNext;
}
return count;
}
//因為word.txt檔裡面的文件都是已經排序好的 所以用Sorted Linked List to Balanced BST ,
//而不用去byte-by-byte comparsion
//length第一次進入function時=list總長度
treeNode *BuildBST(entry **headRef, int length)
{
if (length <= 0)
return NULL;
treeNode *left = BuildBST(headRef, length/2);
treeNode *root = (treeNode *) malloc(sizeof(treeNode));
root->entry = *headRef;
root->left = left;
*headRef = (*headRef)->pNext;
root->right = BuildBST(headRef, length - (length / 2) - 1);
return root;
}
entry *findName(char lastName[], treeNode *root)
{
treeNode *current = root;
int result;
while (current != NULL && (result = strcasecmp(lastName, current->entry->lastName)) != 0) {
if (result < 0)
current = current -> left;
else
current = current -> right;
}
if (current)
return (current->entry);
else
return NULL;
}
entry *append(char lastName[], entry *e)
{
e->pNext = (entry *) malloc(sizeof(entry));
// e->detail = NULL;
e = e -> pNext;
strcpy(e->lastName, lastName);
e->pNext = NULL;
return e;
}