泛型思想理解数据结构链表-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

泛型思想理解数据结构链表

简介:

前言

  1. 本文用到一个很重要的思想--泛型编程思想;不熟悉泛型的话,请自行搜索相关资料学习(void *,如memcpy,memmove,qsort,memset等库函数均使用到了泛型思想) 。
  2. 本文最后会提供一个demo程序附件,该demo程序以c99标准进行编写的,在Linux-gcc下调试通过,vc6下可能会有错误。
  3. 本文图示中,红色实线表示要添加的地方,黑色虚线表示要断开的地方,黑色实线保持原样。
  4. 本文链表设计为最简单的非循环单链表。
    数组与链表比较

     数组    链表

    优点 存取速度快

操作方便 不限制大小
插入删除易于实现
空间无需连续
缺点 插入删除等操作不易实现
需要连续空间存储
数组元素需要类型相同 存取速度慢
操作复杂
通过比较可以发现,数组的优点正好就是链表的缺点,而链表的缺点正好是数组的优点。
链表的分类

单链表
    每个节点有1个指针域,指向后继(next)
双链表
    每个节点都有2个指针域,一个指向前驱(previous),一个指向后继(next)
循环链表
    首尾相接,tail->next = head; 能通过任意一个节点找到其他所有的节点
非循环链表
    首尾不相接,tail->next = NULL;通过head可以找到所有节点。

链表数据结构
typedef struct node{ //节点结构

void *data;
struct node *next;

} node;

typedef struct { //链表结构

struct node *head;
struct node *tail;
long len;

} List;
常见链表算法
初始化 void list_init(List *list);
销毁 void list_destroy(List list, void (destroy)(void *));
插入 void list_insert(List list, void data);

头插法    void  list_insert_at_head(List *list, void *data);                                   
随插法    void  list_insert_at_index(List *list, void *data);                                  
尾插法    void  list_insert_at_tail(List *list, void *data, long idx);                         

删除 void list_delete(List list, void key, int (compare)(const void , const void ));
搜索 void list_search(List list, void key, int (compare)(const void , const void ));
排序 void list_sort(List list, void key, int (compare)(const void , const void ));
遍历 void list_traverse(List list, void (handle)(void *));
逆序 void list_reverse(List *list);
求长度 long get_lenth(List *list);
获取链表节点 void list_get_element(List list, long index);
判断空链表 bool is_empty(List *list);
各算法的详解与实现
已知链表结构如下所示
typedef struct{ //链表结构

struct node *head;
struct node *tail;
long len;

}List;
该链表有具有3个属性,头指针head,尾指针tail以及链表长度len;

首先,定义一个链表,
List list;
此时链表结构如下所示:

链表的初始化
链表刚建立的时候,是不含任何有效数据的,也就是说不含有效节点。因此头指针head和尾指针tail无指向,即指向NULL,此时链表长度为0。
即此时链表结构如下所示

程序实现
void list_init(List *list)
{

list->head = NULL;
list->tail = NULL;
list->len = 0;

}
刚初始化完的链表是一个空链表,空链表的头指针必定为NULL,该特征可以作为判定空链表的依据,由此实现判断空链表的程序

include

bool is_empty(List *list)
{

return (list->head == NULL);

}
链表节点的插入
链表初始化完成之后,就可以进行各种操作(如插入删除节点,求长度,销毁链表等)了,下面来解释一下链表插入的操作方法;
插入节点需要分2种情况讨论:

  1. 链表为空时,插入的第一个节点(首节点);
  2. 在非空链表上插入一个节点。
    1、第一种情况

该种情况可用下图表示

    此时,只有一个节点A,此时节点A既是首节点(因此head指向节点A),又是尾节点(因此tail也指向节点A,并且A->next = NULL);同时,链表长度要相应的+1(插入程序中,len始终呈++的状态,下文不再赘述)。

程序实现(假设n为待插入的节点)
struct node *new;

list->head = new;
list->tail = new;
new->next = NULL;

list->len++;
2、第二种情况
第二种情况又分为3种情况,根据新节点的插入位置,分为

1.在头部插,头插法:list_insert_at_head(...);
2.在尾部插,尾插法:list_insert_at_tail(...);
3.在第index个节点处插,随插法:list_insert_at_index(...)。

