ngaut

asm/c/c++/......

常用链接

统计

积分与排名

others

something special

经典的c/c++

朋友的网上家园

最新评论

数据结构笔记：调整一个链表，使链表左侧的数为奇数，右侧的为偶数，两种算法

/****************************************************************************
**    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;
}

posted on 2005-12-21 13:22 ngaut 阅读(422) 评论(2)  编辑 收藏 引用 所属分类: c/c++/ds

评论

# re: 数据结构笔记：调整一个链表，使链表左侧的数为奇数，右侧的为偶数，两种算法 2005-12-21 17:37 小明

让我想想，如果是stl怎么实现

bool mygreater ( int elem1, int elem2 )
{
return elem1%2 > elem2%2;
}
list<int> t;
t.sort(mygreater);

你的程序有这个弹性么，可以改变算法？  回复  更多评论   

# re: 数据结构笔记：调整一个链表，使链表左侧的数为奇数，右侧的为偶数，两种算法 2005-12-21 18:17 me

呵呵，多谢提醒。当然没有这个弹性，而且我的这个代码是纯c的，不敢和stl比啊，不过使用list的sort算法的时间复杂度是 N log N。  回复  更多评论   


标题  
姓名  
主页
验证码 *
内容(提交失败后,可以通过“恢复上次提交”恢复刚刚提交的内容)  
  登录  使用高级评论  新用户注册  返回页首  恢复上次提交      
[使用Ctrl+Enter键可以直接提交]

相关链接:
网站导航: