循环双向链表排序有关问题-

循环双向链表排序问题--------------在线等
以下是我写的，不知道哪写错了，总是排不对
PGAMESTUFF   insert       这个是准备插入到链表中的值

PSTUFFSTYLE   StyleList这个是存链表的结构体

StyleList-> m_pStuffhead   这个是链表的头

int   Sort_StuffWithCharacter(PGAMESTUFF   insert,PSTUFFSTYLE   StyleList)
{
PGAMESTUFF   pre,   p,head;
pre   =   NULL;
p   =   StyleList-> m_pStuffhead;
head   =   p-> m_pPrve;
while(p!=   head   &&   p-> m_sSaleMoney   <   insert-> m_sSaleMoney)
{
pre   =   p;
p   =   p-> m_pNext;
}
if(pre==NULL)
{
insert-> m_pNext   =   p-> m_pNext;
p-> m_pNext-> m_pPrve   =   insert;
p-> m_pNext   =   insert;
insert-> m_pPrve   =   p;  
}
else
{
pre-> m_pNext   =   insert;
insert-> m_pPrve   =   pre;
insert-> m_pNext   =   p;
p-> m_pPrve   =   insert;  
}
if   (insert-> m_sSaleMoney   >   StyleList-> m_pStuffhead-> m_sSaleMoney)
{
StyleList-> m_pStuffhead   =   insert;
}
return   1;
}

[解决办法]
bool Sort_StuffWithCharacter(PGAMESTUFF insert,PSTUFFSTYLE StyleList)
{
PGAMESTUFF pre, p,head;

if ( StyleList == NULL )
{
return false;
}

if ( StyleList-> m_pStuffhead == NULL )
{
//这里要处理；你出始化时要设定为空的
StyleList-> m_pStuffhead = insert;
insert-> m_pNext = insert;
insert-> m_pPrve = insert;
return true;
}
else
{
p = StyleList-> m_pStuffhead;
head = p-> m_pPrve;
}

while( p!= head && p-> m_sSaleMoney < insert-> m_sSaleMoney)
{
pre = p;
p = p-> m_pNext;
}

insert-> m_pNext = pre-> m_pNext;
pre-> m_pNext-> m_pPrve = insert;
pre-> m_pNext = insert;
insert-> m_pPrve = pre;
if (insert-> m_sSaleMoney > StyleList-> m_pStuffhead-> m_sSaleMoney)
{
StyleList-> m_pStuffhead = insert;
}
return true;
}
基本这样
[解决办法]
偶自己用的, 给链表排序的时候太少, 没咋做过优化, 勉强够用了 ....

// test.cpp
#include <x4c/x4c.h>
#include <time.h>

typedef struct _test_node_st _test_node , _test_list , *_p_test_node ;

struct _test_node_st
{
_p_test_node xd_next , xd_prev;
int value ;
};

void _list_sort( _p_test_node lo , _p_test_node hi );

#define X_NODE_TYPE_p_test_node
#define X_ALGO_LT(lhs,rhs)((lhs)-> value < (rhs)-> value)
#if 0
#define X_NODE_SWAP( lhs , rhs )do { \
int tttt = rhs-> value ; rhs-> value = lhs-> value; lhs-> value = tttt;\
} while(0)
#endif
#define X_ALGO_FUNC_NAME_list_sort
#include <x4c/algo/x_list_sort.inl>

int main()
{
int i , j , ppp;
_test_listl , *p;
int s = time ( NULL );
printf( "seed %d\n " , s );

srand( s );
for( j = 0; j < 10; ++j ) {
XDS_list_init( &l );
for( i = 0;i < 100000; ++i )
{
_p_test_node x = new _test_node;
x-> value = (rand() < < 8)^rand() ;
XDS_list_push_back( &l , x );

}
printf ( ".....................\n " );
_list_sort( l.xd_next , l.xd_prev );
ppp=l.xd_next-> value;
XDS_list_for_each( &l , p ){
if( p-> value < ppp ) { printf ( "******ERROR******\n " ); getchar(); }
//printf( "%d--> " , ppp=p-> value );
}
XDS_list_cleanup( &l , delete );
}
return 0;
}

/************************************************************************/
/* x_list.h
*/

#ifndef __XINCL_X_LIST_H_INCLUDE__
#define __XINCL_X_LIST_H_INCLUDE__

