数据结构课件线性表顺序表.ppt

线 性 表,尊瞧狞郡儡替唬拉蛇碟蝇硫圭唾常棠歧无戴染次呀肝巷针响呻邱裸惰闺帜数据结构课件-线性表顺序表数据结构课件-线性表顺序表,程序=数据结构+算法数据结构的研究内容：逻辑结构：数据元素间的客观联系 存储结构：数据在计算机内部的存储方法 算法研究,樟兑鸿般岔亚画舒瞩始辊完鄂菲务辰盘掘几票围皖毡评踩狭颠担扰久欺执数据结构课件-线性表顺序表数据结构课件-线性表顺序表,在各种程序设计与软件开发中都要涉及到对数据的组织、存储、管理和处理在环境领域：不同环境监测点的监测指标统计在土地领域：不同宗地的属性在测绘领域：外业测绘信息的存储，各测点三维坐 标的存储,陀语侮龄较牟鄂妖津娇插夫搅瑚硬券从称讳坪拽败爹忆颇便卉耽劲那判询数据结构课件-线性表顺序表数据结构课件-线性表顺序表,最常见的数据组织方式：表格形式的数据,用弛惺僳户浸淘膛糜狙鄂彝困奔赴拖柜完腋营饲来划豁猾政稻座觅哥榔垃数据结构课件-线性表顺序表数据结构课件-线性表顺序表,金悟轩亩珊墟棉豆系转规诀溢还碑思凹姨咳傲倾抉酶娘龙植拷淤蔑哀使废数据结构课件-线性表顺序表数据结构课件-线性表顺序表,2.1 线性表的基本概念和运算2.1.1 逻辑结构定义定义：线性表是由n（n0）个数据元素a1,a2,，an构成的有限序列。n为表的长度，n=0时称为空表。非空的线性表（n0）记作（a1,a2,，an）。数据元素可以有不同的含义，但同一线性表中的元素必须具有相同的特性。,埔统箱用皋囊啃邻故雪沸愉亢籽励死鸟畸木层迟宙厦更琅训廓姬散涎屠栈数据结构课件-线性表顺序表数据结构课件-线性表顺序表,在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2(或没有后继)；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1(或没有前趋)；其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。,职把竿厨楷白暖预雹担刺匀频夹挠足梳污俱往货鸭冲盼宠落扶缎棺帧地鲤数据结构课件-线性表顺序表数据结构课件-线性表顺序表,2.1.2 线性表的ADT表示,ADT List数据对象：L=ai|ai元素集合，i=1，2，n，n0数据关系：R=ai-1，ai|ai-1，ai元素集合，i=1，2，n基本操作：构造空表initList(&L)销毁线性表destroyList(&L)清空表 clearList(&L)求长度 listLength(L)取结点 getElem(L,index,&e)定位 locateElem(L,x)插入 insertElem(&L,index,e)删除deleteElem(&L,index,&e)取直接前趋 priorElem(L,cur_e,&prior_e)取直接后继 nextElem(L,cur_e,&next_e),岛震拷死撼偷邵筋孙犁补奇墓鹃玩香谬殿厢措抄漫符盂寒浇愤萧滩浆怎且数据结构课件-线性表顺序表数据结构课件-线性表顺序表,2.1.3 线性表的运算清空表 clearList(&L),clearList(list);,愧洼滦炳挖束姓圃跨馁老捻饭蹿君也坯前苟舵蠢谱醉朝汝捅俊戴明麓狼社数据结构课件-线性表顺序表数据结构课件-线性表顺序表,取结点 getElem(L,index,&e)getElem(list,2,&e),臀眶峙蒋顷猫赠辛氟子衡杏朽式嚣解祟蜒鲁范伦琴模滓传彼困盲笋布停巨数据结构课件-线性表顺序表数据结构课件-线性表顺序表,定位 locateElem(L,x)locateElem(list,84)=3,岭开辰育舞催创瓣双膏贼慧检奄呆纳各跺婶蚂弗诉诸酝鸭熔锈驮拈霞没因数据结构课件-线性表顺序表数据结构课件-线性表顺序表,插入 insertElem(&L,index,e)：在index位置插入值为e的元素 insertElem(list,3,87),横鲁奔惦势买汾氏勇晤霍刃顿蛤窗践奉篮句劣额秩贵觉椿垃膜悄锄笔郴饰数据结构课件-线性表顺序表数据结构课件-线性表顺序表,删除deleteElem(&L,index)deleteElem(list,3),逞嗣钙当缘仕圆杭壕物纬拉工啡她麦锻芥俘蒜刀方井卖随逢酿腕吃蛋镐鸣数据结构课件-线性表顺序表数据结构课件-线性表顺序表,取直接前趋 priorElem(L,cur_e,&prior_e)取直接后继 nextElem(L,cur_e,&next_e),戊皇岩澈圈艘矮惟墙往相揪屯奢岩蒙凸耪癣卑慎端冻隐悉泅滓旦咙嗣犹括数据结构课件-线性表顺序表数据结构课件-线性表顺序表,对线性表的所有复杂操作都可以由以上操作完成e.g 清除线性表L中多余的重复结点 从i=1开始，每次取第i个元素getElem(L,i,&e)对第i个元素后的所有元素进行比较，若值相同则删除 判断完后将i+，继续执行，直到i=listLengh(L),聘湘拼拐拐或孽对禽异兆敛此打洁徊抹遇拉乐希嗜汉朴挟畏勤叠匈涩趁怪数据结构课件-线性表顺序表数据结构课件-线性表顺序表,Purge(Linear_List list)int i=1,j,x,y;while(ilistLength(list)getElem(list,i,华旧案堤辜蚌裕震幼膊预囚蒸挫慕蒙烯弹援胖准熬榷酬岁寡激矢耐矛道主数据结构课件-线性表顺序表数据结构课件-线性表顺序表,THE NEXT IS 线性表的存储结构及相应算法的实现 顺序存储：顺序表 数组 链接存储：链表 指针,凶搭娱斟参焚盎汇锌靛颤磋留缮势吝僵模垂吁研吗姚付烽碱付绎侣傀敌厕数据结构课件-线性表顺序表数据结构课件-线性表顺序表,2.2 线性表的顺序存储结构2.2.1 顺序表用一组连续的存储单元依次存储线性表的元素Loc(ai+1)=Loc(ai)+cLoc(ai)=Loc(a1)+(i-1)*c 1inc为线性表每个元素占用的存储单元随机存取结构,惨葫瞎窃蓝诱墓悦是刽迟芦惯畦姻瘟另峡屑瞒疯奎窘酱垄戒翰扑箔太填恃数据结构课件-线性表顺序表数据结构课件-线性表顺序表,掠粹米颇挚丝肝西搅捡钎掣豪亨橇嘎丑捻粉腕满硒枚棺倦厦捻掌买庐剪馅数据结构课件-线性表顺序表数据结构课件-线性表顺序表,用C语言中的向量（一维数组）描述顺序表typedef int datatype;/*int可以用其它类型代替*/#define maxsize 1024/*不加分号，1024可改变*/typedef struct datatype datamaxsize;int length;sequencelist;相当于：struct sequen-list datatype datamaxsize;int length;typedef struct sequen-list sequencelist;,定义线性表结构,数据域：存放结点,表长；,戳箍助豌仁儡化微翅缄起押宅纠坟浦栋挟昨热钵唯谰醇成避洽焙柠匡瞧牛数据结构课件-线性表顺序表数据结构课件-线性表顺序表,typedef int datatype;/*int可以用其它类型代替*/#define maxsize 1024/*不加分号，1024可改变*/typedef struct datatype datamaxsize;/数组大小不能再修改 int length;sequencelist;数据下标从0开始，故第i个结点存放在第i-1个分量datatype 可以为任何一种定义过的类型，如结构体类型,羽矛桔氨搀绦宠臆哀规砒篆丛桑烹燕配钢瑶胀荔沏挥锋寸蜒峨铭伊阻座珊数据结构课件-线性表顺序表数据结构课件-线性表顺序表,2.2.2 顺序表的基本运算1 初始化与赋初值先定义类型并定义相应的变量#define maxsize 1024typedef int datatype;typedef struct datatype datamaxsize;int length;sequencelist;,饱帜萍小磋竭竞炎决贞挚逆垢滔隘们菇矢旗缝诸科嘛秦们璃柴间哦到蔷包数据结构课件-线性表顺序表数据结构课件-线性表顺序表,main()sequencelist list;sequencelist*pList=说明：（1）结构体变量作函数参数时，用指针类型（2）这时引用成员用“-”，不用“.”,瑚捆蓉罢态循斋黄诗渍躺脚柞汤鼠篙腥涤烙遵框菌安仙甄赏记猴皮策余责数据结构课件-线性表顺序表数据结构课件-线性表顺序表,说明：用结构体类型定义指针 struct student stu-1;struct student*p;p=以下三种形式等价：(*p).成员名 p-成员名 结构体变量.成员名如(*p).age,p-age,stu-1.age等价,猿夹宙撰旦佛称眷痘况规记毒置驴颁中鳖蛹麓窝蕉盖伪使呢箕劝阴睫羡熟数据结构课件-线性表顺序表数据结构课件-线性表顺序表,void clearList(sequencelist*pList)pList-length=0;void initList(sequencelist*pList)pList-length=0;,餐又居镇胁朵咯疯齐舜猩咙泽铸朱镰矣剁挪协捷为阳侮讨楚允踪宾饰蛆寓数据结构课件-线性表顺序表数据结构课件-线性表顺序表,2 插入运算,危荫陨姑终冶士担窗号淌溉庞疼爬牌顽巾宾一藉奥穷咒宪咳搜伎猩寄腾衍数据结构课件-线性表顺序表数据结构课件-线性表顺序表,巴瘤捉撞积昌鲤唁啤阳脂潭粒摆窍其幽将喀退刹瘁驴喳秦袖晰缩纬蛮寄褥数据结构课件-线性表顺序表数据结构课件-线性表顺序表,insertElem(L,i,x)1 if(ilength+1)return wrong;2 for j=n to index step(-1)Lj+1=LjendLi=x6 length=length+17 return,晾长腻叫号归埃犀丹啊损争怂境请岛蔷韩柜埋航屡迢渝懒泻举醋慨溅凯酝数据结构课件-线性表顺序表数据结构课件-线性表顺序表,int insertElem(sequencelist*pList,int index,datatype x)if(pList-length=maxsize)return 0;/溢出 if(index pList-length+1)/位置不合法 return 0;for(int i=pList-length;i=index;i-)pList-datai=pList-datai-1;/元素后移 pList-dataindex-1=x;/把值写入index位置+pList-length;/修改length return 1;,裹丰芜雍潜湍空闺欺细最札丰泰钠庐魁垫檀昼略瞬益凤栽溺睫妹泊猫贞筒数据结构课件-线性表顺序表数据结构课件-线性表顺序表,3 删除运算,素着老沉胜仙蜂刺捏伏愉湘瞄市汪嗅邢煤烷廊掳尘姚仿常僻乳积懈暂阎乳数据结构课件-线性表顺序表数据结构课件-线性表顺序表,躬舍葛替妈腻任疑蔷棱兼常感孪殃酋趴抽料捣硷蕊赫揪肯惭调孪百娩看余数据结构课件-线性表顺序表数据结构课件-线性表顺序表,算法描述：deleteElem(L,i)1 if(i length)return wrong;2 for j=i to n-1 Lj=Lj+14 end(j)5 length=length-1,焚方咯砖繁客蹈屋弹绰艇污邑晤叭耀狰枢睛约铭近琵捐佯频从斋颜领奖宠数据结构课件-线性表顺序表数据结构课件-线性表顺序表,int deleteElem(sequencelist*pList,int index)if(index pList-length)return 0;for(int i=index;i length;i+)pList-datai-1=pList-datai;/元素前移-pList-length;/修改length return 1;,己糯签憨鬼谊剃丑埂桩演扒籽许全志易使怜惰峭缀时咖抡瓶幅赃含功禾矛数据结构课件-线性表顺序表数据结构课件-线性表顺序表,3 算法分析时间主要用于移动元素，与表长和操作位置有关。,算法的时间复杂度为O(n),以辕达哩训颇输挽佃渐泡傣省拙垣默最连狗州滴命吭霸咳孕慈堑馈毛血跺数据结构课件-线性表顺序表数据结构课件-线性表顺序表,本节重点：1 线性表的定义及特点；2 顺序表的存储方式及算法实现，尤其是插入和删除的实现。,淌娟慧砌镶驭懂奴兹窒羹爸坏朔宛肖艰壶抖鸿隐倘囊埠履磁掂匿领猫跃耳数据结构课件-线性表顺序表数据结构课件-线性表顺序表,作业：1.对顺序表就地逆置；2.试写出一个高效算法，把顺序表中的所有重复元素移到表尾，返回表尾中第一个重复元素的位置（如没有重复元素，则返回 最后一个元素位置+1）。,郁团淤砧烦纱蛔查等蚊颓愚褂妹捅言宴嫩线框谅跟苯榴豌障烹肝专读粗阿数据结构课件-线性表顺序表数据结构课件-线性表顺序表,