hg888皇冠手机登录

www.hg888.comC语言面向对象编制程序(五卡塔 尔(阿拉伯语:قطر‎:单链表完结

十一月 15th, 2019  |  www.hg888.com

单链表的粗略c++完毕

以下代码只兑现了单链表的手动创建以至出口作用

#include
using namespace std;
struct node
{
  int data;
  node *next;
};
class list
{
public:
    void creat();
    void show();

private:
    node *head;

};
void list::creat()   //创建链表
{
    node *f=new node();  //建立链表的第一个元素
    f->data=44;
    f->next=NULL;
    head=f;

    f=new node();       //建立链表的第二个元素
    f->data=72;
    f->next=NULL;
    head->next=f;

    f=new node();        //建立链表的第三个元素
    f->data=220;
    f->next=NULL;

    head->next->next=f;
}
void list::show()  //输出链表
{
  node *p=head;
  while(p->next)
  {
    cout<data<<"->";
    p=p->next;
  }
  cout<data<

以下代码只兑现了单链表的手动创制甚至出口功用 #include using namespace
std;struct node{ int data; node *next;};class list{public: v…

  

前方大家介绍了什么在 C
语言中引进面向对象语言的有的天性来张开面向对象编制程序,从本篇先河,大家采纳前面提到的本领,陆陆续续完毕多少个例子,最终吧,会提供一个骨干的
http server 完成(使用 libevent
卡塔 尔(阿拉伯语:قطر‎。在此篇文章里,大家贯彻三个通用的数据结构:单链表。

  小编想你去过多家杂货店面试的时候,蒙受单链表倒置的标题或然超级多,借使应当要给面试题来叁个排行的榜单,测度也能上top10啊,其实这几个

那边达成的单链表,能够储存自便数据类型,扶植增、删、改、查找、插入等基本操作。(本文提供的是全体代码,大概某些长。卡塔尔国

标题玩的是技术和您对单链表的知道,其实大家紧凑思索亦不是很难,既然是倒置,那咱们必定是必必要走叁遍单链表的,对吗,那么走单链

下边是头文件:

表有二种样式,递归和巡回二种办法,而递归正是压栈和出栈,那么咱们就想起来了,那不正是种种和逆序的涉嫌啊?第三种就是循环,还记

#ifndef SLIST_H
#define SLIST_H

#ifdef __cplusplus
extern "C" {
#endif

#define NODE_T(ptr, type) ((type*)ptr)

struct slist_node {
    struct slist_node * next;
};

typedef void (*list_op_free_node)(struct slist_node *node);
/*
 * return 0 on hit key, else return none zero
 */
typedef int (*list_op_key_hit_test)(struct slist_node *node, void *key);

struct single_list {
    /* all the members must not be changed manually by callee */
    struct slist_node * head;
    struct slist_node * tail;
    int size; /* length of the list, do not change it manually*/

    /* free method to delete the node
     */
    void (*free_node)(struct slist_node *node);
    /*
     * should be set by callee, used to locate node by key(*_by_key() method)
     * return 0 on hit key, else return none zero
     */
    int (*key_hit_test)(struct slist_node *node, void *key);

    struct single_list *(*add)(struct single_list * list, struct slist_node * node);
    struct single_list *(*insert)(struct single_list * list, int pos, struct slist_node *node);
    /* NOTE: the original node at the pos will be freed by free_node */
    struct single_list *(*replace)(struct single_list *list, int pos, struct slist_node *node);
    struct slist_node *(*find_by_key)(struct single_list *, void * key);
    struct slist_node *(*first)(struct single_list* list);
    struct slist_node *(*last)(struct single_list* list);
    struct slist_node *(*at)(struct single_list * list, int pos);
    struct slist_node *(*take_at)(struct single_list * list, int pos);
    struct slist_node *(*take_by_key)(struct single_list * list, void *key);
    struct single_list *(*remove)(struct single_list * list, struct slist_node * node);
    struct single_list *(*remove_at)(struct single_list *list, int pos);
    struct single_list *(*remove_by_key)(struct single_list *list, void *key);
    int (*length)(struct single_list * list);
    void (*clear)(struct single_list * list);
    void (*deletor)(struct single_list *list);
};

struct single_list * new_single_list(list_op_free_node op_free, list_op_key_hit_test op_cmp);

#ifdef __cplusplus
}
#endif

#endif // SLIST_H

得我们曾今学习单链表的时候有风流浪漫种插法叫做头插法,这种插入复杂度为O(1),倒霉之处正是逐豆蔻年华插入的数字,出来的时候却是反的,所以那

struct single_list
这么些类,据守大家后面介绍的着力尺度,不再意气风发风度翩翩细说。有几点须求提一下:

个不正是能够将本来的链表原地倒置过来呢?

咱俩定义了 slist_node 作为链表节点的基类,客商自定义的节点,都必得从
slist_node 世袭为了扶持节点( node 卡塔 尔(阿拉伯语:قطر‎的获释,大家引进叁个回调函数
list_op_free_node
,那么些回调要求在开创链表时传出为了援协助调查找,引进别的二个回调函数
list_op_key_hit_test

 

好了,下边看落到实处公文:

一:递归

#include "slist.h"
#include 

static struct single_list * _add_node(struct single_list *list, struct slist_node *node)
{

    if(list->tail)
    {
        list->tail->next = node;
        node->next = 0;
        list->tail = node;
        list->size++;
    }
    else
    {
        list->head = node;
        list->tail = node;
        node->next = 0;
        list->size = 1;
    }

    return list;
}

static struct single_list * _insert_node(struct single_list * list, int pos, struct slist_node *node)
{
    if(pos < list->size)
    {
        int i = 0;
        struct slist_node * p = list->head;
        struct slist_node * prev = list->head;
        for(; i < pos; i++)
        {
            prev = p;
            p = p->next;
        }
        if(p == list->head)
        {
            /* insert at head */
            node->next = list->head;
            list->head = node;
        }
        else
        {
            prev->next = node;
            node->next = p;
        }

        if(node->next == 0) list->tail = node;
        list->size++;
    }
    else
    {
        list->add(list, node);
    }

    return list;
}

static struct single_list * _replace(struct single_list * list, int pos, struct slist_node *node)
{
    if(pos < list->size)
    {
        int i = 0;
        struct slist_node * p = list->head;
        struct slist_node * prev = list->head;
        for(; i < pos; i++)
        {
            prev = p;
            p = p->next;
        }
        if(p == list->head)
        {
            /* replace at head */
            node->next = list->head->next;
            list->head = node;
        }
        else
        {
            prev->next = node;
            node->next = p->next;
        }

        if(node->next == 0) list->tail = node;

        if(list->free_node) list->free_node(p);
        else free(p);
    }

    return list;
}

static struct slist_node * _find_by_key(struct single_list *list, void * key)
{
    if(list->key_hit_test)
    {
        struct slist_node * p = list->head;
        while(p)
        {
            if(list->key_hit_test(p, key) == 0) return p;
            p = p->next;
        }
    }
    return 0;
}

static struct slist_node *_first_of(struct single_list* list)
{
    return list->head;
}

static struct slist_node *_last_of(struct single_list* list)
{
    return list->tail;
}

static struct slist_node *_node_at(struct single_list * list, int pos)
{
    if(pos < list->size)
    {
        int i = 0;
        struct slist_node * p = list->head;
        for(; i < pos; i++)
        {
            p = p->next;
        }
        return p;
    }

    return 0;
}

static struct slist_node * _take_at(struct single_list * list, int pos)
{
    if(pos < list->size)
    {
        int i = 0;
        struct slist_node * p = list->head;
        struct slist_node * prev = p;
        for(; i < pos ; i++)
        {
            prev = p;
            p = p->next;
        }
        if(p == list->head)
        {
            list->head = p->next;
            if(list->head == 0) list->tail = 0;
        }
        else if(p == list->tail)
        {
            list->tail = prev;
            prev->next = 0;
        }
        else
        {
            prev->next = p->next;
        }

        list->size--;

        p->next = 0;
        return p;
    }

    return 0;
}

static struct slist_node * _take_by_key(struct single_list * list, void *key)
{
    if(list->key_hit_test)
    {
        struct slist_node * p = list->head;
        struct slist_node * prev = p;
        while(p)
        {
            if(list->key_hit_test(p, key) == 0) break;
            prev = p;
            p = p->next;
        }

        if(p)
        {
            if(p == list->head)
            {
                list->head = p->next;
                if(list->head == 0) list->tail = 0;
            }
            else if(p == list->tail)
            {
                list->tail = prev;
                prev->next = 0;
            }
            else
            {
                prev->next = p->next;
            }

            list->size--;

            p->next = 0;
            return p;
        }
    }
    return 0;
}

static struct single_list *_remove_node(struct single_list * list, struct slist_node * node)
{
    struct slist_node * p = list->head;
    struct slist_node * prev = p;
    while(p)
    {
        if(p == node) break;
        prev = p;
        p = p->next;
    }

    if(p)
    {
        if(p == list->head)
        {
            list->head = list->head->next;
            if(list->head == 0) list->tail = 0;
        }
        else if(p == list->tail)
        {
            prev->next = 0;
            list->tail = prev;
        }
        else
        {
            prev->next = p->next;
        }

        if(list->free_node) list->free_node(p);
        else free(p);

        list->size--;
    }
    return list;
}

static struct single_list *_remove_at(struct single_list *list, int pos)
{
    if(pos < list->size)
    {
        int i = 0;
        struct slist_node * p = list->head;
        struct slist_node * prev = p;
        for(; i < pos ; i++)
        {
            prev = p;
            p = p->next;
        }
        if(p == list->head)
        {
            list->head = p->next;
            if(list->head == 0) list->tail = 0;
        }
        else if(p == list->tail)
        {
            list->tail = prev;
            prev->next = 0;
        }
        else
        {
            prev->next = p->next;
        }

        if(list->free_node) list->free_node(p);
        else free(p);

        list->size--;
    }

    return list;
}

static struct single_list *_remove_by_key(struct single_list *list, void *key)
{
    if(list->key_hit_test)
    {
        struct slist_node * p = list->head;
        struct slist_node * prev = p;
        while(p)
        {
            if(list->key_hit_test(p, key) == 0) break;
            prev = p;
            p = p->next;
        }

        if(p)
        {
            if(p == list->head)
            {
                list->head = list->head->next;
                if(list->head == 0) list->tail = 0;
            }
            else if(p == list->tail)
            {
                prev->next = 0;
                list->tail = prev;
            }
            else
            {
                prev->next = p->next;
            }

            if(list->free_node) list->free_node(p);
            else free(p);

            list->size--;
        }
    }

    return list;
}

static int _length_of(struct single_list * list)
{
    return list->size;
}

static void _clear_list(struct single_list * list)
{
    struct slist_node * p = list->head;
    struct slist_node * p2;
    while(p)
    {
        p2 = p;
        p = p->next;

        if(list->free_node) list->free_node(p2);
        else free(p2);
    }

    list->head = 0;
    list->tail = 0;
    list->size = 0;
}

static void _delete_single_list(struct single_list *list)
{
    list->clear(list);
    free(list);
}

struct single_list * new_single_list(list_op_free_node op_free, list_op_key_hit_test op_cmp)
{
    struct single_list *list = (struct single_list *)malloc(sizeof(struct single_list));
    list->head = 0;
    list->tail = 0;
    list->size = 0;
    list->free_node = op_free;
    list->key_hit_test = op_cmp;

    list->add = _add_node;
    list->insert = _insert_node;
    list->replace = _replace;
    list->find_by_key = _find_by_key;
    list->first = _first_of;
    list->last = _last_of;
    list->at = _node_at;
    list->take_at = _take_at;
    list->take_by_key = _take_by_key;
    list->remove = _remove_node;
    list->remove_at = _remove_at;
    list->remove_by_key = _remove_by_key;
    list->length = _length_of;
    list->clear = _clear_list;
    list->deletor = _delete_single_list;

    return list;
}

 
谈到递归,大家脑子里面料定要有四个V型图,还恐怕有多个便是好记性比不上烂笔头,算法那东西很难用脑子想的敞亮的,多画画图就见青天了,

地点的代码就不风姿罗曼蒂克后生可畏细说了,上面是测量检验代码:

上面小编就举个大约的事例:现存链表L={8,1,6,3},须要将L倒置,然后作者就画好了V型图。

/* call 1 or N arguments function of struct */
#define ST_CALL(THIS,func,args...) ((THIS)->func(THIS,args))

/* call none-arguments function of struct */
#define ST_CALL_0(THIS,func) ((THIS)->func(THIS))

struct int_node {
    struct slist_node node;
    int id;
};

struct string_node {
    struct slist_node node;
    char name[16];
};


static int int_free_flag = 0;
static void _int_child_free(struct slist_node *node)
{
    free(node);
    if(!int_free_flag)
    {
        int_free_flag = 1;
        printf("int node free\n");
    }
}

static int _int_slist_hittest(struct slist_node * node, void *key)
{
    struct int_node * inode = NODE_T(node, struct int_node);
    int ikey = (int)key;
    return (inode->id == ikey ? 0 : 1);
}

static int string_free_flag = 0;
static void _string_child_free(struct slist_node *node)
{
    free(node);
    if(!string_free_flag)
    {
        string_free_flag = 1;
        printf("string node free\n");
    }
}

static int _string_slist_hittest(struct slist_node * node, void *key)
{
    struct string_node * sn = (struct string_node*)node;
    return strcmp(sn->name, (char*)key);
}

void int_slist_test()
{
    struct single_list * list = new_single_list(_int_child_free, _int_slist_hittest);
    struct int_node * node = 0;
    struct slist_node * bn = 0;
    int i = 0;

    printf("create list && nodes:\n");
    for(; i < 100; i++)
    {
        node = (struct int_node*)malloc(sizeof(struct int_node));
        node->id = i;
        if(i%10)
        {
            list->add(list, node);
        }
        else
        {
            list->insert(list, 1, node);
        }
    }
    printf("create 100 nodes end\n----\n");
    printf("first is : %d, last is: %d\n----\n",
           NODE_T( ST_CALL_0(list, first), struct int_node )->id,
           NODE_T( ST_CALL_0(list, last ), struct int_node )->id);

    assert(list->size == 100);

    printf("list traverse:\n");
    for(i = 0; i < 100; i++)
    {
        if(i%10 == 0) printf("\n");
        bn = list->at(list, i);
        node = NODE_T(bn, struct int_node);
        printf(" %d", node->id);
    }
    printf("\n-----\n");

    printf("find by key test, key=42:\n");
    bn = list->find_by_key(list, (void*)42);
    assert(bn != 0);
    node = NODE_T(bn, struct int_node);
    printf("find node(key=42), %d\n------\n", node->id);

    printf("remove node test, remove the 10th node:\n");
    bn = list->at(list, 10);
    node = NODE_T(bn, struct int_node);
    printf("  node 10 is: %d\n", node->id);
    printf("  now remove node 10\n");
    list->remove_at(list, 10);
    printf(" node 10 was removed, check node 10 again:\n");
    bn = list->at(list, 10);
    node = NODE_T(bn, struct int_node);
    printf("  now node 10 is: %d\n------\n", node->id);

    printf("replace test, replace node 12 with id 1200:\n");
    bn = list->at(list, 12);
    node = NODE_T(bn, struct int_node);
    printf("  now node 12 is : %d\n", node->id);
    node = (struct int_node*)malloc(sizeof(struct int_node));
    node->id = 1200;
    list->replace(list, 12, node);
    bn = list->at(list, 12);
    node = NODE_T(bn, struct int_node);
    printf("  replaced, now node 12 is : %d\n----\n", node->id);

    printf("test remove:\n");
    ST_CALL(list, remove, bn);
    bn = ST_CALL(list, find_by_key, (void*)1200);
    assert(bn == 0);
    printf("test remove ok\n----\n");
    printf("test remove_by_key(90):\n");
    ST_CALL(list, remove_by_key, (void*)90);
    bn = ST_CALL(list, find_by_key, (void*)90);
    assert(bn == 0);
    printf("test remove_by_key(90) end\n----\n");
    printf("test take_at(80):\n");
    bn = ST_CALL(list, take_at, 80);
    printf("  node 80 is: %d\n", NODE_T(bn, struct int_node)->id);
    free(bn);
    printf("test take_at(80) end\n");

    int_free_flag = 0;
    printf("delete list && nodes:\n");
    list->deletor(list);
    printf("delete list && nodes end\n");
    printf("\n test add/insert/remove/delete/find_by_key/replace...\n");
}

void string_slist_test()
{
    struct single_list * list = new_single_list(_string_child_free, _string_slist_hittest);
}

void slist_test()
{
    int_slist_test();
    string_slist_test();
}

www.hg888.com 1

测验代码里重要演示了:

从图中能够看出,当自己递归到3再出栈的时候,只必要将6赋给3.next,1赋给6.next,然后那样就那样类推。。。最终结果就出来了,貌似

自定义链表节点类型定义释放回调定义用于查找的 hit test
回调怎样创建链表怎么样利用( add 、remove 、 take 、find 、 insert 等卡塔 尔(阿拉伯语:قطر‎

口头上描述起来非常粗大略,不过在写代码的时候须要专一以下多少个点,先上代码说话。

言听计行到此地,单链表的利用已经正常了。

 1         public LinkNode Reverse(LinkNode node)
 2         {
 3             if (node.next == null)
 4                 return node;
 5 
 6             var prevNode = Reverse(node.next);
 7 
 8             var temp = node.next;
 9 
10             temp.next = node;
11 
12             node.next = null;
13 
14             return prevNode;
15         }

以单链表为根底,能够更进一层贯彻无数数据结构,比如树(兄弟孩子表示法卡塔 尔(英语:State of Qatar),比如key-value 链表等等。接下来依据例子的须求,会择机实行显示。

 

C
语言中引进面向对象语言的后生可畏部分表征来开展面向对象编制程序,从本篇起头,大家使用前边提到的技术,时断时续落到实处多少个…

标签:, ,

Your Comments

近期评论

    功能


    网站地图xml地图