900第2章 线性表.ppt

第2章 线性表,2.1 线性表的概念和基本操作2.2 线性表的顺序存储结构2.3 线性表的链式存储结构2.4 线性表两种存储方式的比较 2.5 应用举例分析,本章要点,线性表的两种存储方式顺序表和单链表的插入、查找、删除操作及效率分析双向链表、循环链表线性表两种存储方式的比较,本章难点,单链表的存储方式及各种操作线性表的两种存储方式的比较,学习目标,掌握线性表的定义和各种操作掌握线性表的两种种存储方式掌握顺序表、单链表、循环链表、双向链表,2.1 线性表的概念和基本操作,线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为：(a1，a2，ai-1，ai，ai+1，an)，其中n为表长，n0时称为空表。表中相邻元素之间存在着顺序关系。将ai-1称为ai的直接前驱，ai+1称为ai的直接后继。,线性表上的基本操作有：（1）INIT_LIST(L)线性表初始化，当表L不存在时，构造一个空的线性表。（2）LENGTH_LIST(L)求线性表的长度，当表L存在时，返回线性表中的所含元素的个数。（3）GET_LIST(L,i)取表元，当表L存在且1iLength_List(L)时，返回线性表L中的第个元素的值或地址。（4）LOCATE_LIST(L,x)按值查找，是给定的一个数据元素。当线性表L存在时，在表L中查找值为的数据元素，其结果返回在L中首次出现的值为的那个元素的序号或地址，称为查找成功；否则，即在L中未找到值为的数据元素时，返回一特殊值表示查找失败。,2.1 线性表的概念和基本操作,（5）INSERT_LIST(L,i,x)插入操作，当线性表L存在，插入位置正确(1in+1,为插入前的表长)时，在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i,i+1,.,n 的数据元素的序号变为 i+1,i+2,.,n+1，插入后表长=原表长+1。（6）DELETE_LIST(L,i)删除操作，当线性表L存在，1in时，在线性表L中删除序号为i的数据元素，删除后使序号为 i+1,i+2,.,n 的元素变为序号为 i,i+1,.,n-1，新表长原表长-。,2.1 线性表的概念和基本操作,2.2 线性表的顺序存储结构,2.2.1 顺序表的定义线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。,线性表的顺序存储示意图,第i个数据元素的地址为：Loc(ai)=Loc(a)+(i-1)*d 1in从结构性上考虑，通常将data和last封装成一个结构体作为顺序表的类型，具体描述如下表示：,2.2.1 顺序表的定义,#define MAXSIZE 100#define datatype int typedef struct datatype dataMAXSIZE;int last;SEQLIST;,2.2.1 顺序表的定义,顺序表的初始化问题，顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为指针参数，首先动态分配存储空间，然后，将表中 last 设置为0，表示表中没有数据元素。算法如下：SEQLIST*init_seqlist()SEQLIST*L;L=(SEQLIST*)malloc(sizeof(SEQLIST);L-last=0;return L;,2.2.1 顺序表的定义,线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长为 n的表(a1，a2，.，ai-1，ai，ai+1，.，an)成为表长为 n+1表(a1，a2，.，ai-1，x，ai，ai+1，.，an)。i 的取值范围为1in+1。步骤如下：将aian 顺序向下移动，为新元素让出位置；将 x 置入空出的第i个位置；修改 last 指针(相当于修改表长)，使之增加1。,2.2.2 顺序表上元素的插入,算法如下：int insert_seqlist(SEQLIST*L，int i，datatype x)int j;if(L-last=MAXSIZE)printf(表已满);return(-1);/*表空间已满，不能插入*/if(i L-last+1)/*检查插入位置的正确性*/printf(位置错);return(0);,2.2.2 顺序表上元素的插入,for(j=L-last;j=i;j-)L-dataj=L-dataj-1;/*结点依次向后移动*/L-datai-1=x;/*新元素插入*/L-last+;/*last仍指向最后元素*/return(1);/*插入成功，返回*/,2.2.2 顺序表上元素的插入,设在第i个位置上作插入的概率为pi，则平均移动数据元素的次数：设：pi=1/(n+1)，即为等概率情况，则：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为(n),2.2.2 顺序表上元素的插入,顺序表上元素的删除 线性表的删除运算是指将表中第 i 个元素从线性表中去掉，删除后使原表长为 n 的线性表(a1，a2，.，ai-1，ai，ai+1，.，an)成为表长为 n-1 的线性表(a1，a2，.，ai-1，ai+1，.，an)。i 的取值范围为：1in。顺序表上完成这一运算的步骤如下：将ai+1an 顺序向上移动。修改last指针（相当于修改表长），使之减1。,2.2.2 顺序表上元素的删除,顺序表上元素的定位 顺序表上元素的定位主要为按值查找，按值查找是指在线性表中查找与给定值x相等的数据元素。在顺序表中完成该运算最简单的方法是：从第一个元素 a1 起依次和x比较，直到找到一个与x相等的数据元素，则返回它在顺序表中的存储下标或序号（二者差一）；或者查遍整个表都没有找到与 x 相等的元素，返回0。,2.2 线性表的顺序存储定位,2.3 线性表的链式存储结构,顺序表的存储特点是用物理上的相邻实现了逻辑上的相邻，它要求用连续的存储单元顺序存储线性表中各元素，因此，对顺序表插入、删除时需要通过移动数据元素来实现，影响了运行效率。本节介绍线性表链式存储结构，它不需要用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系来，因此对线性表的插入、删除不需要移动数据元素。,单链表的定义 为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继ai+1所在的存储单元的地址，这两部分信息组成一个“结点”，结点的结构如图所示每个元素都如此。存放数据元素信息的称为数据域，存放其后继地址的称为指针域。n个元素的线性表通过每个结点的指针域拉成了一个“链子”，称之为链表。因为每个结点中只有一个指向后继的指针，所以称其为单链表。,2.3.1 单链表的定义和操作实现,链表是由一个个结点构成的，结点定义如下：typedef struct node datatype data;struct node*next;LINKLIST；作为线性表的一种存储结构，我们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心，所以通常的单链表用下图表示。,2.3.1 单链表的定义和操作实现,建立单链表（1）头插入法建立链表 链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求而生成的，因此建立单链表从空表开始，每读入一个数据元素则申请一个新结点，然后将此结点放在链表中已有结点的前面，作为新链表的第一个结点，因此称为头部插入法。如图所示：,2.3.1 单链表的定义和操作实现,算法如下：LINKLIST*creat_linklist1()LINKLIST*H=NULL；/*空表*/LINKLIST*s;int x;/*设数据元素的类型为int*/scanf(%d,头插入建立单链表简单，但读入的数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插入的方法。,2.3.1 单链表的定义和操作实现,（2）尾插入建立链表 尾插入算法建立链表的过程和头插入法正好相反，它每次都将新结点放在已有链表的最后面，成为新链表的尾结点。因为每次是将新结点插入到链表的尾部，需要先找到旧链表的尾结点，然后才能将新结点放在其后面，所以为了提高程序效率，需加入一个指针 r 用来始终指向链表中的尾结点，以便能够将新结点快速插入到链表的尾部。,2.3.1 单链表的定义和操作实现,算法如下：LINKLIST*creat_linklist2()LINKLIST*L=NULL;LINKLIST*s,*r=NULL;int x;/*设数据元素的类型为int*/scanf(%d,2.3.1 单链表的定义和操作实现,头结点 在上面的算法中，第一个结点的处理和其它结点是不同的，原因是第一个结点加入时链表为空，它没有直接前驱结点，它的地址就是整个链表的指针，需要放在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。为了方便操作，有时在链表的头部加入一个“头结点”，头结点的类型与数据结点一致，标识链表的头指针变量L中存放该结点的地址，这样即使是空表，头指针变量L也不为空了。头结点的加入使得“第一个结点”的问题不再存在，也使得“空表”和“非空表”的处理成为一致。下图是带头结点的单链表空表和非空表的示意图。,2.3.1 单链表的定义和操作实现,单链表求表长 算法思路：设一个移动指针和计数器，初始化后，所指结点后面若还有结点，向后移动，计数器加1。（1）设L是带头结点的单链表（线性表的长度不包括头结点），求表长的算法如下：int length_linklist1(LINKLIST*L)LINKLIST*p=L;/*p指向头结点*/int j=0;while(p-next)p=p-next;j+；/*p所指的是第 j 个结点*/return j;,2.3.1 单链表的定义和操作实现,（2）设L是不带头结点的单链表，求表长的算法如下：int Length_linklist2(LINKLIST*L)LINKLIST*p=L;int j;if(p=NULL)return 0;/*空表的情况*/j=1;/*在非空表的情况下，p所指的是第一个结点*/;while(p-next)p=p-next;j+;return j;不带头结点的单链表空表情况要单独处理。两个算法的时间复杂度均为O(n)。,2.3.1 单链表的定义和操作实现,单链表查找操作 单链表的查找分为按序号查找和按值查找（1）按序号查找 GET_LINKLIST(L,i)算法思路：从链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，表结束为止；没有第个结点时返回空。算法如下：LINKLIST*get_linklist(LINKLIST*L,int i);/*在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/LINKLIST*p=L;int j=0;while(p-next!=NULL,2.3.1 单链表的定义和操作实现,（2）按值查找即定位 LOCATE_LINKLIST(L,x)算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于x，若是，返回该结点的指针，否则继续后一个，表结束为止；找不到时返回空。算法如下：LINKLIST*Locate_linklist(LINKLIST*L,datatype x)/*在单链表L中查找值为x的结点，找到后返回其指针，否则返回空*/LINKLIST*p=L-next;while(p!=NULL 在单链表中查找元素的两种操作的时间复杂度均为O(n)。,2.3.1 单链表的定义和操作实现,单链表插入操作（1）后插结点 设p指向单链表中某结点，s指向待插入的值为x的新结点，将s插入到p的后面，插入示意图如图，操作如下：s-next=p-next;p-next=s;,2.3.1 单链表的定义和操作实现,（2）前插结点 设指向链表中某结点，指向待插入的值为x的新结点，将s插入到p的前 面，插入示意图如图，与后插不同的是：首先要找到p的前驱q，然后再完 成在q之后插入s，设单链表头指针为L。算法思路（此算法描述在链表第i个位置前插入元素x）：找到第i-1个结点；若存在继续，否则结束。申请、填装新结点；将新结点插入，结束。,2.3.1 单链表的定义和操作实现,单链表删除操作 删除结点：设p指向单链表中某结点，删除p，操作示意图如图所示。通过示意图可见，要实现对结点p的删除，首先要找到p的前驱结点q，然后完成指针的操作即可。算法思路（此算法描述删除第i个结点）：找到第i-1个结点；若存在继续，否则结束；若存在第i个结点则继续，否则结束；删除第i个结点，结束。,2.3.1 单链表的定义和操作实现,循环链表定义和操作实现 对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表，如图所示。当循环链表为空时，仅有头节点，并且头节点的指针域指向头节点自身。,非空表,空表,使用尾指针R标识的循环链表,2.3.2 循环链表定义和操作实现,对两个单循环链表H1、H2的连接操作，是将H2的第一个数据结点接到H1的尾结点，如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)，而链表若用尾指针R1、R2来标识，则时间性能为O(1)。操作如下：p=R1 next;/*保存R1 的头结点指针*/R1-next=R2-next-next;/*头尾连接*/free(R2-next);/*释放第二个表的头结点*/R2-next=p;/*组成循环链表*/这一过程可见下图。,2.3.2 循环链表定义和操作实现,双向链表定义和操作实现 以上讨论的单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为p，其后继结点的指针则为p-next，而找其前驱则只能从该链表的头指针开始，顺着各结点的next域进行，也就是说找后继的时间性能是O(1)，找前驱的时间性能是O(n)，如果也希望找前驱的时间性能达到O(1)，则只能付出空间的代价：每个结点再加一个指向前驱的指针域，结点的结构为如下图所示，用这种结点组成的链表称为双向链表。,2.3.2 循环链表定义和操作实现,2.3.3 双向链表定义和操作实现,双向链表结点的定义如下：typedef struct dlnode datatype data;struct dlnode*prior,*next;DLINKLIST;,和单链表类似，双向链表通常也是用头指针标识，也可以带头结点做成循环结构，下图是带头结点的双向循环链表示意图。显然通过某结点的指针p即可以直接得到它的后继结点的指针p-next，也可以直接得到它的前驱结点的的指针p-prior。这样在有些操作中需要找前驱时，则无需再用循环。,非空表,空表,2.3.3 双向链表定义和操作实现,双向链表中结点的插入 设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，插入如下图所示。操作如下：s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;,2.3.3 双向链表定义和操作实现,双向链表中结点的删除 设p指向双向链表中某结点，删除*p。操作示意图如下图所示。操作如下：p-prior-next=p-next;p-next-prior=p-prior;free(p);,2.3.3 双向链表定义和操作实现,2.4 线性表两种存储方式的比较,顺序存储的优点：方法简单，各种高级语言中都有数组，容易实现。不用为表示结点间的逻辑关系而增加额外的存储开销。顺序表具有按元素序号随机访问的特点。顺序结构的缺点：在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反。,在实际中选取存储结构基于以下几点考虑：（1）基于存储的考虑（2）基于运算的考虑（3）基于环境的考虑,2.4 线性表两种存储方式的比较,2.5 应用举例分析,例1 一元多项式相加。数学上，n阶一元多项式可以用下面的式子表示：A(x)=anxn+an-1xn-1+a1x1+a0 x0(a0),A(x)的阶数为n。一个n阶一元多项式中含有n+1项系数，并惟一确定，分别对应xn的系数到x0的系数。在计算机中，描述一个一元多项式，可用线性表表示 A=(n,an,an-1,an-2,a1,a0)，其中第一个元素是阶数，后面都是系数，按阶次逐一递减排列，A的长度是n+2。数学上，一元多项式的另一种表示方法是：A(x)=bx+bx+bx,式中每一项都是非零系数项，bi是非零系数，ei具有递减性。这种表示法对稀疏型多项式特别适合。在计算机中，可用线性表表示 A=(m,em,bm,em-1,bm-1,e1,b1)，其中第一个元素是多项式中非零系数的项数，后面是每个项对应的阶次和系数，每两项ei,bi对应多项式中的某一非零系数项的指数和系数，A的长度是2m+1。试用第二种表示方法写出多项式相加的算法,例2 有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。,2.5 应用举例分析,例3 将所有在顺序表lb中存在而在顺序表la中不存在的数据元素插入到la表中。这个例子实现的思路是：从顺序表lb中依次取出每一个元素，并在顺序表la中查访，若在la表中不存在，则可插到la表中。而且每个插入到la中的元素均统一规定插在la表的尾部，这样可节省算法执行的时间。过程中的查访和插入可调用前面的locate和insert函数。,2.5 应用举例分析,例4 写出一个计算链表（此链表带头结点）中结点个数的算法，并依次打印出链表中元素的值。例5 将一个用单链表存储的线性表T=(a1,a2,am-1,am)置换成T=(am,am-1,a2,a1。例6 已知单链表L，写一算法，删除其重复结点。例7 写出双向链表中逻辑交换结点a和b的算法,2.5 应用举例分析,本章小结,本章主要讲解了线性表的基本概念和两种存储方式。介绍了顺序表，单链表，循环链表，双向链表等概念。1.顺序表：线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。2.单链表：链表是通过一组任意的存储单元来存储线性表中的数据元素的。为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继ai+1所在的存储单元的地址，这两部分信息组成一个“结点”。n个元素的线性表通过每个结点的指针域拉成了一个“链子”，称之为链表。,本章小结,3.循环链表：在单链表的基础之上，将链表头指针置入最后一个结点的指针域，使得链表头尾结点相连，就构成了单循环链表。4.双向链表：在单链表的基础之上，每个结点再加一个指向前驱的指针域，用这种结点组成的链表称为双向链表。两种存储方式的比较：顺序表存储方法简单，各种高级语言中都有数组，容易实现。不用为表示结点间的逻辑关系而增加额外的存储开销。具有按元素序号随机访问的特点。链表做插入删除操作时，效率较高。对内存的分配灵活，高效。应根据具体存储要求决定表的存储方式。,