网站icp备案是什么意思,wordpress禁止拖拽,免费的html大作业网站,wordpress视频主题下载双向链表是一种比单向链表更为灵活的数据结构#xff0c;与单向链表相比可以有更多的应用场景#xff0c;本文讨论双向链表的基本概念及实现方法#xff0c;并着重介绍使用GLib的GList实现单向链表的方法及步骤#xff0c;本文给出了多个实际范例源代码#xff0c;旨在帮助… 双向链表是一种比单向链表更为灵活的数据结构与单向链表相比可以有更多的应用场景本文讨论双向链表的基本概念及实现方法并着重介绍使用GLib的GList实现单向链表的方法及步骤本文给出了多个实际范例源代码旨在帮助学习基于GLib编程的读者较快地掌握GList的使用方法本文程序在 ubuntu 20.04 下编译测试完成gcc 版本号 9.4.0本文适合初学者阅读。 1 双向链表及其实现 在文章《单向链表以及如何使用GLib中的GSList实现单向链表》中介绍了单向链表以及基于 GLib 实现单向链表的方法建议阅读本文前先阅读这篇文章 在文章《使用GLib进行C语言编程的实例》中简单介绍了 GLib建议阅读本文前先阅读这篇文章 双向链表(Doubly Linked List)是一种链式数据结构每个节点包含三个主要部分 数据部分存储节点的数据前向指针指向链表中的下一个节点后向指针指向链表中的上一个节点 可以看出和单向链表相比较双向链表多了一个指向前一个节点的指针 双向链表的基本特性 双向性与单向链表不同双向链表允许从两个方向遍历可以从头节点向尾节点遍历也可以从尾节点向头节点遍历动态大小双向链表的大小可以动态增长或缩小不需要提前定义大小节点插入和删除在双向链表中插入和删除节点操作相对简单因为每个节点都有指向前后节点的指针 双向链表的节点结构 struct Node {int data; // 数据部分struct Node *next; // 指向下一个节点的指针struct Node *prev; // 指向前一个节点的指针
};双向链表的基本操作 插入节点可以在链表的开头、结尾或任意位置插入节点删除节点可以删除链表中的任意节点操作相对简单因每个节点都知道其前一个和后一个节点遍历链表可以从头到尾遍历链表(正向遍历)或从尾到头遍历链表(反向遍历) 与单向链表相比双向链表有以下特点 由于数据结构中增加了后向指针使链表可以双向遍历而单向链表仅能单向遍历通过后向指针可以直接访问前一个节点与单向链表相比可以简化节点删除操作的复杂度在插入节点时比单向链表更快捷更灵活与单向链表相比由于增加了后向指针内存开销增加与单向链表相比双向链表需要操作两个指针其操作和维护的复杂度要高一些 总的来说双向链表比单向链表更加灵活适用场景也要多一些。 下面程序是一个简单的双向链表的 C 语言标准库实现dllist-c.c(点击文件名下载源程序) 编译gcc -Wall -g dllist-c.c -o dllist-c 运行./dllist-c 该程序实现了双向链表的插入、删除以及正向遍历 该程序首先建立一个双向链表并在链表中加入 4 个节点数据分别为1、2、3、5然后显示整个链表 在第 3 个节点(数据为 3索引号为 2)的后面插入节点数据为 4然后显示整个链表 将第 3 个节点(数据为 3索引号为 2)删除然后显示整个链表 最后释放整个链表 运行截图
2 GLib 中双向链表结构 GList
GLib API version 2.0 手册 (点击查看手册)GLib API 手册中 GList 部分 (点击查看手册)在 GLib 中双向链表是通过 GList 结构体实现的GList 是一个简单的双向链表结构用于存储各种类型的数据GSList 定义如下struct GList {gpointer data;GList *next;GList *prev;
}data 为双向链表的数据指针可以指向任何类型或结构的数据next 为指向该双向链表当前节点的下一个节点的指针prev 为指向该双向链表当前节点的前一个节点的指针GLib 为双向链表结构 GList 的操作提供了大量的函数本文仅就其中的一部分函数进行简单介绍 添加、插入新节点 g_list_append() 在双向链表的最后添加一个新节点GList *g_slist_append(GList *list, gpointer data)list - 指向双向链表的指针data - 指向添加节点的数据返回指向双向链表的起始指针说明在双向链表的最后添加节点必须要遍历整个链表才能找到链表的尾部这种做法效率很低通常的做法是使用 g_list_prepend() 在链表的起始位置添加节点当所有节点添加完毕后再使用 g_list_reverse() 将整个链表反转 g_list_prepend() 在双向链表的最前面添加一个新节点GList *g_list_prepend(GList *list, gpointer data)list - 指向双向链表的指针data - 指向添加节点的数据返回指向双向链表的指针在双向链表的开头添加一个节点双向链表的指针是肯定会变化的 g_list_insert() 在双向链表的中间插入一个新节点GList *g_list_insert(GList *list, gpointer data, gint position)list - 指向双向链表的指针data - 指向添加节点的数据position - 插入节点的位置如果是负数或者超过了该双向链表的节点的数量新节点将插到双向链表的最后返回该双向链表的起始指针 g_list_insert_before() 在包含指定数据的节点之前插入一个新节点GList *g_list_insert_before(GList *list, GSList *sibling, gpointer data)list - 指向双向链表的指针data - 指向添加节点的数据sibling - 指向一个节点的指针将在这个节点前插入新节点返回该双向链表的起始指针 删除节点 g_list_remove_link() 从双向链表中删除一个节点但并不释放该节点占用的内存GList *g_list_remove_link(GList *list, GList *llink_)list - 指向双向链表的指针llink_ - 指向双向链表中一个节点的指针该节点将被删除返回该双向链表的起始指针该函数并不释放被删除的节点内存被删除的节点的 next 和 prev 指针将指向 NULL所以可以认为被删除的节点变成了一个只有一个节点的新的双向链表 g_list_delete_link() 从双向链表中删除一个节点并释放该节点占用的内存GList *g_list_delete_link(GList *list, GList *link_)list - 指向双向链表的指针link_ - 指向双向链表中一个节点的指针该节点将被删除返回该双向链表的起始指针该函数与 g_list_remove_link() 的唯一区别是该函数在删除节点后释放了被删除节点占用的内存 g_list_remove() 从双向链表中删除指定数据的一个节点如果链表中有指定数据的节点有多个将只删除第一个GList *g_list_remove(GList *list, gconstpointer data)list - 指向双向链表的指针data - 指向要删除节点的数据返回该双向链表的起始指针 g_list_remove_all() 从双向链表中删除指定数据的所有节点GList *g_list_remove_all(GList *list, gconstpointer data)list - 指向双向链表的指针data - 指向要删除节点的数据返回该双向链表的起始指针 遍历链表 g_list_foreach() 遍历双向链表每个节点都会调用一个指定函数void g_list_foreach(GList *list, GFunc func, gpointer user_data)list - 指向双向链表的指针func - 一个指向函数的指针遍历到双向链表的每个节点时都会调用这个函数GFunc 的定义如下 void (* GFunc) (gpointer data, gpointer user_data)GFunc 的定义表明传递给 func 的参数有两个一个是 data - 指向当前节点的节点数据指针另一个就是指向自定义参数 user_data 的指针user_data - 指针指向调用 func 时传递的用户参数 查找节点 g_list_find() 查找链表中包含给定数据的节点GList *g_list_find(GList *list, gconstpointer data)list - 指向双向链表的指针data - 指向要查找节点的数据返回在双向链表中找到的节点的指针如果没有找到相应节点返回 NULL; g_list_index() 获取包含给定数据的节点的位置(从 0 开始)gint g_list_index(GList *list, gconstpointer data)list - 指向双向链表的指针data - 指向要查找节点的数据返回数据为 data 的节点在双向链表中的位置(从 0 开始)如果没找到相应节点则返回 -1 g_list_position() 获取给定节点在链表中的位置(从 0 开始)gint g_list_position(GList *list, GList *llink)list - 指向双向链表的指针llink - 指向双向链表中的一个节点的指针返回 llink 指向的节点在双向链表中的位置(从 0 开始)如果没找到相应节点则返回 -1 释放链表 g_list_free() 释放链表使用的所有内存该函数不会释放节点中动态分配的内存void g_list_free(GList *list)list - 指向双向链表的指针该函数仅释放 GList 占用的内存并不释放双向链表中各个节点动态申请的内存如果链表中有动态申请内存考虑使用 g_list_free_full() 或手动释放内存 g_list_free_full() 释放链表使用的所有内存并对每个节点的数据调用指定的销毁函数void g_list_free_full(GList *list, GDestroyNotify free_func)list - 指向双向链表的指针free_func - 销毁函数对双向链表中的每个节点数据将调用该函数可用于释放节点中动态分配的内存GDestroyNotify 的定义如下 void (* GDestroyNotify) (gpointer data)所以在调用 free_func 时会将指向节点数据的指针传递给该函数 其它 g_list_length() 获取双向链表的长度guint g_list_length(GList *list)list - 指向双向链表的指针返回双向链表中节点的数量。 g_list_last() 获取双向链表的最后一个节点GList *g_list_last(GList *list)list - 指向单向链表的指针返回双向链表的最后一个节点的指针如果双向链表没有节点则返回 NULL g_list_concat() 连接两个双向链表GList *g_list_concat(GList *list1, GList *list2)list1 - 指向第 1 个双向链表的指针list2 - 指向准备连接到第 1 个双向链表后面的双向链表的指针返回连接好的双向链表的指针 g_list_reverse() 反转整个双向链表GList *g_list_reverse(GList *list)list - 指向双向链表的指针返回该双向链表的起始指针
3 如何使用 GList 实现双向链表 文章的一开始有一个使用标准 C 语言函数库的双向链表的实例使用 GLib 的 GList 操作双向链表要容易得多 下面程序是使用 C 语言基于 GLib 实现的双向链表dllist-glib.c(点击文件名下载源程序) 该程序实现的功能与文章开头的程序 dllist-c.c 完全一样但程序看上去要简洁很多我们不妨把源程序列在这里 该程序与文章《单向链表以及如何使用GLib中的GSList实现单向链表》中使用 GLib 实现单向链表的程序非常相似 #include stdio.h
#include glib.hvoid print_node(gpointer data, gpointer user_data) {printf(%d - , GPOINTER_TO_INT(data));
}
void print_list(GList *list) {g_list_foreach(list, print_node, NULL);printf(NULL\n);
}int main() {GList *list NULL;printf(Append 4 nodes, the data are 1, 2, 3, 5.\n);list g_list_append(list, GINT_TO_POINTER(1));list g_list_append(list, GINT_TO_POINTER(2));list g_list_append(list, GINT_TO_POINTER(3));list g_list_append(list, GINT_TO_POINTER(5));print_list(list);printf(Insert a new node after node with the data 3.\n);list g_list_insert(list, GINT_TO_POINTER(4), 3);print_list(list);printf(Remove node with the data 3.\n);list g_list_remove(list, GINT_TO_POINTER(3));print_list(list);// Free the listg_list_free(list);return 0;
}该程序中涉及到的两个宏GINT_TO_POINTER(value) 和 GPOINTER_TO_INT(p)在文章《单向链表以及如何使用GLib中的GSList实现单向链表》中有比较详细的介绍 编译 gcc -Wall -g dllist-glib.c -o dllist-glib pkg-config --cflags --libs glib-2.0其中pkg-config --cflags --libs glib-2.0 的含义在文章《使用GLib进行C语言编程的实例》中做过介绍 运行./dllist-glib 该程序实现了双向链表的插入、删除、遍历 print_list() 中使用 g_list_foreach() 对链表进行遍历对链表中的每个节点数据将调用函数 print_node() 运行截图
4 双向链表的应用场景
双向链表是一种数据结构它的每个节点包含对前一个节点和后一个节点的引用这种结构在许多应用场景中非常有用以下是一些常见的应用场景 浏览器历史记录 双向链表可以用来实现浏览器的“后退”和“前进”按钮用户可以在历史记录中前后移动当前指针 音乐播放器 在音乐播放器中双向链表可以用于管理播放列表允许用户在歌曲之间前后切换 文本编辑器 在实现撤销和重做功能时双向链表可用于存储编辑历史方便在不同操作间切换 LRU缓存 在实现最近最少使用(LRU)缓存时双向链表可以高效地维护访问顺序以便快速找到和删除最少使用的项 操作系统中的进程调度 在某些调度算法中双向链表可用于管理就绪队列使得进程可以方便地添加和移除 图形界面中的组件布局 在某些图形用户界面(GUI)框架中双向链表用于管理组件的顺序和关系使得组件之间的插入和删除变得灵活 实现栈和队列 双向链表可以作为基础结构来实现栈和队列提供灵活的插入和删除操作。
5 基于 GLib 的 GList 模拟终端命令的历史记录 当我们在 Linux 终端上输入命令时终端应用程序会记录你输入的命令并形成历史记录可以使用 history 命令来查看这个历史记录 在终端上也可以使用上、下箭头键来翻看曾经输入过的前一个或者后一个历史命令这个命令历史记录给使用终端带来了一定的便利 本实例模拟了终端输入命令并使用双向链表生成命令的历史记录按上下箭头键可以查看上一条或下一条命令 源程序 cmd-history.c(点击文件名下载源程序) 基于 GLib 的 GList 模拟了终端历史记录 该程序首先建立了一个双向链表队列然后模拟输入命令链表中的每个节点存储一条命令命令输入完成后显示最后一条命令然后按上下箭头键可以从链表中取出上一条命令或者下一条命令并显示在屏幕上 很显然使用单向链表实现命令历史记录是不方便的但使用双向链表就很方便 编译 gcc -Wall -g cmd-history.c -o cmd-history pkg-config --cflags --libs glib-2.0其中pkg-config --cflags --libs glib-2.0 的含义在文章《使用GLib进行C语言编程的实例》中做过介绍 运行./cmd-history 运行截图 该程序涉及到终端的操作使用了结构 struct termios、函数 tcgetattr() 和 tcsetattr()这些并不在 C 标准库 libc 中需要启用 GNU 扩展库所以在程序的开始有 #define _GNU_SOURCE 有关终端操作的相关数据结构、宏定义以及相关函数并不在本文的讨论之内请自行参考其它资料 该程序中还涉及到了使用 ESC 转义符对终端屏幕进行清屏操作有关 ESC 转义符的含义请参考另一篇文章《ANSI的ESC转义序列》 该程序中还涉及到了从键盘缓冲区读取上、下箭头键的方法上箭头键返回的编码为 ESC [ A下箭头键返回的编码为 ESC [ B这里说明一下有助于读者更快地读懂程序。 email: hengch163.com
