分享：通用链表（有任何问题或建议，请提出）（5.2新增两个函数）
思路借鉴了库函数qsort，由具体的程序提供比较和打印函数，GenericityList.h中的函数完成对链表的所有操作。 链表中的值字段可以是任意的数据类型。
Insert函数要求提供数据类型的大小，以及一个比较函数。
Print函数要求提供一个打印函数。
DeleteNode函数要求提供一个比较函数。
5.2
新增两个函数，QuickOperateR（） 和 OperateR（）
这两个函数执行相同的任务，逆向操作链表中的节点，如果只是单纯的逆序打印链表中的节点，那么这两个函数等同于Reverse（）+ Print（） + Reverse（）函数相同。
这两个函数的不同在于，QuickOperateR为递归实现。
而OperateR为迭代实现。
创建链表，我没明白有什么用，所以就没写。
在Insert中，比较函数如果永远返回-1，那么就是头部插入；如果永远返回1，就是尾部插入；根据不同的比较函数的返回值，也可以按照升序或降序插入。
应用：
https://bbs.bccn.net/viewthread.php?tid=476513&page=1&extra=page%3D1#pid2626355
程序代码：
//测试：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include "GenericityList.h"
int
COM( void *a, void *b );
int
com( void *, void * );
void
PRINT( void * );
int
main( void )
{
List Root;
List T;
int s;
int ix;
srand( ( unsigned )time( NULL ) );
Root = NULL;
for( ix = 0; 20 > ix; ++ix )
{
s = rand() % 10000;
Insert( &Root, &s, sizeof( int ), COM);
}
Print( Root, PRINT );
Reverse( &Root );
printf("\n逆序后：\n");
Print( Root, PRINT );
DeleteNode( &Root, &s, com );
printf( "\n删除第一个节点：\n" );
Print( Root, PRINT );
T = First( Root );
printf( "\n首节点的值：" );
PRINT( T->Element );
printf( "\n" );
while( !DelFirst( &Root ) )
{
printf( "\n删除首节点：" );
Print( Root, PRINT );
}
if( NULL == ( T = First( Root ) ) )
printf( "\n空链表\n" );
printf( "\n\n\n" );
Delete( &Root );
Print( Root, PRINT );
return 0;
}
int
COM( void *a, void *b )
{
return ( *( int * )a - *( int * )b ) > 0? 1: -1;
}
int
com( void *a, void *b )
{
return 0;
}
void
PRINT( void *a )
{
printf("%d ",*( int* )a );
}
程序代码：
//接口：
#ifndef _GENERICITY_LIST_
#define _GENERICITY_LIST_
struct List{
void *Element;
struct List *Link;
};
typedef struct List List_T;
typedef List_T *List;
typedef List List_T_P;
int
Insert( List *RootPP, void *Value, unsigned int DataSize , int ( *Compare )( void *, void * ) );//插入节点，成功返回1，否则返回1
void
Print( List RootP, void ( *Print )( void * ) );
void
Delete( List *RootPP );
int
DeleteNode( List *RootPP, void *Value, int ( *Compare )( void *, void * ) );//删除节点，成功返回0，否则返回1
List
Find( List RootP, void *Value, int ( *Compare )( void *, void * ) );//查找节点，成功返回该节点，否则返回NULL
void
Reverse( List *RootP );
List
First( List RootP );//返回首节点，如果链表为空，则返回NULL
int
DelFirst( List *RootPP );//删除首节点，成功返回0，否则返回1
void
OperateR( List Root, void ( *Operate )( List ) );//链表逆操作
void
QuickOperateR( List Root, void ( *Operate )( List ) );//链表逆操作
#endif
程序代码：
//实现：
#include "GenericityList.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
enum { OK = 0, NOT };
int
Insert( List *RootPP, void *value, unsigned int DataSize , int ( *compare )( void *, void * ) )
{
List Next;
List NewCell;
while( NULL != ( Next = *RootPP ) && 0 < compare( Next->Element, value ) )
RootPP = &Next->Link;
if( NULL == ( NewCell = ( List )malloc( sizeof( struct List ) ) ) )
return NOT;
if( NULL == ( NewCell->Element = malloc( DataSize ) ) )
return NOT;
memmove( NewCell->Element, value, DataSize );
NewCell->Link = Next;
*RootPP = NewCell;
return OK;
}
void
Print( List RootP, void ( *print )( void * ) )
{
while( NULL != RootP )
{
print( RootP->Element );
RootP = RootP->Link;
}
}
void
Delete( List *RootPP )
{
List Temp;
List This;
for( This = *RootPP, *RootPP = NULL; NULL != This; This = Temp )
{
Temp = This->Link;
free( This->Element );
free( This );
}
}
int
DeleteNode( List *RootPP, void *value, int ( *compare )( void *, void * ) )
{
List This;
for( ;NULL != ( This = *RootPP ); RootPP = &This->Link )
if( 0 == compare( This->Element, value ) )
break;
if( NULL != This )
{
*RootPP = This->Link;
free( This->Element );
free( This );
return OK;
}
return NOT;
}
List
Find( List RootP, void *value, int ( *compare )( void *, void * ) )
{
List This;
for( This = RootP; NULL != This; This = This->Link )
if( 0 == compare( This->Element, value ) )
break;
return This;
}
List
Reverse( List RootP )
{
List Next, Current;
for( Current = NULL; NULL != RootP; RootP = Next )
{
Next = RootP->Link;
RootP->Link = Current;
Current = RootP;
}
return Current;
}
/*下面这个不要返回的Reverse函数好么，怎么都感觉不如有返回值的，还是说我写的太烂了。*/
/*
void
Reverse( List *RootP )
{
List Next, Current;
for( Current = NULL; NULL != *RootP; *RootP = Next )
{
Next = (*RootP)->Link;
(*RootP)->Link = Current;
Current = *RootP;
if( NULL == Next )
break;
}
}
*/
static int
__C__O__M__( void *, void * );
List
First( List RootP )
{
return Find( RootP, ( void * )0, __C__O__M__ );
}
int
DelFirst( List *RootPP )
{
return DeleteNode( RootPP, ( void * )0, __C__O__M__ );
}
int
__C__O__M__( void *a, void *b )
{
return 0;
}
void
QuickOperateR( List Root, void ( *Operate )( List ) )
{
if( NULL == Root )
return;
QuickOperateR( Root->Link, Operate );
Operate( Root );
}
static void
Push( List );
static List
Pop( void );
static void
Destroy( void );
static int
IsEmpty( void );
static int
IsFull( void );
void
OperateR( List Root, void ( *Operate )( List ) )
{
while( NULL != Root )
{
Push( Root );
Root = Root->Link;
}
while( !IsEmpty() )
Operate( Pop() );
Destroy();
}
#define INITSIZE 128
static List *Stack;
static int Top = -1;
static int CurrentSize = INITSIZE;
int
IsEmpty( void )
{
return -1 == Top;
}
int
IsFull( void )
{
List *Temp;
if( Top == CurrentSize )
{
CurrentSize += INITSIZE;
Temp = ( List * )realloc( Stack, CurrentSize * sizeof( List_T ) );
if( NULL == Temp )
{
CurrentSize -= INITSIZE;
return NOT;
}
Stack = Temp;
return OK;
}
else
return OK;
}
void
Push( List a )
{
if( NULL == Stack )
{
Stack = ( List * )malloc( CurrentSize * sizeof( List_T ) );
if( NULL == Stack )
exit( EXIT_FAILURE );
}
if( !IsFull() )
Stack[ ++Top ] = a;
else
return;
}
List
Pop( void )
{
return Stack[ Top--];
}
void
Destroy( void )
{
free( Stack );
Stack = NULL;
Top = -1;
CurrentSize = INITSIZE;
}
[此贴子已经被作者于2017-5-3 17:06编辑过]
~~~
~~~~