数据结构-线性表.

2线性表信息学院暑期培训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)2.1.2线性表的逻辑结构◆线性表中的结点可以是记录型元素，每个元素含有多个数据项，每个项称为结点的一个域。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。例4：某校2001级同学的基本情况：{(‘2001414101’，‘张里户’，‘男’，06/24/1983)，(‘2001414102’，‘张化司’，‘男’，08/12/1984)…，(‘2001414102’，‘李利辣’，‘女’，08/12/1984)}◆若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。2.1.3线性表的抽象数据类型定义◆线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。◆对线性表的数据元素可以访问、插入和删除。2.1.3线性表的抽象数据类型定义ADTList{数据对象：数据关系：基本操作：InitList(&L)/*初始化线性表*/DestroyList(&L)/*销毁线性表*/ListEmpty(L)/*判断是否为空线性表*/......}}0,,...,2,1,|{nniElemSetaaDii},...,2,1,,|,{11niDaaaaRiiii2.1.3线性表的抽象数据类型定义2.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线性表的顺序存储表示2.2线性表的顺序存储在高级语言(如C语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。#defineOK1/*预定义正确标识*/#defineERROR-1/*预定义错误标识*/#defineMAX_SIZE100/*预定义数组长度*/typedefintStatus;/*声明元素类型*/typedefintElemType;/*声明数据元素的类型*/typedefstructsqlist{ElemTypeelem_array[MAX_SIZE];intlength;/*数组的当前长度*/}SqList;2.2.2顺序表的基本操作顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。以下将对几种主要的操作进行讨论。1顺序线性表初始化StatusInit_SqList(SqList*L){L-elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType));if(!L-elem_array)returnERROR;else{L-length=0;returnOK;}}补充C语言中malloc是动态内存分配函数。函数原型：void*malloc(unsignedintnum_bytes);参数：num_bytes是无符号整型，用于表示分配的字节数。返回值：如果分配成功则返回指向被分配内存的指针(此存储区中的初始值不确定)，否则返回空指针NULL。void*表示未确定类型的指针，void*可以指向任何类型的数据，更明确的说是指申请内存空间时还不知道用户是用这段空间来存储什么类型的数据（比如是char还是int或者...）功能：分配长度为num_bytes字节的内存块注意：当内存不再使用时，应使用free()函数将内存块释放。函数返回的指针一定要适当对齐，使其可以用于任何数据对象。关于该函数的原型，在以前malloc返回的是char型指针，新的ANSIC标准规定，该函数返回为void型指针，因此必要时要进行类型转换。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。2.2.2顺序表的基本操作算法描述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;}2.2.2顺序表的基本操作时间复杂度分析在线性表L中的第i个元素之前插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。设在线性表L中的第i个元素之前插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。总的平均移动次数：Einsert=∑pi*(n-i+1)(1≦i≦n)∴Einsert=n/2。即在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。2.2.2顺序表的基本操作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。2.2.2顺序表的基本操作算法描述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);}}2.2.2顺序表的基本操作时间复杂度分析删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。设在线性表L中删除第i个元素的概率为Pi，不失一般性，设删除各个位置是等概率，则Pi=1/n，而删除时移动结点的次数为n-i。则总的平均移动次数：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。即在顺序表上做删除运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。2.2.2顺序表的基本操作4顺序线性表的查找定位删除在线性表L=(a1，a2，…，an)中删除值为x的第一个结点。实现步骤(1)在线性表L查找值为x的第一个数据元素。(2)将从找到的位置至最后一个结点依次向前移动一个位置。(3)线性表长度减1。2.2.2顺序表的基本操作算法描述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.2.2顺序表的基本操作时间复杂度分析时间主要耗费在数据元素的比较和移动操作上。首先，在线性表L中查找值为x的结点是否存在;其次，若值为x的结点存在，且在线性表L中的位置为i，则在线性表L中删除第i个元素。设在线性表L删除数据元素概率为Pi，不失一般性，设各个位置是等概率，则Pi=1/n。◆比较的平均次数：Ecompare=∑pi*i(1≦i≦n)∴Ecompare=(n+1)/2。◆删除时平均移动次数：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。平均时间复杂度：Ecompare+Edelete=n，即为O(n)2.3线性表的链式存储2.3.1线性表的链式存储结构•链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。•存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。•链表中结点的逻辑顺序和物理顺序不一定相同。为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了链表中的结点结构，如图2-2所示。链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。每一个结只包含一个指针域的链表，称为单链表。为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一结点。头结点的数据域可以不