数据结构 链表_双向链表的接口定义
2018-06-18 03:56:38来源：未知 阅读 ()
双向链表介绍
双向链表中的每一个元素都由3部分组成：除了数据成员、next指针外，每个元素还包含一个指向其前驱元素的指针，称为prev指针。双向链表的组成是这样的：将一些元素链接在一起，使得每个元素的next指针都指向其后继的元素，而每个元素的prev指针都指向其前驱元素。
为了标识链表的头和尾，将第一个元素的prev指针和最后一个元素的next指针设置为NULL。
要反向遍历整个双向链表，使用prev指针以从尾到头的顺序连续访问各个元素。当我们知道某个元素存储在链表在的某处时，我们可以选择按何种方式访问到它，这会非常有帮助。例如，双向链表的一种灵活性在于它提供了一种比单链表更直观的方式移除一个元素。
双向链表接口定义
| dlist_init |
| void dlist_init(DList *list, void(*destroy)(void *data)); |
| 返回值：无 |
| 描述：初始化由list所指向的双向链表。该函数必须在双向链表做其他任何操作之前调用。当调用dlist_destroy时，这里传入的destroy参数提供了一种释放动态分配空间的方法。它的工作方式如同单链表中的list_destroy。对于双向链表，如果其中包含不需要手动释放空间的数据，destroy参数应该设置为NULL。 |
| 复杂度：O(n) |
| dlist_destroy |
| void dlist_destroy(DList *list); |
| 返回值：无 |
| 描述：销毁由参数list所指定的双向链表。调用该函数后不允许再执行其他操作，除非用户再次调用dlist_init。dlist_destroy将移除链表中的所有元素，如果传给dlist_init的参数destroy不为NULL，则调用destroy所指定的函数，对链表中每个移除的元素数据施行资源回收操作。 |
| 复杂度：O(n)，这里n代表双向链表中的元素个数。 |
| dlist_ins_next |
| int dlist_ins_next(DList *list, DLIstElmt *element,const void *data) |
| 返回值：如果插入成功则返回1，否则返回-1。 |
| 描述：将元素插入由list指定的双向链表的element元素之后
。当插入空链表中时，element可能指向任何位置，为了避免混淆，element此时应该设置为NULL。新的元素包含一个指向data的指针，因此只要该元素仍在链表中，data所引用的内存空间就应该保持合法。
由调用者负责管理data所引用的存储空间。 |
| 复杂度：O(1) |
| dlist_ins_prev |
| int dlist_ins_prev(DList *list, DLIstElmt *element,const void *data) |
| 返回值：无 |
| 描述：将元素插入由list指定的双向链表的element元素之前
。当插入空链表中时，element可能指向任何位置，为了避免混淆，element此时应该设置为NULL。新的元素包含一个指向data的指针，因此只要该元素仍在链表中，data所引用的内存空间就应该保持合法。
由调用者负责管理data所引用的存储空间。 |
| 复杂度：O(1) |
| dlist_remove |
| int dlist_remove(DList *list, DLIstElmt *element,const void *data) |
| 返回值：如果移除成功则返回0，否则返回-1。 |
| 描述：从由list指定的双向链表中移除由element所指定的元素。函数返回后，参数data将指向已移除元素中存储的数据域。由调用者负责管理data所引用的存储空间。 |
| 复杂度：O(1) |
| dlist_size |
| intdlist_size(DList *list) |
| 返回值：链表中的元素个数 。 |
| 描述：这是一个宏，用来计算由list所指定的双向链表中的元素个数。 |
| 复杂度：O(1) |
| dlist_head |
| DListElmt *dlist_head(const DList *list) |
| 返回值：返回链表的头元素。 |
| 描述：这是一个宏，用来返回由list所指定的双向链表中的头元素。 |
| 复杂度：O(1) |
| dlist_tail |
| DListElmt *dlist_tail(const DList *list) |
| 返回值：返回链表的尾元素。 |
| 描述：这是一个宏，用来返回由list所指定的双向链表中的尾元素。 |
| 复杂度：O(1) |
| dlist_is_head |
| int *dlist_is_head(const DListElmt *element) |
| 返回值：如果由参数element所指定的元素是链表头元素则返回1；否则返回0。 |
| 描述：这是一个宏，用来判断由参数element所指定的元素是否为链表头元素。 |
| 复杂度：O(1) |
| dlist_is_tail |
| int *dlist_is_tail(const DListElmt *element) |
| 返回值：如果由参数element所指定的元素是链表尾元素则返回0；否则返回-1。 |
| 描述：这是一个宏，用来判断由参数element所指定的元素是否为链表尾元素。 |
| 复杂度：O(1) |
| dlist_data |
| int *dlist_data(const DListElmt *element) |
| 返回值：返回由element所指定的链表元素的数据域。 |
| 描述：这是一个宏，用来返回由element所指定的双向链表元素的数据域。 |
| 复杂度：O(1) |
| dlist_next |
| DListElmt *dlist_next(const DListElmt *element) |
| 返回值：返回由element所指定的元素的下一个元素。 |
| 描述：这是一个宏，用来返回由element所指定的链表元素的后继元素。 |
| 复杂度：O(1) |
| dlist_prev |
| DListElmt *dlist_prev(const DListElmt *element) |
| 返回值：返回由element所指定的元素的前驱元素。 |
| 描述：这是一个宏，用来返回由element所指定的链表元素的前驱元素。 |
| 复杂度：O(1) |
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：第一周自学总结
下一篇：数据结构 集合_集合的性质
- leetcode 反转链表 2020-06-06
- 数据结构—链表 2020-05-29
- 图 2020-05-02
- STL之list 2020-04-30
- 【数据结构】树套树——线段树套平衡树 2020-04-18
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
