| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 10184 人关注过本帖, 1 人收藏
标题:分享:通用链表(有任何问题或建议,请提出)(5.2新增两个函数)
只看楼主 加入收藏
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
结帖率:95.65%
收藏(1)
已结贴  问题点数:20 回复次数:47 
分享:通用链表(有任何问题或建议,请提出)(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编辑过]

搜索更多相关主题的帖子: 通用 
2017-04-25 00:25
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:7 
回复 楼主 renkejun1942
创建链表,我没明白有什么用,所以就没写。


可能是指 先创建一个 句柄 或是  初始化执行环境, 像下面的回调, 可以统一用一个Create/Init接口 进行设置, 简洁也方便维护

void Insert( List *RootPP, void *Value, int TypeSize , int (*compare)( void *, void * ) );

void Print( List RootP, void (*PRINT)( void * ) );

void Delete( List *RootPP );

void DeleteNode( List *RootPP, void *value, int ( *compare )( void *, void * ) );
2017-04-25 00:51
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 2楼 寒风中的细雨
创建链表似乎就是单纯的返回一个NULL指针。
所以我没闹明白,创建链表这个函数有什么具体用处,为什么不直接声明一个NULL的链表指针。

[此贴子已经被作者于2017-4-25 01:01编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-04-25 00:55
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:7 
发现自己对"句柄"和"封装"理解不到位~还是不多说了~~~

[此贴子已经被作者于2017-4-25 12:42编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-25 04:15
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
首先写了一部分不完整的~还没有封装完毕~就是更新了用一个句柄来调用函数~

程序代码:
#include<stdlib.h>
#include<string.h>
#include<assert.h>

#ifndef _STRUCTURE_LIST_
#define _STRUCTURE_LIST_

#define LEN_List sizeof(List)

typedef struct List
{
    void* Element;
    struct List* next;
}List,*PList;

typedef struct HAND_LIST
{
    void (*Creat_Node)(PList* p,void* Value,int size);   //创建一个节点并赋予初值
    void (*Insert_Node)();
}HAND_LIST;

 
void Creat_Node(PList* p,void* Value,int size);
void Insert_Node();

HAND_LIST Hand_List=
{
    Creat_Node,
    Insert_Node
};

void Creat_Node(PList* p,void* Value,int size)
{
    *p=(PList)malloc(LEN_List);
    assert(*p!=NULL);
    memset(*p,0,LEN_List);

    (*p)->Element=malloc(size);
    assert((*p)->Element!=NULL);
    memset((*p)->Element,0,size);

    memmove((*p)->Element,Value,size);
}

void Insert_Node()
{

}
#endif

程序代码:
#include"List.h"
#include<stdio.h>

typedef struct Node
{
    int a;
    char b;
}Node,*PNode;

int main()
{
    PList head=NULL;
    Node node={0};

    node.a=1;
    node.b=2;

    Hand_List.Creat_Node(&head,&node,sizeof(Node));

    printf("%d\n%d\n",((PNode)(head->Element))->a,((PNode)(head->Element))->b);

    return 0;
}



[此贴子已经被作者于2017-4-25 05:53编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-25 05:16
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:7 
乱用“句柄”这个专有名词。
句柄是由系统管理的指针,在整个操作系统运行期间具有唯一性,程序只能通过操作系统创建并使用,主要作为和底层I/O或文件打交道的接口,所以通常也叫设备句柄。
2017-04-25 06:20
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 4楼 九转星河
你的意思是自动补齐吧?
我用VIM只要调用这个.h文件,就可以自动补齐。
vs我好久不用了,不清楚可不可以这样。

封装,C语言没有封装的概念吧?封装我怎么都记得是C++的概念。

我搜一下封装,学学吧。看了下你写的代码,嗯……很简单。我现在在上班,等时间…………
其实具体点应该是创建并初始化节点判断分配内存状态并把链表指针和抽象指针赋值给NULL;这创建节点这个操作样可以简并成一行代码完成~

原来是这样,我当时看到书上的一段示例代码,就是创建链表……我想破头都没弄明白,为什么要分配节点,然后再删除这个节点。
现在我算是明白了。
嗯……我回家之后,把这个函数补上。


[此贴子已经被作者于2017-4-25 10:39编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-04-25 10:23
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 6楼 xzlxzlxzl
好像我不只对"句柄"理解不到位~对"封装也是"~
重新思考了一下~感觉句柄简单理解就是系统处理一些底层硬件设备的操作接口~感觉这个和汇编有些联系~~

[此贴子已经被作者于2017-4-25 12:47编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-25 12:42
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 7楼 renkejun1942
我还是先按自己的思路写写~如果有兴趣的话可以试试写个链表排序函数~感觉那个就没那么简单了~~而且感觉栈和队列的链表操作也有通用性~有兴趣也可以写一下~~~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-25 12:45
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 9楼 九转星河
栈和队列,已经可以用主题贴中的代码了,然后封装一下就行了。
只有一些小细节要处理,不过应该不是什么大问题。

高效的链式栈和队列,我还需要再想想。

链表排序这一个,当时学到链表的时候,我还真想过。不过最终没动手,打算等学到排序算法的时候再来说吧。
我当时想的方法是不排序,建立一个buffer,利用升序/降序插入buffer,然后删除掉原链表,最后将新链表作为返回值返回。
这是当时想的,结果没写。

[此贴子已经被作者于2017-4-25 12:58编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-04-25 12:56
快速回复:分享:通用链表(有任何问题或建议,请提出)(5.2新增两个函数)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.023971 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved