復(fù)習(xí)一、靜態(tài)存儲與動態(tài)存儲：1、簡單變量：4個標(biāo)準(zhǔn)類型、子界、枚舉類型2、構(gòu)造型變量：數(shù)組、集合、記錄、文件共同特點：經(jīng)過變量說明，留下相應(yīng)存儲空間。程序中不能改變變量定義的個數(shù)。3、動態(tài)存儲結(jié)構(gòu)：可以根據(jù)程序運行時的需要，隨時申請存儲空間。其存儲空間的大小，根據(jù)用戶的定義的類型，計算機(jī)給予相應(yīng)空間——指針類型二、動態(tài)存儲結(jié)構(gòu)：指針類型，特殊的類型1、定義方法：Type標(biāo)識符=^基本類型；typepoint=＾integer;chx=＾char;varp1,p2:point;c1,c2:chx;3、指針類型的作用：這是一種特殊的數(shù)據(jù)類型，該類型的變量的內(nèi)容是地址而其它類型變量則是：X=35X變量名——地址35變量的值——存儲內(nèi)容

p1,p2——指針類型變量，它通過一個過程（new）向計算機(jī)申請內(nèi)存地址

指針變量所指向的類型不同，計算機(jī)所給予的存儲單元的多少也不相同。

p1,p2得到單元為兩個字節(jié)，c1,c2則每個變量得到單元為一個字節(jié)。4、指針變量的使用方法：（1）申請存儲單元地址的操作：new(p1),new(p2)（2）歸還存儲單元的操作：dispose(p1),dispose(p2)5、指針變量類型定義的特殊性：（1）可以先使用后定義（2）可以遞歸定義例如：

ttttt=＾stu;stu=recordname:string[10];number:integer;end;vart1,t2:ttttt;beginnew(t1);new(t2);地址：typeclasses＝＾students;students＝recordname:string[8];num:1..100;link:classes;end;varclas1,clas2:classes;使用方法：

NEW(clas1);NEW(clas2);

計算機(jī)開辟了兩個

students記錄類型的存貯空間，分別由

clas1,clas2指向這兩個記錄：

clas1＾.nameclas1＾.num,clas1＾.link

clas2＾.name,clas2＾.num,clas2＾.link

(3)對指針變量可以進(jìn)行關(guān)系運算

如:ifP1<>P2then語句1else語句2;

whileP3<>NILdo..........................end;

關(guān)系運算的結(jié)果,仍是

FALSE,TRUE。數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)：（1）定義：數(shù)據(jù)之間的關(guān)系（2）邏輯結(jié)構(gòu)：數(shù)據(jù)之間的形式上的關(guān)系（3）物理結(jié)構(gòu)：數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)采用不同的存儲結(jié)構(gòu)，將引起不同的處理方法，即算法也不相同。二、數(shù)據(jù)結(jié)構(gòu)的描述：1、描述方法：用二元組表示，B=(K,R)

其含義是：B是一種數(shù)據(jù)結(jié)構(gòu)，K表示K個數(shù)據(jù)元素，R表示元素之間的關(guān)系。這里R可以是多個關(guān)系，我們主要研究R＝1

的關(guān)系2、例如：一種數(shù)據(jù)結(jié)構(gòu)表示如下：

LLL＝（K,R）K={01,02,03,04,05,06,07,08,09,10}R={r}r={<05,01>,<01,03>,<03,08>,<08,02>,<02,07>,<07,04>,<04,06>,<06,09>,<09,10>}

例題2、一種數(shù)據(jù)結(jié)構(gòu)tree=(K,R)K={01,02,03,04,05,06,07,08,09,10}R={r}r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,07>,<03,08>,<03,09>,<04,10>}三、算法的時間復(fù)雜性和空間復(fù)雜性1、時間復(fù)雜性：取決于循環(huán)次數(shù)和循環(huán)嵌套層數(shù)O(log2n)<O(n)<O(nlog2n)<O(n2)…<O(2n)<O(n!)2、空間復(fù)雜性計算：存儲單元的多少，主要在于數(shù)組單元數(shù)據(jù)之間的關(guān)系一、線性關(guān)系：1、L1=（a,b,c,f,h,x,z);2、L2=（34，56，12，78，45，86，100）

L=（a1,a2,a3,a4,……,an)

二、非線性關(guān)系

三、線性表1、線性表、線性鏈表2、棧、鏈接棧3、隊列、鏈接隊列

四、關(guān)于線性鏈表的幾點說明：（1）結(jié)點：數(shù)據(jù)域

指針域

（2）線性鏈表的幾種形式：單向鏈表、雙向鏈表、循環(huán)鏈表其特點如下：

