资源描述
第二章线性表,2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4顺序表与链表的比较,线性表(LinearList)：由n(n)个数据元素(结点)a1，a2，an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)。记作：(a1，a2，an)这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。,2.1线性表的类型定义,例1、26个英文字母组成的字母表（A，B，C,Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）,2.1线性表的类型定义,例3、学生健康情况登记表如下：,2.1线性表的类型定义,例4、一副扑克的点数（2，3，4，J，Q，K，A）,2.1线性表的类型定义,从以上例子可看出线性表的逻辑特征是：在非空的线性表中，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。,线性表的特点同一性：线性表中所有元素的性质相同有序性：除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱，最后一个数据元素无后继有穷性：数据元素在表中的位置只取决于它自身的序号，序号不可能无穷，故元素个数不可能无穷,2.1线性表的类型定义,抽象数据类型（ADT）的表示ADT数据对象：结构关系：基本操作：ADT/（参数表）操作前提：操作结果：,2.1线性表的类型定义,线性表的抽象数据类型定义,ADTLinearList数据元素:D=ai|aiD0,i=1,2,n,n0,D0为某一数据对象结构关系:S=|ai,ai+1D0,I=1,2,n-1基本操作:(1)InitList(L)/初始化操作前提:L为未初始化线性表操作结果:将L初始化为空表(2)DestroyList(L)/删除表操作前提:线性表L已存在操作结果:将L销毁(3)ClearList(L)/内容清空操作前提:线性表L已存在操作结果:将表L置为空表,(4)EmptyList(L)/判空操作前提:线性表L已存在操作结果:如果L为空表则返回真,否则返回假(5)ListLength(L)/求长度操作前提:线性表L已存在操作结果:如果L为空表则返回0,否则返回表中的元素个数(6)Locate(L,e)/检索操作前提:表L已存在,e为合法元素值操作结果:如果L中存在元素e,则将“当前指针”指向e所在位置并返回真,否则返回假(7)GetData(L,i)/取元素操作前提:表L已存在,且i值合法,即1iListLength(L)操作结果:返回线性表L中第i个元素的值,线性表的抽象数据类型定义,(8)InsList(L,i,e)/插入(前插)操作前提:表L已存在,e为合法元素值且1iListLength(L)+1操作结果:将表L中第i个位置插入新的数据元素e,L的长度加1(9)DelList(L,i,/*V是数组的名字，假设数组中的元素是整型类型*/,第i个元素的ai存储地址：Loc(ai)=Loc(a1)+(i-1)*m,V,V,Vi,Vm-1,2.2.1顺序表的存储结构,由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。,2.2.1顺序表的存储结构,#defineMAXSIZE100/*线性表可能达到的最大长度为100*/typedefintelemtype;typedefstructelemtypeelemMAXSIZE;/*线性表占用的数组空间*/intlen;/*线性表实际长度，这里记录线性表中最后一个元素在数组elem中的位置（下标值），空表置1*/Sqlist;,2.2.1顺序表的存储结构,#defineMAXSIZE100typedefstructelemtypeelemMAXSIZE;intlen;Sqlist;,2.2.1顺序表的存储结构,在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.elemi-1。,2.2.2顺序表上实现的基本操作,顺序表的初始化顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为指针参数，首先动态分配存储空间，然后，将表中len指针置为0，表示表中没有数据元素。算法如下：,2.2.2顺序表上实现的基本操作,Sqlist*init_Sqlist()Sqlist*L;L=(Sqlist*)malloc(sizeof(Sqlist);L-len=0;returnL;设调用函数为主函数，主函数对初始化函数的调用如下：main()Sqlist*L;L=Init_Seqlist();,顺序表的初始化,按序号查找注意：元素标号与数组的下标之间的关系,Elem0,Elem1,Elemi-1,Elemn-1,2.2.2顺序表上实现的基本操作,Locate（L，x）：查找顺序表中是否含有与x值相同的元素,x,按内容查找,x,按内容查找,x,如果x和ai-1相同，则找到并停止查找；否则按照前面的步骤继续下去,按内容查找,x,如果此时仍然没有找到，返回错误并停止,有关算法及程序在“查找”一章中介绍,按内容查找,intLocation_Sqlist(Sqlist*L,elemtypex)inti=0;while(ilen/*返回的是存储位置*/,按内容查找,以下主要讨论线性表的插入和删除两种运算。1、插入线性表的插入运算是指在表的第i(1in+1)个位置上，插入一个新结点x，使长度为n的线性表(a1，ai-1，ai，an)变成长度为n+1的线性表(a1，ai-1，x，ai，an),2.2.2顺序表上实现的基本操作,.,a2,a1,an,.,ai+1,ai,0,1,i-1,i,ai-1,.,a2,a1,alen,ai+1,ai,x,x,n-1,插入运算,顺序表上完成这一运算通过以下步骤进行：(1)将aian顺序向下移动，为新元素让出位置；(2)将x置入空出的第i个位置；(3)修改表长。,插入运算,intInsList(Sqlist*L,inti,intx)/*在线性表V中第i个元素之前插入x，i的合法值为1iL-len+1*/intk;if(iL-len+1)printf(“LocateError!”);return0;/*位置i值不合法*/if(L-len=MAXSIZE)printf(Filled!);return(ERROR);for(k=L-len-1;k=i-1;k-)L-elemk+1=L-elemk;/*插入位置后的元素依次右移*/L-elemi-1=x;/*插入x*/L-len+;/*表长加1*/return1;,注意数组元素从0开始,插入运算,main()/*顺序表插入的主函数*/Sqlist*a;Sqlistm;intn,x,k;scanf(“%d”,插入运算,本算法中注意以下问题：(1)顺序表中数据区域有MAXSIZE个存储单元，所以在向顺序表中做插入时先检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。(2)要检验插入位置的有效性，这里i的有效范围是：1elemi-1;for(k=i;klen;k+)L-elemk-1=L-elemk;/*被删除元素之后的元素左移*/L-len-;/*表长减1*/return1;,删除运算,本算法注意以下问题：（1）删除第i个元素，i的取值为1len的值为0，条件（iL-len）也包括了对表空的检查。（3）删除ai之后，该数据将不存在，如果需要可先取出ai，再做删除。,删除运算,该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若i=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故Ede(n)=pi(n-i),删除算法的时间性能分析：,删除运算,式中，pi表示删除表中第i个结点的概率。在等概率的假设下，p1=p2=p3=pn=1/n由此可得：Ede(n)=(n-i)/n=(n-1)/2即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。,删除运算,3、顺序表的应用例：将有序线性表La=2,4,6,7,9，Lb=1,5,7,8，合并为Lc=1,2,4,5,6,7,7,8,9。,分析：Lc中的数据元素或者是La中的数据元素，或者是Lb中的数据元素，则只要先将Lc置为空表，然后将La或Lb中的元素逐个插入到Lc中即可。设两个指针i和j分别指向La和Lb中的某个元素，若设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到Lc中的元素c为c=，当时；，当时，很显然，指针i和j的初值均为1，在所指元素插入Lc后，i，j在La或Lb中顺序后移。,2.2.2顺序表上实现的基本操作,线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。也就是说定位操作可以直接实现。高级程序设计语言提供的数组数据类型可以直接定义顺序存储结构的线性表，使其程序设计十分方便。,顺序表存储结构的特点,但是，顺序存储结构也有一些不方便之处，主要表现在：（1）数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间。（2）插入与删除运算的效率很低。为了保持线性表中的数据元素的顺序，在插入操作和删除操作时需移动大量数据。这对于插入和删除操作频繁的线性表、以及每个数据元素所占字节较大的问题将导致系统的运行速度难以提高。（3）顺序存储结构的线性表的存储空间不便于扩充。当一个线性表分配顺序存储空间后，如果线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。在这种情况下，如果在原线性表的存储空间后找不到与之连续的可用空间，则会导致运算的失败或中断。,线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(LinkedList)。,2.3.1线性表的链式表示(线性链表)和实现,链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构,2.3.1线性链表,其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结点只有一个链域，故将这种链表称为单链表（SingleLinked)。显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即null（图示中也可用表示)。,2.3.1线性链表,110130135160头指针head165170200205,2.3.1线性链表,例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat)的单链表示意图如右：,单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。,例如：若头指针名是head，则把链表称为表head。,head,2.3.1线性链表,typedefcharelemtype;typedefstructnodeelemtypedata;structnode*next;NODE，*NODEPTR;NODE*p；,用C语言描述的单链表结构定义如下：,2.3.1线性链表,注意区分指针变量和结点变量这两个不同的概念。P为动态变量，它是通过标准函数生成的，即p=(NODE*)malloc(sizeof(NODE);函数malloc分配了一个类型为NODE的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数free(p)；释放所指的结点变量空间。注意：指针变量P和（其值为结点地址）结点变量*P之间的关系。,2.3.1线性链表,L,.,带头结点的单链表,头结点,头指针,相关概念,头结点在第一个结点之前附设的一个结点，该结点的数据域可以存储附加信息，也可以什么都没有头指针永远指向头结点的指针空链表,L,2.3.1线性链表,一、建立单链表假设线性表中结点的数据类型是字符型，我们逐个输入这些字符型的结点，并以换行符n为输入结束标记。动态地建立单链表的常用方法有如下两种：头插法建表尾插法建表,2.3.1线性链表,P,P,S,在P所指向的结点之后插入新的结点,S,单链表的插入,s-next=p-next;p-next=s;,s,s,该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。,snext=head-next;head-next=s;,头插法建表,NODEPTRcreatefromhead()charch;NODEPTRhead;NODE*p;head=(NODEPTR)malloc(sizeof(NODE);head-next=NULL;ch=getchar();while(ch!=n）p=(NODE*)malloc(sizeof(NODE);pdata=ch;pnext=head-next;head-next=p;ch=getchar();return(head);,头插法建表,头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。,尾插法建表,尾插法建表,L,r,L,S,头指针,头结点,增加一个结点,L,S,r,r,If(c!=$)s=(NODE*)malloc(sizeof(NODE);/*用来创建一个新结点*/s-data=c;r-next=s;/*r永远指向链表的最后一个结点*/r=s;elseflag=0;/*设置的标志变量，表示建表结束，当输入“$”时结束建表*/r-next=NULL;/*将最后一个结点的next链域置为空，表示链表的结束*/,尾插法建表,P,P,L,S,二、插入运算,InsLinkList(NODE*p,intx)/*在P所指向的结点之后插入新的结点，新结点的内容为x*/NODE*s;/*定义指向结点类型的指针*/s=(NODE*)malloc(sizeof(NODE);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,二、插入运算,P,L,InsLinkList(NODE*p,intx)/*在P所指向的结点之后插入新的结点*/NODE*s;/*定义指向结点类型的指针*/s=(NODE*)malloc(sizeof(NODE);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,二、插入运算,P,L,InsLinkList(NODE*p,intx)/*在P所指向的结点之后插入新的结点*/NODE*s;/*定义指向结点类型的指针*/s=(NODE*)malloc(sizeof(NODE);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,S,二、插入运算,P,L,InsLinkList(NODE*p,intx)/*在P所指向的结点之后插入新的结点*/NODE*s;/*定义指向结点类型的指针*/s=(NODE*)malloc(sizeof(NODE);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,S,二、插入运算,P,L,InsLinkList(NODE*p,intx)/*在P所指向的结点之后插入新的结点*/NODE*s;/*定义指向结点类型的指针*/s=(NODE*)malloc(sizeof(NODE);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,S,二、插入运算,P,L,InsLinkList(NODE*p,intx)/*在P所指向的结点之后插入新的结点*/NODE*s;/*定义指向结点类型的指针*/s=(NODE*)malloc(sizeof(NODE);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,二、插入运算,DelLinkList(NODE*p)/*删除p指针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,三、删除运算,L,p,DelLinkList(NODE*p)/*删除p指针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,q,三、删除运算,L,p,DelLinkList(NODE*p)/*删除p指针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,三、删除运算,L,p,q,DelLinkList(NODE*p)/*删除p指针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,三、删除运算,L,p,q,DelLinkList(NODE*p)/*删除p指针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,三、删除运算,L,p,DelLinkList(NODE*p)/*删除p指针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,三、删除运算,按内容查找：设含有表头结点的单链表的头指针为L,沿着链表的开始往后找结点x，若找到，则返回该结点在链表中的位置，否则返回空地址按序号查找：设含有表头结点的单链表的头指针为L，沿着链表的开始位置往后找并且从1开始计数，若数量等于i时，则返回该位置具体的值，否则可以返回错误提示信息,四、线性链表的查找操作,Node*lbcz(Node*h,intx)Node*p;p=h-next;while(p!=NULL,按内容查找,Node*lbcz(Node*h，inti)Node*p;intk=1;p=h-next;while(p!=NULL,按内容查找,循环链表是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。,2.3.2循环链表,循环链表：首尾相接的链表。将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。,L,.,带头结点的单链表,L,.,循环单链表,2.3.2循环链表,a1,an,.,head,非空表,空表,在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n),2.3.2循环链表,在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rearnext)next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。,2.3.2循环链表,若已知某结点的指针为p，其后继结点的指针则为p-next，而找其前驱则只能从该链表的头指针开始,顺着各结点的next域进行，也就是说找后继的时间性能是O(1)，找前驱的时间性能是O(n),如果也希望找前驱的时间性能达到O(1)，则只能付出空间的代价：每个结点再加一个指向前驱的指针域，用这种结点组成的链表称为双向链表。双向链表(Doublelinkedlist):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样形成的链表中有两个方向不同的链，故称为双向链表。和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。,2.3.3双向链表,设指针p指向某一结点，则双向链表结构的对称性可用下式描述：(pprior)next=p=(pnext)prior即结点*p的存储位置既存放在其前趋结点*(pprior)的直接后继指针域中，也存放在它的后继结点*(pnext)的直接前趋指针域中。,2.3.3双向链表,在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点，提高运算效率。,L,structDNodeElemTypedata;structDNode*prior,*next;；,带头结点的双向链表,2.3.3双向链表,双向链表的前插运算intDlinkIns(structDNode*L,inti,ElemTypee),L,P,S,S-prior=P-prior;,P-prior-next=S;,S-next=P;,P-prior=S;,2.3.3双向链表,双向链表的删除操作intDlinkDel(structDNode*L,inti,ElemType*e),P,P-next-prior=p-prior;,P-prior-next=P-next；注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。,2.3.3双向链表,区别动态链表由指针实现的，表中的结点空间的分配和回收（即释放）都是由系统提供的标准函数malloc和free动态实现的链表静态链表用游标指示器代替指针实现的链表静态链表的结构也是由数据域和指针域组成指针域不再是指针，而是在一个数组中的相对位置（游标指示器）结点不是动态生成的，而是数组静态分配的,2.3.4动态链表与静态链表,顺序存储的三个优点：(1)方法简单，各种高级语言中都有数组，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。顺序存储的两个缺点：(1)在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。(2)需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反。,2.4顺序表和链表的比较,在实际中怎样选取存储结构呢？通常有以下几点考虑：、基于存储的考虑顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对MAXSIZE要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于的。,2.4顺序表和链表的比较,、基于运算的考虑在顺序表中按序号访问ai的时间性能是O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。,2.4顺序表和链表的比较,、基于环境（语言）的考虑顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。总之，两中存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。,2.4顺序表和链表的比较,基于空间的考虑空间的利用率和存储密度存储密度结点数据本身所占的存储量/结点结构所占的存储总量基于时间的考虑实现某一操作的时间基于语言的考虑高级语言是否提供指针类型将决定链表的实现,2.4顺序表和链表的比较,
展开阅读全文