數(shù)據(jù)結(jié)構(gòu)案例教程（CC++版）第2版 課件 第5章 元素?cái)U(kuò)展的線性表：矩陣和廣義表

第5章元素?cái)U(kuò)展的線性表：

矩陣和廣義表個(gè)性化推薦系統(tǒng)中的用戶評(píng)分表導(dǎo)學(xué)問題1矩陣的基本操作⑴存?。航o定一組下標(biāo)，讀出對(duì)應(yīng)的數(shù)組元素；⑵修改：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)組元素。存取和修改操作本質(zhì)上只對(duì)應(yīng)一種操作——尋址矩陣應(yīng)該采用何種方式存儲(chǔ)？矩陣沒有插入和刪除操作，所以，不用預(yù)留空間，適合采用順序存儲(chǔ)。知識(shí)學(xué)習(xí)——矩陣的基本概念設(shè)一維數(shù)組的下標(biāo)的范圍為閉區(qū)間［l，h］，每個(gè)數(shù)組元素占用c個(gè)存儲(chǔ)單元，則其任一元素ai的存儲(chǔ)地址可由下式確定：Loc(ai)＝Loc(al)＋(i－l)×c

calai-1ai……ahal+1……Loc(al)Loc(ai)知識(shí)學(xué)習(xí)——矩陣的存儲(chǔ)結(jié)構(gòu)常用的映射方法有兩種：按行優(yōu)先：先行后列，先存儲(chǔ)行號(hào)較小的元素，行號(hào)相同者先存儲(chǔ)列號(hào)較小的元素。

按列優(yōu)先：先列后行，先存儲(chǔ)列號(hào)較小的元素，列號(hào)相同者先存儲(chǔ)行號(hào)較小的元素。

二維數(shù)組內(nèi)存二維結(jié)構(gòu)一維結(jié)構(gòu)知識(shí)學(xué)習(xí)——矩陣的存儲(chǔ)結(jié)構(gòu)l2h2

l1h1(a)二維數(shù)組aij前面的元素個(gè)數(shù)=陰影部分的面積=整行數(shù)×每行元素個(gè)數(shù)+本行中aij前面的元素個(gè)數(shù)=(i

-l1)×(h2

-l2＋1)＋(j

-l2)本行中aij前面的元素個(gè)數(shù)每行元素個(gè)數(shù)整行數(shù)aij按行優(yōu)先存儲(chǔ)的尋址知識(shí)學(xué)習(xí)——矩陣的存儲(chǔ)結(jié)構(gòu)第l1行第l1+1行al1l2…al1h2a(l1+1)l2…a(l1+1)h2……aij…ah1h2Loc(aij)Loc(al1l2)(i

-l1)×(h2

-l2＋1)＋(j

-l2)個(gè)元素Loc(aij)＝Loc(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c按列優(yōu)先存儲(chǔ)的尋址方法與此類似。知識(shí)學(xué)習(xí)——矩陣的存儲(chǔ)結(jié)構(gòu)按行優(yōu)先存儲(chǔ)的尋址知識(shí)學(xué)習(xí)——特殊矩陣的壓縮存儲(chǔ)特殊矩陣：包括對(duì)稱矩陣、三角矩陣、對(duì)角矩陣和稀疏矩陣等。

稀疏矩陣：矩陣中有很多零元素。壓縮存儲(chǔ)的基本思想是：為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配存儲(chǔ)空間。3647862842481697460582957A＝對(duì)稱矩陣特點(diǎn)：aij=aji如何壓縮存儲(chǔ)？只存儲(chǔ)下三角部分的元素。特殊矩陣的壓縮存儲(chǔ)——對(duì)稱陣(a)下三角矩陣(b)存儲(chǔ)說明(c)計(jì)算方法aij在一維數(shù)組中的序號(hào)=陰影部分的面積=

i×(i-1)/2+j-1∵一維數(shù)組下標(biāo)從0開始∴aij在一維數(shù)組中的下標(biāo)k=i×(i-1)/2+j-1

1…

in-11

…j…n-1

aij每行元素個(gè)數(shù)12…iaij在本行中的序號(hào)aij第1行第2行…第i-1行特殊矩陣的壓縮存儲(chǔ)——對(duì)稱陣對(duì)于下三角中的元素aij（i≥j），在數(shù)組SA中的下標(biāo)k與i、j的關(guān)系為：k＝i×(i-1)/2＋j-1。上三角中的元素aij（i＜j），因?yàn)閍ij＝aji，則訪問和它對(duì)應(yīng)的元素aji即可，即：k＝j(luò)×(j-1)/2＋i-1

