I suppose they would, but they are somewhat overcomplicated.
And also, you have to rewrite your new() function (and also, rename it ;)), it's messed in the malloc(sizeof(node**)) part.
I'm against typedefing List as node**, rather as node*(LPNODE), as you don't have to (and don't want to) pass node** everywhre to use your nodes.
Where you should be passing node**, do it explicite, by LPNODE*. That happens, in functions, that may get the main node of your list, and change it. Like when you have empty list, and after insert, one-node list. In your new() function, you are proposing using, so called, guard. This is what I call overcomplicating stuff. A simple NULL pointer is enough.
What your guard does really? It allows you to pass empty list to insert function without seg-fault. How? By passing a <location>, where the real "NULL-something" is, that is, where you check for NullItem, and overwrite it, if necessary.
Instead, you can pass a location to a real NULL pointer, and overwite it, if necessary.
Check my previous code posted (with insert(node** ppNode, Item i)).
Cheers.
/def
pointer doubt...
bah, you're right deffer I wasnt paying attention >_< i had just got back from Uni had a 2 hour test and my brain hurts!
You if want to manipulate a pointer in one scope from another scoep then you
should use a pointer-pointer...
Cheers,
-Danu
Ps. appologies for my idiocy, I hope that didn't throw you off too much -_-'
You if want to manipulate a pointer in one scope from another scoep then you
should use a pointer-pointer...
Cheers,
-Danu
Ps. appologies for my idiocy, I hope that didn't throw you off too much -_-'
IMHO, I think your design apporach is all wrong FreJa a few things:
you are treating a linked list like it is a tree, and even in doing so you
haven't updated the name... so this is isn't healping solve your issue
I'm really tired atm, and Im usually not good at explinations anyway..
but i can show you how i would implement a Binary Tree in C
scroll down to the bottom to see the main() function and the test case.
I have only implemented "insert", remove should be trivial as i have
provided functions that traverse the nodes and shown you how to completly
avoid the pointer-pointer issues!
Compile Command: GCC v3.3.1 i386 Win32
gcc -W -Wall bintree.c -o bintree
Good Identifier Naming Goes A Long Way In Making Good Code.
you are treating a linked list like it is a tree, and even in doing so you
haven't updated the name... so this is isn't healping solve your issue
I'm really tired atm, and Im usually not good at explinations anyway..
but i can show you how i would implement a Binary Tree in C
scroll down to the bottom to see the main() function and the test case.
I have only implemented "insert", remove should be trivial as i have
provided functions that traverse the nodes and shown you how to completly
avoid the pointer-pointer issues!
#include <stdio.h>#include <stdlib.h>#include <math.h>#include <string.h>//----------------------------------------------------------------------------------------------// declarationstypedef int ItemType;// the node of our tree, notice the nice clean naming !!typedef struct BinaryTreeNode { union { // allow us to access the same pointers but with some optional flexibility struct { struct BinaryTreeNode *left, *right; }; struct { struct BinaryTreeNode *less_than_this, *more_than_this; }; }; ItemType data; int dataInstances; // for when we have two datum the same in the same tree} BinaryTreeNode;// tree data structure, avoid nasty pointer-pointer issues// using ecapsulation where ever possibletypedef struct BinaryTree{ BinaryTreeNode *root; int numElements;} BinaryTree;// help us out heretypedef BinaryTree *LPBINARYTREE;typedef BinaryTreeNode *LPBINARYTREENODE;//----------------------------------------------------------------------------------------------// function declarationsLPBINARYTREENODE bintree_create_node ( LPBINARYTREE tree, ItemType data );LPBINARYTREENODE bintree_insert ( LPBINARYTREE tree, ItemType data );LPBINARYTREE bintree_create ( );void bintree_print_node ( LPBINARYTREENODE node, int level, const int numLayers, int pos );void bintree_print ( LPBINARYTREE tree );//----------------------------------------------------------------------------------------------// creats a single node, returns addressLPBINARYTREENODE bintree_create_node( LPBINARYTREE tree, ItemType data ){ LPBINARYTREENODE ret = (LPBINARYTREENODE) malloc( sizeof(BinaryTreeNode ) ); ret->dataInstances++; ret->data = data; ret->left = ret->right = NULL; tree->numElements++; return ret;}//----------------------------------------------------------------------------------------------// creates a tree, returns addressLPBINARYTREE bintree_create(){ // allocate tree and root node LPBINARYTREE ret = (LPBINARYTREE) malloc( sizeof( BinaryTree ) ); ret->root = NULL; return ret;}//----------------------------------------------------------------------------------------------// recursively print out a node and its non-null subnodes// pos = 0 its a center node, -1 its a left node, 1 its a right nodevoid bintree_print_node( LPBINARYTREENODE node, int level, const int numLayers, int pos ){ int i = 0; char desc[4] = "C\000"; if( node == NULL ) return; if( pos == -1 ) strncpy( desc, "L\000", 4 ); if( pos == +1 ) strncpy( desc, "R\000", 4 ); for( i=0; i<level; i++ ) printf(" "); printf( "%s%i: %i\n", desc, level, node->data ); ++level; bintree_print_node( node->left, level, numLayers, -1 ); bintree_print_node( node->right, level, numLayers, +1 );}//----------------------------------------------------------------------------------------------// print out a treevoid bintree_print( LPBINARYTREE tree ){ int numLayers = 0; if( tree == NULL ) return; numLayers = (int)log( (double)tree->numElements ); bintree_print_node( tree->root, 0, numLayers, 0 );}//----------------------------------------------------------------------------------------------// returns a pointer to the newly inserted nodeLPBINARYTREENODE bintree_insert( LPBINARYTREE tree, ItemType data ){ LPBINARYTREENODE cur = tree->root; int done = 0; if( cur == NULL ) // no root node { tree->root = bintree_create_node( tree, data ); tree->numElements++; return tree->root; } // if done == -1 insertion occured on a left node // if done == +1 insertion occured on a right node while( done == 0 ) { // saftey check if( cur == NULL ) break; // if its less than either follow the left node // or add it to the null left node if( data < cur->data ) { if( cur->less_than_this != NULL ) cur = cur->less_than_this; else { cur->less_than_this = bintree_create_node( tree, data ); done--; } } else // if its greater than, do the opposite if( data > cur->data ) { if( cur->more_than_this != NULL ) cur = cur->more_than_this; else { cur->more_than_this = bintree_create_node( tree, data ); done++; } } else { // it must be equal, since its already in the tree // just increment the data-instance counter cur->dataInstances++; done = -2; } } tree->numElements++; return cur;}// our test functionint main(){ /* example binary tree: 6 .-----------+-----------. 3 10 .-------+-------. .-------+------- 2 5 7 --+-- --+---. 9 application output: C0: 6 L1: 3 L2: 2 R2: 5 R1: 10 L2: 7 R3: 9 */ LPBINARYTREE myTree = bintree_create(); bintree_insert( myTree, 6 ); bintree_insert( myTree, 10 ); bintree_insert( myTree, 3 ); bintree_insert( myTree, 2 ); bintree_insert( myTree, 7 ); bintree_insert( myTree, 9 ); bintree_insert( myTree, 5 ); bintree_print( myTree ); return 0;}Compile Command: GCC v3.3.1 i386 Win32
gcc -W -Wall bintree.c -o bintree
Good Identifier Naming Goes A Long Way In Making Good Code.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
