第5章 數(shù)據(jù)結(jié)構(gòu)（Ｃ＋＋版）數(shù)組和廣義3表

數(shù)據(jù)結(jié)構(gòu)第5章數(shù)組第3講1本章分為（2～3）講第1講

5.1

數(shù)組的基本概念

5.2

特殊矩陣

第2講5.3稀疏矩陣5.3.1數(shù)組元素的三元組

5.3.2三元組順序表供教師參考第2講5.3.3十字鏈表5.5廣義表

2稀疏矩陣A與它的十字鏈表存儲(chǔ)圖

回顧3十字鏈表概括如下:它有一個(gè)總表頭結(jié)點(diǎn)，由hm指針來表示。以總表頭結(jié)點(diǎn)為附加頭結(jié)點(diǎn)與S個(gè)行列表頭結(jié)點(diǎn)組成行列表頭循環(huán)鏈表。通過S個(gè)行列表頭結(jié)點(diǎn)，分別在m個(gè)行方向上組成以自己為附加頭結(jié)點(diǎn)的，m個(gè)行循環(huán)鏈表。通過S個(gè)行列表頭結(jié)點(diǎn)，又分別在n個(gè)列方向上組成以自己為附加頭結(jié)點(diǎn)的，n個(gè)列循環(huán)鏈表。只要給定hm指針值，便可取得整個(gè)稀疏矩陣的全部信息?；仡?2．十字鏈表的類定義

將3種不同用途的結(jié)點(diǎn)定義為同一種結(jié)構(gòu)體Node，在它的6個(gè)子域中，其中一個(gè)子域定義為共用體。typedef

int

ElemType;structNode //定義十字鏈表的結(jié)點(diǎn)

{Introw;int

col; //行號(hào)和/列號(hào)

Node*down; //行方向指針

Node*right; //列方向指針

union //定義共用體

{Node*next;

//作表頭結(jié)點(diǎn)，使用next

ElemType

val;//作數(shù)據(jù)結(jié)點(diǎn)，使用val

};};5//十字鏈表類定義classLinkedmat //十字鏈表類定義{private:Node*hm; //頭指針

public:

Linkedmat(); //構(gòu)造函數(shù)，初始化空十字鏈表

~Linkedmat(); //析構(gòu)函數(shù)

voidCreat(); //創(chuàng)建一個(gè)十字鏈表

voidShow(); //輸出顯示十字鏈表};

在此，主要突出基本算法，十字鏈表的建立和輸出。作為一個(gè)完整的鏈表類設(shè)計(jì)，其構(gòu)造和析構(gòu)函數(shù)十分重要不可或缺，它們的實(shí)現(xiàn)請(qǐng)讀者自行解決。63．十字鏈表的主要算法介紹建立稀疏矩陣的十字鏈表的算法；輸出十字鏈表的算法。