2.1、头插法

                        
    分析图例可知,已有链表(左侧),list->head = A;现在要在head处插入一个节点N,需要断开head与A的连接,使N->next = A;然后list->head = N(这两步不可调换顺序,可以想想为什么?)。

程序实现如下:
struct node *new;

new->next = list->head->next;
list->head = new;

list->len++;

2.2、尾插法

                                  
    分析图例可知,已有链表(左侧),list->tail = Z;现在要在tail处插入一个节点N,需要断开tail与Z的连接,使Z->next = N;(即list->tail->next = N;)然后list->tail = N(这两步可以调换顺序吗?想想为什么?),然后再使N->next = NULL。

程序实现如下:
struct node *new;

list->tail->next = new;
list->tail = new;
new->next = NULL;

list->len++;

2.3、随插法

                              
    分析图例可知,已有链表(左侧),A->next= B;现在要在A处插入一个节点N,需要断开A与B的连接,使N->next = B;(即N->next = A->next;)然后使A->next = N(这两步可以调换顺序吗?想想为什么?)。
    随插法由于插入位置不确定,所以不一定在图中的A节点处插入,有可能是B、C、D甚至Z。所以此处需要通过用户给定的index值配合list->head来找到插入位置。

代码实现如下:
static struct node make_node(void data) //把用户传递过来的数据打包为一个链表节点
{

struct node *n;

n = malloc(sizeof(struct node));
assert(n != NULL);

n->next = NULL;
n->data = data;

return n;

}
__
void list_insert_at_head(List list, void data) //头插法
{

struct node *n;
n = make_node(data);

if(list->head == NULL){ //如果是空链表
    list->head = n;
    list->tail = n;
}
else{                   //如果不是非空链表
    n->next = list->head;
    list->head = n;
}
list->len++;

}
__
void list_insert_at_tail(List list, void data) //尾插法
{

struct node *n;
n = make_node(data);

if(list->head == NULL){    //如果是空链表
    list->head = n;
    list->tail = n;
    n->next = NULL;
}
else{                      //如果不是非空链表
    list->tail->next = n;
    list->tail = n;
    n->next = NULL;
}
list->len++;

}
__
void list_insert_at_index(List list, void data, long index)
{

long i = 1; //从1开始算
struct node *p, *n;

p = list->head;

while(p && i < index){
    p = p->next;
    i++;
}

if(p){ //如果链表遍历完了,计数i还没到index,说明第index个节点不存在。
    n = make_node(data);
    n->next = p->next;
    p->next = n;
    list->len++;
}

}
__
void list_insert(List list, void data) //默认采用尾插法
{

list_insert_at_tail(list, data);

}
链表节点的删除
删除链表中的一个已有节点,如下图所示:

             
    分析图例可知,已有链表(左侧),A->next= B;B->next = C;现在要删除节点B,那么需要断开节点AB和BC之间的关系,然后把AC连接起来。即A->next = A->next->next;然后根据需要f释放节点B即可。

程序实现:
void list_delete(List list, void *key,

        int (*compare)(const void *, const void *))  //以key为删除关键词,compare为节点数据比较机制,由用户自己编写  

{

void *data;
struct node *n, *t;
n = list->head;

if(!compare(n->data, key)){    //如果要删除的节点为首节点
    printf("list_delete\n");
    t = n;
    data = n->data;
    list->head = n->next;
    free(t);
    list->len--;
    return data;
}

while(n->next != NULL){        //遍历查找符合条件的节点,删除之
    if(compare(n->next->data, key) == 0){    //只删除第一个符合条件的节点。
        t = n->next;
        if(n->next == list->tail){
            list->tail = n;
        }
        n->next = n->next->next;
        data = t->data;
        free(t);
        list->len--;
        return data;    //把删除的数据返回给用户,供用户后续的处理使用。
    }
    n = n->next;
}
return NULL;    //没找到匹配的节点,返回NULL

}
链表的遍历
使用node = node->next的方式,依次得到各个节点,对各个节点使用handle方法,即实现了链表的遍历。
void list_traverse(List list, void (handle)(void *)) //handle为节点遍历策略,由用户自己编写
{

struct node *p;

p = list->head;
while(p){
    handle(p->data);
    p = p->next;
}

}
链表的搜索
根据用户给点的数据遍历匹配节点,如果找到了,则将该节点的数据域返回给用户;找不到返回NULL。
void list_search(List list, void key, int (compare)(const void , const void )) //以key为搜索关键词,compare为节点数据比较机制,由用户自己编写
{

struct node *n;
n = list->head;

while(n){
    if(!compare(n->data, key)){    //找到了,返回找到的数据
        return n->data;
    }
    n = n->next;    
}

return NULL;    //找不到,返回NULL

}
链表的排序

