第5章數(shù)組和廣義表課件

數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表中的所有元素本身也是一種線性表。由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的數(shù)據(jù)結(jié)構(gòu)較為簡單。多維數(shù)組是向量的推廣。例如，二維數(shù)組：5.1數(shù)組的定義二維數(shù)組可以看成是由行向量組成的向量，也可以看成是由列向量組成的向量。同樣，可把三維數(shù)組看成是一個線性表，表中每一個數(shù)組元素為一個二維數(shù)組。依次類推，可把n維數(shù)組看成是一個線性表，表中每一個數(shù)據(jù)元素是一個n-1維數(shù)組。數(shù)組的運(yùn)算：數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作，即給定一組下標(biāo)，存取或修改相應(yīng)的數(shù)組元素。5.1數(shù)組的定義1、順序存儲結(jié)構(gòu)5.2數(shù)組的順序表示和實現(xiàn)用一組地址連續(xù)的存儲單元依次存放數(shù)組的數(shù)據(jù)元素，稱為數(shù)組的順序存儲結(jié)構(gòu)。由于計算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。由于對數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲的方法來表示數(shù)組。

通常有兩種順序存儲方式：2、順序存儲方式⑴行優(yōu)先順序——將數(shù)組元素按行向量排列，第i+1個行向量緊接在第i個行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲的線性序列為：a11,a12,…,a1n,a21,a22,…,a2n,……,am1,am2,…,amn

在PASCAL、C語言中，數(shù)組就是按行優(yōu)先順序存儲的。⑵列優(yōu)先順序——將數(shù)組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后。以二維數(shù)組為例，按列優(yōu)先順序存儲的線性序列為：a11,a21,…,am1,a12,a22,…,am2,……,a1n,a2n,…,amn

在FORTRAN語言中，數(shù)組就是按列優(yōu)先順序存儲的。

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序為主序存放amn……

am2am1………a2n……

a22a21a1n

……a12

a1101n-1m*n-1n

按列序為主序存放01m-1m*n-1mamn……

a2na1n………am2……

a22a12am1

……a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

以上規(guī)則推廣到多維數(shù)組的情況：行優(yōu)先順序可規(guī)定為先排最右的下標(biāo)，從右到左，最后排最左的下標(biāo)；3、n維數(shù)組按上述兩種方式順序存儲的數(shù)組，只要知道開始結(jié)點的存放地址（即基地址）、維數(shù)和每維的上、下界，以及每個數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為其下標(biāo)的線性函數(shù)。因此，數(shù)組中的任一元素可以在相同的時間內(nèi)存取，即順序存儲的數(shù)組是一個隨機(jī)存取結(jié)構(gòu)。列優(yōu)先順序與此相反，先排最左的下標(biāo)，從左向右，最后排最右的下標(biāo)。例如，二維數(shù)組Amn按“行優(yōu)先順序”存儲在內(nèi)存中，假設(shè)每個元素占用d個存儲單元。4、地址公式

元素aij的存儲地址應(yīng)是數(shù)組的基地址加上排在aij前面的元素所占用的單元數(shù)。因為aij位于第i行、第j列，前面i-1行一共有(i-1)×n個元素，在第i行上aij前面又有j-1個元素，故它前面一共有(i-1)×n+j-1個元素，因此，aij的地址計算函數(shù)為：LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d同樣，三維數(shù)組Aijk按“行優(yōu)先順序”存儲，其地址計算函數(shù)為：LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p+(k-1)]*d上述討論均是假設(shè)數(shù)組各維的下界是1，更一般的二維數(shù)組是A[c1..d1,c2..d2]，這里c1,c2不一定是1。aij前一共有i-c1行，二維數(shù)組一共有d2-c2+1列，故這i-c1行共有(i-c1)*(d2-c2+1)個元素，在第i行上aij前一共有j-c2個元素，因此，aij的地址計算函數(shù)為：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d例如，在C語言中，數(shù)組各維下標(biāo)的下界是0，因此在C語言中，二維數(shù)組的地址計算公式為：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d4、地址公式在高級語言編制程序時，將一個矩陣描述為一個二維數(shù)組。但是在矩陣中非零元素呈某種規(guī)律重復(fù)分布或者矩陣中出現(xiàn)大量的零元素的情況下，實際上占用了許多單元去存儲重復(fù)的非零元素或零元素，這對高階矩陣會造成極大的浪費(fèi)，為了節(jié)省存儲空間，可以對這類矩陣進(jìn)行壓縮存儲。5.3矩陣的壓縮存儲壓縮存儲：為多個值相同的非零元素只分配一個存儲空間；對零元素不分配空間。假若值相同的元素或零元素在矩陣中的分布有一定規(guī)律，則稱此類矩陣為特殊矩陣；反之，稱為稀疏矩陣。1、對稱矩陣5.3.1特殊矩陣在一個n階方陣A中，若元素滿足下述性質(zhì)：aij=aji0≦i,j≦n-1

