数据结构线性表3

数据结构第二章线性表2.1线性表的定义及操作2.2线性表的顺序存储及操作实现2.3线性表的链式存储及操作实现2.4顺序表与链表的比较物理结构逻辑结构操作一.线性表的定义（逻辑结构）背景和线性关系

一班学生考完某门课后成绩，通讯录在数据元素的非空有限集中：（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继。

2.1线性表的定义及操作说明：元素可以是简单的一个数，也可以复杂的个人信息。

具有相同特征的n（n0)个元素构成的有限序列称为线性表。n为线性表的长度；长度为0的线性表称为空表。

A=(a1，a2，a3，...ai,ai+1,...,an)

线性表一般表示：

ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。其中：ai是线性表第i个元素，把i称为数据元素ai在线性中的位序。a1a2a3·

·

·

字母表：(‘A’，‘B’，‘C’，……,‘X’,‘Y’,‘Z’)

a1a2a3

……a24,a25a26数据文件：例：

学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004...

a1a2a3

……图片文件：数据元素a

可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。二.线性表的基本运算

1.创建一个新的线性表。

5.修改线性表的第i个位置上的数据元素。

4.根据数据元素的某数据项(通常称为关键字)的值求该数据元素在线性表中的位置。

3.检索线性表中第i个数据元素。

2.求线性表的长度n。

6.在线性表的第i个位置上插入一个新的数据元素。

7.删除线性表中第i个数据元素。8.对线性表中的数据元素按照某一个数据项的值的大小做升序或者降序排序。

10.按照一定的原则，将两个或两个以上的线性表合并成为一个线性表。

9.复制一个线性表。

11.按照一定的原则，将一个线性表分解为两个或两个以上的线性表。

……2.2线性表的顺序存储结构及操作实现一.顺序表顺序存储方式2000:00012000:00032000:00052000:00072000:00092000:00112000:001300000000000000010000000000000010000000000000001100000000000001000000000000000101000000000000011000000000000001111234567a[7]例如：C语言中的数组即采用顺序存储方式。

用一组地址连续的存储单元依次存储线性表中的数据元素，数据元素之间的逻辑关系通过元素的存储位置直接反映。若假设每个数据元素占用k个存储单元，并且已知第一个元素的存储位置LOC(a1)，则有

LOC(ai)=LOC(a1)+(i-1)ka1a2a3……and1d2d3

……dn

(a1，a2，a3，......,an)顺序表在类C语言中，可用一维数组来描述顺序表：#definemaxsize1024intlinearlist[maxsize];charcharlist[maxsize];二.顺序表的类C语言表示#definemaxlen=1024typedefstructlisttype{ datatypedata[maxlen]; intlength;}listtype;1.在线性表的第i个位置上插入一个新的数据元素

该运算是在线性表的第i-1个数据元素与第i个数据元素之间插入一个由符号item表示的数据元素，使长度为n的线性表(a1,a2,

…

,ai-1,ai,

ai+1,

…

,an-1,

an)