在循環(huán)鏈表中，為了方便插入和刪除操作，一般加入頭結(jié)點

線性表的基本操作：（1）建立線性表（2）插入結(jié)點、刪除結(jié)點（3）求線性表的長度（4）查找（5）線性表的排序（6）線性表的歸并運算插入結(jié)點的操作：插入到頭結(jié)點:插入到某一個結(jié)點：插入到尾部:P＾.next:=head;

P＾.next:=q＾.next;r＾.next:=p;head:=p;

q＾.next:=p;

r:=p;

q:=q＾.netx;

刪除操作

：

刪除頭結(jié)點

刪除某一個結(jié)點

P：=head;

q＾.next:=p＾.next;Head:=head^.next;

dispose(p);Dispose(p);

五、棧的操作：1、進(jìn)棧（壓棧）2、出棧（彈棧）3、主要應(yīng)用于：遞歸、回溯算法、深度搜索等算法六、隊列操作：1、進(jìn)隊2、出隊3、主要應(yīng)用于：搜索算法（寬度搜索）、進(jìn)程管理等

第五節(jié)稀疏矩陣與廣義表一、稀疏矩陣

1、矩陣：由一組行列組成的數(shù)字陣列，稱為矩陣。如下圖：

123453-106121794-3721025-13-180-2242、矩陣的存儲方法：（1）一般用二維數(shù)組，數(shù)據(jù)之間的關(guān)系：行、列——線性，存儲結(jié)構(gòu)：由行、列唯一確定一個元素的位置（2）用線性鏈接表的結(jié)構(gòu)存儲矩陣一般矩陣存儲都采用順序存儲結(jié)構(gòu)，便于訪問和操作。3、稀疏矩陣：（1）定義：矩陣中非零元素的個數(shù)遠(yuǎn)遠(yuǎn)少于零元素的個數(shù)，這樣的矩陣稱為非零矩陣。如下圖所示：

123456300500100-200021040603000000400-10005

二、稀疏矩陣的存儲1、稀疏矩陣若采用普通存儲方法，則占用大量的存儲空間。（從節(jié)約內(nèi)存考慮，如何減少存儲空間？）2、存儲方法：三元組存儲法，設(shè)稀疏矩陣按行、列號從小到大順序排列。如書圖（3-16），變?yōu)橐粋€線性表順序存儲用一個二維數(shù)組A[0..m,1..3]:integer

其中m表示非零元素的個數(shù)

A12301234567

用順序存儲結(jié)構(gòu)表示三元組存儲非零元素的個數(shù)

A[0，1]=5，A[0，2]=6，A[0，3]=7A[1，1]=1，A[1，2]=1，A[1，3]=3A[2，1]=1，A[2，2]=4，A[2，3]=556711314523-231133435633-1存儲方法：

A[0,1]—存放整個矩陣的非零元素個數(shù)，

A[0,2]—總行數(shù)，

A[0,3]—存放總列數(shù)按行存放：每個非零元素所在行、列數(shù)以及本身值鏈接存儲：設(shè)定一個數(shù)組，其類型為指針，該指針類型有4個域：

typematnode=recordrow,col:integer;

val:integer;next:^matnode;end;

varA:array[1..5]ofmatnode數(shù)組的每個單元是一個結(jié)點，它將鏈接本行的非零元素。因此，這是一種將順序存儲與動態(tài)存儲有機(jī)結(jié)合的存儲方法。存儲結(jié)構(gòu)圖如下：

A數(shù)組12345113145∧22-2∧311334356∧53-1∧三、稀疏矩陣運算：

1、轉(zhuǎn)置運算

所謂矩陣轉(zhuǎn)置是指將矩陣的行、列數(shù)據(jù)進(jìn)行轉(zhuǎn)換——即第一行變?yōu)榈谝涣?，第二行變?yōu)榈诙小?。一般的轉(zhuǎn)置方法是通過雙重循環(huán)，將行列值交換。稀疏矩陣的轉(zhuǎn)換方法是：

123451234563010030050010000000-200020-240-110406035000000000040060000-1000500000

（1）用三元組方法存儲原稀疏矩陣——A數(shù)組（設(shè)m行、n列），t個非零元素（2）轉(zhuǎn)換后的矩陣為B數(shù)組（T行，N列）：

B[0，1]=n，B[0，2]=m，B[0，3]=t（3）對A數(shù)組進(jìn)行T次掃描，其方法是：

第一次掃描，將A數(shù)組中非零元素的列值為1所有單元，按照從上到下（行號從小到大）順序?qū)懭隑數(shù)組中。第二次掃描，將A數(shù)組中非零元素的列值為2的所有單元，按照同樣方法，再寫入B數(shù)組?！瓕懭氲姆椒ㄊ牵簩數(shù)組的行、列、本身值依次賦給B數(shù)組的列、行、本身值算法如下：Proceduretransmat(A,B);{本題的時間復(fù)雜性：？}