則稱A為對稱矩陣。對稱矩陣中的元素關(guān)于主對角線對稱，故只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間，這樣，能節(jié)約近一半的存儲空間。不失一般性，按“行優(yōu)先順序”存儲主對角線（包括對角線）以下的元素，其存儲形式如圖所示：

a00a01

….

……..a0n-1

a10

a11

……..…….a1n-1

an-10

an-11

……..an-1n-1

….a00a10a11a20a21a22………………..an-10an-11an-12…an-1n-1

a00a01

….

……..a0n-1

a10

a11

……..…….a1n-1

an-10

an-11

……..an-1n-1

….圖5.1對稱矩陣在這個下三角矩陣中，第i行恰有i+1個元素，元素總數(shù)為：n(n+1)/2。這樣可將n2個壓縮到n(n+1)/2個元的空間中。因此，可以按將這些元素存放在一個向量sa[0..n(n+1)/2-1]中。為了便于訪問對稱矩陣A中的元素，必須在aij和sa[k]之間找一個對應(yīng)關(guān)系。1、對稱矩陣若i≧j，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）一共有1+2+…+i=i(i+1)/2個元素，在第i行上，aij之前恰有j個元素（即ai0,ai1,ai2,…,aij-1），因此有：1、對稱矩陣

k=i*(i+1)/2+j0≦k<n(n+1)/2若i<j，則aij是在上三角矩陣中。因為aij=aji，所以只要交換上述對應(yīng)關(guān)系式中的i和j即可得到：

k=j*(j+1)/2+i0≦k<n(n+1)/2令I(lǐng)=max(i,j)，J=min(i,j)，則k和i,j的對應(yīng)關(guān)系可統(tǒng)一為：

k=I*(I+1)/2+J0≦k<n(n+1)/2因此，aij的地址可用下列式計算：

LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*d=LOC(sa[0])+[I*(I+1)/2+J]*da00a10a11a20……an-10……an-1,n-1有了上述的下標(biāo)交換關(guān)系，對于任意給定一組下標(biāo)(i，j)，均可在sa[k]中找到矩陣元素aij，反之，對所有的k=0,1,2,…n(n-1)/2-1，都能確定sa[k]中的元素在矩陣中的位置(i,j)。由此，稱sa[n(n+1)/2]為n階對稱矩陣A的壓縮存儲，見下圖：k=0123…n(n-1)/2n(n-1)/2-1例如a21和a12均存儲在sa[4]中，這是因為

k=I*(I+1)/2+J=2*(2+1)/2+1=4以主對角線劃分，三角矩陣有上三角和下三角兩種。2、三角矩陣a00a01…a0n-1ca11…a1n-1……………..cc…an-1n-1(a)上三角矩陣a00c…ca10a11…c……………..an-10an-11…an-1

n-1

(b)下三角矩陣上三角矩陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角矩陣中的常數(shù)c為零。在帶狀矩陣中，所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。這個帶狀區(qū)域若包含主對角線下面及上面各d條對角線上的元素，那么，該方陣稱為半帶寬為d的帶狀矩陣。2d+1稱為帶狀矩陣的帶寬。3、帶狀（對角）矩陣

a11a120

…………….

0

a21

a22a23

0

……………0

0

0

…an-1,n-2an-1,n-1

an-1,n

0

0

……an,n-1

ann

0

a32

a33a34

0

