下载文档原格式
数据结构在现实生活中的应用数据结构在现实生活中的应用⒈序言本文档旨在介绍数据结构在现实生活中的应用。
数据结构是计算机科学中非常重要的概念之一，它提供了存储和组织数据的方式和方法。
虽然数据结构通常与计算机程序相关联，但它们也在我们的日常生活中起到重要作用。
⒉数组(Array)的应用⑴数据存储：数组被广泛用于存储和管理数据。
例如，我们可以使用数组来存储学生的成绩、员工的工资等信息。
⑵图像处理：图像可以由像素数组组成。
通过操作数组中的元素，我们可以对图像进行处理，例如修改亮度、调整对比度等。
⑶数学模型：数组可以用于表示和处理数学模型。
例如，我们可以使用数组来存储和计算矩阵。
⒊链表(Linked List)的应用⑴链表结构：链表结构在许多现实生活中的情况下很有用。
例如，我们可以使用链表来表示地铁线路，每个节点表示一个站点，节点之间的表示站点之间的连接。
⑵数据处理：链表可以用于处理大量的数据。
它们允许动态的插入和删除操作，这在某些情况下是很有用的。
例如，在社交网络中，我们可以使用链表来存储和管理用户之间的关系。
⒋栈(Stack)和队列(Queue)的应用⑴符号匹配：使用栈可以判断括号是否匹配。
在编译器和解释器中，栈被广泛用于处理符号匹配问题。
⑵计算表达式：栈可以用于计算中缀表达式和后缀表达式。
它们还可以用于实现逆波兰表达式和算术表达式的求值。
⑶进程调度：队列可以用于进程调度。
操作系统使用队列来管理进程，并按照一定的策略对它们进行分配和执行。
⒌树(Tree)的应用⑴文件系统：文件系统通常使用树的结构来组织和管理文件和目录。
每个节点表示一个文件或目录，节点之间的表示它们之间的层次关系。
⑵数据搜索：二叉搜索树是一种常用的数据结构，用于高效地搜索和插入数据。
它们广泛用于数据库和搜索引擎中。
⑶组织结构：树可以用于表示组织结构。
例如，一家公司的组织架构可以被表示为一个树，根节点表示公司，子节点表示部门和员工。
⒍图(Graph)的应用⑴网络路由：图可以用于网络路由算法。
数据结构经典案例在计算机科学领域，数据结构是组织和存储数据的方式，以便能够高效地访问、操作和管理数据。
数据结构的选择对于算法的性能和程序的效率有着至关重要的影响。
下面将为您介绍几个数据结构的经典案例。
一、栈（Stack）栈是一种遵循“后进先出”（Last In First Out，LIFO）原则的数据结构。
想象一下一叠盘子，最后放上去的盘子总是最先被拿走，栈就是这样的工作原理。
一个常见的栈的应用是表达式求值。
比如我们要计算数学表达式“3 ＋ 4 2”。
首先，将数字和运算符依次压入栈中。
当遇到运算符时，从栈中弹出相应数量的操作数进行计算，然后将结果压回栈中。
通过这种方式，能够按照正确的运算顺序得出最终的结果。
在编程语言中，函数调用也用到了栈。
当一个函数被调用时，其相关的信息（如参数、返回地址等）被压入栈中。
当函数执行完毕后，这些信息被弹出，程序回到之前的执行点继续执行。
二、队列（Queue）队列遵循“先进先出”（First In First Out，FIFO）原则。
就像排队买东西，先排队的人先得到服务。
在操作系统中，打印任务通常使用队列来管理。
多个打印任务按照提交的先后顺序排列在队列中，打印机依次处理队列中的任务。
另外，在消息传递系统中，队列也被广泛应用。
发送方将消息放入队列，接收方从队列中取出消息进行处理。
三、链表（Linked List）链表是一种动态的数据结构，其中的元素通过指针连接在一起。
在需要频繁进行插入和删除操作的场景中，链表表现出色。
比如，在一个学生管理系统中，如果需要不断地添加或删除学生信息，使用链表可以方便地在任意位置进行操作，而不需要像数组那样移动大量的元素。
四、树（Tree）树是一种分层的数据结构，具有根节点、子节点和叶节点。
二叉搜索树（Binary Search Tree）是一种常见的树结构。
在二叉搜索树中，左子树的所有节点值都小于根节点的值，右子树的所有节点值都大于根节点的值。
认识各种常见数据结构的特点与优缺点数据结构是计算机科学中非常重要的概念，它是指数据元素之间的关系，以及对这些数据元素进行操作的方法。
不同的数据结构适用于不同的场景，每种数据结构都有其独特的特点和优缺点。
本文将介绍几种常见的数据结构，包括数组、链表、栈、队列、树和图，分析它们的特点与优缺点。
1. 数组数组是最基本的数据结构之一，它由相同类型的元素组成，这些元素在内存中是连续存储的。
数组的特点包括：- 支持随机访问：可以通过下标快速访问数组中的任意元素。
- 内存占用连续：由于元素在内存中是连续存储的，因此插入和删除操作可能需要移动大量元素。
- 大小固定：数组的大小在创建时就确定，无法动态扩展。
优点：- 随机访问效率高。
- 实现简单，易于理解。
缺点：- 插入和删除元素效率低。
- 大小固定，无法动态扩展。
2. 链表链表是一种非连续存储的数据结构，它由节点组成，每个节点包含数据和指向下一个节点的指针。
链表的特点包括：- 插入和删除操作高效：在链表中插入和删除元素只需要改变指针指向，不需要移动元素。
- 不支持随机访问：无法通过下标直接访问元素，需要从头节点开始遍历。
优点：- 插入和删除操作高效。
- 可动态扩展，不受固定大小限制。
缺点：- 不支持随机访问，访问效率低。
- 需要额外的指针空间。
3. 栈栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。
栈的特点包括：- 后进先出：最后插入的元素最先删除。
- 限制操作：只能在栈顶进行插入和删除操作。
优点：- 简单易用，操作简单。
- 可用于实现递归算法。
缺点：- 功能受限，只能在栈顶进行操作。
- 不支持随机访问。
队列是一种先进先出（FIFO）的数据结构，只能在队首删除元素，在队尾插入元素。
队列的特点包括：- 先进先出：最先插入的元素最先删除。
- 限制操作：只能在队首删除元素，在队尾插入元素。
优点：- 用于实现广度优先搜索算法。
- 可以保持数据的顺序性。
数据结构在现实生活中的应用数据结构在现实生活中的应用一、介绍数据结构是计算机科学中的一门重要的学科，它研究数据的组织方式、存储方式和操作方式。
在现实生活中，数据结构有着广泛的应用，能够帮助我们有效地解决各种问题。
本文将从多个角度分析数据结构在现实生活中的应用。
二、线性数据结构的应用⒈数组- 在电子商务中，可以使用数组来存储商品的价格、库存等信息。
- 在学绩管理系统中，可以使用数组来存储学生的考试成绩。
⒉链表- 在社交网络中，可以使用链表将用户的朋友关系组织起来，方便查找和更新。
- 在操作系统的任务管理中，可以使用链表来组织进程的执行顺序。
⒊栈- 在计算器中，可以使用栈来实现表达式的计算。
- 在浏览器的前进后退功能中，可以使用栈来记录用户的浏览历史。
⒋队列- 在银行、超市等场景中，可以使用队列来管理顾客的排队顺序。
- 在操作系统的进程调度中，可以使用队列来按照先来先服务的原则分配CPU时间。
三、树型数据结构的应用⒈二叉树- 在文件系统中，可以使用二叉树来组织文件和文件夹的层级关系。
- 在数据库中，可以使用二叉树来优化数据的查找和插入操作。
⒉AVL树- 在自动平衡二叉搜索树中，可以使用AVL树来保持树的平衡，提高查找效率。
- 在日程管理中，可以使用AVL树来按照时间顺序存储和访问日程。
⒊B树- 在数据库中，可以使用B树来存储和索引大量的数据。
- 在文件系统中，可以使用B树来加速文件的读写操作。
四、图的应用⒈最短路径算法- 在地图导航系统中，可以使用最短路径算法来计算所需的最短路径。
- 在网络路由中，可以使用最短路径算法选择数据包的传输路径。
⒉最小树算法- 在电力系统中，可以使用最小树算法来确定电力网的布局，降低成本。
- 在社交网络中，可以使用最小树算法来找到一个社交网络的核心成员。
五、散列数据结构的应用⒈哈希表- 在方式簿中，可以使用哈希表来加速查找某人的方式号码。
- 在数据库中，可以使用哈希表来加速数据的插入和查询。
程序设计中常用的数据结构在程序设计中，数据结构是许多算法和程序的基础。
以下是程序设计中常用的几种数据结构：1. 数组（Array）：数组是一组有序的数据元素，可以通过索引值来访问和修改数组中的元素。
数组的主要优点是支持随机访问，但插入和删除操作的效率相对较低。
2. 栈（Stack）：栈是一种后进先出（LIFO）的数据结构，只能从栈顶插入和删除数据。
栈的主要应用场景包括函数调用、表达式求值和内存分配等。
3. 队列（Queue）：队列是一种先进先出（FIFO）的数据结构，只能从队列尾插入数据并从队列头删除数据。
队列的主要应用场景包括广度优先搜索和任务调度等。
4. 链表（Linked List）：链表是一种递归的数据结构，由若干个节点组成，每个节点包含当前元素的值和指向下一个节点的指针。
链表支持快速插入和删除操作，但访问特定位置的元素需要顺序查找，效率相对较低。
5. 哈希表（Hash Table）：哈希表是一种基于哈希函数实现的数据结构，可以快速地插入、删除和查找元素。
在哈希表中，元素的存储位置是通过哈希函数计算得到的，因此访问特定位置的元素效率很高。
6. 树（Tree）：树是一种层次结构，由若干个节点和连接这些节点的边组成。
常见的树形数据结构包括二叉搜索树、红黑树、AVL 树和 B 树等。
树的主要应用场景包括搜索、排序和存储等。
7. 图（Graph）：图是由一组节点和连接这些节点的边组成的数据结构。
图常用来表示实体之间的关系，如社交网络、路线图等。
在计算机科学中，图的主要应用包括最短路径算法、网络流等。
8. 堆（Heap）：堆是一种特殊的树形数据结构，它满足某些特定的性质。
被称为“最小堆”的堆中，每个父节点的值都小于或等于其子节点的值，而被称为“最大堆”的堆中，每个父节点的值都大于或等于其子节点的值。
堆可以用来实现优先队列和堆排序等算法。
9. 字典树（Trie）：字典树是一种用于字符串处理的树形数据结构。
数据结构在现实生活中的应用数据结构在现实生活中的应用概述数据结构是计算机科学中重要的基础概念之一，它提供了一种有效地组织和管理数据的方式。
尽管它们最初是为计算机科学设计的，但数据结构的概念和方法在现实生活中也有广泛的应用。
本文将介绍一些常见的现实生活中使用数据结构的例子。
数组数组是最基本的数据结构之一，它是一个连续的、固定大小的存储元素的集合。
在现实生活中，我们经常使用数组来存储和管理一系列相关的数据。
例如，在商店的库存管理中，我们可以使用一个数组来存储每个商品的库存数量。
这样，当我们需要查询某个商品的库存数量时，只需要通过索引访问数组中的元素即可。
另外，数组还可以用于存储成绩在某个考试中的学生列表。
这样，我们可以根据学生的索引快速获取他们的成绩，并进行排序和统计。
链表链表是另一种常用的数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的引用。
链表在现实生活中的应用非常广泛。
一个常见的例子是方式通讯录。
我们可以使用链表来存储联系人的信息。
每个节点表示一个联系人，包含姓名、方式号码等信息，同时还包含指向下一个联系人的引用。
这样，我们可以通过遍历链表，轻松地查找、添加和删除联系人。
链表还可以在火车或地铁系统中使用。
每个节点表示一个站点，包含站点名称和到下一个站点所需的时间。
通过遍历链表，我们可以计算出从起点到终点的最短时间，并提供路线规划服务。
栈栈是一种具有特定的操作规则的数据结构，它遵循后进先出（LIFO）的原则。
在现实生活中，我们可以找到许多适合使用栈的场景。
一个典型的例子是浏览器的后退功能。
当我们浏览网页时，每访问一个页面，都将其存储在栈中。
当我们后退按钮时，栈中的顶部元素会被弹出，我们就可以返回到上一个页面。
另一个例子是函数调用的堆栈。
每当我们调用一个函数时，函数的信息将被存储在栈中。
当函数执行完毕后，这些信息会被弹出。
这使得函数之间的嵌套调用成为可能。
队列队列是一种遵循先进先出（FIFO）原则的数据结构，它经常被用来在现实生活中模拟排队的场景。
数据结构链表的基本操作一、引言链表是计算机科学中的一种数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
链表可以用于实现栈、队列和其他数据结构。
本文将详细介绍链表的基本操作。
二、链表的基本概念1. 节点：链表中的每个元素称为节点，它包含两部分：数据和指向下一个节点的指针。
2. 头结点：链表中第一个节点称为头结点，它不包含实际数据，只有指向第一个真正节点的指针。
3. 尾节点：链表中最后一个节点称为尾节点，它的指针为空。
4. 空链表：不包含任何元素的链表称为空链表。
三、链表的基本操作1. 创建链表创建一个空链表很简单，只需要让头结点指针为空即可。
如果需要创建带有多个元素的非空链表，则需要依次创建每个节点，并将前一个节点的指针指向当前节点。
2. 插入元素在插入元素时，需要先找到要插入位置前面的那个节点。
然后新建一个要插入的节点，并将其指针指向原来位置上后面那个节点。
最后将前面那个节点的指针改为新建立的节点。
3. 删除元素在删除元素时，需要先找到要删除的那个节点。
然后将前一个节点的指针指向后一个节点，从而跳过要删除的那个节点。
最后释放要删除的节点。
4. 遍历链表遍历链表是指依次访问链表中每个元素。
可以使用循环结构来实现遍历操作。
从头结点开始，依次访问每个节点，并将其数据输出即可。
5. 查找元素查找元素时，需要从头结点开始依次遍历每个节点，直到找到目标元素或者遍历完整个链表为止。
6. 反转链表反转链表是指将原来的链表顺序倒置。
可以使用三个指针分别表示当前节点、前一个节点和后一个节点，依次修改它们之间的指针即可实现反转操作。
四、链表的应用举例1. 栈和队列：栈和队列都可以用链表来实现。
栈是一种先进后出（FILO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。
2. 链式存储文件系统：文件系统中通常采用基于树或者基于哈希表的存储方式。
但是在某些情况下，也可以采用基于链式存储方式来实现文件系统。
多重链表的结构及应用一、概述多重链表是一种特殊的链表结构，每个节点可以有多个指针域，用于指向不同的节点。
它可以用来表示复杂的数据结构，例如树和图等。
在实际应用中，多重链表可以用于实现各种数据结构和算法，例如哈希表、图遍历和拓扑排序等。
二、多重链表的定义多重链表由一个头指针和若干个节点组成。
每个节点包含若干个指针域和一个数据域。
指针域用于指向其他节点，数据域存储节点的数据。
三、多重链表的分类1. 单向多重链表：每个节点只有一个指针域，用于指向下一个节点。
2. 双向多重链表：每个节点有两个指针域，分别用于指向前一个节点和后一个节点。
3. 循环多重链表：最后一个节点的指针域指向第一个节点，形成一个环形结构。
4. 带头结点的多重链表：在头部添加一个空节点作为头结点，方便对链表进行操作。
四、多重链表的应用1. 哈希表：哈希表是一种高效的查找算法，在实现过程中需要使用到多重链表来解决冲突问题。
2. 图遍历：图是一种复杂的数据结构，可以用多重链表来表示。
在进行图遍历时，需要使用到深度优先搜索和广度优先搜索算法，这两种算法都需要使用到多重链表来存储节点信息。
3. 拓扑排序：拓扑排序是一种有向无环图的排序算法，在实现过程中需要使用到多重链表来存储节点信息。
4. 文件系统：文件系统是一种树形结构，可以用多重链表来表示。
在实现过程中，需要使用到双向多重链表来维护文件的父子关系和兄弟关系。
5. 文本编辑器：文本编辑器是一种常见的应用程序，可以用多重链表来实现撤销和重做功能。
在实现过程中，需要使用到循环多重链表来维护撤销和重做操作。
五、多重链表的优缺点1. 优点：（1）可以表示复杂的数据结构；（2）方便实现各种算法和数据结构；（3）灵活性高，可以根据需求灵活调整指针域。
2. 缺点：（1）空间复杂度高；（2）访问节点时需要遍历指针域；（3）容易出现指针错误。
六、总结多重链表是一种特殊的链表结构，可以用于表示复杂的数据结构和实现各种算法和数据结构。
数据结构中的常见问题与解决方案数据结构是计算机科学中非常重要的基础知识，它是用来组织和存储数据的一种特殊方式。
在实际的编程过程中，我们经常会遇到各种关于数据结构的问题，如何选择合适的数据结构、如何高效地操作数据结构等等。
本文将介绍数据结构中的一些常见问题，并给出相应的解决方案。
一、数组越界访问数组是一种最基本的数据结构，它由一组连续的内存空间组成，可以存储相同类型的数据。
在使用数组时，经常会出现数组越界访问的问题，即访问数组中不存在的索引位置。
这种错误通常会导致程序崩溃或产生不可预测的结果。
解决方案：1. 在编程过程中，要时刻注意数组的索引范围，避免越界访问。
2. 使用边界检查来确保数组访问的合法性，可以在访问数组元素之前进行索引范围的检查。
3. 在编程语言中，一些工具和库提供了数组越界检查的功能，可以利用这些工具来避免越界访问的问题。
二、链表中的循环引用链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
在使用链表时，可能会出现循环引用的问题，即链表中的某个节点指向了链表中的前面节点，导致链表形成了一个环。
解决方案：1. 使用快慢指针来检测链表中是否存在循环引用，快指针每次移动两步，慢指针每次移动一步，如果两个指针相遇，则说明链表中存在循环引用。
2. 在插入和删除节点时，要注意更新节点之间的指针关系，避免出现循环引用的情况。
3. 可以使用哈希表来存储已经访问过的节点，当遍历链表时，检查当前节点是否已经存在于哈希表中，如果存在则说明存在循环引用。
三、栈和队列的应用栈和队列是两种常见的数据结构，它们分别具有后进先出和先进先出的特性，在实际编程中有着广泛的应用。
在使用栈和队列时，可能会遇到一些问题，如如何实现栈和队列、如何高效地进行操作等。
解决方案：1. 对于栈的实现，可以使用数组或链表来存储数据，通过压栈和出栈操作来实现栈的功能。
在使用数组实现栈时，要注意栈的扩容和缩容操作，以提高效率。
内核中常见的数据结构链表之分析及应用 作为实现Linux内核代码的主体语言C，它是朴素的、直接的，直接到你可以对硬件寄存器的某一位进行操作，C语言又是原始的，基本的，基本的就像构建大厦的一块块砖，运用它，你可以随意地建造自己梦想中的大厦。 但是，与其他语言不同，C语言标准库中并没有对数据结构的支持函数，比如，没有对链表、队、栈、树等数据结构操作的函数集合，但在Linux内核代码中，随处都可以觅见这些数据结构的踪影。 现实世界中数据的组织形式逃脱不出数据结构课程所涵盖的那些结构，相对于其他数据结构而言，链表这种组织方式更常用和灵活，或者说，其他数据结构，都可以从链表衍生而来。 在Linux内核源代码树中，include/linux/list.h 文件中用GNU C语言实现了封装好的、易用的双向链表函数集合，这种实现是高效和可移植的--否则，这些代码也进不了内核，同时，这种实现又是巧妙和可见的，赏析这些代码，让我们领悟内核代码设计之美妙。
1. 链表及衍生 为什么链表是数据组织的根本形式？ 最简单的数组组织形式是数组，它在内存顺序存放，其存取效率无疑是高效的，但除非你存放的数据是静态的，否则，增加和删除一个元素的代价是不可小估的。而链表，在建立之初，无需知晓其节点是多少，在构建过程中，增加和删除一个节点与链表的长度无关，主要开销为访问的顺序性和链表节点所占的空间。 尽管链表可以分类为单链表、双链表和循环链表，但在此，以分析双链表为基点，从而退化或者衍生出其他数据结构。
在C 语言中，一个基本的双向链表定义如下：
struct my_list{ void *mydata; struct my_list *next; struct my_list *prev; };
图2. 1 双链表 图2.1是一双链表，通过前趋（prev）和后继（next）两个指针字段，就可以从两个方向遍历双链表，这使得遍历链表的代价减少。如果打乱前驱、后继的依赖关系，就可以构成"二叉树"；如果再让首节点的前趋指向链表尾节点、尾节点的后继指向首节点（如图1中虚线部分），就构成了循环链表；如果设计更多的指针字段，就可以构成各种复杂的树状数据结构。 如果减少一个指针域，就退化成单链表，如果只能对链表的首尾进行插入或删除操作，就演变为队结构，如果只能对链表的头进行插入或删除操作，就退化为栈结构。 如此看来，双链表，是演化各种数据结构的基石。 2. 链表的实现 抽象是软件设计中一项基本技术，如上所述，在众多数据结构中，选取双向链表作为基本数据结构，这就是一种提取和抽象。 1）简约而又不简单的链表定义 于双向链表而言，内核中定义了如下简单结构： struct list_head { struct list_head *next, *prev; }; 这个不含任何数据项的结构，注定了它的通用性和未来使用的灵活性，例如前面的例子就可以按如下方式定义： struct my_list{ void *mydata; struct list_head list; }; · 在此，进一步说明几点：
list字段，隐藏了链表的指针特性，但正是它，把我们要链接的数据组织成了链表。 · struct list_head可以位于结构的任何位置
· 可以给struct list_head起任何名字。
· 在一个结构中可以有多个list
简约而又不简单的struct list_head，以此为基本对象，就衍生了对链表的插入、删除、合并以及遍历等各种操作： 2）链表的声明和初始化宏 实际上， struct list_head只定义了链表节点，并没有专门定义链表头，那么一个链表结构是如何建立起来的？让我们来看看下面两个宏： #define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
如果我们要申明并定义自己的链表头mylist，直接调用LIST_HEAD： LIST_HEAD(mylist) 则mylist的next、prev指针都初始化为指向自己，这样，我们就有了一个空链表，如何判断链表是否为空，自己写一下这个简单的函数list_empty ，也就是让头指针的next指向自己而已。
3）staitic inline函数－隐藏并展开 在list.h中定义的函数大都是 staitic inline f()形式，为什么这样定义？ 关键字“static”加在函数前，表示这个函数是静态函数，所谓静态函数，实际上是对函数作用域的限制，指该函数的作用域仅局限于本文件。所以说，static具有信息隐藏作用。 而关键字"inline“加在函数前，说明这个函数对编译程序是可见的，也就是说，编译程序在调用这个函数时就立即展开该函数。所以，关键字inline 必须与函数定义体放在一起才能使函数成为内联。inline函数一般放在头文件中。
4） 无处不在的隐藏特性 我们分析一下在链表中增加一个节点的函数实现： 有三个函数： static inline void __list_add(); static inline void list_add(); static inline void list_add_tail(); ------------------------------------------------------------------------------------------------- /* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */ static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { next->prev = new; new->next = next; new->prev = prev; prev->next = new; } -------------------------------------------------------------------------------------------------- /** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */ static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } -------------------------------------------------------------------------------------------------- /** * list_add_tail - add a new entry * @new: new entry to be added * @head: list head to add it before * Insert a new entry before the specified head. * This is useful for implementing queues. */ static inline void list_add_tail(struct list_head *new, struct list_head *head) { __list_add(new, head->prev, head); }
--------------------------------------------------------------------------------------------------
仔细体会其实现代码，看起来简单有效，但实际上也是一种抽象和封装的体现。首先__list_add()函数做基本的操作，该函数仅仅是增加一个节点，至于这个节点加到何处，暂不考虑。list_add（）调用__list_add()这个内部函数，在链表头增加一个节点，实际上实现了栈在头部增加节点的操作，而list_add_tail()在尾部增加一个节点，实际上实现了队的操作。
至于链表的删除、搬移和合并，读者自行分析，不再此一一讨论
3. 遍历链表－似走过千山万水 遍历链表本是简单的，list.h中就定义了如下的宏： -------------------------------------------------------------------------------------------------- ** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop counter. * @head: the head for your list. */ #define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); \ pos = pos->next)
-------------------------------------------------------------------------------------------------- 这种遍历仅仅是找到一个个节点在链表中的偏移位置pos，如图2.2所示。
图2.2 遍历链表 问题在于，如何通过pos获得节点的地址，从而可以使用节点中的数据？ 于是 list.h中定义了晦涩难懂的list_entry（）宏： -------------------------------------------------------------------------------------------------- /** * list_entry - get the struct for this entry
