动态数据结构

1、动态数据结构第1页，共13页，2022年，5月20日，15点11分，星期一指 针1、引入指针类型的必要性（静态数据结构的弊端）（1）pascal系统为属于静态数据结构的变量提供了64KB的静态数据区，用户需求不能超出该存储空间。（2）静态数据结构的变量一经定义，pascal系统将自动为它们在静态数据区分配内存。在程序执行过程中，这些变量所占的存储空间大小固定不变，极有可能产生无谓的浪费。（3）在静态的数据序列中，增加或删除一个元素必须经过大量的数据移动才能实现。第2页，共13页，2022年，5月20日，15点11分，星期一指 针2、指针类型的定义格式Typepointer=数据基类型;Varp

2、:pointer;Varp: 数据基类型;数据基类型是指针所指向的存储单元存放的数据类型第3页，共13页，2022年，5月20日，15点11分，星期一指 针3、指针变量的引用Varptr1,ptr2: integer;i,t:integer;Begini:=10; ptr1:=i; t:=ptr1;ptr2:=20; ptr1:=ptr2;ptr1:=ptr2;End.ptr110i10t10ptr22020第4页，共13页，2022年，5月20日，15点11分，星期一指 针4、动态变量的生成和释放（1）生成动态变量New(指针变量)例：new(p)p一个指针变量只能存放一个地址，再次执行ne

3、w（p）语句，生成新单元，丢失原单元。功能：生成一个类型为指针基类型的存储单元，并将此存储单元的地址赋给指针变量。第5页，共13页，2022年，5月20日，15点11分，星期一指 针4、动态变量的生成和释放例：dispose(p)p功能：释放指针变量所指的存储单元，并使指针变量的值取nil。（2）释放动态变量dispose(指针变量)nilnil表示指针暂不指向任何变量。第6页，共13页，2022年，5月20日，15点11分，星期一指针的应用链表结构（1）每个框表示链表的一个元素结点。（2）每个结点包含两个域：一个放数据，为数据域；另一个存放后继结点的地址，为后继指针域。（3）链表的第一个结点

4、称为表头，指向表头的指针head称为头指针，头指针为nil时，链表为空链表。（4）表尾结点的后继指针域的值为nil。headnil第7页，共13页，2022年，5月20日，15点11分，星期一指针的应用链表结构1、单链表的定义结点数据域后继指针域记录类型Typepointer=element;element=record data:integer; next:pointer; end;Varp:pointer;ppdatanextp.datap.nextp.next第8页，共13页，2022年，5月20日，15点11分，星期一指针的应用链表结构2、建立链表ppheadNew (p);If n=

5、1 then head:=p else q.next:=p;q:=p;p:指向新建结点 q:指向当前结点q循环第9页，共13页，2022年，5月20日，15点11分，星期一指针的应用链表结构2、建立链表定义一个建立有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页，2022年，5月20日，15点11分，星期一指针的应用链表结构3、链表结点的插入pNew (p);Read(p.data);p.next:=q.next;q.next:=p;q第11页，共13页，2022年，5月20日，15点11分，星期一指针的应用链表结构4、链表结点的删除q.next:=p.next;dispose(p);qp第12页，共13页，2022年，5月20日，15点11分，星期一指针的应用链表结构练习利用随机函数建立一个具有50个结点的链表，每个