第二章指针与链表

1、第二章指针与链表一、静态存贮和动态存贮1、静态存贮程序中的变量一经说明，计算机操作系统就会在内存空间中分配相应的存贮单元，其中变量名是存贮单元的地址，而变量的值是存贮单元的内容，且该存贮单元自始至终都被该变量所占用，直到程序结束。如果变量是局部变量，那么在它的作用域内，一经说明也占有一定的存贮单元，直到退出其作用域为止。这样的变量，在程序执行过程中，不能随时使用随时分配存贮空间，也不能在程序执行的过程中，释放这些空间。也就是说，一旦给这些变量分配存贮空间，无论程序是否还需要使用，它们都要占用一定的存贮空间，以便给用户存贮数据。我们称具有这样特点的存贮为静态存贮，它所对应的变量称为静态变量。如字

2、符类型、数组类型、记录类型等。这类变量的优点是存贮方便，查找容易，可以通过一个简单的公式随机存取表中的任一元素，逻辑关系上相邻的两个元素在物理位置上也是相邻的，很容易找到前趋与后继元素；缺点是在线性表的长度不确定时，必须分配足够大的存储空间，经常浪费了宝贵的存储资源；而线性表的容量一经定义确定后就难以扩充；在插入和删除线性表的元素时，需要移动大量的元素，时间效率也比较差。2、动态存贮在程序执行过程中，通过向操作系统申请存贮空间或释放存贮空间的命令，达到动态管理计算机的存贮空间，以保证存贮空间的充分利用。存贮空间可以随时申请、随时释放，这样的存贮方式称为动态存贮，其变量称为动态变量。指针变量即为

3、动态变量。动态存储所需要的空间可以是不连续的，这样有利于充分利用零散的小空间。但缺无法用o（1）的时间实现存取了。如何用这些零散的空间存储数组这些大规模数据呢？如何表示这些数据之间的逻辑关系呢？为了表示这些物理存储单元之间的逻辑关系，对于每个数据元素来说，除了要存储它本身的信息（数据域data）外，还要存储它的直接后继元素的存储位置（指针域，一般用link 或 next 表示） 。我们往往把这两部分信息合在一起称为一个“结点node” 。 n 个结点链接在一起就构成了一个链表。n=0 时，称为空链表。同时，为了按照逻辑顺序对链表中的元素进行各种操作，我们需要定义一个变量用来存储整个链表的第一个

4、结点的物理位置，这个变量称为“头指针，一般用h 或 head 表示”。也可以把头指针定义成一个结点，称为“头结点”，头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头结点的指针域（头指针）存储指向第一个结点的指针，若线性表为空表，则头结点的指针域为空（ nil） 。由于最后一个元素没有后继，所以线性表中最后一个结点的指针域为空（nil） 。由于此链表中的每个结点都只包含一个指针域，故称为“线性链表或单向链表”。二、指针类型与指针变量1指针类型和指针变量的说明type指针类型标识符= 基类型名；基类型不能为文件类型var 指针变量名：指针类型标识符；2申请存储单元动态申请、空

5、间大小由指针变量的基类型决定new(指针变量名 )；pascal 标准过程 3指针变量的赋值指针变量名：=nil；初始化，暂时不指向任何存储单元如何表示和操作指针变量？不同于简单变量（如a：=0； ） ，pascal 规定用“指针变量名”的形式引用指针变量（如p：=0； ） 。区分如下图所示：如计算机执行下面的程序段时：new（h） ；h:=123；new（h） ；h:=234;内存示意图如图所示（阴影部分表示该单元已被占）：4相同基类型的指针变量之间可以进行相互赋值。如有下面的程序段，可以画出右边的示意图：varp1,p2:integer;new(p1);new(p2);p1:=90;p2:

6、=80;p1:=p2;5关系运算如：ifp1=p2thenwhilep nildo 6释放动态存储单元dispose( 指针变量名 );系统收回指针变量所指的内存单元另作它用，此时指针变量的值变成无定义。注意，我们应该养成一个好的习惯，就是及时释放不用的动态存储单元，很多同学使用指针变量时就知道new(p) ，而不知道及时dispose(p)，最后造成内存空间溢出错误、出现死循环甚至死机现象。三、单向链表1、单向链表的结构由于单向链表的每个结点都有一个数据域和一个指针域，所以，每个结点都可以定义成一个记录。一般，把 head 称为头结点， head.next 称为头指针。比如，有如下一个单向链

