第二章 线性表学时

第2章线性表马伟锋(Wei-fengMA)信息与电子工程学院SchoolofInformationandElectronicEngineering

2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4线性表的应用举例目标：掌握线性表的特性和实现方法，并能够利用线性表解决简单的应用问题。教学安排2.1线性表的逻辑结构

线性表的定义

线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,...,ai-1,ai,ai+1,...,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。La=（34，89，765，12，90，-34，22）数据元素类型为int。Ls=(Hello,World,China,Welcome)数据元素类型为string。Lb=(book1,book2,...,book100)数据元素类型为下列所示的结构类型：

structbookinfo{intNo;//图书编号char*name;//图书名称char*auther;//作者名称...;}线性表举例

ADTList{

数据对象：D={ai|ai∈Elemset，i=1,2,3…}

数据关系：R=(<ai-1,ai>|ai-1,ai

∈D,i=2,3…}

基本操作：InitList(&L)

操作结果：构造空的线性表L。DestroyList(&L)

初始条件：线性表L已经存在

操作结果：销毁线性表L…………}ADTLsit线性表抽象数据类型描述ListLength(L)

初始条件：线性表L已存在。

操作结果：返回L中元素个数。GetElem(L,i,&e)

初始条件：线性表L已存在，1≤i≤LengthList(L)。

操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())

初始条件：线性表L已存在,compare()是元素判定函数。

操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。ListInsert(&L,i,e)

初始条件：线性表L已存在，1≤i≤LengthList(L)+1。

操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)

初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。

操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。线性表的其他部分操作2.2线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示：图2-1线性表顺序存储结构示意图存储地址

内存单元

...

d

a1

d+L

a2

d+2L

a3

...

d+(i-1)L

ai

...

d+(n-1)L

an

...

...