beginm:=a[0,1];n:=a[0,2];t:=a[0,3];b[0,1]:=n;b[0,2]:=m;b[0,3]:=t;ift=0thenreturn;q:=1;forcol:=1tondoforp:=1totdoifa[p,2]=colthenbeginb[q,1]:=a[p,2];b[q,2]:=a[p,1];b[q,3]:=a[p,3];q:=q+1;end;end;方法二：（1）對數(shù)組A進(jìn)行兩次掃描，首先掃描A數(shù)組中的每一列非零元素的個數(shù)，并得到每一列的第一個非零元素在B數(shù)組中的位置；（2）第二次掃描，將A數(shù)組的每個三元組寫入到B數(shù)組的相應(yīng)位置。（3）細(xì)化：用num數(shù)組統(tǒng)計原矩陣中每列的非零元素的個數(shù)，用pot數(shù)組記錄下一個非零元素在B數(shù)組中的存儲位置（B的行號）

計算式：pot[1]:=1;pot[col]:=pot[col-1]+num[col-1];

由數(shù)組A可以得到num數(shù)組與pot數(shù)組的初始值：

其算法如下：

procedurefasttrans(A,B);begin

(1)m:=a[0,1];n:=a[0,2];t:=a[0,3];

(2)b[0,1]:=n;b[0,2]:=m;b[0,3]:=t;(3)ift=0thenreturn;(4)forcol:=1tondonum[col]:=0;(5)forI:=1totdonum[a[I,2]]:=num[a[I,2]]+1;(6)pot[1]:=1;forcol:=2tondopot[col]:=pot[col-1]+num[col-1];

ForI:=1totdobegin

col:=A[I,2];q:=pot[col];B[q,1]:=A[I,2];B[q,2]:=A[I,1];B[q,3]:=A[I,3];pot[col]:=pot[col]+1;end;End;2、矩陣加法運算：（1）一般矩陣加法運算的方法：將兩個矩陣中對應(yīng)的行、列元素進(jìn)行加法運算——一一對應(yīng)，求和。(A:=A+B)（2）稀疏矩陣加法（用順序存儲的三元組方法）（3）用線性鏈接表的方法，進(jìn)行矩陣加法計算

其算法：Procedurejuzhenjiafa(a,b,n);typepoint=^node;node=record

da:integer;x,y:integer;next:point;end;

vara,b:array[1..100]ofpoint;p,q,r:point;begin(1)建立兩個稀疏矩陣（鏈?zhǔn)剑?2)ForI:=1tondo

[q:=A[I];p:=q^.next;r:=B[I]^.next;]

(原先的兩個鏈表都帶有頭結(jié)點）(3)

while(p<>nil)and(r<>nil)dobeginifq^.x<r^.xthen[q:=p;p:=p^.next];ifq^.x=r^.x

thenifp^.da+r^.da<>0then[p^.da:=p^.da+r^.da;q:=p;p:=p^.next]else[q^.next:=p^.next;p:=p^.next;r:=r^.next]ifp^.col>r^.colthen[s:=r^.next;q^.next:=r;r^.next:=p;q:=r;r:=s]end;(4)ifp=nilthenp^.next:=r;End;矩陣乘法：矩陣乘法：A[M，N]*B[N，T]=C[M，T]例如：

一般矩陣乘法的運算方法：（1）A、B兩矩陣必須滿足如下條件：

A矩陣的列數(shù)與B矩陣的行數(shù)相同，即：A[K，T]，B[T，X]

得到新的矩陣：C[K，X]（2）乘法方法：將A矩陣的一行的每個元素，對應(yīng)乘以B矩陣的每一列的元素，其代數(shù)和為當(dāng)前新矩陣的一個元素值。（3）程序?qū)崿F(xiàn)的方法：建立三個數(shù)組，其行列個數(shù)，根據(jù)需要設(shè)定輸入兩個矩陣，并輸出利用三重循環(huán)語句完成矩陣乘法運算。稀疏矩陣的乘法運算：用三元組存儲方法，計算兩個矩陣相乘廣義表一、廣義表1、定義：線性表的推廣。廣義表是指一個表或者是空表或是一個非空元素組成的表。其元素可以是某個確定類型的元素，也可以是子表組成。（a1,a2,a3,B4,a5,a6,B7……an)其中B4、B7分別為一個子表。B4=（b1,b2,b3,……bi),B7=(d1,d2,……,dj)例如：A=（），B=（e），C=(a,(b,c,d))D=(A,B,C)=((),(e),(a,(b,c,d)))E=((a,(a,b),((a,b),c)))注意：①廣義表通常用圓括號括起來，用逗號分隔其中的元素。

