数据结构概念及顺序表_第1页
数据结构概念及顺序表_第2页
数据结构概念及顺序表_第3页
数据结构概念及顺序表_第4页
数据结构概念及顺序表_第5页
已阅读5页,还剩17页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构概念及顺序表第1页,共22页,2023年,2月20日,星期六2.1数据结构基本概念1.数据(data)

数据是指能够输入到计算机中,并被计算机识别和处理的符号的集合。

2.数据元素(dataelement)

数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项(字段),故不是组成数据的最小单位第2页,共22页,2023年,2月20日,星期六数据结构(datastructure)

是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容,即数据的逻辑结构,数据的存贮结构和对数据所施加的运算。

这三个方面的关系为:

数据的逻辑结构独立于计算机,是数据本身所固有的存贮结构是逻辑结构在计算机存贮器中的映像,必须依赖于计算机。运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构,但运算的实现必依赖于存贮结构。第3页,共22页,2023年,2月20日,星期六数据结构基本类型

线性结构——

通迅录、成绩单、花名册树形结构——

电子字典、家谱、目录图状结构——

交通线路、通信网络第4页,共22页,2023年,2月20日,星期六数据结构中常用的存贮结构(1)顺序存贮

所有元素存放在一片连续的存贮单元中,逻辑上相邻的元素存放到计算机内存仍然相邻。(2)链式存贮

所有元素存放在可以不连续的存贮单元中,元素之间的关系通过地址确定,逻辑上相邻的元素存放到计算机内存后不一定是相邻的。(3)索引存贮(略) (4)散列存贮(略)第5页,共22页,2023年,2月20日,星期六算法(algorithm)

通俗地讲,算法就是一种解题的方法。更严格地说,算法是由若干条指令组成的有穷序列,它必须满足下述条件(也称为算法的五大特性):(1)输入:具有0个或多个输入的外界量(算法开始前的初始量)(2)输出:至少产生一个输出,它们是算法执行完后的结果。(3)有穷性:每条指令的执行次数必须是有限的。(4)确定性:每条指令的含义都必须明确,无二义性。(5)可行性:每条指令的执行时间都是有限的。第6页,共22页,2023年,2月20日,星期六1.时间复杂度

一个算法花费的时间与算法中语句的执行次数成正比,哪个算法中语句执行次数多,它花费时间就多。

数据结构中数据元素个数n称为问题的规模,当n不断变化时,语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数量级来衡量。 例如:for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

d[i][j]=data[i][j]+1;算法分析O(n2)第7页,共22页,2023年,2月20日,星期六2.空间复杂度

与时间复杂度类似,空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似,不再赘述。第8页,共22页,2023年,2月20日,星期六2.2

线性数据结构

线性表是由有限个同类型的数据元素组成的有序序列,一般记作(a1,a2,…,an)。除了a1和an之外,任意元素ai都有一个直接前趋ai-1和一个直接后继ai+1。a1无前趋,an无后继。

线性表的存储结构主要有顺序存储结构和链式存储结构两种。

第9页,共22页,2023年,2月20日,星期六顺序表

采用顺序存储结构的线性表称为顺序表,它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素,其存储位置也彼此相邻。

假定元素a1的物理地址是Loc(a1),每个元素占d个存储单元,则第i个元素的存储位置为:Loc(ai)=Loc(a1)+(i-1)*d

length=nmaxsize01i-2i-1in-1a2…ai-1aiai+1a1…an第10页,共22页,2023年,2月20日,星期六顺序表类描述constintMAXSIZE=100; //顺序表最大允许长度classSeqList{public: ElemTypedata[MAXSIZE]; //存储数据的数组

intlength; //顺序表当前长度

SeqList(){length=0;}//构造函数

voidClearList(){length=0;}//将顺序表置为空表

//判断顺序表是否为空表

boolIsListEmpty(){returnlength==0;} (下页continue….)第11页,共22页,2023年,2月20日,星期六

(接上页)//判断顺序表是否为满

boolIsListFull(){returnlength==MAXSIZE;} //在表中删除第i个元素

voidListDelete(inti);//在表中第i个位置插入新元素xvoidListInsert(inti,ElemTypex);intFind(ElemTypex); //在表中查找元素};(1)ElemType代表数组的某种类型。(2)length表示线性表当前长度,初始长度为0(空表),最大不超过maxsize。第12页,共22页,2023年,2月20日,星期六顺序表的主要算法

(1)在表中第i个位置插入新元素x

算法实现的主要步骤是: ①判断插入位置的合理性以及表是否已满。

②从最后一个元素开始依次向前,将每个元素向后移动一个位置,直到第i个元素为止。

③向空出的第i个位置存入新元素x。 ④最后还要将线性表长度加一。第13页,共22页,2023年,2月20日,星期六第14页,共22页,2023年,2月20日,星期六voidSeqList::ListInsert(inti,ElemTypex){if(i<1||i>length+1||length==MAXSIZE) cout<<"插入位置错误或表满"; else{ for(intj=length-1;j>=i-1;j--){ data[j+1]=data[j]; //元素依次向后移动

} data[i-1]=x; //向第i个位置存入新元素

length++; //表长度加1}}第15页,共22页,2023年,2月20日,星期六(2)在表中删除第i个元素

算法实现的主要步骤是: ①判断删除位置的合理性。

②从第i+1个元素开始,依次向后直到最后一个元素为止,将每个元素向前移动一个位置。这时第i个元素已经被覆盖删除。 ③最后还要将线性表长度减一。第16页,共22页,2023年,2月20日,星期六第17页,共22页,2023年,2月20日,星期六voidSeqList::Delete(inti){if(i<1||i>L->length) cout<<"表中没有第"<<i<<"个元素";else{ for(intj=i;j<=length-1;j++) data[j-1]=data[j];//元素依次向前移动

length--; } }第18页,共22页,2023年,2月20日,星期六(3)在表中查找某个元素

下面是根据数据元素本身的值进行查询的算法,x为需要查找的元素,算法返回元素的实际位置。

intSeqList::Find(ElemTypex) { for(inti=0;i<length;i++) {//查找成功,返回元素位置

if(data[i]==x)returni+1; } return0; //查找失败,返回0 }第19页,共22页,2023年,2月20日,星期六顺序表应用举例

【例2-1】利用顺序表表示多项式,实现两个一元多项式L1(x)和L2(x)相加,将结果存于多项式L3(x)中。并计算当L1(x)=3.5+4x2+2.5x4,L2(x)=1.5x+2.6x2+1.6x3时,L3(x)的结果是什么。

一元多项式P(x)可以表示为((a0,0),(a1,1),…,(an,n))。例如线性表((6,1),(-5,4),(8,10))表示多项式:

P(x)=6x-5x4+8x10。第20页,共22页,2023年,2月20日,星期六

用顺序表L1和L2存放需要相加的两个多项式L1(x)和L2(x),用顺序表L3来存放结果。多项式相加算法可按照下列步骤实现:①设定两个位置变量i和j指向顺序表L1和L2的第一个元素,设定位置变量k表示L3的插入位置,插入位置从1开始。本例中i、j和k初值均为1。②比较i和j两个位置数据元素的指数项,如果L1中第i项指数较小,则将此项数据元素复制到L3的位置k

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论