………0……………非零元素僅出現(xiàn)在主對角上、緊鄰主對角線上面的d條對角線上和緊鄰主對角線下面的d條對角線上。顯然，當(dāng)∣i-j∣>d時，元素aij=0。對帶狀矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標(biāo)的對應(yīng)關(guān)系。上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲到一個一維數(shù)組中，并且一般都能找到矩陣中的元素與該一維數(shù)組元素的對應(yīng)關(guān)系，通過這個關(guān)系，能對矩陣的元素進(jìn)行隨機(jī)存取。5.3.2稀疏矩陣什么是稀疏矩陣？精確地，設(shè)在m×n的矩陣A中，有t個非零元素。

令δ=t/(m*n)，稱δ為矩陣的稀疏因子。通常認(rèn)為δ≤0.05時可稱之為稀疏矩陣。簡單說，設(shè)矩陣A中有s個非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。在存儲稀疏矩陣時，為了節(jié)省存儲單元，很自然地想到使用壓縮存儲方法。但由于其非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須同時記下它所在的行和列的位置（i，j)。1、三元組順序表

反之，一個三元組(i，j，aij)唯一確定了矩陣A的一個非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。例如，下列三元組表((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))加上(6,7)這一對行、列值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲方法。

圖5.4稀疏矩陣M和T1、三元組順序表

#defineM20typedefstructnode{inti,j;intv;}JD;JDma[M];三元組表所需存儲單元個數(shù)為3(t+1)，其中t為非零元個數(shù)678

121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分別存放

矩陣行、列維數(shù)和非零元個數(shù)行列下標(biāo)非零元值2、稀疏矩陣的壓縮存儲方法3、求轉(zhuǎn)置矩陣問題描述：已知一個稀疏矩陣M的三元組表ma，求該矩陣的轉(zhuǎn)置矩陣T的三元組表mb。解決思路：

（1）將矩陣行、列維數(shù)互換

（2）將每個三元組中的i和j相互調(diào)換

（3）重排三元組次序，使mb中元素以T的行(M的

列)為主序67

8

121213931-3361443245218611564-7ijv012345678maijv76

8

13-3161521122518319342446-76314012345678mb?一個m×n的矩陣A，它的轉(zhuǎn)置B是一個n×m的矩陣，且aij=bji，0≤i≤m-1，0≤j≤n-1，即A的行是B的列，A的列是B的行。方法一將A轉(zhuǎn)置為B，就是將A的三元組表a.data置換為表B的三元組表b.data，如果只是簡單地交換a.data中i和j的內(nèi)容，那么得到的b.data將是一個按列優(yōu)先順序存儲的稀疏矩陣B。要得到按行優(yōu)先順序存儲的b.data，就必須重新排列三元組的順序。

由于A的列是B的行，因此，按a.data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b.data必定是按行優(yōu)先順序存放的。按這種方法設(shè)計的算法，其基本思想是：對A中的每一列col(0≤col≤n-1)，通過從頭至尾掃描三元表a.data，找出所有列號等于col的那些三元組，將它們的行號和列號互換后依次放入b.data中，即可得到B的按行優(yōu)先順序的壓縮存儲表示。方法一

#defineMAXSIZE12500typedefstruct{inti,j;ElemTypee;}Triple;typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;

StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)

{q=1;

for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)

if(M.data[p].j==col){

T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}

}returnOK;}6

7

8

121213931-3361443245218611564-7ijv012345678ma7

6

8

13-3161521122518319342446-76314ijv012345678mbqppppppppqqqqppppppppcol=1col=2方法一這個算法，主要的工作是在p和col的兩個循環(huán)中完成的，故算法的時間復(fù)雜度為O(nu*tu)，即矩陣的列數(shù)和非零元的個數(shù)的乘積成正比。而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為：for(col=1;col<=nu;++col)

for(row=1;row<=mu;++row)t[col][row]=m[row][col];