其中，L为每个数据元素所占据的存储单元数目。相邻两个数据元素的存储位置计算公式LOC(ai+1)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai)=LOC(a1)+(i-1)*L顺序存储结构的特点（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；（2尸）在形访问录线性滴表时挥，可译以利掌用上卸述给编出的斯数学漠公式廊，快祸速地君计算矮出任盼何一以个数季据元固素的石存储卡地址遣。因释此，糖我们苍可以锄粗略锣地认道为，打访问台每个疮数据瓶元素皇所花焦费的季时间席相等松。这问种存要取元移素的岔方法访被称楼为随辽机存搬取法着，使峰用这乎种存荡取方扔法的弊存储讨结构趣被称镜为随机花存储型结构。在C矮语言蒜中，阁实现澡线性洽表的般顺序冰存储功结构刚的类抛型定府义：#d稻ef能in色e否L稀IS紫T_园IN滚IT干_S泪IZ呼E狗10般0价//忠线性管表的真最大性长度#d阶ef肢in筹e挂L荣IS傻TI晶NC切RE点ME闹NT灾1滨0沫/慢/每德次扩抹展长巴度ty圈pe光de煮f葵s遮tr铸uc是t{甚El倚em窜Ty追pe鸽*纳e月le恭m;免/唐/馋El蛙em桐Ty碧pe靠d搜at滋a[炒MA劫XS科IZ似E]挨;in域t夺l输en羡gt巧h;in浪t破li锐st境si慰ze始;}茫Se拖qL颂is谜t;2.源2.炕2棋典享型操政作的自算法傲实现1.碰初累始化卫线性腿表LSt鹅at瘦usIn旦it离Li韵st(免Sq浊Li跪st剖&L救)花/刷/宫算法耽2.洪3{删//六操苗作结环果：哥构造筹一个冷空的巴顺序丢线性充表L.el劲em=行(E恳le轻mT叹yp抬e*赛)m坊al童lo尽c(朝LI猪ST暗_I融NI核T_筛SI傍ZE序*s端iz供eo乳f(恼El分em棚Ty慕pe送))编;if凝(!妻L.鸭el扣em狼)ex械it健(O情VE腊RF遇LO绿W)想;马/预/贺存储溪分配抓失败L.le喂ng昌th=现0;积/量/示空表夕长度痒为0L.li辽st夸si征ze=蒸LI置ST横_I菌NI留T_鬼SI全ZE凳;附//骨初晌始存斤储容偶量re棵tu余rn昆O鸣K;}2.姐线性躁表L摊中数盖据元宫素X窜插入券第i孟个位谨置a1a2…aiAi河+1…an…01…i-射1n-盗1i…a1a2…aiAi陷+1…an…xxLI湖ST听_I掉NI裤T_绕SI棋ZE强-拖1…nLI惰ST铅_I电NI朋T_邪SI攻ZE浙-盏1插入房诚算法壮的分菌析假设羊线性啊表中奖含有即n个汇数据浴元素参，在稳进行运插入树操作姐时，胳若假班定在离n+衔1个巡寿位置拔上插内入元雅素的拆可能故性均糖等，违则平宝均移建动元南素的湾个数药为：3.天线押性表逗L中受数据宰元素厦X插符入第音i个剥位置a1a2…aia刮i+拍1…an…01…i-腹1n-群1i…a1a2…a建i+旷1…an…La贸staiLa浑st…nLI眼ST页_I爆NI侄T_富SI庸ZE夫-岛1LI泛ST镰_I药NI税T_竿SI弟ZE娘-颈1删除娃算法喘的分免析在进迫行删刻除操沿作时蔑，若脱假定跃删除汇每个减元素牙的可说能性腐均等寨，则哈平均浅移动泼元素呼的个课数为禽：结论：顺碧序存煌储结独构表咸示的奥线性捡表，咳在做揉插入颠或删左除操露作时协，平碌均需哥要移均动大聚约一男半的富数据禽元素何。当非线性烦表的估数据材元素辅量较首大，昏并且烧经常罩要对澡其做训插入断或删当除操搂作时犁，这酷一点占需要扰值得明考虑家。in故tLo血ca建te究El河em(S召qL扎is唐t崇L,亦El静em境Ty悦pe努e趟,S猫ta宰tu面s(斜*c详om夫pa仅re株)(届El著em杨Ty朴pe集,E唱le仰mT巷yp柜e)匹){签//文初材始条轻件：糠顺序念线性踏表L纳已存肝在，再co晶mp肚ar妻e(回)是该数据落元素及判定驰函数谦(满鸽足为奥1,跪否则担为0冲)//认操那作结款果：预返回刷L中颈第1萌个与南e满开足关恶系c描om畏pa脸re厕()朱的数使据元卡素的角位序锋。//唉若性这样纲的数着据元各素不次存在善，则真返回尘值为准0。郑算法惧2.叉6El晃em接Ty扭pe丙*俗p;in狼t部i=锹1;小/蛋/裹i的候初值悟为第师1个轻元素贡的位走序p=扫L.和el具em娘;域//耐p划的初蛾值为刘第1束个元搅素的策存储药位置wh烧il毯e(单i<白=L版.l臣en舰gt晶h&伙&!撕co旅mp妄ar妹e(求*p室++栗,e晚))++邀i;if泪(i奖<=舍L.迅le葡ng车th梦)re胡tu肤rn执i烦;el啦sere鼻tu烘rn喉0起;}4.碎在候线性糖表L蓬中检冲索值命为X僚的数竞据元永素2.俗3泽线报性表宜的链傲式存姐储结凳构线性眠表顺亮序存橡储结妥构的迈特点芝:它是披一种倚简单尊、方撤便的土存储腥方式窜。它倦要求决线性显表的淡数据销元素烛依次妻存放丙在连果续的绝存储悔单元目中，复从而降利用艰数据隙元素裳的存润储顺择序表滑示相廉应的凭逻辑扯顺序毙，这纹种存肢储方坐式属条于静满态存老储形押式。暴露务的问互题:(1济)猛在做错插入呢或删粱除元诱素的模操作抄时，器会产珍生大涛量的临数据姿元素林移动乔；(2脏)纯对于宪长度扬变化毙较大唉的线崇性表摆，要晶一次丑性地叫分配例足够澡的存君储空恒间，但这绞些空选间常窗常又围得不僻到充夸分的掘利用推；(3稳)笑线性叙表的粗容量优难以循扩充戏。线性蛙表的牲链式已存储陈结构场是指用踩一组救任意壳的存斤储单闭元（峰可以闸连续肥，也楚可以咱不连培续）激存储率线性旷表中沿的数腊据元帅素。为了必反映券数据头元素先之间艇的逻项辑关砍系，围对于橡每个植数据兔元素喉不仅窃要表笔示它思的具菊体内筒容，衣还要附加忧表示下它的菊直接隐后继恭元素虎存储领位置班等信茧息。链表材:单向、双或向和然循环闲链表抽。假设测有一疑个线祥性表旷（a稍,b男,c胀,d提），嚷可用贵下图朱2-俊2所吐示的侄形式欧存储蠢：线性划表的霜链式悼存储谷结构图2星-2税线性搭表链创式存伴储结熄构示跃意图相关闲术语表示占每个浙数据忌元素斩的两照部分氏信息仅组合赏在一摔起被西称为结点；其中咳表示规数据销元素揪内容容的部销分被扇称为数据刑域（d谎at撞a）判；表示丧直接躬后继易元素断存储胖地址临的部别分被读称为指针或指针删域（n鄙ex肝t）很。单链拿表简粥化的词图2难-3麦描述底形式he说add^cba图捆2-诸3暑单须链表倡结构兔示意济图

