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

2.2线性表及其顺序存储结构,线性表的基本概念线性表的顺序存储及运算队列,2.2.1线性表及其运算1、概念,线性表（简称表）：零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度。长度等于零时称为空表，通常记为：L()；非空表通常记为：L(a1，a2，an)。理解线性表的定义有以下要点：序列顺序性：元素具有线性顺序，第一个元素无前驱，最后一个元素无后继，其他每个元素有且仅有一个前驱和一个后继。有限有限性：元素个数有限，在计算机中处理的对象都是有限的。相同类型相同性：元素取自于同一个数据对象，这意味着每个元素占用相同数量的存储单元。元素类型不确定抽象性：数据元素的类型是抽象的、不具体的，需要根据具体问题确定。,顺序表用一段地址连续的存储单元依次存储线性表的数据元素。线性表(a1，a2，an)的顺序存储示意图如图2.5所示。由于线性表中每个数据元素的类型相同，可以用C+语言中的一维数组来实现顺序表，也就是把线性表中相邻的元素存储在数组中相邻的位置，如图2.6所示,在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成。例如，某班的学生情况登记表是一个复杂的线性表，表中每一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括学号、姓名、性别、入学成绩4个数据项。,2、线性表的顺序存储线性表的顺序存储结构称为顺序表。,线性表的顺序存储结构具有两个基本特点：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。,假设线性表中的第一个数据元素的存储地址（即首地址）为ADR(a1)，每一个数据元素占k个字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,长度为n的线性表在计算机中的顺序存储结构,在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。应注意数组的基本类型要与线性表中数据元素的类型相同。,数组需要根据情况预设足够的大小，同时还需要一个变量指出线性表在数组中的当前状况，如元素个数或最后一个元素在数组中的位置等。这两方面的信息共同描述一个顺序表，可将它们封装在一起。对C语言，顺序表可定义如下：,对C语言，顺序表可定义如下：#defineMaxLength50typedefintElemType;typedefstructElemTypelistMaxLength;intlength;SeqList;今后使用此定义时，MaxLength及ElemType要根据实际问题的需要可重新选定。,3、顺序表的基本运算,1.顺序表的插入操作接口voidInsert(inti,Tx)：在线性表的第i（1in+1）个位置上插入一个新元素x。插入前：(a1，ai-1，ai，an)，插入后：(a1，ai-1，x，ai，an)，顺序表在插入前后的状态对比如图2.12所示。,插入操作要点：顺序存储要求逻辑上相邻的元素存储在数组中相邻的单元。注意元素移动的方向后移一个单元。从最后一个元素开始移动，直至第i个元素。分析边界条件：如果表满了，则引发上溢异常。如果元素的插入位置不合理，则引发位置异常。,C语言描述templatevoidSeqList:Insert(inti,Tx)if(length=MaxSize)throw上溢;if(ilength+1)throw位置;for(j=length;j=i;j-)/注意j指的是元素序号dataj=dataj-1;/注意第j个元素存储在数组下标为j-1处datai-1=x;length+;,2.顺序表的删除,操作接口TDelete(inti)：将线性表中的第i（1in）个元素删除，并返回被删除元素的值。删除前：(a1，ai-1，ai，ai+1，an)，删除后：(a1，ai-1，ai+1，an)，顺序表删除前后状态的对比如图2.13所示,删除操作要点：元素移动的方向前移一个单元；从第i+1个元素开始移动，直至最后一个元素；在移动元素之前要取出被删元素。分析边界情况：如果表空，则发生下溢异常；如果元素的删除位置不合理，则引发删除位置异常。1.如果表空，则抛出下溢异常;2.如果删除位置不合理，则抛出删除位置异常；3.取出被删元素；4.将第i+1个元素直至最后一个元素分别向前移动一个位置；5.表长减1，返回被删元素值；,C语言描述templateTSeqList:Delete(inti)if(length=0)throw下溢;if(ilength)throw位置;x=datai-1;for(j=i+1;jrear=0;2）判断队列空intQueueEmpty(CircularQueue*q)/*队列为空返回1，否则返回0*/if(q-front=q-rear)exit(1);elseexit(0);,3）入队voidInsertQueue(CircularQueue*q,ElemTypex)if(q-rear+1)%MAXSIZE=q-front)printf(n队满，上溢！);exit(1);q-dataq-rear=x;/*新元素插入到队尾*/q-rear=(q-rear+1)%MAXSIZE;/*尾指针加1*/,4）出队ElemTypeDeleteQueue(CircularQueue*q)ElemTypex;if(QueueEmpty(q)printf(n队空，下溢！);exit(1);x=q-dataq-front;/*取出队头元素*/q-front=(q-front+1)%MAXSIZE;/*队头指针加1*/returnx;,5）读取队头元素ElemTypeGetHead(CircularQueue*q)ElemTypex;if(QueueEmpty(q)printf(n队空，下溢！);exit(1);x=q-dataq-front;/*取出队头元素*/returnx;,4.队列应用举例,例如，某银行储蓄所有一个服务窗口，该窗口在某个时刻只能接待一位顾客，假设为一位顾客服务的时间为定值，在顾客人数众多时需