数据结构(C语言版)第2章线性表ppt课件

数据结构 DataStructures C语言版 主讲教师 吴让仲Instructor WU RANGZHONGE mail wurangzhong 第二章线性表 2 1线性表的类型定义2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 3 1线性链表2 3 2循环链表2 3 3双向链表2 4一元多项式的表示及相加 2 1线性表的逻辑结构线性表 LinearList 由n n 0 个数据元素 结点 a1 a2 an组成的有限序列 其中数据元素的个数n定义为表的长度 当n 0时称为空表 常常将非空的线性表 n 0 记作 a1 a2 an 这里的数据元素ai 1 i n 只是一个抽象的符号 其具体含义在不同的情况下可以不同 例1 26个英文字母组成的字母表 A B C Z 例2 某校从1978年到1983年各种型号的计算机拥有量的变化情况 6 17 28 50 92 188 例3 学生健康情况登记表如下 例4 一副扑克的点数 2 3 4 J Q K A 从以上例子可看出线性表的逻辑特征是 在非空的线性表 有且仅有一个开始结点a1 它没有直接前趋 而仅有一个直接后继a2 有且仅有一个终端结点an 它没有直接后继 而仅有一个直接前趋an 1 其余的内部结点ai 2 i n 1 都有且仅有一个直接前趋ai 1和一个直接后继ai 1 线性表是一种典型的线性结构 数据的运算是定义在逻辑结构上的 而运算的具体实现则是在存储结构上进行的 抽象数据类型的定义为 P19 抽象数据类型线性表的定义 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 基本操作 InitList 2TheListADT Objects item0 item1 itemN 1 Operations Findingthelength N ofalist Printingalltheitemsinalist Makinganemptylist Findingthek thitemfromalist 0 k N Insertinganewitemafterthek thitemofalist 0 k N Deletinganitemfromalist Findingnextofthecurrentitemfromalist Findingpreviousofthecurrentitemfromalist ADT Whyafter Definition DataType Objects Operations Example int 0 1 2 INT MAX INT MIN Definition AnAbstractDataType ADT isadatatypethatisorganizedinsuchawaythatthespecificationontheobjectsandspecificationoftheoperationsontheobjectsareseparatedfromtherepresentationoftheobjectsandtheimplementationontheoperations 算法2 1例2 1利用两个线性表LA和LB分别表示两个集合A和B 现要求一个新的集合A A B voidUnion SqList La SqListLb ElemTypee intLa len Lb len inti La len ListLength La Lb len ListLength Lb for i 1 i Lb len i GetElem Lb i 算法2 2例2 2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列 现要求将LA和LB归并为一个新的线性表LC 且LC中的元素仍按值非递减有序排列 此问题的算法如下 voidmergelist listla listlb listwhile I la len j lb len getelem la I ai getelem lb j bj if ai bj listinsert lc k ai I else listinsert lc k bj j while I la len getelem la I ai listinsert lc k ai while j lb len getelem lb j bj listinsert lc k bi 两种算法时间复杂度比较 算法1 O ListLength LA ListLength LB 算法2 O ListLength LA ListLength LB 自测题1 线性表是具有n个 的有限序列 n 0 清华大学1998一 4 2分 A 表元素B 字符C 数据元素D 数据项E 信息项 2 2线性表的顺序存储结构2 2 1线性表 LinearList 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里 用这种方法存储的线性表简称顺序表 假设线性表的每个元素需占用l个存储单元 并以所占的第一个单元的存储地址作为数据元素的存储位置 则线性表中第i 1个数据元素的存储位置LOC ai 1 和第i个数据元素的存储位置LOC ai 之间满足下列关系 LOC ai 1 LOC ai l线性表的第i个数据元素ai的存储位置为 LOC ai LOC a1 i 1 l 由于C语言中的一维数组也是采用顺序存储表示 故可以用数组类型来描述顺序表 又因为除了用数组来存储线性表的元素之外 顺序表还应该用一个变量来表示线性表的长度属性 所以我们用结构类型来定义顺序表类型 defineListSize100typedefintDataType typedefstruc DataTypedata ListSize intlength Sqlist SimpleArrayimplementationofLists array i itemi MaxSizehastobeestimated Sequentialmapping Find KthtakesO 1 time InsertionandDeletionnotonlytakeO N time butalsoinvolvealotofdatamovementswhichtakestime 3 18 2 2 2顺序表上实现的基本操作在顺序表 SequentialList 存储结构中 很容易实现线性表的一些操作 如线性表的构造 第i个元素的访问 注意 C语言中的数组下标从 0 开始 因此 若L是Sqlist类型的顺序表 则表中第i个元素是L data i 1 以下主要讨论线性表的插入和删除两种运算 1 插入 Insert 线性表的插入运算是指在表的第i个位置上 插入一个新结点x 使长度为n的线性表 a1 ai 1 ai an 变成长度为n 1的线性表 a1 ai 1 x ai an 算法2 3voidInsertList Sqlist L DataTypex inti intj if il length 1 printf Positionerror returnERROR if L length ListSize printf overflow exit overflow for j L length 1 j i 1 j L data j 1 L data j L data i 1 x L length 现在分析算法的复杂度 这里的问题规模是表的长度 设它的值为 该算法的时间主要化费在循环的结点后移语句上 该语句的执行次数 即移动结点的次数 是 由此可看出 所需移动结点的次数不仅依赖于表的长度 而且还与插入位置有关 当时 由于循环变量的终值大于初值 结点后移语句将不进行 这是最好情况 其时间复杂度O 1 当i 1时 结点后移语句将循环执行n次 需移动表中所有结点 这是最坏情况 其时间复杂度为O n 由于插入可能在表中任何位置上进行 因此需分析算法的平均复杂度在长度为n的线性表中第i个位置上插入一个结点 令Eis n 表示移动结点的期望值 即移动的平均次数 则在第i个位置上插入一个结点的移动次数为n i 1 故Eis n pi n i 1 不失一般性 假设在表中任何位置 1 i n 1 上插入结点的机会是均等的 则p1 p2 p3 pn 1 1 n 1 因此 在等概率插入的情况下 Eis n n i 1 n 1 n 2 也就是说 在顺序表上做插入运算 平均要移动表上一半结点 当表长n较大时 算法的效率相当低 虽然Eis n 中n的的系数较小 但就数量级而言 它仍然是线性阶的 因此算法的平均时间复杂度为O n 2 删除 Delete 线性表的删除运算是指将表的第i 1 i n 结点删除 使长度为n的线性表 a1 ai 1 ai ai 1 an 变成长度为n 1的线性表 a1 ai 1 ai 1 an voiddeleteList Sqlist L inti intj if iL length printf Positionerror returnERRORfor j i j L length 1 j L data j 1 L data j L length 该算法的时间分析与插入算法相似 结点的移动次数也是由表长n和位置i决定 若i n 则由于循环变量的初值大于终值 前移语句将不执行 无需移动结点 若i 1 则前移语句将循环执行n 1次 需移动表中除开始结点外的所有结点 这两种情况下算法的时间复杂度分别为O 1 和O n 删除算法的平均性能分析与插入算法相似 在长度为n的线性表中删除一个结点 令Ede n 表示所需移动结点的平均次数 删除表中第i个结点的移动次数为n i 故Ede n pi n i 式中 pi表示删除表中第i个结点的概率 在等概率的假设下 p1 p2 p3 pn 1 n由此可得 Ede n n i n n 1 2即在顺序表上做删除运算 平均要移动表中约一半的结点 平均时间复杂度也是O n 顺序表的优点和缺点 优点存储密度大随机存取缺点插入和删除必须大量移动元素必须预先确定空间表空间不易扩充 2 3线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系 这一特点使我们可以随机存取表中的任一结点 但它也使得插入和删除操作会移动大量的结点 为避免大量结点的移动 我们介绍线性表的另一种存储方式 链式存储结构 简称为链表 LinkedLists LinkedLists NULL Initialization typedefstructlist node list ptr typedefstructlist node chardata 4 list ptrnext list ptrptr Tolink ZHAO and QIAN list ptrN1 N2 N1 list ptr malloc sizeof structlist node N2 list ptr malloc sizeof structlist node N1 data ZHAO N2 data QIAN N1 next N2 N2 next NULL ptr N1 Locationsofthenodesmaychangeondifferentruns 4 18 2 3 1线性链表链表是指用一组任意的存储单元来依次存放线性表的结点 这组存储单元即可以是连续的 也可以是不连续的 甚至是零散分布在内存中的任意位置上的 因此 链表中结点的逻辑次序和物理次序不一定相同 为了能正确表示结点间的逻辑关系 在存储每个结点值的同时 还必须存储指示其后继结点的地址 或位置 信息 这个信息称为指针 pointer 或链 link 这两部分组成了链表中的结点结构 其中 data域是数据域 用来存放结点的值 next是指针域 亦称链域 用来存放结点的直接后继的地址 或位置 链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的 由于上述链表的每一个结只有一个链域 故将这种链表称为单链表 SingleLinked 显然 单链表中每个结点的存储地址是存放在其前趋结点next域中 而开始结点无前趋 故应设头指针head指向开始结点 同时 由于终端结点无后继 故终端结点的指针域为空 即null 图示中也可用 表示 例1 线性表 bat cat eat fat hat jat lat mat 单链表示意图如下 110 130135 160头指针head165170 200205 head bat cat eat mat 单链表是由表头唯一确定 因此单链表可以用头 指针的名字来命名 例如 若头指针名是head 则把链表称为表head 用C语言描述的单链表如下 Typedefchardatatype Typedefstructnode datatypedata structnode next listnode typedeflistnode linklist listnode p linklisthead 注意区分指针变量和结点变量这两个不同的概念 P为动态变量 它是通过标准函数生成的 即p listnode malloc sizeof listnode 函数malloc分配了一个类型为listnode的结点变量的空间 并将其首地址放入指针变量p中 一旦p所指的结点变量不再需要了 又可通过标准函数free p 释放所指的结点变量空间 一 建立单链表假设线性表中结点的数据类型是字符 我们逐个输入这些字符型的结点 并以换行符 n 为输入结束标记 动态地建立单链表的常用方法有如下两种 1 头插法建表该方法从一个空表开始 重复读入数据 生成新结点 将读入数据存放到新结点的数据域中 然后将新结点插入到当前链表的表头上 直到读入结束标志为止 linklistcreatelistf void charch linklisthead listnode p head null ch getchar while ch n p listnode malloc sizeof listnode p data ch p next head head p ch getchar return head listlinkcreatelist intn intdata linklisthead listnode phead null for i n i 0 i p listnode malloc sizeof listnode scanf d 2 尾插法建表头插法建立链表虽然算法简单 但生成的链表中结点的次序和输入的顺序相反 若希望二者次序一致 可采用尾插法建表 该方法是将新结点插入到当前链表的表尾上 为此必须增加一个尾指针r 使其始终指向当前链表的尾结点 例 linklistcreater charch linklisthead listnode p r head NULL r NULL while ch getchar n p listnode malloc sizeof listnode p data ch if head NULL head p elser next p r p if r NULL r next NULL return head 说明 第一个生成的结点是开始结点 将开始结点插入到空表中 是在当前链表的第一个位置上插入 该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的 原因是开始结点的位置是存放在头指针 指针变量 中 而其余结点的位置是在其前趋结点的指针域中 算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理 算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况 若读入的第一个字符就是结束标志符 则链表head是空表 尾指针r亦为空 结点 r不存在 否则链表head非空 最后一个尾结点 r是终端结点 应将其指针域置空 如果我们在链表的开始结点之前附加一个结点 并称它为头结点 dummyheadnode 那么会带来以下两个优点 a 由于开始结点的位置被存放在头结点的指针域中 所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致 无需进行特殊处理 b 无论链表是否为空 其头指针是指向头结点在的非空指针 空表中头结点的指针域为空 因此空表和非空表的处理也就统一了 其算法如下 linklistcreatelistr1 charch linklisthead linklist malloc sizeof listnode listnode p r r head while ch getchar n p listnode malloc sizeof listnode p data ch p next p r p r next NULL return head 上述算法里动态申请新结点空间时未加错误处理 可作下列处理 p listnode malloc sizeof listnode if p NULL error Nospacefornodecanbeobtained returnERROR 以上算法的时间复杂度均为O n 二 查找运算1 按序号查找在链表中 即使知道被访问结点的序号i 也不能象顺序表中那样直接按序号i访问结点 而只能从链表的头指针出发 顺链域next逐个结点往下搜索 直到搜索到第i个结点为止 因此 链表不是随机存取结构 设单链表的长度为n 要查找表中第i个结点 仅当1 i n时 i的值是合法的 但有时需要找头结点的位置 故我们将头结点看做是第0个结点 其算法如下 Listnode getnode linklisthead inti intj listnode p p head j 0 while p next 2 按值查找按值查找是在链表中 查找是否有结点值等于给定值key的结点 若有的话 则返回首次找到的其值为key的结点的存储位置 否则返回NULL 查找过程从开始结点出发 顺着链表逐个将结点的值和给定值key作比较 其算法如下 Listnode locatenode linklisthead intkey listnode p head next while p 该算法的执行时间亦与输入实例中的的取值key有关 其平均时间复杂度的分析类似于按序号查找 也为O n 三 插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 1与ai之间 因此 我们必须首先找到ai 1的存储位置p 然后生成一个数据域为x的新结点 p 并令结点 p的指针域指向新结点 新结点的指针域指向结点ai 从而实现三个结点ai 1 x和ai之间的逻辑关系的变化 插入过程如 s next p next p next s x 注意 两条语句的顺序不能颠倒 否则ai的地址会丢失 另外 要注意合法i值为 1 i n 1若in 1 则i值非法 Question Whatwillhappeniftheorderofthetwostepsisreversed 具体算法如下 voidinsertnode linklisthead datetypex inti listnode p q p getnode head i 1 if p NULL error positionerror q listnode malloc sizeof listnode q data x q next p next p next q 设链表的长度为n 合法的插入位置是1 i n 1 注意当i 1时 getnode找到的是头结点 当i n 1时 getnode找到的是结点an 因此 用i 1做实参调用getnode时可完成插入位置的合法性检查 算法的时间主要耗费在查找操作getnode上 故时间复杂度亦为O n 四 删除运算删除运算是将表的第i个结点删去 因为在单链表中结点ai的存储地址是在其直接前趋结点aai 1的指针域next中 所以我们必须首先找到 ai 1的存储位置p 然后令p next指向ai的直接后继结点 即把ai从链上摘下 最后释放结点ai的空间 将其归还给 存储池 此过程为 s p next p next p next next free s Question Howcanwedeletethefirstnodefromalist Answer Wecanaddadummyheadnodetoalist 具体算法如下 voiddeletelist linklisthead inti listnode p r p getnode head i 1 if p NULL p next NULL returnERROR r p next p next r next free r 设单链表的长度为n 则删去第i个结点仅当1 i n时是合法的 注意 当i n 1时 虽然被删结点不存在 但其前趋结点却存在 它是终端结点 因此被删结点的直接前趋 p存在并不意味着被删结点就一定存在 仅当 p存在 即p NULL 且 p不是终端结点 即p next NULL 时 才能确定被删结点存在 显然此算法的时间复杂度也是O n 从上面的讨论可以看出 链表上实现插入和删除运算 无须移动结点 仅需修改指针 线性表实现方法的比较 实现不同顺序表方法简单 各种高级语言中都有数组类型 容易实现 链表的操作是基于指针的 相对来讲复杂些 存储空间的占用和分配不同从存储的角度考虑 顺序表的存储空间是静态分配的 在程序执行之前必须明确规定它的存储规模 也就是说事先对 MAXSIZE 要有合适的设定 过大造成浪费 过小造成溢出 而链表是动态分配存储空间的 不用事先估计存储规模 可见对线性表的长度或存储规模难以估计时 采用链表 线性表运算的实现不同按序号访问数据元素 使用顺序表优于链表 插入删除操作 使用链表优于顺序表 2 3 2循环链表 LinkedCircularLists 循环链表时一种头尾相接的链表 其特点是无须增加存储量 仅对表的链接方式稍作改变 即可使得表处理更加方便灵活 单循环链表 在单链表中 将终端结点的指针域NULL改为指向表头结点的或开始结点 就得到了单链形式的循环链表 并简单称为单循环链表 为了使空表和非空表的处理一致 循环链表中也可设置一个头结点 这样 空循环链表仅有一个自成循环的头结点表示 如下图所示 a1 an head 非空表 空表 在用头指针表示的单链表中 找开始结点a1的时间是O 1 然而要找到终端结点an 则需从头指针开始遍历整个链表 其时间是O n head 在很多实际问题中 表的操作常常是在表的首尾位置上进行 此时头指针表示的单循环链表就显得不够方便 如果改用尾指针rear来表示单循环链表 则查找开始结点a1和终端结点an都很方便 它们的存储位置分别是 rear next next和rear 显然 查找时间都是O 1 因此 实际中多采用尾指针表示单循环链表 由于循环链表中没有NULL指针 故涉及遍历操作时 其终止条件就不再像非循环链表那样判断p或p next是否为空 而是判断它们是否等于某一指定指针 如头指什或尾指针等 算法举例单链表的合并 LinkedListUnion LinkedListla LinkedListlb 将非递减有序的单链表la和lb合并成新的 非递减有序单链表lc 并要求利用原表空间lc LNode malloc sizeof LNode 申请结点lc next NULL 初始化链表lcpa la next pa是链表la的工作指针pb lb next pb是链表lb的工作指针pc lc pc是链表lc的工作指针while pa 接上页 else lb中元素插入lc pc next pb pc pb pb pb next if pa pc next pa 若pa未到尾 将pc指向paelsepc next pb 若pb未到尾 将pc指向pbreturn lc Union 自测题2 若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值 为节省时间应采用的存储方式 A 单链表B 双向链表C 单循环链表D 顺序表 北京理工大学2004一 3 1分 2 3 3双向循环链表DoublyLinkedCircularLists Don twehaveenoughheadachealready Whydoweneedthedoublylinkedlists Supposeyouhavealist1 2 3 m Nowhowwouldyougetthem thnode I llgofromthe1stnodetothem thnode Thenyouareaskedtofinditspreviousnodem 1 Uhhh ThenI llhavetogofromthe1stnodeagain Buthey whydoIwanttafindthepreviousnode Whydoyouaskme Maybeyouwanttadeletethem thnode typedefstructnode node ptr typedefstructnode node ptrllink elementitem node ptrrlink ptr ptr llink rlink ptr rlink llink Adoublylinkedcircularlistwithheadnode Anemptylist 7 18 双向链表 DoublyLinkedLists 在单链表的每个结点里再增加一个指向其直接前趋的指针域prior 这样就形成的链表中有两个方向不同的链 故称为双向链表 形式描述为 typedefstructdlistnode datatypedata structdlistnode prior next dlistnode typedefdlistnode dlinklist dlinklisthead 和单链表类似 双链表一般也是由头指针唯一确定的 增加头指针也能使双链表上的某些运算变得方便 将头结点和尾结点链接起来也能构成循环链表 并称之为双向链表 设指针p指向某一结点 则双向链表结构的对称性可用下式描述 p prior next p p next prior即结点 p的存储位置既存放在其前趋结点 p prior 的直接后继指针域中 也存放在它的后继结点 p next 的直接前趋指针域中 双向链表的插入 p q p prior q 1 2 q prior p prior p prior next q q next p 3 4 双向链表的前插操作算法如下 voiddinsertbefor dlistnode p datatypex dlistnode q malloc sizeof dlistnode q data x q prior p prior q next p p prior next q p prior q 双向链表的删除 p 1 2 p prior next p next p next prior p prior free p voidddeletenode dlistnode p p prior next p next p next prior p prior free p 注意 与单链表的插入和删除操作不同的是 在双链表中插入和删除必须同时修改两个方向上的指针 上述两个算是法的时间复杂度均为O 1 自测题3 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素 则采用 存储方式最节省运算时间 A 单链表B 仅有头指针的单循环链表C 双链表D 仅有尾指针的单循环链表 南开大学2000一 3 自测题4 设一个链表最常用的操作是在末尾插入结点和删除尾结点 则选用 最节省时间 A 带头结点的双循环链表B 单循环链表C 带尾指针的单循环链表D 单链表 江苏大学2006一 3 2分 TwoApplications ThePolynomialADT Objects P x a1xe1 anxen asetoforderedpairsofwhereaiisthecoefficientandeiistheexponent eiarenonnegativeintegers Operations Findingdegree max ei ofapolynomial Additionoftwopolynomials Subtractionbetweentwopolynomials Multiplicationoftwopolynomials Differentiationofapolynomial Representation1 typedefstruct intCoeffArray MaxDegree 1 intHighPower Polynomial Ilikeit It seasytoimplementmostoftheoperations suchasAddandMultiplication Really WhatisthetimecomplexityforfindingtheproductoftwopolynomialsofdegreeN1andN2 O N1 N2 What swrongwiththat TrytoapplyMultPolynomialOnP1 x 10 x1000 5x14 1andP2 x 3x1990 2x1492 11x 5 nowdoyouseemypoint Given Declaration typedefstructpoly node poly ptr structpoly node intCoefficient assumecoefficientsareintegers intExponent poly ptrNext typedefpoly ptra nodessortedbyexponent Representation2 Multilists Example Supposethatwehave40 000studentsand2 500courses Printthestudents namelistforeachcourses andprinttheregisteredclasses listforeachstudent Representation1 intArray 40000 2500 11 18 Representation2 12 18 3 CursorImplementationofLinkedLists nopointer Featuresthatalinkedlistmusthave Thedataarestoredinacollectionofstructures Eachstructurecontainsdataandapointertothenextstructure Anewstructurecanbeobtainedfromthesystem sglobalmemorybyacalltomallocandreleasedbyacalltofree Note Theinterfaceforthecursorimplementation giveninFigure3 27onp 52 isidenticaltothepointerimplementation giveninFigure3 6onp 40 13 18 malloc p CursorSpace 0 Next CursorSpace 0 Next CursorSpace p Next x free p 2 CursorSpace p Next CursorSpace 0 Next CursorSpace 0 Next p Note Thecursorimplementationisusuallysignificantlyfasterbecauseofthelackofmemorymanagementroutines ReadoperationimplementationsgiveninFigures3 31 3 35 14 18 静态链表 有些高级程序设计语言并没有指针类型 如FORTRAN和JAVA 我们可以用数组来表示和实现一个链表 称为静态链表 可定义如下 defineMAXSIZE1000 最多元素个数typedefstruct ElemTypedata 数据元素intnext 指向后继元素在数组中的位置 SLinkedList MAXSIZE 静态链表图示 线性表L 2 3 4 6 8 9 的静态链表图示 自测题5 静态链表中指针表示的是 A 下一元素的地址B 内存储器的地址C 下一元素在数组中的位置D 左链或右链指向的元素的地址 中南大学2003二 2 1分 静态链表与动态链表 静态链表的操作和动态链表相似 只是以整型游标代替动态指针 设以Sa表示静态链表 通常可把Sa 0 理解为 头结点 第1个元素的位置由Sa 0 next指出 用全局整型变量av指出可利用空间的下标 初始时将整个静态链表看作一个 空表 操作中用GetNode 和FreeNode 函数模拟C中的malloc 和free 函数 以下是初始化 取结点和释放结点3个函数 静态链表的初始化 intInitilize 初始可利用空间表 inti for i 0 i maxsize 1 i 链成可利用空间表Sa i next i 1 Sa maxsize 1 next 1 链表尾av 1 returnav 返回可利用空间表的下标 静态链表的申请结点空间 intGetNode 取结点 if av 1 1表示无空间 p av av Sa av next p为可利用空间的下标 returnp 静态链表的释放结点空间 intFreeNode intp 将p归还到可利用空间表中 Sa p next av av p returnav 静态链表的操作举例 1 1 查找值为x的结点intLocate SLinkedListSL ElemTypex intp SL 0 next while p 1 元素下标 静态链表的操作举例 2 2 查找i第个结点ElemT