数据域

指针其中犯，h帅ea舟d是房诚头指食针，唉它指颠向单暑链表汪中的却第一均个结并点，教这是书单链皆表操究作的蹄入口尘点。宁由于菊最后糠一个背结点蛮没有预直接域后继仍结点诵，所座以，移它的疮指针俊域放山入一胶个特露殊的票值N姓UL南L。餐NU匹LL柏值在威图示修中常泛用（柱^）蛾符号岁表示跪。带头僵结点揉的单芦链表为了虹简化谅对链匙表的杂操作呢，人评们经蓄常在睛链表绳的第诵一个邮结点讯之前卡附加家一个桨结点西，并竭称为头结障点。这议样可厨以免呀去对给链表妥第一抬个结完点的屯特殊烟处理宜。如震下图丹2-链4所抛示：he银add两^cba图窄2-征4抽带头及结点惭的单舱链表鲜结构泰示意锄图不带绍头结礼点与篇带头氧结点畜链表吉分析d^

headcbaheadd^

cba访问耀a节戚点，归he伯ad祝访即问c瘦节点哗，b休-冰>n早ex仔t访问炼a节型点，泊he筹ad肯-鸟>御ne掠xt梯访问餐c节兔点，铸b逃->炒ne蒸xt链式僚存储牵结构不的特引点（1出）线册性表处中的贡数据袜元素飞在存嫌储单赞元中叶的存遗放顺搜序与所逻辑搁顺序溪不一曲定一血致；（2叮）在归对线墙性表惯操作忘时，亦只能羡通过脆头指出针进镰入链冰表，州并通建过每亡个结这点的史指针中域向京后扫纳描其欣余结森点，停这样每就会叮造成汪寻找劝第一陆个结窗点和誓寻找夹最后观一个粱结点鲜所花兰费的骄时间宿不等头，具驴有这觉种特决点的智存取俩方式曲被称善为顺冠序存阿取方煌式。在C我语言朵中，狂实现队线性鲁表的律链式存储殊结构啦的类路型定染义ty场pe易de偶f询st恒ru雕ct呼L伯No迎de{姥El思em异Ty矛pe咐da题ta角;st由ru岁ct再L骂No啦de扩*监ne决xt币;}嘉LN蒙od现e,迁*铜Li冷nk舞Li皮st颜；定义押头指领针变质量：Li目nk影Li仿st窑L；刷//滑链表零L动态维分配像与释微放空览间：L＝闷(L之in饰kL法is爪t)破ma龟ll细oc找(正si貌ze宝of赠(L孕No虹de轿)教)照;Fr元ee点（L辱）;2.宅3.姨2度典型冠操作丘的算础法实稼现插入迫操作he闸adabcxspd^2134第i舰个节销点//翁//2.红3.辽3升典型扎操作烦的算阶法实纺现删除断操作he父adabcpd^21第i伙个节饰点//庸//其他钱操作in脸t涨Li宽st墨Le姿ng轰th敬(L叹in米kL打is忠t梨L)St饱at领us今G裁et运El谷em墨(L怜in化kL拘is景t听L,锄i仅nt粮i凶,女El罪em棚Ty调pe强&驱e)单链晃表特祝殊操另作—有序本表合辽并，p3岭1Vo向id谱M信er越ge词li想st巡寿_l绪(L足in律kL回is罩t菜&L钥a,涨L添in膜kL萌is悉t侦&L攀b,Li浊nk郊Li台st辜&备Lc杰)2.病3.庸3齿静态级链表#d歼ef确in并e乳MA导XS应IZ计E恒10引00ty厉pe区de昌f岸s殊tr涂uc为t{El磁em治Ty歌pe雄d些at姥a;in希t草c约ur省;}c雀om功po栏ne枪nt伙,搜S舟Li纺nk乒Li播st醒[M使AX暂SI吓ZE戏];P3验2,升图延2.逮10失所示若将哑链表垒中最波后一患个结武点的致ne域xt争域指晓向头甘结点实现其循环谦链表价的类河型定病义与敬单链寒表完昏全相拐同，顽它的以所有杠操作睁也都灿与单命链表真类似矛。只状是判赢断链献表结折束的躲条件沃有所司不同异。下岭面我厨们就简列举通两个磨循环密链表徒合并万的操子作示软例，P3泥5，胁图2鲁.1捷3。head图华带烦头结鞭点的屯循环诞链表套示意康图2.走3.慎3鸽循环不链表2.肾3.菠4途双否向循让环链羞表在循语环链振表中拌，访释问结怠点的特点:访问兰后继蜻结点循，只超需要费向后绝走一占步，躁而访午问前轻驱结刷点，妄就需捏要转模一圈庭。结论：循贺环链圣表并区不适辣用于时经常慕访问鼓前驱辆结点葡的情挂况。解决床方法：在闯需要你频繁稀地同钱时访祝问前北驱和辣后继啊结点横的时岔候，聪使用泻双向聪链表党。所您谓双向菠链表。双向娇链表议就是沸每个终结点坛有两童个指鸣针域看。一咬个指易向后恩继结箭点，嗽另一姻个指淋向前疗驱结弓点。图撞循环速双向母链表headpriordatanext(a库)(b拳)类型切定义缴——ty餐pe鸦de尝f困st呼ru办ct颈dl骨no冲de{框E他le拒mt叫yp河e势da沟ta臣;st推ru生ct擦d滑ln方od胳e恢*p夸ri狼or交,店*僻ne遵xt真;}证DL旅in窄kL传is铸t;用C饺语言诉实现姨双向赶循环围链表图铺2-常9ps在一齐个结虏点前得插入巾一个率新结轧点s-卖>p被ri事or琴=p似->匀pr凑io碍r;p-欧>p好ri促or劳->运ne葵xt拖=s台;s-辞>n骄ex芽t=气p;p-犁>p胸ri禽or泳=s返;使用愚下列灾核心案语句祸：双向老链表裂中结庸点的炮删除②P①p-纷>p逮ri睁or痛->践ne广xt晚=p痰->寇ne侵xt箩;p-齿>n恭ex胀t-裹>p甩ri悲or疏=p维->喷pr厘io乘r;fr街ee文(p袋);使用即下列码核心暑语句荒：2.其4木一元裂多项同式的数表示处和相恒加S(龙X)交=找7僻+嫂1诉2X3-雄2X8+敏5毅X12P4伪1，今图2答.1秩7两服个多亡项式辰相加2.搞4汉顺序胡表和昌链表物的比雨较基于空间基于时间基于语言顺序表静态存储密度大利于查询都支持链表动态存储密度小利于删除、插入都支持小结冰：线性尤表逻毅辑结嘱构线性鞠表