2012年jsoi春季函授 a层次第一讲 线性表应用

《2012年jsoi春季函授 a层次第一讲 线性表应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性表及其应用【学习与辅导方式】自学为主，所有提到的例题和算法都要编写完整的程序，有疑问的地方可以在网站论坛提问或面授时解答。内部资料，请勿外传。【学习要点】（1）掌握线性表的存储结构及基本操作（2）了解高精度计算中数据处理方法，掌握常见高精度计算方法（3）了解数据处理的常用方法：排序与查找，理解它们的概念（4）掌握常见排序与查找的基本方法及算法的时间复杂性（5）能够比较多种排序算法的优缺点及空间、时间的复杂性（6）理解散列查找、哈希函数的概念，并能够进行简单应用1线性表的存储结构线性表可以用多种方法实现，最常用的、最简单的就

2、是数组。其它的还有：字符串、栈、队列、链表等。在计算机内的存储分为顺序存储方式（数组）和链式存储方式（指针）。对于不同的题目，选用不同的存储方式，其执行效果是不一样的，主要体现在空间复杂度、时间复杂度、编程复杂度三个方面。在选择具体的存储结构实现算法时，必须考虑要进行的是哪些运算，充分估计这些运算执行次数的数量级，以及对存储容量的要求和编程量。1、顺序存储方式（数组方式）在计算机内，存储线性表的最简单和最自然的方式，是把表中的数据元素一个接一个地放进一组连续的存储单元之中，也就是说，把表中相邻的数据元素存放在内存中邻接的存储单

3、元里，这种存储方法叫做顺序存储，又称顺序映象。其特点是：逻辑上相邻的数据元素，它们的物理次序也是邻接的。缺点是要求有足够的、完整的、连续的存储空间供编程者开辟大数组。假设每个数据元素占用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)*Len2、链式存储方式（链表）利用数组描述线性表时，其优点是对线性表中任一

4、元素都可随机存取，具体反映为通过改变下标的值可以对线性表中的任一元素进行访问和修改。其缺点是在向线性表中插入和删除元素时，必须移动表中的部分元素。插入元素时，要将从插入位置直至最后的所有元素后移一个位置。大量的移动操作浪费了宝贵的CPU资源。链表是一种可以实现动态分配的存储结构，它不需要一组地址连续的存储单元，而是一组任意的、甚至是在存储空间中零散分布的存储单元。【例1-1】用随机函数产生N（N<=100000）个小于100000的正整数，统计共产生了多少个不相同的正整数及每个数出现的次数。[思考]1、数组，A[i]=x，表示

5、数i出现了X次。但空间不够；2、有人想，如果数据量很小（255个），也可以用集合做。3、本题用单链表做。4、说明：选用什么样的数据结构和算法在很大程度上取决于数据规模！（1）单链表每个结点的存储单元分为两部分：一部分存储结点的数据域（data域，1个或多个），另一部分存储指向后续结点的指针(next域)。最后一个结点没有后续结点（next域为空NIL），另外，一般线性表的操作都是从表头开始的，所以一般设置一个表头指针head，指向链表的头结点，有时我们还会把链表的实际结点个数存入到头结点中。类型定义如下：typepointer

6、=^node;node=recorddata:datatype;next:pointer;end;A.建立一个单链表(输入一系列自然数，以0表示结束)procedurecreat;varhead，p，s:pointer;b:Boolean;x:integer;beginnew(head);p:=head;b:=true;whilebdobeginreadln(x)；ifx<>0thenbeginnew(s);s^.data:=x;p^.next:=s;p:=s;endelseb:=false;end;p^.next:=nil;

7、end;B．查找p:=head^next;while(p^.data<>x)and(p^.next<>nil)dop:=p^.next;{找到第一个就结束}ifp^.data=xthen找到了处理else输出不存在；如果想找到所有满足条件的结点，则修改如下：p:=head^next;whilep^.next<>nildo{一个一个判断}beginifp^.data=xthen找到一个处理一个；p:=p^.next;end;取出单链表的第i个结点的数据域：functionget(head:pointer;i:integer):i

8、nteger;varp:pointer;j:integer;beginp:=head^.next;j:=1;while(p<>nil)and(jnil)and(j=i)thenwriteln(p^.d