其時間復(fù)雜度為O(nu*mu)。方法一當(dāng)非零元素的個數(shù)tu和mu*nu同數(shù)量級時，方法一的時間復(fù)雜度為O(mu*nu2)。三元組順序表雖然節(jié)省了存儲空間，但時間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時還有可能增加算法的難度。因此，此算法僅適用于tu<<mu*nu的情況。方法一按照a.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入b.data中的恰當(dāng)位置。方法二：快速轉(zhuǎn)置算法如果能預(yù)先確定矩陣M中每一列（即T中每一行）的第一個非零元素在b.data中應(yīng)有的位置，那么在對a.data中的三元組依次作轉(zhuǎn)置時，便可直接放到b.data中恰當(dāng)?shù)奈恢蒙先ァ榱舜_定這些位置，在轉(zhuǎn)置前，應(yīng)先求得M的每一列中非零元的個數(shù)，進(jìn)而求得每一列的第一個非零元在b.data中應(yīng)有的位置。快速轉(zhuǎn)置算法的思想：對A掃描一次，按A第二列提供的列號依次確定裝入B的一個三元組的位置。具體實施如下：一遍掃描先確定三元組的位置關(guān)系，二次掃描由位置關(guān)系裝入三元組?？梢姡恢藐P(guān)系是此種算法的關(guān)鍵。

實現(xiàn)：需要附設(shè)num和cpot兩個數(shù)組。num[col]：表示矩陣M中第col列中非零元的個數(shù)；cpot[col]：指示矩陣M中第col列第一個非零元在mb中的位置顯然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2cola.nu)1357889colnum[col]cpot[col]12223241506170方法二：快速轉(zhuǎn)置算法StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];//求M中每一列含非零元個數(shù)cpot[1]=1;方法二：快速轉(zhuǎn)置算法for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];//求第col列中第1個非零元素在b.data中的序號。for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpot[col];}//ifreturnOK;}

T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}方法二：快速轉(zhuǎn)置算法這個算法僅比前一個算法多用了兩個輔助數(shù)組。快速轉(zhuǎn)置算法分析從時間上看，算法中有四個并列的單循環(huán)，循環(huán)次數(shù)分別為nu和tu，因而總的時間復(fù)雜度為O（nu＋tu）。在M的非零元素個數(shù)tu和mu×nu等數(shù)量級時，其時間復(fù)雜度為O（mu×nu），和經(jīng)典算法的時間復(fù)雜度相同。67

8

121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]1122323524715806817907

6

8

13-3161521122518319342446-76314pppppppp4629753typedefstructOLNode{inti，j;ElemTypee;structOLNode*down,*right;}OLNode,*OLink;ijedownright在鏈表中，每個非零元素可用一個含5個域的結(jié)點表示，right域用以鏈接同一行中下一個非零元素，down域用以鏈接同一列中下一個非零元素。4、十字鏈表ijedownright4、十字鏈表同一行的非零元素通過right域鏈接成一個線性表，同一列的非零元素通過down域鏈接成一個線性表，每個非零元素既是某個行鏈表中的一個結(jié)點，又是某個列鏈表中的一個結(jié)點，整個矩陣構(gòu)成了一個十字交叉的鏈表，故稱這樣的存儲結(jié)構(gòu)為十字鏈表。十字鏈表可用兩個分別存儲行鏈表的頭指針和列鏈表的頭指針的一維數(shù)組表示。113418225234^^^^^^^4、十字鏈表例題：兩個矩陣相加假設(shè)兩個矩陣相加后的結(jié)果為A’，則和矩陣A’中的非零元aij’只可能有三種情況:aij+bij

由此，當(dāng)將B加到A上去時，對A矩陣的十字鏈表來說：改變結(jié)點的e值（aij+bij0）aij(bij=0)bij(aij=0)不變(bij=0)插入一個新結(jié)點(aij=0)還有一種情況是：和A矩陣中的某個非零元相對應(yīng)，和矩陣A’中是零元，即對A的操作是刪除一個結(jié)點（aij+bij=0）。由此，整個運(yùn)算過程可從矩陣的第一行起逐行進(jìn)行。對每一行都從表頭出發(fā)分別找到A和B在該行中的第一個非零元結(jié)點后，開始比較，然后按上述四種不同情況分別處理。例題：兩個矩陣相加廣義表（lists，又稱列表）是線性表的推廣。

在第2章，線性表定義為n0個元素a1,a2,a3,…,an的有限序列。線性表的元素僅限于原子項。原子是作為結(jié)構(gòu)上不可分割的成分，它可以是一個數(shù)或一個結(jié)構(gòu)，若放松對表元素的這種限制，容許它們具有其自身結(jié)構(gòu)，這樣就產(chǎn)生了廣義表的概念。5.4廣義表的定義廣義表是n(n0)個元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項，或者是一個廣義表。通常記作