排序思想:新建一个链表tmp,然后依次取出原链表list中的最小节点,以头插法或者尾插法的机制插入到tmp链表中,直到原链表list为空。然后再把list指向tmp,此时list即为排序好的链表。当然也可以采用选择排序、冒泡排序等其它方式实现。

static struct node find_min_node(List list,

    int (*compare)(const void *, const void *))    //找最小节点,链表排序用;以compare为比较机制,由用户自己编写

{

struct node *min, *n;

n = list->head;
min = list->head;

while(n) {
    if(compare(min->data, n->data) > 0) {
        min = n;
    }
    n = n->next;
}
return min;

}

static void delete_node(List list, struct node key) //以节点数据key为关键词,删除匹配的节点,链表排序用;
{

struct node *n;

n = list->head;

if(n == key){
    list->head = n->next;
    return;
}

while(n->next){
    if(n->next == key){
        if(key == list->tail){
            list->tail = n;
        }
        n->next = n->next->next;
        return;
    }
    n = n->next;
}

}

static void insert_node(List list, struct node key)//以节点数据key为关键词,插入匹配的节点,链表排序用;
{

if(list->head == NULL){
    list->head = key;
    list->tail = key;
}else{
    list->tail->next = key;
    list->tail = key;
}

}

void list_sort(List *list,

    int (*compare)(void *, void *))

{

List tmp;
struct node *n;

list_init(&tmp);

while(! is_empty(list)) {
    n = find_min_node(list, compare);
    delete_node(list, n);
    n->next = NULL;
    insert_node(&tmp, n);
}
list->head = tmp.head;
list->tail = tmp.tail;

}
链表逆序
如下图所示:

基本思想:遍历一遍链表,依次处理每个节点的next指针指向;遍历完一遍链表,链表的顺序就倒置过来了。见下列程序实现:
void list_reverse(List *list)
{

struct node *pre = NULL, *next, *p = list->head;

list->tail = list->head;    //tail指向head;第一次head到tail的倒置。
while(p){
    next = p->next;
    if(!next){  //当p->next为最后一个节点时,让head指向p->next;最后一次tail到head的倒置。
        list->head = p;
    }
    //备份当前节点为pre,作为其下一个节点的next(第一个节点为NULL,初始化时已定义);中间部分节点的倒置。
    p->next = pre;
    pre = p;
    p = next;
}

}
求链表长度
由于链表结构中添加了len属性,因此获取链表长度,直接读取len即可。如果链表结构中不实用len属性,则需要遍历一遍链表,统计循环次数。
程序实现:
long get_lenth(List *list)
{

return (list->len);

}
获取链表某节点的数据
遍历链表到第idx个节点,将该节点处的数据返回给用户即可。
程序实现:
void list_get_element(List list, int idx)
{

int i = 0;
struct node *n;
n = list->head;

while(n && i < idx){
    i ++;
    n = n->next;
}

if(n){
    return n->data;
}

return NULL;

}
链表的注销
使用完链表之后,需要销毁链表来释放资源;秉着谁的数据谁负责的原则,需要传递一个函数指针到list_destroy中,用于销毁节点的数据;
void list_destroy(List list, void (destroy)(void *)) //destroy为销毁链表时对节点数据的处理函数,由用户自己编写。传递NULL时表示不做处理
{

list->len = 0;
struct node *n, *tmp;
n = list->head;

while(n){
    tmp = n->next;    //tmp只起一个记录n->next的功能,否则后面把n free掉之后,就找不到n->next了。
    if(destroy){  //传递用户自定义的数据处理函数,为0时不执行
       destroy(n->data);    //使用用户提供的destroy函数来释放用户的数据。
    }
    free(n);    
    n = tmp;  //把n free掉之后,再把tmp给n,相当于把n->next给n,如此循环遍历链表,挨个删除。
}

}
Sample1
简单的功能测试函数,程序无实际意义。

