数据结构强化课程

1、数据结构强化数据结构强化刘建圻刘建圻链表链表v链表链表是一种常用的组织有序数据的数据结构，它通过指针将一系列数据节点连接成一条数据链，是线性表的一种重要实现方式。相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。 v通常链表数据结构至少应包含两个域：数据域和数据域和指针域指针域，数据域用于存储数据，指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式，链表又可以分为单链表、单链表、双链表、循环链表双链表、循环链表等多种类型。 单链表单链表 v

2、 单链表是最简单的一类链表，它的特点是仅有一个指针域单链表是最简单的一类链表，它的特点是仅有一个指针域指向后继节点（指向后继节点（next），因此，对单链表的遍历只能从），因此，对单链表的遍历只能从头至尾（通常是头至尾（通常是NULL空指针）顺序进行。空指针）顺序进行。 双链表双链表 、循环链表、循环链表v 通过设计前驱和后继两个指针域，双链表可以从两个方向通过设计前驱和后继两个指针域，双链表可以从两个方向遍历，构成了双链表。遍历，构成了双链表。v 让首节点的前驱指向链表尾节点、尾节点的后继指向首节让首节点的前驱指向链表尾节点、尾节点的后继指向首节点（虚线部分），构成了循环链表。特点是从任意一

3、个节点（虚线部分），构成了循环链表。特点是从任意一个节点出发，沿两个方向的任何一个，都能找到链表中的任意点出发，沿两个方向的任何一个，都能找到链表中的任意一个数据。如果去掉前驱指针，就是单循环链表。一个数据。如果去掉前驱指针，就是单循环链表。 Linux中的链表中的链表v在在Linux内核中使用了大量的链表结构来组织数内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组据，包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在织。这些链表大多采用在include/linux/list.h实现的一个相当精彩实现的一个相当精彩的链表数据结构。的链表数据结构。 Linu

4、x 2.6内核链表数据结构的实现内核链表数据结构的实现 v 经典链表定义经典链表定义v 链表数据结构的定义链表数据结构的定义 include/linux/list.h，这里的这里的list_head没有数据域。在没有数据域。在Linux内核链表中，不是在链表结构中内核链表中，不是在链表结构中包含数据，而是在数据结构中包含链表节点。包含数据，而是在数据结构中包含链表节点。Linux链表示例链表示例vLinux 内核链表中，需要用链表组织起来的数据内核链表中，需要用链表组织起来的数据通常会包含一个通常会包含一个struct list_head成员，例如成员，例如在在include/linux/ne

5、tfilter.h中定义了一中定义了一个个nf_sockopt_ops结构来描述结构来描述 Netfilter为为某一协议族准备的某一协议族准备的getsockopt/setsockopt接口，其中就有一个（接口，其中就有一个（struct list_head list）成员，各个协议族的成员，各个协议族的nf_sockopt_ops结构都结构都通过这个通过这个list成员组织在一个链表中，表头是定成员组织在一个链表中，表头是定义在义在 net/core/netfilter.c中的中的nf_sockopts（struct list_head）。）。 Linux链表图例链表图例v 1、申明和初始

6、化、申明和初始化v2、LIST_HEAD(nf_sockopts)声明一个名为声明一个名为nf_sockopts的链表头时，它的的链表头时，它的next、prev指针都初指针都初始化为指向自己始化为指向自己。v3、空链表的判断（用头指针的空链表的判断（用头指针的next是否指向自己来判是否指向自己来判断链表是否为空断链表是否为空 ）链表操作接口链表操作接口 链表操作接口链表操作接口v 4、初始化（、初始化（2）v 5、插入（、插入（表头插入、表尾插入表头插入、表尾插入 ） 插入示例（插入示例（新新nf_sockopt_ops结构变量结构变量new_sockopt需要添加到需要添加到nf_soc

7、kopts链表头链表头 ）链表操作接口链表操作接口v 6、删除删除 删除示例（删除示例（删除删除nf_sockopts链表中添加的链表中添加的new_sockopt项项 ）v 7、搬移（将原本属于一个链表的节点移动到另一个链表的操作搬移（将原本属于一个链表的节点移动到另一个链表的操作 ） v 例如例如list_move(&new_sockopt.list,&nf_sockopts)会把会把new_sockopt从它所在的链表上删除，并将其再从它所在的链表上删除，并将其再链入链入nf_sockopts的表头。的表头。链表操作接口链表操作接口v 8、合并、合并v 合并示例：合并示例

8、：当前有两个链表，表头分别是当前有两个链表，表头分别是list1和和 list2（都是（都是struct list_head变量），当调用变量），当调用list_splice(&list1,&list2)时，只要时，只要list1非非空，空，list1链表的内容将被挂接在链表的内容将被挂接在list2链表上，位于链表上，位于list2和和list2.next（原（原list2表的第一个节点）之间。新表的第一个节点）之间。新list2链表将以原链表将以原list1表的第一个节点表的第一个节点为首节点，而尾节点不变。如图（虚箭头为为首节点，而尾节点不变。如图（虚箭头为next指针）

