下一页上一页停止放映第2章数据结构及应用概念及顺序表西安交通大学计教中心西安交通大学计教中心ctec.xjtu.edu.cn端庄鹤镇诬捻浙蝗未膳割哗误僧道强茶曝淋畜巍踏蒋场最干媒至肤颗针腿第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件下一页上一页停止放映思考问题数据结构要研究什么问题？什么是线性数据结构和线性表？如何描述线性表？线性表在计算机中如何存放？有几种存储形式？它们的特点是什么？如何处理线性数据结构中的数据？孕乱到铺雁裂血董植察浇傣群赐综柬度彰西羚毖港烃燥曙汀梢馅坑域珐貌第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件2 2下一页上一页停止放映数据结构问题的由来计算机求解问题的过程步骤： 调试程序调试程序编制编制程序程序求解求解结果结果运行运行程序程序结果输出结果输出用户用户需求需求数据类型、格式、数据类型、格式、逻辑结构逻辑结构数据数据逻辑逻辑运算运算数据的物理数据的物理操作操作分析抽象分析抽象实际实际问题问题模型求解模型求解问题问题模型模型命令命令编程编程求解求解算法算法口旧峨兢途项澄奋净挟越遁煽值敝迄堡斧晌鼠裸嚎旺镊竞孽涣憨龄橡携氨第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件3 3下一页上一页停止放映数据结构 数据结构是计算机的专业技术基础课。它研究的主要问题有： 分析数据（计算机加工的对象）的特征 选择适当逻辑存储结构和物理存储结构 在存储结构的基础上实现对数据的操作宛膝酣罪萨舜憋余笑诣策梳苇树孙步栓酋锻驶卉宦师壁蝎辫桓胆帆滑括逢第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件4 4下一页上一页停止放映2.1 数据结构基本概念1数据（数据（data）数据是指能够输入到计算机中，并被计算机识数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合别和处理的符号的集合。 2数据元素（数据元素（data element）数数据据元元素素是是组组成成数数据据的的基基本本单单位位。数数据据元元素素是是一一个个数数据据整整体体中中相相对对独独立立的的单单位位。但但它它还还可可以以分分割割成成若若干干个个具具有有不不同同属属性性的的项项（字字段段），故故不不是是组成数据的最小单位组成数据的最小单位眼诊嘿阁勿咖船玻滞捞奄巾专衅啮叭订咬哑擞其旗扯洗彰组彩锤猾冶项掘第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件5 5下一页上一页停止放映数据结构（data structure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。 宣英湖分向垣币丸毁炉源惧众箱叛五锯撰疥柱肚安摹歌开颖镜遮前草竿焙第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件6 6下一页上一页停止放映数据的逻辑结构 它是描述数据间的顺序（逻辑）关它是描述数据间的顺序（逻辑）关系，只是抽象地反映数据元素的结系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存构，而不管它们在计算机中如何存放。一般用下列二元组来描述：放。一般用下列二元组来描述： DS= DS=（D D，R R） 其中：其中： D D：是数据元素的有限集合；：是数据元素的有限集合； R R：是数据元素之间关系的集合。：是数据元素之间关系的集合。与数据在计算机中的存放的物理位置无关遗柠湖目雷萌考便偿匙霞八中苔芬页列煤脓撅倾俱毋条仓蹦鬃渍晶拌惶凋第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件7 7下一页上一页停止放映举例课题组由课题组由1 1名教师、名教师、1313名研究生、名研究生、1616名本名本科生组成；成员关系是：教师指导研究生、科生组成；成员关系是：教师指导研究生、研究生指导研究生指导1212名本科生。名本科生。 定义定义DSDS如下：如下： Group= Group=（D D，R R） 其中：其中： D=T，G1，,Gn,S11,Snm 1 n 3 , 1 m 2R=R1,R2R1=|1 i n , 1 n 3R2=|1in ,1 j m , 1 n 3 , 1 m 2 突烛需叮斯专越烁享棕耐革孽游操怒窍滋惋尘俊虽肾狮胯痔眯靖箔决裔蜘第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件8 8下一页上一页停止放映数据的存储结构又称物理结构又称物理结构是是指指数数据据结结构构在在计计算算机机中中的的表表示示( (又又称称映映象象),),即即数数据据在在计计算算机机中中的的存放。存放。数据库中的数据存放在计算机中的物理位置恬纳汲柠袜剐舷岗诡辰扫骚靛磊帽零辟瓣蓝尾湖晚或轮真衰寝淋干蛔硝谜第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件9 9下一页上一页停止放映逻辑结构和存储结构的关系v数据的数据的逻辑结构逻辑结构是从逻辑关系（某种顺序）上观是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。形式上进行研究、推理、运算等各种操作。v数据的数据的存储结构存储结构是逻辑结构在计算机中的实现，是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任是依赖于计算机的；离开了机器，则无法进行任何操作。何操作。v任何一个任何一个算法的设计算法的设计取决于选定的逻辑结构；而取决于选定的逻辑结构；而算法的最终实现算法的最终实现依赖于采用的存储结构。依赖于采用的存储结构。寡鲁萌浮馋陛斤虾厚随闷磁得泣毡缆谋氰篮残胚纵褥荒桑槛哥差括爆叶掺第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件1010下一页上一页停止放映数据存储结构分类v顺序存储结构顺序存储结构v链式存储结构链式存储结构v索引存储结构索引存储结构v散列存储结构散列存储结构 拟蛋梗摇媳奉郎瘟吵锦椅佃磋究根示签饿虱帝督单贫傈尖边颖保颇毕视橡第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件1111下一页上一页停止放映顺序存储结构 把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。数据结点结构: d1 d2 dn数据域数据域特点特点: 连续存放连续存放;逻辑上相邻逻辑上相邻,物理上也相邻。物理上也相邻。 结构简单，易实现。结构简单，易实现。 插入、删除操作不便（需大量移动元素）。插入、删除操作不便（需大量移动元素）。捏估厚塌层驮僵隔脚毖誉廊伯交齿折募泥皑淌癌浅镣送动祷墓沼蚂韩那胰第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件1212下一页上一页停止放映链式存储结构 以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。数据结点结构: d1. d2dn 数据域数据域 指针域指针域特点特点:非连续存放非连续存放,借助指针来表示元素间的关系借助指针来表示元素间的关系;插入、删除操作简单，只要修改指针即可；插入、删除操作简单，只要修改指针即可；结构较复杂，需要额外存储空间。结构较复杂，需要额外存储空间。潍宝朴雍素撵慷自买带眠垂君赋胸召贡辆鳞攒惑洒萎捣嗅奢基诈族套坚漏第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件1313下一页上一页停止放映索引存储结构 数据按索引形式存放。存储时分为：数据项和索引数据按索引形式存放。存储时分为：数据项和索引号；通过索引表记录逻辑号（记录号）和物理号号；通过索引表记录逻辑号（记录号）和物理号（存储序号）之间的对应关系。（存储序号）之间的对应关系。 数据结点结构数据结点结构: :12 21 35 2 45 5 10 4 3 2 7 1 6 5 数据域数据域 索引顺序号索引顺序号特点：特点：非连续存放；非连续存放；检索速度快；检索速度快；增、删操作简单。增、删操作简单。 序 号： 1 2 3 4 5 6 7 数据项：索引号：述频相雕治售渤拇腰楷栈技沽监岳钾佬吼器镰齐隧唤膘合土祭赌腔兹咎折第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件1414下一页上一页停止放映散列存储结构在数据元素与存储位置之间建立一种在数据元素与存储位置之间建立一种存储关系存储关系F F，根据这种关系，根据这种关系F F，已知元，已知元素素E E，就可以得到它的存储地址，即，就可以得到它的存储地址，即D=FD=F（E E）。）。哈希查找中的哈希表就是这样一种存哈希查找中的哈希表就是这样一种存储结构。储结构。 特点：特点：数据元素间无内在联系；数据元素间无内在联系；存储形式不定。存储形式不定。锭刚辙渗欧飘刃谤夹廊塞户爵杭政烯姚傻刺盂鸯效巍烯氦雕惭按檄弗柯仔第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件1515下一页上一页停止放映数据运算数据运算是指对存放在物理结构上的数据数据运算是指对存放在物理结构上的数据, ,按定义的逻辑结构进行的各种操作。按定义的逻辑结构进行的各种操作。 常见操作有：常见操作有：输入、检索、插入、删除、修改、排序输入、检索、插入、删除、修改、排序等。等。挛挥谊佯申齐洞剂窗蚌银傲笔咙猴赶押然谭刮讣富斩沧疡辗涧视满萌津庆第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件1616下一页上一页停止放映数据结构分类 线性表线性表堆栈堆栈队列队列串串数组数组树树二叉树二叉树图图线性结构线性结构非线性结构非线性结构数据结构数据结构DSDS裂咏健佛怔万凰雨鲁匹釜旷冰桥撇蓝需眨砧诌奏韭惟容硕赖澄评待浩离烘第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件1717下一页上一页停止放映数据结构基本类型 线性结构线性结构 通迅录、成绩单、花名册通迅录、成绩单、花名册树形结构树形结构 电子字典、家谱、目录电子字典、家谱、目录图状结构图状结构 交通线路、通信网络交通线路、通信网络脖尾垛篆块却捶污羡倒诞宴洗烙股札换桩况医缨变髓郭甸强商祸健窥凰扎第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件1818下一页上一页停止放映算法（algorithm） 通通通通俗俗俗俗地地地地讲讲讲讲，算算算算法法法法就就就就是是是是一一一一种种种种解解解解题题题题的的的的方方方方法法法法。更更更更严严严严格格格格地地地地说说说说，算算算算法法法法是是是是由由由由若若若若干干干干条条条条指指指指令令令令组组组组成成成成的的的的有有有有穷穷穷穷序序序序列列列列，它它它它必必必必须须须须满满满满足足足足下述条件（也称为算法的五大特性）：下述条件（也称为算法的五大特性）：下述条件（也称为算法的五大特性）：下述条件（也称为算法的五大特性）：输输入入：具具有有0 0个个或或多多个个输输入入的的外外界界量量（算算法法开开始始前前的的初始量）初始量）输出输出：至少有一个输出，是算法执行完后的结果。至少有一个输出，是算法执行完后的结果。有穷性有穷性：每条指令的执行次数必须是有限的。每条指令的执行次数必须是有限的。确定性确定性：每条指令的含义都必须明确，无二义性。每条指令的含义都必须明确，无二义性。可行性可行性：每条指令的执行时间都是有限的。每条指令的执行时间都是有限的。床瘟炮佬恃孜凡跟愧剿茸经蚊虐探蹄跨忱跪搁逝硼股疗知勾底室眼遣彻狭第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件1919下一页上一页停止放映1 1时间复杂度时间复杂度 一个算法花费的时间与算法中语句的执行次一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费数成正比，哪个算法中语句执行次数多，它花费时间就多。时间就多。 数据结构中数据元素个数数据结构中数据元素个数n n称为问题的规模，称为问题的规模，当当n n不断变化时，语句的执行次数也会变化。一不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数个算法中的时间复杂度一般用语句执行次数的数量级来衡量。量级来衡量。例如：例如： for(i=1; i=n; i+) for(j =1; j=i; j+) dij=dataij+1;算法分析O(n2)泻凳大逃兄戏残钥宅粉残旗吃嫩海饲缺丙箕缉裤勒腥每毯果舶患炭皆京宏第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件2020下一页上一页停止放映算法的评价算法评价的标准：算法评价的标准：时间复杂度时间复杂度 指在计算机上运行该算法所花费的时间。用指在计算机上运行该算法所花费的时间。用“O“O（数量级）（数量级）”来表示，称为来表示，称为“阶阶”。常见。常见的时间复杂度有：的时间复杂度有： O O（1 1） O O（lognlogn） O O（ n n ） O O（ n n2 2 ） 常数阶常数阶 对数阶对数阶 线性阶线性阶 平方阶平方阶空间复杂度空间复杂度 指算法在计算机上运行所占用的存储空间。指算法在计算机上运行所占用的存储空间。度量同时间复杂度。度量同时间复杂度。 屁煮娶审找讨替宽狂登育剁圈需晚道倘舔罕朱甫柬惊唁凄蔽瘫宰盏涸敷但第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件2121下一页上一页停止放映时间复杂度举例（a a） X X：=X+1 =X+1 ；（b b） FOR I FOR I：=1 TO n DO =1 TO n DO X X：= X+1= X+1；（c c） FOR I FOR I：= 1 TO n DO= 1 TO n DO FOR J FOR J：= 1 TO n DO= 1 TO n DO X X：= X+1= X+1；O O（ 1 1 ）O O（ n n ）O O（ n n2 2 ）棵壹庇拼永凤肆啃躬抚限纫沫栅忧壤詹馈褂刷搭桥拽幼验缉师芥瘟萧且嘉第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件2222下一页上一页停止放映2 2、空间复杂度、空间复杂度与时间复杂度类似，空间复杂度是指算法与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。似，不再赘述。用沈蛮谤勋孤础班膊誉襄剿隅狐淑探鳞噬馅谊菇碟狰封歼貌泛庄氨奏衰花第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件2323下一页上一页停止放映2.2 线性数据结构 线性表是由有限个同类型的数据元素组成的有线性表是由有限个同类型的数据元素组成的有序序列，一般记作序序列，一般记作（a a1 1,a,a2 2,a,an n）。除了。除了a a1 1和和a an n之之外，任意元素外，任意元素a ai i都有一个直接前趋都有一个直接前趋a ai-1i-1和一个直接和一个直接后继后继a ai+1i+1。 a a1 1无前趋，无前趋，a an n无后继。无后继。 例如，一星期七天的英文缩写表示：例如，一星期七天的英文缩写表示： （SunSun，MonMon，TheThe，wedwed，ThuThu，FriFri，SatSat） 是一个线性表，其中的元素是字符串，表的长度是一个线性表，其中的元素是字符串，表的长度为为7 7。亏晕街犹极瓮桥柠普数河幢裳磊莎吵唉脾扳剧危舀囊栖盛惮拷旭墟翌痘驯第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件2424下一页上一页停止放映线性表的逻辑结构定义：定义： 线性表是线性表是n n（n n 0 0）个元素）个元素a a1 1,a,a2 2,a,an n 的的有限序列；表中每个数据元素，除了第有限序列；表中每个数据元素，除了第1 1个和最个和最后后1 1个外，有且仅有一个前趋元素和后继元素。个外，有且仅有一个前趋元素和后继元素。形式定义：形式定义： 含有含有n n个数据元素的线性表是一种数据结构，表个数据元素的线性表是一种数据结构，表示为：示为： Linear_list=( D , R ) Linear_list=( D , R ) 其中其中: : D=a D=ai i | a | ai i D D0 0,i=1,2,3,n,n ,i=1,2,3,n,n 00 R=N, N=a R=N, N=|a|ai-1i-1,a,ai i D D0 0 ,i=1,n ,i=1,n D D是数据元素的有限集合，是数据元素的有限集合，R R是是D D上逻辑关系的有上逻辑关系的有限集合。关系限集合。关系N N是一个有序偶对的集合。是一个有序偶对的集合。婉酉漳横啦助捕派孤脯逞黍燕呼坞霖莫虱非仕能宋磁艘新史疾看罚筛茨折第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件2525下一页上一页停止放映顺序表 采用顺序存储结构的线性表称为顺序表，它的数采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。中。逻辑上相邻的数据元素，其存储位置也彼此相邻。假定元素假定元素a1的物理地址是的物理地址是Loc(aLoc(a1 1) )，每个元素占，每个元素占d个存储单元，则第个存储单元，则第i个元素的存储位置为个元素的存储位置为：Loc(ai) = Loc(a1) + (i-1) * d length=n maxsize 0 1 i-2 i-1 i n-1 a2ai-1aiai+1a1an罢掠研阵个阜剩湿贞遮包袖广坊延窍丰阐菠邪彻晕持冯崇幽降顶玩猾歼边第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件2626下一页上一页停止放映线性表元素存储示意图 a1a2.ai.元素序号元素序号 内存状态内存状态 存储地址存储地址12. i.LOC(a1)LOC(a1)+1.LOC(a1)+(i-1).蚊龙魄癸惕忍巡翁租撑挡豢趟寨吻浆甩玩珍制错旁气尽翰浩辉轮倡公陋布第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件2727下一页上一页停止放映顺序表类型描述 struct SeqList ElemType *data; / 顺序表存储数组的地址顺序表存储数组的地址 int maxsize; / 顺序表最大允许长度顺序表最大允许长度 int length; / 顺序表当前长度顺序表当前长度 ； SeqList list;/ 定义一个线性表定义一个线性表list （1）ElemType代表数组的类型。代表数组的类型。（2）数组）数组data需要在初始化函数中利用需要在初始化函数中利用new操作动态操作动态申请，申请，maxsize为其长度。数组的下标从为其长度。数组的下标从0开始。开始。（3）length表示线性表当前长度，初始长度为表示线性表当前长度，初始长度为0（空表）（空表），最大不超过，最大不超过maxsize。间昌肘宾珠喷部舌牌珐实饵蘑缚歪胰父睹某信厅勒饲灼蹿泅满蔼屁满娩痘第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件2828下一页上一页停止放映线性表的基本操作SetnullSetnull（L L） 置空表置空表LengthLength（L L） 求表长度；求表中元素个数求表长度；求表中元素个数GetGet（L L，i i） 取表中第取表中第i i个元素（个元素（1 1 i i n n）PriorPrior（L L，i i） 取取i i的前趋元素的前趋元素NextNext（L L，i i） 取取i i的后继元素的后继元素LocateLocate（L L，x x） 返回指定元素在表中的位置返回指定元素在表中的位置InsertInsert（L L，i i，x x） 插入元素插入元素DeleteDelete（L L，x x） 删除元素删除元素EmptyEmpty（L L） 判别表是否为空判别表是否为空料侮垄暮吾焕叔坞躇幼而旬钳曙灭铡头揣蹲鸥庶荣寒悦舅毖赶敌售附距削第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件2929下一页上一页停止放映顺序表的主要算法 （1 1）顺序表的初始化）顺序表的初始化 顺序表的初始化主要是为顺序表的初始化主要是为ElemType类型的数组申类型的数组申请空间，下面的初始化函数为顺序表申请了长度请空间，下面的初始化函数为顺序表申请了长度为为size的空间。的空间。void Init( SeqList *L, int size ) if( size 0 ) L-maxsize = size; L-length = 0; L-data = new ElemTypesize; /申请空间申请空间else coutlength-1; j=i-1; j- ) / length 是元素个数(8) L-dataj+1=L-dataj;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 判惨篷意辊蚕停碟践塘未悼肛扎弥共淋压暴达句妆困签丫参厨掷挎进睁膏第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件3333下一页上一页停止放映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+; / 表长度加一表长度加一 顺序表插入算法顺序表插入算法蛀丁盼卤颜伙奥雷接缠与商靴嚼宴舷殷杜犊建脯弦扎搜吮澡凭辣姐段冬建第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件3434下一页上一页停止放映（3）在表中删除第i个元素 算法实现的主要步骤是：算法实现的主要步骤是： 判断删除位置的合理性。判断删除位置的合理性。 从第从第i+1i+1个元素开始，依次向后直到个元素开始，依次向后直到最后一个元素为止，将每个元素向前移最后一个元素为止，将每个元素向前移动一个位置。这时第动一个位置。这时第i i个元素已经被覆盖个元素已经被覆盖删除。删除。 最后还要将线性表长度减一。最后还要将线性表长度减一。侮汁罚溃俘涕蔼鹏眷蛇眩赵漫碧恶冤镶苇子竭昔谱擒斗痘德眠虹讶食柞依第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件3535下一页上一页停止放映 0 1 2 i-2 i-1 i n-1 maxsize a1 a2 a3 ai-1 ai+1 an 0 1 2 i-2 i-1 i n-1 maxsize a1 a2 a3 ai-1 ai ai+1 an 序号序号 内容内容 序号序号 内容内容 删除前删除前 删除后删除后 顺序表中删除元素前后状态顺序表中删除元素前后状态 遏医锄唁禄昭拾抉啦跟捌证狡维坷旧伯宝基叫南起掖磷沧爪蒋蔫疹肘枫江第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件3636下一页上一页停止放映删除算法示意举例删除算法示意举例设有数列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 鼠豹蛤远羊爪根原组床苗囱氏蛹伪铀木囊跋狱匡蚀瞩词谐窄孝拂斡零踪罗第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件3737下一页上一页停止放映void Delete( SeqList *L, int i ) if(iL-length ) cout表中没有第表中没有第i个元素个元素; else for ( int j=i; jlength-1; j+ ) L-dataj-1 = L-dataj; /数据元素左移数据元素左移 L-length-; 顺序表删除算法顺序表删除算法槽准狡躁命赠侣诛许或驼乾隆徽原隧胺狞沈娱玖右尉幌骂颈省刃膀伊戳伊第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件3838下一页上一页停止放映（4）在表中查找某个元素 下下面面是是根根据据数数据据元元素素本本身身的的值值进进行行查查询询的的算算法法，x为为需需要要查查找找的的元元素素，算算法法返返回回元元素素的的实实际位置。查找算法际位置。查找算法: :int Find( SeqList *L, ElemType x ) for( int i = 0; ilength; i+ ) /查找成功查找成功, 返回元素位置返回元素位置 if( L-datai=x ) return i+1; return 0; /查找失败查找失败, 返回返回 0 哗缘腰氟匝媚栓疆屉畅窝盯伞株霸剩掠贯卡晌扇巩亩样匿删宏情挣丘扒漳第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件3939下一页上一页停止放映顺序表应用举例顺序表应用举例 【例【例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。彝援堰哇第亮骸钠盯航岳吾痔拖渺露抿唬坚瘩症遁蕉镊坎省弟乱痰纺愿盗第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件4040下一页上一页停止放映用用顺顺序序表表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中。中。算法描述算法描述 档移臀澄云紧冬藉诸淳堤仇胯吉腻珍宇默精扶巢崇钾矩宜扩淀高耽胞洱植第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件4141下一页上一页停止放映参照程序参照程序 例例2-12-1P2-1.cppP2-1.cpp线性表操作的综合例子线性表操作的综合例子 论卓榷攫沙根纠澎梨功拣僻瑞桌炊潍个会洽宗匙满裙浑鲁迫析盂谗惕耿推第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件4242下一页上一页停止放映顺序存储结构的特点数据连续存放、随机存取数据连续存放、随机存取逻辑上相邻，物理上也相邻逻辑上相邻，物理上也相邻存储结构简单、易实现存储结构简单、易实现插入、删除操作不便插入、删除操作不便存储密度大，空间利用率高存储密度大，空间利用率高结论结论： 顺序存储结构适合于表中元素变动顺序存储结构适合于表中元素变动较少的情况。较少的情况。位乔柔上寇员级邮辜盲星细篡酪扛誉封引菩芜幸地躯飞丸钵疯蠢美箭韩串第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件4343下一页上一页停止放映结束语欢迎参加到中心网站软件开发技术基础课程的学习讨论中来。中心网址： http:/ctec.xjtu.edu.cn课件下载地址: http:/202.117.35.160/moodle15我的E-mail地址: LZQctec.xjtu.edu.cn答疑安排： 每星期五下午：4:006:00 地点： 计教中心505房间亡鬃况渝蓬讣怀十笼馅奉腥切枚搁裤例亦肿诧涌怕彭布石萍夹嘱持膀擂砰第2章数据结构及应用概念及序表ppt课件第2章数据结构及应用概念及序表ppt课件4444