include

include "list.h"

typedef struct test{

int val1;
float val2;

}test_t;

void handle(void *data)
{

test_t *test = (test_t *)data;
printf("val1:%d, val2:%f\n", test->val1, test->val2);

}

int compare_int(const void s1, const void s2)
{

test_t *data1 = (test_t *)s1;
int *data2 =(int *)s2;

return (data1->val1 - *data2);

}

int compare_int_sort(const void s1, const void s2)
{

test_t *data1 = (test_t *)s1;
test_t *data2 = (test_t *)s2;

return (data1->val1 - data2->val1);

}

void print(List *list)
{

printf("list len = %ld\n", list_get_lenth(list));
if(!is_empty(list)){ 
    //test list_reverse
    list_traverse(list, handle);
}
else{
    printf("\tthe list is empty\n");
}

}

int main(void)
{

List list;
list_init(&list);
test_t test1 = {10, 10.5};
test_t test2 = {20, 20.5};
test_t test3 = {30, 30.5};
test_t test4 = {40, 40.5};
test_t test5 = {50, 50.5};

//test list_insert
printf("------insert(_at_tail)----\n");
list_insert(&list, &test1);
list_insert(&list, &test2);
list_insert(&list, &test3);
print(&list);

//test list_delete
printf("------delete----\n");
list_delete(&list, &test1.val1, compare_int);
print(&list);

//test list_insert_at_head
printf("------insert_at_head----\n");
list_insert_at_head(&list, &test4);
print(&list);

//test list_insert_at_index
printf("------insert_at_index(2)----\n");
list_insert_at_index(&list, &test5, 2);
print(&list);

//test list_reverse
printf("------reverse----\n");
list_reverse(&list);
print(&list);

//test list_search
int key = 20;
test_t *ret;
printf("------search----\n");
ret = list_search(&list, &key, compare_int);
printf("%d:%f\n", ret->val1, ret->val2);
key = 50;
ret = list_search(&list, &key, compare_int);
printf("%d:%f\n", ret->val1, ret->val2);

//test list_get_element 
printf("------list_get_element----\n");
ret = list_get_element(&list, 2);
printf("%d:%f\n", ret->val1, ret->val2);
ret = list_get_element(&list, 3);
printf("%d:%f\n", ret->val1, ret->val2);

//test list_sort
printf("-----sort----\n");
list_sort(&list, compare_int_sort);
print(&list);

//test list_destroy
printf("-----destroy----\n");
list_destroy(&list, NULL);

return 0;

}
输出结果如下所示:
------insert(_at_tail)----
list len = 3
val1:10, val2:10.500000
val1:20, val2:20.500000
val1:30, val2:30.500000
------delete----
list len = 2
val1:20, val2:20.500000
val1:30, val2:30.500000
------insert_at_head----
list len = 3
val1:40, val2:40.500000
val1:20, val2:20.500000
val1:30, val2:30.500000
------insert_at_index(2)----
list len = 4
val1:40, val2:40.500000
val1:20, val2:20.500000
val1:50, val2:50.500000
val1:30, val2:30.500000
------reverse----
list len = 4
val1:30, val2:30.500000
val1:50, val2:50.500000
val1:20, val2:20.500000
val1:40, val2:40.500000
------search----
20:20.500000
50:50.500000
------list_get_element----
50:50.500000
20:20.500000
-----sort----
list len = 4
val1:20, val2:20.500000
val1:30, val2:30.500000
val1:40, val2:40.500000
val1:50, val2:50.500000
-----destroy----
获取Sample1源码
Sample2

预计是一个学生信息管理系统,待续.......

后记
通过valgrind这个工具可以检测内存泄漏,ubuntu下使用sudo apt-get install valgrind即可安装;使用方法:valgrind --tool=memcheck ./app
Sample1的检查结果如下所示:
$ valgrind --tool=memcheck ./app
==4298== Memcheck, a memory error detector
==4298== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==4298== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info
==4298== Command: ./app
==4298==
....
....
....
==4298==
==4298== HEAP SUMMARY:
==4298== in use at exit: 0 bytes in 0 blocks
==4298== total heap usage: 5 allocs, 5 frees, 40 bytes allocated
==4298==
==4298== All heap blocks were freed -- no leaks are possible
==4298==

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章