。第2行第n行第1行

a11

a21

a22

a31

a32

a33

aij…

a

n1

an2…ann…第3行012345kn(n+1)/2-1特殊矩陣的壓縮存儲(chǔ)——對(duì)稱陣3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩陣如何壓縮存儲(chǔ)？只存儲(chǔ)上三角（或下三角）部分的元素。特殊矩陣的壓縮存儲(chǔ)——三角陣矩陣中任一元素aij在數(shù)組中的下標(biāo)k與i、j的對(duì)應(yīng)關(guān)系：i×(i-1)/2＋j-1

當(dāng)i≥jn×(n＋1)/2當(dāng)i＜jk=012345

k

n(n+1)/2第2行第1行

a11

a21

a22

a31

a32

aij…ann…第3行

c

a33存儲(chǔ)下三角元素對(duì)角線上方的常數(shù)——只存一個(gè)特殊矩陣的壓縮存儲(chǔ)——三角陣矩陣中任一元素aij在數(shù)組中的下標(biāo)k與i、j的對(duì)應(yīng)關(guān)系：

(i-1)×(2n－i＋2)/2＋j－i

當(dāng)i≤jn×(n＋1)/2當(dāng)i＞jk=存儲(chǔ)上三角元素對(duì)角線上方的常數(shù)——只存一個(gè)特殊矩陣的壓縮存儲(chǔ)——三角陣按行存儲(chǔ)元素aij在一維數(shù)組中的序號(hào)=3(i－1)-1+(

j－i+1)=2i+j-3

∵一維數(shù)組下標(biāo)從0開始∴元素aij在一維數(shù)組中的下標(biāo)=2i+j-3(b)尋址的計(jì)算方法(c)壓縮到一維數(shù)組中a11a12a21a22a23a32a33a34a43a44a45a54a550123456789101112(a)三對(duì)角矩陣

0

00

000

000

000

A=a11a12a21a22

a23a32a33

a34a43a44

a45a54a55特殊矩陣的壓縮存儲(chǔ)——對(duì)角矩陣1500000

0110000

000600

0000009

00000A=如何只存儲(chǔ)非零元素？注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。特殊矩陣的壓縮存儲(chǔ)——稀疏矩陣typedefstruct{

inti,j;

ElemTypee;}Triple;將稀疏矩陣中的每個(gè)非零元素表示為：(行號(hào)，列號(hào)，非零元素值)——三元組定義三元組：稀疏矩陣的壓縮存儲(chǔ)——三元組順序表typedefstruct{

Tripledata[MAXSIZE];

intmu,nu,tu;}SparseMatrix;定義三元組順序表：三元組表：將稀疏矩陣的非零元素對(duì)應(yīng)的三元組所構(gòu)成的集合，按行優(yōu)先的順序排列成一個(gè)線性表。三元組表＝((0,0,15),(1,1,11),(2,3,6),(4,0,9))1500000

0110000

000600

0000009

00000A=如何存儲(chǔ)三元組表？稀疏矩陣的壓縮存儲(chǔ)——三元組順序表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表1500220-15

0113000

000600

00000091

00000A=三元組順序表是否需要預(yù)留存儲(chǔ)空間？稀疏矩陣的修改操作三元組順序表的插入/刪除操作稀疏矩陣的壓縮存儲(chǔ)——三元組順序表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑

ije0123456MAXSIZE-11500220-15

0113000

000600

00000091

00000A=7（非零元個(gè)數(shù)）是否對(duì)應(yīng)惟一的稀疏矩陣？5（矩陣的行數(shù)）6（矩陣的列數(shù)）稀疏矩陣的壓縮存儲(chǔ)——三元組順序表創(chuàng)建基于三元組順序表結(jié)構(gòu)的稀疏矩陣:voidCreateMatrix(SparseMatrix&M){ cout<<"請(qǐng)輸入矩陣行數(shù)："; cin>>M.mu; cout<<"請(qǐng)輸入矩陣列數(shù)："; cin>>M.nu; cout<<"請(qǐng)輸入非零元素個(gè)數(shù)："; cin>>M.tu; cout<<"請(qǐng)輸入非零元素（輸入格式為：行號(hào)列號(hào)元素值）：\n"; for(intp=0;p<M.tu;p++) cin>>M.data[p].i>>M.data[p].j>>M.data[p].e;}稀疏矩陣的壓縮存儲(chǔ)——三元組順序表采用鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表，每個(gè)非零元素對(duì)應(yīng)的三元組存儲(chǔ)為一個(gè)鏈表結(jié)點(diǎn)，結(jié)構(gòu)為：ijedownrighti：存儲(chǔ)非零元素的行號(hào)j：存儲(chǔ)非零元素的列號(hào)e：存儲(chǔ)非零元素的值right：指針域，指向同一行中的下一個(gè)三元組down：指針域，指向同一列中的下一個(gè)三元組稀疏矩陣的壓縮存儲(chǔ)——十字鏈表

