动态数据结构优秀PPT.ppt

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