2012年JSOI春季函授A层次第一讲线性表应用.doc

线性表及其应用 【学习与辅导方式】 自学为主，所有提到的例题和算法都要编写完整的程序，有疑问的地方可以在网站论坛提问或面授时解答。 内部资料，请勿外传。 【学习要点】 （1）掌握线性表的存储结构及基本操作 （2）了解高精度计算中数据处理方法，掌握常见高精度计算方法 （3）了解数据处理的常用方法：排序与查找，理解它们的概念 （4）掌握常见排序与查找的基本方法及算法的时间复杂性 （5）能够比较多种排序算法的优缺点及空间、时间的复杂性 （6）理解散列查找、哈希函数的概念，并能够进行简单应用 1 线性表的存储结构 线性表可以用多种方法实现，最常用的、最简单的就是数组。其它的还有：字符串、栈、队列、链表等。在计算机内的存储分为顺序存储方式（数组）和链式存储方式（指针）。 对于不同的题目，选用不同的存储方式，其执行效果是不一样的，主要体现在空间复杂度、时间复杂度、编程复杂度三个方面。 在选择具体的存储结构实现算法时，必须考虑要进行的是哪些运算，充分估计这些运算执行次数的数量级，以及对存储容量的要求和编程量。 1、顺序存储方式（数组方式） 在计算机内，存储线性表的最简单和最自然的方式，是把表中的数据元素一个接一个地放进一组连续的存储单元之中，也就是说，把表中相邻的数据元素存放在内存中邻接的存储单元里，这种存储方法叫做顺序存储，又称顺序映象。其特点是：逻辑上相邻的数据元素，它们的物理次序也是邻接的。缺点是要求有足够的、完整的、连续的存储空间供编程者开辟大数组。 假设每个数据元素占用Len个存储单元，则相邻的两个数据元素ai与ai+1在机器内的存储地址LOC（ai）与LOC(ai+1)将满足下面的关系： LOC(ai+1) = LOC（ai）+Len 一般把LOC（a1）称为基地址，而LOC（ai）的存储地址就为： LOC（ai）= LOC（a1）+(i - 1) *Len 2、链式存储方式（链表） 利用数组描述线性表时，其优点是对线性表中任一元素都可随机存取，具体反映为通过改变下标的值可以对线性表中的任一元素进行访问和修改。其缺点是在向线性表中插入和删除元素时，必须移动表中的部分元素。插入元素时，要将从插入位置直至最后的所有元素后移一个位置。大量的移动操作浪费了宝贵的CPU资源。 链表是一种可以实现动态分配的存储结构，它不需要一组地址连续的存储单元，而是一组任意的、甚至是在存储空间中零散分布的存储单元。 【例1 next:pointer; end; 建立一个单链表(输入一系列自然数，以0表示结束) procedure creat; var head，p，s:pointer; b:Boolean; x:integer; begin new(head); p:=head; b:=true; while b do begin readln(x)； if x0 then begin new(s);s^.data:=x;p^.next:=s;p:=s; end else b:=false; end; p^.next:=nil; end; B．查找 p:=head^next; while (p^.datax) and (p^.nextnil) do p:=p^.next; {找到第一个就结束} if p^.data = x then 找到了处理 else 输出不存在； 如果想找到所有满足条件的结点，则修改如下： p:=head^next; while p^.nextnil do {一个一个判断} begin if p^.data = x then 找到一个处理一个； p:=p^.next; end; 取出单链表的第i个结点的数据域： function get(head:pointer;i:integer):integer; var p:pointer;j:integer; begin p:=head^.next; j:=1; while (pnil) and (ji) do begin p:=p^.next; j:=j+1; end; if (p nil) and (j=i) then writeln(p^.data) else writeln(‘i not exsit!’); end; C．插入一个结点（在单链表中第i个结点（i=0）之后插入一个结点（值为X）） P