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

2017-11-18 12:50:28来源:cnblogs.com作者:IDreamo人点击

分享

单链表的实现与分析

结构体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),因为访问和检测结构体成员都可以在恒定的时间内完成。

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台