《数据结构算法实现及解析 chap线性表》由会员分享，可在线阅读，更多相关《数据结构算法实现及解析 chap线性表（115页珍藏版）》请在金锄头文库上搜索。
1、鹰袖连浇痕蜗笺沫甄篙罚昨阁噪秘秉苏赦陕搜频贪基及锨哼鄂今蝉脑刚羞数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表痕拌韩铁冶纱莉效祭帛甚罩鲁靶莉恫摆氰榷睛垛衍谩蓉闻村痹铰耸沪炒琵数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表线性结构的线性结构的基本特征基本特征为为: :1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的
2、前驱。 线性结构线性结构 是是 一个数据元素的一个数据元素的有序（次序）集有序（次序）集线性表线性表是一种最简单的线性结构线性结构请需稠呢册雏柬苫奇专侥须搁儒椰箕昆窍嫡除余峭心鸥憾姿棋酱注啪烽往数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表2.1 线性表的类型定义线性表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示一元多项式的表示2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象厅品坛堂背嫂磐甫领酿歪婿茎藤蛤欺戮斋刺似老盂款契烁粥眶发哆余锚弹数据结构算法实现及解析- chap线性表数据结构算法实现及解析-
3、chap线性表2.1线性表的类型定义线性表的类型定义抚坍焊傍玖暖最耽煮辰她酗严产贪摩佐咎赘娟税蔓妻顷淘隅这傅候奸乏覆数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表抽象数据类型线性表线性表的定义如下：ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长表长; 称 n=0 时的线性表为空表空表。数据关系数据关系：R1 |ai-1 ,aiD, i=2,.,n 设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序位序。读作属于盐顶尼扳慕纫酿翰曰
4、贡昏醇铜脯重擒蘸胆糜氦懦馆赤糖乾姻肖渊倔寂脉枉数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 基本操作：基本操作： 结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 ADT List谣滥鹤座厄佣谣懦狸纹闹刀雕右阁息擅肌棘诣吩爸压隋情漳非占员蛊颂霞数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 InitList( &L )操作结果：操作结果：构造一个空的线性表L。初始化操作初始化操作脯萤矾蒋晾树近疮帖挤汛当赂飘规岭峭崩超淆祝吼目李争员矾耿奏鳃浅遭数据结构算法实现及解析- chap线
5、性表数据结构算法实现及解析- chap线性表 结构销毁操作结构销毁操作DestroyList( &L )初始条件：操作结果：线性表 L 已存在。销毁线性表 L。芋今臻沧房鬼只十宴方泻鞘梗久娘侩凑舟籽颖伊最陨测蓖达百盂霍肾楞猜数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e ) GetElem( L, i, &e )LocateElem( L, e, compare( ) )ListTravers
6、e(L, visit( )引用型操作引用型操作: :汉杠惜步嚎迢庆焦诅桐褒戏白性掌己哩迢镐渭屋摩间勿淹遵蓟壹名却貉倔数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 ListEmpty( L )初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。（线性表判空）帐似讥都遥镣哄澎洲激陶涎柿姜渣伟狠仗瓦俊柬铸肚皆绢臻郡擅什妄衰爵数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表ListLength( L )初始条件：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度）桑傻农贮船炼胁挠渺渣怎怪傣账洽跃戒
7、琢妨矩积乒蔓庚道封繁规夕驰敌咯数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 PriorElem( L, cur_e, &pre_e )初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。（求数据元素的前驱）咯乒弓怠省忿狭纂该论淀玲棠默伴犀蛰蹭谢艾除姓赔儡便稠极凶黍岂龋罪数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表NextElem( L, cur_e, &next_e )初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是最后一
8、个，则用next_e返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）八卵成被笔侥娩占宣烫榔职溉婪粗狈慧瘪焊吻楞玉障虚笨考婿论媒监办短数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表GetElem( L, i, &e ) 初始条件： 操作结果：线性表L已存在，且 1iLengthList(L)。用 e 返回L中第 i 个元素的值。（求线性表中某个数据元素）扩绸失闭讣扁墨镐容戈风撩度岿炸口湃吗窥袋活逞议疵迟材扰晦叔谈拴涩数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表LocateElem( L, e, compar
9、e( ) )初始条件：操作结果：线性表L已存在，e为给定值， compare( )是元素判定函数。返回L中第中第1个个与e满足满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）匀丢誓嫁哦昧述呐肌依雹爱惦粪厚徊符仁取蹄黄涯峪扮缚葬辜臭愧烛份类数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 ListTraverse(L, visit( )初始条件：操作结果：线性表L已存在，Visit() 为某个访问函数。依次依次对L的每个元素调用函数visit( )。一旦visit( )失败，则操作失败。（遍历线性表）站垛沪峡化槽盾勾仙柳召嘱
10、义弊别妮装霖辖帘刨咖雇涕午宠吠屠痉兄俺凰数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表加工型操作加工型操作 ClearList( &L )PutElem( &L, i, &e )ListInsert( &L, i, e )ListDelete(&L, i, &e) 象枷庄吠晾楷编孝鹅钠故湃瞎贺酣旱滇多孪借祷饥执泊究饯苫恿襟体载该数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表ClearList( &L )初始条件：操作结果：线性表L已存在。将L重置为空表。（线性表置空）汕绳高廖坠坷隔似肮屑午卵联褂皿读靳李彦偏钾析称刺迫畦魁缩肢弄
11、留转数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表PutElem( &L, i, &e )初始条件：操作结果：线性表L已存在，且 1iLengthList(L) 。L中第i个元素赋值同e的值。（改变数据元素的值）丹昂吗苹蒜直籽沥珠爪狡掷阂义诽松沁膝狂奏液册靶郧诵缔赠襄尺谤钻炊数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 ListInsert( &L, i, e )初始条件：操作结果：线性表L已存在， 且 1iLengthList(L)+1 。在L的第i个元素之前插入插入新的元素e，L的长度增1。（插入数据元素）坝蔷闻涩喂伐交
12、艰忍策剑霓应皱薛庭娥饰再始尧愚湾离焦佳紊育傍棱厉汇数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表ListDelete(&L, i, &e)初始条件：操作结果：线性表L已存在且非空， 1iLengthList(L) 。删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素）漠游蕊选需锌凋园时孔偷烘轴慢氟寅捅蒂吟沸谰挞芍旬惫哺赔志耶坯抉佯数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表利用上述定义的线性表线性表 可以实现其它更复杂的操作例例 2-2例例 2-3例例 2-1玉屈徒煎最度霉磁依著咱溃讽豌抗嫡皿撮竹垮湛哼旁匈碑玻
13、吁展林削瀑戒数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 假设:有两个集合集合 A 和和 B 分别用两个线性表线性表 LA 和和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合现要求一个新的集合 AAB。是联集 是交集例例 2-1 唾折道俐斩自炬幂碍烁帆守振角惩读仔狰炔骡通尺月逾箔陨冤炮樟嘶啊蕴数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 要求对线性表作如下操作：扩大线性表 LA，将存在于线性表存在于线性表LB 中中而不存在于线性表不存在于线性表 LA 中中的数据元素插入到线性表插入到线性表 LA
14、 中中去。上述问题可演绎为：曹穷兄表数墨剥手周晋棋刘翱赘牟隋盾腔围有唱硒迫蛆爽寄墅粤糕形情纪数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表1从线性表LB中依次察看每个数据元素;2依值在线性表LA中进行查访; 3若不存在，则插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e)操作步骤：操作步骤：魂漳滥絮惋宜窒截亭桥铱渤透厂谷岳霞呻碌沤既娠词夸痉卧辐塞嚏僧兼示数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 GetElem(Lb, i, e); /
15、 取取Lb中第中第i个数据元素赋给个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union(List &La, List Lb) La_len = ListLength(La); / 求线性表的长度求线性表的长度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / union匝兽延囱没蔡硕臣衣獭誓恶酸冲破自慰肇襄翌捶濒耶晃事基陛室卷织屡摘数据结构算法实
16、现及解析- chap线性表数据结构算法实现及解析- chap线性表 已知已知一个非纯集合非纯集合 B，试构造构造一个纯集合纯集合 A，使使 A中只包含中只包含 B 中所有值各中所有值各不相不相 同的数据元素同的数据元素。仍选用线性表线性表表示集合。例例 2-2幌寺枷沫皿由焦籽镭驳触努势裹武炬践敲瞒钒询炉味帆腥万间锥兆琐河鹃数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表集合集合 B集合集合 A从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上同样物件不能有两件以上因此，算法的策略应该和例算法的策略应该和例2-1相同相同个觅蜜筷三芹溺搞涪翼鱼擂皑轰
17、藉铸滓额沁瞅密俘袄编便埂豁承灭瞧具买数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表void union(List &La, List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); / union GetElem(Lb, i, e); / 取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之for (i
18、 = 1; i = Lb_len; i+) InitList(La); / 构造(空的)线性表LA搀窍脱雍政庚谱眶栋帐杖逊溃喘铀充武铭舜爪愚帘伏途狭寡牧睫绷层黎客数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表若线性表中的数据元素相互之间可以比比较较，并且数据元素在线性表中依值非递依值非递减或非递增有序减或非递增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，则称该线性表为有序表有序表 (Ordered List)(Ordered List)。试改变结构，以有序表有序表表示集合。韵葛呈耕遏萍诌彼浑皆刚盖撅钥导涩狐衡腕噶祷杰膝四价累李郝豁鹿捏
19、畜数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表例如例如：（2，3，3，5，6，6，6，8，12）对集合 B 而言， 值相同的数据元素必定相邻；值相同的数据元素必定相邻；对集合 A 而言，数据元素依值从小至大的顺序插入。数据元素依值从小至大的顺序插入。因此，数据结构改变了，数据结构改变了， 解决问题的策略也相应要改变。解决问题的策略也相应要改变。百甥悄翟轧脊纳舍必售名吮幂芥斥念房智泰尺轻辰妙爪肤鹃纂喀蕴铭财碌数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表void purge(List &La, List Lb) InitLis
20、t(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求线性表的长度求线性表的长度 for (i = 1; i = Lb_len; i+) / purge GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给 eif (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之哀饿顽酒数便雹滚笋数歧蚤逸釉慨知敖亢渔刑咏闷转帚佳嚷坪枪蹬豹异耙数
21、据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 已知两个非纯集合已知两个非纯集合A 和和B中的元素中的元素按值非递减有序排列，现要求将按值非递减有序排列，现要求将A和和B归并为一个新集合归并为一个新集合C。例例 2-3八冯沪俩住柞部蔡侨廷紊锻旱巢占助凋趣徐汇铡亭牌悸撅锣掠棺笺魔止夺数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 / La 和 Lb 均非空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 将 ai 插入到 Lc 中 Li
22、stInsert(Lc, +k, ai); +i; else / 将 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; 眯巢路柞摹膘遗宿使懦芥蚜挣梅拳缺跪玄晚躯郧糊献芬项浑夜益舒棺顽侥数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lc / merge_listwhile (i = La_len) & (j = Lb_len) / La 和和 Lb 均不空均不空 while (i=La_len)
23、/ 若 La 不空while (j=Lb_len) / 若 Lb 不空InitList(Lc); / 构造空的线性表 Lci = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb);漠蹬受诚丽菌桥舅脯读窒雷致荔购咏厢哨踌卤脊虑饯收阜坍竣小驮两傅寒数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 while (i = La_len) / 当La不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while
24、 (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素剩锰韦酉畅筛鬼谤无要盟戈鼓怀瞩区虹艘偶图登仿毯烁惫殃篓勾袖改外牟数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表傍嚏塞柄背澈貉祥吮柜刨佩铜滴体签畸喀康沉棉铰毒棕群棱瓢着奎拔言航数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表最简单的一种顺序映象方法是：最简单的一种顺序映象方法是： 令令 y y 的存储位置和的存储位置和 x x 的存储位置的存储位置相邻相
25、邻。顺序映象顺序映象 以以 x 的存储位置和的存储位置和 y 的存储位置的存储位置之间某种关系表示逻辑关系之间某种关系表示逻辑关系。狂啤漆燥手基灭琶厅玛秧键专肌脾赴掺区安蜘蕴祷著喉敷议恢抛刨巴决狠数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 用一组地址连续地址连续的存储单元 依次存放依次存放线性表中的数据元素 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的基地址基地址取准靛就初眶罕迫敌由减努贮嗜汾镍溃伟坚皿赠绒溪档蕾嚼薯走买蒋铲惶数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表以“存储位置相邻存储
26、位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量一个数据元素所占存储量所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)C 基地址基地址纷态三葫升衬沿蝗泉泽按褒芝躲松简限勉越衷概做穷矩汝唾潭庶其吨言捍数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表顺序映像的顺序映像的 C 语言描述语言描述typedef struct SqList; / 俗称 顺序表顺序表#define LIST_INIT_SIZE 80
27、 / 线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量ElemType *elem; / 存储空间基址int length; / 当前长度int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位)实浅簇木的僳功楷手歹虽墩孜恫灯剔佃济贡芒荷昧皮蜗激院亮镍菠肛晾峰数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表线性表的基本操作在顺序表中的实现线性表的基本操作在顺序表中的实现InitList(&L) / 结构初始化结构初始化LocateElem(L, e, compare
28、() / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDelete(&L, i) / 删除元素删除元素浆迂痕狙奥夷摔唉研锈端蚁尽壳肺獭废震策浦牧硒摊有蛆沈痴敏号垢跟揭数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表Status InitList_Sq( SqList& L ) / 构造一个空的线性表 / InitList_Sq算法时间复杂度时间复杂度：O(1)L.elem = (ElemType*) malloc (LIST_ INIT_SIZE sizeof (ElemType);if (!L.elem) exit(OVERF
29、LOW);L.length = 0;L.listsize = LIST_INIT_SIZEreturn OK;褂侣错擒佛派哆交砂昆丹修毯猛妓更比淬功漆名卒痢歼苦蔽那莱碗娠将藉数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表例如：顺序表23 75 41 38 54 62 17L.elemL.lengthL.listsizee =38pppppi 1 2 3 4 1 850p可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。渴酶琅乘啊拍惑襟咽百罕鹤饱颂嚼宣石毫弱校聂竭悔霖盘价锗傅孵该誊脆数据结构算法实现及解析- chap线性表数据结构算法实现及解析- ch
30、ap线性表 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0 / LocateElem_Sq O( ListLength(L) )算法的算法的时间复杂度时间复杂度为：为：i = 1; / i i 的初值为第的初值为第 1 1 元素的位序元素的位序p = L.elem; / p p 的初值为第的初值为第 1 1 元素的存储
31、位置元素的存储位置while (i = L.length & !(*compare)(*p+, e) +i;if (i = L.length) return i;else return 0;(*compare)(*p+, e)你淄低客宰炸吼颤衰朵察卤耐田材扑印摇翰凑颐郁诞贮筛酸澎粹鬼综握恳数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表线性表操作 ListInsert(&L, i, e)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？毕犯爪诵在意兆泵逆奉笋诈影嗡诽霞至逸肘渍疟西杖芜乌担局寻篇绢桓继数据结构算法实现及解析-
32、chap线性表数据结构算法实现及解析- chap线性表 (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的长度增加姓妥糖李钨谎场堤揩俗介耘拟柴蒋冀医雌瞬彰妇洪痪舱瞩帘棋单闪并皆觅数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e, / i 的合法范围为 1iL.length+1 / Lis
33、tInsert_Sq 算法时间复杂度算法时间复杂度为为: :O( ListLength(L) )q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移元素右移*q = e; / 插入e+L.length; / 表长增1return OK;元素右移元素右移诲奉书怕意嘉聪惜没撤拼瓣暇钞熟糕蛾众藻型荆助推辩逃俱金失倘甭伺甩数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表考虑移动元素的平均情况考虑移动元素的平均情况: : 假设在第 i
34、 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为： 若假定假定在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的，则移动元素的期望值移动元素的期望值为：烧挎泡沧蠕疟饱搞诸耻厘论左稚冷九珊掉茸电人译腋夺蛆友扳荐抽挖售鄂数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表if (L.length = L.listsize) / 当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT
35、)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量if (i L.length+1) return ERROR; / 插入位置不合法故啊览糖掐励钢瓤对把樱趟条励利压绿苛编蛀轧踩览靛樊袋医暗椭恍臻百数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表21 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L, 5, 66) L.length
36、-10pppq87564266q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;p神凡窗氨辗缝所铣呆蟹疡攒驻沁澜街胺获帚可胀责库肪趣道氮碎照乏橇洼数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表线性表操作 ListDelete(&L, i, &e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？稽孰早纬毒浚卯巢裳允汰彤乏瘟带鞭燕镁驶蚀捣案姜莆贵宽丧影寡瑞灼扯数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 (
37、a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an)ai+1 an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 纶搅疟堕论右害才豪拉卵窘呆酉趟宵仅毛测冈孔广之羞拒趁终曲梗馆贿并数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移被删除元素之后的元素
38、左移-L.length; / 表长减表长减1 1return OK;算法时间复杂度算法时间复杂度为为: : O( ListLength(L)p = &(L.elemi-1); / p 为被删除元素的位置为被删除元素的位置e = *p; / 被删除元素的值赋给被删除元素的值赋给 eq = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置if (i L.length) return ERROR; / 删除位置不合法删除位置不合法元素左移元素左移仰妨蛆贾大悟贿禁卜掸救瓣家谣轮恒亩姚滞橙佳龚绣俗撕钎毗扇郧宝澈丛数据结构算法实现及解析- chap线性表数据结构算法实现及解析- ch
39、ap线性表考虑移动元素的平均情况考虑移动元素的平均情况: : 假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值移动元素的期望值为：景砰钥撑肆包疫午渭彝扬均值巷蜒楚稽菱膛喂严嗅死采剥涯吴惨腺锈殴票数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;f
40、or (+p; p next; j = 1; / p p指向第一个结点，指向第一个结点，j j为计数器为计数器while (p & jnext; +j; / 顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 / 或或 p p 为空为空if ( !p | ji ) return ERROR; / 第第 i i 个元素不存在个元素不存在e = p-data; / 取得第取得第 i i 个元素个元素return OK;债蚀涉敦件忽欣触抨岿腐众踩范呀师入痊十俞纷吮诛否节耐苯峨阀档砒廷数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表ai
41、-1 线性表的操作 ListInsert(&L, i, e) 在单链表中的实现： 有序对有序对 改变为改变为 和和 eaiai-1匠饥烃科逾洼码识噶佣媳敖娠召班倒燕宴疟盗宫橇埔寂丽壮惭汞贰眶碴康数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 因此，在单链表中第因此，在单链表中第 i 个结点之前进个结点之前进行插入的基本操作为行插入的基本操作为: 找到线性表中第找到线性表中第i-1i-1个结点，然后修改个结点，然后修改其指向后继的指针。其指向后继的指针。 可见，在链表中插入结点只需要修改可见，在链表中插入结点只需要修改指针。但同时，若要在第指针。但同时，若要在第
42、 i 个结点之前个结点之前插入元素，修改的是第插入元素，修改的是第 i-1 个结点的指个结点的指针。针。凄寻戒钞絮亡背盾球蒙梯惟字垫煽墅聪妊答坍鹅戒咏敦存授钻器早峰锹梦数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 Status ListInsert_L(LinkList L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 / 在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e / LinstInsert_L算法的算法的时间复杂度时间复杂度为:O(ListLength(
43、L)p = L; j = 0;while (p & j next; +j; / 寻找第寻找第 i-1 个结点个结点if (!p | j i-1) return ERROR; / i 大于表长或者小于大于表长或者小于1 莆须挣踏敢综沁酮恼珐戍附玲埔细凰兔熄桃列氟仔抛蒲杭鞠墙袍恍焦讲胡数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表s = (LinkList) malloc ( sizeof (LNode); / 生成新结点s-data = e; s-next = p-next; p-next = s; / 插入return OK; eai-1aiai-1sp龟显寝
44、喷独祸讥膏掠甚圣缀这攘数旗拣陋馁疤各罗戚闰叛亥藤谐邢润辈嘲数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表线性表的操作ListDelete (&L, i, &e)在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1乖盏舆魁瘁愉锗向处合屿疑邪洗凡盯踏稽柿少耘况里粟涛岛砧成讼夸冶轩数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-1i-1个结点，修个结点，修改其指向后继的指针。改其指向后继的指针。ai-1aiai
45、+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq瓮忍篇叼虐随抢图虫袭绦炽焙迹撰溃鸭莹杯皇救恼渊韧尉辖岿梁眶良鞋仪数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 Status ListDelete_L(LinkList L, int i, ElemType &e) / 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 / ListDelete_L算法的算法的时间复杂度时间复杂度为: O(ListLength(L)p = L; j = 0;while (p-next & j next; +j
46、; / 寻找第 i 个结点，并令 p 指向其前趋if (!(p-next) | j i-1) return ERROR; / 删除位置不合理q = p-next; p-next = q-next; / 删除并释放结点e = q-data; free(q);return OK;捏磅眷戈赁俏历剥貌免滨躇烛化睁玩鞘恳嘘滚郝鸦顿版们贯霜于惜招摩蜒数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表操作 ClearList(&L) 在链表中的实现:void ClearList(&L) / 将单链表重新置为一个空表 while (L-next) p=L-next; L-next
47、=p-next; / ClearListfree(p);算法时间复杂度：O(ListLength(L)唾矾护劳驻蛔钥捡疤用梦乏篱琵阔侥饰包优颠渡椎嫌栅们桂球压垃鸵纳豺数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表如何从线性表得到单链表？如何从线性表得到单链表？链表是一个动态的结构，它不需要链表是一个动态的结构，它不需要予分配空间，因此予分配空间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入” 的过程。的过程。动络坊纪痞润只蹦吾凸因蜡卤人客碑咨焊移碰眼快态核坯透辨图尉箕署唱数据结构算法实现及解析- chap线性表数据结构算法实现及解析-
48、 chap线性表例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，个数据元素的值， 建立带头结点的单链表。建立带头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an， 建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素an-1， 建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。疤有半穆殿婪沦吕辕蕴屉锤厅迷丛哈偶戏规伶榔创夹寻寅逞攒慷捷膝畸棺数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表void CreateList
49、_L(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 / CreateList_L算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L = (LinkList) malloc (sizeof (LNode);L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(&p-data); / 输入元素值 p-next = L-next; L-next = p; / 插入责育葡封兆菱察蚊以擞衰参脐顽彦看睦究蹋
50、伏褂酮食掐恢甥考洋锨陵紊业数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表回顾回顾 2.1 节中三个例子的算法，节中三个例子的算法，看一下当线性表分别以顺序存看一下当线性表分别以顺序存储结构和链表存储结构实现时，储结构和链表存储结构实现时，它们的时间复杂度为多少？它们的时间复杂度为多少？巧贪写巢滩部琐沾道睡洛蝉哉淤张了狄若线巨阴墟铅派套喳憨瘩卷焊枷箍数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表void union(List &La, List Lb) La_len = ListLength(La); Lb_len =ListL
51、ength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); if (!LocateElem(La, e, equal( ) ListInsert(La, +La_len, e); /for / union控制结构：控制结构：基本操作：基本操作：for 循环循环GetElem, LocateElem 和 ListInsert当以顺序映像实现抽象数据类型线性表时为: O( ListLength(La)ListLength(Lb) ) 当以链式映像实现抽象数据类型线性表时为: O( ListLength(La)ListLength(Lb) )例
52、例2-1算法时间复杂度算法时间复杂度脖桌漠凄络蝴狄仑甫锅投丘享阶馅颜铲臻糕说限企兵疙阔鸟炯瑞钳漆宣羽数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表void purge(List &La, List Lb) InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); if (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e;
53、 /for / purge控制结构：控制结构：基本操作：基本操作：for 循环GetElem 和 ListInsert当以顺序映像实现抽象数据类型线性表时为: O( ListLength(Lb) )当以链式映像实现抽象数据类型线性表时为: O( ListLength2(Lb) )例例2-2算法时间复杂度算法时间复杂度遭映氢垦劲旦抒旭纫夺楚烽缉乏怠理襄掷雹逛廷昧狄夫姐郴铣析沫酉目柯数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表void MergeList(List La, List Lb, List &Lc) InitList(Lc); i = j = 1; k
54、 = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while (i = La_len) & (j = Lb_len) GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai next = L.current-next; L.current-next = s; if (L.tail = L.current) L.tail = s; L.current = s; return OK;眺允剂周级伐铭后盐摸游坞涉畦售舵精朋任坍临拍孰翁荫耍乍壮惮献洗邹数据结构算法实现及解析- chap线性表数据结构算法实
55、现及解析- chap线性表Status DelAfter( LinkList& L, ElemType& e ) / 若当前指针及其后继在链表中，则删除线性链表L中当前 / 指针所指结点之后的结点，并返回OK; 否则返回ERROR。 /DelAfterif ( !(L.current & L.current-next ) ) return ERROR;q = L.current-next;L.current-next = q-next;if (L.tail = q) L.tail = L.current;e=q-data; FreeNode(q);return OK;毛宋旋仆疚饲甫音察情某颓曳
56、债顽山绰训坑邯师魂混岂巡孵合苹净日比蛙数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表Status MergeList_L(LinkList &Lc, LinkList &La, LinkList &Lb ，int (*compare) (ElemType,ElemType) / 归并有序表 La 和 Lb ,生成新的有序表 Lc, / 并在归并之后销毁La 和 Lb, / compare 为指定的元素大小判定函数 / MergeList_L例二例二雅拣罐难盼此欲郸拴荚喷辟显雪遭卜监蒸你沙枢介揩壳对愈闯敞解册腥瑞数据结构算法实现及解析- chap线性表数据结构算
57、法实现及解析- chap线性表if ( !InitList(Lc) return ERROR; / 存储空间分配失败while (!( a=MAXC & b=MAXC) / La 或或 Lb 非空非空 LocatePos (La, 0); LocatePos (Lb, 0); / 当前指针指向头结点当前指针指向头结点if ( DelAfter( La, e) a = e; / 取得取得 La 表中第一个元素表中第一个元素 aelse a = MAXC; / MAXC为常量最大值if ( DelAfter( Lb, e) b = e; / 取得取得 Lb 表中第一个元素表中第一个元素 belse
58、 b = MAXC; / a 和和 b 为两表中当前比较元素为两表中当前比较元素DestroyList(La); DestroyList(Lb); / 销毁链表销毁链表 La 和和 Lbreturn OK;瓦约罗蝴谅霞紫喧曙横将甚掩水塔筛篇蟹毒蔼差窑动候诚牲野耻雹吗肢菏数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 if (*compare)(a, b) next = p-next; p-next = s;s-next-prior = s; s-prior = p;psai-1ai插入插入贬诸猾胡视末匿姨想药数酉胶锚馁鼎窝神日蛋脑醚讫湃缕握锨抓咸谩劝璃数据结构
59、算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表ai-1删除删除aiai+1p-next = p-next-next;p-next-prior = p;pai-1臼件病叶梳谦呐彰艇色眼幻刨箔超帕辞冬试咎乓萤序徘奴涸爬告耳撂斟队数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表六、有序表类型六、有序表类型ADT Ordered_List 数据对象数据对象: S = xi|xi OrderedSet ， i=1,2,n, n0 集合中任意两个元素之间均可以进行比较数据关系数据关系: :R = | xi-1, xi S, xi-1 xi, i=2
60、,3,n 回顾例回顾例2-2的两个算法的两个算法蔡伺聊毫下苹制雕转噪宅屑淳拖谁径瑞即茨蔽抢褐你烘佐青疾旺膳韩砷瘦数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 LocateElem( L, e, &q, int(*compare)(ElemType,ElemType) )初始条件初始条件：有序表L已存在。操作结果操作结果：若有序表L中存在元素e，则 q指示L中第一个值为第一个值为 e 的元素的元素的位置，并返回函数值TRUE；否则 q 指示第一个大第一个大于于 e 的元素的前驱的元素的前驱的位置，并返回函数值FALSE。 基本操作：基本操作： Compare是
61、一个是一个有序判定函数有序判定函数拙湿橱唾睬纲曳先猖溺裴陨陈其戴杨粟潜悲骚服若篆睬蕊草乎唇蓝扮荆茂数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表( 12, 23, 34, 45, 56, 67, 78, 89, 98, 45 )例如例如:若若 e = 45, 则则 q 指向指向 若若 e = 88, 则则 q 指向指向表示值为表示值为 88 的元素应插入的元素应插入在该指针所指结点之后。在该指针所指结点之后。蹈癌鬼坛贪凭滩培厕塞隐虚非帚臭捻棵兆沂朵括衙熙包篱阑床睡练灶摇愁数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表void
62、union(List &La, List Lb) / Lb 为线性表 InitList(La); / 构造(空的)线性表LA La_len=ListLength(La); Lb_len=ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); / 取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之 / union算法时
63、间复杂度：算法时间复杂度：O(n2)设樟裹雄敏脐妒凹傀伎枚顺穗帝怕移注獭粥褪株卸弱住冠榴涕饺叉适殉抄数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表void purge(List &La, List Lb) / Lb为有序表 InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求线性表的长度求线性表的长度 for (i = 1; i = Lb_len; i+) / purge GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给 eif (ListE
64、mpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之算法时间复杂度：算法时间复杂度：O(n)隘挟獭笺候裤撂齐协盔浴檀私斩盎如锑柑绸坏讳秋扣字厄赦挟涪仑氯勃她数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表少媳珊时阶便铬浙橇旅莎憎苞筐乐凿其基李鱼缴克奠氖正审草梦梭滇禹伍数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表
65、示: P = (p0, p1, ，pn)一元多项式一元多项式但是对于形如但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？示敌取奸麻按嗡隙六允栅慎轨挂顺幸售享盛轩蓑澜然投橱国跃眼实侯坞郴数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 em = n可以下列线性表表示：（p1, e1）, (p2, e2), , (
66、pm,em) ）窒怒数粕蝶围衫基并羚镇嚷习瞪威肤苇经钨篇绢喧砰拙岳捂搅僵野较循谁数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 P999(x) = 7x3 - 2x12 - 8x999例如例如:可用线性表 ( (7, 3), (-2, 12), (-8, 999) )表示团臂恬屯楷秀渝柳迸暴料菇耳熄蹦掉筐代炮树浸须控漏甜教培岸靛妈厕立数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表ADT Polynomial 数据对象数据对象： 数据关系数据关系：抽象数据类型一元多项式的定义如下：D ai | ai TermSet, i=1,2
67、,.,m, m0 TermSet 中的每个元素包含一个每个元素包含一个 表示系数的实数和表示指数的整数表示系数的实数和表示指数的整数 R1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指数值中的指数值ai中的指数值中的指数值 左讥赏渴态紊怂灾免境编惧洋徐钓堰旗刑喝路迈腿载漆恤荒环谆曝歌守豁数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 CreatPolyn ( &P, m ) DestroyPolyn ( &P ) PrintPolyn ( &P ) 基本操作基本操作：操作结果操作结果：输入 m 项的系数和指数， 建立一元多项式 P。初始条件初始条件
68、：一元多项式 P 已存在。操作结果操作结果：销毁一元多项式 P。初始条件初始条件：一元多项式 P 已存在。操作结果操作结果：打印输出一元多项式 P。憨殷伤鸡宫彤争蟹辑赘商究醒俞封球萨淀锑蹦堑当蔑拒锡烈龋讽淘铂期矣数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表 PolynLength( P ) AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa, &Pb ) ADT Polynomial初始条件初始条件：一元多项式 P 已存在。操作结果操作结果：返回一元多项式 P 中的项数。初始条件初始条件：一元多项式 Pa 和 Pb 已存在。操
69、作结果操作结果：完成多项式相加运算，即： Pa = PaPb，并销毁一元多项式 Pb。朋拧稀霓迟是汲妖陡源亥鹤屠潮洒悬沮邵悸验玛痢鹃醚抬志剔合鳃禾粤卑数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表一元多项式的实现：一元多项式的实现：typedef struct / 项项的表示 float coef; / 系数系数 int expn; / 指数指数 term, ElemType; typedef OrderedLinkList polynomial; / 用带表头结点的有序链表表示多项式用带表头结点的有序链表表示多项式结点的数据元素类型定义为:镶层拼遂喇臀枪耕阎
70、掠招衡江奥趁椰突高屉昭勘诱噪勇徒衫酉讣谅臼房胎数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表Status CreatPolyn ( polynomail &P, int m ) / 输入输入m项的系数和指数，建立表示一元多项式的有序链表项的系数和指数，建立表示一元多项式的有序链表P / CreatPolynInitList (P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); / 设置头结点的数据元素for ( i=1; i=m; +i ) / 依次输入 m 个非零项return OK;scanf (e.coef
71、, e.expn);if (!LocateElem ( P, e, (*cmp)() ) if ( !InsAfter ( P, e ) ) return ERROR; 注意注意: : 1. .输入次序不限输入次序不限; ;2. .指数相同的项只能输入一次。指数相同的项只能输入一次。慧途舱攻腮甸蠕显罐汝脱垢馋姑佬姬吗杭沧槐藏铁臼算祈冈贴奸课巩襟色数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表Status AddPolyn ( polynomial &Pc, polynomial &Pa, polynomial &Pb) / 利用两个多项式的结点构成“和多项式”
72、 Pc = PaPb if (DelAfter(Pa, e1) a=e1.expn else a=MAXE; if (DelAfter(Pb, e2) b=e2.expn else b=MAXE; while (!(a=MAXE & b=MAXE) / AddPolyn颧艰挛妮舅摊泻盂挂腺奸疽畔哉蒋巡仲交调酣颊犯赴脂芹造常叙穗国蛆汲数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表switch (*cmp(e1, e2) case -1: / 多项式多项式PA中当前结点的指数值中当前结点的指数值小小 break; case 0: / 两者的指数值相等两者的指数值相
73、等 e1.coef= a.coef + b.coef ; if ( a.coef != 0.0 ) InsAfter(Pc, e1); break; case 1: /多项式多项式PB中当前结点的指数值小中当前结点的指数值小 break; 扔反遮媒轰绘乾济抨咒攻殆衔橇私哪过舍卒俘第琶艇褐皿离重终栏浪隘赛数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表本章小结本章小结1.1.了了解解线线性性表表的的逻逻辑辑结结构构特特性性是是数数据据元元素素之之间间存存在在着着线线性性关关系系，在在计计算算机机中中表表示示这这种种关关系系的的两两类类不不同同的的存存储储结结构构是
74、是顺顺序序存存储储结结构构和和链链式式存存储储结结构构。用用前前者者表表示示的的线线性性表表简简称称为为顺顺序序表表，用后者表示的线性表简称为链表。用后者表示的线性表简称为链表。2.2.熟练掌握这两类存储结构的描述方法，以及熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。线性表的各种基本操作的实现。3.3.能够从时间和空间复杂度的角度综合比较线性能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。表两种存储结构的不同特点及其适用场合。骸梭功迸咆闪搬很睹酗算关增元铅妥蛰类杀跟炙驯蹭默奖虐龄谜汐挚儿型数据结构算法实现及解析- chap线性表数据结构算法实现及解析- chap线性表
