《信息学奥赛数据结构教程pascal版》由会员分享，可在线阅读，更多相关《信息学奥赛数据结构教程pascal版（11页珍藏版）》请在金锄头文库上搜索。
1、信息学奥赛数据结构教程信息学奥赛数据结构教程 PASCAL 版版 第三课第三课 链表链表存储方式的分类：顺序存储结构和链式存储结构；顺序存储结构：在（子）程序的说明部分就必须加以说明，以便分配固定大小的存储单元，直到（子）程序结束，才释放空间。因此，这种存储方式又称为静态存储。所定义的变量相应的称为静态变量。它的优缺点如下：1 优点：可以通过一个简单的公式随机存取表中的任一元素，逻辑关系上相邻的两个元素在物理位置上也是相邻的，且很容易找到前趋与后继元素；2 缺点：在线性表的长度不确定时，必须分配最大存储空间，使存储空间得不 到充分利用，浪费了宝贵的存储资源；线性表的容量一经定义就难以扩充；在插
2、入和删除线性表的元素时，需要移动大量的元素，浪费了时间； 链式存储结构：在程序的执行过程中，通过两个命令向计算机随时申请存储空间或随时释放存储空间，以达到动态管理、使用计算机的存储空间，保证存储资源的充分利用。这样的存储方式称为动态存储。所定义的变量称为动态变量。它的优点如下：1 优点：可以用一组任意的存储单元（这些存储单元可以是连续的，也可以不连续的）存储线性表的数据元素，这样就可以充分利用存储器的零碎空间；2 概念 1：为了表示任意存储单元之间的逻辑关系，对于每个数据元素来说，除了要存储它本身的信息（数据域、data）外，还要存储它的直接后继元素的存储位置（指针域、link 或 next）
3、。我们把这两部分信息合在一起称为一个“结点 node”。 3 概念 2：N 个结点链接在一起就构成了一个链表。N=0 时，称为空链表。4 概念 3：为了按照逻辑顺序对链表中的元素进行各种操作，我们需要定义一个变量用来存储整个链表的第一个结点的物理位置，这个变量称为“头指针、H 或 head”。也可以把头指针定义成一个结点，称为“头结点”，头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头结点的指针域（头指针）存储指向第一个结点的指针，若线性表为空表，则头结点的指针域为空（NIL）。由于最后一个元素没有后继，所以线性表中最后一个结点的指针域为空（NIL）。5 概念 4：由于此
4、链表中的每个结点都只包含一个指针域，故称为“线性链表或单链表”。 （一）指针类型和指针变量的说明、使用、操作1类型和变量的说明type 指针类型标识符= 基类型名； 基类型不能为文件类型var 指针变量名：指针类型标识符；2申请存储单元 动态申请、空间大小由指针变量的基类型决定new(指针变量名)； PASCAL 标准过程3指针变量的赋值指针变量名：=NIL； 初始化，暂时不指向任何存储单元如何表示和操作指针变量？不同于简单变量（如 A：=0；），PASCAL 规定用“指针变量名”的形式引用指针变量（如 P：=0；）。如下图：4相同基类型的指针变量之间可以进行相互赋值如有下面的程序段，可以画出
5、右边的示意图：var p1,p2:integer;new(p1);new(p2);p1:=90;p2:=80;p1:=p2;5关系运算如：if p1=p2 then while p-1 do 读入的数非-1beginnew(p); 则，申请一个新结点p.data:=x;p.next:=nil;r.next:=p; 把新结点链接到前面的链表中，实际上 r 是 p 的直接前趋r:=p; 尾指针后移一个read(x);end;r.next:=nil; 最后一个结点的指针域赋空readln;writeln(output: ); 输出 p:=head.next; 头指针没有数据，只要从第一个结点开始就可
6、以了while p.next x) and (p.nextnil do 一个一个判断beginif p.data = x then 找到一个处理一个；p:=p.next;end;2 取出单链表的第 i 个结点的数据域function get(head:pointer;i:integer):integer;varp:pointer;j:integer;beginp:=head.next;j:=1;while (pnil) and (ji-1) then writeln(no this position!)else begin 插入new(s);s.data:=x;s.next:=p.next;p
7、.next:=s;end;end; 4 删除单链表中的第 i 个结点（如下图的“b”结点）procedure delete(head:pointer;i:integer;);删除第 i 个元素varp,s:pointer;j:integer;beginp:=head;j:=0;while (p.next nil dobeginn:=n+1;p:=p.next;end;len:=n;end; （四）双向链表每个结点有两个指针域和若干数据域，其中一个指针域指向它的前趋结点，一个指向它的后继结点。它的优点是访问、插入、删除更方便，速度也快了。但“是以空间换时间”。数据结构的定义：type point
8、er=nodetype;nodetype=recorddata:datatype;pre,next:pointer; pre 指向前趋，next 指向后继end;var head,p,q,r:pointer;下面给出双向链表的插入和删除过程。Procedure insert(head:pointer;i,x:integer);在双向链表的第 i 个结点之前插入 XVars,p:pointer;j:integer;BeginNew(s);S.data:=x;P:=head;j:=0;while (p.nextnil) do 归并beginif p1.datanil then p3.next:=p
9、1 将 p1 中剩下的结点一起链接到 p3 中else p3.next:=p2; 将 p2 中剩下的结点一起链接到 p3 中end; 2一元多相式的表示和加减运算问题描述在数学上，一个一元 n 次多项式 Pn(x)，可以按升幂写成：Pn(x)=P0 + P1X + P2X2 + P3X3 + PnXn它由 n+1 个系数唯一确定。因此，在计算机里，它可以用一个线性表 P 来表示：P = （P0，P1，P2，Pn）每一项的指数 i 隐含在系数 Pi 的序号里。 任务给定一个一元 n 次多项式 Pn(x) 和一个一元 m 次多项式 Qm(x)，求它们的和与差。 数据结构方法 1：按 n,m 分别生
10、成 n+1 和 m+1 个结点的两个单链表，即不管系数是否为 0 都生成一个结点。一个指针域指向后继结点，一个数据域存放系数（不存在的项系数为 0）。浪费了很多空间，尤其是指数很高，而项数很少的情况下，浪费更严重。方法 2：只生成存在的项，实际多少项就有多少结点，每个结点有 2 个数据域，一个存放系数，一个存放指数。如有以下多项式 P8(x)=3+8x+9x5+6x8 ，用上述两种方法表示的示意图分别如下： 方法 1 示意图方法 2 示意图算法分析算法非常简单，遍历两个单链表，根据指数和系数进行相应的加减，生成一个新链表。系数为 0 的结点删除掉（或不生成这种结点），输出该链表。 3魔术师与扑
11、克问题问题描述13 张黑桃扑克（A 2 3 4 5 6 7 8 9 10 J Q K），预先排好，正面朝下拿在魔术师的手里，从最上面开始，第一次数一张牌翻过来放在桌面上，正好是“A”；第二次数两张牌，数 1 的那张放在手中扑克的最下面，数 2 的那张翻过来放在桌面上正好是“2”；,如此下去，放在桌面上的牌最后正好是“A 2 3 4 5 6 7 8 9 10 J Q K”的顺序（从下向上）。 任务编程，找出魔术师手中扑克原来的排列顺序（从下向上）。 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 个分数。
