數(shù)據(jù)實(shí)驗(yàn)報(bào)告9篇

篇一 數(shù)據(jù)庫實(shí)驗(yàn)報(bào)告

數(shù)據(jù)庫實(shí)驗(yàn)報(bào)告

課 程 實(shí) 驗(yàn) 報(bào) 告

課程名稱：

學(xué) 號：

v202341129

姓 名：

吳光藝

指導(dǎo)老師：

胡 侃

專業(yè)班級：

計(jì)算機(jī)1402班

報(bào)告日期：

2023年4月22日

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

一．實(shí)驗(yàn)?zāi)康?/p>

1.通過對某個數(shù)據(jù)庫管理系統(tǒng)的安裝使用，初步了解dbms的工作環(huán)境和系統(tǒng)架構(gòu)

2.熟悉通過sql對數(shù)據(jù)庫進(jìn)行操作，完成下面的sql語句

3.學(xué)習(xí)系統(tǒng)的備份功能，學(xué)習(xí)系統(tǒng)的身份、權(quán)限配置操作，了解系統(tǒng)的查詢性能分析功能。

4.熟悉通過sql對數(shù)據(jù)進(jìn)行完整性檢查性控制

二．實(shí)驗(yàn)平臺

操作系統(tǒng)：win7 數(shù)據(jù)庫管理系統(tǒng)：

server2023r2 交互式查詢語言：sql語言

三．實(shí)驗(yàn)要求

1.在rdbms中建立一個數(shù)據(jù)庫，進(jìn)行實(shí)驗(yàn)所要求的各種操作，所有的sql操作均在此建立的的新數(shù)據(jù)庫進(jìn)行

(轉(zhuǎn) 載于: 酷貓寫作范文網(wǎng))

2.根據(jù)一下要求認(rèn)真進(jìn)行實(shí)驗(yàn)，記錄所有的實(shí)驗(yàn)用例 數(shù)據(jù)定義：基本表的創(chuàng)建，修改和刪除，視圖的創(chuàng)建和刪除。

數(shù)據(jù)操作：完成各類查詢操作（單表查詢，連接查詢，嵌套查詢，集合查詢）；完成各類更新操作（插入數(shù)據(jù)，刪除數(shù)據(jù)，思想?yún)R報(bào)專題修改數(shù)據(jù)，增加數(shù)據(jù)）

視圖的操作：視圖的定義（創(chuàng)建和刪除），查詢，更新（注意更新的條件） 3.使用sql對數(shù)據(jù)進(jìn)行完整性控制（觸發(fā)器），用實(shí)例證實(shí)，當(dāng)操作違反了完整性約束條件時，系統(tǒng)是如何處理的

四．實(shí)驗(yàn)內(nèi)容

1．sql練習(xí)部分：

創(chuàng)建三個關(guān)系：

商品表商品名稱、商品類型

goodsgname char（20）,gtype char（10）

主關(guān)鍵字為（商品名稱）。商品類型為（電器、文具、服裝。。。）

商場商場名稱,所在地區(qū)

plazapname char（20），parea char（20）

主關(guān)鍵字為商場名稱。所在地區(qū)為（洪山、漢口、漢陽、武昌。。。）

銷售價格表商品名稱、商場名稱、當(dāng)前銷售價格、目前舉辦活動類型

salegname

（10）

主關(guān)鍵字為（商品名稱、商場名稱）。舉辦活動類型為（送券、打折），也可為空值，表示當(dāng)前未舉辦任何活動。表中記錄如（‘哈森皮靴’，‘亞貿(mào)廣場’，200，‘打折’），同一商場針對不同的商品可能采取不同的促銷活動。

create table goods

(

gname char(20) primary key,gtype char(10) char（20），pname char（20），price float，atype char

);

--主關(guān)鍵字為（商品名稱）。商品類型為（電器、文具、服裝。。。）

create table plaza

(

pname char(20) primary key,parea char(20)

)；---- 商場商場名稱,所在地區(qū)

create table sale

(

gname char(20),pname char(20),

price float,

atype char(10),

primary key(gname,pname),foreign key(gname) references goods(gname),foreign key(pname) references plaza(pname)

--銷售價格表商品名稱、酷貓寫作范文網(wǎng)商場名稱、當(dāng)前銷售價格、目前舉辦活動類型 )；

insert into goods values ('電風(fēng)扇','電器');

insert into goods values('電腦','電器');

insert into goods values('彩電','電器');

insert into goods values('空調(diào)','電器');

insert into goods values('熱水器','電器');

insert into goods values('鋼筆','文具');

insert into goods values('練習(xí)本','文具');

insert into goods values('墨水','文具');

insert into goods values('書包','文具');

insert into goods values('橡皮','文具');

insert into goods values('西裝','服裝');

insert into goods values('襯衣','服裝');

insert into goods values('裙子','服裝');

insert into goods values('內(nèi)褲','服裝');

insert into plaza values('蘇寧','洪山');

insert into plaza values('國美','洪山');

insert into plaza values('中百','洪山');

insert into plaza values('國泰','洪山');

insert into plaza values('家樂福','漢口');

insert into plaza values('大洋百貨','武昌');

insert into plaza values('武商','武昌');

insert into sale values('電風(fēng)扇','蘇寧',258,'打折');

insert into sale values('電風(fēng)扇','國美',288,'送券');

insert into sale values('電風(fēng)扇','中百',288,'');

insert into sale values('電風(fēng)扇','國泰',275,'送券');

insert into sale values('電風(fēng)扇','家樂福',188,'');

insert into sale values('電腦','蘇寧',5000,'打折');

insert into sale values('電腦','國美',5200,'');

insert into sale values('電腦','中百',6400,'打折');

insert into sale values('電腦','國泰',5800,'送券');

insert into sale values('彩電','蘇寧',2700,'打折');

insert into sale values('彩電','國美',2300,'送券');

insert into sale values('彩電','大洋百貨',2900,'');

insert into sale values('熱水器','蘇寧',888,'打折');

insert into sale values('熱水器','國美',488,'打折');

insert into sale values('熱水器','中百',570,'');

insert into sale values('熱水器','大洋百貨',620,'送券');

insert into sale values('鋼筆','中百',1,'打折');

insert into sale values('鋼筆','大洋百貨',5,'');

insert into sale values('鋼筆','家樂福',3,'打折');

insert into sale values('練習(xí)本','中百',12,'送券');

insert into sale values('練習(xí)本','國泰',13,'');

insert into sale values('練習(xí)本','家樂福',6,'');

insert into sale values('墨水','中百',8,'送券');

insert into sale values('墨水','國泰',10,'打折');

insert into sale values('墨水','武商',15,'');

范文寫作下頁

數(shù)據(jù)庫實(shí)驗(yàn)報(bào)告

insert into sale values('書包','中百',88,'打折');

insert into sale values('書包','家樂福',88,'');

insert into sale values('書包','武商',188,'打折');

insert into sale values('橡皮','中百',2,'打折');

insert into sale values('橡皮','家樂福',5,'');

insert into sale values('長褲','中百',188,'打折');

insert into sale values('長褲','家樂福',388,'打折');

insert into sale values('長褲','武商',590,'');

insert into sale values('長褲','國泰',288,'送券');

insert into sale values('短袖','中百',188,'');

insert into sale values('短袖','家樂福',459,'');

insert into sale values('短袖','武商',118,'');

insert into sale values('短袖','國泰',268,'');

insert into sale values('裙子','中百',288,'打折');

insert into sale values('裙子','家樂福',488,'');

insert into sale values('裙子','武商',588,'送券');

insert into sale values('裙子','國泰',128,'');

insert into sale values('短褲','中百',99,'');

insert into sale values('短褲','家樂福',118,'打折');

insert into sale values('短褲','武商',198,'');

insert into sale values('短褲','國泰',88,'');

update sale

set atype='null'

where atype='

';

6

table goods

table plaza

table sale

7

(轉(zhuǎn)載于: 在點(diǎn) 網(wǎng))

2．?dāng)?shù)據(jù)更新：范文top100

1）向上述表格中用sql語句完成增、刪、改的操作；

2）編寫一個觸發(fā)器，并測試該觸發(fā)器；

3）將sale表中的打折記錄插入到新表sale_cheap中，并基于sale_cheap表創(chuàng)建一個統(tǒng)計(jì)每個商場各自打折商品平均價格的視圖。

create table sale_cheap

8