LS=（a1,a2,a3,…,an)

LS是廣義表的名字，n為它的長度。

若ai是廣義表，則稱它為LS的子表。通常用圓括號將廣義表括起來，用逗號分隔其中的元素。為了區(qū)別原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。若廣義表LS（n>=1)非空，則a1是LS的表頭，其余元素組成的表(a2,a3,…,an)稱為LS的表尾。顯然廣義表是遞歸定義的，這是因為在定義廣義表時又用到了廣義表的概念。廣義表的例子如下：

（1）A=（）——A是一個空表，其長度為零。

（2）B=（e）——表B只有一個原子e，B的長度為1。

（3）C=（a,(b,c,d))——表C的長度為2，兩個元素分別為原子a和子表(b,c,d)。

（4）D=（A，B，C）——表D的長度為3，三個元素都是廣義表。顯然，將子表的值代入后，則有D=((),(e),(a,(b,c,d)))。5.4廣義表的定義

（5）E=（a,E）——這是一個遞歸的表，它的長度為2，E相當(dāng)于一個無限的廣義表E=(a,(a,(a,(a,…)))).例如：D=(E,F)

其中:

E=(a,(b,c))F=(d,(e))DEFa()d()bce從上述定義和例子可推出廣義表的三個重要結(jié)論：（1）廣義表的元素可以是子表，而子表的元素還可以是子表。由此，廣義表是一個多層次的結(jié)構(gòu)，可以用圖形象地表示。5.4廣義表的定義（2）廣義表可為其它表所共享。例如在上述例（4）中，廣義表A，B，C為D的子表，則在D中可以不必列出子表的值，而是通過子表的名稱來引用。（3）廣義表的遞歸性。綜上所述，廣義表不僅是線性表的推廣，也是樹的推廣。廣義表中所含括弧的重數(shù)稱為表的深度，表中元素的層數(shù)就是包括該元素的括弧重數(shù)。例如：F（a，b，（c，（d）））其中，單元素a、b在第一層，d在第三層，廣義表的深度為3。5.4廣義表的定義由于廣義表(a1,a2,a3,…,an)中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)（或是原子，或是廣義表），因此，難以用順序存儲結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，每個數(shù)據(jù)元素可用一個結(jié)點表示。tag=1hptptag=0atom表結(jié)點原子結(jié)點由于廣義表中有兩種數(shù)據(jù)元素：原子或廣義表，因此，需要兩種結(jié)構(gòu)的結(jié)點：一種是表結(jié)點，一種是原子結(jié)點。表結(jié)點由三個域組成：標(biāo)志域、指示表頭的指針域和指示表尾的指針域；而原子結(jié)點只需兩個域：標(biāo)志域和值域。5.5廣義表的存儲結(jié)構(gòu)L=(a,(x,y),((x)))a(x,y)(

)

1

L0a

1

1

1

1

10x()xBCDE10e110a1∧1110a110d0c0b11廣義表的存儲結(jié)構(gòu)示例（1）A=（）（2）B=（e）（3）C=（a,（b,c,d））（4）D=（A，B，C）（5）E=（a,E）**5.6m元多項式的表示1、一元多項式一個多項式可以用一個長度為m且每個數(shù)據(jù)元素有兩個數(shù)據(jù)項（系數(shù)項和指數(shù)項）的線性表來表示。2、m元多項式一個m元多項式的每一項，最多有個m變元，如果用線性表來表示，則每個數(shù)據(jù)元素需要m+1個數(shù)據(jù)項，以存儲一個系數(shù)值和m個指數(shù)值。將產(chǎn)生兩個問題：造成浪費(fèi)線性表中結(jié)點大小不一樣因此，由于m元多項式中每一項的變化數(shù)目不均勻性和變元信息的重要性，故不適于用線性表表示。例如：上式是變元Z的多項式，即

其中：A和B本身又是一個（x,y）的二元多項式，15是Z的零次項的系數(shù)。進(jìn)一步考察A(x,y)，又可把它看成是y的多項式。Cy3+Dy2，而其中C和D為x的一元多項式。循環(huán)以往，每個多項式都可看作是由一個變量加上若干個系數(shù)指數(shù)偶對組成。**5.6m元多項式的表示任何一個m