数据结构线性表

第二章线性表2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4一元多项式的表示及相加通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性表的基本运算以及实现算法。2.1线性表的逻辑结构第二章线性表线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继线性表是一种最简单的线性结构线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为：（a1,a2,……,an）简言之，线性结构反映结点间的逻辑关系是的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------线性表一对一(1:1)2.1线性表的基本概念１、线性表它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的，由n（n≥0)个相同类型数据元素a0,a1,…,an-1组成的线性结构。（a0,a1,…ai-1，ai,ai＋1，…,an-1）线性表的逻辑结构：n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点（A,B,C,D,……,Z）学号姓名性别年龄班级012003010622陈建武男192003级电信0301班012003010704赵玉凤女182003级电信0302班012003010813王泽男192003级电信0303班012003010906薛荃男192003级电信0304班012003011018王春男192003级电信0305班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。强调本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储数据结构？如何在计算机上实现对数据结构的各种操作，为此，我们将用计算机语言来描述数据的存储结构，用计算机语言来描述这些操作的算法，本课程我们用类C语言做为描述语言。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。数据结构有两种存储方式:顺序存储，链式存储，线性表也可以用这两种方法实现。在计算机内，线性表有两种基本的存储结构：顺序存储结构和链式存储结构。下面我们分别讨论这两种存储结构以及对应存储结构下实现各操作的算法。线性表的存储结构(1)顺序存储结构:它是使用一片地址连续的有限内存单元空间存储数据元素的一种计算机存储数据方法。特点：(任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻)逻辑上相邻的元素，物理上也相邻。(2)链式存储结构:它是把数据元素和指针定义成一个存储体，使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。特点：任意两个在逻辑上相邻的数据元素在物理上不一定相邻，数据元素的逻辑次序是通过链中的指针链接实现的。2.2线性表的顺序存储结构2.2.1顺序表2.2.2顺序表上实现的基本运算2.2线性表的顺序存储和实现如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？2.2.1顺序表一、顺序表的存储结构表示1、顺序表：用一组地址连续的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储。可以利用数组V[n]来实现注意：在C语言中数组的下标是从0开始，即：V[n]的有效范围是从V[0]～V[n-1](1)逻辑上相邻的数据元素，其物理上也相邻；(2)若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。设首元素a0的存放地址为LOC(a0)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a0)+L*i对上述公式的解释如图所示2、线性表顺序存储特点：a0a1……aiai+1……an-1地址内容元素在表中的位序0i1n-1空闲区i+1Lb=LOC(a0)b+Lb+iLb+(n-1)Lb+(MaxSize-1)LLOC(ai)=LOC(a0)+L*i3、线性表的顺序存储结构示意图4、用C语言描述typedefstruct{DateTypelist[MaxSize];intsize;}SeqList;/*MaxSize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size≤MaxSize，SeqList是该结构体的名字。*/设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是多少？113LOC(M[3])=98+5×3=113解：已知地址计算通式为：LOC(ai)=LOC(a0)+L*i例1charV[30];voidbuild()/*字母线性表的生成，即建表操作*/{inti;V[0]='a';for(i=1;i=n-1;i++)V[i]=V[i-1]+1;}核心语句：方法1V[i]=V[i-1]+1;方法2V[i]=’a’+i;方法3V[i]=97+i;例2用数组V来存放26个英文字母组成的线性表（a，b，c，…，z），写出在顺序结构上生成和显示该表的C语言程序。voidmain(void)/*主函数，字母线性表的生成和输出*/{n=26;/*n是表长，是数据元素的个数，而不是V的实际下标*/build();display();}voiddisplay()/*字母线性表的显示，即读表操作*/{inti;for(i=0;i=n-1;i++)printf(%c,v[i]);printf(\n);}执行结果：abcdefghijklmnopqrstuvwxyz由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型#defineListSize100线性表可能达到的最大长度；typedefintDataType;typedefstruct{DataTypedata[ListSize];/*线性表占用的数组空间*/intlength;/*记录线性表中最后一个元素在数组data[]中的位置（下标值），空表置为-1*/}Sqlist;注意区分元素的序号和数组的下标，如a1的序号为1，而其对应的数组下标为0。顺序存储结构的C语言定义类型定义语句typedef并不是用来定义新的数据类型,只是用来对原有的数据类型起一个新的名字(习惯上常用大写字母表示,区别于系统提供的标准数据类型),方便后续程序的使用和程序的移植。a1a2an01n-112n内存V数组下标元素序号M-1typedefintDATATYPE;#defineM1000DATATYPEdata[M];例typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];备用空间数据元素不是简单类型时,可定义结构体数组或动态申请和释放内存DATATYPE*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE));free(pData);线性表的顺序存储结构总结2.2.2顺序表上实现的基本运算二、顺序表的实现（或操作）数据结构的基本运算：修改、插入、删除、查找、排序1)修改通过数组的下标便可访问某个特定元素并修改之。核心语句:V[i]=x;显然，顺序表修改操作的时间效率是O(1)2.2.2顺序表上实现的基本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.data[i-1]。以下主要讨论线性表的插入和删除两种运算。插入定义：线性表的插入是指在第I（1in+1）个元素之前插入一个新的数据元素x，使长度为n的线性表niiaaaaa,,,,1,21变成长度为n+1的线性表nii,a,a,x,a,a,a121需将第i至第n共（n-i+1)个元素后移算法Ch2_1.c顺序表的插入：插入操作分成两阶段：第一阶段将位于插入点以后的数据元素依次向后移动，为新数据元腾出一个空间，然后在第二阶段中将数据元素插入空挡。插入算法示意图已知：线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，序号移动元素插入元素1234567810949152830304251624915283030426251491521283030426251内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x在线性表（n个元素）的第i个位置前插入一个元素实现步骤：•将第n至第i位的元素向后移动一个位置；•将要插入的元素写到第i个位置；•表长加1。注意：事先应判断:插入位置i是否合法?表是否已满?for(j=n-1;j=i;j--)a[j+1]=a[j];a[i]=x;n++;//元素后移一个位置//插入x//表长加1核心语句：2)插入在线性表的第i个位置前插入一个元素的示意图如下：121321242830427712132124252830427712345678123456789插入25在一个顺序表中第i个元素之前插入一个元素x的函数：顺序表的删除：删除操作分为相应两个阶段，只是顺序与前者相反：第一阶段先执行数据元素的删除，第二阶段再移动数据将空挡填上。删除算法示意：将线性表(4,9,15,21,28,30,30,42,51,62)中的第5个元素删除。序号123456781094915212830304262514915213030425162删除28后内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2实现步骤：将第i+1至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法?删除线性表的第i个位置上的元素for(j=i+1;j=n-1;j++)a[j-1]=a[j];n--;//元素前移一个位置//表长减1核心语句：3)删除123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：在一个顺序表中删除第i个元素的函数：顺序表的运算效率分析算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置.思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能