C实现通用数据结构--单链表

单链表概述

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。

从概念上讲，可以把链表想象成一系列连续的元素，然而，由于这些元素是动态分配的（C语言中使用malloc），切记这些元素通常实际上都是分散在内存空间的

欢迎关注我的个人博客：www.wuyudong.com, 更多精彩文章与您分享

单链表的接口定义：

1、list_init

void list_init(List *list, void (*destroy)(void *data));

返回值   void

描述    初始化由参数list指定的链表，该函数必须在链表做其他操作之前调用，当调用list_destroy时，destroy参数提供了一种释放动态分配数据的方法。如果链表采用malloc动态分配的数据，destroy应该设置为free来释放这些数据

复杂度   O(1)


2、list_destroy

void list_destroy(List *list);

返回值   void

描述    销毁由参数list指定的链表，调用该函数以后任何函数都不能再执行，除非重新执行list_init函数。list_destroy将list中的所有元素都移除，每移除一个元素都会调用此函数

复杂度   O(n)  n为链表元素的个数


3、list_ins_next

int list_ins_next(List *list, ListElmt *element, const void *data);

返回值   如果插入元素成功返回0，否则返回-1

描述    在指定的list的element元素后面插入一个元素，如果element为NULL，则在链表的头部插入新的元素，该元素包含一个指向data的指针

复杂度   O(1)  


 4、list_rem_next

int list_rem_next(List *list, ListElmt *element, void **data);

返回值    如果移除元素成功返回0，否则返回-1

描述    移除在指定的list的element后面的那个元素，如果element为NULL，则移除链表的头元素，调用返回后，data指向已经移除元素的数据

复杂度   O(1)  


5、list_size

int list_size(const List *list);

返回值    如果list中元素的个数

描述    这是一个宏，用来计算指定list中元素的个数

复杂度   O(1)  


 6、list_head

ListElmt *list_head(const List *list);

返回值    指向链表头元素的指针

描述    这是一个宏，返回由参数list指定的链表头元素的指针

复杂度   O(1)  


 7、list_tail

ListElmt *list_tail(const List *list) ((list)->tail);

返回值    指向链表尾元素的指针

描述    这是一个宏，返回由参数list指定的链表尾元素的指针

复杂度   O(1)  


 8、list_is_head

int list_is_head(const ListElmt *element);

返回值    如果element元素是链表头元素返回1，否则返回-1

描述    这是一个宏，用来判断element元素是否是list的头元素

复杂度   O(1)   


 9、list_is_tail

int list_is_tail(const ListElmt *element);

返回值    如果element元素是链表尾元素返回1，否则返回-1

描述    这是一个宏，用来判断element元素是否是list的尾元素

复杂度   O(1)   


10、list_data

void *list_data(const ListElmt *element);

返回值    结点中保存的数据

描述    这是一个宏，返回由element元素中保存的数据

复杂度   O(1)    


11、list_next

ListElmt *list_next(const ListElmt *element) ;

返回值    返回element所指定结点的下一个结点

描述    这是一个宏，返回链表中element所指定结点的下一个结点

复杂度   O(1)    

单链表的实现和分析

抽象数据类型的头文件（list.h）：

#ifndef LIST_H
#define LIST_H
#include <stdlib.h>
//为单链表的结点定义一个结构体.
typedef struct ListElmt_ {
    void               *data;   //数据域
    struct ListElmt_   *next;    //指针域

} ListElmt;

//为单链表定义一个结构体.
typedef struct List_ {
    int                size;     //容量
    int                (*match)(const void *key1, const void *key2);    //匹配函数
    void               (*destroy)(void *data);    //撤销操作
    ListElmt           *head;   //头指针
    ListElmt           *tail;   //尾指针

} List;

//公共接口
void list_init(List *list, void (*destroy)(void *data));

void list_destroy(List *list);

int list_ins_next(List *list, ListElmt *element, const void *data);

int list_rem_next(List *list, ListElmt *element, void **data);

#define list_size(list) ((list)->size)

#define list_head(list) ((list)->head)

#define list_tail(list) ((list)->tail)

#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)

#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)

#define list_data(element) ((element)->data)

#define list_next(element) ((element)->next)

#endif

初始化单链表：

void list_init(List *list, void (*destroy)(void *data)) {  //初始化list
    list->size = 0;
    list->destroy = destroy;   //设置为定义的析构函数
    list->head = NULL;
    list->tail = NULL;
    return;
}

回收单链表：

void list_destroy(List *list) {
//移除每一个元素
    while (list_size(list) > 0) {
           if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) {  //不断地移除链表的头结点
                  list->destroy(data);  //调用一个用户定义的函数来释放动态分配的数据.
           }
    }
    //现在没有操作了,释放结构体作为预防措施
    memset(list, 0, sizeof(List));
    return;
}

