/***************************************************************************
COPYRIGHT(c) 2010 XXX Co., Ltd.
****************************************************************************
*
* Workfile : DLL_And_BT.c
* Revision : Rev. 0.1
* Date : Fri Mar 26 2010, 18:59:40
* Author : Victor
*
****************************************************************************
*
* File Description
* ----------------
* This file is source file for "Linked List + Bynary Search Tree".
*
****************************************************************************
*
* Revision Details
* ----------------
* Rev. 0.1 Initial revision.
*
***************************************************************************/
#ifndef _LINKEDLIST_BINARYSEARCHTREE_
#define _LINKEDLIST_BINARYSEARCHTREE_
/***************************************************************************
* Include Files
**************************************************************************/
#include
#include
/***************************************************************************
* Macros
**************************************************************************/
// Safe free
#define RELEASEIF( a ) if(a){free(a); a=NULL;}
// Memory allocation
#define MALLOC( x ) x=(Node *)malloc(sizeof(Node));if(x == NULL){printf(" Malloc is failed!!\n");return;}
/***************************************************************************
* Define
**************************************************************************/
#define CLS system ( "cls" )
#define PAUSE system ( "pause" )
#define TRUE 1
#define FALSE 0
// Display method select
#define ALL 0
#define ONE 1
// First Search and Reverse Search
#define FORWARD 1
#define REVERSE 2
// Delete method select : First, Last, Select
#define FIRST 1
#define LAST 2
#define SELECT 3
/***************************************************************************
* Type Definitions
**************************************************************************/
// Linked List
typedef struct _Node
{
int m_nData;
struct _Node *m_pNext;
struct _Node *m_pPrev;
}Node;
// Binary Search Tree
typedef struct _Tree
{
int m_nData;
struct _Tree *m_pLeft;
struct _Tree *m_pRight;
}Tree;
/***************************************************************************
* Function Prototypes
**************************************************************************/
// Linked List
void LinkedList_DisplayNode ( Node *pHead, int nCase );
void LinkedList_AddNode ( Node **ppHead, Node **ppTail, int nData, int nPosition );
void LinkedList_InsertNode ( Node **ppHead, Node ** ppTail, int nData, int nTarget );
void LinkedList_RemoveNode ( Node **ppHead, Node **ppTail, int nData, int nPosition );
void LinkedList_RemoveAllNode ( Node **ppHead );
void LinkedList_SearchNode ( Node *pHead, Node *pTail, int nData, int nSearch );
// Binary Search Tree
void BinaryTree_Inorder ( Tree *pTree );
void BinaryTree_Main ( Tree **ppTree, Node *pList );
int BinaryTree_CreateLeaf ( Tree **ppTree, int nData );
void BinaryTree_Insert ( Tree *pTree, Tree *pNewLeaf );
void BinaryTree_RemoveAll ( Tree **ppTree );
//===========================================================================
// DESCRIPTION
// "Double Linked List + Binary Search Tree" Idle
//
// PARAMETERS
// none
//===========================================================================
int main(void)
{
int nSelect = 0; // Menu Select
int nTemp = 0; // Input Data
int nPosition = 0; // Method Select
int nTarget = 0; // Traget Data
int nSearch = 0; // Search Data
Node *pHead = NULL; // Head node
Node *pTail = NULL; // Tail node
Tree *pTree = NULL; // Binary Tree
for(;;)
{
CLS;
printf ( "\n __________________________________\n" );
printf ( " |________ Linked List TEST _______|\n" );
printf ( " | Select >>>> 1. Add |\n" );
printf ( " | >>>> 2. Insert |\n" );
printf ( " | >>>> 3. Search |\n" );
printf ( " | >>>> 4. Remove |\n" );
printf ( " | >>>> 5. Remove All |\n" );
printf ( " | >>>> 6. Print |\n" );
printf ( " | >>>> 7. Sort |\n" );
printf ( " | >>>> 0. Exit |\n" );
printf ( " |_________________________________|\n" );
printf ( " Enter a select Number : " );
scanf ( "%d", &nSelect );
// Program End
if ( nSelect == 0 )
{
CLS;
printf( "\n ______________________________\n" );
printf( " Exit Linked List TEST \n" );
printf( " ______________________________\n" );
LinkedList_RemoveAllNode( &pHead );
return;
}
// LinkedList Add
else if( nSelect == 1 )
{
CLS;
printf( "\n ______________________________\n" );
printf( " Add Linked List TEST\n" );
printf( " ______________________________\n" );
printf( " Enter a input Data : " );
scanf ( "%d", &nTemp );
printf( " First = 1 | Last = 2 :" );
scanf ( "%d", &nPosition );
LinkedList_AddNode( &pHead, &pTail, nTemp, nPosition );
PAUSE;
}
// LinkedList Insert
else if( nSelect == 2 )
{
CLS;
printf( "\n ______________________________\n" );
printf( " Insert Linked List TEST\n" );
printf( " ______________________________\n" );
printf( " Enter a input Data : " );
scanf ( "%d", &nTemp );
printf( " Enter a taget Node : " );
scanf ( "%d", &nTarget );
LinkedList_InsertNode( &pHead, &pTail, nTemp, nTarget );
PAUSE;
}
// LinkedList Search
else if( nSelect == 3 )
{
CLS;
printf( "\n ______________________________\n" );
printf( " Search Linked List TEST\n" );
printf( " ______________________________\n" );
printf( " Enter a search Data : " );
scanf ( "%d", &nTemp );
printf( " Forward = 1 | Reverse = 2 :" );
scanf ( "%d", &nSearch );
LinkedList_SearchNode( pHead, pTail, nTemp, nSearch );
PAUSE;
}
// LinkedList Remove
else if( nSelect == 4 )
{
CLS;
printf( "\n ______________________________\n" );
printf( " Remove Linked List TEST\n" );
printf( " ______________________________\n" );
printf( " First = 1 | Last = 2 | Select = 3 :" );
scanf ( "%d", &nPosition );
if( nPosition == 1 || nPosition == 2 )
{
LinkedList_RemoveNode( &pHead, &pTail, nTemp, nPosition );
}
else if( nPosition == 3 )
{
printf( " Enter a remove Data : " );
scanf ( "%d", &nTemp );
LinkedList_RemoveNode( &pHead, &pTail, nTemp, nPosition );
}
else
{
printf( " Error Input Number!!\n" );
}
PAUSE;
}
// All node Remove
else if( nSelect == 5 )
{
CLS;
printf( "\n ______________________________\n" );
printf( " Remove All Linked List TEST\n" );
printf( " ______________________________\n" );
LinkedList_RemoveAllNode( &pHead );
printf( " Remove All SUCCESS!!\n" );
PAUSE;
}
// Display LinkedList node
else if( nSelect == 6 )
{
CLS;
printf( "\n ______________________________\n" );
printf( " Display Linked List TEST\n" );
printf( " ______________________________\n" );
LinkedList_DisplayNode( pHead, ALL );
PAUSE;
}
// Binary Tree compose and then Dispaly (Inorder)
else if( nSelect == 7 )
{
CLS;
printf( "\n ______________________________\n" );
printf( " Sort Linked List TEST\n" );
printf( " ______________________________\n" );
// Binary Tree Main
BinaryTree_Main( &pTree, pHead );
// Binary Tree Copy and then Display (Inorder)
BinaryTree_Inorder( pTree );
PAUSE;
// Binary Remove all
BinaryTree_RemoveAll( &pTree );
}
// Error input number
else
{
CLS;
printf( "\n ______________________________\n" );
printf( " Error input Number!!\n" );
printf( " ______________________________\n" );
PAUSE;
}
}
return;
}
//===========================================================================
// DESCRIPTION
// LinkedList_DisplayNode
//
// PARAMETERS
// *pHead : Head Node
// nCase : All and One node - Display method SELECT
//===========================================================================
void LinkedList_DisplayNode( Node *pHead, int nCase )
{
switch( nCase )
{
// All node Display
case 0:
while( pHead != NULL )
{
printf( "\n ______________________________\n" );
printf( " LinkedList Data : %d\n", pHead->m_nData );
printf( " LinkedList Next : 0x%x\n", pHead->m_pNext );
printf( " LinkedList Prev : 0x%x\n", pHead->m_pPrev );
pHead = pHead->m_pNext;
}
printf( " ______________________________\n" );
break;
// One node Display
case 1:
printf( "\n ______________________________\n" );
printf( " LinkedList Data : %d\n", pHead->m_nData );
printf( " LinkedList Next : 0x%x\n", pHead->m_pNext );
printf( " LinkedList Prev : 0x%x\n", pHead->m_pPrev );
printf( " ______________________________\n" );
break;
}
}
//===========================================================================
// DESCRIPTION
// LinkedList_AddNode
//
// PARAMETERS
// **ppHead : Head node
// **ppTail : Tail node
// nData : Input Data
// nPosition : Input Position
//===========================================================================
void LinkedList_AddNode( Node **ppHead, Node **ppTail, int nData, int nPosition )
{
// New node________________________
Node *pTemp = NULL;
MALLOC( pTemp );
pTemp->m_nData = nData;
pTemp->m_pNext = NULL;
pTemp->m_pPrev = NULL;
//_________________________________
// in case : no Node -> New Head
if( *ppHead == NULL )
{
*ppHead = pTemp;
*ppTail = pTemp;
LinkedList_DisplayNode( *ppHead, ONE );
}
// in case : Node existence
else
{
// First Add - New Head
if( nPosition == FIRST )
{
if( *ppHead )
{
(*ppHead)->m_pPrev = pTemp;
pTemp->m_pNext = (*ppHead);
(*ppHead) = pTemp;
}
LinkedList_DisplayNode( *ppHead, ONE );
}
// Last Add - New Tail
else if( nPosition == LAST )
{
if( *ppTail )
{
(*ppTail)->m_pNext = pTemp;
pTemp->m_pPrev = (*ppTail);
(*ppTail) = pTemp;
}
LinkedList_DisplayNode( *ppTail, ONE );
}
// Error Input Number
else
{
printf( " Error Input Number!!\n" );
}
}
}
//===========================================================================
// DESCRIPTION
// LinkedList_InsertNode
//
// PARAMETERS
// **ppHead : Head node
// **ppTail : Tail node
// nData : Input Data
// nTarget : Traget Data
//===========================================================================
void LinkedList_InsertNode (Node **ppHead, Node **ppTail, int nData, int nTarget)
{
Node *pNode = NULL; // Insert Node
Node *pTemp = NULL; // Temporary space
Node *pList = NULL; // Head Node
// New node________________________
MALLOC( pNode );
pNode->m_nData = nData;
pNode->m_pPrev = NULL;
pNode->m_pNext = NULL;
//_________________________________
pList = *ppHead;
// no Head node >> New Head node
if( pList == NULL )
{
*ppHead = pNode;
}
// Head node existence
else
{
// Search Traget node
while( pList )
{
if( pList->m_nData == nTarget )
{
break;
}
pList = pList->m_pNext;
}
// pList next to pNode
if( pList )
{
pTemp = pList->m_pNext;
pList->m_pNext = pNode;
pNode->m_pNext = pTemp;
pNode->m_pPrev = pList;
if( pTemp )
{
pTemp->m_pPrev = pNode;
}
}
// In case : Target node is not existence
else
{
printf( "\n Error Input Node!!" );
printf( "\n It is not existence!!\n" );
return;
}
// In case : pNode == Tail
if( pNode->m_pPrev == *ppTail )
{
*ppTail = pNode;
}
}
LinkedList_DisplayNode( pNode, ONE );
}
//===========================================================================
// DESCRIPTION
// LinkedList_RemoveNode
//
// PARAMETERS
// **ppHead : Head node
// **ppTail : Tail node
// nData : Remove Data
// nPosition : Node position
//===========================================================================
void LinkedList_RemoveNode( Node **ppHead, Node **ppTail, int nData, int nPosition )
{
Node *pTemp = NULL; // Temporary space
// In case : Remove node is Head node
if ( nPosition == FIRST )
{
if( *ppHead == *ppTail )
{
RELEASEIF( *ppHead );
*ppTail = NULL;
}
else
{
if( !*ppTail )
{
return;
}
if( *ppHead == NULL )
{
return;
}
pTemp = (*ppHead)->m_pNext;
pTemp->m_pPrev = NULL;
*ppHead = pTemp;
}
printf( "\n Remove SUCCESS!!\n" );
}
// In case : Remove node is Tail node
else if( nPosition == LAST )
{
if( *ppHead == *ppTail )
{
RELEASEIF( *ppHead );
*ppTail = NULL;
}
else
{
pTemp = *ppHead;
pTemp = (*ppTail)->m_pPrev;
pTemp->m_pNext = NULL;
RELEASEIF( *ppTail );
*ppTail = pTemp;
}
printf( "\n Remove SUCCESS!!\n" );
}
// In case : Remove node is Target node
else if( nPosition == SELECT )
{
Node *pPrev = NULL; // Previous Node
Node *pNext = NULL; // Next Node
pTemp = *ppHead;
//Search Node
while( pTemp != NULL && (pTemp->m_nData != nData) )
{
pTemp = pTemp->m_pNext;
}
if( pTemp != NULL )
{
pPrev = pTemp->m_pPrev;
pNext = pTemp->m_pNext;
if( pPrev )
{
pPrev->m_pNext = pNext;
}
else
{
*ppHead = pNext;
}
if( pNext )
{
pNext->m_pPrev = pPrev;
}
else
{
*ppTail = pPrev;
}
RELEASEIF( pTemp );
printf( "\n Remove SUCCESS!!\n" );
}
}
else
{
printf( " Error Input Number!!\n" );
}
}
//===========================================================================
// DESCRIPTION
// LinkedList_RemoveAllNode
//
// PARAMETERS
// **ppHead : Head node
//===========================================================================
void LinkedList_RemoveAllNode( Node **ppHead )
{
Node *pRemove = NULL; // Delete Node
while( *ppHead != NULL )
{
pRemove = *ppHead;
*ppHead = (*ppHead)->m_pNext;
RELEASEIF( pRemove );
}
(*ppHead) = NULL;
}
//===========================================================================
// DESCRIPTION
// LinkedList_SearchNode
//
// PARAMETERS
// **ppHead : Head node
// **ppTail : Tail node
// nData : Search Data
// nSearch : Search direction
//===========================================================================
void LinkedList_SearchNode( Node *pHead, Node *pTail, int nData, int nSearch )
{
Node *pTemp = NULL; //Print distinction
// In case : Search direction is FORWARD
if( nSearch == FORWARD )
{
pTemp = pHead;
while( pTemp != NULL && (pTemp->m_nData != nData) )
{
pTemp = pTemp->m_pNext;
}
}
// In case : Search direction is REVERSE
else if( nSearch == REVERSE )
{
pTemp = pTail;
while( pTemp != NULL && (pTemp->m_nData != nData) )
{
pTemp = pTemp->m_pPrev;
}
}
// In case : Other number
else
{
printf( " Error Input Number!!\n" );
}
// In case : Find SUCCESS
if( pTemp != NULL )
{
printf( "\n Find SUCCESS!!\n" );
LinkedList_DisplayNode( pTemp, ONE );
}
// In case : Not find SUCCESS
else
{
printf( "\n Not Find!!\n" );
}
}
//===========================================================================
// DESCRIPTION
// BinaryTree_Inorder
//
// PARAMETERS
// *pTree : Tree root node
//===========================================================================
void BinaryTree_Inorder( Tree *pTree )
{
if( pTree )
{
if( pTree->m_pLeft )
{
BinaryTree_Inorder( pTree->m_pLeft );
}
printf( "\n ______________________________\n" );
printf( " LinkedList Data : %d\n", pTree->m_nData );
printf( " ______________________________\n" );
if( pTree->m_pRight )
{
BinaryTree_Inorder( pTree->m_pRight );
}
}
}
//===========================================================================
// DESCRIPTION
// BinaryTree_Main
//
// PARAMETERS
// **ppTree : Tree node
// *pList : Head node
//===========================================================================
void BinaryTree_Main( Tree **ppTree, Node *pList )
{
Tree *pLeaf = NULL; // New node
if( pList == NULL ) return;
while( pList )
{
// Create Node
BinaryTree_CreateLeaf( &pLeaf, pList->m_nData );
// In case : no Root node
if( *ppTree == NULL )
{
*ppTree = pLeaf;
}
// In case : Root node existence
else
{
BinaryTree_Insert( *ppTree, pLeaf );
}
// Move Node to next node
pList = pList->m_pNext;
}
}
//===========================================================================
// DESCRIPTION
// BinaryTree_CreateLeaf
//
// PARAMETERS
// **ppTree : Tree node
// nData : Node data by Double Linked List
//===========================================================================
int BinaryTree_CreateLeaf( Tree **ppLeaf, int nData )
{
*ppLeaf = (Tree *)malloc( sizeof(Tree) );
if( *ppLeaf == NULL )
{
return FALSE;
}
(*ppLeaf)->m_nData = nData;
(*ppLeaf)->m_pRight = NULL;
(*ppLeaf)->m_pLeft = NULL;
return TRUE;
}
//===========================================================================
// DESCRIPTION
// BinaryTree_Insert
//
// PARAMETERS
// **ppTree : Binary Tree
// *pNewLeaf : New node
//===========================================================================
void BinaryTree_Insert( Tree *pTree, Tree *pNewLeaf )
{
// Insert - Left Node
if( pTree->m_nData > pNewLeaf->m_nData )
{
if( pTree->m_pLeft )
{
BinaryTree_Insert( pTree->m_pLeft, pNewLeaf );
}
else
{
pTree->m_pLeft = pNewLeaf;
}
}
// Insert - Right Node or Equal
else if( pTree->m_nData < pNewLeaf->m_nData ||
pTree->m_nData == pNewLeaf->m_nData )
{
if( pTree->m_pRight )
{
BinaryTree_Insert( pTree->m_pRight, pNewLeaf );
}
else
{
pTree->m_pRight = pNewLeaf;
}
}
}
//===========================================================================
// DESCRIPTION
// BinaryTree_RemoveAll
//
// PARAMETERS
// **ppTree : Binary Trees
//===========================================================================
void BinaryTree_RemoveAll( Tree **ppTree )
{
if( (*ppTree) )
{
// Remove - Left node
if( (*ppTree)->m_pLeft )
{
BinaryTree_RemoveAll( &(*ppTree)->m_pLeft );
}
// Remove - Right node
if( (*ppTree)->m_pRight )
{
BinaryTree_RemoveAll( &(*ppTree)->m_pRight );
}
RELEASEIF( (*ppTree) );
}
(*ppTree) = NULL;
}
#endif //_LINKEDLIST_BINARYSEARCHTREE_