(

gname char(20),pname char(20),

price float,

insert into sale_cheap(gname,pname,price,atype)

select gname,pname,price,atype

from sale

where atype='打折';

create view pxsale(pname,avg_price)

as

select pname,avg(price)

from sale_cheap

group by pname atype char(10),primary key(gname,pname),foreign key(gname) references goods(gname),foreign key(pname) references plaza(pname)

9

3．用sql語句完成下述查詢需求：

1）查詢所有以“打折”方式銷售的商品的當(dāng)前銷售情況，并按照價格的降序排列；select gname,price

from sale

where atype='打折'

order by price desc;

2）查詢所有沒有任何活動的商品及其所在的商場，結(jié)果按照商品排序；

10

上頁 下頁

數(shù)據(jù)庫實(shí)驗(yàn)報(bào)告

select gname,pname

from sale

where atype=null

order by gname;

3）查詢價格在200～500元之間的商品名稱、所在的商場名稱、價格，結(jié)果按照商場名稱排序；

select gname,pname,price

from sale

where price between 200 and 500

order by pname;

4）查詢每種商品的最低價格、商品名稱；

select gname,min(price)

from sale

group by gname;

5）查詢以“送券”方式銷售的商品總數(shù)超過30種的商場名稱；

select pname

from sale

where atype='送券'

group by pname having count(*)>;15

6）查詢以“送券”方式銷售的商品總數(shù)超過30種的商場所在地區(qū)；

select parea

from plaza

where plaza.pname in

(

select sale.pname

from sale

where atype='送券'

group by sale.pname having count(*)>;

7）查詢價格為下列取值之一的商品名稱、所在商場名稱、目前舉辦活動的類型，（88、188、288、388、488、588、888）；

select gname,pname,atype

from sale

where price in(88,188,288,388,488,588,888)

8）查詢以“老”字開頭的所有商品的名稱；(ps:由于三個關(guān)系設(shè)計(jì)的時候沒有注意題目的要求，所以沒有符合的選項(xiàng)，故自己有另外建了一個)

create table goods

(

gname char(20) primary key,gtype char(10)

);

--主關(guān)鍵字為（商品名稱）。商品類型為（電器、文具、服裝。。。）

insert into goods values ('電風(fēng)扇','電器');

insert into goods values('電視','電器');

insert into goods values('冰箱','電器');

insert into goods values('老花鏡','電器');

insert into goods values('老干媽','電器');

select *

from goods

where gname like '老

%';

9）查詢同時銷售“剃須刀”和“電池”的商場名稱；

select s1.pname

from sale s1,sale s2

where s1.pname=s2.pname and s1.gname='剃須刀'

and s2.gname='電池'

10）查詢不舉辦任何活動的商場；

select distinct pname

from sale

except

select distinct pname

from sale

where atype is not null;

11）查詢所銷售的商品包含了“校園超市”所銷售的所有商品的商場名稱。

select distinct pname

from sale sx

where not exists

(select * from sale sy where pname='校園超市'

and not exists ( select * from sale sz where sz.pname=sx.pname and sz.gname=sy.gname));

2．軟件功能學(xué)習(xí)部分

（1）學(xué)習(xí)系統(tǒng)的備份功能。

利用sql server本身帶有的備份功能（dts）把數(shù)據(jù)庫全部或者差額定時備份到某個目錄，一旦備份成功，這時候在指定的備份目錄下有.bak文件存在，選擇sqlserver 服務(wù)器的數(shù)據(jù)庫，單擊鼠標(biāo)右鍵，選擇“所有任務(wù)”選“備份數(shù)據(jù)庫”即可

（2）學(xué)習(xí)系統(tǒng)的身份、權(quán)限配置操作。

打開“ssms—sql server實(shí)例—安全性—登錄名”，右鍵選擇“新建登錄名”，選擇身份驗(yàn)證模式（身份驗(yàn)證模式不同，帳戶類型也不一樣，），輸入名字，并為該用戶選擇一個默認(rèn)數(shù)據(jù)庫（比如默認(rèn)為master數(shù)據(jù)庫）。該賬戶建立好之后，建立數(shù)據(jù)庫用戶，以便用戶可以訪問數(shù)據(jù)庫，對數(shù)據(jù)庫進(jìn)行操作。我們在建立數(shù)據(jù)庫用戶時，其實(shí)就是映射登錄用戶，所以在一般情況下，我們的登錄名和數(shù)據(jù)庫用戶名是一致的。操作方法：打開“ssms—sql server實(shí)例—具體的數(shù)據(jù)庫—安全性—數(shù)據(jù)庫用戶”；最后是在具體的數(shù)據(jù)庫對象（比如表）上授予具體的權(quán)限，三種權(quán)限：授予、回收、拒絕。

上頁 下頁

數(shù)據(jù)庫實(shí)驗(yàn)報(bào)告

（3）了解系統(tǒng)的查詢性能分析功能。

查詢優(yōu)化有下面3種方法：

a建立索引，建立“適當(dāng)”的索引是實(shí)現(xiàn)查詢優(yōu)化的首要前提；

b重寫sql語句（即重寫查詢語句），sql server中有一個“查詢分析優(yōu)化器”，它可以計(jì)算出where子句中的搜索條件并確定哪個索引能縮小表掃描的搜索空間，也就是說，它能實(shí)現(xiàn)自動優(yōu)化；

c其他優(yōu)化方法（調(diào)整參數(shù)，建立視圖，臨時表等）

五．實(shí)驗(yàn)體會 通過數(shù)據(jù)庫的多次的上機(jī)實(shí)驗(yàn)，使我對數(shù)據(jù)庫以及sql語言有了一個更透徹的理解，對以前上課學(xué)習(xí)到的知識有了更深的認(rèn)識，通過自己上機(jī)實(shí)驗(yàn)，對很多以前不是很清楚很明白的問題也有了更清醒的認(rèn)識，在各種不同的環(huán)境中，也能夠適時作出相應(yīng)的調(diào)整，在某種程度上提高了自己對知識的領(lǐng)悟能力和學(xué)習(xí)能力。

通過這次設(shè)計(jì)，我受益非淺，親身體驗(yàn)了數(shù)據(jù)庫設(shè)計(jì)的全過程，在實(shí)踐中了解了數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)的步驟、流程以及思路，增長了在數(shù)據(jù)庫設(shè)計(jì)方面的見識，我深刻認(rèn)識到以前所學(xué)的基礎(chǔ)課程的重要性，也使我們掌握了很多新知識，特別是一些課本之外的知識，體會到了理論知識和實(shí)踐相結(jié)合的重要性。

16

上頁

篇二 數(shù)據(jù)庫課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告

數(shù)據(jù)庫課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告

導(dǎo)語：通過本課程設(shè)計(jì)，培養(yǎng)學(xué)生具有c/s模式的數(shù)據(jù)庫應(yīng)用軟件系統(tǒng)的設(shè)計(jì)和開發(fā)能力。以下是小編為大家整理的數(shù)據(jù)庫課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告，歡迎大家閱讀與借鑒！

數(shù)據(jù)庫課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告（1）

有關(guān)于數(shù)據(jù)庫實(shí)驗(yàn)的心得體會，總的來說，受益匪淺。在這些天中，我們學(xué)到了很多東西，包括建表，導(dǎo)入數(shù)據(jù)，查詢，插入。最重要的是我們有機(jī)會用電腦自己進(jìn)行實(shí)踐，沒接觸的時候總是覺得它比較深奧或是不可接近的新型語言，盡管自己對c語言非常感興趣，但還是有些心理上的陌生感。學(xué)習(xí)數(shù)據(jù)庫就和我們平時的其它科目學(xué)習(xí)一樣感覺它有永無止境的知識，數(shù)據(jù)庫是我在高中時候聽過，到了大學(xué)漸漸了解了些，但就其原理性的內(nèi)容還不知道，也就是根本就不清楚什么是數(shù)據(jù)庫，只是知道一個所謂的中國字典里的名詞。我認(rèn)識它是從我接觸實(shí)驗(yàn)運(yùn)作開始的，剛開始就是建立數(shù)據(jù)庫，兩種驗(yàn)證模式，沒什么東西但還覺得不錯。進(jìn)而就是操作語言了，緊接著就是觸發(fā)器的使用，進(jìn)而對數(shù)據(jù)庫高級的使用，等等。 開始知道數(shù)據(jù)庫的時候想學(xué)，不知道從何而起，不懂的話怎么問，從什么地方學(xué)起。后來到大三開學(xué)后有數(shù)據(jù)庫原理必修課，非常高興。當(dāng)時感覺sql sever數(shù)據(jù)庫管理既然是單獨(dú)一門課程一定會講的比較細(xì)，也能學(xué)到真正實(shí)用的內(nèi)容。學(xué)了這門課以后發(fā)現(xiàn)和我想的基本是一樣的，老師對學(xué)生也比較和藹可親，對我們要求也不是很緊。讓每個人都覺得輕輕松松就能把這門課程學(xué)完，沒有多么緊張的作業(yè)，也沒有太苛刻的要求。

當(dāng)老師在最后說這個課程結(jié)束了，回顧一下以前老師給我們講過的東西，真的有很多是我們應(yīng)該去注意的。學(xué)習(xí)完sql sever數(shù)據(jù)庫后感覺可分兩大塊，一塊是開發(fā)，一塊是管理。開發(fā)主要是寫寫存儲過程、觸發(fā)器什么的，還有就是用oracle的develop工具做form。有點(diǎn)類似于程序員。開發(fā)還需要有較強(qiáng)的邏輯思維和創(chuàng)造能力，自己沒有真正做過，但感覺應(yīng)該會比較辛苦，是青春飯；管理則需要對sql sever數(shù)據(jù)庫的原理有深刻的認(rèn)識，有全局操縱的能力和緊密的思維，責(zé)任較大，因?yàn)橐粋€小的失誤就會弄掉整個數(shù)據(jù)庫，相對前者來說，后者更看重經(jīng)驗(yàn)。這些東西都是從老師哪里和朋友的討論中得到的心得，也希望其他朋友能多多向老師和朋友請教，如果是個人單獨(dú)靠自己來完成一個完美的數(shù)據(jù)庫我覺得比較困難，現(xiàn)在基本上都是團(tuán)隊(duì)類型的，而且他們的效率高開發(fā)的周期也快。由于數(shù)據(jù)庫管理的責(zé)任重大，很少公司愿意請一個剛剛接觸sql sever的人去管理數(shù)據(jù)庫。對于我們這些初出茅廬的新手而且電子商務(wù)的專業(yè)，個人認(rèn)為可以先選擇做管理，有一定經(jīng)驗(yàn)后轉(zhuǎn)型，去做數(shù)據(jù)庫的開發(fā)。當(dāng)然，這個還是要看人個的實(shí)際情況來定。

sql server數(shù)據(jù)庫的實(shí)驗(yàn)學(xué)習(xí)使我對數(shù)據(jù)庫的有了新的進(jìn)步，以后再看到也就不至于什么也不懂，其實(shí)那么多數(shù)據(jù)庫我覺得學(xué)好一門就行，只是他們的語言可能不大一樣，學(xué)好一門后就可去認(rèn)識其它的，這樣應(yīng)該有事半功倍的效果。就像我學(xué)習(xí)c語言，當(dāng)時不能說是學(xué)習(xí)的棒，但不算差。所以我對以后的語言感覺都不是很困難，了解了vb、c++還有網(wǎng)頁中用的html語言、asp語言都能看懂，起碼可以對別人的東西進(jìn)行了一下修改。因此，我感謝數(shù)據(jù)庫老師給了我有用的知識，以便我在以后學(xué)習(xí)或認(rèn)識更多的內(nèi)容能有新的方法和思維，也能更加有效和快速的去消化吸收新的`東西。希望在今后中，sql server能給我更多幫助。感謝學(xué)校開設(shè)這樣一門優(yōu)秀使用的課程，讓我對數(shù)據(jù)庫有了更深的了解。

數(shù)據(jù)庫課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告（2）

由于平時接觸的都是一些私人項(xiàng)目，這些項(xiàng)目大都是一些類庫，其他人的交流相對可以忽略不計(jì)，因此也就不考慮規(guī)范化的文檔。實(shí)際上從學(xué)習(xí)的經(jīng)歷來看，我們接觸的知識體系都是屬于比較老或比較傳統(tǒng)的，與現(xiàn)在發(fā)展迅速的it行業(yè)相比很多情況已不再適用，尤其是當(dāng)開源模式逐漸走近開發(fā)者后更是如此。

雖然這次是一個數(shù)據(jù)庫課程設(shè)計(jì)，由于本人在選擇項(xiàng)目的時候是本著對自己有實(shí)際應(yīng)用價值的角度考慮的，所以其中也涉及到一些數(shù)據(jù)庫以外的設(shè)計(jì)。對于ooa/ood的開發(fā)模式有時不免要提出一些疑問，uml是設(shè)計(jì)階段的工具，而它基本涵蓋了軟件設(shè)計(jì)的方方面面，也就是說按照這一軟件工程的正常流程，在動手寫第一句代碼之前，開發(fā)人員已經(jīng)非常熟悉軟件產(chǎn)品了，這對于相當(dāng)有經(jīng)驗(yàn)的架構(gòu)師一類人說可能會很容易，但是我們作為學(xué)生，連足夠的編碼經(jīng)驗(yàn)都沒有，卻首先被教授并要求先ooa再oop，這樣直接導(dǎo)致的問題就是文檔與編碼對不上號，在修改代碼的時候基本不會再去審查文檔和先前的分析。甚至根本就是現(xiàn)有代碼再有文檔，即便是這種情況，代碼與文檔還是不對應(yīng)。不可否認(rèn)，在傳統(tǒng)軟件工程的詳細(xì)設(shè)計(jì)之前的項(xiàng)目過程中還是有很多利于項(xiàng)目開發(fā)的部分的。所以我就一直在尋找適合我——針對探究型項(xiàng)目——的開發(fā)模式，這次的項(xiàng)目也算是一次嘗試，當(dāng)然這個過程并不會太短。

回到數(shù)據(jù)庫設(shè)計(jì)上了，這次的數(shù)據(jù)庫設(shè)計(jì)我是嚴(yán)格按照數(shù)據(jù)庫建模的步驟來進(jìn)行的，老實(shí)說我并沒有感覺這樣的流程對開發(fā)帶來多大的幫助，反倒是覺得將思維轉(zhuǎn)化為圖表很浪費(fèi)時間?？傮w上來說這次的項(xiàng)目也不是很大，而且在數(shù)據(jù)庫的設(shè)計(jì)上比較保守，也就是說實(shí)際上數(shù)據(jù)庫設(shè)計(jì)還可以再完善完善的。隨著我對計(jì)算機(jī)領(lǐng)域的拓寬和加深，我也會靜下心來思考在接觸計(jì)算機(jī)之前的行為，很多次我能深切感覺到，其實(shí)我的大腦(未于別人比較)本身就是在使用一種更接近關(guān)系數(shù)據(jù)庫的方式來記憶，所以我很可恨自然的設(shè)計(jì)出符合三范式的表結(jié)構(gòu)來，即便我不知道這些范式的確切含義。可能就像“范式不太容易用通俗易懂的方式解釋”一樣，在“讓工具用圖標(biāo)表述我的思維”時費(fèi)了一番力氣。

從我作為項(xiàng)目的提出人和實(shí)現(xiàn)者來看，這是個失敗的項(xiàng)目，結(jié)合幾次教學(xué)項(xiàng)目的的實(shí)踐，發(fā)現(xiàn)這也已經(jīng)不是第一次了。主觀原因占多數(shù)，比如，嘗試新的開發(fā)方式，根據(jù)設(shè)計(jì)花了太多的時間來抽象出公用的庫而忽略業(yè)務(wù)邏輯。就這次項(xiàng)目而言，失敗的原因有以下幾點(diǎn)：

1、使用了新的開發(fā)環(huán)境(vim)，這是首次在脫離高級ide的情況下編碼。

2、使用了新的開發(fā)語言(python，actionscript3)，因?yàn)槲乙恢北容^喜歡“學(xué)以致用”，而且這樣的“數(shù)據(jù)驅(qū)動型”軟件的整套自實(shí)現(xiàn)的庫都已經(jīng)完成了，但是由于語言本身的差異，遷移時問題很多，當(dāng)發(fā)現(xiàn)這一點(diǎn)是，已沒有多少有效剩余時間了。

3、編碼流程的不妥，我比較喜歡從底層的庫開始開發(fā)，因?yàn)橐坏鞙y試通過，將很容易將它放到不同的表示層下。但如果庫沒有測試成功，將導(dǎo)致整個項(xiàng)目沒有任何可視化模型，所以這次的項(xiàng)目無法提交“可運(yùn)行的代碼”。

4、實(shí)踐目的的不同，我輕易不放棄鍛煉的機(jī)會，事實(shí)上，有機(jī)會就一定要比以前有所突破，總是照搬以前的做法還不如就不做呢。這個前提是因?yàn)楝F(xiàn)在能完全用來的學(xué)習(xí)的時間比較多，等到工作時再這樣做的可能性就很小了，因此當(dāng)然要抓緊機(jī)會了。不過還有一個隱藏原因，總以為自己很了不起，其實(shí)“遇到的問題數(shù)跟人的能力是成正比的”。

5、客觀原因在這里就不說了。

由于項(xiàng)目還未完成，暫時無法提出需要改進(jìn)了地方。

篇三 access數(shù)據(jù)庫實(shí)驗(yàn)報(bào)告

《數(shù)據(jù)庫及其應(yīng)用》

（課程編號：b0901000）

實(shí)驗(yàn)報(bào)告

（2013-2014學(xué)年第2學(xué)期）

實(shí)驗(yàn)成績：

學(xué) 號：

姓 名：

專業(yè)班級：

課 堂 號：

任課教師：

完成日期： 20xx.05.27

直接啟動access，或在“文件”選項(xiàng)卡中選擇“新建”命令項(xiàng)，出現(xiàn)新建空數(shù)據(jù)庫的backstage視圖界面。在窗口左側(cè)列出了可以執(zhí)行的命令項(xiàng)。包括“打開”、“最近使用文件”、“新建”、“幫助”、“選項(xiàng)”等。

②已有打開數(shù)據(jù)庫的backstage視圖

若已打開數(shù)據(jù)庫，單擊“文件”選項(xiàng)卡，進(jìn)入當(dāng)前數(shù)據(jù)庫的backstage視圖。包括“數(shù)據(jù)庫另存為”、“關(guān)閉數(shù)據(jù)庫”、“信息”“打印”“保存并發(fā)布”等。

（2）觀察功能區(qū)：了解組成功能區(qū)的選項(xiàng)卡。

①功能區(qū)主選項(xiàng)卡包括“文件”、“開始”、“創(chuàng)建”、“外部數(shù)據(jù)”和“數(shù)據(jù)庫工具”。每個選項(xiàng)卡都包含多組相關(guān)命令。在功能區(qū)選項(xiàng)卡上，某些按鈕提供選項(xiàng)樣式庫，而其他按鈕將啟動命令。4個主要命令選項(xiàng)卡為后四個。

②有一些選項(xiàng)卡屬于上下文命令選項(xiàng)卡，根據(jù)當(dāng)前的操作出現(xiàn)或轉(zhuǎn)換。

③快速訪問工具欄。出現(xiàn)在窗口頂部access圖標(biāo)右邊顯示的標(biāo)準(zhǔn)工具欄，它將常用操作

命令顯示在這里，用戶可以單擊按鈕進(jìn)行快速操作。用戶可以定制該工具欄。

④快捷鍵。執(zhí)行命令的方法有多種。最快速、最直接的方法是使用與命令相關(guān)聯(lián)的`鍵盤

