高中信息技术 竞赛班数据结构专项培训教程 02线性表教案-人教版高中全册信息技术教案VIP免费

§2线性表§2.1线性表的定义及其基本运算线性表是n个数据元素（结点）a1，a2，……，an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表。线性表的常用的运算：（1）置空表。（2）求线性表L的长度。（3）取表中的第i个结点（4）按值查找。（5）插入：在表L的第i个位置上插入新的结点X。（6）删除：删除表L的第i个结点。线性表可采用两种存储结构：顺序存储和链式存储。§2.2线性表的顺序存储结构它的特点是逻辑上相邻的结点其物理位置亦相邻，下标可以看成是结点的相对地址。·运算：1)插入用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此我们必须将表中位置n,n-1,...,i上的结点依次后移到位置n+1,n,...,i+1上,腾出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。2）删除在顺序表上实现删除运算也必须移动结点，才能反映出结点间逻辑关系的变化。仅当i=n，才能简单地删除终端结点，无须移动结点；3）取表S中的第i个结点:直接以S[i]表示4)查找须顺序取出表中元素逐一比较·顺序表有如下优缺点：优点：（1）无须为表示结点间的逻辑关系而增加额外的存储空间；（2）可以方便地随机存取表中的任一结点。缺点：（1）插入和删除运算不方便，除表尾的位置外，在表的其它位置上进行插入和删除操作都必须移动大量的结点，其效率较低；（2）由于顺序表要求占用连续的存储空间，存储分配只能预先进行（静态分配），因此当表变化较大时，难以确定合适的存规模，若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用，若事先对表长估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出。§2.3线性表的链式存储结构从链接方式上可分为：单链表、循环链表和双链表。1）单链表2）循环链表3）双链表§2.3.1单链表基本运算一、建立单链表建立链表就是要在表中逐一增加新的结点。为此，必须反复执行下列步骤：i）使用过程NEW，获得新的存储单元；ii）读入新结点分量的数据域iii）将指针向后推移，跟踪链表的增长到链表的长度满足要求为止。（1）头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直至读入结束标志为止。【练习1】：完成下面的程序{逐个输入字符型数据，以'$'为结束符，用头插法建立单链表}programlian;typepoint=^node;node=Recorddata:char;next:point;end;varCh:char;Head,S,R:point;beginHead:=nil;{将单链表置为空表}read(Ch);{读入第一个结点的值}while(Ch<>'$')dobeginnew(S);{生成新结点S}{将读入数据放到新结点的数据域中}{将新结点插入链表的表头上}read(Ch);{读入下一个结点的值}end;end.（2）尾插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾上，直至读入结束标志为止。为此必须增加一个尾指针R，使其始终指向当前链表的表尾上。【练习2】：完成下面的程序{尾插法建立单链表Head，数据说明如前}beginHead:=nil;{将链表Head置为空表}R:=nil;{尾指针初值为空}read(Ch);{读入第一个结点的值}while(Ch<>'$')dobegin{'$'为输入结束符}new(S);{生成新结点S}{将读入数据放到新结点的数据域中}If(Head=nil)then{新结点S插入空表}else{S插入非空表尾结点R之后}{尾指针R指向新的表尾}read(Ch);{读入下一个结点的值}end;If(R<>nil)then{R=nil时是空表}R^.next=nil;{将非空表的终端结点的指针域置空}end;☆头结点：如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点：（a）由于开始结点位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无须进行特殊处理；（b）无论链表是否为空，其头指针是指向结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。图:带头结点的单链表Head二、查找运算（1）按序号查找在带头结点的单链表Head中查找第i个结...