/************************************************************************/
/* XDS_slist */
/************************************************************************/

typedef struct XDS_slist_node_st XDS_slist_node ;
typedef struct XDS_slist_node_st XDS_slist_head ;
typedef struct XDS_slist_node_st *XDS_p_slist_node;
struct XDS_slist_node_st
{
struct XDS_slist_node_st *xd_next;
};

#define XDS_slist_init( __h__ )((__h__)-> xd_next = (__h__))

#define XDS_slist_erase_after( __n__ , __f__ )\
do {\
void*__p_next_node__ = (void*)(__n__)-> xd_next;\
(__n__)-> xd_next = (__n__)-> xd_next-> xd_next;\
__f__ ( __p_next_node__ ) ;\
} while(0)

#define XDS_slist_pop_front( __h__ , __f__ )XDS_slist_erase_after( __h__ , __f__ )
#define XDS_slist_insert_after( __n__ , __p__ )\
do {\
(__p__)-> xd_next = (__n__)-> xd_next;\
(__n__)-> xd_next = (__p__);\
} while(0)

#define XDS_slist_push_front( __h__ , __p__ )XDS_slist_insert_after( __h__ , __p__ )
#define XDS_slist_cleanup( __h__ , __f__ )\
do {\
void*__p_first_node__ ;\
while( 1 )\
{\
XDS_slist_pop_front( __h__ , __p_first_node__ = );\
if( (__h__) == __p_first_node__ )break;\
__f__ ( __p_first_node__ );\
}\
} while(0)

#define XDS_slist_for_each( __h__ , __n__ )\
for( (__n__) = (__h__)-> xd_next; (__h__) != (__n__); (__n__) = (__n__)-> xd_next )

/************************************************************************/
/* XDS_list */
/************************************************************************/

typedef struct XDS_list_node_st XDS_list_node ;
typedef struct XDS_list_node_st XDS_list_head ;
typedef struct XDS_list_node_st *XDS_p_list_node;
struct XDS_list_node_st
{
struct XDS_list_node_st *xd_next;
struct XDS_list_node_st *xd_prev;
};


#define XDS_list_init( __h__ )((__h__)-> xd_prev=(__h__)-> xd_next=(__h__))

#define XDS_list_insert_before( __n__ , __p__ )\
do {\
(__p__)-> xd_next = (__n__);(__p__)-> xd_prev = (__n__)-> xd_prev;\
(__n__)-> xd_prev-> xd_next = (__p__);(__n__)-> xd_prev = (__p__);\
} while(0)

#define XDS_list_insert_before2( __n__ , __lh__ , __lt__ )\
do {\
(__lt__)-> xd_next = (__n__);(__lh__)-> xd_prev = (__n__)-> xd_prev;\
(__n__)-> xd_prev-> xd_next = (__lh__);(__n__)-> xd_prev = (__lt__);\
} while(0)

#define XDS_list_insert_after( __n__ , __p__ )\
do {\
(__p__)-> xd_prev = (__n__);(__p__)-> xd_next = (__n__)-> xd_next;\
(__n__)-> xd_next-> xd_prev = (__p__);(__n__)-> xd_next = (__p__);\

} while(0)

#define XDS_list_insert_after2( __n__ , __lh__ , __lt__ )\
do {\
(__lh__)-> xd_prev = (__n__);(__lt__)-> xd_next = (__n__)-> xd_next;\
(__n__)-> xd_next-> xd_prev = (__lt__);(__n__)-> xd_next = (__lh__);\
} while(0)

#define XDS_list_push_back( __h__ , __p__ )XDS_list_insert_before( __h__ , __p__ )

#define XDS_list_push_front( __h__ , __p__ )XDS_list_insert_after( __h__ , __p__ )

#define XDS_list_erase( __n__ , __f__ )\
do {\
(__n__)-> xd_prev-> xd_next = (__n__)-> xd_next;\
(__n__)-> xd_next-> xd_prev = (__n__)-> xd_prev;\
__f__ ( __n__ );\
} while(0)

#define XDS_list_pop_back( __h__ , __f__ )\
do {\
void*__the_node__ = (__h__)-> xd_prev;\
(__h__)-> xd_prev-> xd_prev-> xd_next = (__h__);\
(__h__)-> xd_prev = (__h__)-> xd_prev-> xd_prev;\
__f__ ( __the_node__ );\
} while(0)