②為了區(qū)分原子和子表，書寫時用大寫字母表示廣義表的子表，用小寫字母表示原子。

③若廣義表L非空(n≥1)，則al是L的表頭，其余元素組成的表(a1，a2，…，an)稱為L的表尾。

④廣義表是遞歸定義的

2、廣義表常用表示

①E=()

E是一個空表，其長度為0。

②L=(a，b)

L是長度為2的廣義表，它的兩個元素都是原子，因此它是一個線性表

③A=(x，L)=(x，(a，b))

A是長度為2的廣義表，第一個元素是原子x，第二個元素是子表L。

④B=(A，y)=((x，(a，b))，y)

B是長度為2的廣義表，第一個元素是子表A，第二個元素是原子y。⑤C=(A，B)=((x，(a，b))，((x，(a，b))，y))

C的長度為2，兩個元素都是子表。

⑥D(zhuǎn)=(a，D)=(a，(a，(a，(…))))

D的長度為2，第一個元素是原子，第二個元素是D自身，展開后它是一個無限的廣義表。

3、廣義表的深度

一個表的"深度"是指表展開后所含括號的層數(shù)。

【例】表L、A、B、C的深度為分別為1、2、3、4，表D的深度為∞。

4、廣義表的結(jié)構(gòu)圖：A=（），B=（e），C=(a,(b,c,d))D=(A,B,C)=((),(e),(a,(b,c,d)))樹形結(jié)構(gòu)二、廣義表的存儲結(jié)構(gòu)由于廣義表中元素及子表中的元素多少不固定，所以一般用動態(tài)鏈接結(jié)構(gòu)。結(jié)點表示：

A=NIL，

B

C

Tag(0,1)

da(或link)Next0e∧0a1∧0b0c∧d0練習(xí)：畫出下列廣義表的鏈接存儲結(jié)構(gòu)

A=（a,b,c);B=(a,(b,(c)));C=((a,b),(c,d));D=(a,(b,(c,d),(e))；E=((a,(b,(),c),((d),e)))。三、廣義表類型定義方法及操作：

1.定義：

typenode=recordtag:0..1;{0：表示元素，1：表示子表}

next:^node;casetagof0:da:integer;{char}1:link:^node;end;

2.廣義表的操作：建立廣義表、輸出廣義表求廣義表的表頭和表尾

(3)計算廣義表的深度:所有子表中最大深度加1例題1：建立廣義表的算法元素之間用“，”分開，表元素的開始結(jié)束符號用“（）”，空表用（）表示。設(shè)用“；”號作為表的結(jié)束符號。（加一個表頭結(jié)點）

E=((a,(b,(),c),((d),e)))；Procedurecreat(varpo:node);begin(1)read(ch);(2)casechof‘

’:po=nil;‘(‘:[new(po);po^.tag:=1;creat(po^.link);]‘a(chǎn)’..’z’:[new(po);po^.tag:=0;po^.da:=ch;]end;(3)read(ch);(4)ifpo<>nilthenifch:=‘,’thencreat(po^.next)elsepo^.next:=nilend;例題2輸出廣義表的算法用“（”表示廣義表的開始，用“）”表示結(jié)束Procedureprint(p:node);begin(1)ifp^.tag=1thenbeginwrite(‘(‘);ifp^.link=nilthenprint(‘‘)elseprint(p^.link)elsewrite(p^.da);(2)ifp^.tag=1thenwrite(‘)’)(3)ifp^.next<>nilthen[write(‘,’);print(p^.next))]end;例題3求廣義表的表頭和表尾。表頭：head(),

表尾:tail()

表頭是指表中的第一個元素，表尾是指除表頭以外的元素。任何一個非空廣義表的表頭是表中第一個元素，它可以是原子，也可以是子表，而其表尾必定是子表。

例如：(1)

HEAD(TAIL(HEAD(((a,b),(c,d))))(2)

TAIL(HEAD(TAIL(((a,b),(c,d))))

(3).廣義表((A,B,E,F,G))的表尾是()。

A.(B,E,F,G)

B.()C.（A，B，E，F(xiàn)，G)

D.不存在

(4).廣義表（(()，()),(a,b,c),(e,d)）的表頭是()，表尾是()。

A.((e,d))B.(())C.((),())D.（(a,b,c）,(e,d))

(5)對廣義表((a),(b))進(jìn)行下面的操作head(head((a),(b)))后的結(jié)果是()。

A.