Old高一下期6月13日第二部分 数据结构

安阳一中信息学奥赛辅导资料 第二部分 数据结构 概 述 数据结构是计算机专业基础课程之一，是十分重要的核心课程。计算机的所有系统软件和应用软件都要用到各种类型的数据结构。要想更好运用计算机来解决实际问，仅仅学习计算机语言而缺乏数据结构知识是远远不够的，瑞士著名的计算机专家沃思(N.Writh)曾经说过：“算法+数据结构=程序”。可见有了程序设计的基本知识，掌握了一种程序设计语言，并不一定就能设计出比较好的程序，解决比较复杂的实际问题，还必须掌握数据结构及算法设计的基本知识。 数据（Data） 数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。 数据元素（Data Element） 数据元素是数据的基本单位。数据元素也称元素、结点、顶点、。一个数据元素可以由若干个数据项（也称为字段、域、属性）组成。数据项是具有独立含义的最小标识单位。为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。 【例1.1】 学生成绩，见下表。 注意：在表中指出数据元素、数据项、开始结点和终端结点等概念 数据结构（Data Structure） 数据结构指的是数据之间的相互关系，即数据的组织形式。 1．数据结构一般包括以下三方面内容： ① 数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）； 数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 ② 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构(Storage Structure) 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。 ③ 数据的运算，即对数据施加的操作。 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。 （1）逻辑结构 表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"马二"所在结点的直接前趋结点和直接后继结点分别是"丁一"和"张三"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。 （2）存储结构 该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？ （3）数据的运算 在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查找、删除、插入，这就是数据的运算问题。搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。 2．数据的逻辑结构分类 在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类： （1）线性结构 线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 线性表是一个典型的线性结构。栈、队列、串等都是线性结构。 （2）非线性结构 非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 第一章 线性表 在处理实际问题时，大量的是表格处理。例如：一个班级50名学生的某门考试的成绩表。 这类表通常称为“线性表”，每个表是一个整体。同时，它们又都是由多个互相独立的成分（或元素）有序（线性）地组成的，各个成分的类型均相同，这种表在PASCAL语言中通常用数组来实现其组织和加工。 线性表是最常用且最简单的一种数据结构。简而言之，一个线性表是N个数据元素的有限序列，至于每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数或一个符号，也可以是一页书，甚至其它更复杂的信息。例如：由每个英文字母组成的字母表：（A、B、C、……、Z）是一个线性表，表中的数据元素是单个字符；又如某校从1993年至1998年各种型号计算机的拥有量的变化情况，可以用线性表的形式给出（16、27、38、60、102、198），表中的数据元素是自然数，线性表的特点是： ① 存在唯一的一个被称作“第一个”的数据元素； ② 存在唯一的一个被称为“最后一个”的数据元素； ③ 除第一个元素外,线性表中的每个数据元素均只有一个前驱； ④ 除最后一个元素之外,每个数据元素均只有一个后继. 综上所述，线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性，因此属于同一类数据对象。对线性表可进行的运算种类繁多，其中包括： ① 确定表的长度n，即求表中数据元素的个数； ② 从左到右（或从右到左）读表，即按a1、a2…、an（或an、an-1 …、a1 ）读取数据元素的值； ③ 存、取表中第i个数据元素（1≤i≤n），即改变或检查第i个数据元素的值； ④ 在第i-1个和第i个数据元素之间（1≤i≤n）插入一个新的数据元素，使原来的第i，i+1，…，n个数据元素变成为第i+1，i+2，…，n，n+1个数据元素； ⑤ 删除第i个数据元素（1≤i≤n），使原来的第i+1，i+2，…，n个数据元素变成为第i，i+1，…，n-1个数据元素； ⑥ 检索线性表，即在表中查找具有某个特征值的数据元素； ⑦ 对表排序，即按某个特征值递增（或递减）的顺序对表中的数据元素重新排列。 对一个线性表，同时要求进行上述的所有运算，这在计算机的应用中是很少有的。实际上，在很多情况下，只需要完成其中的一部分运算就够了。 二、线性表的存储结构 　　在计算机内，线性表可以用不同的方式表示，即有多种存储结构可供选择。对于完成某种运算来说，不同的存储方式，其执行效果是不一样的，为了使所要进行的运算得以有效地执行，在选择存储结构时，必须考虑要施行的是哪些运算，对选定的存储结构，应估计这些运算执行时间的量级，以及它对存储容量的要求。本讲只介绍数组形式存储的线性表。 在计算机内，存储线性表的最简单和最自然的方式，是把表中的数据元素一个接一个地放进一组连续的存储单元之中，也就是说，把表中相邻的数据元素存放在内存中邻接的存储单元里，这种存储方法叫做顺序分配（Sequential Allocation），又称顺序映象(Sequential Mapping)，其特点是：逻辑上相邻的数据元素，它们的物理次序也是邻接的。 假设每个数据元素占用L个存储单元，则相邻的两个数据元素ai与ai+1在机器内的存储地址LOC（ai）与LOC(ai+1)将满足下面的关系： LOC(ai+1) = LOC（ai）+L，而存储地址LOC（ai）为： LOC（ai）= LOC（a1）+(i - 1) *L 线性表是一个相当灵活的数据结构,它的长度可根据需要增长或缩短。 三、线性表的插入和删除 若插入是在表的末尾进行，即在长度为n的线性表（a1, a2，a3，…，an）的第n个元素之后，添加一个新元素，使长度变为n+1的表（a1, a2，a3，…，an，an+1），这很简单，只要在表的第n+1 个位置上写入新元素即可。 若插入是在表的中间进行，即在长度为n的线性表（a1, a2，a3，…，an）的第i（1≤i≤n）个元素之前插入一个新元素，使长度变为n+1的表（a1, a2，a3，…，an，an+1），此时的情况要稍复杂一点，因为顺序分配是把表中的元素依次放在一组连续的存储单元中，也就是说，表中的元素在机器内是一个紧接着一个，没有“空隙”。为了能在第i个元素之前插入一个新元素，就必须把从第i个到第n个之间的元素依次向后挪动一个位置，腾出一个空位给插入的元素。 所以，在一般情况下，顺序分配的线性表的插入算法为： ① 把ai到an的元素后移一个位置，腾出空位。 ② 往第i个位置上写入新值。 　　现用一个过程描述如下： procedure insert(var v:arraytype;var n:integer;i:integer;x:elementtype); var 　j:integer; begin 　for j:=n downto i do v[j+1]:=v[j]; 　v[i]:=x; 　n:=n+1 end; 　　同样，若删除是在表的末尾进行，也很简单，只要把表的长度n减1即可。 当删除是在表的中间进行，则也要引起表中元素移动。若要删除长度为n的线性表中第i（1≤i≤n）个元素，则必须把表中第i+1到n之间的元素依次向前挪动一个位置，以覆盖掉第i个位置上的存储单元。 在一般情况的线性表的删除算法如下： procedure delete(var v:arraytype;var n:integer;i:integer); var 　j:integer; begin 　for j:=i to n-1 do v[j]:=v[j+1]; 　n:=n-1 end; 四、线性表应用举例 【例1】、某旅馆有100 个房间，以1 到100 编号，第一个服务员来了，他将所有的房门都打开，第二个服务员再把所有编号是2 的倍数的房门都关上，第三个服务员对编号是3 的倍数的房门原来开的关上，原来关上的打开，此后的第四，五...服务员均照此办理。问第100个服务员走进后，有哪几扇门是开着的。 Program lt7_1_1； var door：array[1..100] of boolean； {1 到100 号房门状态，false--关，true--开} i，j：integer； begin fillchar(door，sizeof(door)，true)； {第一个服务员打开全部房门} for i：=2 to 100 do { i表示服务员号码} for j：=1 to 100 div i do door[i*j]：=not door[i*j]； {对房号为i 的倍数的房门进行相反处理} write(’The code of opening door is ： ’)； for i：=1 to 100 do if door[i] then write(i，’ ’)； end. 【算法分析】 (1)这里用door[1..100]来存储1 到100 号房门的开关状态，即是一种线性表，其中：door[1]可以看成是头结点，而door[100]是尾结点；同时由于数组在内存中是按顺序占有一片连续的内存空间，因此这种存储结构即是顺序存储结构。 (2)这里用布尔变量true 和false 分别表示开和关两种状态，对某一房门进行相反处理时只要取反(not)即可，比如：若door[10]为false，not door[10]则为true。 【例2】编码问题：设有一个数组A：ARRAY[0..N-1] OF INTEGER；数组中存储的元素为0-N-1之间的整数，且A[I]≠A[J] (当I≠J)时。 例如：N=6时，有：（4，3，0，5，1，2） 此时，数组A的编码定义如下： A[0]的编码为0： A[I]的编码为：在A[0]，A[1]，……A[I-1]中比A[I]的值小的元素的个数（I=1，2，……N-1）所以上面数组A的编码为:B=(0,0,0,3,1,2) 程序要求解决以下问题： ① 给出数组A后，求出其编码； ② 给出数组A的编码后，求出A的原数据。 [算法设计] 问题①比较简单，只要统计一下即可。问题②是一个线性表的删除问题，将0到 N-1之间的N个整数顺序放在一个线性表C中，取出编码数组B中的最后一个元素b[N-1]，则C中的第b[N-1]个元素为数组A的最后一个元素，取出该元素后从C中删除之，再取编码数组B中的前一个元素，重复上述操作，直到数组A的所有元素都得到为止。 [程序清单] program ex4_1(input,output); const maxn=50; type arraytype=array [0..maxn] of integer; var 　n,select:integer; 　a,b:arraytype; 　procedure init(var v:arraytype); 　var 　　i:integer; 　begin 　　write('Input n:'); 　　readln(n); 　　write('Input ',n,' integer number:'); 　　for i:=0 to n-1 do read(v[i]); 　　readln 　end; 　procedure print(v:arraytype); 　var 　　i:integer; 　begin 　　for i:=0 to n-1 do write(v[i],' '); 　　writeln 　end; 　procedure task1; 　var 　　i,j:integer; 　begin 　　init(a); 　　for i:=0 to n-1 do 　　begin 　　　b[i]:=0; 　　　for j:=0 to i-1 do 　　　　if a[i]>a[j] then b[i]:=b[i]+1; 　　end; 　　writeln('The code of array A is:'); 　　print(b) 　end; 　procedure delete(var v:arraytype;var n:integer;i:integer); 　var 　　j:integer; 　begin 　　for j:=i to n-2 do v[j]:=v[j+1]; 　　n:=n-1 　end; 　procedure task2; 　var 　　i,len:integer; 　　c:arraytype; 　begin 　　init(b); 　　for i:=0 to n-1 do c[i]:=i; 　　len:=n; 　　for i:=n-1 downto 0 do 　　begin 　　　a[i]:=c[b[i]]; 　　　delete(c,len,b[i]) 　　end; 　　writeln('Array A is:'); 　　print(a) 　end; begin 　writeln(' ':20,'1--Task1'); 　writeln(' ':20,'2--Task2'); 　write(' ':20,'Input your select(1 or 2):'); 　readln(select); 　if select=1 then task1 else task2 end. 【例3】M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1、2、…、N报数，凡报到N的猴子退出到圈外，如此循环报数，直到圈内只剩下一只猴子时，这只猴子就是大王。M和N由键盘输入，打印出最后剩下的那只猴子的编号。 这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。 在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素的数组monkey来实现。利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。程序采用模拟选举过程的方法，开始时将报数变量count置为1，用变量current表示当前报数的猴子的编号，也置为1，变量out记录出圈猴子数。当报数达到n时，对当前报数的猴子作出圈处理，即monkey[current]置0，count置0，out增加1。然后继续往下报数，直到圈中只剩一只猴子为止。 [程序清单] program ex4_2(input,output); const maxm=100; var 　i,m,n,count,current,out:integer; 　monkey:array [1..maxm] of integer; begin 　write('Input m,n:'); 　readln(m,n); 　for i:=1 to m do monkey[i]:=1; 　out:=0; count:=1; current:=1; 　while out1 do 　begin 　　current:=(current+n-1) mod rest; 　　if current=0 then current:=rest; 　　for i:=current to rest-1 do monkey[i]:=monkey[i+1]; 　　rest:=rest-1 　end; 　writeln('The monkey king is no.',monkey[1]) end. 【例4】对任意给定的一个自然数n(n<=100)，将分母小于等于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/6,6/7,7/8,1/1. 编程求出n级法雷序列，每行输出10个分数。 [算法设计]由于程序要求以分数的形式输出法雷序列，对每个真分数必需分别存放其分子分母，这就要用两个线性表来实现。开始时线性表中只有两个元素，分别是0/1和1/1，线性表用两个数组fp和fq来表示，fp存放分子，fq存放分母。所有的真分数用一个两重循环来产生，每次将当前产生的真分数p/q插入到线性表中去。为了保证线性表中所有元素在插入新元素后仍然按从小到大的次序排列，首先要从表中找出第一个不小于p/q的元素，如果该元素等于p/q，则说明p/q不是不可约的真分数，p/q无需插入，否则p/q应插入在表中第一个大于它的元素的位置。当向线性表中插入新元素时，如果该线性表是用数组实现的，则插入新元素之前要将从插入位置直到最后的所有元素都后移一位，然后再插入新元素。删除线性表中元素时，只要将从删除位置之后的那个元素直到最后的所有元素都前移一位即可。由于对实数要避免等或不等的比较，程序中在对两个分数进行比较时，将它们化成了乘式进行。 [程序清单] program ex4_3(input,output); const maxn=100; type arraytype=array [1..maxn*maxn] of integer; var 　i,k,n,p,q,total:integer; 　fp,fq:arraytype; begin 　write('Input n:'); readln(n); 　fp[1]:=0; fq[1]:=1; fp[2]:=1; fq[2]:=1; total:=2; 　for q:=2 to n do{列举分母} 　　for p:=1 to q-1 do{列举分子} 　　begin 　　　k:=1; 　　　while p*fq[k]>q*fp[k] do k:=k+1; {寻找插入位置} 　　　if p*fq[k]<>q*fp[k] then { p/q不在表中} 　　　begin 　　　　for i:=total downto k do fp[i+1]:=fp[i]; 　　　　for i:=total downto k do fq[i+1]:=fq[i]; 　　　　fp[k]:=p; fq[k]:=q; total:=total+1 　　　end 　　end; 　　for i:=1 to total do 　　begin 　　　write(fp[i],'/',fq[i],' '); 　　　if i mod 10=0 then writeln 　　end; 　writeln end. [运行程序]下划线表示输入 Input n:15 0/1 1/15 1/14 1/13 1/12 1/11 1/10 1/9 1/8 2/15 1/7 2/13 1/6 2/11 1/5 3/14 2/9 3/13 1/4 4/15 3/11 2/7 3/10 4/13 1/3 5/14 4/11 3/8 5/13 2/5 5/12 3/7 4/9 5/11 6/13 7/15 1/2 8/15 7/13 6/11 5/9 4/7 7/12 3/5 8/13 5/8 7/11 9/14 2/3 9/13 7/10 5/7 8/11 11/15 3/4 10/13 7/9 11/14 4/5 9/11 5/6 11/13 6/7 13/15 7/8 8/9 9/10 10/11 11/12 12/13 13/14 14/15 1/1 到目前为止，我们所知道的描述线性表的方法只有数组，利用数组描述线性表时，其优点是对线性表中任一元素都可随机存取，具体反映为通过改变下标的值可以对线性表中的任一元素进行访问和修改。其缺点是在向线性表中插入和删除元素时，必须移动表中的部分元素。插入元素时，要将从插入位置直至最后的所有元素后移一个位置，如上例所示。删除第i个元素时，需将第i+1至最后一个元素依次向前移动一个位置。 练习一： 1、求1987 乘幂的尾数： M 和N 是自然数，N>M>=1，而1987^M与1987^N的末三位数相同，求最小的M和N。 【算法分析】 （1）本题只须记录1987 的乘幂的末三位数，故不必高精度计算； （2）用数组a[1..n]存储1987 的1至n 次幂的末三位数； （3）)n 的初始值为2，计算1987 的n 次幂的末三位数，并和1987 的1至n-1 次幂进行比较，若无相等的，则n=n+1，重复(3)；否则，第一次找到相等的，即是所求的m，n值。 2、一个特殊的数列： 写出两个1，然后在它们中间插入2 成为121，下一步是在任意两个相邻的和数为3 的数之间插入3，成为13231；再下一步又在任意两个相邻的和数为4 的数之间插入4，成为1432341，...，由键盘输入N(1<=N<=9)，求出用上面方法构造出来的序列，其最后插入的数为N。 【算法分析】 字符串也可以看做是一个特殊的线性表，本题初始串是11，对应N=1 时的情况；然后在串中寻找相应的位置，依次插入2，3，...，K。 3、求序列的第300 项： 把所有3 的方幂及互不相等的3 的方幂和排列成一个递增序列：1，3，4，9，10，12，13，...，求这个序列的第300项。 【算法分析】 本题可以用一个线性表来记录这个递增的序列，通过递推可以将整个序列构造出来。方法如下： (1)数组a 存放线性表，t为尾指针，b 存放3 的幂，初始时t=1，b=1； (2)将b放入表尾，尾指针加1；a[t]←b；t←t+1； (3)将b依次与1至t-1 的元素相加，按顺序放入表尾； (4)重复(2)，(3)，直至第300项放入表中。 第 8 页 共 10 页