#define XDS_list_pop_front( __h__ , __f__ )\
do {\
void*__the_node__ = (__h__)-> xd_next;\
(__h__)-> xd_next-> xd_next-> xd_prev = (__h__);\
(__h__)-> xd_next = (__h__)-> xd_next-> xd_next;\
__f__ ( __the_node__ );\
} while(0)

#define XDS_list_cleanup( __h__ , __f__ )\
do {\
void*__the_first_node__;\
while(1)\
{\
XDS_list_pop_front( __h__ , __the_first_node__= );\
if( __the_first_node__ == __h__ ) break;\
__f__ ( __the_first_node__ );\
}\
} while(0)

#define XDS_list_for_each( __h__ , __n__ )\
for( (__n__) = (__h__)-> xd_next; (__h__) != (__n__); (__n__) = (__n__)-> xd_next )

/************************************************************************/

#endif
[解决办法]
/************************************************************************/
/* x_list_sort.inl
*/

#ifndef X_NODE_TYPE
#define X_NODE_TYPEXDS_p_list_node
#error X_NODE_TYPE must declare ...
#endif

#ifndef X_ALGO_LT
#define X_ALGO_LT( lhs , rhs )((lhs) < (rhs))
#errorX_ALGO_LT must declare ...
#endif

#ifndef X_NODE_SWAP
#define X_NODE_SWAP( prev , next )do {\
XDS_list_erase( prev , (void) );\
XDS_list_insert_after( next , prev );\
next = prev ; prev = next-> xd_prev;\
} while(0)
#endif

#ifndef X_ALGO_FUNC_USER_DECL
void X_ALGO_FUNC_NAME( X_NODE_TYPE lo , X_NODE_TYPE hi )/* [lo,hi] */
#else
X_ALGO_FUNC_USER_DECL
#endif
#undef X_ALGO_FUNC_USER_DECL
#undef X_ALGO_FUNC_NAME
{
X_NODE_TYPE pr , mid , ne , p , pn ;
X_NODE_TYPE lostk[ 32 ] , histk [ 32 ];
intstkptr = 0 , counter;

#if defined( X_ALGO_USER_DECL_CODE )
X_ALGO_USER_DECL_CODE ;
#undef X_ALGO_USER_DECL_CODE
#endif

if( lo == hi )/* 0 , 1 */
return ;
recurse:
if( lo-> xd_next == hi )/* 2 */{
if( X_ALGO_LT( hi , lo ) )
X_NODE_SWAP( lo , hi );}
else{
counter = 0;
pr = lo-> xd_prev;
ne = hi-> xd_next;
mid = hi-> xd_prev;
XDS_list_erase( lo , (void) );
XDS_list_insert_before( mid , lo );
if( X_ALGO_LT( mid , lo ) )X_NODE_SWAP( lo , mid );
if( X_ALGO_LT( hi , mid ) )X_NODE_SWAP( mid , hi );
if( X_ALGO_LT( mid , lo ) )X_NODE_SWAP( lo , mid );

for( p = pr-> xd_next; p != lo; ){
if( X_ALGO_LT( mid , p ) ){
--counter; pn = p ; p = p-> xd_next;
XDS_list_erase( pn , (void) );
XDS_list_insert_after( hi , pn );}
else{++counter; p = p-> xd_next;}}
if( counter <= 0 ){/* 1 .. 2 */
if( pr-> xd_next == lo )/* .1. */ {
if( hi != ne-> xd_prev ) {
lo = hi ; hi = ne-> xd_prev;
goto recurse; }}
else {
lostk[ stkptr ] = hi;
histk[ stkptr ] = ne-> xd_prev; ++stkptr;
hi = lo; lo = pr-> xd_next;
goto recurse;}}
else{
if( hi == ne-> xd_prev ) {
hi = lo; lo = pr-> xd_next;
goto recurse;}
else {
lostk[ stkptr ] = pr-> xd_next;
histk[ stkptr ] = lo; ++stkptr;
lo = hi; hi = ne-> xd_prev;
goto recurse;}}}
if( --stkptr > = 0 ){
lo = lostk[ stkptr ];
hi = histk[ stkptr ];
goto recurse;}
else
return;/* done */
}

#undef X_NODE_TYPE
#undef X_ALGO_LT
#undef X_NODE_SWAP