haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

指针的动态变量

发布时间:2014-04-12 13:07:25  

指针的动态变量

1.定义指针类型

在Turbo Pascal中,指针变量中存放的某个存储单元的地址,即指针变量指向某个存储单元。一个指针变量仅能指向某一种类型的存储单元,这种数据类型是在指针类型的定义中确定的,称为指针类型的基类型。指针类型定义如下:

类型名=^基类型名;

例如:type q=^integer;

var a,b,c:q;

说明q是一指向整型存储单元的指针类型,其中"^"为指针符。a,b,c均定义为指针变量,分别可以指向一个整型存储单元。

上例也可定义为:

var a,b,c:^integer;

指针也可以指向有结构的存储单元。

例如:type person=record

name:string[10];

sex:(male,female);

age:20..70

end;

var pt:^person;

pt为指向记录类型person的指针变量。

2.动态变量

应用一个指针指向的动态存储单元即动态变量的形式如下:

指针变量名^

例如:p^、q^、r^

指针变量p和它所指向的动态变量^p之间有如下关系:

P->P'

以下语句把整数5存放到p所指向的动态变量p^ 中去:

p^:=5;

以下语句把p所指向的p^中的值赋给整型变量i:

i:=p^;

如果指针变量p并未指向任何存储单元,则可用下列赋值语句:

p:=nil;

其中nil是Turbo Pascal保留字,表示“空”,相当于C里面的null

10.2 对动态变量的操作

在Turob Pascal程序中,动态变量不能由var直接定义而是通过调用标准过程new建立的。过程形式为:

new(指针变量名);

如果有下列变量定义语句:

var p:^integer;

仅仅说明了p是一个指向整型变量单元的指针变量,但这个整型单元并不存在,在指针变量p中还没有具体的地址值。在程序中必须通过过程调用语句:new(p);才在内存中分配了一个整型变量单元,并把这个单元的地址放在变量p中,一个指针变量只能存放一个地址。在同一时间内一个指针只能指向一个变量单元。当程序再次执行new(p)时,又在内存中新建立了一个整型变量单元,并把新单元的地址存放在p中,从而丢失了旧的变量单元的地址。

为了节省内存空间,对于一些已经不使用的现有动态变量,应该使用标准过程dispose予以释放。过程形式为:dispose(指针变量名);为new(指针变量名)的逆过程,其作用是释放由指针变量所指向的动态变量的存储单元。例如在用了new(p)后在调用dispose(p),则指针p所指向的动态变量被撤销,内存空间还给系统,这时 p的值为 nil。

例:输入两个数,要求先打印大数后打印小数的方式输出,用动态变量做。

program dongtai;

type intepter=^integer;

var p1,p2:intepter;

procedure swap(var,q1,q2:intepter);

var p:integer;

begin

p:=q1;q1:=q2;q2:=p;

end;

begin

new(p1);new(p2);

writeln('input 2 data: ');readln(p1^,p2^);

if p1^ writeln('output 2 data: ',p1^:4,p2^:$);

end.

1 建立链表

链表是动态数据结构的一种基本形式。如果我们把指针所指的一个存贮单元叫做结点,那么链表就是把若干个结点链成了一串。我们把链表叫做动态数据结构,是因为链表中的结点可增可减,可多可少,可在中间任意一个位置插入和删除。

下面就是一个链表:

(图T10.2)

每个链表有两个域,一个是数据域,一个是指向下一个结点的指针域。最后一个结点的指针域为NIL,NIL表示空指针。

要定义一个链表,每个结点要定义成记录型,而且其中有一个域为指针。

TYPE

POINT=↑PP;

PP=RECORD

DATA:STRING[5];

LINK:POINT;

END;

VAR P1,P2:POINT;

在这个定义中,定义了两个指针变量P1,P2。每个结点有两个域,一个是数据域,一个是指针域,数据域是字符串型。这种定义中,指针中有记录,记录中有指针,形成一种递归调用。

下面我们来看一下如何定义上图的链表:

有:P1,P2,P3,P4属于POINT类型。

