信息学奥赛数据结构教程pascal版

《信息学奥赛数据结构教程pascal版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息学奥赛数据结构教程PASCAL版第三课　链表存储方式的分类：顺序存储结构和链式存储结构；顺序存储结构：在（子）程序的说明部分就必须加以说明，以便分配固定大小的存储单元，直到（子）程序结束，才释放空间。因此，这种存储方式又称为静态存储。所定义的变量相应的称为静态变量。它的优缺点如下：　　1．优点：可以通过一个简单的公式随机存取表中的任一元素，逻辑关系上相邻的两个元素在物理位置上也是相邻的，且很容易找到前趋与后继元素；　　2．缺点：在线性表的长度不确定时，必须分配最大存储空间，使存储空间得不到充分利用，浪费了宝贵的

2、存储资源；线性表的容量一经定义就难以扩充；在插入和删除线性表的元素时，需要移动大量的元素，浪费了时间；链式存储结构：在程序的执行过程中，通过两个命令向计算机随时申请存储空间或随时释放存储空间，以达到动态管理、使用计算机的存储空间，保证存储资源的充分利用。这样的存储方式称为动态存储。所定义的变量称为动态变量。它的优点如下：　　1．优点：可以用一组任意的存储单元（这些存储单元可以是连续的，也可以不连续的）存储线性表的数据元素，这样就可以充分利用存储器的零碎空间；　　2．概念1：为了表示任意存储单元之间的逻辑关系，对于每

3、个数据元素来说，除了要存储它本身的信息（数据域、data）外，还要存储它的直接后继元素的存储位置（指针域、link或next）。我们把这两部分信息合在一起称为一个“结点node”。　　3．概念2：N个结点链接在一起就构成了一个链表。N=0时，称为空链表。　　4．概念3：为了按照逻辑顺序对链表中的元素进行各种操作，我们需要定义一个变量用来存储整个链表的第一个结点的物理位置，这个变量称为“头指针、H或head”。也可以把头指针定义成一个结点，称为“头结点”，头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加

4、信息，头结点的指针域（头指针）存储指向第一个结点的指针，若线性表为空表，则头结点的指针域为空（NIL）。由于最后一个元素没有后继，所以线性表中最后一个结点的指针域为空（NIL）。　　5．概念4：由于此链表中的每个结点都只包含一个指针域，故称为“线性链表或单链表”。（一）指针类型和指针变量的说明、使用、操作1．类型和变量的说明　type指针类型标识符=^基类型名；{基类型不能为文件类型}　var指针变量名：指针类型标识符；2．申请存储单元{动态申请、空间大小由指针变量的基类型决定}　new(指针变量名)；{PASCA

5、L标准过程}3．指针变量的赋值　指针变量名：=NIL；{初始化，暂时不指向任何存储单元}　如何表示和操作指针变量？不同于简单变量（如A：=0；），PASCAL规定用“指针变量名^”的形式引用指针变量（如P^：=0；）。如下图：4．相同基类型的指针变量之间可以进行相互赋值　如有下面的程序段，可以画出右边的示意图：　　varp1,p2:^integer;　　new(p1);new(p2);　　p1^:=90;p2^:=80;　　p1:=p2;5．关系运算　如：ifp1=p2then……　　　whilep<>nildo…

6、…　6．释放动态存储单元　　dispose(指针变量名);（二）单链表的结构、建立、输出　　由于单链表的每个结点都有一个数据域和一个指针域，所以，每个结点都可以定义成一个记录。比如，有如下一个单链表，如何定义这种数据结构呢？typepointer=^nodetype;　　nodetype=record　　　　data:datatype;　　　　next:pointer;{嵌套定义}　　end;varhead,p,q,r:pointer;　　下面给出建立并输出单链表的程序，大家可以把它改成过程用在以后的程序当中。Pr

7、ogramcreat;typepointer=^nodetype;　　nodetype=record　　　data:integer;　　　next:pointer;　　end;var　head,p,r:pointer;{r指向链表的当前最后一个结点，可以称为尾指针}　x:integer;begin　writeln('pleaseinputnum(-1isend):');　read(x);　new(head);{申请头结点}　head:=nil;{头结点初始化}　r:=head;　whilex<>-1do{读入的数非

8、-1}　begin　　new(p);{则，申请一个新结点}　　p^.data:=x;　　p^.next:=nil;　　r^.next:=p;{把新结点链接到前面的链表中，实际上r是p的直接前趋}　　r:=p;{尾指针后移一个}　　read(x);　end;　r^.next:=nil;{最后一个结点的指针域赋空}　readln;　writeln('output