7、表，如何定义这种数据结构呢？方法如下：type pointer=nodetype;nodetype=recorddata:datatype;next:pointer;嵌套定义 end;var head,p,q,r:pointer;2、单链表的建立、输出下面结合一个例子，给出建立并输出单向链表的程序。例 1、从键盘输入若干个正整数，请按输入顺序建立一个单向链表并输出它，输入-1 时表示结束。program creat;type pointer=nodetype;nodetype=recorddata:integer;next:pointer;end;var head,p,r:pointer;r

8、指向链表的当前最后一个结点，可以称为尾指针x:integer;beginwriteln(please input num(-1 is end):);read(x);new(head);申请头结点 head.next:=nil;头结点初始化 r:=head;while x-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:

9、);输出p:=head.next;头指针没有数据，只要从第一个结点开始就可以了while p.nextnil dobeginwrite(p.data:4);p:=p.next;end;write(p.data:4);最后一个结点的数据单独输出，也可以改用repeat 循环 readln;end.为了充分利用空间和随时统计出链表的实际结点个数，我们经常把链表的实际结点个数存入到头结点的数据域（head.data ）中，请大家改写上面的程序，并输出最后的结点个数。3、查找“数据域满足一定条件的结点”（1）从前往后找到第一个满足条件的结点,程序如下：p:=headnext;while(p.data

10、x) and(p.nextnil)do p:=p.next;找到第一个就结束ifp.data= xthen找到了处理else输出不存在；（2）如果想找到所有满足条件的结点，则修改如下：p:=headnext;whilep.nextnildo一个一个判断 beginifp.data = xthen找到一个处理一个；p:=p.next;end;4、获取第i 个结点的数据域functionget(head:pointer;i:integer):integer;var p:pointer;j:integer;beginp:=head.next;j:=1;while(pnil) and (ji) dob

11、eginp:=p.next; j:=j+1;end;if(p nil)and(j=i)thenwriteln(p.data)elsewriteln(inot exsit! );end;5、插入一个结点到单链表中一般情况： s.next:=p.next;p.next:=s;特殊情况，插在表头：s.next:=head;head:=s;插在表尾（假设p 已是表尾）：p.next:=s;p:=s;程序实现时，从表头开始找，是一致的。procedureinsert(head:pointer;i:integer;x:integer);插入 x 到第 i 个元素之前 varp,s:pointer;j:in

12、teger;beginp:=head;j:=0;while(pnil) and (ji-1)thenwriteln( nothis position!)elsebegin插入 new(s);s.data:=x;s.next:=p.next;p.next:=s;end;end;6、删除单向链表中的第i 个结点（如下图中数据域为“b”的结点）proceduredelete(head:pointer;i:integer;);删除第 i 个元素 varp,s:pointer;j:integer;beginp:=head;j:=0;while(p.nextnil) and (ji-1)thenwrite

13、ln( nothis position!)elsebegin删除 p 的后继结点，假设为ss:=p.next;p.next:=p.next.next;或 p.next:=s.nextdispose(s);end;end;7、求单向链表的实际长度functionlen(head:pointer):integer;var n:integer;beginp:=head;n:=0;whilep nildobeginn:=n+1;p:=p.next;end;len:=n;end;四、双向链表每个结点有两个指针域和若干数据域，其中一个指针域指向它的直接前趋结点，一个指向它的直接后继结点。它的优点是访问、插

14、入、删除更方便，速度也快了。实质上是以空间换时间。数据结构的定义：type pointer=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

15、) and (ji) dobeginp:=p.next;j:=j+1;end;p 指向第 i 个结点 if p=nil then writeln( nothis position!)elsebegin将结点 s 插入到结点p之前 s.pre:=p.pre;1、将 s 的前趋指向p 的前趋 p.pre:=s;2、将 s 作为 p 的新前趋 s.next:=p;3、将 s的后继指向ps.pre.next:=s;4、将 p 的本来前趋结点的后继指向send;end;proceduredelete(head:pointer;i:integer);删除双向链表的第i 个结点 varp:pointer;j

16、:integer;beginp:=head;j:=0;while(p.nextnil) and (ji) dobeginp:=p.next;j:=j+1;end;p 指向第 i 个结点 if p=nil then writeln( nothis position!)elsebegin将结点 p 删除 p.prenext:=p.next;1、p 的前趋结点的后继赋值为p的后继 p.next.pre:=p.pre;2、p 的后继结点的前趋赋值为p的前趋 end;end;五、循环链表1、单向循环链表：最后一个结点的指针指向头结点。如下图：2、双向循环链表：最后一个结点的后继指针指向头结点，且头结点的

