《數(shù)據(jù)結(jié)構(gòu)試驗(yàn)》講義

本文格式為Word版，下載可任意編輯——《數(shù)據(jù)結(jié)構(gòu)試驗(yàn)》講義試驗(yàn)1線性表的基本操作

試驗(yàn)編號(hào)JX020231-01

所屬院系計(jì)算機(jī)科學(xué)與技術(shù)所屬年級(jí)2023-03

所屬課程數(shù)據(jù)結(jié)構(gòu)試驗(yàn)

試驗(yàn)?zāi)康?/p>

1．把握線性表的特點(diǎn)及其存儲(chǔ)結(jié)構(gòu)2．把握線性表的基本操作

試驗(yàn)要求

1．線性表可以用順序表也可以用單鏈表實(shí)現(xiàn)，勉勵(lì)大家用兩種方式實(shí)現(xiàn)；2．創(chuàng)立線性表時(shí)，數(shù)據(jù)從鍵盤輸入整形數(shù)據(jù)；

3．線性表類型定義和或各種操作的實(shí)現(xiàn)，可以用教材給出的方法，也可以自己設(shè)計(jì)。

試驗(yàn)環(huán)境

硬件平臺(tái)：計(jì)算機(jī)CPU主頻2.0G以上；內(nèi)存128兆以上；軟件平臺(tái)：Windows2023或以上版本，VisualC++6.0。

試驗(yàn)內(nèi)容

1．用結(jié)構(gòu)體描述一個(gè)線性表；

2．創(chuàng)立線性表，在線性表中實(shí)現(xiàn)插入、刪除、按位置查找、按元素值查找和求表長(zhǎng)等操作；3．設(shè)計(jì)選擇式菜單，以選擇菜單方式進(jìn)行操作。

試驗(yàn)步驟

試驗(yàn)指導(dǎo)定義順序表

#defineLIST_INIT_SIZE100/*線性表存儲(chǔ)空間的初始分派量*/#defineLISTINCREMENT2/*線性表存儲(chǔ)空間的分派增量*/structSqList{

ElemType*elem;/*存儲(chǔ)空間基址*/intlength;/*當(dāng)前長(zhǎng)度*/

intlistsize;/*當(dāng)前分派的存儲(chǔ)容量(以sizeof(ElemType)為單位)*/};

定義算法函數(shù)

StatusInitList(SqListif(!L.elem)

exit(OVERFLOW);/*存儲(chǔ)分派失敗*/

L.length=0;/*空表長(zhǎng)度為0*/

L.listsize=LIST_INIT_SIZE;/*初始存儲(chǔ)容量*/returnOK;}

StatusListInsert(SqList

if(iL.length+1)/*i值不合法*/returnERROR;

if(L.length>=L.listsize){/*當(dāng)前存儲(chǔ)空間已滿,增加分派*/if(!(newbase=(ElemType*)realloc(

L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType))))

exit(OVERFLOW);/*存儲(chǔ)分派失敗*/L.elem=newbase;/*新基址*/

L.listsize+=LISTINCREMENT;//增加存儲(chǔ)容量}

q=L.elem+i-1;/*q為插入位置*/

for(p=L.elem+L.length-1;p>=q;--p)/*插入位置及之后的元素右移*/*(p+1)=*p;*q=e;//插入e

++L.length;/*表長(zhǎng)增1*/returnOK;}

主函數(shù)樣例

voidmain(){

SqListL;Statusi;intj;i=InitList(

printf(\初始化L后：L.elem=%uL.length=%dL.listsize=%d\\n\for(j=1;j3．從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)參與森林；4．重復(fù)（2）、（3）步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為所求得的哈夫曼樹(shù)。由已形成的哈夫曼樹(shù)求哈夫曼編碼：對(duì)每個(gè)葉結(jié)點(diǎn)都進(jìn)行如下的處理：

掃描由葉結(jié)點(diǎn)到根結(jié)點(diǎn)的各條分支，若分支中的當(dāng)前結(jié)點(diǎn)與雙親結(jié)點(diǎn)是左支關(guān)系，則生成編碼0，若分支中的當(dāng)前結(jié)點(diǎn)與雙親結(jié)點(diǎn)是右支關(guān)系，則生成編碼1，由此生成的二進(jìn)制碼的序列即為該結(jié)點(diǎn)的哈夫曼編碼。

思考題

1．用非遞歸算法實(shí)現(xiàn)二叉樹(shù)的前序、中序和后序遍歷；2．設(shè)計(jì)一個(gè)哈夫曼編碼器的譯碼系統(tǒng)。

試驗(yàn)4圖的遍歷的實(shí)現(xiàn)

試驗(yàn)編號(hào)JX020231-04所屬院系計(jì)算機(jī)科學(xué)與技術(shù)所屬年級(jí)2023-03所屬課程數(shù)據(jù)結(jié)構(gòu)試驗(yàn)

試驗(yàn)?zāi)康?/p>

1．把握?qǐng)D的鄰接矩陣、鄰接表的表示方法。2．把握建立圖的鄰接矩陣的算法。3．把握建立圖的鄰接表的算法。

4．加深對(duì)圖的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。

試驗(yàn)要求

試驗(yàn)環(huán)境

硬件平臺(tái)：計(jì)算機(jī)CPU主頻2.0G以上；內(nèi)存128兆以上；軟件平臺(tái)：Windows2023或以上版本，VisualC++6.0

試驗(yàn)內(nèi)容

1．建立圖的鄰接矩陣、鄰接表。

2．對(duì)建立好的鄰接矩陣表示的圖進(jìn)行深度優(yōu)先探尋遍歷。

試驗(yàn)步驟

試驗(yàn)指導(dǎo)

1．圖的結(jié)構(gòu)定義

#defineVMAX30/*圖中最多頂點(diǎn)數(shù)*/

typedefstructnode/*鄰接表中鏈表的結(jié)點(diǎn)類型*/{

intvno;/*鄰接頂點(diǎn)的頂點(diǎn)序號(hào)*/structnode*next;/*后繼鄰接頂點(diǎn)*/}EdgeNode;

typedefEdgeNode*lgraph[VMAX];/*鄰接表類型*/

typedefintmgraph[VMAX][VMAX];/*鄰接矩陣類型*/

intvisited[VMAX];/*訪問(wèn)標(biāo)志*/

intqueue[VMAX];/*廣度優(yōu)先探尋遍歷存儲(chǔ)隊(duì)列*/

2．函數(shù)定義

intcreate_graph(lgraphlg,mgraphmg)

/*輸入無(wú)向圖的邊，建立圖的鄰接表，鄰接矩陣*/

voidldfs(lgraphg,inti)/*鄰接表表示的圖的深度優(yōu)先探尋遍歷*/voidlbfs(lgraphg,ints,intn)/*廣度優(yōu)先探尋遍歷*/

3