数据结构 链表_单链表的实现与分析

2018-06-18 03:56:50来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

单链表的实现与分析

结构体ListElmt表示链表中的单个元素(见示例1),这个结构体拥有两个成员,就是前面介绍的数据成员和指针成员。

结构体List则表示链表这种数据结构(见示例1)。这个结构由5个成员组成:size表示链表中元素个数;match并不由链表本身使用,而是由链表数据结构派生而来的新类型所使用;destroy是封装之后传递给list_init的析构函数;head是指向链表中头结点元素的指针;tail则是指向链表中末尾结点元素的指针。

示例1:链表抽象数据类型的头文件

    /*list.h*/  
    #ifndef LIST_H  
    #define LIST_H  
      
    #include <stdio.h>  
    /*Define a structure for linked list elements.*/  
    typedef struct ListElmt_  
    {  
        void *data;  
        struct ListElmt_ *next;  
    } ListElmt;  
      
    /*Define a structure for linked lists.*/  
    typedef struct List_  
    {  
        int size;  
        int (*match)(const void *key1,const void *key2);  
        void (*destroy)(void *data);  
        ListElmt *head;  
        ListElmt *tail;  
    } List;  
      
    /*Public Interface*/  
    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 // LIST_H  

 

list_init

list_init用来初始化一个链表以便能够执行其他操作(见示例2)。

初始化链表是一种简单的操作,只要把链表的size成员设置为0,把函数指针成员destroy设置为定义的析构函数,head和tail指针全部设置为NULL即可。

list_init的复杂度为O(1),因为初始化过程中的所有步骤都能在一段恒定的时间内完成。

示例2:链表抽象数据类型的实现

    /*list.c*/  
    #include <stdio.h>  
    #include <string.h>  
      
    #include "lish.h"  
      
    /*list_init*/  
    void list_init(List *list,void(*destroy)(void *data))  
    {  
        list->size = 0;  
        list->destroy = destroy;  
        list->head = NULL;  
        list->tail = NULL;  
      
        return;  
    }  
      
    /*list_destroy*/  
    void list_destroy(List *list)  
    {  
        void *data;  
        /*Remove each element*/  
        while(list_size(list)>0)  
        {  
            if(list_rem_next(list,NULL,(void **)&data)==0 && list->destroy!=NULL)  
            {  
                /*Call a user-defined function to free dynamically allocated data.*/  
                list->destroy(data);  
            }  
        }  
        memset(list,0,sizeof(list));  
        return;  
    }  
      
    /*list_ins_next*/  
    int list_ins_next(List *list,ListElmt *element,const void *data)  
    {  
        ListElmt *new_element;  
          
        /*Allocate storage for the element*/  
        if((new_element=(ListElmt *)malloc(sizeof(ListElmt)))==NULL)  
            return -1;  
        /*insert the element into the list*/  
        new_element->data=(void *)data;  
        if(element == NULL)  
        {  
            /*Handle insertion at the head of the list. */  
            if(list_size(list)==0)  
                list_tail = new_element;  
                  
            new_element->next = list->head;  
            list->head = new_element  
        }  
        else   
        {  
            /*Handle insertion somewhere other than at the head*/  
            if(element->next==NULL)  
                list->tail = new_element;  
              
            new_element->next = element->next;  
            element->next = new_element;  
        }  
        /*Adjust the size of the list of account for the inserted element. */  
        list->size++;  
          
        return 0;  
    }  
      
    /*list_rem_next*/  
    int list_rem_next(List *list,ListElmt *element,void **data)  
    {  
        ListElmt *old_element;  
          
        /*Do not allow removal from an empty list. */  
        if(list_size(list) == 0)  
            return -1;  
          
        /*Remove the element from the list. */  
        if(element == NULL)  
        {  
            /*Handle removal from the head of the list. */  
            *data = list->head->data;  
            old_element = list->head;  
            list->head = list->head->next;  
              
            if(list_size(list) == 1)  
                list->tail = NULL;  
        }  
        else   
        {  
            /*Handle removal from somewhere other than the head. */  
            if(element->next == NULL)  
                return -1;  
              
            *data = element->next->data;  
            old_element = element->next;  
            element->next = element->next->next;  
              
            if(element->next == NULL)  
                list->tail = element;  
        }  
        /*Free the storage allocated by the abstract datatype.*/  
        free(old_element);  
        /*Adjust the size of the list account for the removed element. */  
        list->size--;  
        return 0;  
    }  

 

list_destroy

list_destroy用来销毁链表(见示例2),其意义就是移除链表中的所有的元素。

如果调用list_init时destroy参数不为NULL,则当每个元素被移除时都将调用list_destroy一次。

list_destroy的运行时复杂度为O(n),n代表链表中的元素个数,这是因为list_rem_next的复杂度为O,而移除每个元素时都将调用list_rem_next一次。

list_ins_next

list_ins_next将一个元素插入由element参数所指定的元素之后(见示例2)。该调用将新元素的数据指向由用户传递进来的数据。向链表中插入新元素的处理步骤很简单,但需要特别小心。有两种情况需要考虑:插入链表头部和插入其他位置。

一般来说,要把一个元素插入链表中,需要将新元素的next指针指向它之后的那个元素,然后将新元素位置之前的结点next指针指向新插入的元素(见图3)。但是,当从链表头部插入时,新元素之前没有别的结点了。因此在这种情况下,将新元素的next指针指向链表的头部,然后重置头结点指针,使其指向新元素。回顾一下前面接口设计,当传入element为null时代表新的元素将插入链表头部。另外需要注意的是,无论何时当插入的元素位于链表末尾时,都必须重置链表数据结构的tail成员使其指向新的结点。最后,更新统计链表中结点个数的size成员。


list_rem_next

list_rem_next从链表中移除由element所指定的元素之后的那个结点(见示例2)。移除的是element之后的那个结点而不是移除element本身。这个调用也需要考虑两个因素,移除的是头结点以及移除其余位置上的结点。

移除操作是很简单的,但同样需要注意一些细节问题(见图4)。一般来说,从链表中移除一个元素,需要将移除的目标结点前一个元素的next结点指针指向目标结点的下一个元素。但是,当移除的目标结点是头指针时,目标结点之前并没有其他元素了。因此,在这种情况下,只需要将链接表的head成员指向目标结点的下一个元素。同插入操作一样,当传入的element为NULL时就代表链表的头结点需要移除。另外,无论何时当移除的目标结点是链表的尾部结点时,都必须更新链表数据结构中的tail成员,使其指向新的尾结点,或者当移除操作使得整个链表为空链表时,需要把tail设置为NULL。最后,更新链表的size成员,使其减1。当这个调用返回时,data将指向已经移除结点的数据域。


list_rem_next的复杂度为O(1),因为所有的移除步骤都在恒定的时间内完成。

list_size、list_head、list_tail、list_is_tail、list_data以及list_next

这些宏实现了一些链表中的一些简单操作(见示例1)。一般来说,它们提供了快速访问和检测List和ListElmt结构体中成员的能力。

这些操作的复杂度都是O(1),因为访问和检测结构体成员都可以在恒定的时间内完成。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C语言可以分配的最大内存

下一篇:数据结构 链表_单链表的接口定义