(1)建立第一个结点

NEW(P1);

P1↑.DATA:=D1;

(2) 建立第二个结点,并把它接在P1的后面

NEW(P2);

P2↑.DATA:=D2;

P1↑.LINK:=P2;

(3) 建立第三个结点,并把它接在P2的后面.

NEW(P3);

P3↑.DATA:=D3;

P2↑.LINK:=P3;

(4) 建立最后一个结点,并把它接在P3的后面. NEW(P4);

P4↑.DATA:=D4;

P4↑.LINK:=NIL;

P3↑.LINK:=P4;

例1 建立一个有10个结点的链表,最后输出该链表。 P2前一个结点,K一直指向第一个结点。

PROGRAM E1(INPUT,OUTPUT);

TYPE point=^pp;

pp=record

data:string[5];

link:point;

end;

VAR

p1,p2,k:point;

i:integer;

BEGIN

{产生新结点P1,作为链表的头}

new(p1);

writeln('input data');

readln(p1^.data);

{指针K指向链表头}

k:=p1;

{用循环产生9个新结点,每个结点都接在上一个结点之后} for i:=1 to 9 do

begin

new(p2);

writeln('input data');

readln(p2^.data);

p1^.link:=p2;

p1:=p2;

end;

{给最后一个结点的LINK域赋空值NIL}

p2^.link:=nil;

{从链表头开始依次输出链表中的DATA域}

while k^.link<>nil do

begin

write(k^.data,'->');

k:=k^.link;

end;

END.

在本程序里,输出链表的过程就是一个链表的遍历。给出一个链表的头结点,依次输出后面每一个结点的内容,指针依次向后走的语句用K:=K↑.LINK 来实现。

例2 读入一批数据,遇负数时停止,将读入的正数组成先进先出的链表并输出。

分析:首先应定义指针类型,结点类型和指针变量,读入第一个值,建立首结点,读入第二个值,判断它是否大于零,若是,建立新结点。

PROGRAM fifo(input,output);

{建立先进先出链表}

TYPE

Point=^node;

Node=RECORD

Data:real;

Link:point

END;

VAR

head,last,next:point;

x:real;

BEGIN

{读入第一个值,建立首结点}

read(x);

write(x:6:1);

new(head);

head^.data:=x;

last:=head;

{读入第二个值}

read(x);

write(x:6:1);

WHILE x>=0 DO

BEGIN

{建立新结点}

new(next);

next^.data:=x; {链接到表尾} last^.link:=next; {指针下移} last:=next; {读入下一个值} read(x);

write(x:6:1)

END;

Writeln; {表尾指针域置NIL} Last^.link:=NIL; {输出链表} Next:=head;

WHILE next<>NIL DO BEGIN

Write(next^.data:6:1);

Next:=next^.link

END;

Writeln

END.

例3 读入一批数据,遇负数时停止,将读入的正数组成先进后出的链表并输出。

PROGRAM fifo(input,output);

{建立先进后出链表}

TYPE

point=^node;

node=RECORD

data:real;

link:point

END;

VAR

head,last,next:point;

x:real;

BEGIN

{初始准备}

next:=NIL;

read(x); {读入第一个数}

write(x:6:1);

WHILE x>=0 DO

BEGIN {建立一个新结点}

new(head);

head^.data:=x; {链接到表首}

head^.link:=next;{指针前移}

next:=head; {读入下一个数}

read(x);

write(x:6:1)

END;

writeln; {输出链表}

WHILE next<>NIL DO

BEGIN

write(next^.data:6:1);

next:=next^.link

END;

writeln

END.

2 在链表中插入结点

在一个已建好的链表中插入一个结点,这是一种常见算法。当我们找到插入点后,就断开原先的链接,将新结点插入进来。

(图T10.3)

如图所求示:要把P3的结点插入到P2之前,应该这样操作:

(1) P1,P2之间的链断开,改为P1指向P3。 P1↑.LINK:=P3;

(2) 将P2,P3连接起来:

P3↑.LINK:=P2;

于是,P3所指向的结点便插入进来了。

