线性表及其顺序存储结构.pptxVIP

2.2线性表及其顺序存储结构线性表的基本概念线性表的顺序存储及运算队列

2.2.1线性表及其运算1、概念线性表（简称表）：零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度。·长度等于零时称为空表，通常记为：L＝()；·非空表通常记为：L＝(a1，a2，……，an)。理解线性表的定义有以下要点：⑴序列——顺序性：元素具有线性顺序，第一个元素无前驱，最后一个元素无后继，其他每个元素有且仅有一个前驱和一个后继。⑵有限——有限性：元素个数有限，在计算机中处理的对象都是有限的。⑶相同类型——相同性：元素取自于同一个数据对象，这意味着每个元素占用相同数量的存储单元。⑷元素类型不确定——抽象性：数据元素的类型是抽象的、不具体的，需要根据具体问题确定。

顺序表用一段地址连续的存储单元依次存储线性表的数据元素。线性表(a1，a2，……，an)的顺序存储示意图如图2.5所示。由于线性表中每个数据元素的类型相同，可以用C++语言中的一维数组来实现顺序表，也就是把线性表中相邻的元素存储在数组中相邻的位置，如图2.6所示

在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成。例如，某班的学生情况登记表是一个复杂的线性表，表中每一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括学号、姓名、性别、入学成绩4个数据项。

线性表的顺序存储结构具有两个基本特点：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表的顺序存储线性表的顺序存储结构称为顺序表。

假设线性表中的第一个数据元素的存储地址（即首地址）为ADR(a1)，每一个数据元素占k个字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为：ADR(ai)=ADR(a1)+(i-1)k

长度为n的线性表在计算机中的顺序存储结构

在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。应注意数组的基本类型要与线性表中数据元素的类型相同。01数组需要根据情况预设足够的大小，同时还需要一个变量指出线性表在数组中的当前状况，如元素个数或最后一个元素在数组中的位置等。这两方面的信息共同描述一个顺序表，可将它们封装在一起。对C语言，顺序表可定义如下：02

对C语言，顺序表可定义如下：#defineMaxLength50typedefintElemType;typedefstruct{ElemTypelist[MaxLength];intlength;}SeqList;今后使用此定义时，MaxLength及ElemType要根据实际问题的需要可重新选定。

3、顺序表的基本运算1.顺序表的插入操作接口voidInsert(inti,Tx)：在线性表的第i（1≤i≤n+1）个位置上插入一个新元素x。插入前：(a1，…，ai-1，ai，…，an)，插入后：(a1，…，ai-1，x，ai，…，an)，顺序表在插入前后的状态对比如图2.12所示。

插入操作要点：

·顺序存储要求逻辑上相邻的元素存储在数组中相邻的单元。

·注意元素移动的方向——后移一个单元。

·从最后一个元素开始移动，直至第i个元素。

分析边界条件：

·如果表满了，则引发上溢异常。

·如果元素的插入位置不合理，则引发位置异常。

C语言描述C语言描述templateclassTvoidSeqList::Insert(inti,Tx){if(length=MaxSize)throw上溢;if(i1||ilength+1)throw位置;for(j=length;j=i;j--)//注意j指的是元素序号data[j]=data[j-1];//注意第j个元素存储在数组下标为j-1处data[i-1]=x;length++;}

操作接口TDelete(inti)：将线性表中的第i（1≤i≤n）个元素删除，并返回被删除元素的值。删除前：(a1，…，ai-1，ai，ai+1，…，an)，删除后：(a1，…，ai-1，ai+1，…，an)，顺序表删除前后状态的对比如图2.13所示顺序表的删除

删除操作要点：·元素移动的方向——前移一个单元；·从第i+1个元素开始移动，直至最后一个元素；·在移动元素之前要取出被删元素。分析边界情况：·如果表空，则发生下溢异常；·如果元素的删除位置不合理，则引发删除位置异常。1.如果表空，则抛出下溢异常;2.如果删除位置不合理，则抛出删除位置异常；3.取