1、图像数据结构与算法 C语言版尹继豪E-mail:2022-11-112第二章 线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表2022-11-1132.1 线性表的类型定义线性表的类型定义 线性表(Linear List)：由n(n1)个数据元素(结点)a1，a2，an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作：(a1，a2，an)这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文
2、字母组成的字母表（A，B，C、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）2022-11-114例3、学生健康情况登记表如下：姓 名学 号性 别年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱.2022-11-115例4、一副扑克的点数（2，3，4，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而
3、仅有一个直接前趋a n-1；其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。因此，线性表是一种典型的线性结构。注意：注意：数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。2022-11-1162.2 线性表的顺序表示和实现线性表的顺序表示和实现2.2.1 线性表 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(a i+1)和第i个数据元素的存储位
4、置LOC(ai)之间满足下列关系：LOC(a i+1)=LOC(a i)+L 线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)L 2022-11-117 2.2.2 顺序表上实现的基本操作顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：注意：C语言中的数组下标从“0”开始，因此，若L是SqList类型的顺序表，则表中第i个元素是L.datai-1。以下主要讨论线性表的插入、删除、合并三种运算。1、插入（演示：顺序表插入）、插入（演示：顺序表插入）线性表的插入运算是指在表的第i(1in+1)个位置上
5、，插入一个新结点x，使长度为n的线性表(a1，a i-1，ai，an)变成长度为n+1的线性表(a1，a i-1，x，ai，an)2022-11-1182、删除（演示：顺序表删除）、删除（演示：顺序表删除）线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表：(a1，a i-1，ai，a i+1，an)变成长度为n-1的线性表(a1，a i-1，a i+1，an)3、合并（演示：顺序表合并）、合并（演示：顺序表合并）2022-11-1192.3 线性表的链式表示和实现线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以
6、随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点。为避免大量结点的移动，我们介绍线性表的另一种存储方式链式存储结构，简称为链表(Linked List)。2.3.1 线性链表 链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：2022-11-1110 其中：dat
7、a域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表(Single Linked)。显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即null（图示中也可用表示）。datanext2022-11-1111例、线性表:(bat，cat，eat，fat，hat，jat，lat，mat)用C语言描述的单链表如
8、下：typedef struct LNode ElemType data;struct LNode *next;listnode;bat cat eat mat 2022-11-1112一、建立单链表（演示：创建链表）一、建立单链表（演示：创建链表）假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符n为输入结束标记。动态地建立单链表的常用方法有如下两种：1、头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。2、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的
9、次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。2022-11-1113二、插入运算（演示：向链表中插入结点）二、插入运算（演示：向链表中插入结点）插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai，从而实现三个结点ai-1，x和ai之间的逻辑关系的变化。三、删除运算（演示：从链表中删除结点）三、删除运算（演示：从链表
10、中删除结点）删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以我们必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下，最后释放结点ai的空间，将其归还给“存储池”。2022-11-1114四、合并运算（演示：生成新结点的有序链表四、合并运算（演示：生成新结点的有序链表合并）合并）从上面的讨论可以看出，链表上实现插从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指入和删除运算，无须移动结点，仅需修改指针。针。2022-11-11152.3.2 2.3.2 循环链表循环链
11、表 循环链表是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：2022-11-1116 在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)。a1 an .head 非空表 空表2022-11-1117 在很多实际问
12、题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便。如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rearnext)next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。2022-11-11182.3.32.3.3双链表双链表 双向链表(Double linked list):在单链表的每个结点里再增加一个指向
13、其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：typedef struct DuLNode ElemType data;struct DuLNode*prior,*next;DuLNode;typedef DuLNode*dlinklist;dlinklist head;2022-11-1119 在单链表中，NextElem的执行时间为O(1)，然而PriorElem的执行时间为O(n)。为了克服单链表的这种单向性的缺点，引入了双向链表。和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：(p-prior)-next=p=(p-next)-prior 即结点*p的存储位置既存放在其前趋结点*(p-prior)的直接后继指针域中，也存放在它的后继结点*(p-next)的直接前趋指针域中。2022-11-11201、双向链表的插入操作2、双向链表的删除操作 注意：注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。