插入新节点作为指定结点的直接后继结点:

int list_ins_next(List *list, ListElmt *element, const void *data) {
    ListElmt *new_element;     //为结点动态分配存储空间
    if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)  //假如分配失败
          return -1;
    // 将元素插入链表
    new_element->data = (void *)data;
    if (element == NULL) {
        //插入到链表的头部
        if (list_size(list) == 0)
            list->tail = new_element;
        new_element->next = list->head;
        list->head = new_element;
    } else {
        //插入到除了链表头部以外指定的其他地方
        if (element->next == NULL)
            list->tail = new_element;
        new_element->next = element->next;
        element->next = new_element;
    }
    list->size++; //表长增加
    return 0;
}

删除指定结点的直接后继结点:

int list_rem_next(List *list, ListElmt *element, void **data) {
    ListElmt *old_element;
    //不允许从一个空的list中移除元素.
    if (list_size(list) == 0)
        return -1;
    // 从list中移除元素.
    if (element == NULL) {
        // 移除表头的结点.
           *data = list->head->data;
        old_element = list->head;
        list->head = list->head->next;
        if (list_size(list) == 1)   //如果list只有一个元素，则直接删除尾结点
            list->tail = NULL;
    } else {
        // 移除非头结点.
        if (element->next == NULL)
            return -1;
        *data = element->next->data;
        old_element = element->next;
        element->next = element->next->next;
        if (element->next == NULL)  //移除指定结点后，后继为NULL，则用尾结点指向
            list->tail = element;
    }
    //释放分配的抽象数据类型.
    free(old_element);
    //调整list的长度.           *
    list->size--;
    return 0;
}

注意：list_size、list_head、list_tail、list_is_head、list_is_tail、list_data、
list_next 这些宏实现了链表中的一些简单操作，它们提供了快速访问和检测结构体成员的能力。这些操作的时间复杂度都是O(1)

完整的测试代码如下：

// Completed on 2014.10.22 21:00
// Language: C99
//
// 版权所有（C）codingwu   (mail: oskernel@126.com)
// 博客地址：http://www.cnblogs.com/archimedes/
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

static void print_list(const List *list) {
    ListElmt *element;
    int *data, i;
    fprintf(stdout, "List size is %d\n", list_size(list));
    i = 0;
    element = list_head(list);
    while (1) {
        data = list_data(element);
        fprintf(stdout, "list[%03d]=%03d\n", i, *data);
        i++;
        if (list_is_tail(element))
            break;
        else
            element = list_next(element);
    }
    return;
}

int main(int argc, char **argv) {

    List list;
    ListElmt *element;
    int *data, i;

    //初始化list
    list_init(&list, free);
    element = list_head(&list);
    for (i = 10; i > 0; i--) {
        if ((data = (int *)malloc(sizeof(int))) == NULL)
            return 1;
        *data = i;
        if (list_ins_next(&list, NULL, data) != 0)  //逐个插入元素
            return 1;

    }
    print_list(&list);    //打印初始list
    element = list_head(&list);  //指向头结点
    for (i = 0; i < 7; i++)
        element = list_next(element);

    data = list_data(element);
    fprintf(stdout, "Removing an element after the one containing %03d\n", *data);

    if (list_rem_next(&list, element, (void **)&data) != 0)  //删除指定结点
        return 1;
    print_list(&list);
    fprintf(stdout, "Inserting 011 at the tail of the list\n");
    *data = 11;
    if (list_ins_next(&list, list_tail(&list), data) != 0)   //插入指定结点
        return 1;
    print_list(&list);
    fprintf(stdout, "Removing an element after the first element\n");

    element = list_head(&list);
    if (list_rem_next(&list, element, (void **)&data) != 0)
       return 1;

    print_list(&list);

    fprintf(stdout, "Inserting 012 at the head of the list\n");

    *data = 12;
    if (list_ins_next(&list, NULL, data) != 0)
        return 1;

    print_list(&list);

    fprintf(stdout, "Iterating and removing the fourth element\n");

    element = list_head(&list);
    element = list_next(element);
    element = list_next(element);

    if (list_rem_next(&list, element, (void **)&data) != 0)
        return 1;

    print_list(&list);

    fprintf(stdout, "Inserting 013 after the first element\n");

    *data = 13;
    if (list_ins_next(&list, list_head(&list), data) != 0)
        return 1;

    print_list(&list);

    i = list_is_head(&list, list_head(&list));
    fprintf(stdout, "Testing list_is_head...Value=%d (1=OK)\n", i);
    i = list_is_head(&list, list_tail(&list));
    fprintf(stdout, "Testing list_is_head...Value=%d (0=OK)\n", i);
    i = list_is_tail(list_tail(&list));
    fprintf(stdout, "Testing list_is_tail...Value=%d (1=OK)\n", i);
    i = list_is_tail(list_head(&list));
    fprintf(stdout, "Testing list_is_tail...Value=%d (0=OK)\n", i);

    fprintf(stdout, "Destroying the list\n");
    list_destroy(&list);
    return 0;

}
时间： 2024-09-19 09:24:35