快捷方式。在功能區(qū)中可以使用鍵盤快捷方式。

（3）觀察導(dǎo)航窗格。各種對象的顯示組合。

4．a(chǎn)ccess選項(xiàng)及其設(shè)置

在backstage視圖中選擇“選項(xiàng)”命令單擊，進(jìn)入access選項(xiàng)對話框窗口。在該窗口可設(shè)置默認(rèn)文件夾等。選擇“當(dāng)前數(shù)據(jù)庫”頁，在該頁面可設(shè)置文檔窗口顯示方式、定制導(dǎo)航窗格、定制工具欄的項(xiàng)目等。

#．回答問題

（1）啟動access一般有幾種方法？

答：3種．

1.單擊“開始”按鈕，選擇“所有

程序”|“microsoft office”|“microsoft access 2010”菜單項(xiàng)單

擊。

2．雙擊access桌面快捷方式（若沒有快捷方式可先創(chuàng)建）。

3．打開“計(jì)算機(jī)”窗口，找到要操作的access數(shù)據(jù)庫文件，雙擊

（2）按鍵退出access，對應(yīng)的鍵是什么？

答：alt+f4

（3）幾種方式進(jìn)入backstage視圖？

答：2種。通過“開始”按鈕或桌面access快捷方式啟動進(jìn)入backstage視圖。

篇四 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)五

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)五

一.實(shí)驗(yàn)內(nèi)容：

實(shí)現(xiàn)哈夫曼編碼的生成算法。

二.實(shí)驗(yàn)?zāi)康模?/p>

1、使學(xué)生熟練掌握哈夫曼樹的生成算法。

2、熟練掌握哈夫曼編碼的方法。

三.問題描述：

已知n個字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。

1、讀入n個字符，以及字符的.權(quán)值，試建立一棵huffman樹。

2、根據(jù)生成的huffman樹，求每個字符的huffman編碼。并對給定的待編碼字符序列進(jìn)行編碼，并輸出。

四.問題的實(shí)現(xiàn)

(1)郝夫曼樹的存儲表示

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}htnode,*huffmantree; //動態(tài)分配數(shù)組存儲郝夫曼樹

郝夫曼編碼的存儲表示

typedef char* *huffmancode;//動態(tài)分配數(shù)組存儲郝夫曼編碼

(2)主要的實(shí)現(xiàn)思路：

a.首先定義郝夫曼樹的存儲形式，這里使用了數(shù)組

b.用select遍歷n個字符，找出權(quán)值最小的兩個

c.構(gòu)造郝夫曼樹ht，并求出n個字符的郝夫曼編碼hc

總結(jié)

1.基本上沒有什么太大的問題，在調(diào)用select這個函數(shù)時，想把權(quán)值最小的兩個結(jié)點(diǎn)的序號帶回huffmancoding，所以把那2個序號設(shè)置成了引用。

2.在編程過程中，在什么時候分配內(nèi)存，什么時候初始化花的時間比較長

3.最后基本上實(shí)現(xiàn)后，發(fā)現(xiàn)結(jié)果仍然存在問題，經(jīng)過分步調(diào)試，發(fā)現(xiàn)了特別低級的輸入錯誤。把ht[i].weight=ht[s1].weight+ht[s2].weight;中的s2寫成了i

附：

//動態(tài)分配數(shù)組存儲郝夫曼樹

typedef struct{

int weight; //字符的權(quán)值

int parent,lchild,rchild;

}htnode,*huffmantree;

//動態(tài)分配數(shù)組存儲郝夫曼編碼

typedef char* *huffmancode;

//選擇n個(這里是k=n)節(jié)點(diǎn)中權(quán)值最小的兩個結(jié)點(diǎn)

void select(huffmantree &ht,int k,int &s1,int &s2)

{ int i;

i=1;

while(i<=k && ht[i].parent!=0)i++;

//下面選出權(quán)值最小的結(jié)點(diǎn)，用s1指向其序號

s1=i;

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&ht[i].weight

}

//下面選出權(quán)值次小的結(jié)點(diǎn)，用s2指向其序號

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&i!=s1)break;

}

s2=i;

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&i!=s1&&ht[i].weight

}

}

//構(gòu)造huffman樹，求出n個字符的編碼

void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n)

{

int m,c,f,s1,s2,i,start;

char *cd;

if(n<=1)return;

m=2*n-1; //n個葉子n-1個結(jié)點(diǎn)

ht=(huffmantree)malloc((m+1)*sizeof(htnode)); //0號單元未用，預(yù)分配m+1個單元

huffmantree p=ht+1;

w++; //w的號單元也沒有值，所以從號單元開始

for(i=1;i<=n;i++,p++,w++)

{

p->;weight=*w;

p->;parent=p->;rchild=p->;lchild=0;

}

for(;i<=m;++i,++p)

{

p->;weight=p->;parent=p->;rchild=p->;lchild=0;

}

for(i=n+1;i<=m;i++)

{

select(ht,i-1,s1,s2); //選出當(dāng)前權(quán)值最小的

ht[s1].parent=i;

ht[s2].parent=i;

ht[i].lchild=s1;

ht[i].rchild=s2;

ht[i].weight=ht[s1].weight+ht[s2].weight;

}

//從葉子到根逆向求每個字符的郝夫曼編碼

hc=(huffmancode)malloc((n+1)*sizeof(char*)); //分配n個字符編碼的頭指針變量

cd=(char*)malloc(n*sizeof(char)); //分配求編碼的工作空間

cd[n-1]='';//編碼結(jié)束符

for(i=1;i<=n;i++) //逐個字符求郝夫曼編碼

{

start=n-1; //編碼結(jié)束符位置

for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent) //從葉子到根逆向求編碼

{

if(ht[f].lchild==c)cd[--start]='0';

else

cd[--start]='1';

}

hc[i]=(char*)malloc((n-start)*sizeof(char)); //為第i個字符編碼分配空間

strcpy(hc[i],&cd[start]);//從cd復(fù)制編碼到hc

}

free(cd); //釋放工作空間

}

void main

{ int n,i;

int* w; //記錄權(quán)值

char* ch; //記錄字符

huffmantree ht;

huffmancode hc;

cout<<'請輸入待編碼的字符個數(shù)n=';

cin>;>;n;

w=(int*)malloc((n+1)*sizeof(int)); //記錄權(quán)值，號單元未用

ch=(char*)malloc((n+1)*sizeof(char));//記錄字符，號單元未用

cout<<'依次輸入待編碼的字符data及其權(quán)值weight'<

for(i=1;i<=n;i++)

{

cout<<'data['<

}

篇五 sql數(shù)據(jù)庫制作考務(wù)管理系統(tǒng)實(shí)驗(yàn)報(bào)告

sql數(shù)據(jù)庫制作考務(wù)管理系統(tǒng)實(shí)驗(yàn)報(bào)告

一、實(shí)驗(yàn)?zāi)康?/p>

1. 掌握sql server的基本用法

2. 熟悉掌握asp語言的應(yīng)用

3. 掌握asp的頁面結(jié)構(gòu)和內(nèi)置對象

4. 掌握asp與sql server數(shù)據(jù)庫的連接和應(yīng)用

5. 掌握asp 另外一個重要的語言——javascript,并熟悉它的應(yīng)用

6.制作一個功能完善的考務(wù)管理系統(tǒng)

7.能夠獨(dú)立的完成系統(tǒng)策劃，系統(tǒng)分析和程序的編寫

8. 提高發(fā)現(xiàn)問題，解決問題的能力

二、實(shí)驗(yàn)內(nèi)容

制作一個考務(wù)管理系統(tǒng)，用于從考生報(bào)名、產(chǎn)生準(zhǔn)考證到錄取考生和打印成績單即對考生考試和錄取全過程的考務(wù)管理，系統(tǒng)要實(shí)現(xiàn)的功能有：考生報(bào)名，按報(bào)名順序產(chǎn)生報(bào)名號;產(chǎn)生準(zhǔn)考證號和打印準(zhǔn)考證;輸入考生成績和輸入錄取合格標(biāo)準(zhǔn);根據(jù)合格標(biāo)準(zhǔn)錄取上線考生;打印考生成績單和錄取通知書;設(shè)置系統(tǒng)用戶和系統(tǒng)初始化。

三、實(shí)驗(yàn)環(huán)境

1、windows xp或 windows xx;

2、安裝 microsoft sql server xx 個人版。

3、iis 5.0及以上版本和瀏覽器ie5.5及以上版本

4、macromedia dreamwezver8等相關(guān)軟件

四、實(shí)驗(yàn)步驟

首先：配置環(huán)境，安裝sql server，macromedia dreamwezver8。

第二：對要做的系統(tǒng)進(jìn)行構(gòu)思、策劃、布局。

第三：建立數(shù)據(jù)庫kaoshi及數(shù)據(jù)表：學(xué)生信息表(student)，用戶表(yonghu)，考生表(biaozhun)。

第四：建立連接數(shù)據(jù)庫的文件conn.asp,其代碼如下所示：

<%

set conn=server.createobject('adodb.connection')

conn.open 'provider=sqloledb;' & 'data source=localhost;initial catalog=ksd;user id=sa;password=100200;'

%>;

第五：制作各個網(wǎng)頁并聯(lián)接所有需要聯(lián)接的網(wǎng)頁。

第六：運(yùn)行整個系統(tǒng)，查找是否有錯誤，并進(jìn)行修改直至整個系統(tǒng)運(yùn)行無誤。

五、實(shí)驗(yàn)過程與分析

(一)系統(tǒng)分析與總體設(shè)計(jì)

