|
常用链接
留言簿(26)
随笔分类(128)
随笔档案(169)
文章分类
文章档案(3)
others
something special
经典的c/c++
搜索
积分与排名
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
Powered by: 博客园
模板提供:沪江博客
|
|
|
|
|
发新文章 |
|
|
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//****************************************************************************
** File name: AdjustByInsert.c
** Description: 调整一个链表,使链表左侧的数为奇数,右侧的为偶数
** Author: Liu Qi, //
** Version: 0.1
** commnet:
****************************************************************************/
#include <stdio.h>
#include <assert.h>
#include <time.h>
#include "../sllist.h"
![](/Images/OutliningIndicators/None.gif)
#define MAX_NUM 10
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*===========================================================================
** 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
===========================================================================*/
![](/Images/OutliningIndicators/None.gif)
void AdjustByInsert(List L)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
Position pos = L->Next;
Position tmpPos;
assert( (NULL != L) && (NULL != L->Next) );
while (NULL != pos)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ((pos->Element) % 2 != 0) //为奇数
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
SLL_InsertAfter( pos->Element, L);
tmpPos = pos;
pos = SLL_NextPos(pos);
SLL_DeleteAt(tmpPos, L);
}
else
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
pos = SLL_NextPos(pos);
}
}
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*===========================================================================
** Function name: AdjustBySwap
** Parameter: L:链表头指针
** Precondition: (NULL != L) && (NULL != L->Next)
** Description: 调整一个链表,使链表左侧的数为奇数,右侧的为偶数
算法:通过交换来实现,使用两个指针来遍历链表,其中
一个指向偶数,时间复杂度O(n)
![](/Images/OutliningIndicators/InBlock.gif)
** Return value: void
** Author: Liu Qi, 2005/12/19
===========================================================================*/
void AdjustBySwap( List L)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
Position posEven = L->Next;
Position pos = posEven->Next;
ElemType tmp;
assert( (NULL != L) && (NULL != L->Next) );
for ( ; NULL != pos; pos = pos->Next)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( ((posEven->Element % 2) == 0) && ((pos->Element % 2) != 0) )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
//swap
tmp = pos->Element;
pos->Element = posEven->Element;
posEven->Element = tmp;
}
if ( ((posEven->Element % 2) != 0) ) //奇数,指向下一个
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
posEven = SLL_NextPos(posEven);
}
}
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*===========================================================================
** Function name: GetRandList
** Parameter: void
** Precondition: void
** Description: 构造一个由随机数组成的链表
![](/Images/OutliningIndicators/InBlock.gif)
** Return value: 链表的头节点指针
** Author: Liu Qi, 2005/12/18
===========================================================================*/
![](/Images/OutliningIndicators/None.gif)
List GetRandList(void)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
int i;
List L = SLL_Create();
srand( (unsigned)time( NULL ) );
for ( i = 0; i < MAX_NUM; i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
SLL_PushFront(rand() % 10, L);
}
return L;
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*===========================================================================
** Function name: TestAdjustByInsert
** Parameter: void
** Precondition: void
** Description: 用于测试函数AdjustByInsert
![](/Images/OutliningIndicators/InBlock.gif)
** Return value: void
** Author: Liu Qi, 2005/12/19
===========================================================================*/
void TestAdjustByInsert( void )
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
List L = GetRandList();
SLL_PrintList(L);
printf("\n");
AdjustByInsert(L);
SLL_PrintList(L);
printf("\n");
SLL_DeleteList(L);
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*===========================================================================
** Function name: TestAdjustBySwap
** Parameter: void
** Precondition: void
** Description: 测试函数AdjustBySwap
![](/Images/OutliningIndicators/InBlock.gif)
** Return value:
** Author: Liu Qi, 2005/12/19
===========================================================================*/
void TestAdjustBySwap( void )
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
List L = GetRandList();
SLL_PrintList(L);
printf("\n");
AdjustBySwap(L);
SLL_PrintList(L);
printf("\n");
SLL_DeleteList(L);
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
int main(int argc, char *argv[])
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
printf("TestAdjustByInsert:\n");
TestAdjustByInsert();
printf("TestAdjustBySwap:\n");
TestAdjustBySwap();
return 0;
}
![](/Images/OutliningIndicators/None.gif)
|
|