數(shù)據(jù)結(jié)構(gòu)郝春梅C語(yǔ)言版第5章

1、2第5章 數(shù)組和廣義表學(xué)習(xí)目標(biāo)與要求：了解數(shù)組的概念及基本操作。掌握二維數(shù)組的行主序和列主序兩種存儲(chǔ)方式。 了解特殊矩陣的特點(diǎn)并掌握特殊矩陣的存儲(chǔ)形式及基本運(yùn)算。了解廣義表的概念及相關(guān)術(shù)語(yǔ)。掌握廣義表的存儲(chǔ)形式。3數(shù)組數(shù)組是一種擴(kuò)展的線性數(shù)據(jù)結(jié)構(gòu)。線性表、數(shù)組是一種擴(kuò)展的線性數(shù)據(jù)結(jié)構(gòu)。線性表、棧、隊(duì)列、串的數(shù)據(jù)元素都是不可再分的棧、隊(duì)列、串的數(shù)據(jù)元素都是不可再分的原子類型，而數(shù)組中的數(shù)據(jù)元素是可以再原子類型，而數(shù)組中的數(shù)據(jù)元素是可以再分的。數(shù)組可以分為一維數(shù)組和多維數(shù)組，分的。數(shù)組可以分為一維數(shù)組和多維數(shù)組，一維數(shù)組中的元素是由原子構(gòu)成的，多維一維數(shù)組中的元素是由原子構(gòu)成的，多維數(shù)組中的元素又

2、是一個(gè)線性表。因此，數(shù)數(shù)組中的元素又是一個(gè)線性表。因此，數(shù)組是一種特殊的線性表。組是一種特殊的線性表。4數(shù)組是由數(shù)組是由n個(gè)類型相同的數(shù)據(jù)元素組成的個(gè)類型相同的數(shù)據(jù)元素組成的有限序列。其中，這有限序列。其中，這n個(gè)數(shù)據(jù)元素占用一個(gè)數(shù)據(jù)元素占用一塊地址連續(xù)的存儲(chǔ)空間。數(shù)組中的數(shù)據(jù)元塊地址連續(xù)的存儲(chǔ)空間。數(shù)組中的數(shù)據(jù)元素可以是原子類型的，如整型、字符型、素可以是原子類型的，如整型、字符型、浮點(diǎn)型等，這種類型的數(shù)組稱為一維數(shù)組；浮點(diǎn)型等，這種類型的數(shù)組稱為一維數(shù)組；也可以是一個(gè)線性表，這種類型的數(shù)組稱也可以是一個(gè)線性表，這種類型的數(shù)組稱為二維數(shù)組。二維數(shù)組可以看成是線性表為二維數(shù)組。二維數(shù)組可以看成

3、是線性表的線性表。的線性表。5.1 數(shù)組的定義數(shù)組的定義5一個(gè)含有一個(gè)含有n個(gè)元素的一維數(shù)組可以表示成個(gè)元素的一維數(shù)組可以表示成線性表線性表A=（a0,a1,an-1）。其中，）。其中，ai(0=i=j當(dāng)當(dāng)ij235.3.1 特殊矩陣 245.3.1 特殊矩陣 255.3.1 特殊矩陣 k=（i-1）*(2n-i+2)/2 +j-i+10 當(dāng)ij上三角矩陣上三角矩陣k=i*(i-1)/2 +j0當(dāng)i=j當(dāng)icol=pb-col,且且pa-v+pb-v!=0,則只需用則只需用aij+bij的值改寫的值改寫pa所指結(jié)點(diǎn)的值域即可。所指結(jié)點(diǎn)的值域即可。（2）若）若pa-col=pb-col,且且pa

4、-v+pb-v=0,則只需在矩陣則只需在矩陣A的十字鏈表中刪除的十字鏈表中刪除pa所指結(jié)點(diǎn)，此時(shí)需改變?cè)撔墟湵碇星膀?qū)結(jié)所指結(jié)點(diǎn)，此時(shí)需改變?cè)撔墟湵碇星膀?qū)結(jié)點(diǎn)的點(diǎn)的right域，以及該列鏈表中前驅(qū)結(jié)點(diǎn)的域，以及該列鏈表中前驅(qū)結(jié)點(diǎn)的down域。域。（3）若）若pa-colcol,且且pa-col!=0(即不是表頭結(jié)點(diǎn)即不是表頭結(jié)點(diǎn))，則，則只需將只需將pa指針向右推進(jìn)一步，并繼續(xù)進(jìn)行比較。指針向右推進(jìn)一步，并繼續(xù)進(jìn)行比較。（4）若）若pa-colpb-col或或pa-col=0(即是表頭結(jié)點(diǎn)即是表頭結(jié)點(diǎn))，則需，則需要在矩陣要在矩陣A的十字鏈表中插入一個(gè)的十字鏈表中插入一個(gè)pb所指結(jié)點(diǎn)。所指結(jié)點(diǎn)。52本 章 小 結(jié)(1)數(shù)組可看作線性表的推廣，數(shù)組在計(jì)算機(jī)中數(shù)組可看作線性表的推廣，數(shù)組在計(jì)算機(jī)中采用順序存儲(chǔ)結(jié)構(gòu)表示，通常有兩種存儲(chǔ)順序：采用順序存儲(chǔ)結(jié)構(gòu)表示，通常有兩種存儲(chǔ)順序：以行序?yàn)橹餍蚝鸵粤行驗(yàn)橹餍?。以行序?yàn)橹餍蚝鸵粤行驗(yàn)橹餍颉?2)為了節(jié)省存儲(chǔ)空間，可以對(duì)特殊矩陣和稀疏為了節(jié)省存儲(chǔ)空間，可以對(duì)特殊矩陣和稀疏矩陣進(jìn)行壓縮存儲(chǔ)。矩陣進(jìn)行壓縮存儲(chǔ)。(3)廣義表是線性表的推廣，有兩種表示方法：廣義表是線性表的推廣，有兩