例4 插入一结点的过程

PROCEDURE insert(x:real;VAR head:point);

{插入一结点的过程}

VAR

q,last,next:point;

BEGIN

{建立新结点}

new(q);

q^.data:=x;

IF X<=head^.ata

THEN {插入前表}

BEGIN

q^.link:=head;

head:=q;

EDN

ELSE BEGIN {找出表中合适的位置}

Next:=head;

WHILE (x>next^.data) AND (next^.link<>NIL) DO

BEGIN

Last:=next;

Next:=next^.link

END;

IF x<=next^.data

THEN {插入中间表}

BEGIN

last^.link:=q;

q^.link:=next

END

ELSE {插入表尾}

BEGIN

next^.link:=q;

q^.link:=NIL

END

END

END;

例5 建立一个有序的整数链表,再将一任意整数插入进链表,使链表仍然有序。

PROGRAM e1(input,output);

TYPE point=^pp;

pp=record

data:integer;

link:point;

end;

VAR

p1,p2,p3,k:point;

BEGIN

{建立一个整数的链表,要求输入的整数依次是有序的,以数9999结束}

new(p1);

writeln('input data');

readln(p1^.data);

k:=p1;

repeat

new(p2);

writeln('input data');

readln(p2^.data);

p1^.link:=p2;

p1:=p2;

until p2^.data=9999;

p2^.link:=nil;{有序链表建立完毕}

writeln('input p3');

readln(p3^.data);

p1:=k;p2:=k;{P1,P2都指向表头}

{P2找到插入点后一个结点}

while p2^.data<p3^.data do

p2:=p2^.link;

{P1找到插入点以前的结点}

while p1^.link<>p2 do

p1:=p1^.link;

{将P3接入P1,P2之间}

p1^.link:=p3;

p3^.link:=p2;

{将整个插入后的链表依次打印出来}

repeat

write(k^.data,'->');

k:=k^.link;

until k^.data=9999;

write(k^.data);

END.

3 删除一个结点

要在一个链表中删去一个结点,首先在链表中找到该结点,将其前面的指针与该点断开,直接接到后面的结点,再用DISPOSE 命令将P3结点空间释放。如图,删除P3结点:

(图T10.4)

删除语句如下:

P1↑.LINK:=P3↑.LINK

DISPOSE(P3);

例6 删除结点的过程

PROCEDURE delete(x:real;VAR head;point;VAR deleted:Boolean); {删除结点的过程}

VAR

Last,next:point;

BEGIN

{遍历表直到找到目标或到达表末}

next:=head;

WHILE(next^.data<>x)AND(next^.link<>DIL) DO

BEGIN

Last:=next;

Next:next^.link

END;

{如果目标文件找到,删除包含它的结点,设置deleted}

IF next^.data=x

THEN BEGIN

Deleted:=true;

IF next=head

THEN head:=head^.link

ELSE last^.link:=next^.link

END

ELSE deleted:=false

END;

例7 在一个有序链表中装有1到100共100个整数。要求任意输入100以内的一个整数,把它从链表中删除。

PROGRAM e1(input,output);

TYPE point=^pp;

pp=record

data:integer;

link:point;

end;

VAR

p1,p2,p3,k:point;

i:integer;

BEGIN

{建立一个1――100的整数的有序链表}

new(p1);

k:=p1;

p1^.data:=1;

for i:=2 to 100 do

begin

new(p2);

p2^.data:=i;

p1^.link:=p2;

p1:=p2;

end;

p2^.link:=nil;

{输入要删除的结点的DATA值}

new(p3);

writeln('input p3');

readln(p3^.data);

P1:=k;p2:=k;

{P2指针查找P3结点}

while p2^.data<p3^.data do

p2:=p2^.link;

{P1指针定位于P3之前}

while p1^.link<>p2 do

p1:=p1^.link;

p1^.link:=p2^.link;

dispose(p3);{将P3结点的空间释放} {输出修改后的链表}

repeat

write(k^.data,'->'); k:=k^.link;

until k^.data=100;

write(k^.data);

END.

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com