基於C/S架構的Trie樹查詢

一 問題     模擬一個成績查詢系統，用戶輸入姓名，返回相應的分數，整個查詢過程放在服務器上運行，采用Trie樹加速查詢。 二 代碼 服務器端：  

#include <stdio.h>  
#include <unistd.h>  
#include <stdlib.h>  
#include <sys/types.h>  
#include <sys/socket.h>  
#include <signal.h>  
#include <netinet/in.h>  
#include <ctype.h>  
  
#define N 8  
typedef const char * keyType;  
typedef unsigned int valType;  
/* 
 * to define a Person structure and initialize 
 * */  
typedef struct Person {  
    keyType name;  
    valType score;  
}Person;  
Person person[N] = {{"LiTao", 89}, {"ZhangQiang", 77},  {"ChengTianXiong", 88}, {"ZhangWei", 90},  
    {"SongTao", 100}, {"LiMin", 88}, {"SongZuDe", 88}, {"ChengFei", 66}};  
/* 
 * to define Trie node structure 
 * */  
enum NodeType {UNCOMPLETED, COMPLETED};  
typedef struct TrieNode {  
    enum NodeType type;  
    char ch;  
    valType val;  
    struct TrieNode *child[26];  
}TrieNode;  
TrieNode *root;  // the root of trie   
/* 
 * to define some functions for Trie  
 * */  
TrieNode * newTrieNode(char ch) {  
    TrieNode *p =(TrieNode *)malloc(sizeof(TrieNode));  
    if(!p) {  
    perror("Memory error!\n");  
    exit(1);  
    }  
    p->type = UNCOMPLETED;  
    p->ch = ch;  
//  memset(p->child, NULL, sizeof(p->child)); // there are some warnings if using memset   
    int i;  
    for(i = 0;i < 26;i++) p->child[i] = NULL;  
  
    return p;  
}  
int index(char ch) {  
    if(isupper(ch)) ch = tolower(ch);  
    return ch - 'a';  
}  
void createTrieroot() {  
    root = newTrieNode('@');  
}  
void insertNode(keyType key, valType val) {  
    TrieNode *ptr = root;  
    int pos;  
    int i;  
    for(i = 0;key[i];i++) {  
    pos = index(key[i]);  
    if(ptr->child[pos] == NULL) {  
        ptr->child[pos] = newTrieNode(key[i]);  
    }  
    ptr = ptr->child[pos];  
    }  
    ptr->type = COMPLETED;  
    ptr->val = val;  
}  
/* 
 * to find the val in terms of key  
 * return -1 if fail to find  
 * */  
int find(keyType key) {  
    TrieNode *ptr = root;  
    int pos;  
    int i;  
    for(i = 0;key[i];i++) {  
    pos = index(key[i]);  
    if(ptr->child[pos] == NULL) break;  
    ptr = ptr->child[pos];  
    }  
    if(!key[i] && ptr->type == COMPLETED) return ptr->val;  
    else return -1;  
}  
void createTrie() {  
    if(root) return;  
    createTrieroot();  
    int i;  
    keyType key;  
    valType val;  
    for(i = 0;i < N;i++) {  
    key = person[i].name;  
    val = person[i].score;  
    if(find(key) == -1) {  
        insertNode(key, val);  
    }  
    }  
}  
int main() {  
    createTrie();  
    /* 
     * to test some cases 
     * */  
//  char name[20];  
//  while(1) {  
//    gets(name);  
//        int val = find(name);  
//        printf("%d\n", val);  
//}  
    /* 
     * the socket fd is same the file descriptor 
     * */  
    int server_sockfd = -1;  
    int client_sockfd = -1;  
    int client_len = 0;  
    /* 
     * to define socket address 
     * */  
    struct sockaddr_in server_addr;  
    struct sockaddr_in client_addr;  
    /* 
     * to create a socket  
     * a socket contains domain, type and protocal 
     * */  
    server_sockfd = socket(AF_INET, SOCK_STREAM, 0);  
//  bzero(&server_addr, sizeof(server_addr));  // to clear the server_addr  
    /* 
     * to initialize the socket address  
     * */  
    server_addr.sin_family = AF_INET;  
    server_addr.sin_addr.s_addr = htonl(INADDR_ANY);  
    /* 
     * pay attention 
     * the port should be same with the port from client  
     * */  
    server_addr.sin_port = htons(9736);  
    /* 
     * to bind the sockect and its address  
     * */  
    bind(server_sockfd, (struct sockaddr *)&server_addr, sizeof(server_addr));  
    /* 
     * to listen the port  
     * */  
    listen(server_sockfd, 5);  
    /* 
     * to ignore child processes which stop  
     * */  
   signal(SIGCHLD, SIG_IGN);  
      
    while(1) {  
    keyType key;  
        valType val = -1;  
  
    client_len = sizeof(client_addr);  
    printf("server is waiting...\n");  
    /* 
     * to accept a connect from a client socket  
     * */  
    client_sockfd = accept(server_sockfd, (struct sockaddr *)&client_addr, &client_len);  
        /* 
     * let the child process to deal with  
     * */  
    if(fork() == 0) {  
        /* 
         * read data from socket  
         * */  
        char name[20];  
        read(client_sockfd, &name, sizeof(name));  
        int  score = find(name);     // to search in the trie   
        /* 
         * write the data to socket  
         * */  
        write(client_sockfd, &score, sizeof(score));  
        close(client_sockfd);  
        exit(0);  
    }  
    else {  
        close(client_sockfd);  
    }  
    }  
    close(server_sockfd);  
    return 0;  
}  

#include <stdio.h>  
#include <unistd.h>  
#include <stdlib.h>  
#include <sys/types.h>  
#include <sys/socket.h>  
#include <signal.h>  
#include <netinet/in.h>  
#include <arpa/inet.h>  
  
int main() {  
    /* 
     * the socket fd is same the file descriptor 
     * */  
    int sockfd = -1;  
    int len = 0;  
    /* 
     * to define socket address 
     * */  
    struct sockaddr_in address;  
    int result;  
  
    char name[20];  
    unsigned int score;  
  
    int i;  
    for(i = 0;i < 10;i++) {  
    /* 
     * to create a socket  
     * a socket contains domain, type and protocal 
     * */  
    sockfd = socket(AF_INET, SOCK_STREAM, 0);  
    /* 
     * to initialize the socket address  
     * */  
    address.sin_family = AF_INET;  
    address.sin_addr.s_addr = inet_addr("127.0.0.1");  
    address.sin_port = htons(9736);  
    len = sizeof(address);  
    /* 
     * to connect the server  
     * */  
    result = connect(sockfd, (struct sockaddr *)&address, len);  
    if(result == -1) {  
    perror("ops:client!\n");  
    exit(1);  
    }  
  
    printf("input a name:");  
    gets(name);  
    write(sockfd, &name, sizeof(name));  
    read(sockfd, &score, sizeof(score));  
    printf("score from server = %d\n", score);  
  
    close(sockfd);  
    }  
    exit(0);  
  
    return 0;  
}