312∧M=300501002000

113

145∧∧

221∧∧∧∧稀疏矩陣的壓縮存儲(chǔ)——十字鏈表按矩陣形式顯示基于三元組順序表結(jié)構(gòu)的稀疏矩陣:voidShowMatrix(SparseMatrixM){ intk=0;//記錄遍歷到的非零元素個(gè)數(shù) for(inti=1;i<=M.mu;i++) { for(intj=1;j<=M.nu;j++) { if(k==M.tu) k=0; if(i==M.data[k].i&&j==M.data[k].j&&k<M.tu) { cout<<M.data[k].e<<"\t"; k++; } else cout<<"0"<<"\t"; } cout<<endl; }}知識(shí)應(yīng)用——導(dǎo)學(xué)問題1的實(shí)現(xiàn)例：15000910110000300022060000000-150000B=1500220-15

0113000

000600

00000091

00000A=知識(shí)拓展——稀疏矩陣轉(zhuǎn)置

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

1

1

15

1

591

2211

323

4122

436

61-15

空空空閑閑閑0123456MAXSIZE-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）知識(shí)拓展——稀疏矩陣轉(zhuǎn)置

ije

ije知識(shí)拓展——稀疏矩陣轉(zhuǎn)置基本思想：在A的三元組順序表中依次找第1列、第2列、…直到最后一列的三元組，并將找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到B的三元組順序表中。

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0123456MAXSIZE-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）知識(shí)拓展——稀疏矩陣轉(zhuǎn)置

ije

ije0123456MAXSIZE-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0123456MAXSIZE-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）在矩陣A中查找第1列非零元，順序存儲(chǔ)到矩陣B中

1115

1591

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0123456MAXSIZE-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

1115

1591

2211在矩陣A中查找第2列非零元，順序存儲(chǔ)到矩陣B中

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0123456MAXSIZE-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

1115

1591

2211

323在矩陣A中查找第3列非零元，順序存儲(chǔ)到矩陣B中

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0123456MAXSIZE-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

1115

1591

2211

323

4122

436在矩陣A中查找第4列非零元，順序存儲(chǔ)到矩陣B中

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0123456MAXSIZE-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

1115

1591

2211

323

436在矩陣A中查找第5列非零元，順序存儲(chǔ)到矩陣B中

4122

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0123456MAXSIZE-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

1115

1591

2111

323

4122

436

61-15在矩陣A中查找第6列非零元，順序存儲(chǔ)到矩陣B中

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0123456MAXSIZE-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

1115

1591

2211

323

4122

436

61-15在矩陣A中查找第7列非零元，順序存儲(chǔ)到矩陣B中

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑1.設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元個(gè)數(shù)；2.在B中設(shè)置初始存儲(chǔ)位置q；3.for(col=最小列號(hào);col<=最大列號(hào);col++)3.1在A中查找列號(hào)為col的三元組；3.2交換其行號(hào)和列號(hào)，存入B中q位置；3.3q++；三元組順序表操作——轉(zhuǎn)置算法1三元組順序表操作——轉(zhuǎn)置算法1該算法的主要時(shí)間耗費(fèi)是在col和p的兩重循環(huán)上。對(duì)于一個(gè)m行n列且非零元素個(gè)數(shù)為t的稀疏矩陣而言，該算法的時(shí)間復(fù)雜度為O(tn)。最壞情況是，當(dāng)稀疏矩陣中的非零元素個(gè)數(shù)t與mn同數(shù)量級(jí)時(shí)，上述算法的時(shí)間復(fù)雜度就為O(mn2)。顯然這種情況下，該樸素算法效率較低。分析：A中第0列的第一個(gè)非零元素一定存儲(chǔ)在B中下標(biāo)為0的位置上，該列中其它非零元素應(yīng)存放在B中后面連續(xù)的位置上，那么第1列的第一個(gè)非零元素在B中的位置便等于第0列的第一個(gè)非零元素在B中的位置加上第0列的非零元素的個(gè)數(shù)，以此類推。基本思想：順序取，直接存。即在A中依次取三元組，交換其行號(hào)和列號(hào)放到B中適當(dāng)位置。如何確定當(dāng)前從A中取出的三元組在B中的位置？三元組順序表操作——轉(zhuǎn)置算法2

0123456MAXSIZE-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

1115

1591

2211

323

4122

436

61-15第1列第1個(gè)非零元素第1列有2個(gè)非零元素第2列第2個(gè)非零元素三元組順序表操作——轉(zhuǎn)置算法2觀察轉(zhuǎn)置后矩陣的三元組順序表

ije引入兩個(gè)數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：cnum[cols]：存儲(chǔ)矩陣A中某列的非零元素的個(gè)數(shù)；cpot[clos]：初值表示矩陣A中某列的第一個(gè)非零元素在B中的位置。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：cpot[1]=0；cpot[col]=cpot[col-1]+cnum[col-1]；1<col<=cols-1cnum與cpot存在如下遞推關(guān)系：三元組順序表操作——轉(zhuǎn)置算法2

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑ije0123456MAXSIZE-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

col123456cnum[col]21

12

01cpot[col]

023466根據(jù)矩陣A計(jì)算cnum和cpot

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]cpot[6]

