09年自考《數據結構》各章要點一[9]

　　順序串又可按存儲分配的不同分為

　　·靜態存儲分配直接用定長的字符數組來定義優點是涉及串長的操作速度快但不適合插入鏈接操作

　　·動態存儲分配是在定義串時不分配存儲空間需要使用時按所需串的長度分配存儲單元

　　串的鏈式存儲就是用單鏈表的方式存儲串值串的這種鏈式存儲結構簡稱為鏈串鏈串與單鏈表的差異只是它的結點數據域為單個字符

　　為了解決存儲密度低的狀況可以讓一個結點存儲多個字符即結點的大小

　　順序串上子串定位的運算又稱串的模式匹配或串匹配是在主串中查找出子串出現的位置在串匹配中將主串稱為目標(串)子串稱為模式(串)這是比較容易理解的串匹配問題就是找出給定模式串P在給定目標串T中首次出現的有效位移或者是全部有效位移最壞的情況下時間復雜度是O((nm+)m)假如m與n同階的話則它是O(n^)鏈串上的子串定位運算位移是結點地址而不是整數

　　第五章 多維數組和廣義表

　　數組一般用順序存儲的方式表示存儲的方式有

　　·行優先順序也就是把數組逐行依次排列PASCALC

　　·列優先順序就是把數組逐列依次排列FORTRAN

　　地址的計算方法

　　·按行優先順序排列的數組LOCa(ij)=LOCa()+((i)*n+(j))*d

　　·按列優先順序排列的數組LOCa(ij)=LOCa()+((j)*n+(i))*d

[]  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/22849.html