建立稀疏矩陣的十字鏈表的算法，實(shí)質(zhì)上是一個(gè)以插入操作為主的復(fù)雜算法。大體上分為兩步。首先建立總表頭結(jié)點(diǎn)為主的行列表頭結(jié)點(diǎn)組成的循環(huán)鏈表。然后逐一輸入數(shù)據(jù)元素的三元組，將每個(gè)數(shù)據(jù)結(jié)點(diǎn)既要插入所在行的行循環(huán)鏈表，也要插入所在列的列循環(huán)鏈表。7建立十字鏈表算法-5.3voidLinkedmat::Creat(){ intm,n,s,r,c,v;Node*p，*q，*h[10];

cout<<"請(qǐng)輸入要?jiǎng)?chuàng)建的矩陣維數(shù)->"<<endl<<endl;

cout<<"行數(shù):";cin>>m;cout<<"列數(shù):";cin>>n;s=m>n?m:n;//把行數(shù)和列數(shù)較大的賦值給sp=newNode;//動(dòng)態(tài)分配Node空間

p->row=m;p->col=n;

hm=p;h[0]=p;//hm

和h[0]指向總表頭結(jié)點(diǎn)

for(inti=1;i<=s;i++)//創(chuàng)建s個(gè)行列表頭結(jié)點(diǎn)

{

p=newNode;p->row=0;p->col=0;

h[i]=p;p->right=p;p->down=p;h[i-1]->next=p;}

h[s]->next=hm; //組成行列表頭的循環(huán)鏈表8

cout<<"三元組最多個(gè)數(shù):"<<m*n<<endl;

intt;

cout<<"輸入非零元素的個(gè)數(shù)t=?";

cin>>t;

cout<<"輸入三元組格式(以空格分開):rcv(回車)"<<endl;

for(inti=0;i<t;i++) {cout<<"輸入三元組:";cin>>r>>c>>v;p=newNode;p->row=r;p->col=c;p->val=v;q=h[r]; //在r行上尋找插入位置

while((q->right!=h[r])&&(q->right->col<c))q=q->right;p->right=q->right;q->right=p;

//插入第r行

q=h[c];//在c列上尋找插入位置

while((q->down!=cp[c])&&(q->down->row<r))q=q->down;p->down=q->down; q->down=p;

//插入第c列

}//fori}//算法結(jié)束9輸出十字鏈表-算法5.4

算法5.4包含著對(duì)十字鏈表的遍歷和查找操作。學(xué)習(xí)十字鏈表可以加深對(duì)單鏈表的認(rèn)識(shí)。voidLinkedmat::Show(){Node*p，*p1;

int

i,j;

cout<<endl<<"十字鏈表的矩陣為:“<<endl;for(i=0;i<=hm->col;i++){cout<<"\t"<<i;}//輸出各列的標(biāo)號(hào)

cout<<endl;10for(i=1,p=hm->next;p!=hm;i++)//按行輸出

{cout<<"\t"<<i; //輸出每行的標(biāo)號(hào)

for(j=1,p1=p->right;p1!=p;j++)//取每列數(shù)據(jù)

{if(j-1==p1->col){cout<<p1->val;p1=p1->right;}else{out<<"\t";}//不存在的元素，輸出跳格

}//forj

cout<<endl;p=p->next;//指向下一行表頭結(jié)點(diǎn)

}//foricout<<endl;}//算法結(jié)束輸出十字鏈表-算法5.4115.5廣義表

廣義表不同于線性表，它的元素不僅允許為基本數(shù)據(jù)類型而且也允許為廣義表。從基本數(shù)據(jù)元素的角度思考，它們之間已經(jīng)不再是單純的線性關(guān)系，而且還存在層次關(guān)系。在人工智能領(lǐng)域表處理語言LISP中，就是把廣義表作為基本的數(shù)據(jù)結(jié)構(gòu)。本節(jié)是從線性向非線性關(guān)系的過渡。125.5.1廣義表的基本概念廣義表簡稱為表，是n(n≥0)個(gè)元素的有限序列，記作：LS

=

(a1,a2,…,an)

其中，LS是廣義表的名稱;

元素ai(1≤i≤n)或者是基本數(shù)據(jù)元素，或者是廣義表;n代表中元素的個(gè)數(shù)，稱為廣義表的長度。廣義表的定義是遞歸的，廣義表中可以包含廣義表。

13廣義表的基本概念按照慣例，用英文大寫字母表示廣義表的名稱，小寫字母表示基本數(shù)據(jù)元素。某個(gè)元素ai是一個(gè)基本數(shù)據(jù)時(shí)，稱其為LS的一個(gè)原子，用小寫字母表示；當(dāng)ai不是一個(gè)基本數(shù)據(jù)元素時(shí)，則稱它為廣義表LS的子表，用大寫字母表示。當(dāng)廣義表LS非空時(shí)，稱第一個(gè)元素a1為LS的表頭（Head）；而稱其余元素組成的表(a2,…,an)為LS的表尾（Tail）。14廣義表舉例：①A=(),A是空表；表長度n為零。②B=(e),B有一個(gè)元素e，為原子；表長度為1。③C=(a,(b,c,d)),C有兩個(gè)元素，分別為原子a和子表(b,c,d)；表長度為2。④D=(A,B,C),D有三個(gè)元素都是子表；表長度3。⑤E=(a,E),E有兩個(gè)元素，一個(gè)是原子a，一個(gè)是表E；表長度為2，可以看出該表定義是遞歸的。廣義表可以共享子表，且允許遞歸。廣義表的元素之間存在次序關(guān)系，還存在層次關(guān)系。15廣義表舉例：

廣義表中元素的最大層次數(shù)為表的深度。

元素的層次就是包含該元素的括號(hào)對(duì)的數(shù)目。

A=()表A深度為0；

B=(e)表B深度為1；

C=(a,(b,c,d))表C深度為2；

D=(A,B,C)表D深度為3；

E=(a,E)

表E深度為無窮∞；16再如廣義表：F=(x,y,(z,(t)),u)

數(shù)據(jù)元素x,y和u在第一層；數(shù)據(jù)元素z在第二層；數(shù)據(jù)元素t在第三層。廣義表F深度為3。該表有4個(gè)元素，表長度為4。

A=()B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E),

又義可知，任一個(gè)非空廣義表其表頭可能是原子，也可能是表，而其表尾必定為表。例如：Head(D)=ATail(D)=(B,C)

Head(C)=aTail(C)=((b,c,d))175.5.2廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表（a1,a2,…,an）中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)(或是原子，或是表)，難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)元素用一個(gè)結(jié)點(diǎn)表示。廣義表的存儲(chǔ)結(jié)構(gòu)主要有頭尾鏈表存儲(chǔ)結(jié)構(gòu)和擴(kuò)展線性鏈表結(jié)構(gòu)兩種表示方法?，F(xiàn)僅對(duì)頭尾鏈表存儲(chǔ)結(jié)構(gòu)加以介紹

