2011-05-29 247 views
0

我有一個家庭作業,從我這裏要求創建一個二叉搜索樹的結構,其中二叉搜索樹的節點是另一個二叉搜索樹。第一個BST有學生的姓氏,另一個有姓氏和身份證。另外,如果某人與另一個學生姓氏相同,我不能創建另一個「姓氏」節點,但我必須在現有的「姓氏」節點內創建另一個「名字和ID」節點。更具體地講:二進制搜索樹內的二進制搜索樹

typedef struct nameANDid{ //name and id nodes 
    char first[20]; 
    int ID; 
    struct nameANDid *nleft; 
    struct nameANDid *nright; 
}yohoho; 
typedef struct node{ //surname nodes 
    char last[20]; 
    struct nameANDid yohoho; 
    struct node *left; 
    struct node *right; 
}node; 

我的主要問題是如何創建的每個名字我用下面的代碼,因爲發現了一個不同的nameANDid節點創建2 BST一個姓氏,另一個名字,但我想要像例如: 如果我有這些學生

Stallone Sylvester 11111111 
Stallone Noah  22222222 
Norris Chuck  33333333 
Hogan Hulk  44444444 
Hogan Daniel 55555555 

我想將它們存儲這樣的:.........

Stallone Sylvester 11111111 
      Noah  22222222 
Norris Chuck  33333333 
Hogan Hulk  44444444 
      Daniel 55555555 

相反,這個我的助教柯類似:...........

Stallone Sylvester 11111111. 
      Noah  22222222 
      Chuck  33333333 
      Hulk  44444444 
      Daniel 55555555 

Norris Sylvester 11111111. 
      Noah  22222222 
      Chuck  33333333 
      Hulk  44444444 
      Daniel 55555555 
Hogan Sylvester 11111111. 
      Noah  22222222 
      Chuck  33333333 
      Hulk  44444444 
      Daniel 55555555 

我會把在這裏爲了一些功能更具體

負載函數加載從txt文件的名稱。

void loadData(struct node *temp){  
int i; 
FILE *fp; 
fp=fopen(FILENAME,"r"); 
if (fp == NULL) printf("File does not exist\n"); 
for (i=0; i<5; i++){     
    fscanf(fp,"%s",&temp->last); 
    fscanf(fp,"%s",&temp->yohoho.first); 
    fscanf(fp,"%d",&temp->yohoho.ID);     
    top=add_node(top,temp); //this function create a surname node   
    }   
fclose(fp);  
    printf("\n\nFile loaded\n"); 
} 

其中

 struct node temp;//just a node pointer 
     struct node *top=NULL; //shows the top of the tree 

的addnode的功能是:...

 struct node * add_node (struct node *top, struct node *temp){ 
      struct node *newNode; 
      if (top == NULL){  
      newNode=(struct node *)malloc(sizeof(struct node)); 
      temp->left=NULL; 
      temp->right=NULL;  
      if (memcpy(newNode,temp,sizeof(struct node)) == NULL){ 
       printf("Node addition failed\n"); 
       return NULL;} 
      else {    
       topname=add_node_nameANDid(topname,&temp->yohoho); //Call the add_node_nameANDid to create a new name node in the other tree       
       return newNode;} 
      } 
      else { 
       if (stricmp(temp->last,top->last) < 0){ //Insert node surname left 
        top->left=add_node(top->left,temp);} 
       else if (stricmp(temp->last,top->last) == 0){   
        topname=add_node_nameANDid(topname,&temp->yohoho); //Call the add_node_nameANDid to create a new name node in the other tree if i have the same surname   
       } 
       else { 
        top->right=add_node(top->right,temp);   
       } 
       return top; 
      } 
      return NULL; 
     } 

而且add_node_nameANDid()函數是像以前的功能,但它有一些變量改變:

 struct nameANDid * add_node_nameANDid (struct nameANDid *topname, struct nameANDid *temp2){ 
     struct nameANDid *newNode_nameANDid;  
     if (topname == NULL){ 
      newNode_nameANDid=(struct nameANDid *)malloc(sizeof(struct nameANDid)); 
      temp2->nleft=NULL; 
      temp2->nright=NULL; 
      if (memcpy(newNode_nameANDid,temp2,sizeof(struct nameANDid)) == NULL){ 
        printf("Node addition failed\n"); 
        return NULL;} 
      else {     
        return newNode_nameANDid;} 
      } 
     else { 
      if (stricmp(temp2->first,topname->first) <= 0){  
        topname->nleft=add_node_nameANDid(topname->nleft,temp2);} 
     else {   
        topname->nright=add_node_nameANDid(topname->nright,temp2);} 
     return topname; 
     } 
    return NULL; 
    } 

對不起f或者我剛剛上傳的龐大源代碼,但如果沒有這個,很難解釋。

我認爲我有兩個問題,但我沒有解決這些問題的知識。

第一:我不得不爲每個節點姓創建不同的名字BST,我認爲我不這樣做,但我不知道該怎麼做......

有什麼建議?

+1

