動態(tài)數(shù)據(jù)結構

動態(tài)數(shù)據(jù)結構第1頁，課件共13頁，創(chuàng)作于2023年2月指針1、引入指針類型的必要性（靜態(tài)數(shù)據(jù)結構的弊端）（1）pascal系統(tǒng)為屬于靜態(tài)數(shù)據(jù)結構的變量提供了64KB的靜態(tài)數(shù)據(jù)區(qū)，用戶需求不能超出該存儲空間。（2）靜態(tài)數(shù)據(jù)結構的變量一經(jīng)定義，pascal系統(tǒng)將自動為它們在靜態(tài)數(shù)據(jù)區(qū)分配內(nèi)存。在程序執(zhí)行過程中，這些變量所占的存儲空間大小固定不變，極有可能產(chǎn)生無謂的浪費。（3）在靜態(tài)的數(shù)據(jù)序列中，增加或刪除一個元素必須經(jīng)過大量的數(shù)據(jù)移動才能實現(xiàn)。第2頁，課件共13頁，創(chuàng)作于2023年2月指針2、指針類型的定義格式Typepointer=^數(shù)據(jù)基類型;Varp:pointer;Varp:^數(shù)據(jù)基類型;數(shù)據(jù)基類型是指針所指向的存儲單元存放的數(shù)據(jù)類型第3頁，課件共13頁，創(chuàng)作于2023年2月指針3、指針變量的引用Varptr1,ptr2:^integer;i,t:integer;Begini:=10;ptr1^:=i;t:=ptr1^;ptr2^:=20;ptr1^:=ptr2^;ptr1:=ptr2;End.ptr110i10t10ptr22020第4頁，課件共13頁，創(chuàng)作于2023年2月指針4、動態(tài)變量的生成和釋放（1）生成動態(tài)變量New(指針變量)例：new(p)p一個指針變量只能存放一個地址，再次執(zhí)行new（p）語句，生成新單元，丟失原單元。功能：生成一個類型為指針基類型的存儲單元，并將此存儲單元的地址賦給指針變量。第5頁，課件共13頁，創(chuàng)作于2023年2月指針4、動態(tài)變量的生成和釋放例：dispose(p)p功能：釋放指針變量所指的存儲單元，并使指針變量的值取nil。（2）釋放動態(tài)變量dispose(指針變量)nilnil表示指針暫不指向任何變量。第6頁，課件共13頁，創(chuàng)作于2023年2月指針的應用——鏈表結構（1）每個框表示鏈表的一個元素——結點。（2）每個結點包含兩個域：一個放數(shù)據(jù)，為數(shù)據(jù)域；另一個存放后繼結點的地址，為后繼指針域。（3）鏈表的第一個結點稱為表頭，指向表頭的指針head稱為頭指針，頭指針為nil時，鏈表為空鏈表。（4）表尾結點的后繼指針域的值為nil。headnil第7頁，課件共13頁，創(chuàng)作于2023年2月指針的應用——鏈表結構1、單鏈表的定義結點數(shù)據(jù)域后繼指針域記錄類型Typepointer=^element;element=recorddata:integer;next:pointer;end;Varp:pointer;pp^datanextp^.datap^.nextp^.next^第8頁，課件共13頁，創(chuàng)作于2023年2月指針的應用——鏈表結構2、建立鏈表ppheadNew(p);Ifn=1thenhead:=pelseq^.next:=p;q:=p;p:指向新建結點q:指向當前結點q循環(huán)第9頁，課件共13頁，創(chuàng)作于2023年2月指針的應用——鏈表結構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.第10頁，課件共13頁，創(chuàng)作于2023年2月指針的應用——鏈表結構3、鏈表結點的插入pNew(p);Read(p^.data);p^.next:=q^.next;q^.next:=p;q第11頁，課件共13頁，創(chuàng)作于2023年2月指針的應用——鏈表結構4、鏈表結點的刪除q^.next:=p^.next;dispose(p);qp第12頁，課件共13頁，創(chuàng)作于2023年2月指針的應用——鏈表結構練習利用隨機函數(shù)建立