現(xiàn)在用計(jì)算機(jī)來進(jìn)行考生的管理及考生的`錄取已普遍存在。因如果用人來進(jìn)行這項(xiàng)工作將十分煩瑣，系統(tǒng)管理員需要劃分很多的時間和精力，而且還不能保證其正確率。

而用考務(wù)管理系統(tǒng)可以簡化管理員的工作，還會提高工作的正確率。以下將對考務(wù)管理系統(tǒng)進(jìn)行系統(tǒng)分析和設(shè)計(jì)。

(1)系統(tǒng)的功能描述

考務(wù)管理系統(tǒng)包括學(xué)生報(bào)名管理、考生成績管理系統(tǒng)維護(hù)三大模塊。

考生報(bào)名管理 包括報(bào)名處理、產(chǎn)生準(zhǔn)考證、打印準(zhǔn)考證和退出系統(tǒng)等4項(xiàng)功能。

考生成績管理 包括考生成績錄入、合格標(biāo)準(zhǔn)錄入、錄取考生、打印成績單和打印錄取通知單等5項(xiàng)功能。

系統(tǒng)維護(hù) 包括用戶設(shè)置和系統(tǒng)初始化等2項(xiàng)功能。

用戶通過系統(tǒng)菜單執(zhí)行相應(yīng)的操作。

(2)數(shù)據(jù)庫設(shè)計(jì)

本系統(tǒng)以sql server xx作為數(shù)據(jù)庫平臺。在sql server xx中設(shè)計(jì)一個數(shù)據(jù)庫kaoshi，其中包含如下數(shù)據(jù)表。

1.student表

該表用于存放所有考生記錄，包括基本數(shù)據(jù).表的結(jié)構(gòu)如圖2所示。

2biaozhun表

該表用于存放錄取考生的合格標(biāo)準(zhǔn)，其中只有一個記錄，該記錄指出各門課程的最低分和總分的最低分。只有各門成績和總分都超過這個標(biāo)準(zhǔn)的考生才能被錄取。該表的結(jié)構(gòu)如圖3所示。

3.yonghu表

該表用于存放本系統(tǒng)用戶的信息。包括用戶的用戶名、密碼和級別(只分“一般操作員”和“系統(tǒng)管理員”兩類)。該表結(jié)構(gòu)如圖4所示。

六、實(shí)驗(yàn)結(jié)果與總結(jié)

實(shí)驗(yàn)中的考務(wù)管理系統(tǒng)是經(jīng)過很多次的測試、修改再測試、再修改才完成的。也就是在多次的測試修改的過程中使我學(xué)發(fā)現(xiàn)了很多平時上課發(fā)現(xiàn)不了的問題，也發(fā)現(xiàn)了自己學(xué)習(xí)這門課程的薄弱的地方和學(xué)的不足的地方。通過實(shí)驗(yàn)期間的發(fā)現(xiàn)問題、分析問題、查找問題原因、解決問題及進(jìn)一步完善考務(wù)管理系統(tǒng)的過程，我的能力和水平有一定程度的提高。經(jīng)過一次獨(dú)立完成系統(tǒng)給我以后編程打下了基礎(chǔ)，讓我面對的不再是茫然和無措，而是有條不紊的思緒和完成的信心。所以這次實(shí)驗(yàn)對我來說是一筆極大的財(cái)富。

當(dāng)然，在實(shí)驗(yàn)中我也有很多不足的地方，系統(tǒng)也有需要進(jìn)一步完善的地方，這主要是我對asp與sql server數(shù)據(jù)庫的連接和應(yīng)用不熟悉和經(jīng)驗(yàn)不足的原因造成的。所以我還要在以后繼續(xù)學(xué)習(xí)，以求做的更好。

篇六 北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告線性表

北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告線性表

實(shí)驗(yàn)報(bào)告;課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：軟件工程實(shí)驗(yàn)成績：;1206;實(shí)驗(yàn)名稱：打印機(jī)隊(duì)列模擬學(xué)號：20124848批;程序的設(shè)計(jì);實(shí)驗(yàn)編號：實(shí)驗(yàn)一姓名：實(shí)驗(yàn)日期：2014年5月2;一、實(shí)驗(yàn)?zāi)康?對隊(duì)列的理解;對stl中的queue的使用;實(shí)驗(yàn)仿真一個網(wǎng)絡(luò)打印過程;二、實(shí)驗(yàn)內(nèi)容與實(shí)驗(yàn)步驟流程圖;這個任務(wù)隊(duì)列的測試使用stl隊(duì)列適配器;具體地說,每一行中包含的信息是

實(shí) 驗(yàn) 報(bào) 告

課程名稱：數(shù)據(jù)結(jié)構(gòu) 班級：軟件工程實(shí)驗(yàn)成績：

1206

實(shí)驗(yàn)名稱：打印機(jī)隊(duì)列模擬學(xué)號：20124848 批閱教師簽字：

程序的設(shè)計(jì)

實(shí)驗(yàn)編號：實(shí)驗(yàn)一 姓名： 實(shí)驗(yàn)日期：2014年5 月 24 日

一、實(shí)驗(yàn)?zāi)康?/p>

對隊(duì)列的理解

對stl中的queue的使用

實(shí)驗(yàn)仿真一個網(wǎng)絡(luò)打印過程

二、實(shí)驗(yàn)內(nèi)容與實(shí)驗(yàn)步驟流程圖

這個任務(wù)隊(duì)列的測試使用stl隊(duì)列適配器。程序要求完成模擬的實(shí)現(xiàn)共享打印機(jī)。這個打印機(jī)使用先進(jìn)先出隊(duì)列。仿真是通過讀取和處理事件數(shù)據(jù)文件的列表。一個有效的數(shù)據(jù)文件中的每一行包含信息打印作業(yè)和提交這份工作的時間。

具體地說,每一行中包含的信息是提交工作的時間(以秒為單位),和在頁面的工作長及工作的計(jì)算機(jī)的名稱。在模擬的開始,每個這些事件的每一個應(yīng)該被程序所讀，存儲在繼承工作負(fù)載隊(duì)列。程序應(yīng)該通過循環(huán)遞增計(jì)數(shù)器或while-loop模擬時間的流逝。程序應(yīng)該將計(jì)數(shù)器初始化為零,然后依次增加1秒。當(dāng)模擬等于當(dāng)前時間的打印作業(yè)的提交時間在工作隊(duì)列的前面，一個打印作業(yè)完成。當(dāng)這一切發(fā)生的時候,從工作隊(duì)列取出這個事件,然后把它放在另一個隊(duì)列對象。這個隊(duì)列對象存儲已完成的打印作業(yè)。當(dāng)程序仿真其他的打印工作的時候，這些工作在隊(duì)列等待。

win8，visual c++ 6.0

四、實(shí)驗(yàn)過程與分析

(1)實(shí)驗(yàn)主要函數(shù)及存儲結(jié)構(gòu)

main.cpp 包括主函數(shù)和主要的功能

simulator.h 仿真類的聲明

simulator.cpp 仿真類的定義

event.h 事件類的聲明

event.cpp - 事件類的定義

job.h 作業(yè)類的聲明

job.cpp 作業(yè)類的.定義

arbitrary.run 包括任意打印作業(yè)數(shù)的數(shù)據(jù)文件

arbitrary.out 輸出 arbitrary.run

bigfirst.run 包括打印較大作業(yè)的數(shù)據(jù)文件

bigfirst.out 輸出 bigfirst.run

(2)實(shí)驗(yàn)代碼

#ifndef fifo_h //fifo.h

#define fifo_h

#include 'simulator.h'

class fifo:public simulator{

protected:

queue waiting;

priority_queue priority_waiting;

public:

fifo(int seconds_per_page);

void simulate(string file);

};

bool operator < (event evtleft,event evtright);

#endif

#include 'fifo.h' //fifo.cpp

#include

using namespace std;

fifo::fifo(int seconds_per_page):simulator(seconds_per_page){ }

void fifo::simulate(string file){

int finish_time = 0;

float agg_latency = 0;

int totaljob =0;

event evt;

if(file.find('arbitrary')!= string::npos){

string outfile ='arbitrary.out';

ofstream osf(outfile.c_str);

loadworkload(file);

osf<<'fifo simulation '<

for(int time =1;!waiting.empty||!workload.empty;time++){ while(!workload.empty && time ==

workload.front.arrival_time){

evt= workload.front;

osf<<' arriving: '<

workload.pop;

}

if(!waiting.empty && time >;= finish_time){

totaljob ++;

evt = waiting.front;

agg_latency += time - evt.arrival_time;

osf<<' servicing: '<

finish_time = time + evt.getjob.getnumpages * seconds_per_page;

}

}

osf<<' total job '<

osf<<' aggregate latency: '<

osf<<' mean latency : '<

return;

}

if(file.find('bigfirst') != string::npos){

string outfile = 'bigfirst.out';

ofstream osf(outfile.c_str);

loadworkload(file);

osf<<'fifo simulation '<

for(int time

=1;!priority_waiting.empty||!workload.empty;time++){

while(!workload.empty && time ==

workload.front.arrival_time){

evt= workload.front;

osf<<' arriving: '<

workload.pop;

}

if(!priority_waiting.empty && time >;= finish_time){

totaljob ++;

evt = priority_waiting.top;

agg_latency += time - evt.arrival_time;

osf<<' servicing: '<

finish_time = time + evt.getjob.getnumpages * seconds_per_page; }

}

osf<<' total job '<

osf<<' aggregate latency: '<

osf<<' mean latency : '<

return;

}

cerr<<'the program don't know what algorithm to use'<

cerr<<'you should specify the file name with arbitrary or bigfirst'<

bool operator < (event evtleft,event evtright){

return evtleft.getjob.getnumpages <

evtright.getjob.getnumpages;

}

五、實(shí)驗(yàn)結(jié)果總結(jié)

經(jīng)測試，功能較為完整。代碼流程簡圖如下：

通過這次實(shí)驗(yàn)，我了解了有關(guān)隊(duì)列方面的知識。掌握了隊(duì)列的邏輯結(jié)構(gòu)，抽象數(shù)據(jù)類型，隊(duì)列的存儲方式等。運(yùn)用先進(jìn)先出表，仿真了網(wǎng)絡(luò)打印隊(duì)列。這都使我對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)有了新的認(rèn)識與幫助。在實(shí)驗(yàn)過程中，我也遇到了許多困難，從開始時對隊(duì)列運(yùn)算的不熟悉，到逐漸查找資料，從而完成了實(shí)驗(yàn);六、附錄;-《數(shù)據(jù)結(jié)構(gòu)與算法分析》以及網(wǎng)上資料;

逐漸查找資料，從而完成了實(shí)驗(yàn)。在今后的學(xué)習(xí)中，我將繼續(xù)努力，加強(qiáng)對堆棧，隊(duì)列等知識的學(xué)習(xí)，以達(dá)到精益求精。

六、附錄

-《數(shù)據(jù)結(jié)構(gòu)與算法分析》以及網(wǎng)上資料

篇七 c數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

c數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)(c語言版)實(shí)驗(yàn)報(bào)告;專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程;學(xué)號:____201240703061_____;班級:_________軟件二班________;姓名:________朱海霞__________;指導(dǎo)教師:___劉遵仁_____________;青島大學(xué)信息工程學(xué)院;2013年10月;實(shí)驗(yàn)1;實(shí)驗(yàn)題目：順序存儲結(jié)構(gòu)線性表的插入和刪除;實(shí)驗(yàn)?zāi)?/p>

數(shù)據(jù)結(jié)構(gòu)(c語言版) 實(shí)驗(yàn)報(bào)告

專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程

學(xué)號:____201240703061___________________

班級:_________軟件二班______________

姓名:________朱海霞______________

指導(dǎo)教師:___劉遵仁________________

青島大學(xué)信息工程學(xué)院

2013年10月

實(shí)驗(yàn)1

實(shí)驗(yàn)題目：順序存儲結(jié)構(gòu)線性表的插入和刪除

實(shí)驗(yàn)?zāi)康模?/p>

了解和掌握線性表的邏輯結(jié)構(gòu)和順序存儲結(jié)構(gòu)，掌握線性表的基本算法及相關(guān)的時間性能分析。

實(shí)驗(yàn)要求：

建立一個數(shù)據(jù)域定義為整數(shù)類型的線性表，在表中允許有重復(fù)的數(shù)據(jù);根據(jù)輸入的數(shù)據(jù)，先找到相應(yīng)的存儲單元，后刪除之。

實(shí)驗(yàn)主要步驟：

1、分析、理解給出的示例程序。

2、調(diào)試程序，并設(shè)計(jì)輸入一組數(shù)據(jù)(3，-5，6，8，2，-5，4，7，-9)，測試程序的如下功能：根據(jù)輸入的數(shù)據(jù)，找到相應(yīng)的存儲單元并刪除，顯示表中所有的數(shù)據(jù)。

程序代碼:

#include

#include

#define ok 1

#define error 0

#define overflow -2

#define list_init_size 100

#define listincrement 10

typedef struct{

int* elem;

int length;

int listsize;

}sqlist;

int initlist_sq(sqlist &l){

l.elem=(int*)malloc(list_init_size*sizeof(int));

if(!l.elem) return -1;

l.length=0;

l.listsize=list_init_size;

return ok;

}

int listinsert_sq(sqlist&l,int i,int e){

if(i<1||i>;l.length+1) return error;

if(l.length==l.listsize){

int *newbase;

newbase=(int*)realloc(l.elem,(l.listsize+listincrement)*sizeof(int));

if(!newbase) return -1;

l.elem=newbase;

l.listsize+=listincrement;

}

int *p,*q;

q=&(l.elem[i-1]);

for(p=&(l.elem[l.length-1]);p>;=q;--p)

*(p+1)=*p;

*q=e;

++l.length;

return ok;

}

int listdelete_sq(sqlist &l,int i,int e){

int *p,*q;

if(i<1||i>;l.length)return error;

p=&(l.elem[i-1]);

e=*p;

q=l.elem+l.length-1;

for(++p;p<=q;++p)

*(p-1)=*p;

--l.length;

return ok;

}

int main{

sqlist l;

initlist_sq(l);//初始化

int i,a[]={3,-5,6,8,2,-5,4,7,-9};

for(i=1;i<10;i++)

listinsert_sq(l,i,a[i-1]);

for(i=0;i<9;i++)

printf(' %d',l.elem[i]);

printf(' ');//插入9個數(shù)

listinsert_sq(l,3,24);

for(i=0;i<10;i++)

printf(' %d',l.elem[i]);

printf(' ');//插入一個數(shù)

int e;

listdelete_sq(l,2, e);

for(i=0;i<9;i++)

printf(' %d',l.elem[i]);//刪除一個數(shù)

printf(' ');

return 0;

}

實(shí)驗(yàn)結(jié)果：

3，-5,6,8,2，-5,4,7，-9

3，-5,24,6,8,2，-5,4,7，-9

3,24,6,8,2，-5,4,7，-9

心得體會：

順序存儲結(jié)構(gòu)是一種隨機(jī)存取結(jié)構(gòu)，存取任何元素的時間是一個常數(shù)，速度快;結(jié)構(gòu)簡單，邏輯上相鄰的元素在物理上也相鄰;不使用指針，節(jié)省存儲空間;但是插入和刪除元素需要移動大量元素，消耗大量時間;需要一個連續(xù)的存儲空間;插入元素可能發(fā)生溢出;自由區(qū)中的存儲空間不能被其他數(shù)據(jù)共享 實(shí)驗(yàn)2

實(shí)驗(yàn)題目：單鏈表的插入和刪除

實(shí)驗(yàn)?zāi)康模?/p>

了解和掌握線性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，掌握單鏈表的基本算法及相關(guān)的時間性能分析。

實(shí)驗(yàn)要求：

建立一個數(shù)據(jù)域定義為字符類型的單鏈表，在鏈表中不允許有重復(fù)的字符;根據(jù)輸入的字符，先找到相應(yīng)的結(jié)點(diǎn)，后刪除之。

實(shí)驗(yàn)主要步驟：

3、分析、理解給出的示例程序。

4、調(diào)試程序，并設(shè)計(jì)輸入數(shù)據(jù)(如：a，c，e，f，h，j，q，m)，測試程序的如下功能：不允許重復(fù)字符的插入;根據(jù)輸入的字符，找到相應(yīng)的結(jié)點(diǎn)并刪除。

5、修改程序：

(1) 增加插入結(jié)點(diǎn)的功能。

(2) 建立鏈表的方法有“前插”、“后插”法。

程序代碼:

#include

#include

#define null 0

#define ok 1

#define error 0

typedef struct lnode{

int data;

struct lnode *next;

}lnode,*linklist;

int initlist_l(linklist &l){

l=(linklist)malloc(sizeof(lnode)); l->;next=null;

return ok;

}

int listinsert_l(linklist &l,int i,int e){ linklist p,s;

int j;

p=l;j=0;

while(p&&j

p=p->;next;++j;

}

if(!p||j>;i-1)

return error;

s=(linklist)malloc(sizeof(lnode)); s->;data=e;

s->;next=p->;next;

p->;next=s;

return ok;

}

int listdelete_l(linklist&l,int i,int &e){ linklist p,q;

int j;

p=l;j=0;

while(p->;next&&j

p=p->;next;++j;

}

if(!(p->;next)||j

return error;

q=p->;next;p->;next=q->;next; e=q->;data;free(q);

return ok;

}

int main{

linklist l,p;

char a[8]={'a','c','e','f','h','j','q','u'}; int i,j;

initlist_l(l);

for(i=1,j=0;i<=8,j<8;i++,j++) listinsert_l(l,i,a[j]);

p=l->;next;

while(p!=null){

printf('%c ',p->;data); p=p->;next;

}//插入八個字符printf(' ;實(shí)驗(yàn)結(jié)果：;acefhjqu;abcefhjqu;abefhjqu;心得體會：;單鏈表是通過掃描指針p進(jìn)行單鏈表的操作;頭指針唯;實(shí)驗(yàn)3;實(shí)驗(yàn)題目：棧操作設(shè)計(jì)和實(shí)現(xiàn);實(shí)驗(yàn)?zāi)康模?1、掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，以便在實(shí);2、掌握棧的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則;3、掌握棧的'基本運(yùn)算，如：入棧與出棧

}

}//插入八個字符 printf(' '); i=2; int e; listinsert_l(l,i,'b'); p=l->;next; while(p!=null){ printf('%c ',p->;data); p=p->;next; }//插入一個字符 printf(' '); i=3; listdelete_l(l,i,e); p=l->;next; while(p!=null){ printf('%c ',p->;data); p=p->;next; } printf(' '); return 0;

實(shí)驗(yàn)結(jié)果：

a c e f h j q u

a b c e f h j q u

a b e f h j q u

心得體會：

單鏈表是通過掃描指針p進(jìn)行單鏈表的操作;頭指針唯一標(biāo)識點(diǎn)鏈表的存在;插入和刪除元素快捷，方便。

實(shí)驗(yàn)3

實(shí)驗(yàn)題目：棧操作設(shè)計(jì)和實(shí)現(xiàn)

實(shí)驗(yàn)?zāi)康模?/p>

1、掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，以便在實(shí)際中靈活應(yīng)用。

2、掌握棧的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則。

3、掌握棧的基本運(yùn)算，如：入棧與出棧等運(yùn)算在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實(shí)現(xiàn)。

實(shí)驗(yàn)要求：

回文判斷：對于一個從鍵盤輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤?。如

“abba”是回文，而“abab”不是回文。

實(shí)驗(yàn)主要步驟

(1)數(shù)據(jù)從鍵盤讀入;

(2)輸出要判斷的字符串;

(3)利用棧的基本操作對給定的字符串判斷其是否是回文，若是則輸出“yes”，否則輸出“no”。

程序代碼:

#include

#include

#define true 1

#define false 0

#define ok 1

#define error 0

#define overflow -2

#define n 100

#define stack_init_size 100

#define stackincrement 10

typedef struct{

int *base; // 在棧構(gòu)造之前和銷毀之后，base的值為null int *top; // 棧頂指針

int stacksize; // 當(dāng)前已分配的存儲空間，以元素為單位

} sqstack;

int initstack(sqstack &s)

{ // 構(gòu)造一個空棧s

if(!(s.base=(int *)malloc(stack_init_size*sizeof(int))))

exit(overflow); // 存儲分配失敗

s.top=s.base;

s.stacksize=stack_init_size;

return ok;

}

int stackempty(sqstack s)

{ // 若棧s為空棧，則返回true，否則返回false

if(s.top==s.base)

return true;

else

return false;

}

int push(sqstack &s, int e)

{ // 插入元素e為新的棧頂元素

if(s.top-s.base>;=s.stacksize) // 棧滿，追加存儲空間

{

s.base=(int *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(int)); if(!s.base)

exit(overflow); // 存儲分配失敗

s.top=s.base+s.stacksize;

s.stacksize+=stackincrement;

}

*(s.top)++=e;

return ok;

}

int pop(sqstack &s,int &e)

{ // 若棧不空，則刪除s的棧頂元素，用e返回其值，并返回ok;否則返回error if(s.top==s.base)

return error;

e=*--s.top;

return ok;

}

int main{

sqstack s;

int i,e,j,k=1;

char ch[n] = {0},*p,b[n] = {0};

if(initstack(s)) // 初始化棧成功

{

printf('請輸入表達(dá)式: ');

gets(ch);

p=ch;

while(*p) // 沒到串尾

push(s,*p++);

for(i=0;i

if(!stackempty(s)) {// 棧不空

pop(s,e); // 彈出棧頂元素

b[i]=e;

}

}

for(i=0;i

if(ch[i]!=b[i])

k=0;

}

if(k==0)

printf('no!');

else

printf('輸出:')

printf('yes!');

}

return 0;

}

實(shí)驗(yàn)結(jié)果：

請輸入表達(dá)式：

abcba

輸出：yes!

心得體會：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進(jìn)后出的性質(zhì)，這個固有性質(zhì)使棧成為程序設(shè)計(jì)中的有用工具。

實(shí)驗(yàn)4

實(shí)驗(yàn)題目：二叉樹操作設(shè)計(jì)和實(shí)現(xiàn)

實(shí)驗(yàn)?zāi)康模?/p>

掌握二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法。

實(shí)驗(yàn)要求：

采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作。

實(shí)驗(yàn)主要步驟：

1、分析、理解程序。

2、調(diào)試程序，設(shè)計(jì)一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結(jié)點(diǎn)(空指針)，如abd###ce##f##，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結(jié)點(diǎn)總數(shù)。

程序代碼:

實(shí)驗(yàn)結(jié)果：

心得體會：

實(shí)驗(yàn)5

實(shí)驗(yàn)題目：圖的遍歷操作

實(shí)驗(yàn)?zāi)康模?/p>

掌握有向圖和無向圖的概念;掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu);掌握dfs及bfs對圖的遍歷操作;了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。

實(shí)驗(yàn)要求：

采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的dfs和bfs操作。

實(shí)驗(yàn)主要步驟：

設(shè)計(jì)一個有向圖和一個無向圖，任選一種存儲結(jié)構(gòu)，完成有向圖和無向圖的dfs(深度優(yōu)先遍歷)和bfs(廣度優(yōu)先遍歷)的操作。

1. 鄰接矩陣作為存儲結(jié)構(gòu)

#include'stdio.h'

#include'stdlib.h'

#define maxvertexnum 100 //定義最大頂點(diǎn)數(shù)

typedef struct{

char vexs[maxvertexnum]; //頂點(diǎn)表

int edges[maxvertexnum][maxvertexnum]; //鄰接矩陣，可看作邊表 int n,e; //圖中的頂點(diǎn)數(shù)n和邊數(shù)e

}mgraph; //用鄰接矩陣表示的圖的類型

//=========建立鄰接矩陣=======

void creatmgraph(mgraph *g)

{

int i,j,k;

char a;

printf('input vertexnum(n) and edgesnum(e): ');

scanf('%d,%d',&g->;n,&g->;e); //輸入頂點(diǎn)數(shù)和邊數(shù)

scanf('%c',&a);

printf('input vertex string:');

for(i=0;in;i++)

{

scanf('%c',&a);

g->;vexs[i]=a; //讀入頂點(diǎn)信息，建立頂點(diǎn)表

}

for(i=0;in;i++)

for(j=0;jn;j++)

g->;edges[i][j]=0; //初始化鄰接矩陣

printf('input edges,creat adjacency matrix ');

for(k=0;ke;k++) { //讀入e條邊，建立鄰接矩陣

scanf('%d%d',&i,&j); //輸入邊(vi，vj)的頂點(diǎn)序號

g->;edges[i][j]=1;;g->;edges[j][i]=1;//若為;//=========定義標(biāo)志向量，為全局變量=;typedefenum{false,true}b;booleanvisited[maxvertex;//========dfs：深度優(yōu)先遍歷的遞歸算;voiddfsm(mgraph*g,inti);{//以vi為出發(fā)點(diǎn)

g->;edges[i][j]=1;

g->;edges[j][i]=1; //若為無向圖，矩陣為對稱矩陣;若建立有向圖，去掉該條語句 }

}

//=========定義標(biāo)志向量，為全局變量=======

typedef enum{false,true} boolean;

boolean visited[maxvertexnum];

//========dfs：深度優(yōu)先遍歷的遞歸算法======

void dfsm(mgraph *g,int i)

{ //以vi為出發(fā)點(diǎn)對鄰接矩陣表示的圖g進(jìn)行dfs搜索，鄰接矩陣是0，1矩陣

給出你的編碼

//===========bfs：廣度優(yōu)先遍歷=======

void bfs(mgraph *g,int k)

{ //以vk為源點(diǎn)對用鄰接矩陣表示的圖g進(jìn)行廣度優(yōu)先搜索

給出你的編碼

//==========主程序main =====

void main

{

int i;

mgraph *g;

g=(mgraph *)malloc(sizeof(mgraph)); //為圖g申請內(nèi)存空間

creatmgraph(g); //建立鄰接矩陣

printf('print graph dfs: ');

dfs(g); //深度優(yōu)先遍歷

printf(' ');

printf('print graph bfs: ');

bfs(g,3); //以序號為3的頂點(diǎn)開始廣度優(yōu)先遍歷

printf(' ');

}

2. 鄰接鏈表作為存儲結(jié)構(gòu)

#include'stdio.h'

#include'stdlib.h'

#define maxvertexnum 50 //定義最大頂點(diǎn)數(shù)

typedef struct node{ //邊表結(jié)點(diǎn)

int adjvex; //鄰接點(diǎn)域

struct node *next; //鏈域

}edgenode;

typedef struct vnode{ //頂點(diǎn)表結(jié)點(diǎn)

char vertex; //頂點(diǎn)域

edgenode *firstedge; //邊表頭指針

}vertexnode;

typedef vertexnode adjlist[maxvertexnum]; //adjlist是鄰接表類型 typedef struct {

adjlist adjlist; //鄰接表

int n,e; //圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)

} algraph; //圖類型

//=========建立圖的鄰接表=======

void creatalgraph(algraph *g)

{

int i,j,k;

char a;

edgenode *s; //定義邊表結(jié)點(diǎn)

printf('input vertexnum(n) and edgesnum(e): ');

scanf('%d,%d',&g->;n,&g->;e); //讀入頂點(diǎn)數(shù)和邊數(shù)

scanf('%c',&a);

printf('input vertex string:');

for(i=0;in;i++) //建立邊表

{

scanf('%c',&a);

g->;adjlist[i].vertex=a; //讀入頂點(diǎn)信息

g->;adjlist[i].firstedge=null; //邊表置為空表

}

printf('input edges,creat adjacency list ');

for(k=0;ke;k++) { //建立邊表

scanf('%d%d',&i,&j); //讀入邊(vi，vj)的頂點(diǎn)對序號

s=(edgenode *)malloc(sizeof(edgenode)); //生成邊表結(jié)點(diǎn)

s->;adjvex=j; //鄰接點(diǎn)序號為j

s->;next=g->;adjlist[i].firstedge;

g->;adjlist[i].firstedge=s; //將新結(jié)點(diǎn)*s插入頂點(diǎn)vi的邊表頭部

s=(edgenode *)malloc(sizeof(edgenode));

s->;adjvex=i; //鄰接點(diǎn)序號為i

s->;next=g->;adjlist[j].firstedge;

g->;adjlist[j].firstedge=s; //將新結(jié)點(diǎn)*s插入頂點(diǎn)vj的邊表頭部

}

}

//=========定義標(biāo)志向量，為全局變量=======

typedef enum{false,true} boolean;

boolean visited[maxvertexnum];

//========dfs：深度優(yōu)先遍歷的遞歸算法======

void dfsm(algraph *g,int i)

{ //以vi為出發(fā)點(diǎn)對鄰接鏈表表示的圖g進(jìn)行dfs搜索

給出你的編碼

//==========bfs：廣度優(yōu)先遍歷=========

void bfs(algraph *g,int k)

{ //以vk為源點(diǎn)對用鄰接鏈表表示的圖g進(jìn)行廣度優(yōu)先搜索

給出你的編碼

//==========主函數(shù)===========

void main

{

int i;

algraph *g;

g=(algraph *)malloc(sizeof(algraph));

creatalgraph(g);

printf('print graph dfs: ');

dfs(g);

printf(' ');

printf('print graph bfs: ');

bfs(g,3);

printf(' ');

}

實(shí)驗(yàn)結(jié)果：

1. 鄰接矩陣作為存儲結(jié)構(gòu)

2. 鄰接鏈表作為存儲結(jié)構(gòu)

心得體會：

實(shí)驗(yàn)6

實(shí)驗(yàn)題目：二分查找算法的實(shí)現(xiàn)

實(shí)驗(yàn)?zāi)康模?/p>

掌握二分查找法的工作原理及應(yīng)用過程，利用其工作原理完成實(shí)驗(yàn)題目中的內(nèi)容。。

實(shí)驗(yàn)要求：

編寫程序構(gòu)造一個有序表l，從鍵盤接收一個關(guān)鍵字key，用二分查找法在l中查找key，若找到則提示查找成功并輸出key所在的位置，否則提示沒有找到信息。。

實(shí)驗(yàn)主要步驟：

1. 建立的初始查找表可以是無序的，如測試的數(shù)據(jù)為{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。

2. 給出算法的遞歸和非遞歸代碼;

3. 如何利用二分查找算法在一個有序表中插入一個元素x，并保持表的有序性?

程序代碼

實(shí)驗(yàn)結(jié)果：

心得體會：

實(shí)驗(yàn)7

實(shí)驗(yàn)題目：排序

實(shí)驗(yàn)?zāi)康模?/p>

掌握各種排序方法的基本思想、排序過程、算法實(shí)現(xiàn)，能進(jìn)行時間和空間性能的分析，根據(jù)實(shí)際問題的特點(diǎn)和要求選擇合適的排序方法。

實(shí)驗(yàn)要求：

實(shí)現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運(yùn)行速度。

實(shí)驗(yàn)主要步驟：

程序代碼

實(shí)驗(yàn)結(jié)果：

心得體會：

篇八 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1

一.實(shí)驗(yàn)內(nèi)容：

實(shí)現(xiàn)哈夫曼編碼的生成算法。

二.實(shí)驗(yàn)?zāi)康模?/p>

1、使學(xué)生熟練掌握哈夫曼樹的生成算法。

2、熟練掌握哈夫曼編碼的方法。

三.問題描述：

已知n個字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。

1、讀入n個字符，以及字符的權(quán)值，試建立一棵huffman樹。

2、根據(jù)生成的huffman樹，求每個字符的huffman編碼。并對給定的待編碼字符序列進(jìn)行編碼，并輸出。

四.問題的實(shí)現(xiàn)

(1)郝夫曼樹的存儲表示

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}htnode,*huffmantree; //動態(tài)分配數(shù)組存儲郝夫曼樹

郝夫曼編碼的存儲表示

typedef char* *huffmancode;//動態(tài)分配數(shù)組存儲郝夫曼編碼

(2)主要的實(shí)現(xiàn)思路：

a.首先定義郝夫曼樹的存儲形式，這里使用了數(shù)組

b.用select遍歷n個字符，找出權(quán)值最小的兩個

c.構(gòu)造郝夫曼樹ht，并求出n個字符的郝夫曼編碼hc

總結(jié)

1.基本上沒有什么太大的問題，在調(diào)用select這個函數(shù)時，想把權(quán)值最小的兩個結(jié)點(diǎn)的序號帶回huffmancoding，所以把那2個序號設(shè)置成了引用。

2.在編程過程中，在什么時候分配內(nèi)存，什么時候初始化花的時間比較長

3.最后基本上實(shí)現(xiàn)后，發(fā)現(xiàn)結(jié)果仍然存在問題，經(jīng)過分步調(diào)試，發(fā)現(xiàn)了特別低級的輸入錯誤。把ht[i].weight=ht[s1].weight+ht[s2].weight;中的s2寫成了i

附：

//動態(tài)分配數(shù)組存儲郝夫曼樹

typedef struct{

int weight; //字符的.權(quán)值

int parent,lchild,rchild;

}htnode,*huffmantree;

//動態(tài)分配數(shù)組存儲郝夫曼編碼

typedef char* *huffmancode;

//選擇n個(這里是k=n)節(jié)點(diǎn)中權(quán)值最小的兩個結(jié)點(diǎn)

void select(huffmantree &ht,int k,int &s1,int &s2)

{ int i;

i=1;

while(i<=k && ht[i].parent!=0)i++;

//下面選出權(quán)值最小的結(jié)點(diǎn)，用s1指向其序號

s1=i;

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&ht[i].weight

}

//下面選出權(quán)值次小的結(jié)點(diǎn)，用s2指向其序號

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&i!=s1)break;

}

s2=i;

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&i!=s1&&ht[i].weight

}

}

//構(gòu)造huffman樹，求出n個字符的編碼

void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n)

{

int m,c,f,s1,s2,i,start;

char *cd;

if(n<=1)return;

m=2*n-1; //n個葉子n-1個結(jié)點(diǎn)

ht=(huffmantree)malloc((m+1)*sizeof(htnode)); //0號單元未用，預(yù)分配m+1個單元

huffmantree p=ht+1;

w++; //w的號單元也沒有值，所以從號單元開始

for(i=1;i<=n;i++,p++,w++)

{

p->weight=*w;

p->parent=p->rchild=p->lchild=0;

}

for(;i<=m;++i,++p)

{

p->weight=p->parent=p->rchild=p->lchild=0;

}

for(i=n+1;i<=m;i++)

{

select(ht,i-1,s1,s2); //選出當(dāng)前權(quán)值最小的

ht[s1].parent=i;

ht[s2].parent=i;

ht[i].lchild=s1;

ht[i].rchild=s2;

ht[i].weight=ht[s1].weight+ht[s2].weight;

}

//從葉子到根逆向求每個字符的郝夫曼編碼

hc=(huffmancode)malloc((n+1)*sizeof(char*)); //分配n個字符編碼的頭指針變量

cd=(char*)malloc(n*sizeof(char)); //分配求編碼的工作空間

cd[n-1]='';//編碼結(jié)束符

for(i=1;i<=n;i++) //逐個字符求郝夫曼編碼

{

start=n-1; //編碼結(jié)束符位置

for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent) //從葉子到根逆向求編碼

{

if(ht[f].lchild==c)cd[--start]='0';

else

cd[--start]='1';

}

hc[i]=(char*)malloc((n-start)*sizeof(char)); //為第i個字符編碼分配空間

strcpy(hc[i],&cd[start]);//從cd復(fù)制編碼到hc

}

free(cd); //釋放工作空間

}

void main

{ int n,i;

int* w; //記錄權(quán)值

char* ch; //記錄字符

huffmantree ht;

huffmancode hc;

cout<<'請輸入待編碼的字符個數(shù)n=';

cin>>n;

w=(int*)malloc((n+1)*sizeof(int)); //記錄權(quán)值，號單元未用

ch=(char*)malloc((n+1)*sizeof(char));//記錄字符，號單元未用

cout<<'依次輸入待編碼的字符data及其權(quán)值weight'<

for(i=1;i<=n;i++)

{

cout<<'data['<

}

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告2

一、實(shí)驗(yàn)?zāi)康募耙?/p>

1)掌握棧和隊(duì)列這兩種特殊的線性表，熟悉它們的特性，在實(shí)際問題背景下靈活運(yùn)用它們。

本實(shí)驗(yàn)訓(xùn)練的要點(diǎn)是“?！焙汀瓣?duì)列”的觀點(diǎn);

二、實(shí)驗(yàn)內(nèi)容

1) 利用棧，實(shí)現(xiàn)數(shù)制轉(zhuǎn)換。

2) 利用棧，實(shí)現(xiàn)任一個表達(dá)式中的語法檢查(選做)。

3) 編程實(shí)現(xiàn)隊(duì)列在兩種存儲結(jié)構(gòu)中的基本操作(隊(duì)列的初始化、判隊(duì)列空、入隊(duì)列、出隊(duì)列);

三、實(shí)驗(yàn)流程、操作步驟或核心代碼、算法片段

順序棧：

status initstack(sqstack &s)

{

s.base=(elemtype*)malloc(stack_init_size*sizeof(elemtype));

if(!s.base)

return error;

s.top=s.base;

s.stacksize=stack_init_size;

return ok;

}

status destorystack(sqstack &s)

{

free(s.base);

return ok;

}

status clearstack(sqstack &s)

{

s.top=s.base;

return ok;

}

status stackempty(sqstack s)

{

if(s.base==s.top)

return ok;

return error;

}

int stacklength(sqstack s)

{

return s.top-s.base;

}

status gettop(sqstack s,elemtype &e)

{

if(s.top-s.base>=s.stacksize)

{

s.base=(elemtype *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(elemtype));

if(!s.base) return error;

s.top=s.base+s.stacksize;

s.stacksize+=stackincrement;

}

*s.top++=e;

return ok;

}

status push(sqstack &s,elemtype e)

{

if(s.top-s.base>=s.stacksize)

{

s.base=(elemtype *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(elemtype));

if(!s.base)

return error;

s.top=s.base+s.stacksize;

s.stacksize+=stackincrement;

}

*s.top++=e;

return ok;

}

status pop(sqstack &s,elemtype &e)

{

if(s.top==s.base)

return error;

e=*--s.top;

return ok;

}

status stacktraverse(sqstack s)

{

elemtype *p;

p=(elemtype *)malloc(sizeof(elemtype));

if(!p) return error;

p=s.top;

while(p!=s.base)//s.top上面一個...

{

p--;

printf('%d ',*p);

}

return ok;

}

status compare(sqstack &s)

{

int flag,ture=ok,false=error;

elemtype e,x;

initstack(s);

flag=ok;

printf('請輸入要進(jìn)?；虺鰲５脑兀?);

while((x= getchar)!='#'&&flag)

{

switch (x)

{

case '(':

case '[':

case '{':

if(push(s,x)==ok)

printf('括號匹配成功! ');

break;

case ')':

if(pop(s,e)==error || e!='(')

{

printf('沒有滿足條件 ');

flag=false;

}

break;

case ']':

if ( pop(s,e)==error || e!='[')

flag=false;

break;

case '}':

if ( pop(s,e)==error || e!='{')

flag=false;

break;

}

}

if (flag && x=='#' && stackempty(s))

return ok;

else

return error;

}

鏈隊(duì)列：

status initqueue(linkqueue &q)

{

q.front =q.rear=

(queueptr)malloc(sizeof(qnode));

if (!q.front) return error;

q.front->next = null;

return ok;

}

status destoryqueue(linkqueue &q)

{

while(q.front)

{

q.rear=q.front->next;

free(q.front);

q.front=q.rear;

}

return ok;

}

status queueempty(linkqueue &q)

{

if(q.front->next==null)

return ok;

return error;

}

status queuelength(linkqueue q)

{

int i=0;

queueptr p,q;

p=q.front;

while(p->next)

{

i++;

p=q.front;

q=p->next;

p=q;

}

return i;

}

status gethead(linkqueue q,elemtype &e)

{

queueptr p;

p=q.front->next;

if(!p)

return error;

e=p->data;

return e;

}

status clearqueue(linkqueue &q)

{

queueptr p;

while(q.front->next )

{

p=q.front->next;

free(q.front);

q.front=p;

}

q.front->next=null;

q.rear->next=null;

return ok;

}

status enqueue(linkqueue &q,elemtype e)

{

queueptr p;

p=(queueptr)malloc(sizeof (qnode));

if(!p)

return error;

p->data=e;

p->next=null;

q.rear->next = p;

q.rear=p; //p->next 為空

return ok;

}

status dequeue(linkqueue &q,elemtype &e)

{

queueptr p;

if (q.front == q.rear)

return error;

p = q.front->next;

e = p->data;

q.front->next = p->next;

if (q.rear == p)

q.rear = q.front; //只有一個元素時(不存在指向尾指針)

free (p);

return ok;

}

status queuetraverse(linkqueue q)

{

queueptr p,q;

if( queueempty(q)==ok)

{

printf('這是一個空隊(duì)列! ');

return error;

}

p=q.front->next;

while(p)

{

q=p;

printf('%d<- ',q->data);

q=p->next;

p=q;

}

return ok;

}

循環(huán)隊(duì)列：

status initqueue(sqqueue &q)

{

q.base=(qelemtype*)malloc(maxqsize*sizeof(qelemtype));

if(!q.base)

exit(owerflow);

q.front=q.rear=0;

return ok;

}

status enqueue(sqqueue &q,qelemtype e)

{

if((q.rear+1)%maxqsize==q.front)

return error;

q.base[q.rear]=e;

q.rear=(q.rear+1)%maxqsize;

return ok;

}

status dequeue(sqqueue &q,qelemtype &e)

{

if(q.front==q.rear)

return error;

e=q.base[q.front];

q.front=(q.front+1)%maxqsize;

return ok;

}

int queuelength(sqqueue q)

{

return(q.rear-q.front+maxqsize)%maxqsize;

}

status destoryqueue(sqqueue &q)

{

free(q.base);

return ok;

}

status queueempty(sqqueue q) //判空

{

if(q.front ==q.rear)

return ok;

return error;

}

status queuetraverse(sqqueue q)

{

if(q.front==q.rear)

printf('這是一個空隊(duì)列!');

while(q.front%maxqsize!=q.rear)

{

printf('%d<- ',q.base[q.front]);

q.front++;

}

return ok;

}

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告3

《數(shù)據(jù)結(jié)構(gòu)與算法》實(shí)驗(yàn)報(bào)告

專業(yè) 班級 姓名 學(xué)號

實(shí)驗(yàn)項(xiàng)目

實(shí)驗(yàn)一 二叉樹的應(yīng)用

實(shí)驗(yàn)?zāi)康?/p>

1、進(jìn)一步掌握指針變量的含義及應(yīng)用。

2、掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點(diǎn)及使用范圍。

3、掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。

實(shí)驗(yàn)內(nèi)容

題目1:編寫一個程序，采用一棵二叉樹表示一個家譜關(guān)系。要求程序具有如下功能：

（1）用括號表示法輸出家譜二叉樹，

（2）查找某人的所有兒子，

（3）查找某人的所有祖先。

算法設(shè)計(jì)分析

（一）數(shù)據(jù)結(jié)構(gòu)的定義

為了能夠用二叉樹表示配偶、子女、兄弟三種關(guān)系，特采用以下存儲關(guān)系，則能在二叉樹上實(shí)現(xiàn)家譜的各項(xiàng)運(yùn)算。

二叉樹型存儲結(jié)構(gòu)定義為：

typedef struct snode

{char name[max]; //人名

struct snode *left;//指向配偶結(jié)點(diǎn)

struct snode *right; //指向兄弟或子女結(jié)點(diǎn)

}fnode;

（二）總體設(shè)計(jì)

實(shí)驗(yàn)由主函數(shù)、家譜建立函數(shù)、家譜輸出函數(shù)、兒子查找函數(shù)、祖先查找函數(shù)、結(jié)點(diǎn)定位函數(shù)、選擇界面函數(shù)七個函數(shù)共同組成。其功能描述如下：

（1）主函數(shù)：統(tǒng)籌調(diào)用各個函數(shù)以實(shí)現(xiàn)相應(yīng)功能

void main

（2）家譜建立函數(shù)：與用戶交互建立家族成員對應(yīng)關(guān)系

void initialfamily(fnode *&head) //家譜建立函數(shù)

（3）家譜輸出函數(shù)：用括號表示法輸出家譜

輸出形式為：父和母（子1和子妻1（孫1），子2和子妻2（孫2））

void printfamily(fnode *head) //家譜輸出函數(shù)

（4）兒子查找函數(shù)：在家譜中查找到某人所有的子女并輸出，同時也能辨別出其是否為家族成員與是否有子女

void findson(fnode *b,char p[]) //兒子查找函數(shù)

（5）祖先查找函數(shù)：在家譜中查找到某人所有的祖先并輸出，同時也能辨別出其是否為家族中成員。

int findancestor(fnode *head,char son[ ]) //祖先查找函數(shù)

（6）結(jié)點(diǎn)定位函數(shù)：在家譜中找到用戶輸入人名所對應(yīng)的結(jié)點(diǎn)。

fnode *findnode(fnode *b,char p[]) //結(jié)點(diǎn)定位函數(shù)

（7）選擇界面函數(shù)：為便于編寫程序，將用戶選擇部分獨(dú)立為此函數(shù)。

void print(int &n)

（三）各函數(shù)的詳細(xì)設(shè)計(jì)：

void initialfamily(fnode *&head) //家譜建立函數(shù)

1：首先建立當(dāng)前人的信息，將其左右結(jié)點(diǎn)置為空，

2：然后讓用戶確定其是否有配偶，如果沒有配偶，則當(dāng)前程序結(jié)束，

3：如果有則建立其配偶信息，并將配偶結(jié)點(diǎn)賦給當(dāng)前人的左結(jié)點(diǎn)；

4：再讓用戶確定其是否有子女，如果有則遞歸調(diào)用家譜建立函數(shù)建立子女結(jié)點(diǎn)，并將其賦給配偶結(jié)點(diǎn)的下一個右結(jié)點(diǎn)。

5：如無，則程序結(jié)束

void printfamily(fnode *head) //家譜輸出函數(shù)

1：首先判斷當(dāng)前結(jié)點(diǎn)是否為空，如果為空則結(jié)束程序；

2：如果不為空，則輸出當(dāng)前結(jié)點(diǎn)信息，

3：然后判斷其左結(jié)點(diǎn)（配偶結(jié)點(diǎn)）是否為空，如不為空則輸出“和配偶信息。

4：再判斷配偶結(jié)點(diǎn)的右結(jié)點(diǎn)是否為空，如不為空則遞歸調(diào)用輸出其子女信息，最后輸出“）”；

5：當(dāng)配偶結(jié)點(diǎn)為空時，則判斷其右結(jié)點(diǎn)（兄弟結(jié)點(diǎn)）是否為空

6：如果不為空，則輸出“，”，并遞歸調(diào)用輸出兄弟信息

7程序結(jié)束

fnode *findnode(fnode *b,char p[]) //結(jié)點(diǎn)定位函數(shù)

1：當(dāng)前結(jié)點(diǎn)是否為空，為空則返回空；

2：如果和查找信息相同，則返回當(dāng)前結(jié)點(diǎn)；

3：如不然，則先后遞歸訪問其左結(jié)點(diǎn)，再不是則遞歸訪問右結(jié)點(diǎn)

void findson(fnode *b,char p[]) //兒子查找函數(shù)

1：在家譜中定位到要查找的結(jié)點(diǎn)，如無則輸出“查找不到此人”

2：判斷其配偶結(jié)點(diǎn)與子女結(jié)點(diǎn)是否為空，為空則輸出“無子女”

3：不為空則輸出其配偶結(jié)點(diǎn)的所有右結(jié)點(diǎn)（子女結(jié)點(diǎn)）。

int findancestor(fnode *head,char son[ ]) //祖先查找函數(shù)

1：先在家譜中定位到要查找的結(jié)點(diǎn)，如為空輸出“不存在此人”，程序結(jié)束

2：先將父母結(jié)點(diǎn)入棧，當(dāng)棧為空時程序結(jié)束，

3：棧不為空時，判斷棧頂元素是否已訪問過，

4：訪問過，再判斷是否為查找結(jié)點(diǎn)，如是則輸出棧中保存的其祖先結(jié)點(diǎn)，并濾過其兄弟結(jié)點(diǎn)不輸出；不是查找結(jié)點(diǎn)，則退棧一個元素

5：未訪問過，則取當(dāng)前棧頂元素，置訪問標(biāo)志——1，同時取其右結(jié)點(diǎn)

6：棧不為空或當(dāng)前所取結(jié)點(diǎn)不為空時，轉(zhuǎn)到2；

實(shí)驗(yàn)測試結(jié)果及結(jié)果分析

（一）測試結(jié)果

（二）結(jié)果分析

（略）

實(shí)驗(yàn)總結(jié)

（略）

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

篇九 北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

北京郵電大學(xué)信息與通信工程學(xué)院

2009級數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)名稱： 實(shí)驗(yàn)三哈夫曼編/解碼器的實(shí)現(xiàn)

學(xué)生姓名：陳聰捷

日 期： 2010年11月28日

1.實(shí)驗(yàn)要求

一、實(shí)驗(yàn)?zāi)康模?/p>

了解哈夫曼樹的思想和相關(guān)概念;

二、實(shí)驗(yàn)內(nèi)容：

利用二叉樹結(jié)構(gòu)實(shí)現(xiàn)哈夫曼編/解碼器

1.初始化：能夠?qū)斎氲娜我忾L度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個字符的頻度，并建立哈夫曼樹。

2.建立編碼表：利用已經(jīng)建好的哈夫曼樹進(jìn)行編碼，并將每個字符的編碼輸出。

3.編碼：根據(jù)編碼表對輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。

4.譯碼：利用已經(jīng)建好的哈夫曼樹對編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。

5.打?。阂灾庇^的方式打印哈夫曼樹。

6.計(jì)算輸入的字符串編碼前和編碼后的長度，并進(jìn)行分析，討論哈夫曼編碼的壓縮效果。

7.用戶界面可以設(shè)計(jì)成“菜單”方式，能進(jìn)行交互，根據(jù)輸入的字符串中每個字符出現(xiàn)的次數(shù)統(tǒng)計(jì)頻度，對沒有出現(xiàn)的字符一律不用編碼。

2. 程序分析

2.1 存儲結(jié)構(gòu)

二叉樹

template

class bitree

{

public:

bitree; //構(gòu)造函數(shù)，其前序序列由鍵盤輸入

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

binode* getroot; //獲得指向根結(jié)點(diǎn)的指針

protected:

binode *root; //指向根結(jié)點(diǎn)的頭指針

};

//聲明類bitree及定義結(jié)構(gòu)binode

data：

二叉樹是由一個根結(jié)點(diǎn)和兩棵互不相交的左右子樹構(gòu)成

哈夫曼樹類的數(shù)據(jù)域，繼承節(jié)點(diǎn)類型為int的二叉樹 class huffmantree:public bitree

data:

hcode* hcodetable;//編碼表

int tsize; //編碼表中的總字符數(shù)

二叉樹的節(jié)點(diǎn)結(jié)構(gòu)

template

struct binode //二叉樹的結(jié)點(diǎn)結(jié)構(gòu) {

t data; //記錄數(shù)據(jù)

t lchild; //左孩子

t rchild; //右孩子

t parent; //雙親

};

編碼表的節(jié)點(diǎn)結(jié)構(gòu)

struct hcode

{

char data; //編碼表中的字符

char code[100]; //該字符對應(yīng)的編碼

};

待編碼字符串由鍵盤輸入，輸入時用鏈表存儲，鏈表節(jié)點(diǎn)為 struct node

{

char character; //輸入的字符

unsigned int count;//該字符的權(quán)值

bool used; //建立樹的時候該字符是否使用過

node* next; //保存下一個節(jié)點(diǎn)的地址

};

示意圖：

2.2 關(guān)鍵算法分析

1.初始化函數(shù)(void huffmantree::init(string input))

算法偽代碼：

1.初始化鏈表的頭結(jié)點(diǎn)

2.獲得輸入字符串的第一個字符，并將其插入到鏈表尾部,n=1(n記錄的是鏈表

中字符的個數(shù))

3.從字符串第2個字符開始，逐個取出字符串中的字符

3.1 將當(dāng)前取出的字符與鏈表中已經(jīng)存在的字符逐個比較，如果當(dāng)前取出

的字符與鏈表中已經(jīng)存在的某個字符相同，則鏈表中該字符的權(quán)值加1。

3.2 如果當(dāng)前取出的字符與鏈表中已經(jīng)存在的字符都不相同，則將其加入

到鏈表尾部，同時n++

4.tsize=n(tsize記錄鏈表中字符總數(shù)，即哈夫曼樹中葉子節(jié)點(diǎn)總數(shù))

5.創(chuàng)建哈夫曼樹

6.銷毀鏈表

源代碼：

void huffmantree::init(string input)

{

node *front=new node; //初始化鏈表的頭結(jié)點(diǎn)

if(!front)

throw exception('堆空間用盡');

front->;next=null;

front->;character=null;

front->;count=0;

node *pfront=front;

char ch=input[0]; //獲得第一個字符

node* new1=new node;

if(!new1)

throw exception('堆空間用盡');

new1->;character=ch; //將第一個字符插入鏈表

new1->;count=1;

new1->;next=pfront->;next;

pfront->;next=new1;

bool replace=0; //判斷在已經(jīng)寫入鏈表的字符中是否有與當(dāng)前讀出的字符相同的字符 int n=1; //統(tǒng)計(jì)鏈表中字符個數(shù)

for(int i=1;i

{

ch=input[i]; //獲得第i個字符

do

{

pfront=pfront->;next;

if((int)pfront->;character == (int)ch) //如果在鏈表中有與當(dāng)前字符相同的字符，

該字符權(quán)值加1

{

pfront->;count++;

replace=1;

break;

}

}while(pfront->;next);

if(!replace) //如果在鏈表中沒找到與當(dāng)前字符相同的字符，則將該字符作為新成 員插入鏈表

{

node* new=new node;

if(!new)

throw exception('堆空間用盡');

new->;character=ch;

new->;count=1;

new->;next=pfront->;next;

pfront->;next=new;

n++;

}

pfront=front; //重置pfront和replace變量為默認(rèn)值 replace=0;

}

tsize=n; //tsize記錄的是編碼表中字符個數(shù)

createhtree(front,n); //創(chuàng)建哈夫曼樹

pfront=front;

while(pfront) //銷毀整個鏈表

{

front=pfront;

pfront=pfront->;next;

front;

}

時間復(fù)雜度：

若輸入的字符串長度為n，則時間復(fù)雜度為o(n)

2.創(chuàng)建哈夫曼樹(void huffmantree::createcodetable(node *p))

算法偽代碼：

1. 創(chuàng)建一個長度為2*tsize-1的三叉鏈表

2. 將存儲字符及其權(quán)值的鏈表中的字符逐個寫入三叉鏈表的前tsize個結(jié)點(diǎn)

的data域，并將對應(yīng)結(jié)點(diǎn)的孩子域和雙親域賦為空

3. 從三叉鏈表的第tsize個結(jié)點(diǎn)開始，i=tsize

3.1 從存儲字符及其權(quán)值的鏈表中取出兩個權(quán)值最小的結(jié)點(diǎn)x,y，記錄其

下標(biāo)x,y。

3.2 將下標(biāo)為x和y的哈夫曼樹的結(jié)點(diǎn)的雙親設(shè)置為第i個結(jié)點(diǎn)

3.3 將下標(biāo)為x的結(jié)點(diǎn)設(shè)置為i結(jié)點(diǎn)的左孩子，將下標(biāo)為y的結(jié)點(diǎn)設(shè)置為

i結(jié)點(diǎn)的右孩子，i結(jié)點(diǎn)的權(quán)值為x結(jié)點(diǎn)的權(quán)值加上y結(jié)點(diǎn)的權(quán)值，i

結(jié)點(diǎn)的雙親設(shè)置為空

4. 根據(jù)哈夫曼樹創(chuàng)建編碼表

源代碼：

void huffmantree::createhtree(node *p,int n)

{

root= new binode[2*n-1]; //初始化哈夫曼樹

node *front=p->;next;

if(n==0)

throw exception('沒有輸入字符');

for(int i=0;i

root[i].data=front->;count;

root[i].lchild=-1;

root[i].rchild=-1;

root[i].parent=-1;

front=front->;next;

}

front=p;

int new1,new2;

for(i=n;i<2*n-1;i++)

{

selectmin(new1,new2,0,i); //從0~i中選出兩個權(quán)值最小的結(jié)點(diǎn)

root[new1].parent=root[new2].parent=i; //用兩個權(quán)值最小的結(jié)點(diǎn)生成新結(jié)點(diǎn)，

新節(jié)點(diǎn)為其雙親

root[i].data=root[new1].data+root[new2].data;//新結(jié)點(diǎn)的權(quán)值為其孩子的權(quán)值的和 root[i].lchild=new1;

root[i].rchild=new2;

root[i].parent=-1;

}

createcodetable(p); //創(chuàng)建編碼表

}

時間復(fù)雜度：

在選取兩個權(quán)值最小的結(jié)點(diǎn)的函數(shù)中要遍歷鏈表，時間復(fù)雜度為o(n),故該函數(shù)

的時間復(fù)雜度為o(n^2)

3.創(chuàng)建編碼表(void huffmantree::createcodetable(node *p))

算法偽代碼：

1.初始化編碼表

2.初始化一個指針，從鏈表的頭結(jié)點(diǎn)開始，遍歷整個鏈表

2.1 將鏈表中指針當(dāng)前所指的結(jié)點(diǎn)包含的字符寫入編碼表中

2.2 得到該結(jié)點(diǎn)對應(yīng)的哈夫曼樹的葉子結(jié)點(diǎn)及其雙親

2.3 如果哈夫曼樹只有一個葉子結(jié)點(diǎn)，將其字符對應(yīng)編碼設(shè)置為0

2.4 如果不止一個葉子結(jié)點(diǎn)，從當(dāng)前葉子結(jié)點(diǎn)開始判斷

2.4.1 如果當(dāng)前葉子結(jié)點(diǎn)是其雙親的左孩子，則其對應(yīng)的編碼為0，否

則為1

2.4.2 child指針指向葉子結(jié)點(diǎn)的雙親，parent指針指向child指針的雙親，

重復(fù)2.4.1的操作

2.5 將已完成的編碼倒序

2.6 取得鏈表中的下一個字符

3.輸出編碼表

源代碼：

void huffmantree::createcodetable(node *p)

{

hcodetable=new hcode[tsize]; //初始化編碼表

node *front=p->;next;

for(int i=0;i

{

hcodetable[i].data=front->;character; //將第i個字符寫入編碼表

int child=i; //得到第i個字符對應(yīng)的葉子節(jié)點(diǎn)

int parent=root[i].parent; //得到第i個字符對應(yīng)的葉子節(jié)點(diǎn)的雙親

int k=0;

if(tsize==1) //如果文本中只有一種字符，它的.編碼為0

{

hcodetable[i].code[k]='0';

k++;

}

while(parent!=-1) //從第i個字符對應(yīng)的葉子節(jié)點(diǎn)開始，尋找它到根結(jié)點(diǎn)的路徑

{

if(child==root[parent].lchild) //如果當(dāng)前結(jié)點(diǎn)為雙親的左孩子，則編碼為0，

否則編碼為1

hcodetable[i].code[k]='0';

else

hcodetable[i].code[k]='1';

k++;

child=parent;

parent=root[child].parent;

}

hcodetable[i].code[k]='';

reverse(hcodetable[i].code); //將編碼逆置

front=front->;next; //得到下一個字符

}

cout<<'編碼表為：'<

for(i=0;i

{

cout<

parent=root[parent].lchild;

else //編碼為1則尋找右孩子

parent=root[parent].rchild;

i++;

}

if(tsize==1) //如果編碼表只有一個字符，則根結(jié)點(diǎn)即為葉子結(jié)點(diǎn) i++;

d.append(1,hcodetable[parent].data);//將葉子節(jié)點(diǎn)對應(yīng)的字符追加到解碼串中 }

cout<

}

時間復(fù)雜度：

設(shè)待解碼串長度為n，則復(fù)雜度為o(n)

8. 計(jì)算哈夫曼編碼的壓縮比(void huffmantree::calculate(string s1,string s2)) 算法偽代碼：

1. 獲得編碼前字符串的長度，即其占用的字節(jié)數(shù)

2. 獲得編碼后的字符串的長度，將其除以8然后向上取整，得到其占用的字

節(jié)數(shù)

3. 壓縮比將兩個相除

源代碼：

void huffmantree::calculate(string s1,string s2)

{

int cal1=s1.length;

int cal2=s2.length;

cal2=ceill((float)cal2/8); //將編碼串的比特?cái)?shù)轉(zhuǎn)化為字節(jié)數(shù) cout<<'編碼前的字符串長度：'<

cout<<'編碼后的字符串長度：'<

cout<<'壓縮比為：'<<((double)cal2/(double)cal1)*100<<'%'<

}

時間復(fù)雜度：

o(1)

9. 打印哈夫曼樹(void huffmantree::printtree(int treenode,int layer) ) 算法偽代碼：

1. 如果待打印結(jié)點(diǎn)為空，則返回

2. 遞歸調(diào)用函數(shù)打印當(dāng)前結(jié)點(diǎn)的右子樹

3. 根據(jù)當(dāng)前結(jié)點(diǎn)所在的層次確定其前面要輸出多少空格，先輸出空格，在打

印當(dāng)前結(jié)點(diǎn)的權(quán)值

4. 遞歸調(diào)用函數(shù)打印當(dāng)前結(jié)點(diǎn)的左子樹

源代碼：

void huffmantree::printtree(int treenode,int layer)

{

if(treenode==-1) //如果待打印結(jié)點(diǎn)為空，則返回 return;

else

{

printtree(root[treenode].rchild,layer+1); //先打印該結(jié)點(diǎn)的右子樹，layer記錄

的是該結(jié)點(diǎn)所在的層次

for(int i=0;i

空格

cout<<' ';

cout<

printtree(root[treenode].lchild,layer+1); //打印該結(jié)點(diǎn)的左子樹

}

}

時間復(fù)雜度：

中序遍歷哈夫曼樹，復(fù)雜度為o(n)

10. 菜單函數(shù)(void huffmantree::menu)

算法偽代碼：

1. 逐一讀取鍵盤緩存區(qū)中的字符，并將它們逐一追加到記錄輸入字符串的

string變量中，直到讀到回車輸入符為止

2. 刪除string變量末尾的回車輸入符

3.利用string變量創(chuàng)建哈夫曼樹，初始化編碼表。

4. 直觀打印哈夫曼樹

5. 對輸入的字符串進(jìn)行編碼

6. 對編碼后的字符串進(jìn)行解碼

7. 計(jì)算編碼前后的壓縮比并輸出

源代碼：

void huffmantree::menu

{

cout<<'請輸入你要編碼的文本,按回車鍵確定輸入'<

string input;

char letter;

do //將字符逐個讀入input變量中

{

letter=cin.get;

input.append(1,letter);

}while(letter!=' ');

input.erase(input.length-1,1); //去掉input末尾的回車符

init(input); //根據(jù)輸入的字符串創(chuàng)建哈夫曼樹及其編碼表 cout<<'直觀打印哈夫曼樹'<

printtree(2*tsize-1-1,1); //打印哈夫曼樹

cout<<' '<<' ';

string d1,d2;

cout<<'編碼后的字符串為'<

encode(input,d1); //編碼并打印編碼串

cout<<'解碼后的字符串為'<

decode(d1,d2); //解碼并打印解碼串

cout<<'ascii碼編碼與huffman編碼的比較'<

calculate(input,d1); //計(jì)算編碼前后的壓縮比

}

2.3 其他

1.由于題目要求能輸入任意長的字符串，所以本程序采用了string變量來記錄輸入

的字符串，并采用string類的類成員函數(shù)來完成各項(xiàng)任務(wù)

2.打印哈夫曼樹時采用了遞歸函數(shù)，且采用了凹凸表的形式打印哈夫曼樹。

3.為了輸入空格，輸入時采取逐個字符輸入的方式

3. 程序運(yùn)行結(jié)果

主函數(shù)流程圖：

運(yùn)行結(jié)果：

各函數(shù)運(yùn)行正常，沒有出現(xiàn)bug

4. 總結(jié)

經(jīng)過這次實(shí)驗(yàn)，我了解了哈夫曼樹的創(chuàng)建過程，了解了一種不等長編碼的方法，用設(shè)斷點(diǎn)調(diào)試的方法更加熟練，同時熟悉了stl中string類型的用法，對c++更加熟悉