动态数据结构.ppt

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