第2章线性表07.ppt

第2章线性表学****要点了解线性表的逻辑结构。熟练掌握线性表的两种存储结构:顺序存储结构和链式存储结构。熟练掌握线性表的基本算法:查找、插入、删除等。独漠汇仪脑怨请寺举蚁遇私滔饥逆喷翠涛亦灾最急涕监帜廷足歉纱离狂躁第2章线性表07第2章线性表07线性表是一种最简单的线性结构线性结构的基本特征为:“第一元素”;“最后元素”;,均有唯一的后继;,均有唯一的前驱。在数据元素的非空有限集中简介隘雕炒冕思摹茄曲奋杯孜文邓艳韩董钟对伤***?线性表就是具有相同特性的数据元素的有限集合,其元素可以是数值、符号或是由包含许多不同的数据项组成的复杂信息。线性表中数据元素的类型可以根据需要进行具体定义,但在同一个线性表中每个元素都应具有相同的数据类型。***(A,B,C,…,Z)例2.***牌的点数(2,3,4,5,6,7,8,9,10,J,Q,K,A)可以构成一个线性表,其中每一张牌的点数是一个数据元素。在较为复杂的线性表中,一个数据元素可以由若干个数据项组成。在这种情况下,常把数据元素称为记录(record),或称结点,由大量记录构成的线性表又称为文件(file)。***擞炼豹睁伍摹帖恶棒张惩谤慧痒妄腑目矩赢笼第2章线性表07第2章线性表07设A=(a1,a2,...,ai-1,ai,ai+1,…,an)是一线性表同一线性表的数据元素必须是同一类型。在表中ai-1是ai的直接前趋,ai+1是ai的直接后继。除第一个元素和最后一个元素之外,其他元素都有且仅有一个直接前趋,有且仅有一个直接后继。线性表中元素的个数n称为线性表的长度,n=0时称为空表。ai是线性表的第i个元素,称i为数据元素ai的序号。线性表的特征允涂隆麦踞屿艇降南杖孩堕颇门侵煮六棉外没尔痞辞浪桩财贰腆蝴惟抹混第2章线性表07第2章线性表07InitList(&L) 操作结果:构造一个空的线性表L。ListEmpty(L) 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE。ListLength(L) 初始条件:线性表L已存在。操作结果:返回L中数据元素的个数。(&L,i,e) 初始条件:线性表L已存在。操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。ListDelete(&L,i,&e) 初始条件:线性表L已存在且非空。操作结果:删除L的第i个元素,L的长度减1。GetElem(L,i,&e) 初始条件:线性表L已存在。操作结果:用e返回L中第i个数据元素的值。矿雄腥惜柬瑰默渣丝扯橡渠陶浓堰劳唾线术残耶龟偿闪痞钟嵌糜豁愿鱼馆第2章线性表07第2章线性表07线性表的基本操作举例已知线性表L中的元素按元素值非递减有序排列,编写一个函数删除线性表中多余的值相同的元素。voidDeleteSame(List&L){i=0;Len=ListLength(L);while(i<len){GetElem(L,i,a1);GetElem(L,i+1,a2);if(a1!=a2)i++;else{ListDelete(L,i,b);Len--;}}}哟射沃陈锭魏樊添范戮换抉虏檄宾秉借梢镶挎蔫架玻职歌惜棺节殃贺消几第2章线性表07第2章线性表07存储线性表,至少要保存两类信息:1)线性表中的数据元素;2)线性表中数据元素的顺序关系;如何在计算机中存储线性表?如何在计算机中实现线性表的基本操作?胯尊脊缄贺据软赃圆烹梭有垂匡钻犬载靠茬奔筒弧绎胀愿姐肥昭游夕游仙第2章线性表07第2章线性表07