广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 02线性表教案.doc

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个结点: 直接以 si表示4) 查找 须顺序取出表中元素逐一比较 顺序表有如下优缺点：优点：（1）无须为表示结点间的逻辑关系而增加额外的存储空间；（2）可以方便地随机存取表中的任一结点。缺点：（1）插入和删除运算不方便，除表尾的位置外，在表的其它位置上进行插入和删除操作都必须移动大量的结点，其效率较低；（2）由于顺序表要求占用连续的存储空间，存储分配只能预先进行（静态分配），因此当表变化较大时，难以确定合适的存规模，若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用，若事先对表长估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出。2.3 线性表的链式存储结构从链接方式上可分为：单链表、循环链表和双链表。1）单链表2）循环链表3）双链表2.3.1 单链表基本运算一、建立单链表 建立链表就是要在表中逐一增加新的结点。为此，必须反复执行下列步骤： i）使用过程new，获得新的存储单元； ii）读入新结点分量的数据域 iii）将指针向后推移，跟踪链表的增长到链表的长度满足要求为止。（1）头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直至读入结束标志为止。 【练习1】：完成下面的程序 逐个输入字符型数据，以 $ 为结束符，用头插法建立单链表 program lian; type point=node; node=record data:char; next:point; end;var ch : char; head, s, r : point; beginhead := nil; 将单链表置为空表 read(ch); 读入第一个结点的值 while (ch $) do begin new(s); 生成新结点s 将读入数据放到新结点的数据域中 将新结点插入链表的表头上 read(ch) ; 读入下一个结点的值 end; end.（2）尾插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾上，直至读入结束标志为止。为此必须增加一个尾指针r，使其始终指向当前链表的表尾上。 【练习2】：完成下面的程序 尾插法建立单链表head，数据说明如前 begin head := nil; 将链表head置为空表 r := nil; 尾指针初值为空 read(ch); 读入第一个结点的值 while (ch $) do begin $为输入结束符 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 个结点(0in)，若找到则输出该结点的数据域，否则输出none。 beginp := head; j := 0; 从头结点开始扫描 while (p.nextnil) and (j i) do begin p := p.next; 扫描下一个结点 j:= j+1; 计数器累计扫描过的结点数 end; if (i = j) then writeln(p.data); 找到了第i个结点 else writeln(none); i n时找不到第i个结点 end;（2）按值查找 在带头结点的单链表head中查找其结点值等于key的结点，若找到则返回该结点的位置p；否则返回nilbegin p := head.next; 从开始结点起比较 while (p nil) and (p.data key) do p := p.next; 继续往下扫描 return(p); end; 三、插入运算（1）后插操作：将值为x的新结点插入p之后【练习3】：完成下面的程序 begin new(s); s.data := x ; 给新结点s赋值x 将s插入p之后 end;（2）前插操作：在带头结点的单链表中，将值为x新结点插入p之前（上图） begin new(s); s.data := x; q := head; 从头指针开始 while (q.next p) 查找p的前趋结点q q := q.next; s.next := p; q.next := s; 将新结点s插入p之前 end;四、删除运算删除p的后继结点r begin r := p.next; p.next := r.next; 将结点*r从链上摘下 dispose(r); 设放结点*r end;【练习4】：完成下面的程序试写一算法实现在单链表中删除多余的、值相同的结点。在单链表上实现时，用指针p指向当前将变为无重复值的结点，指针r用来扫描p的后继结点，并且用指针q始终指向r的前趋。当*r的值和*p的值相同时，删去r，即q的后继，具体算法如下：procedure purge2 (var l:point); 在不带头结点的单链表中删除多余的、值相同的结点var p , q , r : point;begin p := l; while (p nil) and (p.next nil) do begin p不空且p不是终端结点 q := p; r := p.next; 从p的后继开始扫描 while (r nil) do if (p.data = r.data) then begin q.next := r.next; dispose(r); 删去结点r r指向被删结点的后继 end else begin r := r.next; 继续扫描 end; end; end;练习参考答案：练习1：s.data:=ch;s.next:=head;head:=s;练习2：s.data:=ch;head:=sr.next:=s;r:=s;练习3：s.next:=p.next;p.next:=s;练习4：r:=q.next;q:=r;2.3.2 循环链表(circular linked list)是有一种首尾相接的链表。其特点是无需增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加灵活。（1） 单循环链表：在单链表中，将终端结点指针域nil改为指向表头结点或开始结点，就得到了单链表形式的循环链表：（2） 双链表(double linked list)：可以在单链表的每一个结点里再增加一个指向其前趋的指针域prior。这样链表中有两条不同方向的链。结构定义：type point=dnode; dnode=recorddata : real; prior, next : point; end;在带头结点的双链表中，将值为x的新结点插入p之前： new(s); s.data := x;s.prior := p.prior; s.next := p; p.prior.next := s; p.prior := s;删除双链表结点p：p.prior.next := p.next; p.next.prior := p.prior; dispose(p);【综合练习】1约瑟夫问题（ysf.pas）n 个人围成一个圆圈，首先第k个人从1开始一个人一个人顺时针报数, 报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。输入：n、m、k输出：优胜者的序号2多项式相加、减、乘 （dxs.pas）编程进行多项式的加、减、乘的运算。输入： （从文件dxs.in读取）第一行： c （c为字符：+、- 或 * ），表示所要进行的操作第二行：（多项式a）最高项的系数 最高项的指数 次高项的系数 次高项的指数 第三行：（多项式b）最高项的系数 最高项的指数 次高项的系数 次高项的指数 输出： （输出到文件dxs.out） （运算结果）最高项的系数 最高项的指数 次高项的系数 次高项的指数 输入输出举例：输入：a(x) = x4+10x3+3x2+14b(x) = 3x5+5x3-3x2-6a(x)+b(x)=3x5+x4+15x3+8输出：+1 4 10 3 3 2 14 03 5 5 3 3 2 6 03 5 1 4 15 3 8 03法雷序列 （falei.pas）给定任意一个自然数n；将分母小于等于n的不可约的真分数按上升的次序排序，并且在第一个分数前加0/1，而在最后一个分数后加上数1/1，这个序列称为n级法雷序列，以fn表示，例如，f8为0/1，1/8，1/7，1/6，1/5，1/4，2/7，1/3，3/8，2/5，3/7，1/2，4/7，3/5，5/8，2/3，5/7，3/4，4/5，5/