18廣義表的頭尾鏈表存儲(chǔ)結(jié)構(gòu)：若廣義表不空，可分解成表頭和表尾；一對(duì)表頭和表尾可唯一確定廣義表。①表結(jié)點(diǎn)：3個(gè)域，標(biāo)志域tag（1是表）、指向表頭的指針hp和指示表尾的指針tp。②原子結(jié)點(diǎn)：兩個(gè)域，標(biāo)志域tag（0是原子）和數(shù)據(jù)值域atom。191．廣義表元素結(jié)點(diǎn)的結(jié)構(gòu)struct

glnode{inttag; //標(biāo)志域0/1，用來區(qū)分原子和表

union //共用體

{struct

ptrtp{glnode*hp,*tp;//hp指向表頭元素，tp指向表尾

}

ptr;//對(duì)于表結(jié)點(diǎn)使用ptrcharatom;//對(duì)于原子結(jié)點(diǎn)則使用atom};};glnode*p;處理表結(jié)點(diǎn):p->tag//值為1p->ptr.hp//指向表頭p->ptr.tp//指向表尾glnode*q;處理原子點(diǎn)結(jié)：q->tag //值為0q->atom//數(shù)據(jù)元素值202．繪制廣義表的結(jié)構(gòu)圖

對(duì)于：A=()，空表僅用A=NULL來表示，而不分配結(jié)點(diǎn)，也不必畫圖。

對(duì)于：B=(e)

B指向一個(gè)表結(jié)點(diǎn)，B->tag=1。

B->ptr.hp應(yīng)指向表頭，由于表頭是基本數(shù)據(jù)元素e，它指向一個(gè)原子結(jié)點(diǎn)e。

B->ptr.tp應(yīng)指向表尾，B表尾為空，所以B->ptr.tp為NULL。由圖可以理解，該表長度為1，深度也為1。21廣義表：G=(b,c,d)

G指向一個(gè)表結(jié)點(diǎn)，G->tag=1。

G->ptr.hp應(yīng)指向表頭，G表頭是一個(gè)基本數(shù)據(jù)元素b，因此G->ptr.hp指向一個(gè)值為b的原子結(jié)點(diǎn)。

G->ptr.tp應(yīng)指向表尾，G表的表尾是除去a之外剩余元素構(gòu)成的表（b,c），所以G->ptr.tp指向一個(gè)表結(jié)點(diǎn)。設(shè)q=G->ptr.tp，因?yàn)?c,d)的表頭是c，所以q->ptr.hp指向值為c的原子結(jié)點(diǎn)。同理，q->ptr.tp應(yīng)指向（c,d）的表尾，即（d），所以q->ptr.tp也指向一個(gè)表結(jié)點(diǎn)。設(shè)p=q->ptr.tp，因?yàn)?d)的表頭是d，所以p->ptr.hp指向值為d的原子結(jié)點(diǎn)。又因?yàn)椋╠）的表尾是空，所以p->ptr.tp為空NULL。由圖可直觀地看出，該表長度為3，深度為1。建議教師不打字幕而對(duì)圖詳細(xì)講解。22廣義表：C=(a,(b,c,d))

C指向一個(gè)表結(jié)點(diǎn)，所以C->tag=1。

C->ptr.hp指向表頭，是一個(gè)值為a的原子結(jié)點(diǎn)。

C->ptr.tp指向表尾，即剩余元素(b,c,d)構(gòu)成的表((b,c,d))，因此C->ptr.tp指向一個(gè)表結(jié)點(diǎn)。因?yàn)楸?(b,c,d))的表頭素是(b,c,d)，也是G表，所以C->ptr.tp->ptr.hp指向G表。又因?yàn)楸?(b,c,d))的表尾是空，所以C->ptr.tp->ptr.tp為NULL。

C表的長度為2。表的深度為2。建議教師不打字幕而對(duì)圖詳細(xì)講解。23廣義表：D=(A,B,C)

D指向表結(jié)點(diǎn)，所以D->tag=1。

D->ptr.hp指向表頭，即是A表，所以為NULL。D->ptr.tp指向表尾，即是（B,C），所以指向一個(gè)表結(jié)點(diǎn)。

D->ptr.t