#include<stdio.h> #include<stdlib.h> #include "pat.h" static NCS_PATRICIA_NODE *search(NCS_PATRICIA_TREE *pTree,int *key) { NCS_PATRICIA_NODE *pNode; NCS_PATRICIA_NODE *pPrevNode; pNode = (NCS_PATRICIA_NODE *)&pTree->root_node; do { pPrevNode = pNode; if (m_GET_BIT(key, pNode->bit) == 0) { pNode = pNode->left; } else { pNode = pNode->right; } }while (pNode->bit > pPrevNode->bit); return pNode; } int ncs_patricia_tree_init(NCS_PATRICIA_TREE *pTree,const NCS_PATRICIA_PARAMS *const pParams) { if (pParams == NULL) return 0; if ( (pParams->key_size < 1) ||(pParams->key_size > NCS_PATRICIA_MAX_KEY_SIZE) ) { return 0; } pTree->params = *pParams; /* Initialize the root node, which is actually part of the tree structure. */ pTree->root_node.key_info =0; pTree->root_node.bit = -1; pTree->root_node.left =NULL; pTree->root_node.right =NULL; &pTree->root_node; if ((pTree->root_node.key_info= malloc(sizeof(pTree->params.key_size)))== NULL) { return 0; } memset(pTree->root_node.key_info, '\0',pTree->params.key_size); pTree->n_nodes = 0; return 1; } int ncs_patricia_tree_add(NCS_PATRICIA_TREE *pTree, NCS_PATRICIA_NODE *pNode) { NCS_PATRICIA_NODE *pSrch; NCS_PATRICIA_NODE *pTmpNode; NCS_PATRICIA_NODE *pPrevNode; int bit; pTmpNode = search(pTree, pNode->key_info); if (m_KEY_CMP(pTree, pNode->key_info, pTmpNode->key_info) == 0) { return 0; /* duplicate!. */ } bit = 0; while (m_GET_BIT(pNode->key_info, bit) == ((pTmpNode->bit < 0) ? 0 : m_GET_BIT(pTmpNode->key_info, bit))) { bit++; } pSrch = &pTree->root_node; do { pPrevNode = pSrch; if (m_GET_BIT(pNode->key_info, pSrch->bit) == 0) pSrch = pSrch->left; else pSrch = pSrch->right; } while ((pSrch->bit < bit) && (pSrch->bit > pPrevNode->bit)); pNode->bit = bit; if (m_GET_BIT(pNode->key_info, bit) == 0) { pNode->left = pNode; pNode->right = pSrch; } else { pNode->left = pSrch; pNode->right = pNode; } if (m_GET_BIT(pNode->key_info, pPrevNode->bit) == 0) { pPrevNode->left = pNode; } else { pPrevNode->right = pNode; } pTree->n_nodes++; return 1; } int main() { NCS_PATRICIA_TREE * pTree;//*pTree2; NCS_PATRICIA_PARAMS * pParam;//*pParam1; NCS_PATRICIA_NODE * pNode,*pNode1; int key_size; int *key_info; int pTree1,add,c; pTree=(NCS_PATRICIA_TREE *)malloc(sizeof(NCS_PATRICIA_TREE)); pParam=(NCS_PATRICIA_PARAMS *)malloc(sizeof(NCS_PATRICIA_PARAMS)); pNode=(NCS_PATRICIA_NODE *)malloc(sizeof(NCS_PATRICIA_NODE)); while(1) { printf("1.INIT 2.ADD 3.EXIT\n"); printf("Enter the option:\n"); scanf("%d",&c); switch(c) { case 1: printf("Enter the size of the key\n"); scanf("%d",&pParam->key_size); pTree1=ncs_patricia_tree_init(pTree,pParam); if(pTree1==0) { printf("FAILURE\n"); } else { printf("SUCCESS\n"); } break; case 2: //NCS_PATRICIA_TREE *pTree2; //NCS_PATRICIA_NODE *pNode1; //pTree2=(NCS_PATRICIA_TREE *)malloc(sizeof(NCS_PATRICIA_TREE)); //pParam1=(NCS_PATRICIA_PARAMS *)malloc(sizeof(NCS_PATRICIA_PARAMS)); pNode1=(NCS_PATRICIA_NODE *)malloc(sizeof(NCS_PATRICIA_NODE)); printf("Enter the key to be inserted\n"); scanf("%d",&pNode1->key_info); //printf("%d",pNode1->key_info); add=ncs_patricia_tree_add(pTree,pNode1); if(add=0) { printf("Element Not Inserted\n"); } else { printf("Element Inserted\n"); } break; case 3: exit(0); } } return 0; }
#ifndef _PATRICIA_H_ #define _PATRICIA_H_ #include "ncspatricia.h" #define m_KEY_CMP(t, k1, k2) memcmp(k1, k2, (size_t)(t)->params.key_size) #define m_GET_BIT(key, bit) ((bit < 0) ? 0 : ((int)((*((key) + (bit >> 3))) >> (7 - (bit & 0x07))) & 0x01)) #endif
#ifndef _NCSPATRICIA_H_ #define _NCSPATRICIA_H_ #ifdef __cplusplus extern "C" { #endif typedef struct ncs_patricia_params { int key_size; /* 1..NCS_PATRICIA_MAX_KEY_SIZE - in OCTETS */ int info_size; /* NOT USED! Present for backward-compatibility only! */ int actual_key_size; /* NOT USED! Present for backward-compatibility only! */ int node_size; /* NOT USED! Present for backward compatibitity only! */ } NCS_PATRICIA_PARAMS; #define NCS_PATRICIA_MAX_KEY_SIZE 600 /* # octets */ typedef struct ncs_patricia_node { int bit; /* must be signed type (bits start at -1) */ struct ncs_patricia_node *left; struct ncs_patricia_node *right; int *key_info; } NCS_PATRICIA_NODE; #define NCS_PATRICIA_NODE_NULL ((NCS_PATRICIA_NODE *)0) //typedef uns8 NCS_PATRICIA_LEXICAL_STACK; /* ancient history... */ typedef struct ncs_patricia_tree { NCS_PATRICIA_NODE root_node; /* A tree always has a root node. */ NCS_PATRICIA_PARAMS params; int n_nodes; } NCS_PATRICIA_TREE; int ncs_patricia_tree_init(NCS_PATRICIA_TREE *pTree, const NCS_PATRICIA_PARAMS *const pParams); int ncs_patricia_tree_add(NCS_PATRICIA_TREE *pTree, NCS_PATRICIA_NODE *pNode); #ifdef __cplusplus } #endif #endif
#include<stdio.h> #include<stdlib.h> #include "pat.h" static NCS_PATRICIA_NODE *search(NCS_PATRICIA_TREE *const pTree,int* key) { NCS_PATRICIA_NODE *pNode; NCS_PATRICIA_NODE *pPrevNode; pNode = (NCS_PATRICIA_NODE *)&pTree->root_node; do { pPrevNode = pNode; if (m_GET_BIT(key, pNode->bit) == 0) { pNode = pNode->left; } else { pNode = pNode->right; } }while (pNode->bit > pPrevNode->bit); return pNode; } int ncs_patricia_tree_init(NCS_PATRICIA_TREE *const pTree,const NCS_PATRICIA_PARAMS *const pParams) { if (pParams == NULL) return 0; if ( (pParams->key_size < 1) ||(pParams->key_size > NCS_PATRICIA_MAX_KEY_SIZE) ) { return 0; } pTree->params = *pParams; /* Initialize the root node, which is actually part of the tree structure. */ pTree->root_node.key_info =0; pTree->root_node.bit = -1; pTree->root_node.left = pTree->root_node.right = &pTree->root_node; if ((pTree->root_node.key_info= malloc(sizeof(pTree->params.key_size)))== NULL) { return 0; } memset(pTree->root_node.key_info, '\0',pTree->params.key_size); pTree->n_nodes = 0; return 1; } int ncs_patricia_tree_add(NCS_PATRICIA_TREE *const pTree, NCS_PATRICIA_NODE *const pNode) { NCS_PATRICIA_NODE *pSrch; NCS_PATRICIA_NODE *pTmpNode; NCS_PATRICIA_NODE *pPrevNode; int bit; pTmpNode = search(pTree, pNode->key_info); if (m_KEY_CMP(pTree, pNode->key_info, pTmpNode->key_info) == 0) { return 0; //duplicate!. } else { bit = 0; while (m_GET_BIT(pNode->key_info, bit) == ((pTmpNode->bit < 0) ? 0 : m_GET_BIT(pTmpNode->key_info, bit))) { bit++; } pSrch = &pTree->root_node; do { pPrevNode = pSrch; if (m_GET_BIT(pNode->key_info, pSrch->bit) == 0) pSrch = pSrch->left; else pSrch = pSrch->right; } while ((pSrch->bit < bit) && (pSrch->bit > pPrevNode->bit)); pNode->bit = bit; if (m_GET_BIT(pNode->key_info, bit) == 0) { pNode->left = pNode; pNode->right = pSrch; } else { pNode->left = pSrch; pNode->right = pNode; } if (m_GET_BIT(pNode->key_info, pPrevNode->bit) == 0) { pPrevNode->left = pNode; } else { pPrevNode->right = pNode; } pTree->n_nodes++; return 1; } } int ncs_patricia_tree_del(NCS_PATRICIA_TREE *const pTree, NCS_PATRICIA_NODE *const pNode) { NCS_PATRICIA_NODE *pNextNode; NCS_PATRICIA_NODE **pLegDownToNode; NCS_PATRICIA_NODE *pDelNode; NCS_PATRICIA_NODE **pPrevLeg; NCS_PATRICIA_NODE **pNextLeg; int UpWentRight; UpWentRight = 0; pNextNode = &pTree->root_node; pLegDownToNode = &pNextNode->left; while ((pDelNode = *pLegDownToNode) != pNode) { if (pDelNode->bit <= pNextNode->bit) { return 0; /* Key not found. */ } pNextNode = pDelNode; pLegDownToNode = ((m_GET_BIT(pNode->key_info, pNextNode->bit) != 0) ? &pNextNode->right : &pNextNode->left); } pPrevLeg = pLegDownToNode; pNextNode = pNode; while (1) { UpWentRight = (m_GET_BIT(pNode->key_info, pNextNode->bit) != 0); pNextLeg = ((UpWentRight) ? &pNextNode->right : &pNextNode->left); pDelNode = *pNextLeg; if (pDelNode == pNode) break; else if(pDelNode->bit <= pNextNode->bit) { return 0; /* panic??? */ } /* loop around again. */ pNextNode = pDelNode; pPrevLeg = pNextLeg; } pNextNode->bit = pNode->bit; /* it gets the 'bit' value of the evacuee. */ *pLegDownToNode = pNextNode; *pPrevLeg = ((UpWentRight) ? pNextNode->left : pNextNode->right); pNextNode->right = pNode->right; pNextNode->left = pNode->left; pTree->n_nodes--; return 1; } int main() { NCS_PATRICIA_TREE * pTree; NCS_PATRICIA_PARAMS * pParam; NCS_PATRICIA_NODE * pNode,*pNode1; int key_size; int *key_info; int pTree1,add,c,del,b; pTree=(NCS_PATRICIA_TREE *)malloc(sizeof(NCS_PATRICIA_TREE)); pParam=(NCS_PATRICIA_PARAMS *)malloc(sizeof(NCS_PATRICIA_PARAMS)); //pNode=(NCS_PATRICIA_NODE *)malloc(sizeof(NCS_PATRICIA_NODE)); while(1) { printf("1.INIT 2.ADD 3.DELETE 4.COUNT 5.EXIT\n"); printf("Enter the option:\n"); scanf("%d",&c); switch(c) { case 1: printf("Enter the size of the key\n"); scanf("%d",&pParam->key_size); pTree1=ncs_patricia_tree_init(pTree,pParam); if(pTree1==0) { printf("FAILURE\n"); } else { printf("SUCCESS\n"); } break; case 2: pNode1=(NCS_PATRICIA_NODE *)malloc(sizeof(NCS_PATRICIA_NODE)); int a=0; printf("Enter the key to be inserted\n"); scanf("%d",&a); pNode1->key_info = &a; printf("%d",*(pNode1->key_info)); //scanf("%d",&pNode1->key_info); //printf("%d",pNode1->key_info); add=ncs_patricia_tree_add(pTree,pNode1); if(add==0) { printf("Element Not Inserted\n"); } else { printf("Element Inserted\n"); } break; case 3: printf("Enter the key to be deleted\n"); scanf("%d",&b); pNode1->key_info=&b; del=ncs_patricia_tree_del(pTree,pNode1); if(del==0) { printf("Element Not Found\n"); } else { printf("Element Deleted\n"); } break; case 4: printf("The No: of Nodes in Tree is: %d\n",pTree->n_nodes); break; case 5: exit(0); } } return 0; }
when you build your program and it complains: "warning: implicit declaration of function `memset'" ... you have to pay attention to that.
memset() and memcmp() require that you #include <string.h>
theres could be other issues, but start with that and lets see what happens.
.
| DaniWeb Message | |
| Cancel Changes | |