17、前趋指针指向最后一个结点。如下图：六、循环链表的应用举例例 2、约瑟夫问题【问题描述】有 n 只猴子，按顺时针方向围成一圈（开始时编号为1，2， n） ，选大王。从第1 号猴子开始报数1，2， 3，数到m 号时该猴子退出到圈外，如此报数直到圈内只剩下一只猴子时，此猴便是大王。你的任务是从键盘读入n,m，程序判断输出最后的大王是几号？如输入： 135输出： 6换个问法：n 只猴子围成一个圈，按顺时针方向报数，报到m 的出圈，直到剩下一只猴子结束。输出猴子依次出圈的序号。【算法分析】很明显这是一个单向循环链表。数据域为猴子的编号，指针域为下一个猴子的地址。从第1 个猴子开始一一报数，报数实际上是计

18、数，只要设一个计数器就可以了。当计数器由1 变化到 m 时，删除该结点，从下一个结点开始继续计数（计数器回1 或者用求余运算） 。直到链表中只剩下一个结点。【参考程序】program king;typepoint=node;node=recorddata:integer;next:point;end;varm,n,s:integer;p,q,head:point;beginwrite(input n,m:); readln(n,m);new(head);q:=head;head.data:=1;for s:=2to n dobeginnew(p);p.data:=s;q.next:=p;q:=

19、p;end;q.next:=head; s:=1;q:=head;repeatp:=q.next;s:=s+1;if smod m=0 then beginq.next:=p.next;writeln(p.data:4);dispose(p);endelse q:=puntil q.next=q;writeln(the king is:,q.data)end.七、线性表的综合应用【例 3】用单向链表实现线性表的归并操作问题描述 已知线性表l1 和 l2 中的数据元素按值非递减有序排列，现要求将l1 和 l2 归并成一个新的线性表 l3，使 l3 中的数据元素仍按非递减有序排列。例如：l1=（1

20、，3，4，5，8，9，10，11，12） ，l2=（2 ，4， 6， 8） ，则 l3=（ 1，2，3，4，4，5，6， 8，8，9，10，11，12） 。注意：相同元素照算。标准过程 proceduremerge(h1,h2:pointer;varh3:pointer);将头指针分别为h1,h2 的两个单链表归并成一个新的单链表，该链表头指针为h3varp1,p2,p3:pointer;临时用工作指针，一般不能破坏头指针beginp1:=h1.next;p2:=h2.next;h3:=h1;新链表共用第一个链表，简化，也可以另外开辟一个头结点p3:=h3;while(p1nil)and (p

21、2nil)do归并beginifp1.data=p2.datathenbegin将 p1 结点链接到p3 中去p3.next:=p1;指向p3:=p1;p3 后移p1:=p1.nextp1 后移endelsebegin将 p2 结点链接到p3 中去p3.next:=p2;p3:=p2;p2:=p2.nextend;end;ifp1nilthenp3.next:=p1将 p1 中剩下的结点一起链接到p3 中elsep3.next:=p2;将 p2 中剩下的结点一起链接到p3 中end;2一元多相式的表示和加减运算问题描述 在数学上，一个一元n 次多项式pn(x) ，可以按升幂写成：pn(x)=p

22、0 + p1x + p2x2+ p3x3+pnxn它由 n+1 个系数唯一确定。因此，在计算机里，它可以用一个线性表p来表示：p = （p0，p1，p2， pn）每一项的指数i 隐含在系数pi 的序号里。【任务】输入两行，每行为一个字符串，分别表示一个一元n 次多项式pn(x)和一个一元m次多项式qm(x)，输出它们的和。注意：不许输出系数为0 的项、不要输出为1 的系数和幂，且按幂的升序输出。【输入输 出样例】输入 ：3x2+8-5x6+x6x6+5x-3x2+8x9-20输 出： -12+6x+x6+8x9【数据结构】方法 1：按 n,m 分别生成 n+1 和m+1 个结点的 两个单 链表，即不 管 系数是 否为0 都生成一个结点。一个指针域指 向后继 结点，一个数据域存放 系数（不存在的项系数为0）。浪费 了很多空 间，尤其 是指数很高 ，而项数 很少 的 情况 下， 浪费 更 严重。方法 2