數(shù)組、矩陣、廣義表
目錄
數(shù)組、矩陣、廣義表
? 一、數(shù)組
? ? ? ? 二.矩陣
三、廣義表
? 一、數(shù)組
????????這一章節(jié)理解基本概念即可。數(shù)組要看清其實(shí)下標(biāo)是多少，并且二維數(shù)組，存取數(shù)據(jù)，要先看清楚是按照行存還是按列存，按行則是正常一行一行的去讀寫，按列則是，從左至右，一列一列的弄。
????????此外，數(shù)組中具體坐標(biāo)的空間大小要會(huì)計(jì)算，每塊存儲(chǔ)單元，算到該數(shù)組坐標(biāo)的前一位的數(shù)組大?。喝鏏[5][3]，起始位A[0][0]，則計(jì)算A[5][3]的時(shí)候，先計(jì)算0-4行的空間大小，再計(jì)算第5行的大小，第五行的時(shí)候，是計(jì)算0-2列即0，1，2，三列，所以第五行空間個(gè)數(shù)為3，將其加上即可。
二、矩陣
????????則是掌握基本矩陣的代碼，矩陣相加，相乘，轉(zhuǎn)置。
- 其次要會(huì)壓縮矩陣，壓縮矩陣的目的是減少存儲(chǔ)單元
- 方法是，給矩陣中的有效數(shù)據(jù)，存進(jìn)一維數(shù)組中去。
- 這個(gè)時(shí)候就需要壓縮矩陣的計(jì)算了，一般計(jì)算特殊矩陣：
-
對稱陣，上三角下三角，畫一個(gè)簡單的矩陣，然后根據(jù)按行存或者按列存，進(jìn)行存儲(chǔ)，然后計(jì)算，一般是等差數(shù)列，然后加上最后一行或最后一列的有效數(shù)據(jù)，這個(gè)就看具體是多少了。一般遇到選擇題，讓求規(guī)律的，在看清矩陣和一維數(shù)組起始下標(biāo)的前提下，找具體坐標(biāo)試一下，如A[0][0]---0,在一維數(shù)組里面是第0個(gè)，給（行）i=0,（列）j=0，代入試一下即可。如果遇到算具體數(shù)值的，則是畫一個(gè)大概矩陣，然后找規(guī)律。按行排列，則先計(jì)算0到i-1行的個(gè)數(shù)（一般為等差數(shù)列，第0行有1個(gè)，第1行有2個(gè)第i-1行有i個(gè)，則共0到i-1，總個(gè)數(shù)為i個(gè)，a1=1,an=i所以等差數(shù)列為(
）,這是第0到i-1行的總個(gè)數(shù)，再計(jì)算第i行的個(gè)數(shù)，按列算，j+1個(gè)，所以總個(gè)數(shù)為
- 對三角矩陣，則是待定系數(shù)法，為了省事直接k=ai+bj+c，其中k為存進(jìn)一維數(shù)組的下標(biāo)，i為矩陣的行，j為矩陣的列，c為常數(shù)，然后再去帶具體坐標(biāo)去解方程組即可。但上面設(shè)的公式，還要看具體情況去設(shè)置，如果有的個(gè)數(shù)為等差數(shù)列，則肯定有行的平方或者列的平方。
- 之后是稀疏矩陣：矩陣中大部分都是0的矩陣。
稀疏矩陣的壓縮，就是給矩陣中非零元素，存起來。
稀疏矩陣的順序存儲(chǔ)（設(shè)成結(jié)構(gòu)體，里面包含各種變量）
1.三元組表示法
按行優(yōu)先存儲(chǔ)，所以稀疏矩陣三元組，不好逆置，逆置的話，需要按列重新搞一下。
????????三元組，就是數(shù)組結(jié)構(gòu)體里定義三個(gè)變量，分別是行，列，以及坐標(biāo)值。其中數(shù)組結(jié)構(gòu)體，第一個(gè)里面存的是，矩陣信息，即共幾行幾列，有幾個(gè)非零元素。因此如果題中有5個(gè)非零元素，則三元組數(shù)組，要5+1個(gè)數(shù)組空間。
稀疏矩陣轉(zhuǎn)化三元組步驟：
????????1.先計(jì)算矩陣中非零元素個(gè)數(shù)。即二維數(shù)組遍歷，非零的，count（計(jì)數(shù)器）+1。最后返回count。
? ? ? ? 2.之后定義一個(gè)三元組數(shù)組，然后開始寫轉(zhuǎn)換函數(shù)，返回類型為三元組指針類型，即返回三元組。先存儲(chǔ)矩陣信息，再三元組數(shù)組第一個(gè)位置，隨后定義個(gè)記錄器，index=1，表示實(shí)際非零元素個(gè)數(shù)的下標(biāo)，隨后開始遍歷，當(dāng)矩陣元素不等于零的時(shí)候，存進(jìn)index坐標(biāo)下，隨后行和列也記錄，之后，index+1，后移動(dòng)，直到遍歷結(jié)束。
2.偽地址存儲(chǔ)
數(shù)據(jù)結(jié)構(gòu)體，里面變量為偽地址變量以及具體值。偽地址計(jì)算方法，可直接查，按照行或者列，從1開始，哪個(gè)位置非零，就記錄。
稀疏矩陣的鏈?zhǔn)酱鎯?chǔ)
1.鄰接表法。
用一維數(shù)組（矩陣行）去索引，索引內(nèi)容，坐標(biāo)值，列下標(biāo)，以及同行下一個(gè)非零元。
即同一行，串成一個(gè)鏈，只串同行非零元素。
2.十字鏈表
三、廣義表
????????廣義表是線性表的推廣，不是線性表，而是層次結(jié)構(gòu)，樹。
????????每個(gè)廣義表用（）括住，廣義表里面可以套廣義表，每個(gè)廣義表是一個(gè)小整體。廣義表里面，可以是原子元素（單個(gè)值），可以是廣義表。
1.廣義表的深度，長度和表頭表尾
深度：即最外層元素個(gè)數(shù)，查右括號(hào)，最多的括號(hào)數(shù)。如：（（a）,(b,f),(v)）??（（a）,(b,f),(v)），最多括號(hào)數(shù)為2，所以深度為2，最外層括號(hào)+下一層。同層不能多算，取每層最大括號(hào)
長度：第一層元素個(gè)數(shù)，化成樹的話，是第二層結(jié)點(diǎn).
表頭：廣義表非空時(shí)，第一個(gè)元素。即表頭為取第一個(gè)元素的值。
表尾：實(shí)際上是除了表頭以外，其他構(gòu)成的新的廣義表。是個(gè)廣義表。
例如：（（a）,(b,f),(v)）
表頭為：（a）//只包含a的廣義表，? 不是a，a是原子元素。
表尾：（（b，f），(v)），新構(gòu)成的廣義表.
再對表尾求
表頭：（b,f），廣義表。? ?不是（（b，f）），表頭為取第一個(gè)元素
表尾：( (v) ),是個(gè)廣義表，由廣義表（v）構(gòu)成，即刪除表頭，剩下組成的新的廣義表，
廣義表的鏈?zhǔn)酱鎯?chǔ)
有兩個(gè)結(jié)點(diǎn)，第一個(gè)為廣義表結(jié)點(diǎn)，包含標(biāo)記域，表頭，表尾指針，第二個(gè)是原子元素結(jié)點(diǎn)，包含標(biāo)記域，和具體值。其中標(biāo)記域?yàn)?，表示廣義表，標(biāo)記域?yàn)?表示原子元素。
一般，先畫出第一個(gè)廣義表結(jié)點(diǎn)，然后頭節(jié)點(diǎn)指向出來，尾指針指向尾結(jié)點(diǎn)，以此類推。
擴(kuò)展的線性表存儲(chǔ)結(jié)構(gòu)文章來源：http://www.zghlxwxcb.cn/news/detail-648689.html
跟鏈?zhǔn)酱鎯?chǔ)差不多，只不過后面的指針變成了，左孩子又兄弟了，頭指針指向最左邊的孩子，之后孩子的尾指針，指向同級(jí)的右兄弟。（這種一般先畫成樹的形式，好判斷）文章來源地址http://www.zghlxwxcb.cn/news/detail-648689.html
到了這里，關(guān)于12-數(shù)據(jù)結(jié)構(gòu)-數(shù)組、矩陣、廣義表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
