/****************************************************************************
**    File name:         AdjustByInsert.c
**    Description:    调整一个链表，使链表左侧的数为奇数，右侧的为偶数
**    Author:            Liu Qi, //
**    Version:        0.1
**    commnet:    
****************************************************************************/
#include <stdio.h>
#include <assert.h>
#include <time.h>
#include "../sllist.h"

#define MAX_NUM 10


/*===========================================================================
**    Function name:        AdjustByInsert 
**    Parameter:            L:链表头指针
**    Precondition:        NULL != L && NULL != L->Next
**    Description:        调整一个链表，使链表左侧的数为奇数，右侧的为偶数
算法：遍历链表，若为奇数插入到L后面,时间复杂度O(n^2)
因为SLL_DeleteAt的时间复杂度也为O(n)
**    Return value:        void
**    Author:                Liu Qi, 2005/12/18
===========================================================================*/

void AdjustByInsert(List L)
{
    Position pos = L->Next;
    Position tmpPos;
    
    assert( (NULL != L) && (NULL != L->Next) ); 
    
    while (NULL != pos)
    {
        if ((pos->Element) % 2 != 0)    //为奇数
        {
            SLL_InsertAfter( pos->Element, L);
            tmpPos = pos;
            pos = SLL_NextPos(pos);
            SLL_DeleteAt(tmpPos, L);
        }
        else
        {
            pos = SLL_NextPos(pos);
        }
    }
}


/*===========================================================================
**    Function name:        AdjustBySwap 
**    Parameter:            L:链表头指针
**    Precondition:        (NULL != L) && (NULL != L->Next)
**    Description:        调整一个链表，使链表左侧的数为奇数，右侧的为偶数
算法：通过交换来实现，使用两个指针来遍历链表，其中
一个指向偶数,时间复杂度O(n)

**    Return value:        void
**    Author:                Liu Qi, 2005/12/19
===========================================================================*/
void AdjustBySwap( List L)
{
    Position posEven = L->Next;
    Position pos = posEven->Next;
    ElemType tmp;
    
    assert( (NULL != L) && (NULL != L->Next) ); 
    
    for ( ; NULL != pos; pos = pos->Next)
    {
        if ( ((posEven->Element % 2) == 0) && ((pos->Element % 2) != 0) )
        {
            //swap
            tmp = pos->Element;
            pos->Element = posEven->Element;
            posEven->Element = tmp;
        }
        if ( ((posEven->Element % 2) != 0) )    //奇数，指向下一个
        {
            posEven = SLL_NextPos(posEven);
        }
    }
    
}





/*===========================================================================
**    Function name:        GetRandList
**    Parameter:            void
**    Precondition:        void
**    Description:        构造一个由随机数组成的链表

**    Return value:        链表的头节点指针
**    Author:                Liu Qi, 2005/12/18
===========================================================================*/

List GetRandList(void)
{
    int i;
    
    List L = SLL_Create();
    
    srand( (unsigned)time( NULL ) ); 
    for ( i = 0; i < MAX_NUM; i++)
    {
        SLL_PushFront(rand() % 10, L);
    }
    
    return L;
}



/*===========================================================================
**    Function name:        TestAdjustByInsert 
**    Parameter:            void
**    Precondition:        void
**    Description:        用于测试函数AdjustByInsert

**    Return value:        void
**    Author:                Liu Qi, 2005/12/19
===========================================================================*/
void TestAdjustByInsert( void )
{
    List L = GetRandList();
    SLL_PrintList(L);
    
    printf("\n");
    
    AdjustByInsert(L);
    SLL_PrintList(L);
    
    printf("\n");
    
    SLL_DeleteList(L);
    
}



/*===========================================================================
**    Function name:        TestAdjustBySwap
**    Parameter:            void    
**    Precondition:        void
**    Description:        测试函数AdjustBySwap

**    Return value:        
**    Author:                Liu Qi, 2005/12/19
===========================================================================*/
void TestAdjustBySwap( void )
{
    List L = GetRandList();
    SLL_PrintList(L);
    
    printf("\n");
    
    AdjustBySwap(L);
    SLL_PrintList(L);
    
    printf("\n");
    
    SLL_DeleteList(L);
}


int main(int argc, char *argv[])
{
    printf("TestAdjustByInsert:\n");
    TestAdjustByInsert();
    
    printf("TestAdjustBySwap:\n");
    TestAdjustBySwap();
    
    return 0;
}