数据结构及应用概念及顺序表.ppt

第1/42页,第2章数据结构及应用概念及顺序表,西安交通大学计教中心,第2/42页,思考问题,数据结构要研究什么问题？什么是线性数据结构和线性表？如何描述线性表？线性表在计算机中如何存放？有几种存储形式？它们的特点是什么？如何处理线性数据结构中的数据？,第3/42页,数据结构问题的由来,计算机求解问题的过程步骤：,求解结果,用户需求,第4/42页,数据结构,数据结构是计算机的专业技术基础课。它研究的主要问题有：分析数据（计算机加工的对象）的特征 选择适当逻辑存储结构和物理存储结构 在存储结构的基础上实现对数据的操作,第5/42页,2.1 数据结构基本概念,1数据（data）数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。2数据元素（data element）数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位,第6/42页,数据结构（data structure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。,第7/42页,数据的逻辑结构,它是描述数据间的顺序（逻辑）关系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存放。一般用下列二元组来描述：DS=（D，R）其中：D：是数据元素的有限集合；R：是数据元素之间关系的集合。,与数据在计算机中的存放的物理位置无关,第8/42页,举例,课题组由1名教师、13名研究生、16名本科生组成；成员关系是：教师指导研究生、研究生指导12名本科生。定义DS如下：Group=（D，R）其中：,D=T，G1，,Gn,S11,Snm 1 n 3,1 m 2,R=R1,R2R1=|1 i n,1 n 3R2=|1in,1 j m,1 n 3,1 m 2,第9/42页,数据的存储结构,又称物理结构是指数据结构在计算机中的表示(又称映象),即数据在计算机中的存放。,数据库中的数据存放在计算机中的物理位置,第10/42页,逻辑结构和存储结构的关系,数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任何操作。任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。,第11/42页,数据存储结构分类,顺序存储结构链式存储结构索引存储结构散列存储结构,第12/42页,顺序存储结构,把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。数据结点结构:,d1 d2 dn,数据域,特点:连续存放;逻辑上相邻,物理上也相邻。结构简单，易实现。插入、删除操作不便（需大量移动元素）。,第13/42页,链式存储结构,以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。数据结点结构:,d1,.,d2,dn,数据域 指针域,特点:非连续存放,借助指针来表示元素间的关系;插入、删除操作简单，只要修改指针即可；结构较复杂，需要额外存储空间。,第14/42页,索引存储结构,数据按索引形式存放。存储时分为：数据项和索引号；通过索引表记录逻辑号（记录号）和物理号（存储序号）之间的对应关系。数据结点结构:,12 21 35 2 45 5 10,4 3 2 7 1 6 5,特点：非连续存放；检索速度快；增、删操作简单。,序 号：1 2 3 4 5 6 7,数据项：索引号：,第15/42页,散列存储结构,在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到它的存储地址，即D=F（E）。哈希查找中的哈希表就是这样一种存储结构。特点：数据元素间无内在联系；存储形式不定。,第16/42页,数据运算,数据运算是指对存放在物理结构上的数据,按定义的逻辑结构进行的各种操作。常见操作有：输入、检索、插入、删除、修改、排序等。,第17/42页,数据结构分类,第18/42页,数据结构基本类型,线性结构 通迅录、成绩单、花名册树形结构 电子字典、家谱、目录图状结构 交通线路、通信网络,第19/42页,算法（algorithm）,通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）：输入：具有0个或多个输入的外界量（算法开始前的初始量）输出：至少有一个输出，是算法执行完后的结果。有穷性：每条指令的执行次数必须是有限的。确定性：每条指令的含义都必须明确，无二义性。可行性：每条指令的执行时间都是有限的。,第20/42页,1时间复杂度 一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间就多。数据结构中数据元素个数n称为问题的规模，当n不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数量级来衡量。例如：for(i=1;i=n;i+)for(j=1;j=i;j+)dij=dataij+1;,算法分析,第21/42页,算法的评价,算法评价的标准：时间复杂度 指在计算机上运行该算法所花费的时间。用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有：O（1）O（logn）O（n）O（n2）常数阶 对数阶 线性阶 平方阶空间复杂度 指算法在计算机上运行所占用的存储空间。度量同时间复杂度。,第22/42页,时间复杂度举例,（a）X：=X+1；,（b）FOR I：=1 TO n DO X：=X+1；,（c）FOR I：=1 TO n DO FOR J：=1 TO n DO X：=X+1；,O（1）,O（n）,O（n2）,第23/42页,2、空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。,第24/42页,2.2 线性数据结构,线性表是由有限个同类型的数据元素组成的有序序列，一般记作（a1,a2,an）。除了a1和an之外，任意元素ai都有一个直接前趋ai-1和一个直接后继ai+1。a1无前趋，an无后继。例如，一星期七天的英文缩写表示：（Sun，Mon，The，wed，Thu，Fri，Sat）是一个线性表，其中的元素是字符串，表的长度为7。,第25/42页,线性表的逻辑结构,定义：线性表是n（n0）个元素a1,a2,an 的有限序列；表中每个数据元素，除了第1个和最后1个外，有且仅有一个前趋元素和后继元素。形式定义：含有n个数据元素的线性表是一种数据结构，表示为：Linear_list=(D,R)其中:D=ai|aiD0,i=1,2,3,n,n 0 R=N,N=|ai-1,ai D0,i=1,n D是数据元素的有限集合，R是D上逻辑关系的有限集合。关系N是一个有序偶对的集合。,第26/42页,顺序表,采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。假定元素a1的物理地址是Loc(a1)，每个元素占d个存储单元，则第i个元素的存储位置为：Loc(ai)=Loc(a1)+(i-1)*d,第27/42页,线性表元素存储示意图,a1,a2,.,ai,.,元素序号 内存状态 存储地址,1,2,.,i,.,LOC(a1),LOC(a1)+1,.,LOC(a1)+(i-1),.,第28/42页,顺序表类型描述,struct SeqList ElemType*data;/顺序表存储数组的地址 int maxsize;/顺序表最大允许长度 int length;/顺序表当前长度；SeqList list;/定义一个线性表list（1）ElemType代表数组的类型。（2）数组data需要在初始化函数中利用new操作动态申请，maxsize为其长度。数组的下标从0开始。（3）length表示线性表当前长度，初始长度为0（空表），最大不超过maxsize。,第29/42页,线性表的基本操作,Setnull（L）置空表Length（L）求表长度；求表中元素个数Get（L，i）取表中第i个元素（1i n）Prior（L，i）取i的前趋元素Next（L，i）取i的后继元素Locate（L，x）返回指定元素在表中的位置Insert（L，i，x）插入元素Delete（L，x）删除元素Empty（L）判别表是否为空,第30/42页,顺序表的主要算法,（1）顺序表的初始化 顺序表的初始化主要是为ElemType类型的数组申请空间，下面的初始化函数为顺序表申请了长度为size的空间。void Init(SeqList*L,int size)if(size 0)L-maxsize=size;L-length=0;L-data=new ElemTypesize;/申请空间else cout线性表初始化长度错误;,第31/42页,（2）在表中第 i 个位置插入新元素x 算法实现的主要步骤：判断插入位置的合理性以及表是否已满。从最后一个元素开始依次向前，将每个元素向后移动一个位置，直到第i个元素为止。向空出的第i个位置存入新元素x。最后还要将线性表长度加一。,示例,第32/42页,第33/42页,插入算法示意举例,设有数列4,5,8,10,21,30,43,59，长度为8，在“21”和“30”之间插入元素“25”。算法描述：从数列右边开始，即从第8个元素开始；为在第5个元素“21”后插入“25”，则要把其后的3个元素右移，移动元素个数是3（8-5）；for(int j=L-length-1;j=i-1;j-)/length 是元素个数(8)L-dataj+1=L-dataj;/j是插入位置(5)将空出的第6个位置，存放“25”。L-datai-1=x;/将x存放在第i-1 位置表长度加“1”L-length+;/加“1”后，结果为“9”最后，得到的结果数列是4,5,8,10,21,25,30,43,59,第34/42页,void Insert(SeqList*L,int i,ElemType x)if(iL-length+1|L-length=L-maxsize)coutlength-1;j=i-1;j-)L-dataj+1=L-dataj;/元素依次右移 L-datai-1=x;/向第 i 个位置存入新元素 xL-length+;/表长度加一,顺序表插入算法,第35/42页,（3）在表中删除第i个元素 算法实现的主要步骤是：判断删除位置的合理性。从第i+1个元素开始，依次向后直到最后一个元素为止，将每个元素向前移动一个位置。这时第i个元素已经被覆盖删除。最后还要将线性表长度减一。,第36/42页,第37/42页,删除算法示意举例,设有数列4,5,8,10,21,25,30,43,59，长度为9，将第6位的元素“25”删除。算法描述：从第7个元素开始(i+1)；将第7个元素“30”存入第6位，将“25”覆盖，即元素左移，移动元素个数是3（9-6）；for(int j=i;jlength-1;j+)/length是元素个数(9)L-dataj-1=L-dataj;/i是删除位置(6)长度减“1”L-length-；/操作后，length 等于8最后，得到的结果数列是4,5,8,10,21,30,43,59,第38/42页,void Delete(SeqList*L,int i)if(iL-length)coutlength-1;j+)L-dataj-1=L-dataj;/数据元素左移 L-length-;,顺序表删除算法,第39/42页,（4）在表中查找某个元素 下面是根据数据元素本身的值进行查询的算法，x为需要查找的元素，算法返回元素的实际位置。查找算法:int Find(SeqList*L,ElemType x)for(int i=0;ilength;i+)/查找成功,返回元素位置 if(L-datai=x)return i+1;return 0;/查找失败,返回 0,第40/42页,顺序表应用举例,【例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)的结果是:L3(x)=3.5+1.5x+6.6x2+1.6x3+2.5x4 一元多项式P(x)可表示为(a0,0),(a1,1),(an,n)。例如线性表(6,1),(-5,4),(8,10)表示多项式:P(x)=6x-5x4+8x10。,第41/42页,用顺序表L1和L2存放两个多项式L1(x)和L2(x)，用顺序表L3来存放结果。多项式相加算法可按照下列步骤实现：设定三个位置变量i、j和k，分别指向顺序表L1、L2和L3的第一个元素。本例中i、j和k初值均为1。比较i和j两个位置数据元素的指数项，如果L1中第i项指数小，则将此项数据元素复制到L3的位置k中，i+和k+；如果L2中第j项指数小，则同样是将此项复制到L3中，j+和k+；如果两项指数项相等，则合并同类项后再将结果复制到L3中，并同时i+、j+和k+。当L1或L2中的数据元素处理完毕，则将另一个顺序表的剩余部分复制到L3中。,算法描述,第42/42页,参照程序例2-1,P2-1.cpp,线性表操作的综合例子,第43/42页,顺序存储结构的特点,数据连续存放、随机存取逻辑上相邻，物理上也相邻存储结构简单、易实现插入、删除操作不便存储密度大，空间利用率高结论：顺序存储结构适合于表中元素变动较少的情况。,第44/42页,结束语,欢迎参加到中心网站软件开发技术基础课程的学习讨论中来。中心网址：http:/课件下载地址:我的E-mail地址:答疑安排：每星期五下午：4:006:00 地点：计教中心505房间,