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