数据结构PPT教学课件-第2章_线性表.ppt

第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加,线性表,线性结构是一个数据元素的有序（次序）集。 线性结构的特点： 存在唯一的一个被称做“第一个”的数据元素； 存在唯一的一个被称做“最后一个”的数据元素； 除第一个之外，集合中的每个数据元素均只有一个前驱； 除最后一个之外，集合中每个数据元素均只有一个后继。,2.1 线性表的类型定义,线性表（liner list）：n（ 0）个数据元素的有限序列，记作（a1, ai-1, ai, ai+1, an）；其中ai是表中数据元素，n是表长度。 线性表的特点： 同一线性表中元素具有相同特性； 相邻数据元素之间存在序偶关系； 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱； 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。,线性表举例： 1. 数据元素只要是同性质就可以： 比如（a，b，z），又如（6，17，28，50，92，188） 2. 一个数据元素可以由若干项目（数据项item）组成，此时数据元素称为记录（record），而含有大量记录的线性表又称文件（file）。,线性表定义演示,结论： 线性表中的数据元素可以是各种各样的，但同一线性表（a1, ai-1, ai, ai+1, an）中所有元素具有相同特性，即属同一数据对象。 任意两相邻元素ai-1和 ai之间存在序偶关系；其中称ai-1为ai的直接前驱，而ai为ai-1的直接后继。当i=1,2,n-1时，ai有且仅有一个直接后继，当i=2,3,n时，ai有且仅有一个直接前驱。 线性表中元素的个数n定义为线性表的长度，n=0时称为空表。 在非空线性表中，任意一个元素ai是表的第i个元素，i称为数据元素在线性表中的位序。,线性表的抽象数据类型定义以及基本操作,数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。 抽象数据类型线性表的定义如下： adt list 数据对象：d= ai|aielemset，i=1,2,n, n0 数据关系：r1= | ai-1， ai di，i=2,n 基本操作：,线性表的基本操作（一）,initlist(&l) 操作结果：构造一个空的线性表l。 destroylist(&l) 初始条件：线性表l已存在。 操作结果：销毁线性表。,线性表的基本操作（二）,cleanlist(&l) 初始条件：线性表l已存在。 操作结果：将l重置为空表。 listempty(&l) 初始条件：线性表l已存在。 操作结果：若l为空表，则返回true，否则返回false。,线性表的基本操作（三）,listlength(l) 初始条件：线性表l已存在。 操作结果：返回l中数据元素个数。 getelem(l, i, &e) 初始条件：线性表l已存在，1i listlength(l)。 操作结果：用e返回l中第i个数据元素的值。,线性表的基本操作（四）,locateelem(l, e, compare() 初始条件：线性表l已存在， compare()是数据元素判定函数。 操作结果：返回l中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。 priorelem(l, cur_e, &pre_e) 初始条件：线性表l已存在。 操作结果：若cur _e是l的数据元素，且不是第一个，则用pre _e返回它的前驱，否则操作失败， pre _e无定义。,线性表的基本操作（五）,nextelem(l, cur_e, &next_e) 初始条件：线性表l已存在。 操作结果：若cur_e是l的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败， next_e无定义。 listinsert(&l, i, e) 初始条件：线性表l已存在， 1i listlength(l)+1。 操作结果：在l中第i个位置之前插入新的数据元素e，l的长度加1。,线性表的基本操作（六）,listdelete(&l, i, &e) 初始条件：线性表l已存在且非空， 1i listlength(l)。 操作结果：删除l的第i个数据元素，并用e返回其值，l的长度减1。 listtraverse( l, visit() ) 初始条件：线性表l已存在。 操作结果：依次对l的每个数据元素调用函数visit() 。一旦visit()失败，则操作失败。,线性表基本操作演示,例2-1：假设利用两个线性表la和lb分别表示两个集合a和b（即：线性表中的数据元素即为集合中的成员），先要求一个新的集合a=ab。 要求对线性表做如下操作： 扩大线性表la； 将存在于线性表lb中而不存在于la中的数据元素插入到线性表la中去。,集合：a = 5, 17, -3, 36 ,集合：b = 25, 17, -3, 54, 13, 88 ,集合：ab = 5, 25, 17, -3, 36, 54, 13, 88 ,需要做：扩大线性表la，将存在于线性表lb中而不存在于线性表la中的数据元素插入到线性表la中。 解决方法：只要从线性表lb中依次取得每个数据元素，并依值在线性表la中进行查访，若不存在，则插入la。,基本操作： 1、从线性表lb中依次取得每个数据元素; getelem(lb, i) e 2、依值在线性表la中进行查访; locateelem(la, e, equal( ) 3、若不存在，则插入la。 listinsert(la, n+1, e),void union(list ,算法2.1,算法的复杂度分析,上述算法的时间复杂度取决于抽象数据类型list定义中基本操作的执行时间。 假如getelem和listinsert这两个操作的执行时间与表长无关，locateelem的执行时间和表长成正比，则算法2.1的时间复杂度为： o(listlength(la)listlength(lb),例2-2：已知线性表la和lb中的数据元素按值非递减有序排列，先要求将la和lb归并为一个新的线性表lc，且lc中的元素仍旧按值非递减有序排列。 要求对线性表做如下操作： 建立空表lc； 将la或者lb中的元素逐个插入到lc中即可； 同时要保证lc的有序性。,线性表：la = ( -3, 17, 25, 36 ),线性表：lb = ( 27, 33, 54, 63, 88 ),线性表：lc = ( -3, 17, 25, 27, 33, 36, 54, 63, 88 ),lc中的数据元素或是la中的数据元素，或是lb中的数据元素，只要先设lc为空表，然后将la或lb中的元素逐个插入到lc中即可。 为使lc中元素按值非递减有序排列，可设两个指针i和j分别指向la和lb中某个元素，若设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到lc中的元素min(a,b)。 显然，指针i和j的初值均为1，在所指元素插入lc之后，在la或lb中顺序后移。,线性表：la = ( -3, 17, 25, 36 ),线性表：lb = ( 27, 33, 54, 63, 88 ),线性表：lc = ( -3, 17, 25, 27, 33, 36, 54, 63, 88 ),基本操作步骤,设：la = (a1, , ai, , an)，lb = (b1, , bj, , bm) ， lc = (c1, , ck, , cm+n) 且已由(a1, , ai-1)和(b1, ,bj-1)归并得 (c1, , ck-1) 则 k = 1, 2, , m+n。,具体步骤： 1、分别从la和lb中取得当前元素ai和bj； 2、若aibj，则将ai插入到lc中，否则将bj插入到lc中。 3、将 la表或 lb 表中剩余元素复制插入到lc表中。,void mergelist(list la，list lb，list /求取lb的长度 while(i=la-len)&(j=lb-len) /取la和lb两表中当前所考虑两元素ai和bj中较小者放入lc中；同时，当la或者lb已考察完时，循环结束。,getelem(la，i，ai);getelem(lb，j，bj); if(ai=bj)listinsert(lc，+k，ai);+i; elselistinsert(lc，+k，bj);+j; while(i=la-len) /如果la中仍有元素没有合并到lc中 /将这些元素依次插入到lc的尾部 getelem(la，i+，ai);listinsert(lc，+k，ai); while(j=lb-len) /如果lb中仍有元素没有合并到lc中 /将这些元素依次插入到lc的尾部 getelem(lb，j+，bj);listinsert(lc，+k，bj); /此时，新表lc不仅仅包含la和lb中的所有元素，且lc中的数据元素按值非递减有序,算法2.2,算法的复杂度分析,上述算法的时间复杂度取决于抽象数据类型list定义中基本操作的执行时间。 虽然算法2.2中含3个while循环语句，但只有当i和j均指向表中实际存在的数据元素时，才能取得数据元素的值并进行相互比较；并且当其中一个线性表的数据元素均已插入到线性表lc中后，只要将另外一个线性表中的剩余元素依次插入即可。因此，对于每一组具体的输入（la和lb），后两个while循环语句只执行一个循环体。 算法2.2的时间复杂度为 o(listlength(la) + listlength(lb),2.2 线性表的顺序表示和实现,把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。 则线性表中第i+1个数据元素的存储位置loc(ai+1)和第i个数据元素的存储位置loc(ai )之间满足下列关系： loc(ai+1) = loc(ai) + l 线性表的第i个数据元素ai的存储位置为： loc(ai) = loc(a1) + (i-1) * l,loc(a i+1) = loc( a i )+l loc(a i) = loc(a1)+(i-1)*l,每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。,顺序表的特点,线性表的这种机内表示称作线性表的顺序存储结构或顺序映象（sequential mapping），称这种存储结构的线性表为顺序表。 特点：为表中相邻的元素ai和ai+1赋以相邻的存储位置loc(ai)和loc(ai+1)。 换句话说，以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。 每一个数据元素的存储位置都和线性表的起始位置相差一个与数据元素在线性表中的位序成正比的常数。,顺序表的特点,只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。 所有数据元素的存储位置均取决于第一个数据元素的存储位置：loc(ai) = loc(a1) + (i-1)l 式中loc(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。,顺序表定义演示,由于c语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。 又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。 # define listsize 100 typedef int datatype; typedef struc datatype datalistsize; /用一维数组表示顺序表 int length; /length表示数组中实际元素个数，即顺序表的实际长度 /listsize表示数组的最大容量，即顺序表的最大长度 sqlist;,# define listsize 100 typedef int datatype; typedef struc datatype datalistsize; /用一维数组表示顺序表 int length; /length表示数组中实际元素个数，即顺序表的实际长度 /listsize表示数组的最大容量，即顺序表的最大长度 sqlist;, 存放线性表结点的向量空间的大小listsize应仔细选值，使其既能满足表结点的数目动态增加的需求，又不致于预先定义过大而浪费存储空间。,需要注意,# define listsize 100 typedef int datatype; typedef struc datatype datalistsize; /用一维数组表示顺序表 int length; /length表示数组中实际元素个数，即顺序表的实际长度 /listsize表示数组的最大容量，即顺序表的最大长度 sqlist;, 由于c语言中向量的下标从0开始，所以若l是sqlist类型的顺序表，则线性表的开始结点a1和终端结点an分别存储在l.data0和l.datal.length-1中。,# define listsize 100 typedef int datatype; typedef struc datatype datalistsize; /用一维数组表示顺序表 int length; /length表示数组中实际元素个数，即顺序表的实际长度 /listsize表示数组的最大容量，即顺序表的最大长度 sqlist;, 若l是sqlist类型的指针变量，则a1和an分别存储在l-data0和l-datal-length-1中。,高级程序设计语言中的数组也有随机存取的特性； 同时，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在c语言中可用动态分配的一维数组，如下： #define list_init_size 100 /顺序表的初始分配量 #define listincrement 10 /顺序表的分配增量 typedef struct elemtype *elem; /存储空间基址：即数组的起始地址 int length; /顺序表的当前长度：实际的元素个数 int listsize; /当前分配的存储容量（以sizeof（elemtype）为单位） sqlist;,线性表的动态分配顺序存储结构,线性表的动态分配顺序存储结构的初始化,status initlist_sq( sqlist /顺利完成初始化 ,顺序表的基本操作：按值查找,按值查找：找x在表中的位置，若查找成功，返回表项的位置，否则返回-1： int find( sqlist ,求表的长度 int length( seqlist ,在顺序表存储结构中，很容易实现线性表的一些操作，如：线性表的构造、第i个元素的访问。 注意：c语言中的数组下标从“0”开始，因此，若l是sqlist类型的顺序表，则表中第i个元素是l.elemi-1。 以下主要讨论线性表的插入和删除两种运算：,线性表的插入运算：在表的第i(1in+1)个位置上，插入一个新结点x，使长度为n的线性表 (a1，ai-1，ai，an) 变成长度为n+1的线性表 (a1，ai-1，x，ai，an),插入,25 34 57 16 48 09 63 ,0 1 2 3 4 5 6 7,50,插入 x,25 34 57 50 16 48 09 63 ,0 1 2 3 4 5 6 7,50,i,在第i（1in）个元素之前插一个元素时： 需将第n至第i（共n-i+1）个元素向后移动一个位置，依次后移到n+1,n,i+1位置上，空出第i个位置； 在该位置上插入新结点e。,插入,25 34 57 16 48 09 63 ,0 1 2 3 4 5 6 7,50,插入 x,25 34 57 50 16 48 09 63 ,0 1 2 3 4 5 6 7,50,i,注意： 由于向量空间大小在声明时确定，当l.lengthlistsize时，表空间已满，不可再做插入操作； 当插入位置i的值为in或i1时为非法位置，不可做正常插入操作。,插入,25 34 57 16 48 09 63 ,0 1 2 3 4 5 6 7,50,插入 x,25 34 57 50 16 48 09 63 ,0 1 2 3 4 5 6 7,50,i,顺序表插入时，平均数据移动次数amn在各表项 插入概率相等时,线性表的结构定义： -线性表的动态分配存储结构- #define list_init_size 100 /顺序表的初始分配量 #define listincrement 10 /顺序表的分配增量 typedef struct elemtype *elem; /存储空间基址：即数组的起始地址 int length; /顺序表的当前长度：实际的元素个数 int listsize; /当前分配的存储容量（以sizeof（elemtype）为单位） sqlist;,线性表的初始化（算法2.3） status initlist_sq( sqlist /initlist_sq,顺序表的插入（算法2.4） status insertlist_sq(sqlist /线性表长度增加 ,q = /返回插入成功标志“ok” /listinsert_sq,注意：元素位序与数组下标的关系。,插入操作演示,线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表： (a1，ai-1，ai，ai+1，an) 变成长度为n-1的线性表 (a1，ai-1，ai+1，an),需将第i+1至第n共（n-i)个元素前移。 注意：当要删除元素的位置i不在表长范围（即i1或il.length）时，为非法位置，不能做正常的删除操作。,删除,25 34 57 50 16 48 09 63 ,16,删除 x,25 34 57 50 48 09 63 ,0 1 2 3 4 5 6 7,在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。 若i=n，则只要简单地删除终端结点，无须移动结点； 若1in-1，则必须将表中位置i+1,i+2,n的结点，依次前移到位置i,i+1,n-1上，以填补删除操作造成的空缺。,删除,25 34 57 50 16 48 09 63 ,16,删除 x,25 34 57 50 48 09 63 ,0 1 2 3 4 5 6 7,顺序表删除平均数据移动次数amn在各表项 删除概率相等时,顺序表的删除（算法2.5） status listdelete_sq ( sqlist /返回删除元素成功标志 ,删除操作演示,总结,当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上（换句话说，移动元素的操作为预估算法时间复杂度的基本操作），而移动元素的个数取决于插入或删除元素的位置。 所以在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低。,顺序存储结构的优缺点,优点： 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点： 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充,2.3 线性表的链式表示和实现,顺序存储的弱点：在作插入或删除操作时，需移动大量元素。 顺序存储的优点：随机存取。 线性表的另一种表示方法：链式存储结构 不要求逻辑上相邻的元素在物理位置上也相邻； 同时失去了可随机存取的优点。,2.3.1 线性链表,链表是指用一组任意的存储单元来依次存放线性表的结点； 这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同； 为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素来说除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。,两部分信息组成数据元素ai的存储映象，称为结点（node）。,为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：,data域是数据域，用来存放结点的值。 next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（single linked)。,n个结点链结长一个链表，即为线性表(a1，ai-1，ai，ai+1，an)的链式存储结构。 又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。 例如：线性表（zhao,qian,sun,li,zhou,wu,zheng,wang）的线性链表存储结构。,头指针指示链表中第一个结点（即第一个数据元素的存储映象）的存储位置。 同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”（null）。,单链表：这个链表的存取从头指针开始。,单链表的物理（存储）结构,单链表：这个链表的存取从头指针开始。,单链表的逻辑结构,线性表（zhao,qian,sun,li,zhou,wu,zheng,wang）的线性链表存储结构。,再例：线性表(bat, cat, eat, fat, hat, iat, lat, mat) 显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点（根结点）无前趋，故应设头指针head指向开始结点。 同时，由于终端结点（叶子结点）无后继，故终端结点的指针域为空，即null（图示中也可用表示)。 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针名是head，则把链表称为表head。,单链表和指针,线性表的链式表示和实现,/-线性单链表存储结构- typedef struct lnode elemtype data; /数据域 struct lnode *next; /指针域 lnode, *linklist; / lnode应该为线性单链表的结点 / *linklist应该为指向线性单链表结点的指针,非空的线性单链表和空的线性单链表。 假设l是linklist型的变量，则l为单链表的头指针，它指向表中第一个结点； 若l为“空”（l=null），则所以表示的线性表为“空”表，其长度n为“零”。 有时，我们在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置：地址）。,空表的单链表,typedef lnode *linklist; lnode *p; linklist head;,注意：区分指针变量（p以及head）和结点变量（*p）这两个不同的概念： 指针变量p：其值为结点地址； 结点变量*p：其值为结点内容。 linklist和lnode *是不同名字的同一个指针类型（命名的不同是为了概念上更明确）： linklist类型的指针变量head表示它是单链表的头指针； lnode *类型的指针变量p表示它是指向某一结点的指针。,typedef struct lnode elemtype data; struct lnode *next; lnode, *linklist;,指针变量p和结点变量*p,(*p)表示p所指向的结点： (*p).data，即p-data，表示p指向结点的数据域； (*p).next，即p-next，表示p指向结点的指针域。,typedef lnode *linklist; lnode *p; linklist head; p为动态变量，它是通过标准函数生成的，即 p=( lnode * )malloc( sizeof( lnode ) ); 函数malloc分配了一个类型为lnode的结点变量的空间，并将其首地址放入指针变量p中。 一旦p所指的结点变量不再需要了，又可通过标准函数free(p)释放所指的结点变量空间。,typedef struct lnode elemtype data; struct lnode *next; lnode, *linklist;,typedef lnode *linklist; lnode *p; linklist head; 结点分量的访问：利用结点变量的名字*p访问结点分量 方法一：(*p).data和(*p).next 方法二：p-data和p-next 指针变量p和结点变量*p的关系： 指针变量p的值结点地址 结点变量*p的值结点内容 (*p).data的值p指针所指结点的data域的值 (*p).next的值*p的直接后继结点的地址 *(*p).next) *p的直接后继结点,typedef struct lnode elemtype data; struct lnode *next; lnode, *linklist;,注意：若指针变量p的值为空（null），则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。,指针变量p和结点变量*p,线性链表的特性,对于顺序表，逻辑上相邻的两个元素在物理位置上紧邻，则每个元素的存储位置都可从线性表的起始位置计算得到； 对于单链表，任何两个元素的存储位置之间没有固定的联系； 但是，在单链表中，每个元素的存储位置都包含在其直接前驱结点的信息之中。（指针域） 如果p-data = ai, p-next-data = ai+1； 因此，在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是非随机存取的存储结构。,带头结点的线性单链表,头结点：在单链表第一个结点（首结点）前附设一个结点叫头结点。 头结点指针域为空表示线性表为空。,从线性单链表中取第i个数据元素（算法2.8）,status getelem_l ( linklist l, int i, elemtype /取值成功，结束操作并返回取值成功标志。 /getelem_l,指针的基本操作演示,线性单链表的插入与删除操作,在一个带头结点的线性单链表l中插入一个新结点，其结点值为e，而其插入位置在原链表结点a和结点b之间。其中结点a由指针p指向。,插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1（a结点）与ai（b结点）之间。（如前例） 因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*s，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如下：,s=(listnode *)malloc(sizeof(listnode); sdata=e; snext=pnext; pnext=s;,(a1，ai-1，ai，ai+1，an),算法2.9 status listinsert_l(linklist l，int i，elemtype e) /在带头结点的单链表l中第i个位置之前插入元素。 p = l；j = 0； while( p /插入成功。 /listinsert_l,单链表结点插入演示,不带头结点的单链表的插入操作如何完成？,在带头结点的线性链表中删除元素b，为了在单链表中实现元素a、b和c之间逻辑关系的变化，仅需修改结点a中的指针域即可。,删除运算是将表的第i个结点删去。 因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以我们必须首先找到ai-1的存储位置p； 然后令pnext指向ai的直接后继结点，即把ai从链上摘下； 最后释放结点ai的空间，将其归还给“存储池”。此过程为： (a1，ai-1，ai，ai+1，an) 变成：(a1，ai-1，ai+1，an)。,算法2.10 status listdelete _l( linklist l， int i，elemtype /释放结点的存储空间。 ,单链表结点删除演示,不带头结点的单链表的删除操作如何完成？,线性链表的两个基本操作的时间复杂度分析,设链表的长度为n，合法的插入位置是1in+1。 注意当i=1时，是头结点，当 i=n+1时，是结点an。 因此，用i-1做可完成插入位置的合法性检查。算法的时间主要耗费在查找操作上，故时间复杂度亦为o(n)。,线性链表的两个基本操作的时间复杂度分析,设单链表的长度为n，则删去第i个结点仅当1in时是合法的。 注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。 因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=null）且*p不是终端结点（即pnext!=null）时，才能确定被删结点存在。 显然此算法的时间复杂度也是o(n)。,线性链表的两个基本操作的时间复杂度分析,结论：链表上实现插入和删除运算，无须移动结点，仅需修改指针。,线性单链表的生成,单链表和顺序存储结构不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是可以由系统应需求即时生成。 建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。 创建单链表方法有两种，假设线性表中结点的数据类型是字符型，逐个输入这些字符型的结点数据，并以换行符n为输入条件结束标志符，动态地建立单链表。,(1) 尾插法建表,算法思路：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表尾上，直到读入结束标志为止。 注意： 采用尾插法建表，生成链表结点的次序与输入顺序一致； 必须增加一个尾指针r，使其始终指向当前链表的尾结点。,尾插入法建立线性单链表,linklist creatlistr(void) /返回单链表的头指针 char ch; linklist head; /头指针 listnode *s,*r; /工作指针 head=null; /链表开始为空 r=null; /尾指针初值为空 ch=getchar(); /读入第1个字符 while(ch!=n) s=(listnode*)malloc (sizeof(listnode); /生成新结点 s-data=ch; /将读入的数据放入新结点的数据域中,if (head= =null) head=s; /新结点插入空表 else r-next=s; /将新结点插到*r之后 r=s; /尾指针指向新表尾 ch=getchar(); /读入下一字符 /endwhile if (r!=null) r-next=null; /对于非空表，将尾结点指针域置空 return head; / 算法2.11,算法时间复杂度为：o(listlength(l),说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。 算法中的第一个if语句是用来对第一个位置上的插入操作做特殊处理。 第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在； 否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。,如果在链表的开始结点之前附加一个结点，并称它为头结点，则会带来以下两个优点： 由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理； 无论链表是否为空，其头指针是指向头结点所在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。,带头结点尾插法创建单链表算法,linklist creatlistr1(void) /用尾插法建立带头结点的单链表 char ch; linklist head=(listnode*) malloc (sizeof(listnode); /生成头结点 listnode *s,*r; /工作指针 r=head; / 尾指针初值也指向头结点,while (ch=getchar()!=n) s=(listnode*) malloc (sizeof(listnode); /生成新结点 s-data=ch; /将读入的数据放入新结点的数据域中 r-next=s; r=s; r-next=null; /终端结点的指针域置空，或空表的头结点指针域置空 return head; ,算法的时间复杂度为o(listlength(l),(2) 头插法建表,算法思路：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。 注意：该方法生成链表的结点次序与输入顺序相反。,头插入法建表演示,线性单链表的元素查找,（1）按序号查找 在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。 设单链表的长度为n，要查找表中第i个结点，仅当1in时，i的值是合法的。但有时需要找头结点的位置，将头结点看做是第0 个结点，其算法如下：,lnode *getnode (linklist head, int i) int j; lnode *p; p=head; j=0; while (pnext /找不到第i个结点 ,（2）按值查找 按值查找是在链表中，查找是否有结点值等于给定值key的结点， 若有的话，则返回首次找到的其值为key的结点的存储位置； 否则返回null。 查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：,lnode *locatenode (linklist head, int key) lnode *p=headnext; while( p /若p=null，则查找失败，否则p指向值为key的结点 ,2.3.2 循环链表,循环链表（circular linked list）是一种头尾相接的链表。是另一种形式的链式存储结构。 特点： 无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。（链式存储结构的特点） 从表中任一结点出发均可找到表中其它结点。（循环链表的特点） 单循环链表：在单链表中，将终端结点的指针域null改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。,为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：,在用头指针表示的单循环链表中，找开始结点a1的时间是o(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是o(n)。,在很多实际问题中，表的操作常常是在表的尾部进行，此时头指针表示的单循环链表就显得不够方便。 如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rear-next) -next和rear，显然，查找时间都是o(1)。 因此，实际中多采用尾指针表示单循环链表。,由于循环链表中没有null指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p-next是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。,空循环链表,举例：在链表上实现将两个线性表(a1，a2，a3，an)和(b1，b2，b3，bn)链接成一个线性表的运算。,具体算法如下： linklist connect(linklist la，linklist lb) linklist p = la-next; /p指向la头结点后的第一个结点。 la-next = ( lb-next )-next; /lb中的所有结点依次连接在la中的尾指针所指向的最后一个结点之后。 /由于链表的特性，只需要将lb中头指针指向的第一结点的地址赋给la中最后一个结点的指针域。 free( lb-next ); /释放原来lb表的头结点。 lb-next = p; /原lb表的头指针和la的头指针指向一致。 return( lb ); /返回lb，操作完成。 ,2.3.3 双向链表,双向链表(double linked list)：在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。,形式描述为： /-线性表的双向链表存储结构- typedef struct dulnode elemtype data; struct dulnode *prior; /指向后件的指针 struct dulnode *next; /指向前件的指针 dulnode，*dulinklist;,双向链表（带表头结点）,双向循环链表,和单循环链表类型，双向链表也可以有循环表。 链表中存有两个环，并带有头结点。,element,prior,next,结点结构,l,空的双向循环链表,l,非空的双向循环链表,双向循环链表的特性：d-next-prior = d-prior-next = d；,在双向链表中，有些操作如：listlength、getelem和locateelem等仅需涉及一个方向的指针，则它们的算法描述和线性单链表的操作相同； 但在插入、删除时需要修改两个方向上的指针。,双向链表的删除操作需要修改两个方向上的指针：,删除（算法2.18） status listdelete_dul( dulinklist /删除操作成功，返回标志ok。 /listdelete_dul,双向链表的插入操作需要修改两个方向上的指针：,插入（算法2.19） status listinsert_dul( dulinklist /插入结点s成功，返回操作成功标志ok。 ,总结,由于链表在空间的合理利用上和插入、删除时不需要移动等的优点，因此在很多场合下，它是线性表的首选存储结构； 但也存在着实现某些基本操作如求线性表的长度时不如顺序存储结构的缺点； 由于链表中，结点之间的关系用指针来表示，则数据元素在线性表中的“位序”的概念淡化，而被“位置”所代替。,2.4 一元多项式的表示及相加,符号多项式的操作：一元多项式pn(x)可以按升幂写成:,它由n+1个系数唯一确定。 因此，在计算机里，它可用一个线性表p来表示：,假设qm(x)是一元m次多项式，同样可用线性表q来表示：,表示成：,不失一般性，设nm，则两个多项式相加的结果rn(x) = pn(x) + qm(x)可用线性表r表示：,结论：对p、q和r采用顺序存储结构，使得多项式相加的算法定义十分简洁。,需要解决这样的问题： 在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。 比如：s(x)=1+3x10000+2x20000 就需要用一长度为20001的线性表来表示，表中仅有三个非零元素，这种对内存空间的浪费必须避免。 解决方法：在存储非零元素系数项则显然必须同时存储相应的指数。,其中，pi是指数为ei的项的非零系数，其满足 0 e1e2 em m,若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表 （p1, e1），（p2, e2），（pm, em） 便可唯一确定多项式pn(x)。