《线性表及其顺序存储结构.ppt》由会员分享，可在线阅读，更多相关《线性表及其顺序存储结构.ppt（32页珍藏版）》请在金锄头文库上搜索。
1、2.2 线性表及其顺序存储结构线性表及其顺序存储结构线性表的基本概念线性表的基本概念线性表的顺序存储及运算线性表的顺序存储及运算队列队列2.2.1 线性表及其运算线性表及其运算1、概念、概念 线线性性表表（简简称称表表）：零零个个或或多多个个具具有有相相同同类类型型的的数数据据元元素素的的有有限限序序列列。数据元素的个数称为线性表的长度。数据元素的个数称为线性表的长度。长度等于零时称为空表，通常记为：长度等于零时称为空表，通常记为：L( )；非空表通常记为：非空表通常记为：L(a1，a2，an)。理解线性表的定义有以下要点：理解线性表的定义有以下要点： 序序列列顺顺序序性性：元元素素具具有有线
2、线性性顺顺序序，第第一一个个元元素素无无前前驱驱，最最后后一一个元素无后继，其他每个元素有且仅有一个前驱和一个后继。个元素无后继，其他每个元素有且仅有一个前驱和一个后继。 有有限限有有限限性性：元元素素个个数数有有限限，在在计计算算机机中中处处理理的的对对象象都都是是有有限限的。的。 相相同同类类型型相相同同性性：元元素素取取自自于于同同一一个个数数据据对对象象，这这意意味味着着每每个个元素占用相同数量的存储单元。元素占用相同数量的存储单元。 元元素素类类型型不不确确定定抽抽象象性性：数数据据元元素素的的类类型型是是抽抽象象的的、不不具具体体的的，需要根据具体问题确定。需要根据具体问题确定。l
3、顺序表用一段地址连续的存储单元依次存储线性表的数据元素。线性表(a1，a2，an)的顺序存储示意图如图2.5所示。l由于线性表中每个数据元素的类型相同，可以用C+语言中的一维数组来实现顺序表，也就是把线性表中相邻的元素存储在数组中相邻的位置，如图2.6所示 在稍微复杂的线性表中，一个数据元素还在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成。例如，某班的学可以由若干个数据项组成。例如，某班的学生情况登记表是一个复杂的线性表，表中每生情况登记表是一个复杂的线性表，表中每一个学生的情况就组成了线性表中的每一个一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括学号、姓名、性元素
4、，每一个数据元素包括学号、姓名、性别、入学成绩别、入学成绩4个数据项。个数据项。 2、线性表的顺序存储、线性表的顺序存储 线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。 线性表的顺序存储结构具有两个基本特点：线性表的顺序存储结构具有两个基本特点： 线线性性表表中中所所有有元元素素所所占占的的存存储储空空间间是是连连续的；续的； 线性表中各数据元素在存储空间中是按线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。逻辑顺序依次存放的。 假假设设线线性性表表中中的的第第一一个个数数据据元元素素的的存存储储地地址址（即即首首地地址址）为为 ADR(aADR(a1 1) )，每每一
5、一个个数数据据元元素素占占k k个个字字节节，则则线线性性表表中中第第i i个个元元素素a ai i在在计计算算机机存存储储空空间间中中的的存存储储地地址址为为：ADR(aADR(ai i)=ADR)=ADR(a(a1 1)+(i-1)k)+(i-1)k长度为长度为n n的的线性表在线性表在计算机中计算机中的顺序存的顺序存储结构储结构 在程序设计语言中，通常定义一个一维数组在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。来表示线性表的顺序存储空间。 应注意数组的基本类型要与线性表中数据元应注意数组的基本类型要与线性表中数据元素的类型相同。素的类型相同。 数组需要根据情况预设足
6、够的大小，同时数组需要根据情况预设足够的大小，同时还需要一个变量指出线性表在数组中的当前还需要一个变量指出线性表在数组中的当前状况，如元素个数或最后一个元素在数组中状况，如元素个数或最后一个元素在数组中的位置等。这两方面的信息共同描述一个顺的位置等。这两方面的信息共同描述一个顺序表，可将它们封装在一起。对序表，可将它们封装在一起。对C语言，顺序语言，顺序表可定义如下：表可定义如下： 对对C语语言，言，顺顺序表可定序表可定义义如下：如下：#define MaxLength 50 typedef int ElemType; typedef struct ElemType listMaxLength
7、; int length; SeqList; 今今后后使使用用此此定定义义时时，MaxLength及及ElemType要要根根据据实实际际问问题题的的需需要要可可重重新新选选定。定。 3、顺序表的基本运算、顺序表的基本运算 1.1.顺序表的插入顺序表的插入 操作接口操作接口void Insert(int i, T x)void Insert(int i, T x)：在线性：在线性表的第表的第i i（1in+11in+1）个位置上插入一个新元）个位置上插入一个新元素素x x。插入前：插入前：(a1，ai-1，ai，an)，插入，插入后：后：(a1，ai-1，x，ai，an)，顺序表，顺序表在插入
8、前后的状态对比如图在插入前后的状态对比如图2.12所示。所示。 插入操作要点：插入操作要点： 顺序存储要求逻辑上相邻的元素存储在数组中相邻的单元。顺序存储要求逻辑上相邻的元素存储在数组中相邻的单元。 注意元素移动的方向注意元素移动的方向后移一个单元。后移一个单元。 从最后一个元素开始移动，直至第从最后一个元素开始移动，直至第i i个元素。个元素。分析边界条件：分析边界条件： 如果表满了，则引发上溢异常。如果表满了，则引发上溢异常。 如果元素的插入位置不合理，则引发位置异常。如果元素的插入位置不合理，则引发位置异常。lC语言描述 template void SeqList:Insert(int
9、i, T x) 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.顺序表的删除顺序表的删除 操作接口T Delete(int i)：将线性表中的第i（1in）个元素删除，并返回被删除元素的值。删除前：(a1，ai-1，ai，ai+1，an)，删除后：(a1，ai-1，ai+1，an)，顺序表删除前后状态的对比如图2.13所示 删除操作要点：删除操作要点：元素
10、移动的方向元素移动的方向前移一个单元；前移一个单元；从第从第i+1个元素开始移动，直至最后一个元素；个元素开始移动，直至最后一个元素；在移动元素之前要取出被删元素。在移动元素之前要取出被删元素。分析边界情况：分析边界情况：如果表空，则发生下溢异常；如果表空，则发生下溢异常；如果元素的删除位置不合理，则引发删除位置异常。如果元素的删除位置不合理，则引发删除位置异常。1. 如果表空，则抛出下溢异常如果表空，则抛出下溢异常;2. 如果删除位置不合理，则抛出删除位置异常；如果删除位置不合理，则抛出删除位置异常；3. 取出被删元素；取出被删元素；4. 将第将第i+1个元素直至最后一个元素分别向前移动一个
11、位置；个元素直至最后一个元素分别向前移动一个位置；5. 表长减表长减1，返回被删元素值；，返回被删元素值；C语言描述template T SeqList:Delete(int i) if (length=0) throw 下溢下溢; if (ilength) throw 位置位置; x=datai-1; for (j=i+1; j=length; j+) for (j=i; jfront=q-rear=0; 2 2）判断队列空）判断队列空int QueueEmpty(CircularQueue *q) /*队列为空返回队列为空返回1，否则返回，否则返回0*/ if(q-front=q-rear
12、) exit(1); else exit(0); 3 3）入队）入队void InsertQueue(CircularQueue *q, ElemType x) if(q-rear+1)%MAXSIZE=q-front) printf(n 队满队满，上溢！，上溢！); exit(1); q-dataq-rear=x; /*新元素插入到新元素插入到队队尾尾*/ q-rear=(q-rear+1)%MAXSIZE; /*尾指尾指针针加加1*/ 4 4）出队）出队ElemType DeleteQueue(CircularQueue *q) ElemType x; if(QueueEmpty(q) p
13、rintf(n 队队空，下溢！空，下溢！); exit(1); x=q-dataq-front; /*取出取出队头队头元素元素*/ q-front=(q-front+1)%MAXSIZE; /*队头队头指指针针加加1*/ return x; 5 5）读取队头元素）读取队头元素ElemType GetHead(CircularQueue *q) ElemType x; if(QueueEmpty(q) printf(n 队队空，下溢！空，下溢！); exit(1);x=q-dataq-front; /*取出取出队头队头元素元素*/return x; 4.4.队列应用举例队列应用举例 例如，某银行
14、储蓄所有一个服务窗口，例如，某银行储蓄所有一个服务窗口，该窗口在某个时刻只能接待一位顾客，假该窗口在某个时刻只能接待一位顾客，假设为一位顾客服务的时间为定值，在顾客设为一位顾客服务的时间为定值，在顾客人数众多时需要在窗口排队，若队列用人数众多时需要在窗口排队，若队列用q q表表示，顾客到达的时间是随机的，约定按如示，顾客到达的时间是随机的，约定按如下方式处理：每单位时间内产生一个随机下方式处理：每单位时间内产生一个随机数数arrive arrive （0arrive10arrive1），如果），如果arrive arrive 小于小于probprob（ 0 prob 1 0 prob 1 ，由程序输入的，由程序输入的特定值），则记为有特定值），则记为有1 1人到达。顾客用整数人到达。顾客用整数表示，其值为该顾客进入队列的时间。表示，其值为该顾客进入队列的时间。
