第2章线性表(MR)

数据结构,第2章线性表,2,学习重点,线性表的概念及表示方法线性表的顺序存储方式及操作的实现算法线性表的链式存储方式及操作的实现算法,3,线性结构,1结构中有且仅有一个“开始元素”，它没有前驱而仅有一个后继；2结构中有且仅有一个“最后元素”，它没有后继而仅有一个前驱；3除最后元素之外，均有唯一的后继；4除开始元素之外，均有唯一的前驱。,4,2.1线性表的逻辑结构,线性表是一种最简单的线性结构，线性表L是n（n0）个具有相同属性的数据元素a1,a2,an组成的有限序列，一个非空的线性表可表示为L=（a1，a2，ai，ai+1，an）其中，线性表中数据元素个数n称为线性表的长度，当n0时称为空表。ai(1in)是线性表的第i个元素，它后面的元素ai+1称为直接后继，前面的元素ai-1称为直接前驱。,5,2.1线性表的逻辑结构,线性表有以下特点：在非空的线性表中，存在唯一的一个被称为“第一个”的数据元素，又称为表头元素；存在唯一的一个被称为“最后一个”的元素，又称为表尾元素。线性表中数据的位置先后是有序的。除表头元素外，线性表中的每一个元素有且仅有一个前驱；除表尾元素外，线性表中的每一个元素有且仅有一个后继。表头元素只有一个后继而没有前驱，表尾元素只有一个前驱而没有后继。线性表中的数据的类型是相同的。表的长度n的取值是个有限数，最小为0。,6,例如：26个英文字母组成的字母表（A，B，C、Z）例如：,表2-1学生信息表,7,2.1.2线性表的基本运算,数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现则是建立在存储结构上的。(1)初始化线性表：InitList(L)构造一个空的线性表L，即表的初始化。(2)求线性表的长度GetLength(L)求表中结点的个数，即为求表的长度。,8,2.1.2线性表的基本运算,(3)按序号取元素:GetNode（L，i）读取线性表L第i个数据元素，要求满足1iGetLength(L)。(4)按值查找Locate(L,x)在L中查找值为x的结点，并返回该结点在L中的位置。若L中有多个结点的值和x相同，则返回首次找到的结点位置；若L中没有结点的值为x，则返回一个特殊值表示查找失败。,9,2.1.2线性表的基本运算,(5)在线性表中插入新元素：InsertList（L,i,e）在线性表L的第i个位置上插入一个值为e的新结点，使得原编号为i，i+1，n的结点变为编号为i+1，i+2，n+1的结点。这里1in+1，而n是原表L的长度。插入后，表L的长度加1。,10,2.1.2线性表的基本运算,（6）在线性表中删除元素：Delete（L，i）删除线性表L的第i个结点，使得原编号为i+1，i+2，n的结点变成编号为i，i+1，n-1的结点。这里1in，而n是原表L的长度。删除后表L的长度减1。（7）把已有线性表置为空表：ClearList（L）,11,2.2线性表的顺序结构及运算实现,2.2.1线性表的顺序存储结构2.2.2顺序表上基本运算的实现,12,2.2.1线性表的顺序存储结构,顺序存储方式是指在内存中开辟连续的存储单元，按元素的逻辑顺序依次存放在其中，即顺序存放线性表。特点：在逻辑上相邻的数据元素，它们的物理位置也是相邻。,例如：线性表（a1,a2,a3,an）,13,假设线性表中的第一个数据元素的存储地址（首地址）为LOC(a1)，每一个数据元素占k个字节，则各元素的存储地址有如下关系：LOC（a2）=LOC(a1)kLOC（a3）=LOC(a2)kLOC（ai）=LOC(ai-1)k（2in）因此，线性表中第i个元素ai在计算机中的存储地址为：LOC(ai)=LOC(a1)+(i-1)k（1in）,14,15,练习,已知一顺序表的起始地址为2650，顺序表长为100，每个元素占6个字节，求第11个元素的起始地址（其开始结点为第一个元素）。,16,2.2.1线性表的顺序存储结构,在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的序号惟一确定。也就是说，在线性表中只要确定了起始地址，任一元素均可随机存取。,17,在具体实现时，一般用高级语言中的数组来对应连续的存储空间。设最多可存储MaxLen个元素，在C语言中可用数组dataMaxLen来存储数据元素，为保存线性表的长度需定义一个整型变量length。线性表的第l，2，n个元素分别存放在此数组下标为0，1，length-1数组元素中，如下图所示:,18,这样，一个线性表的顺序存储结构需要两个分量。为体现数组data和length之间的内在联系，通常将它们定义在一个结构类型中。此处的元素类型用DataType来表示。综上所述，在C语言中可用下述类型定义来描述顺序表：#defineMaxLen100/线性表的容量typedefintDataType；typedefstructDataTypedataMaxLen;/定义存储表元素的数组intlength;/线性表的实际长度SeqList;SeqListL;/定义表结构的变量,19,2.2.2顺序表上基本运算的实现,1初始化顺序表InitList(L)的实现顺序表的初始化即构造一个空表，顺序表L是否为空取决于其元素个数是否为0，因此，只要将表L中的表长度置为0，就可以实现建空表的功能。voidInitList(SeqList*L)L-length=0;,20,2.2.2顺序表上基本运算的实现,2求线性表长度GetLength(L)的实现只要将表示线性表长度的length返回即可：intGetLength(SeqList*L)returnL-length;该算法的时间复杂度为O(1),21,2.2.2顺序表上基本运算的实现,3按序号取元素GetNode(L,i)的实现按前面的约定，序号为i的元素存储在数组下标为i-1的数组元素中，所以可直接从该数组元素中取得值。i的有效值应大于等于1和小于等于线性表的实际长度。,intGetNode(SeqList*L,inti)if(iL-length)printf(“positionerror”);exit(1);returnL-datai-1;,22,2.2.2顺序表上基本运算的实现,4查找运算Locate(L,e)的实现要确定值为e的元素在L表中的位置，需要依次比较各元素。当查询到第一个满足条件的数据元素时，返回其序号，否则返回-1，表示查找失败。,23,L.data,回顾顺序表的查找过程：,假设给定值e=64,要求L.datak=e,问:i=?,i,i,i,i,7,24,2.2.2顺序表上基本运算的实现,查找操作的具体实现算法如下：intLocate(SeqList*L,inte)inti=0;,if(ilength)returni;elsereturn-1;,while(ilength,25,2.2.2顺序表上基本运算的实现,查找运算Locate(L,e)的时间复杂度由算法可知，对于表长为n的顺序表，在查找过程中，数据元素比较次数最少为1，最多为n，元素比较次数的平均值为(n+1)/2，时间复杂度为O(n)。,26,2.2.2顺序表上基本运算的实现,5顺序表的插入算法InsertList(L,e,i)的实现顺序表的插入是指在表的第i个位置上插入一个值为e的新元素，插入后使原表长为n的表：(a1，a2，ai-1，ai，ai+1，an)，成为表长为n+1的表：(a1，a2，ai-1，e，ai，ai+1，an),i的取值范围为1in+1。,27,(a1,ai-1,ai,an)改变为(a1,ai-1,e,ai,an),28,voidInsertList(SeqList*L,Datatypee,inti)intj;if(iL-length+1)printf(“positionerror!”);/插入位置出错exit(1);,L-datai-1=e;/插入eL-length+;/表长度加1,for(j=L-length-1;j=i-1;j-)L-dataj+1=L-dataj;/数据元素后移,if(L-length=MaxLen)printf(“overflow!”);/表已满exit(1);,29,考虑移动元素的平均情况:,假设在第i个元素之前插入的概率为，则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：,若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：,30,2.2.2顺序表上基本运算的实现,6顺序表的删除运算DeleteList(L,i)的实现顺序表的删除运算是指将表中第i个元素从线性表中去掉，原表长为n的线性表(a1，a2，ai-1，ai，ai+1，an)。进行删除以后的线性表表长变为n-1的表(a1，a2，ai-1，ai+1，an)，i的取值范围为：1in。,31,(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,ai+1,an),ai+1,an,表的长度减少1,32,L.length-1,0,87,56,for(j=i;jlength-1;j+)L-dataj-1=L-dataj;,例如：DeleteList(SeqList*L,5),j,33,voidDeleteList(SeqList*L,inti)/删除线性表中第i个位置上的元素intj;if(iL-length)/检查空表及删除位置的合法性printf(“positionerror”);exit(1);,L-length-;,for(j=i;jlength-1;j+)L-dataj-1=L-dataj;/向前移动元素,34,考虑移动元素的平均情况:,假设删除第i个元素的概率为,则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为：,若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：,35,【例2-1】将顺序表（a1,a2,an）重新排列成以a1为界的两部分：a1前面的值均比a1小，a1后面的值均比a1大（这里假定数据类型具有可比性，例如整型），这一操作称为划分，a1也称为基准。,基本思路：从第二个元素开始到最后一个元素，逐一向后扫描，当数据元素ai比a1大时，表明它已经在a1的后面，不必改变其位置；当数据元素ai比a1小时，需要把它调整到a1前面去，把a1前面的元素依次向下移动一个位置，然后把它置于最上方。,36,voidpart(Seqlist*L)inti,j;DataTypex,yx=L-data0;for(i=1;ilength;i+)if(L-dataidatai;for(j=i-1;j=0;j-)L-dataj+1=L-dataj;L-data0=y;,作业（选作）,写一个程序完成基准划分：在线性表中，将第一个数据元素作为“枢轴”，凡表中元素小于枢轴的均移动至该元素之前，反之，凡表中元素大于枢轴的均移动至该元素之后。（可以参考教材P255算法9-5）,38,【例2-2】利用线性表的基本运算，编写在线性表A中删除线性表B中出现的元素的算法。,voiddelete(SeqList*A,SeqList*B)inti,k;DataTypex;for(i=1;i0)DeleteList(A,k);/若在线性表A中找到了，将其删除,39,线性表的顺序存储结构的特点,优点：顺序表中的任意数据元素的存储地址可由公式直接导出，因此顺序表可以随机存取其中的任意元素。,不足：（1）需预先分配相应的存储空间；存储空间不便于扩充。当一个线性表分配顺序存储空间后，若线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。（2）插入与删除运算的效率很低，插入、删除操作时需移动大量数据。,40,链表：,链表是动态进行存储分配的一种结构。若干数据(每个数据组称为一个结点)按一定的原则连接起来。,以上链表结构中只有一个方向的指针，因此又称为单链表，简称为链表。,41,1249,A,1356,B,1475,C,1021,D,NULL,head,1249,1356,1475,1021,简单的链表:,设置一指针变量，存放第一个结点的地址，称为头指针，一般以head命名。最后一个结点的地址项不指向任何结点，赋以值NULL。,链表中每一个元素称为一个结点,结点是一组数据,包括用户需要的实际数据和下一个结点的地址。,前一个结点指向下一个结点,只有通过前一个结点才能找到下一个结点。,structstudentintnum;charname10;chardepartment20;structstudent*next;,43,malloc函数函数原型：作用:,void*malloc(unsignedintsize)；,在内存的动态存储区中分配一个长度为size的连续存储空间。其中，形参size为无符号整数，是函数malloc要求分配存储空间的字节个数。函数返回值为一个指针，它指向所分配存储空间的起始地址。若函数返回值为0，则表示未能成功申请到内存空间。函数类型为void，表示返回的指针不指向任何具体的类型.,44,malloc函数malloc函数的使用:,malloc(8)开辟长度为8个字节的存储空间,若其起始地址为1268,则malloc(8)的返回值为1268,且返回的指针值指向void型.将此地址赋给一个指向long型的指针变量:p=(long*)malloc(8);,long*lp；lp=(long*)malloc(12)；head=(structstudent*)malloc(sizeof(structstudent)；,45,函数free:函数的原型:函数作用:函数的使用:,voidfree(void*ptr)；,释放由指针变量ptr为所指示的内存区域。其中，ptr一个指针变量，指向最近一次调用函数malloc或calloc时所分配的连续存储空间的首地址。通过函数free将已分配的内存区域交还系统，使系统可以重新对其进行分配。,long*p；p=(long*)malloc(8)；.free(p)；,46,2.3线性表的链式存储和运算实现,2.3.1链表的存储结构2.3.2单向链表2.3.3循环链表2.3.4双向链表2.3.5循环双链表2.3.6静态链表,47,用一组地址任意的存储单元存放线性表中的数据元素。,2.3.1链表的存储结构,以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素或数据元素的映象),采用链式存储结构表示的线性表称作链表,48,以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。,空指针,线性表为空表时，头结点的指针域为空,49,typedefstructnodeDataTypedata;/数据域structnode*next;/指针域ListNode,*LinkList;,结点和单链表的C语言描述,LNode*Head；,50,例:假设有一个线性表为（A,B,C,D,E），存储空间具有10个存储结点，该线性表在存储空间中的存储情况如图所示。,图链表结构示意图,51,2.3.2单向链表,单链表分为带头结点和不带头结点两种类型。对于空链表，头结点的指针域为空。图2-5是带头结点的链表示方式：,图2-5（a）为带头结点的空链(b)为带头结点的单链表,52,1.建立单链表,头插法建表尾插法建表,53,头插法建表,LinkListCreatListF(void)/*返回单链表的头指针*/charch;ListNode*s;/*结点指针*/LinkListhead=(ListNode*)malloc(sizeof(ListNode);head-next=NULL;ch=getchar();/*读入第1个字符*/while(ch!=n)s=(ListNode*)malloc(sizeof(ListNode);s-data=ch;/*将读入的数据放入新结点的数据域中*/s-next=head-next;head-next=s;ch=getchar();returnhead;,ListNode*,ListNode*,54,尾插法建表,LinkListCreatListR1(void)/*用尾插法建立的单链表*/charch;ListNode*s,*r;/*结点指针*/LinkListhead=(ListNode*)malloc(sizeof(ListNode);r=head;/*尾指针初值也指向头结点*/ch=getchar();/*读入第1个字符*/while(ch=getchar()!=n)s=(ListNode*)malloc(sizeof(ListNode);s-data=ch;/*将读入的数据放入新结点的数据域中*/r-next=s;r=s;r-next=NULL;returnhead;,55,练习:求线性表长度GetLength(L)的实现设计思路：设置一个初值为0的计数器变量和一个跟踪链表结点的指针p。初始时p指向链表中的第一个结点，然后顺着next域依次指向每个结点，每指向一个结点计数器变量加1。当p为NULL时，结束该过程。其时间复杂度为O(n)。,56,算法如下:intGetLength(LinkListL)intnum=0;ListNode*p;p=L-next;while(p!=NULL)num+;p=p-next;return(num);,时间复杂度为O(n)。,57,2.单链表的查找运算,按序号查找元素按值查找,58,按序号取元素GetNode(L,i)的实现根据前面的讨论，对单链表中的结点只能顺序存取，即访问前一个结点后才能接着访问后一个结点，所以要访问单链表中第i个元素值，必须从头指针开始遍历链表，依次访问每个结点，直到访问到第i个结点为止。同顺序表一样，也需注意存取的位置是否有效。,59,线性表的操作:GetNode(L,i)在单链表中取出第i个元素,若第i个元素存在则用函数名返回,否则返回Null,返回,1,2,结点p,j,3,GetNode(L,3),60,因此，查找第i个数据元素的基本操作为：移动指针，比较j和i。,单链表是一种链式存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。,不断移动指针p,同时j不断加1。,61,ListNode*GetNode(LinkListL,inti)ListNode*p;intj;,if(iGetLength(L)exit(1);,p=L-next;j=1;while(p!=NULL,时间复杂度为O(n)。,62,按值查找运算Locate(L,x)的实现设置一个跟踪链表结点的指针p，初始时p指向链表中的第一个结点，然后顺着next域依次指向每个结点，每指向一个结点就判断其值是否等于x，若是则返回该结点地址。否则继续往后搜索，直到p为NULL，表示链表中无此元素，返回NULL。其时间复杂度为O(n)。,63,线性表的操作:Locate(L,x)在单链表中查找值为x的元素,若找到了，则返回该元素的地址，否则返回Null,Locate(L,30),returnp;,64,线性表的操作:locate(L,x)在单链表中查找值为x的元素,若找到了，则返回该元素的地址，否则返回Null,locate(L,90),p=p-next;returnp;,65,ListNode*Locate(LinkListL,DataTypex)LNode*p=L-next;,while(p,时间复杂度为O(n)。,p!=NULL,66,3链表的插入算法InsertList(L,x,i)的实现单链表结点的插入是利用修改结点指针域的值，使其指向新的结点位置来完成的插入操作，而无需移动任何元素。,67,线性表的操作InsertList(L,x,i)在单链表中的实现：,有序对改变为和,68,因此，在单链表中第i个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。,可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。,69,链表的插入算法,具体步骤：找到ai-1存储位置*q,并*p指向结点ai生成一个数据域为x的新结点*s新结点的指针域指向结点ai(即*p)令结点*q的指针域指向新结点,70,voidInsertList(LinkListhead,DataTypex,inti)LNode*p,*q,*s;intj=1;p=head;,if(iGetLength(head)+1)exit(1);,while(jnext;j+;,71,s=(ListNode*)malloc(sizeof(ListNode);/生成新结点s-data=x;s-next=q-next;q-next=s;/插入,s,q,p,算法的时间复杂度为:,O(n),72,4链表的删除运算DeleteList(head,i)的实现在单链表中找到删除位置前一个结点，并用指针p指向它指针q指向要删除的结点将*p的指针域修改为待删除结点*q的后继结点的地址删除后的结点需动态的释放。,73,线性表的操作deleteList(L,i)在链表中的实现:,有序对和改变为,74,在单链表中删除第i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。,q=p-next;p-next=q-next;free(q);,p,q,75,voidDeleteList(LinkListhead,inti)ListNode*q,*p;intj=1;p=head;,算法的时间复杂度为:,O(n),if(iGetLength(head)exit(1);,q=p-next;p-next=q-next;free(q);,while(jnext;j+;,76,练习:链表元素输出运算DispList(L)的实现从第一个结点开始，顺着指针链依次访问每一个结点并输出。,voidDispList(LinkListL)ListNode*p;p=L-next;while(p!=NULL)printf(%4d,p-data);p=p-next;printf(n);,时间复杂度为O(n)。,77,【例2-3】已知单链表L，写一算法，删除其重复结点。,算法思路：用指针p指向第一个数据结点，从它的后继结点开始到表的结束，找与其值相同的结点并删除；p指向下一个，依此类推，p指向最后结点时算法结束。,78,【算法2-15】删除单链表中的重复结点voiddelete_list(LinkListL)ListNode*p,*q,*s;p=L-next;/*p指向头结点之后的第一个结点*/if(p=NULL)exit(1)；while(p-next!=NULL)q=p;while(q-next)/*从*p的后继开始找重复结点*/if(q-next-data=p-data)s=q-next;q-next=q-next-next;free(s);elseq=q-next;p=p-next;,while(q-next!=NULL),算法的时间复杂度是0(n2),79,最后一个结点的指针域的指针又指回第一个结点的链表,a1a2.an,2.3.2循环链表,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,80,练习：求循环链表长度GetLength(L)的实现设计思路：设置一个初值为0的计数器变量和一个跟踪链表结点的指针p。初始时p指向链表中的第一个结点，然后顺着next域依次指向每个结点，每指向一个