1115cpot[1]

ije

ije01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[2]cpot[3]cpot[4]cpot[5]cpot[6]

1115cpot[1]

4122cpot[4]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[2]cpot[3]cpot[5]

1115cpot[1]

4122cpot[4]

61-15cpot[6]cpot[6]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[2]cpot[3]cpot[5]

1115cpot[1]

4122cpot[4]

61-15cpot[6]

2211cpot[2]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[3]cpot[5]

1115cpot[1]

4122cpot[4]

61-15cpot[6]

2211cpot[2]

323cpot[3]cpot[2]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[5]

1115cpot[1]

4122cpot[4]

61-15cpot[6]

2211

323cpot[3]cpot[2]

436cpot[4]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[5]

1115cpot[1]

4122

61-15cpot[6]

2211

323cpot[3]cpot[2]

436cpot[4]

1591cpot[1]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑1.設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)；2.計(jì)算A中每一列的非零元素個(gè)數(shù)；3.計(jì)算A中每一列的第一個(gè)非零元素在B中的下標(biāo)；4.依次取A中的每一個(gè)非零元素對(duì)應(yīng)的三元組；4.1確定該元素在B中的下標(biāo)q；4.2將該元素的行號(hào)列號(hào)交換后存入B中q的位置；4.3預(yù)置該元素所在列的下一個(gè)元素的存放位置；三元組順序表操作——轉(zhuǎn)置算法2三元組順序表操作——轉(zhuǎn)置算法2該算法中有4個(gè)平行的for循環(huán)。對(duì)于一個(gè)m行n列且非零元素個(gè)數(shù)為t的稀疏矩陣而言，循環(huán)次數(shù)分別為n和t兩種，故此算法時(shí)間復(fù)雜度為O(n+t)。顯然該算法優(yōu)于轉(zhuǎn)置算法1。為培養(yǎng)本科生的綜合實(shí)踐與研究創(chuàng)新能力，從國家到各高校都實(shí)施了大學(xué)生創(chuàng)新實(shí)踐項(xiàng)目。在項(xiàng)目實(shí)施過程中，教師指導(dǎo)n個(gè)本科生，如果教師是碩導(dǎo)或博導(dǎo)，本科生可接收教師的直接指導(dǎo)，部分本科生也可以在碩士研究生或博士研究生的指導(dǎo)下進(jìn)行項(xiàng)目研究。本科生創(chuàng)新實(shí)踐項(xiàng)目中的人員關(guān)系具有如下形式：（1）若導(dǎo)師不帶研究生：

(導(dǎo)師,(本科生1,…,本科生k))（2）若導(dǎo)師帶研究生：

(導(dǎo)師,((研究生1,(本科生1,…,本科生m)),(本科生1,…,本科生n),…))請(qǐng)?jiān)O(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)以上人員關(guān)系，為簡單起見，各類人員信息僅保留姓名。問題：本科生創(chuàng)新實(shí)踐項(xiàng)目中的人員關(guān)系(本科生1,…,本科