指针类型

(共24张PPT)
存储空间的分配
Var x,y:integer; Begin
x:=4; y:=5;
End.
编译时给变量分配空间
运行时给变量赋值　　　　　　
x
1000H
y
4000H
4
5
思考：变量x，y的关系？
存储空间的分配
Var a:array [1..10] of integer; i:integer;
Begin
for i:=1 to 10 do
a[i]:=i;
End.
1000H
1002H
1004H
1006H
1008H
1010H
1012H
1014H
1016H
1018H
1
2
3
4
5
6
7
8
9
10
a
思考：数组a[i]之间的关系？
指针类型格式：
TYPE
<指针类型标识符> = ^ <结点类型标识符>;
<结点类型标识符> = <类型>
VAR
<指针类型变量表> : <指针类型标识符>;
或
VAR
<指针类型变量表> : ^ <结点类型标识符>;
①结点类型为整型
type pointer=^integer; var p1,p2:pointer;
②结点类型为整型
var a:^real; b:^boolean;
③结点类型为记录型
type person=record 　　　　　　 name:string[10]; 　　　　　　 sex:char; 　　　　　　 age:1..100 　　　　　 end; var p:^person;
编写一个简单的指针类型的程序
Type person=record 　　　　　　 name:string[10]; 　　　　　　 sex:char; 　　　　　　 age:1..100 　　　　　 end; Var p:^person;
Begin
new(p);
p^.name:=‘Peter’; p^.sex:=‘M’; p^.age:=20;
with p^ do
writeln(name:10, sex:10, age:10);
dispose(p)
End.
1、开辟动态存储单元
new过程调用的一般格式: 　new (指针变量) 功能：开辟一个存储单元，并把此存储单元的地址赋给指针变量。
var p: ^ integer;
编译时给 p分配空间 　　　 　　　　　　　
p
p
XXXX
执行new(p)后生成新单元
新单元的地址为XXXX
new(p);
2、释放动态存储单元
dispose过程的一般格式:
dispose (指针变量) 功能：释放指针所指向的存储单元，使指针变量的值无定义。
dispose(p);
p:=NIL
3、动态存储单元的引用
引用动态存储单元一般格式：
＜指针变量＞^
var p:^integer; i:integer; begin
new(p); p^:=4;i:=p^;
①编译时分配存储空间
②执行new语句
③p^:=4
④i:=p^
？
？
p
i
？
？
p
i
？
p^
？
？
p
i
4
p^
？
4
p
i
4
p^
program point1(input,output);
type pointer =^ integer;
var a,b,c:pointer;
begin
new(a); new(b); new(c);
a^:=5; b^:=8;
writeln(‘a=’, a^, ‘ b=’, b^)
c:=a; a:=b; b:=c;
writeln(‘a=’, a^, ‘ b=’, b^)
end.
例1 用指针变量交换两个变量的值 。
program ch346; {初赛篇P157例46}
type pointer : ^ integer;
var p1,p2:pointer;
begin
new(p1);
p1^:=5;
p2:=p1;
new(p1);
p1^:=5;
if p1=p2
then writeln(‘p1=p2’)
else writeln(‘p1<>p2’)
if p1^=p2^
then writeln(‘p1^=p2^)
else writeln(‘p1^<>p2^)
writeln(s)
end.
运行结果：
p1<>p2
p1^=p2^
单向链表 (设输入次序为x1,x2,…,xn)
先进先出队
先进后出栈
x2
…
head
x3
x1
x9
x10
x9
…
head
x8
x10
x2
x1
指针类型格式：
TYPE
<指针类型标识符> = ^ <结点类型标识符>;
<结点类型标识符> = <类型>
VAR
<指针类型变量表> : <指针类型标识符>;
或
VAR
<指针类型变量表> : ^ <结点类型标识符>;
单向链表定义
TYPE
point = ^ node
node = RECORD
data : real ;
link : point
END;
VAR
head, last, next : point ; x:real ;
构建链表（先进先出）
Var
head, last, next : point ; x:real ;
Begin
read(x) ;
new(head) ; head^.data:=x ;
last:=head ;
read(x) ;
while x>=0 do
begin
new(next) ;
next^.data:=x;
last^.link:=next ;
last:=next ;
read(x)
end ;
last^.link:=NIL
End.
输出链表
next:=head ;
while next<>NIL do
begin
write(next^.data:6:0);
next:=next^.link
end ;
writeln
删除一个结点
last
next
last
next
last^.link:=next^.link;
dispose(next);
Procedure delete(x:real; VAR head:point; VAR
deleted:boolean);
Var
last, next : point ;
Begin
next:=head ;
while (next^.data<>x) and (next^.link<>NIL) do
begin
last:=next ;
next:=next ^.link;
end ;
if next^.data=x
then begin
deleted:=true;
if next=head
then head:=head^.link
else last^.link:=next^.link ;
dispose(next)
end
else deleted:=false
End.
插入一个结点
last
next
last^.link:=q;
q^.link:=next;
q
last
next
插入一个结点
head
q
{表头插入}
next
q
{表尾插入}
{表间插入}
next
q
last
在一有序链表中插入一个新的结点，使插入以后仍然有序。
Procedure insert (x:real; VAR head:point) ;
Var
q, last, next : point ;
Begin
new(q); q^.data:=x;
if x<=head^.data
then begin {插入表前}
q^.link:=head;
head:=q
end
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.
建立有序链表
Procedure createorder (VAR head:point) ;
Var x : real ;
Begin
read(x);
new(head);
head^.data:=x; head^.link:=NIL;
read(x)
while x>=0 do
begin
insert (x, head) ;
read(x)
end
End.
栈（先进后出）
1、设栈的输入序列是（1、2、3、4），则（ ）不可能是其出栈序列。
A. 1243 B. 2134 C. 1432
D. 4312 E. 3214
指针类型作业：P257
11.1
11.2
11.3