动态数据结构.ppt

指 针,1、引入指针类型的必要性（静态数据结构的弊端）,（1）pascal系统为属于静态数据结构的变量提供了64KB的静态数据区，用户需求不能超出该存储空间。,（2）静态数据结构的变量一经定义，pascal系统将自动为它们在静态数据区分配内存。在程序执行过程中，这些变量所占的存储空间大小固定不变，极有可能产生无谓的浪费。,（3）在静态的数据序列中，增加或删除一个元素必须经过大量的数据移动才能实现。,指 针,2、指针类型的定义格式,Typepointer=数据基类型;Varp:pointer;,Varp:数据基类型;,数据基类型是指针所指向的存储单元存放的数据类型,指 针,3、指针变量的引用,Varptr1,ptr2:integer;i,t:integer;Begini:=10;ptr1:=i;t:=ptr1;ptr2:=20;ptr1:=ptr2;ptr1:=ptr2;End.,ptr1,10,i,10,t,10,ptr2,20,20,指 针,4、动态变量的生成和释放,（1）生成动态变量,New(指针变量),例：new(p),p,一个指针变量只能存放一个地址，再次执行new（p）语句，生成新单元，丢失原单元。,功能：生成一个类型为指针基类型的存储单元，并将此存储单元的地址赋给指针变量。,指 针,4、动态变量的生成和释放,例：dispose(p),p,功能：释放指针变量所指的存储单元，并使指针变量的值取nil。,（2）释放动态变量,dispose(指针变量),nil,nil表示指针暂不指向任何变量。,指针的应用链表结构,（1）每个框表示链表的一个元素结点。,（2）每个结点包含两个域：一个放数据，为数据域；另一个存放后继结点的地址，为后继指针域。,（3）链表的第一个结点称为表头，指向表头的指针head称为头指针，头指针为nil时，链表为空链表。,（4）表尾结点的后继指针域的值为nil。,head,nil,指针的应用链表结构,1、单链表的定义,结点,数据域,后继指针域,记录类型,Typepointer=element;element=record data:integer;next:pointer;end;,Varp:pointer;,p,p,data,next,p.data,p.next,p.next,指针的应用链表结构,2、建立链表,p,p,head,New(p);If n=1 then head:=p else q.next:=p;q:=p;,p:指向新建结点 q:指向当前结点,q,循环,指针的应用链表结构,2、建立链表,定义一个建立有n个结点的链表的过程。,Procedure creat(var head:pointer;var n:integer);BeginHead:=nil;i:=0;While(inil then q.next:=nil;Dispose(p);End.,指针的应用链表结构,3、链表结点的插入,p,New(p);Read(p.data);p.next:=q.next;q.next:=p;,q,指针的应用链表结构,4、链表结点的删除,q.next:=p.next;dispose(p);,q,p,指针的应用链表结构,练习,利用随机函数建立一个具有50个结点的链表，每个结点中的数值为0至100之间的整数。打印链表中每个结点的值；再删除链表中具有偶数值的那些结点，并把删除后的链表打印出来。,