9、：指针）： 由链表节点到数据项变量由链表节点到数据项变量 v Linux链表中仅保存了数据项结构中链表中仅保存了数据项结构中list_head成员变成员变量的地址，那么我们如何通过这个量的地址，那么我们如何通过这个list_head成员访问到成员访问到作为它的所有者的节点数据呢？作为它的所有者的节点数据呢？v List_entry的实现的实现 Offsetof原理原理链表的遍历链表的遍历v net/core/netfilter.c的的nf_register_sockopt()函数中有函数中有这么一段这么一段 ,如何理解？如何理解？v 函数首先定义一个函数首先定义一个(struct list_h

10、ead *)指针变量指针变量i，然后调用然后调用list_for_each(i,&nf_sockopts)进行遍历。进行遍历。 list_for_each()宏宏 v 它实际上是一个它实际上是一个for循环，利用传入的循环，利用传入的pos作为循环变量，作为循环变量，从表头从表头head开始，逐项向后（开始，逐项向后（next方向）移动方向）移动pos，直至又回到直至又回到head（prefetch()可以不考虑，用于预取可以不考虑，用于预取以提高遍历速度）。以提高遍历速度）。 list_for_each_entry() 宏宏v 宏定义宏定义v 宏定义应用宏定义应用栈的概念栈的概念v一

11、、栈的定义一、栈的定义栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。(2)当表中没有元素时称为空栈。(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。 栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中“最新”的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。v【示例】元素是以【示例】元素是以a1

12、，a2，an的顺序进栈，退栈的次序却是的顺序进栈，退栈的次序却是an，an-1，a1。栈的概念栈的概念v 二、栈的特点二、栈的特点 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(Last In First Out)的线性表，简称为LIFO表。v 三、栈的运算三、栈的运算 1.初始化栈：INISTACK(&S)将栈S置为一个空栈(不含任何元素)。2.进栈：PUSH(&S,X)将元素X插入到栈S中，也称为 “入栈”、 “插入”、 “压入”。3.出栈： POP(&

13、S) 删除栈S中的栈顶元素，也称为”退栈”、 “删除”、 “弹出”。4.取栈顶元素： GETTOP(S)取栈S中栈顶元素。5.判栈空： EMPTY(S)判断栈S是否为空，若为空，返回值为1，否则返回值为0。顺序栈顺序栈v栈的顺序存储结构简称为顺序栈栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。它是运算受限的顺序表。.栈的顺序存储结构一、栈的数组表示#define MAXN 100; /定义栈的最大容量为MAXNchar stackMAXN; /将栈中元素定义为字符类型int top; /指向栈顶位置的指针二、栈的变化栈总是处于栈空、栈满或不空不满三种状态之一，它们是通过栈顶指针top的值

14、体现出来的。规定：top的值为下一个进栈元素在数组中的下标值。栈空时（初始状态），top=0;栈满时，top=MAXN顺序栈顶指针和栈中元素的关系顺序栈顶指针和栈中元素的关系链表栈链表栈v 栈的链式存储结构称为链栈。栈的链式存储结构称为链栈。 一、链栈结构及数据类型栈的链式存贮结构,也称为链栈，它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行。链栈结构见图。 二、栈的变化在链栈中，只会出现栈空和非空两种状态。当栈为空时，有top=null;当栈非空时， top指向链表的第一个结点（栈顶）。函数调用与局部变量函数调用与局部变量v 局部变量局部变量 关于函数中局部变量的存储位

15、置，也是在栈中存储的，但并非以入栈出栈的形式，而是以EBP为顶，依次压入，在执行函数前，EBP存放基址，基址就是，比如说main函数中调用了F函数，main函数中的所有变量都是以EBP为基址依次向下递减，可见EBP也是栈，而ESP与EBP之间存在着一个距离，这个距离是，将ESP的值先赋给EBP，然后，ESP加了一个数，也就是入栈出栈的存储地点在EBP内存下面，比EBP小，两者之间的距离用来函数声明变量存储所用，对于任何一个函数，每次执行时，都要对它确定两个值，EBP和ESP，这两个值要与调用它的函数岔开，不能有重合。函数执行完，对于局部变量，可能是编译器释放内存，但从反汇编的代码看来，只是将E

16、BP返回到了调用函数原来的位置，并没有清空局部变量。v 函数调用入栈过程函数调用入栈过程 函数入栈顺序，1形参，从右到左。2地址，返回地址，一般为下一行地址。3EBP，因为函数执行完毕后，调用函数仍需要用EBP，因此EBP需要保护，同时，在被调函数的执行时，也需要一个EBP，此时的EBP就是栈中返回地址存储的下一位地址，从这位开始为函数内局部变量分配存储空间 v 程序实例程序实例计算函数表达式计算函数表达式v 表达式表达式中缀表示法是算术表达式的常规表示法。称它为中缀表示法是因为每个操作符都位于其操作数的中间，这种表示法只适用于操作符恰好对应两个操作数的时候（在操作符是二元操作符如加、减、乘、除以及取模的情况下）。对以中缀表示法书写的表达式进行语法分析时，需要用括号和优先规则排除多义性。Example: (A+B)*C-D/(E+F) 前缀表示法中，操作符写在操作数的前面。这种表示法经常用于计算机科学，特别是编译器设计方面。为纪念其发明家 Jan Lukasiewicz（请参阅参考资料），这种表示法也称波兰表示法。 Example : -*+ABC/D+EF 在后缀表示法中，操作符位于操作数后面