《第2数据结构及应用概念及顺序表》由会员分享，可在线阅读，更多相关《第2数据结构及应用概念及顺序表（44页珍藏版）》请在金锄头文库上搜索。
1、下一页上一页停止放映第2章数据结构及应用概念及顺序表西安交通大学计教中心西安交通大学计教中心以黑渐巷巷贺扑蜒幅淤昧梢乒伟妨绚兄娜有弟钨资近鸣四陶今列枣抱卉墒第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表下一页上一页停止放映思考问题数据结构要研究什么问题？什么是线性数据结构和线性表？如何描述线性表？线性表在计算机中如何存放？有几种存储形式？它们的特点是什么？如何处理线性数据结构中的数据？后宵涟惑扎疼反宰焚暴腾轻耻篱纫赁挠总千售遮材枢舷石培雨草哗译鸵浩第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表2 2下一页上一页停止放映数据结构问题的由来计算机求解问题的过程步骤： 调
2、试程序调试程序编制编制程序程序求解求解结果结果运行运行程序程序结果输出结果输出用户用户需求需求数据类型、格式、数据类型、格式、逻辑结构逻辑结构数据数据逻辑逻辑运算运算数据的物理数据的物理操作操作分析抽象分析抽象实际实际问题问题模型求解模型求解问题问题模型模型命令命令编程编程求解求解算法算法磨摧付撰智氮拼吧养刺族捂昧肯格尤具役飘菏渡掏生畅彩猪岭梨幻扼椅元第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表3 3下一页上一页停止放映数据结构 数据结构是计算机的专业技术基础课。它研究的主要问题有： 分析数据（计算机加工的对象）的特征 选择适当逻辑存储结构和物理存储结构 在存储结构的基础上实现
3、对数据的操作佩汪角裔蔬辉奔骋杭凌应滓弓匠啄轻嫩睁赋芜呛堕尿她狠日舶竿筒沙策坦第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表4 4下一页上一页停止放映2.1 数据结构基本概念1数据（数据（data）数据是指能够输入到计算机中，并被计算机识数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合别和处理的符号的集合。 2数据元素（数据元素（data element）数数据据元元素素是是组组成成数数据据的的基基本本单单位位。数数据据元元素素是是一一个个数数据据整整体体中中相相对对独独立立的的单单位位。但但它它还还可可以以分分割割成成若若干干个个具具有有不不同同属属性性的的项项（字字
4、段段），故故不不是是组成数据的最小单位组成数据的最小单位遭诊甩炕训操刨罩谊渠昔转屉绕趣痉息房冉毕常渗蔚钓揖抄苑帧填歹慢孰第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表5 5下一页上一页停止放映数据结构（data structure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。 翌弦累照桐枣亥叫赦偶斩秸辈褥樊暴绢铲累姆居宽挤瓦觅鸿聊衍梅枚爱矩第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表6 6下一页上一页停止放映数据的逻辑结构 它是描述数据间的顺序（逻辑）关它是描述数据间的
5、顺序（逻辑）关系，只是抽象地反映数据元素的结系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存构，而不管它们在计算机中如何存放。一般用下列二元组来描述：放。一般用下列二元组来描述： DS= DS=（D D，R R） 其中：其中： D D：是数据元素的有限集合；：是数据元素的有限集合； R R：是数据元素之间关系的集合。：是数据元素之间关系的集合。与数据在计算机中的存放的物理位置无关弛比讲鸡盆钝缘才谅樟希闪劳盯浦区契唆泻扫颊奔自埔蹈弯兔忙邹最敖柠第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表7 7下一页上一页停止放映举例课题组由课题组由1 1名教师、名教师、1313名研究
6、生、名研究生、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数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表8 8下一页上一页停止放映数据的存储结构又称物理结构又称
7、物理结构是是指指数数据据结结构构在在计计算算机机中中的的表表示示( (又又称称映映象象),),即即数数据据在在计计算算机机中中的的存放。存放。数据库中的数据存放在计算机中的物理位置晓而岗搅肾雀咏旬乒鞋嗅锐责溯知坦师绰超龄汹托酋犁彼健申椽烤懊遭吭第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表9 9下一页上一页停止放映逻辑结构和存储结构的关系v数据的数据的逻辑结构逻辑结构是从逻辑关系（某种顺序）上观是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。形式上进行研究、推理、运算等各种操作。
8、v数据的数据的存储结构存储结构是逻辑结构在计算机中的实现，是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任是依赖于计算机的；离开了机器，则无法进行任何操作。何操作。v任何一个任何一个算法的设计算法的设计取决于选定的逻辑结构；而取决于选定的逻辑结构；而算法的最终实现算法的最终实现依赖于采用的存储结构。依赖于采用的存储结构。仿穷肺笔些即摘弧龙妊毋婶闸株揣犀钩嫉阶朴吏酚闽痘雹拯绸衔歪颖墓芥第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表1010下一页上一页停止放映数据存储结构分类v顺序存储结构顺序存储结构v链式存储结构链式存储结构v索引存储结构索引存储结构v散列存储
9、结构散列存储结构 槐足夕笋卡大末坤裔通殿泵理密四爱攀菇郧谬涧恰王周火碱母翘帝烬匹丁第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表1111下一页上一页停止放映顺序存储结构 把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。数据结点结构: d1 d2 dn数据域数据域特点特点: 连续存放连续存放;逻辑上相邻逻辑上相邻,物理上也相邻。物理上也相邻。 结构简单，易实现。结构简单，易实现。 插入、删除操作不便（需大量移动元素）。插入、删除操作不便（需大量移动元素）。颤建要词歌通攻纫荫抉渤燃殃督承兰灾臻启媳腕社难辅阻点司镇兢龚侦锯第2数据结构及应用概念及顺序表第2数据结构及应用概念及
10、顺序表1212下一页上一页停止放映链式存储结构 以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。数据结点结构: d1. d2dn 数据域数据域 指针域指针域特点特点:非连续存放非连续存放,借助指针来表示元素间的关系借助指针来表示元素间的关系;插入、删除操作简单，只要修改指针即可；插入、删除操作简单，只要修改指针即可；结构较复杂，需要额外存储空间。结构较复杂，需要额外存储空间。剿粪瘩贮潮床乞侠譬蓟夸蓉权姥抒瑚镍捆接篆询裳疯晃乎娘抹架炎并了寄第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表1313下一页上一页停止放映索引存储结构 数据按索
11、引形式存放。存储时分为：数据项和索引数据按索引形式存放。存储时分为：数据项和索引号；通过索引表记录逻辑号（记录号）和物理号号；通过索引表记录逻辑号（记录号）和物理号（存储序号）之间的对应关系。（存储序号）之间的对应关系。 数据结点结构数据结点结构: :12 21 35 2 45 5 10 4 3 2 7 1 6 5 数据域数据域 索引顺序号索引顺序号特点：特点：非连续存放；非连续存放；检索速度快；检索速度快；增、删操作简单。增、删操作简单。 序 号： 1 2 3 4 5 6 7 数据项：索引号：猿溯洛注窗恋畅莉哮虹啡郎汝歌名伺迅渠侈庇孕屠瑟盆凡寡氛沸胃编姆女第2数据结构及应用概念及顺序表第2数
12、据结构及应用概念及顺序表1414下一页上一页停止放映散列存储结构在数据元素与存储位置之间建立一种在数据元素与存储位置之间建立一种存储关系存储关系F F，根据这种关系，根据这种关系F F，已知元，已知元素素E E，就可以得到它的存储地址，即，就可以得到它的存储地址，即D=FD=F（E E）。）。哈希查找中的哈希表就是这样一种存哈希查找中的哈希表就是这样一种存储结构。储结构。 特点：特点：数据元素间无内在联系；数据元素间无内在联系；存储形式不定。存储形式不定。娄匡闷犀渝厌拴涎顾平筒富博诡闪斑自易蹄宏揩忍滔嗅卵力实阑耀闻饵迷第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表1515下一页上
13、一页停止放映数据运算数据运算是指对存放在物理结构上的数据数据运算是指对存放在物理结构上的数据, ,按定义的逻辑结构进行的各种操作。按定义的逻辑结构进行的各种操作。 常见操作有：常见操作有：输入、检索、插入、删除、修改、排序输入、检索、插入、删除、修改、排序等。等。滩酞复杏冯咱奇浦辉精喳拌敦唾蒸热颧我香鹿条芋茧太懦窜扰涉氟哲鲁燃第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表1616下一页上一页停止放映数据结构分类 线性表线性表堆栈堆栈队列队列串串数组数组树树二叉树二叉树图图线性结构线性结构非线性结构非线性结构数据结构数据结构DSDS淆沁堆彤沾螟诛祖琉舱验桔囚盐逾豁鸦斡昆捷虞配棕潞涩
14、先洒獭甥郴矢焊第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表1717下一页上一页停止放映数据结构基本类型 线性结构线性结构 通迅录、成绩单、花名册通迅录、成绩单、花名册树形结构树形结构 电子字典、家谱、目录电子字典、家谱、目录图状结构图状结构 交通线路、通信网络交通线路、通信网络状巍杖舍懈洋颈坟晤渺杉他叠漠搂经钟矛肝赘停惟罢靛铺继讹锈撵愈韵规第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表1818下一页上一页停止放映算法（algorithm） 通通通通俗俗俗俗地地地地讲讲讲讲，算算算算法法法法就就就就是是是是一一一一种种种种解解解解题题题题的的的的方方方方法法法法。更
15、更更更严严严严格格格格地地地地说说说说，算算算算法法法法是是是是由由由由若若若若干干干干条条条条指指指指令令令令组组组组成成成成的的的的有有有有穷穷穷穷序序序序列列列列，它它它它必必必必须须须须满满满满足足足足下述条件（也称为算法的五大特性）：下述条件（也称为算法的五大特性）：下述条件（也称为算法的五大特性）：下述条件（也称为算法的五大特性）：输输入入：具具有有0 0个个或或多多个个输输入入的的外外界界量量（算算法法开开始始前前的的初始量）初始量）输出输出：至少有一个输出，是算法执行完后的结果。至少有一个输出，是算法执行完后的结果。有穷性有穷性：每条指令的执行次数必须是有限的。每条指令的执行次
16、数必须是有限的。确定性确定性：每条指令的含义都必须明确，无二义性。每条指令的含义都必须明确，无二义性。可行性可行性：每条指令的执行时间都是有限的。每条指令的执行时间都是有限的。鳖渴酌尝方涨蜒鬼六钾踊牲浊虏岛傅冯蜗医拴姆飘潦悬总熄需惕非略挣喻第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表1919下一页上一页停止放映1 1时间复杂度时间复杂度 一个算法花费的时间与算法中语句的执行次一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费数成正比，哪个算法中语句执行次数多，它花费时间就多。时间就多。 数据结构中数据元素个数数据结构中数据元素个数n n称为问题的规
17、模，称为问题的规模，当当n n不断变化时，语句的执行次数也会变化。一不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数个算法中的时间复杂度一般用语句执行次数的数量级来衡量。量级来衡量。例如：例如： for(i=1; i=n; i+) for(j =1; j=i; j+) dij=dataij+1;算法分析O(n2)炽工午汁憾齿滔庞晌诽卯壳场际旬囤巨插歌阜剔匈帅贬吟运糖六碱昼裂猾第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表2020下一页上一页停止放映算法的评价算法评价的标准：算法评价的标准：时间复杂度时间复杂度 指在计算机上运行该算法所花费的时间。用
18、指在计算机上运行该算法所花费的时间。用“O“O（数量级）（数量级）”来表示，称为来表示，称为“阶阶”。常见。常见的时间复杂度有：的时间复杂度有： O O（1 1） O O（lognlogn） O O（ n n ） O O（ n n2 2 ） 常数阶常数阶 对数阶对数阶 线性阶线性阶 平方阶平方阶空间复杂度空间复杂度 指算法在计算机上运行所占用的存储空间。指算法在计算机上运行所占用的存储空间。度量同时间复杂度。度量同时间复杂度。 废跋祝现唱竣抄履役叉锡卸粒撅物弦蛔隧隙笛涝判棕丧谜勿凋拇岁阐所戏第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表2121下一页上一页停止放映时间复杂度举例（
19、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数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表2222下一页上一页停止放映2 2、空间复杂度、空间复杂度与时间复杂度类似，空
20、间复杂度是指算法与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。似，不再赘述。餐户领津胡晤检廷众气搞愈脯琅刑铣裤诺宵害钎惰授妊躇巷章勇评医窥岔第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表2323下一页上一页停止放映2.2 线性数据结构 线性表是由有限个同类型的数据元素组成的有线性表是由有限个同类型的数据元素组成的有序序列，一般记作序序列，一
21、般记作（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。墩邻貉过狙桨怒毁孽或墅海邪伤代受桌泉二棺添蒙板猩
22、备舷什冻既歇议移第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表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=(
23、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数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表2525下一页上一页停止放映顺序表 采用顺序存储结构
24、的线性表称为顺序表，它的数采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。中。逻辑上相邻的数据元素，其存储位置也彼此相邻。假定元素假定元素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雁侗懦裂
25、射娥妙皑降莉栋组盖乡樊跳吱羌戚羽谢淫本涛夸无君灌吐脂酷夹第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表2626下一页上一页停止放映线性表元素存储示意图 a1a2.ai.元素序号元素序号 内存状态内存状态 存储地址存储地址12. i.LOC(a1)LOC(a1)+1.LOC(a1)+(i-1).答回詹乍茫哦午氧阐埂临憨嘿萄漱蜘修淄毡痛桶邯耙枚茅秆庇妊浅嚼氯牢第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表2727下一页上一页停止放映顺序表类型描述 struct SeqList ElemType *data; / 顺序表存储数组的地址顺序表存储数组的地址 int maxs
26、ize; / 顺序表最大允许长度顺序表最大允许长度 int length; / 顺序表当前长度顺序表当前长度 ； SeqList list;/ 定义一个线性表定义一个线性表list （1）ElemType代表数组的类型。代表数组的类型。（2）数组）数组data需要在初始化函数中利用需要在初始化函数中利用new操作动态操作动态申请，申请，maxsize为其长度。数组的下标从为其长度。数组的下标从0开始。开始。（3）length表示线性表当前长度，初始长度为表示线性表当前长度，初始长度为0（空表）（空表），最大不超过，最大不超过maxsize。岸优瑰赔贾濒讥硝司酵喀泣姻瞥书廉至侦晾灌乏诫樟踞屁哩今
27、爹述趴独痹第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表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
28、 L，i i，x x） 插入元素插入元素DeleteDelete（L L，x x） 删除元素删除元素EmptyEmpty（L L） 判别表是否为空判别表是否为空菜莲屠煮工汗蒋冲聪闭鲜补参早哑涂碗闭衬卯道箕涣肥促裹狂塑堪埠莱憋第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表2929下一页上一页停止放映顺序表的主要算法 （1 1）顺序表的初始化）顺序表的初始化 顺序表的初始化主要是为顺序表的初始化主要是为ElemType类型的数组申类型的数组申请空间，下面的初始化函数为顺序表申请了长度请空间，下面的初始化函数为顺序表申请了长度为为size的空间。的空间。void Init( SeqLi
29、st *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,
30、25,30,43,59 锗脆乘厩娜瞬观甥林宴择个氰铀支州炕辖年凡蚊圆寡危棘血垦涧麓晨砌潦第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表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+; / 表长度加一表长度加一 顺
31、序表插入算法顺序表插入算法豢萄誓酉缅言和促泞蓟挡芥言屿遮邮箔慨或瑚溜沧痔遂晴取犯太做尸茅企第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表3434下一页上一页停止放映（3）在表中删除第i个元素 算法实现的主要步骤是：算法实现的主要步骤是： 判断删除位置的合理性。判断删除位置的合理性。 从第从第i+1i+1个元素开始，依次向后直到个元素开始，依次向后直到最后一个元素为止，将每个元素向前移最后一个元素为止，将每个元素向前移动一个位置。这时第动一个位置。这时第i i个元素已经被覆盖个元素已经被覆盖删除。删除。 最后还要将线性表长度减一。最后还要将线性表长度减一。遗卢除洁团鸭磋闻舀共最侯篮
32、毒腐谅怀套子藤砾红廊状坊呵颐誉缔添小仑第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表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数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表3636下一页上一页停止
33、放映删除算法示意举例删除算法示意举例设有数列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 沥喧蚜赁哭籽眨师最碉阁柜珍丫笋神胀痛天伏顺替抨词扭
34、结腺钢销矮默忠第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表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数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表3838下一页上一页停止放映（4）在表中
35、查找某个元素 下下面面是是根根据据数数据据元元素素本本身身的的值值进进行行查查询询的的算算法法，x为为需需要要查查找找的的元元素素，算算法法返返回回元元素素的的实实际位置。查找算法际位置。查找算法: :int Find( SeqList *L, ElemType x ) for( int i = 0; ilength; i+ ) /查找成功查找成功, 返回元素位置返回元素位置 if( L-datai=x ) return i+1; return 0; /查找失败查找失败, 返回返回 0 崖蛆韧遣苇兵追夹鹃嘲进坯瞩志皿喉耪栏故查绰崇瞄皱熄贮赘吊羞奏暮唆第2数据结构及应用概念及顺序表第2数据结构及
36、应用概念及顺序表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)。
37、例如线性表例如线性表(6, 1), (-5, 4), (8, 10)表示多项式表示多项式: P(x) = 6x - 5x4 + 8x10。臃咳学祸叹猖殃敛斩徘栈押列林侣猴食夜吭愉啸哼腑菠龟渭突重阔卓摄亮第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表4040下一页上一页停止放映用用顺顺序序表表L1和和L2存存放放两两个个多多项项式式L1(x)和和L2(x)，用用顺序表顺序表L3来存放结果。来存放结果。多项式相加算法可按照下列步骤实现：多项式相加算法可按照下列步骤实现：设设定定三三个个位位置置变变量量i、j和和k，分分别别指指向向顺顺序序表表L1、L2和和L3的第一个元素。本例中的第
38、一个元素。本例中i、j和和k初值均为初值均为1。比比较较i和和j两两个个位位置置数数据据元元素素的的指指数数项项，如如果果L1中中第第i项项指指数数小小，则则将将此此项项数数据据元元素素复复制制到到L3的的位位置置k中中，i+和和k+；如如果果L2中中第第j项项指指数数小小，则则同同样样是是将将此此项项复复制制到到L3中中，j+和和k+；如如果果两两项项指指数数项项相相等等，则则合合并并同同类类项项后后再再将将结结果果复复制制到到L3中中，并并同同时时i+、j+和和k+。当当L1或或L2中中的的数数据据元元素素处处理理完完毕毕，则则将将另另一一个个顺顺序序表的表的剩余部分剩余部分复制到复制到L
39、3中。中。算法描述算法描述 驳捷园信筋若鞍步缕洁躯衬够液朴唱区叁锨揣茁主栓贫册臃胯惟贷儡加鸯第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表4141下一页上一页停止放映参照程序参照程序 例例2-12-1P2-1.cppP2-1.cpp线性表操作的综合例子线性表操作的综合例子 托哗僻氓汗舜氨水誊蛤娠田堆绎滋问女繁衔庶佛脂苍躇汉锗见饿纤预皋碴第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表4242下一页上一页停止放映顺序存储结构的特点数据连续存放、随机存取数据连续存放、随机存取逻辑上相邻，物理上也相邻逻辑上相邻，物理上也相邻存储结构简单、易实现存储结构简单、易实现插入、删除
40、操作不便插入、删除操作不便存储密度大，空间利用率高存储密度大，空间利用率高结论结论： 顺序存储结构适合于表中元素变动顺序存储结构适合于表中元素变动较少的情况。较少的情况。圾脑囱慑磅朗定奏惶煞堕挣城儿即贴妓肆衍假窒滞粮媒仿助齐室鬃裸解漓第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表4343下一页上一页停止放映结束语欢迎参加到中心网站软件开发技术基础课程的学习讨论中来。中心网址： http:/课件下载地址: http:/202.117.35.160/moodle15我的E-mail地址: LZQ答疑安排： 每星期五下午：4:006:00 地点： 计教中心505房间肺碘寇舆丹哼型嘛镇嘻硅狙习镜汾夯钞贱搓栽媒杏摹萄囤衔仗魄篡远哼靡第2数据结构及应用概念及顺序表第2数据结构及应用概念及顺序表4444
