动态数据结构

动态数据结构第一页，共十三页，编辑于2023年，星期日指针1、引入指针类型的必要性（静态数据结构的弊端）（1）pascal系统为属于静态数据结构的变量提供了64KB的静态数据区，用户需求不能超出该存储空间。（2）静态数据结构的变量一经定义，pascal系统将自动为它们在静态数据区分配内存。在程序执行过程中，这些变量所占的存储空间大小固定不变，极有可能产生无谓的浪费。（3）在静态的数据序列中，增加或删除一个元素必须经过大量的数据移动才能实现。第二页，共十三页，编辑于2023年，星期日指针2、指针类型的定义格式Typepointer=^数据基类型;Varp:pointer;Varp:^数据基类型;数据基类型是指针所指向的存储单元存放的数据类型第三页，共十三页，编辑于2023年，星期日指针3、指针变量的引用Varptr1,ptr2:^integer;i,t:integer;Begini:=10;ptr1^:=i;t:=ptr1^;ptr2^:=20;ptr1^:=ptr2^;ptr1:=ptr2;End.ptr110i10t10ptr22020第四页，共十三页，编辑于2023年，星期日指针4、动态变量的生成和释放（1）生成动态变量New(指针变量)例：new(p)p一个指针变量只能存放一个地址，再次执行new（p）语句，生成新单元，丢失原单元。功能：生成一个类型为指针基类型的存储单元，并将此存储单元的地址赋给指针变量。第五页，共十三页，编辑于2023年，星期日指针4、动态变量的生成和释放例：dispose(p)p功能：释放指针变量所指的存储单元，并使指针变量的值取nil。（2）释放动态变量dispose(指针变量)nilnil表示指针暂不指向任何变量。第六页，共十三页，编辑于2023年，星期日指针的应用——链表结构（1）每个框表示链表的一个元素——结点。（2）每个结点包含两个域：一个放数据，为数据域；另一个存放后继结点的地址，为后继指针域。（3）链表的第一个结点称为表头，指向表头的指针head称为头指针，头指针为nil时，链表为空链表。（4）表尾结点的后继指针域的值为nil。headnil第七页，共十三页，编辑于2023年，星期日指针的应用——链表结构1、单链表的定义结点数据域后继指针域记录类型Typepointer=^element;element=recorddata:integer;next:pointer;end;Varp:pointer;pp^datanextp^.datap^.nextp^.next^第八页，共十三页，编辑于2023年，星期日指针的应用——链表结构2、建立链表ppheadNew(p);Ifn=1thenhead:=pelseq^.next:=p;q:=p;p:指向新建结点q:指向当前结点q循环第九页，共十三页，编辑于2023年，星期日指针的应用——链表结构2、建立链表定义一个建立有n个结点的链表的过程。Procedurecreat(varhead:pointer;varn:integer);BeginHead:=nil;i:=0;While(i<n)doBeginNew(p);i:=i+1;read(p^.data);Ifi=1thenhead:=pelseq^.next:=p;q:=p;End;Ifhead<>nilthenq^.next:=nil;Dispose(p);End.第十页，共十三页，编辑于2023年，星期日指针的应用——链表结构3、链表结点的插入pNew(p);Read(p^.data);p^.next:=q^.next;q^.next:=p;q第十一页，共十三页，编辑于2023年，星期日指针的应用——链表结构4、链表结点的删除q^.next:=p^.next;dispose(p);qp第十二页，共十三页，编辑于2023年，星期日指针的应用——链表结构练习利用随机函数建立