C实现通用数据结构--单链表的相关文章

数据结构 单链表-求大神给我讲讲数据结构单链表和队列

问题描述 求大神给我讲讲数据结构单链表和队列 帮我彻底分析下两种结构,感激不尽多谢大神了 解决方案 单链表和队列是两个层次的事情. 单链表是一种基本的表示一个线性表的方式,它记录下当前节点的数据和指向下一个节点的指针.因此一环一环可以得到整个数据.除了单链表,我们还有数组.双向链表.循环链表等. 队列是一种先进先出的数据结构,它高于链表一个层次,这是说,你可以用链表实现队列(当然也可以用数组或者别的).另外还有先进后出的数据结构(堆栈)等. 解决方案二: 具体你可以google下wikipedi

插入删除-数据结构单链表的插入与删除

问题描述 数据结构单链表的插入与删除 设单链表某一节点为p,怎样在p节点前插入一个结点?怎样删除p节点自身?(要求:用Java语言写出具体程序语言) 解决方案 这个主要是定位问题,只要能定到节点p的位置就好. List list = new LinkedList(); list.add(list.indexOf(p), "插入内容");//由于是链表结构,所以数据插入位置的后方下标自动后移 list.remove(list.indexOf(p));//删除p节点 就是这个思路,不知道对

浅谈PHP链表数据结构(单链表)_php实例

链表:是一个有序的列表,但是它在内存中是分散存储的,使用链表可以解决类似约瑟夫问题,排序问题,搜索问题,广义表 单向链表,双向链表,环形链表 PHP的底层是C,当一个程序运行时,内存分成五个区(堆区,栈区,全局区,常量区,代码区) 规定:基本数据类型,一般放在栈区 复合数据类型,比如对象,放在堆区 定义一个类Hero 定义成员属性排名 $no 定义成员属性姓名 $name 定义成员属性昵称 $nickname 定义成员属性 $next,是一个引用,指向下一个Hero对象 定义构造函数,传递参数:

用java学习数据结构--单链表

数据|数据结构 /* * Created on 2004-9-10 * * 单链表中的结点类型声明. */package org.arliang;/** * @author 李梁 * * 单链表中的结点. */public class node{ private int data; //存放数据 private node link; //链接的下一个接点. public static void main(String[]args) { } /** * @return Returns the da

数据结构 单链表-帮我看看下面的程序哪里出错了，刚从数据结构学的单链表，运行不了

问题描述 帮我看看下面的程序哪里出错了,刚从数据结构学的单链表,运行不了 就简单的取值 插入 删除 合并 #include #include #include typedef struct LNode { int num; struct LNode *next; }LNode,*LinkList; void InitiList(LinkList L) { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; } void LocateElem(Link

数据结构 单链表-单链表的连接..数据结构..帮忙看一下。第一个表出来正确，但第二个练上去是一窜数字

问题描述 单链表的连接..数据结构..帮忙看一下.第一个表出来正确,但第二个练上去是一窜数字 #include #include using namespace std; typedef struct node { char data; node *next; }Node; int init(Node *&L) { L=(Node *)malloc(sizeof(Node)); L->next=NULL; return 0; } int crete(Node *&L,int a[],

C语言数据结构单链表之温故而知新

抛弃繁杂的定义,以实用,实战的角度来学习数据结构,这将使得数据结构的学习非常的简单. 前面已经学习了单链表的创建操作:http://blog.csdn.net/morixinguan/article/details/68951912 这节,将单链表温习的笔记共享出来,然后写一个例子,以防自己忘记. 1.单链表的数据结构的定义: 创建节点函数原型可定义如下: struct list *create_node(int data) ; 如何创建单链表的节点,主要分以下步骤: (1)给当前的每个节点的数

asp.net C#数据结构 单链表LinkList

继续发数据结构系列-今天是单链表. 类图: 接口的代码不重复发了  代码如下 复制代码 public class Node<T> {     private T _Data;     private Node<T> _Next;     public T Data     {         get { return _Data; }         set { _Data = value; }     }         public Node<T> Next    

数据结构 单链表-设计算法在带头结点的单链表L中删除数据值最小的结点

问题描述 设计算法在带头结点的单链表L中删除数据值最小的结点 //单链表类型定义如下: typedef struct node { int data; struct node *next; } ListNode; typedef ListNode *LinkList; //设计算法在带头结点的单链表L中删除数据值最小的结点(设链表中各结点数据值 均不相同).函数的原型为:void f34(LinkList L)