第2章线性表线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中:①存在一个唯一的被称为“第一个”的数据元素;②存在一个唯一的被称为“最后一个”的数据元素;③除第一个元素外,每个元素均有唯一一个直接前驱;④除最后一个元素外,每个元素均有唯一一个直接后继。2.1线性表的逻辑结构线性表(LinearList):是由n(n≧0)个数据元素(结点)a1,a2,…an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。当n=0时,称为空表。当n0时,将非空的线性表记作:(a1,a2,…an)a1称为线性表的第一个(首)结点,an称为线性表的最后一个(尾)结点。2.1.1线性表的定义a1,a2,…ai-1都是ai(2≦i≦n)的前驱,其中ai-1是ai的直接前驱;ai+1,ai+2,…an都是ai(1≦i≦n-1)的后继,其中ai+1是ai的直接后继。2.1.2线性表的逻辑结构线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同,在线性表的定义中,只不过是一个抽象的表示符号。◆线性表中的结点可以是单值元素(每个元素只有一个数据项)。例1:26个英文字母组成的字母表:(A,B,C、…、Z)例2:某校从1978年到1983年各种型号的计算机拥有量的变化情况:(6,17,28,50,92,188)例3:一副扑克的点数(2,3,4,…,J,Q,K,A)◆线性表中的结点可以是记录型元素,每个元素含有多个数据项,每个项称为结点的一个域。每个元素有一个可以唯一标识每个结点的数据项组,称为关键字。例4:某校2001级同学的基本情况:{(‘2001414101’,‘张里户’,‘男’,06/24/1983),(‘2001414102’,‘张化司’,‘男’,08/12/1984)…,(‘2001414102’,‘李利辣’,‘女’,08/12/1984)}◆若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的,称线性表是有序的。2.1.3线性表的抽象数据类型定义ADTList{数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≧0}数据关系:R={ai-1,ai|ai-1,ai∈D,i=2,3,…,n}基本操作:InitList(&L)操作结果:构造一个空的线性表L;◆线性表是一种相当灵活的数据结构,其长度可根据需要增长或缩短。◆对线性表的数据元素可以访问、插入和删除。ListLength(L)初始条件:线性表L已存在;操作结果:若L为空表,则返回TRUE,否则返回FALSE;….GetElem(L,i,&e)初始条件:线性表L已存在,1≦i≦ListLength(L);操作结果:用e返回L中第i个数据元素的值;ListInsert(L,i,&e)初始条件:线性表L已存在,1≦i≦ListLength(L);操作结果:在线性表L中的第i个位置插入元素e;…}ADTList2.2线性表的顺序存储顺序存储:把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。顺序存储的线性表的特点:◆线性表的逻辑顺序与物理顺序一致;◆数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。设有非空的线性表:(a1,a2,…an)。顺序存储如图2-1所示。2.2.1线性表的顺序存储结构在具体的机器环境下:设线性表的每个元素需占用l个存储单元,以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系:LOC(ai+1)=LOC(ai)+l线性表的第i个数据元素ai的存储位置为:LOC(ai)=LOC(a1)+(i-1)*l…a1a2…ai…an…Loc(a1)Loc(ai)+(i-1)*l图2-1线性表的顺序存储表示在高级语言(如C语言)环境下:数组具有随机存取的特性,因此,借助数组来描述顺序表。除了用数组来存储线性表的元素之外,顺序表还应该有表示线性表的长度属性,所以用结构类型来定义顺序表类型。#defineOK1#defineERROR-1#defineMAX_SIZE100typedefintStatus;typedefintElemType;typedefstructsqlist{ElemTypeElem_array[MAX_SIZE];intlength;}SqList;顺序存储结构中,很容易实现线性表的一些操作:初始化、赋值、查找、修改、插入、删除、求长度等。以下将对几种主要的操作进行讨论。1顺序线性表初始化StatusInit_SqList(SqList*L){L-elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType));if(!L-elem_array)returnERROR;else{L-length=0;returnOK;}}2.2.2顺序表的基本操作2顺序线性表的插入在线性表L=(a1,…ai-1,ai,ai+1,…,an)中的第i(1≦i≦n)个位置上插入一个新结点e,使其成为线性表:L=(a1,…ai-1,e,ai,ai+1,…,an)实现步骤(1)将线性表L中的第i个至第n个结点后移一个位置。(2)将结点e插入到结点ai-1之后。(3)线性表长度加1。算法描述StatusInsert_SqList(Sqlist*L,inti,ElemTypee){intj;if(i0||iL-length-1)returnERROR;if(L-length=MAX_SIZE){printf(“线性表溢出!\n”);returnERROR;}for(j=L-length–1;j=i-1;--j)L-Elem_array[j+1]=L-Elem_array[j];/*i-1位置以后的所有结点后移*/L-Elem_array[i-1]=e;/*在i-1位置插入结点*/L-length++;returnOK;}3顺序线性表的删除在线性表L=(a1,…ai-1,ai,ai+1,…,an)中删除结点ai(1≦i≦n),使其成为线性表:L=(a1,…ai-1,ai+1,…,an)实现步骤(1)将线性表L中的第i+1个至第n个结点依此向前移动一个位置。(2)线性表长度减1。算法描述ElemTypeDelete_SqList(Sqlist*L,inti){intk;ElemTypex;if(L-length==0){printf(“线性表L为空!\n”);returnERROR;}elseif(i1||iL-length){printf(“要删除的数据元素不存在!\n”);returnERROR;}else{x=L-Elem_array[i-1];/*保存结点的值*/for(k=i;kL-length;k++)L-Elem_array[k-1]=L-Elem_array[k];/*i位置以后的所有结点前移*/L-length--;return(x);}}4顺序线性表的查找定位删除在线性表L=(a1,a2,…,an)中删除值为x的第一个结点。实现步骤(1)在线性表L查找值为x的第一个数据元素。(2)将从找到的位置至最后一个结点依次向前移动一个位置。(3)线性表长度减1。算法描述StatusLocate_Delete_SqList(Sqlist*L,ElemTypex)/*删除线性表L中值为x的第一个结点*/{inti=0,k;while(iL-length)/*查找值为x的第一个结点*/{if(L-Elem_array[i]!=x)i++;else{for(k=i+1;kL-length;k++)L-Elem_array[k-1]=L-Elem_array[k];L-length--;break;}}if(iL-length){printf(“要删除的数据元素不存在!\n”);returnERROR;}returnOK;}2.3.1线性表的链式存储结构2.3线性表的链式存储链式存储:用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。存储链表中结点的一组任意的存储单元可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。链表中结点的逻辑顺序和物理顺序不一定相同。为了正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其直接后继结点的地址(或位置),称为指针(pointer)或链(link),这两部分组成了链表中的结点结构,如图2-2所示。链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。每一个结只包含一个指针域的链表,称为单链表。为操作方便,总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)。datanext图2-2链表结点结构data:数据域,存放结点的值。next:指针域,存放结点的直接后继的地址。3695headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfathat⋀head图2-3带头结点的单链表的逻辑状态、物理存储方式单链表是由表头唯一确定,因此单链表可以用头指针的名字来命名。例1、线性表L=(bat,cat,eat,fat,hat)其带头结点的单链表的逻辑状态和物理存储方式如图2-3所示。1结点的描述与实现C语言中用带指针的结构体类型来描述typedefstructLnode{ElemTypedata;/*数据域,保存结点的值*/structLnode*next;/*指针域*/}LNode;/*结点的类型*/2结点的实现结点是通过动态分配和释放来的实现,即需要时分配,不需要时释放。实现时是分别使用C语言提供的标准函数:malloc(),sizeof(),free()。动态分配p=(LNode*)malloc(sizeof(LNode));函数malloc分配了一个类型为LNode的结点变量的空间,并将其首地址放入指针变量p中。动态释放free(p);系统回收由指针变量p所指向的内存区。P必须是最近一次调用malloc函数时的返回值。3最常用的基本操作及其示意图⑴结点的赋值LNode*p;p=(LNode*)malloc(sizeof(LNode));p-data=20;p-next=NULL;p20NULL⑵常见的指针操作①q=p;pa……操作前pa……q操作后②q=p-next;bpa……操作前操作后qbpa……③p=p-next;bpa……操作前操作后pba……④q-next=p;c…pbqa……操作前操作后qb……ac…p(a)⑤q-next=p-next;(a)xy…pbqa……操作前操作后qb……axy…p操作前ypx……bqa…操作后ypx……bqa…(b)操作前ypx……bqa…操作后ypx……bqa…(b)1建立单链表假设线性表中结点的数据类型是整型,以32767作为结束标志。动态地建立单链表的常用方法有如下两种:头插入法,尾插入法。⑴头插入法建表从一个空表开始,重复读入数据,生成新结点,将读入数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。即每次插入的结点都作为链表的第一个结点。2.3.2单线性链式的基本操作算法描述LNode*create_LinkList(void)/*头插入法创建单链表,链表的头结点head作为返回值*/{intdata;LNode*head,*p;head=(LNode*)malloc(sizeof(LNode));head-next=NULL;/*创建链表的表头结点head*/while(1){sc