转换成长度为n+1的线性表(a1,a2,

…

,ai-1,item,ai,

…

,an-1,an)n个数据元素n+1个数据元素三.顺序表的基本运算算法思路:VoidINSERTLIST(chara[],charx,inti,intn)25372145…671移动数据，在插入位置上形成空2在相应的位置上插入在顺序存贮的线性表的第i–1位置与第i位置之间插入一个元素。假设表中有n个元素，那么需要将第n个元素移动为第n+1个元素，第n-1个元素移动为第n个元素，……，第i个元素移动为第i+1个元素for(j=n;j>=i;j--) a[j+1]=a[j];在位置i上插入元素,例如x:a[i]=x;算法框架:VoidInsertList(chara[],charx,inti,intn){

n=n+1;

a[i]=x;

//将x插入第i个位置//

for(j=n;j>=i;j--) a[j+1]=a[j]; //数据元素依次向后移动一个位置//if(表已经满)printf(‘Thelistisfull!’);else//表尚未满，检查插入的位置是否有效if(插入的位置无效)printf(“positionisnotexist”);else{//移动元素，并插入}

//线性表的长度加1//}算法:VoidInsertList(chara[],charx,inti,intn){

n=n+1;

a[i]=x;

//将x插入第i个位置//

for(j=n;j>=i;j--) a[j+1]=a[j]; //数据元素依次向后移动一个位置//if(n==Maxsize)printf(‘Thelistisfull!’);elseif(i<=0||i>n)printf(“positionisnotexist”);else{}

//线性表的长度加1//}时间复杂度分析

若设pi为插入一个元素于线性表第i个位置的概率(概率相等)，则在长度为n的线性表中插入一个元素需要移动其他的元素的平均次数为：

位置1：n 位置2：n-1

… 位置i：n–i+1

… 位置n：1

Tis=Pi(n-i+1)=(n-i+1)/(n+1)=(n+1)/2(概率均等时）称该算法的时间复杂度是O(n)。该运仰算是艺把线保性表状的第i个数圾据元怀素从鲜线性香表中跟去掉焰，使新得长私度为n的线捡性表(a1,接a2,…,宅ai-花1,ai,ai+纱1,…,an-酬1,an)2.君删耳除线盟性表毁的第i个数颗据元脱素转换级成长申度为n-捧1的线深性表(a1,蛇a2,…,俯ai-受1,逆ai+格1,懒…,浇an-赶1,体an)n个数据元素n-1个数据元素算法夺框架迈:voi禽d碎D马el弯et酿eL雪is幼t(建ch室ar蛙l互in剪e[扩]言,两in第t纱n甜,山i殊nt勉i困)弓{}n=衰n-截1;}//线性捏表的纠长度趁减1fo骡r辅(俩j=抛i;畜j<译=n乐-1油;苦j鱼++遇)li惑ne匙[j例]=萍li盘ne卡[j慈+扫1]覆;//数据绘元素彩依次凡向前珍移动示一个轨位置if搅(删除悼元素跳的位豪置无捷效)pr取in钥tf(创‘T棚he妻po汗si邪ti鸡on适is渠no包t乐e怪xi庭st崖!’阿)茧;el钻se匆{算法网:voi踩d瞒D壶EL判ET妻EL猾IS蜻T(惩ch虎ar兄l殖in狂e[鼻]烂,甘in作t食n狠,徒i竟nt必i画)捕{}n=帝n-秘1;}//线性奥表的底长度脚减1fo烦r诱(浸j=凳i;埋j>碗=n糖-1螺;都j撤++塔)li霜ne泰[j日]=叹li灾ne自[j荒+乔1]骑;//数据迁元素脚依次朝向前昨移动勒一个沿位置if太(i岭-1润<0射|容|半i-改1>龄n-堂1)pr邪in厕tf(共‘T肆he犬po妨si揪ti披on羡is易no邮t万e些xi五st路!’环)胶;el斩se匹{时间摄复杂稻度的滩分析

在长度为n的线性表中删除第i个数据元素需要移动其他的元素的平均次数为：

Tds=Pi(n-i)=(n-i)/n=(n-1)/2称该算法的时间复杂度为O(n)。

ni=1ni=1四.坐线幅性表熔的顺乓序存兔储结郑构的徒特点1.倍优点大：2.丈缺点嫩：(1急)闯不终必为川表示炭数据谎元素绕的逻东辑关拔系而先增加贱额外唯的存轧储空锋间。(2俯)及元木素的贯存储则地址探可以裂通过绕一个钥简单竹的解义析式滔计算企出来剩。(1星)巩存段储分幅配需叫要事急先进徐行，押即静筋态分引配。(2柏)垄需矛要一捧片地怖址连拘续的粱存储湿空间棍。(3街)胶基差本操披作必惨须移评动大君量结咐点，崇(时顽间)挪效率熟较低想。a1a2a3a30∧list…一.构造链原理用一纹组地谨址任航意的鞭存储浊单元统(连椒续的快或不耍连续测的)词依次裙存储屈线性歼表的某各个个数据拳元素凭,数毒据元萌素之满间的线逻辑朱关系箱通过遣链指客针间荣接地悄反映樱出来创.…d1d2d3d4

a2a1a4a3d4d1d5d3…2.垃3余线快性表怕的链别式存裤储结望构da伞ta始l涌in绍ka1a2a3anan-1…list^结点线性杯表的愉这种翻存储记结构振又称欠为单拔链表赏，或筐者线性骄链表，其贩一般搞表示锡形式肢为：用类C语言描述：structnode{chardata;…………structnode*link;};structnodenode;structnode*list,*p;

datalink结点定义骆一个敢结构而类型声明规该结根构类助型的震变量班和指称针变丙量三.逃单满链表杰的有奥关操体作求线声性表算的长炕度。建立鹿一个订线性芦链表赏。在线稠性链前表中成插入革一个汇新的乱结点绢。从线蜡性链苏表中胞删除惠一个喜结点岁。从线汽性链竖表中亚检索滑一个岁结点字。将两捉个线叶性链注表合逢并为扩一个肝线性泽链表村。……1.银求单兔链表第的长红度pppppa1a2a3anan-1…list^定位沙于链汪表头移动惑/计姓数,…,移动位/计茎数直到痛不能寄再移出动p=list;p=p->linkP=NULL(循环）n=0;计数器置0n=n+1;算法勒框架in乖t受L线en垒gt巾h(译s伞tr范uc滑t蹲no贱de森*熔li同st坟)派{//定位尽于链蓄表头//链表忽的长待度置初值萄0//wh首il打e层(能移雅动)宇{移动计数汪器加南1;}re涉tu咳rn贵(表长沸度汁);}算法in刊t亡L安en演gt绑h(塘s御tr牺uc付t解no斧de视*粉li鬼st俩)堂{p所=另li款st医;闷//定位现于链予表头n雹=社0;东/虚/链表锋的长档度置初值超0//wh患il射e羡(p抢!食=抬NU柴LL型)青{p盖=医p-涝>l堂in汁k;n业=叼n侦+孙1;}re歇tu旦rn互(殖n剂);//返回斑链表绞的长道度n//}2.锡建悠立一川个单觉链表p=拍ma筹ll续oc复(每…醒);吐/泥/战fr插ee鹊(p患);a1a2a3anan-1…list^(a1,虫a2,伪a3,海a4,…魔,an-大1,僻an)list=NULL申请新结点置数据域置链域

datalinkp-去>d蚊at桌a笔=朱a;li虾st干=奸N填UL屑L;list^an

alinkp^p-易>l记in涨k眯=电l括is守t;li鹊st的=坦p复;

alinkpVoidCreateLinkList(){list=NULL;//创建一个空链表//

for(？？){ //取一个数据元素// //申请一个新结点//

//设置数据域 //设置链域

p->link=list; list=p;}}算法算法框架VoidCreateLinkList(){list=NULL;//创建一个空链表//

for(i=1;i<n;i++){ch=getchar();//取一个数据元素//

p=(structnode*)malloc(sizeof(structnode));

//申请一个新结点//

p->data=ch;p->link=Null;

p->link=list;list=p;}}算法算法说明堡：这那里的区插入瞒点位强于链裂表的爹头，付也可倍以位僻于链恰表的坝尾插入克过程：qlist3盼.在线遵性链耗表中御由指适针q指的左链结宪点之途后页插虑入一减个数野据信织息为it谣em的链掉结点被插入链结点itempp-仗>l棉in屈k摧=赏q-泰>l级in握k;q-樱>l僵in岭k晋=宫p;算族法Vo弄id见I陪ns甘er窜tL晌in割k(迅st寨ru眯ct自n居od厦e使*l洁is堂t,评s遮tr砖uc扣t夏no奖de作*凡q,算c泥ha彩r批ch融)吴{p=身(s心tr调uc们t星no帮de终*浪)m蓬al套lo甘c(医si茫ze热of帐(s好tr石uc裳t额no盘de存))垃;//申请艇一个唉新结帽点p-售>da桂ta伞=c丸h;//将ch送新烤结点味的数胳据域if途(l柿is芝t=昼=N齐UL较L)流{//若原睡链表干为空旺//li秘st转=p弹;p-预>l刘in时k=就NU凭LL秤;}圣el并se遗{//若原郑链表靠为非泉空p-颤>l赴in它k=英q-皱>l词in静k;q-讯>l困in闯k=以p;}}rq^list4.从非来空线怨性链尖表中欧删除q指的曲链结洗点q^li拒st循找q的前唤趋：rl连in禾k(熟r)rr修改弄链域恒：r->茶li辰nk怀=赚q剪->视li兄nk说明董：1冶此时缩慧需要白释放q所占如的空姻间，fr烫ee蚁(q木)。2对于q处于补链表镜头时税，需刑要单向独处悟理。VoidDeleteNode(structnode*list,structnode*q){

if(q是头结点)//当删除链表的第一个结点//直接修改else{//不是头结点

//查找q的直接前趋结点//如果查找不成功 //报告出错 // 否则，证明查找成功，那么修改链域

}free(q);//释放被删除结点的存储空间}算法框架VoidDeleteNode(structnode*list,structnode*q){

if(q==list)//当删除链表的第一个结点

list=q->link;else{

r=list;while(r->link!=q&&r->link!=Null)r=r->link;//移向下一个链结点//寻找q结点的直接前驱rif(r->link=Null){printf(“Thereisnothisnode!”);return;}else

r->link=q->link;}free(q);//释放被删除结点的存储空间}算法一.肺双永向链只表的边构造所谓双向工链表是指母链表缠的每碍一个猪结点丈中除摊了数敬据域捷以外古设置谈两个定指针拣域，稿其中混之一乐指向午结点粒的直塌接前府驱结悬点，邻另外柱一个拢指向补结点键的直邪接后竟继结跨点。链结纯点的录实际油构造猾可以追形象险地描巷述如吨下：llinkdatarlink其中于，da疯ta为数奏据域ll班in侵k,rl班in斑k分别节为指献向该澡结点厅的直俱接前盛驱与直物接后蚁继结意点的避指针浙域2.乏5双向唇链表常及其缠操作^^li缺stlist用类C语言描述：structbinode{chardata;…………structbinode*llink,rlink;};structbinodebinode;Structbinode*list,*p;二.忠双向疤链表歉的插错入在带盏有头陷结点咐的非扭空双氧向循法环链篮表中梢第一密个数判据域挪的内蛾容为x的链卖结点牛右边勤插入茶一个渗新结孕点。需要蚕做的缝工作：找到各满足锄条件雄的结否点。若找朴到，询申请缸一个琴新的眉链结挖点。将新粱结点血插到但满足赏条件卸的结今点后践面。itemitemitemp插入前xq插入后插入算法势框架//勺q初值颠时指诸向头透结点//寻找秃满足签条件拖的链固结点if哨(寻找翅不成珍功)由{pr五in死tf浪(袍“T袜he或re羊i翻s命no陈t谁hi辨s响no帅de趋!疾”并);re扩tu怜rn群;//没有芹找到毒满足佩条件毛的结膊点}

voidInsert(structbinode*list,charx,charch){}//产生缺新结星点，减将数愧据域笔置为chq-痛>r劝li奇nk家=p拦;(q-致>r属li雅nk疯)-介>l川li凡nk姨=p扛;p-糊>r爸li抄nk遣=q足->愈rl道in嫌k;p-龟>ll塞in碌k=哨q;……pxitemq//特完让成链雨接算法q=责li黄st潜;//扣q初值枣时指渗向头慨结点wh定il鸟e骆(缓q龄!=亮l叛is召t闸&餐&捡q不->扛da膀ta芝!昆=移x)q=盟q-印>r跪li耗nk罚;//寻找裳满足利条件质的链兼结点if矿(q截==抬li跌st眉){敏p杆ri观nt勇f(倾“避Th司er黎e庸is棕n预o忘th外is晒n完od躬e麦!”狮)霉;re料tu篮rn舍;杂}//没有杏找到煎满足竹条件乳的结齐点

voidInsert(structbinode*list,charx,charch){}p=掘(s扮tr到uc留t驰bi议no伪de锣*焰)m称al糖lo隆c(码si哑ze佛of景(s塑tr顶uc象t暖bi饼no傍de纤))勒;p-泼>d蝴at朋a=千ch处;q-厅>r扛li南nk里=p炮;(q-书>r潜li丑nk眠)-竞>l掉li尽nk赵=p踏;p-钩>r蓬li佩nk格=q载->骡rl份in讯k;p-印>ll框in协k=沈q;……pxitemq三.赞双向摸链表洲的删介除功能：从带顶有头绘结点睡的非猪空双脖向循分环链叹表中帜删除第象一率个数哗据域权中内踏容为x的链帝结点。需要罢做的更工作金：1.露找到伞满足擦条件飘的结胡点。2.局若找衫到，灿删除侦并释误放该劲结点帮。list删除前删除后删除算法q=之li浆st//q初值除时指掏向头谱结点wh虑il家e樱(然q!阁=l和is御t眼&奥&柔q标->碌da豆ta临!=塔x蚕)q=大q-误>r浊li撇nk舱;//找满骄足条熟件的束链结