搜索
第二章线性表和数组1、线性表的定义和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。2.线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。3.线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。教学重点：1、线性表的定义；2、线性表的顺序表示和实现方法：教学难点：线性表的顺序存储的实现方法。授课内容第二章线性表和数组线性表是最简单、最基本、也是最常用的一种线性结构。它有两种存储方法：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。2.1线性表的逻辑结构2.1.1线性表的定义线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的，如学生情况信息表是一个线性表：表中数据元素的类型为学生类型;一个字符串也是一个线性表：表中数据元素的类型为字符型，等等。综上所述，线性表定义如下：线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为：(a1，a2，…ai-1，ai，ai+1，…an)其中n为表长，n＝0时称为空表。表中相邻元素之间存在着顺序关系。将ai-1称为ai的直接前趋，ai+1称为ai的直接后继。就是说：对于ai，当i=2，...，n时，有且仅有一个直接前趋ai-1.，当i=1，2，...，第三讲线性表的逻辑结构和顺序存储结构第二章线性表和数组n-1时，有且仅有一个直接后继ai+1，而a1是表中第一个元素，它没有前趋，an是最后一个元素无后继。需要说明的是：ai为序号为i的数据元素（i=1,2,…,n），通常我们将它的数据类型抽象为datatype，datatype根据具体问题而定，如在学生情况信息表中，它是用户自定义的学生类型;在字符串中，它是字符型;等等。2.1.2线性表的基本操作在第一章中提到，数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的，因此下面定义的线性表的基本运算作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。线性表上的基本操作有：⑴线性表初始化：Init_List(L)初始条件：表L不存在操作结果：构造一个空的线性表⑵求线性表的长度：Length_List(L)初始条件：表L存在操作结果：返回线性表中的所含元素的个数⑶取表元：Get_List(L,i)初始条件：表L存在且1=i=Length_List(L)操作结果：返回线性表L中的第ｉ个元素的值或地址⑷按值查找：Locate_List(L,x)，ｘ是给定的一个数据元素。初始条件：线性表L存在操作结果：在表L中查找值为ｘ的数据元素，其结果返回在L中首次出现的值为ｘ的那个元素的序号或地址，称为查找成功;否则，在L中未找到值为ｘ的数据元素，返回一特殊值表示查找失败。⑸插入操作：Insert_List(L,i,x)初始条件：线性表L存在，插入位置正确(1=i=n+1,ｎ为插入前的表长)。操作结果：在线性表L的第i个位置上插入一个值为x的新元素，这样使原序号为i,i+1,...,n的数据元素的序号变为i+1,i+2,...,n+1，插入后表长=原表长+1。⑹删除操作：Delete_List(L,i)初始条件：线性表L存在，1=i=n。操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为i+1,i+2,...,n的元素变为序号为i,i+1,...,n-1，新表长＝原表长－１。需要说明的是：1.某数据结构上的基本运算，不是它的全部运算，而是一些常用的基本的运算，而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。比如线性表的查找在链式存储结构中还会有按序号查找;再如插入运算，也可能是将新元素ｘ插入到适当位置上等等，不可能也没有必要全部定义出它的运算集，读者掌握了某一数据结构上的基本运算后，其它的运算可以通过基本运算来实现，也可以直接去实现。2.在上面各操作中定义的线性表Ｌ仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及到它的存储结构，因此每个操作在逻辑结构层次上尚不能用具体的某种程序语言写出具体第二章线性表和数组的算法，而算法的实现只有在存储结构确立之后。2.2线性表的顺序存储结构2.2.1顺序存储结构线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。因为内存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单，又自然的。如图2.1所示。设a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为：Loc(ai)=Loc(a１)+(i-1)*d1=i=n这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过的。考虑到线性表的运算有插入、删除等运算，即表长是可变的，因此，数组的容量需设计的足够大，设用：data[MAXSIZE]来表示，其中MAXSIZE是一个根据实际问题定义的足够大的整数，线性表中的数据从data[0]开始依次顺序存放，但当前线性表中的实际元素个数可能未达到MAXSIZE多个，因此需用一个变量last记录当前线性表中最后一个元素在数组中的位置，即last起一个指针的作用，始终指向线性表中最后一个元素，因此，表空时last=-1。这种存储思想的具体描述可以是多样的。如可以是：datatypedata[MAXSIZE];intlast;这样表示的顺序表如图2.1所示。表长为last+1，数据元素分别存放在data[0]到data[last]中。这样使用简单方便，但有时不便管理。01…i-1i…n-1...MAXSIZE1-1dataa1a2…ai-1aiai+1…an…图2.1线性表的顺序存储示意图从结构性上考虑，通常将data和last封装成一个结构作为顺序表的类型：typedefstruct{datatypedata[MAXSIZE];intlast;}SeqList;定义一个顺序表：SeqListL;这样表示的线性表如图2.2（a）所示。表长＝L.last+1，线性表中的数据元素a1至an分别存放在L.data[0]至L.data[L.last]中。由于我们后面的算法用C语言描述，根据C语言中的一些规则，有时定义一个指向SeqList类型的指针更为方便：SeqList*L；last第二章线性表和数组L是一个指针变量，线性表的存储空间通过L=malloc(sizeof(SeqList))操作来获得。L中存放的是顺序表的地址，这样表示的线性表如图2.2(b)所示。表长表示为（*L）.last或L－＞last+1，线性表的存储区域为L-data，线性表中数据元素的存储空间为：L－＞data[0]~L－＞data[L－＞last]。在以后的算法中多用这种方法表示，读者在读算法时注意相关数据结构的类型说明。2.2.2顺序表上基本操作的实现1.顺序表的初始化顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为指针参数，首先动态分配存储空间，然后，将表中last指针置为－1，表示表中没有数据元素。算法如下：SeqList*init_SeqList(){SeqList*L;L=malloc(sizeof(SeqList));L-last=-1;returnL;}算法2.1设调用函数为主函数，主函数对初始化函数的调用如下：main(){SeqList*L;L=Init_SeqList();．．．}2.插入运算线性表的插入是指在表的第i个位置上插入一个值为x的新元素，插入后使原表长为n的表:图2.2线性表的顺序存储示意图第二章线性表和数组(a1，a2，...，ai-1，ai，ai+1，...，an)成为表长为n+1表:(a1，a2，...，ai-1，x，ai，ai+1，...，an)。i的取值范围为1=i=n+1。顺序表上完成这一运算则通过以下步骤进行：(1)将ai～an顺序向下移动，为新元素让出位置；(2)将x置入空出的第i个位置；(3)修改last指针(相当于修改表长)，使之仍指向最后一个元素。算法如下：intInsert_SeqList(SeqList*L，inti，datatypex){intj;if(L-last==MAXSIZE－1){printf(＂表满＂);return(-1);}/*表空间已满，不能插入*/if(i1||iL-last+2)/*检查插入位置的正确性*/{printf(＂位置错＂);return(0);}for(j=L-last;j=i-1;j--)L-data[j+1]=L-data[j];/*结点移动*/L-data[i-1]=x;/*新元素插入*/L-last++;/*last仍指向最后元素*/return(1);/*插入成功，返回*/}算法2.2本算法中注意以下问题：(1)顺序表中数据区域有MAXSIZE个存储单元，所以在向顺序表中做插入时先检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。(2)要检验插入位置的有效性，这里i的有效范围是：1=i=n+1，其中n为原表长。(3)注意数据的移动方向。a1a2…ai-1aiai+1…an…a1a２…ai-1xaiai+1…an…01i-2i-1in-1MAXSIZE-1插入前插入后图2.3顺序表中的插入第二章线性表和数组插入算法的时间性能分析：顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入x，从ai到an都要向下移动一个位置，共需要移动n－i＋1个元素，而i的取值范围为：1=i=n+1，即有n＋1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：11)1(Eniiininp设：Pi=1/(n+1)，即为等概率情况，则：11112)1(11)1(Eniniiinninninp这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为Ｏ(n)。3.删除运算DeleteList(L,i)线性表的删除运算是指将表中第i个元素从线性表中去掉，删除后使原表长为n的线性表：(a1，a2，...，ai-1，ai，ai+1，...，an)成为表长为n－1的线性表：(a1，a2，...，ai-1，ai+1，...，an)。i的取值范围为：1=i=n。顺序表上完成这一运算的步骤如下：(1)将ai+1～an顺序向上移动。(2)修改last指针(相当于修改表长)使之仍指向最后一个元素。算法如下：intDelete_SeqList(SeqList*L;inti){intj;if(i1||iL-last+1)/*检查空表及删除位置的合法性*/{printf(＂不存在第i个元素＂);return(0);}for(j=i;j=L-last;j++)a1a２…ai-1ai+1an…0a11a2…i-2ai-1i-1aiiai+1．．．n-1an…MAXSIZE-1删除前删除后图2.4顺序表中的删除第二章线性表和数组L-data[j-1]=L-data[j];/*向上移动*/L-last--;return(1);/*删除成功*/}算法2.3本算法注意以下问题：（1）删除第i个元素，i的取值为1=i=n,否则第i个元素不存在，因此，要检查删除位置的有效性。（2）当表空时不能做删除，因表空时L-last的值为-1，条件（i1||iL-last+1）也包括了对表空的检查。（3）删除ai之后，该数据已不存在，如果