




已阅读5页,还剩27页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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.队列应用举例,例如,某银行储蓄所有一个服务窗口,该窗口在某个时刻只能接待一位顾客,假设为一位顾客服务的时间为定值,在顾客人数众多时需
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 中国双向拉伸尼龙薄膜项目创业投资方案
- 2025年矿井通风智能监控系统研究的开题报告
- 山东省生态环境监测中心省属事业单位招聘考试真题2024
- 2025赣州市物业管理委托合同
- 广东中山东凤镇党建和组织人事办公室招聘考试真题2024
- 剪辑技能考试试题及答案
- 监测监控考试试题及答案
- 代持协议书 英文
- 基础统计考试试题及答案
- 机场体育考试试题及答案
- 民航救生衣演示知识培训课件
- 2025-2026学年第一勾股定理、第二章实数检测试卷北师大版八年级数学上册
- 2025内初班语文试卷及答案
- 2025年甘肃省酒泉市瓜州县招聘村副职干部30人考试参考试题及答案解析
- 2025年驾照三力测试试题题库及答案
- 农村厨房翻建申请书
- 网红集装箱商业街方案
- 文库发布:《青鸟》课件
- 2025年上半年银行从业初级考试真题及答案
- 安全生产检查考核办法
- 2025年度济南市工会社会工作专业人才联合招聘(47人)笔试参考题库附答案解析
评论
0/150
提交评论