衛生署!很好的問題................................ – 2011-05-29 11:23:44

+1

你編譯過這些代碼嗎?它似乎充滿了無法編譯的錯誤。 – Hogan 2011-05-29 11:29:03

+2

您應該更具體一些,找出問題併發布問題源代碼和問題。這是太長了.. – 2011-05-29 11:47:36

回答

2

我已經給出了一個下面的示例實現,評論說明我是如何處理這個的。您應該能夠使用我的想法來修改代碼的工作方式。請注意,它不是一個完美的實現,從我的頭頂開始,我可以看到以下問題。

  1. 及其遞歸,這意味着樹它可以處理的深度由在目標機器上的堆的大小的限制。有兩種方法可以對此進行攻擊:
    1. 使之成爲迭代。也就是說,使用for/while循環而不是調用自己的函數 - 這將允許儘可能多的節點作爲您的機器內存可以處理(修復問題)。
    2. 更新add_name_to_tree來處理插入balanced binary tree(但這只是幫助問題,堆棧限制仍然存在)。
  2. 它不能處理兩個人完全相同的名稱,但不同的ID - 第一人被添加到樹後,同名的所有後續的人都將被忽略。

我會把它作爲練習,讓你來處理這些情況。


#include <stdio.h> 
#include <string.h> 

/* a single struct type for storing all tree elements */ 
typedef struct _node 
{ 
    char name[50]; 
    int id; 
    struct _node *subname; 
    struct _node *left; 
    struct _node *right; 
} node; 

/* creates a new node structure for the specified name and id */ 
node *create_node(const char *name, int id) 
{ 
    node *newNode = (node*)malloc(sizeof(node)); 
    memset(newNode, 0, sizeof(*newNode)); 

    newNode->id = id; 
    strncpy(newNode->name, name, sizeof(newNode->name)); 

    return newNode; 
} 

/* inserts the name/id pair into the tree specified by root. 
    note that root is passed as a pointer to a pointer, so that 
    it can accept NULL if no tree exists yet, and return to the 
    caller the node the node that contains the name. Note that 
    id is ignored if "name" already exists, i'll leave it as an 
    excersice for you to handle situations with the same name 
    with multiple id's */ 
node *add_name_to_tree(node **root, const char *name, int id) 
{ 
    if (*root == NULL) 
    { 
     *root = create_node(name, id); 
     return *root; 
    } 

    const int cmp = strcmp(name, (*root)->name); 

    if (cmp < 0) 
    { 
     return add_name_to_tree(&(*root)->left, name, id); 
    } 
    else if (cmp > 0) 
    { 
     return add_name_to_tree(&(*root)->right, name, id); 
    } 
    else 
    { 
     return *root; 
    } 
} 

/* adds the specified first/last name and id combo to the tree 
    specified by root */ 
node *add_name(node *root, const char *first, const char *last, int id) 
{ 
    /* this call will return the node that holds the last name, 
     we can then use its "subname" tree root to insert the first name */ 
    node *last_node = add_name_to_tree(&root, last, 0); 

    /* use the "subname" of the node that stores the last name as the 
     root of the tree that stores first names */ 
    add_name_to_tree(&last_node->subname, first, id); 
    return root; 
} 

/* just to demonstrate why I use the same node type for first/last names, 
    its because it allows you to support any number of names, see 
    below - an add function that adds people with a middle name to the tree 
    */ 
node *add_with_middle_name(node *root, const char *first, 
          const char *middle, const char *last, int id) 
{ 
    node *last_node = add_name_to_tree(&root, last, 0); 
    node *mid_node = add_name_to_tree(&last_node->subname, middle, 0); 
    add_name_to_tree(&mid_node->subname, first, id); 
    return root; 
} 

/* recursively traverse the name tree, printing out the names */ 
void print_names(node *names, int level) 
{ 
    const int indent = 10; 

    if (names == NULL) 
    { 
     printf("\n"); 
    } 

    if (names->left) 
    { 
     print_names(names->left, level); 
    } 

    if (names->subname) 
    { 
     printf("%*c %s \n", (indent * level), ' ', names->name); 
     print_names(names->subname, level + 1); 
     printf("\n"); 
    } 
    else 
    { 
     printf("%*c %-*s %d\n", 
       (indent * level), ' ', 
       indent, names->name, names->id); 
    } 

    if (names->right) 
    { 
     print_names(names->right, level); 
    } 
} 

int main() 
{ 
    node *names = NULL; 

    names = add_name(names, "Sylvester", "Stallone", 11111111); 
    names = add_name(names, "Noah", "Stallone", 22222222); 
    names = add_name(names, "Chuck", "Norris", 33333333); 
    names = add_name(names, "Hulk", "Hogan", 44444444); 
    names = add_name(names, "Daniel", "Hogan", 55555555); 

    names = add_with_middle_name(names, "Peter", "Michael", 
           "Zachson", 66666666); 

    print_names(names, 0); 

    return 0; 
} 
+0

非常非常感謝你!!!!!!!!你拯救了我的生活! – Spyros 2011-05-30 14:49:44