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

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

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

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

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

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

學(xué)號(hào):____201240703061___________________

班級(jí):_________軟件二班______________

姓名:________朱海霞______________

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

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

2024年10月

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

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

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

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

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

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

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

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

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

for(p=&(l.elem);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);

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);

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

printf(' %d'，l.elem);

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

listinsert_sq(l，3，24);

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

printf(' %d'，l.elem);

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

int e;

listdelete_sq(l，2， e);

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

printf(' %d'，l.elem);//刪除一個(gè)數(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

心得體會(huì)：

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

實(shí)驗(yàn)題目：?jiǎn)捂湵淼牟迦牒蛣h除

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

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

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

建立一個(gè)數(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)，測(cè)試程序的如下功能：不允許重復(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 _ne_t;

}lnode，_linklist;

int initlist_l(linklist &l){

l=(linklist)malloc(sizeof(lnode)); l->;ne_t=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->;ne_t;++j;

}

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

return error;

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

s->;ne_t=p->;ne_t;

p->;ne_t=s;

return ok;

}

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

int j;

p=l;j=0;

while(p->;ne_t&&j

p=p->;ne_t;++j;

}

if(！(p->;ne_t)||j

return error;

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

return ok;

}

int main{

linklist l，p;

char a={'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);

p=l->;ne_t;

while(p！=null){

printf('%c '，p->;data); p=p->;ne_t;

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

}

}//插入八個(gè)字符 printf(' '); i=2; int e; listinsert_l(l，i，'b'); p=l->;ne_t; while(p！=null){ printf('%c '，p->;data); p=p->;ne_t; }//插入一個(gè)字符 printf(' '); i=3; listdelete_l(l，i，e); p=l->;ne_t; while(p！=null){ printf('%c '，p->;data); p=p->;ne_t; } 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

心得體會(huì)：

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)利用棧的基本操作對(duì)給定的字符串判斷其是否是回文，若是則輸出“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)前已分配的存儲(chǔ)空間，以元素為單位

} sqstack;

int initstack(sqstack &s)

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

if(！(s.base=(int _)malloc(stack_init_size_sizeof(int))))

e_it(overflow); // 存儲(chǔ)分配失敗

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) // 棧滿，追加存儲(chǔ)空間

{

s.base=(int _)realloc(s.base，(s.stacksize+stackincrement)_sizeof(int)); if(！s.base)

e_it(overflow); // 存儲(chǔ)分配失敗

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 = {0}，_p，b = {0};

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

{

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

gets(ch);

p=ch;

while(_p) // 沒到串尾

push(s，_p++);

for(i=0;i

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

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

b=e;

}

}

for(i=0;i

if(ch！=b)

k=0;

}

if(k==0)

printf('no！');

else

printf('輸出:')

printf('yes！');

}

return 0;

}

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

請(qǐng)輸入表達(dá)式：

abcba

輸出：yes！

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

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

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

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

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

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

采用二叉樹鏈表作為存儲(chǔ)結(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é)果：

心得體會(huì)：

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

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

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

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

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

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

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

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

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

#include'stdio.h'

#include'stdlib.h'

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

typedef struct{

char ve_s; //頂點(diǎn)表

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

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

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

void creatmgraph(mgraph _g)

{

int i，j，k;

char a;

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

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

scanf('%c'，&a);

printf('input verte_ string:');

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

{

scanf('%c'，&a);

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

}

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

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

g->;edges=0; //初始化鄰接矩陣

printf('input edges，creat adjacency matri_ ');

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

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

g->;edges=1;;g->;edges=1;//若為;//=========定義標(biāo)志向量，為全局變量=;typedefenum{false，true}b;booleanvisited=1;

g->;edges=1; //若為無(wú)向圖，矩陣為對(duì)稱矩陣;若建立有向圖，去掉該條語(yǔ)句 }

}

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

typedef enum{false，true} boolean;

boolean visited;

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

void dfsm(mgraph _g，int i)

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

給出你的編碼

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

void bfs(mgraph _g，int k)

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

給出你的編碼

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

void main

{

int i;

mgraph _g;

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

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

printf('print graph dfs: ');

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

printf(' ');

printf('print graph bfs: ');

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

printf(' ');

}

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

#include'stdio.h'

#include'stdlib.h'

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

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

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

struct node _ne_t; //鏈域

}edgenode;

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

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

edgenode _firstedge; //邊表頭指針

}verte_node;

typedef verte_node adjlist; //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 verte_num(n) and edgesnum(e): ');

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

scanf('%c'，&a);

printf('input verte_ string:');

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

{

scanf('%c'，&a);

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

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

}

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

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

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

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

s->;adjve_=j; //鄰接點(diǎn)序號(hào)為j

s->;ne_t=g->;adjlist.firstedge;

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

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

s->;adjve_=i; //鄰接點(diǎn)序號(hào)為i

s->;ne_t=g->;adjlist.firstedge;

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

}

}

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

typedef enum{false，true} boolean;

boolean visited;

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

void dfsm(algraph _g，int i)

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

給出你的編碼

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

void bfs(algraph _g，int k)

{ //以vk為源點(diǎn)對(duì)用鄰接鏈表表示的圖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. 鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)

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

心得體會(huì)：

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

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

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

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

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

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

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

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

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

3. 如何利用二分查找算法在一個(gè)有序表中插入一個(gè)元素_，并保持表的有序性？

程序代碼

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

心得體會(huì)：

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

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

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

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

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

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

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

程序代碼

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

心得體會(huì)：

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

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

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

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

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

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

日 期： 2024年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(zhǎng)度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立哈夫曼樹。

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

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

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

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

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

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

2. 程序分析

2.1 存儲(chǔ)結(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：

二叉樹是由一個(gè)根結(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; //該字符對(duì)應(yīng)的編碼

};

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

{

char character; //輸入的字符

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

bool used; //建立樹的時(shí)候該字符是否使用過(guò)

node_ ne_t; //保存下一個(gè)節(jié)點(diǎn)的地址

};

示意圖：

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

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

算法偽代碼：

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

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

中字符的個(gè)數(shù))

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

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

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

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

到鏈表尾部，同時(shí)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 e_ception('堆空間用盡');

front->;ne_t=null;

front->;character=null;

front->;count=0;

node _pfront=front;

char ch=input; //獲得第一個(gè)字符

node_ new1=new node;

if(！new1)

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

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

new1->;count=1;

new1->;ne_t=pfront->;ne_t;

pfront->;ne_t=new1;

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

for(int i=1;i

{

ch=input; //獲得第i個(gè)字符

do

{

pfront=pfront->;ne_t;

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

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

{

pfront->;count++;

replace=1;

break;

}

}while(pfront->;ne_t);

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

{

node_ new=new node;

if(！new)

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

new->;character=ch;

new->;count=1;

new->;ne_t=pfront->;ne_t;

pfront->;ne_t=new;

n++;

}

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

}

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

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

pfront=front;

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

{

front=pfront;

pfront=pfront->;ne_t;

front;

}

時(shí)間復(fù)雜度：

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

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

算法偽代碼：

1. 創(chuàng)建一個(gè)長(zhǎng)度為2_tsize-1的三叉鏈表

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

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

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

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

下標(biāo)_，y。

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

3.3 將下標(biāo)為_的結(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)值為_結(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; //初始化哈夫曼樹

node _front=p->;ne_t;

if(n==0)

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

for(int i=0;i

root.data=front->;count;

root.lchild=-1;

root.rchild=-1;

root.parent=-1;

front=front->;ne_t;

}

front=p;

int new1，new2;

for(i=n;i<2_n-1;i++)

{

selectmin(new1，new2，0，i); //從0~i中選出兩個(gè)權(quán)值最小的結(jié)點(diǎn)

root.parent=root.parent=i; //用兩個(gè)權(quán)值最小的結(jié)點(diǎn)生成新結(jié)點(diǎn)，

新節(jié)點(diǎn)為其雙親

root.data=root.data+root.data;//新結(jié)點(diǎn)的權(quán)值為其孩子的權(quán)值的和 root.lchild=new1;

root.rchild=new2;

root.parent=-1;

}

createcodetable(p); //創(chuàng)建編碼表

}

時(shí)間復(fù)雜度：

在選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)的函數(shù)中要遍歷鏈表，時(shí)間復(fù)雜度為o(n)，故該函數(shù)

的時(shí)間復(fù)雜度為o(n^2)

3.創(chuàng)建編碼表(void huffmantree::createcodetable(node _p))

算法偽代碼：

1.初始化編碼表

2.初始化一個(gè)指針，從鏈表的頭結(jié)點(diǎn)開始，遍歷整個(gè)鏈表

2.1 將鏈表中指針當(dāng)前所指的結(jié)點(diǎn)包含的字符寫入編碼表中

2.2 得到該結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼樹的葉子結(jié)點(diǎn)及其雙親

2.3 如果哈夫曼樹只有一個(gè)葉子結(jié)點(diǎn)，將其字符對(duì)應(yīng)編碼設(shè)置為0

2.4 如果不止一個(gè)葉子結(jié)點(diǎn)，從當(dāng)前葉子結(jié)點(diǎn)開始判斷

2.4.1 如果當(dāng)前葉子結(jié)點(diǎn)是其雙親的左孩子，則其對(duì)應(yīng)的編碼為0，否

則為1

2.4.2 child指針指向葉子結(jié)點(diǎn)的雙親，parent指針指向child指針的雙親，

重復(fù)2.4.1的操作

2.5 將已完成的編碼倒序

2.6 取得鏈表中的下一個(gè)字符

3.輸出編碼表

源代碼：

void huffmantree::createcodetable(node _p)

{

hcodetable=new hcode; //初始化編碼表

node _front=p->;ne_t;

for(int i=0;i

{

hcodetable.data=front->;character; //將第i個(gè)字符寫入編碼表

int child=i; //得到第i個(gè)字符對(duì)應(yīng)的葉子節(jié)點(diǎn)

int parent=root.parent; //得到第i個(gè)字符對(duì)應(yīng)的葉子節(jié)點(diǎn)的雙親

int k=0;

if(tsize==1) //如果文本中只有一種字符，它的.編碼為0

{

hcodetable.code='0';

k++;

}

while(parent！=-1) //從第i個(gè)字符對(duì)應(yīng)的葉子節(jié)點(diǎn)開始，尋找它到根結(jié)點(diǎn)的路徑

{

if(child==root.lchild) //如果當(dāng)前結(jié)點(diǎn)為雙親的左孩子，則編碼為0，

否則編碼為1

hcodetable.code='0';

else

hcodetable.code='1';

k++;

child=parent;

parent=root.parent;

}

hcodetable.code='';

reverse(hcodetable.code); //將編碼逆置

front=front->;ne_t; //得到下一個(gè)字符

}

cout<<'編碼表為：'<

for(i=0;i

{

cout<

parent=root.lchild;

else //編碼為1則尋找右孩子

parent=root.rchild;

i++;

}

if(tsize==1) //如果編碼表只有一個(gè)字符，則根結(jié)點(diǎn)即為葉子結(jié)點(diǎn) i++;

d.append(1，hcodetable.data);//將葉子節(jié)點(diǎn)對(duì)應(yīng)的字符追加到解碼串中 }

cout<

}

時(shí)間復(fù)雜度：

設(shè)待解碼串長(zhǎng)度為n，則復(fù)雜度為o(n)

8. 計(jì)算哈夫曼編碼的壓縮比(void huffmantree::calculate(string s1，string s2)) 算法偽代碼：

1. 獲得編碼前字符串的長(zhǎng)度，即其占用的字節(jié)數(shù)

2. 獲得編碼后的字符串的長(zhǎng)度，將其除以8然后向上取整，得到其占用的字

節(jié)數(shù)

3. 壓縮比將兩個(gè)相除

源代碼：

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<<'編碼前的字符串長(zhǎng)度：'<

cout<<'編碼后的字符串長(zhǎng)度：'<

cout<<'壓縮比為：'<<((double)cal2/(double)cal1)_100<<'%'<

}

時(shí)間復(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.rchild，layer+1); //先打印該結(jié)點(diǎn)的右子樹，layer記錄

的是該結(jié)點(diǎn)所在的層次

for(int i=0;i

空格

cout<<' ';

cout<

printtree(root.lchild，layer+1); //打印該結(jié)點(diǎn)的左子樹

}

}

時(shí)間復(fù)雜度：

中序遍歷哈夫曼樹，復(fù)雜度為o(n)

10. 菜單函數(shù)(void huffmantree::menu)

算法偽代碼：

1. 逐一讀取鍵盤緩存區(qū)中的字符，并將它們逐一追加到記錄輸入字符串的

string變量中，直到讀到回車輸入符為止

2. 刪除string變量末尾的回車輸入符

3.利用string變量創(chuàng)建哈夫曼樹，初始化編碼表。

4. 直觀打印哈夫曼樹

5. 對(duì)輸入的字符串進(jìn)行編碼

6. 對(duì)編碼后的字符串進(jìn)行解碼

7. 計(jì)算編碼前后的壓縮比并輸出

源代碼：

void huffmantree::menu

{

cout<<'請(qǐng)輸入你要編碼的文本，按回車鍵確定輸入'<

string input;

char letter;

do //將字符逐個(gè)讀入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.由于題目要求能輸入任意長(zhǎng)的字符串，所以本程序采用了string變量來(lái)記錄輸入

的字符串，并采用string類的類成員函數(shù)來(lái)完成各項(xiàng)任務(wù)

2.打印哈夫曼樹時(shí)采用了遞歸函數(shù)，且采用了凹凸表的形式打印哈夫曼樹。

3.為了輸入空格，輸入時(shí)采取逐個(gè)字符輸入的方式

3. 程序運(yùn)行結(jié)果

主函數(shù)流程圖：

運(yùn)行結(jié)果：

各函數(shù)運(yùn)行正常，沒有出現(xiàn)bug

4. 總結(jié)

經(jīng)過(guò)這次實(shí)驗(yàn)，我了解了哈夫曼樹的創(chuàng)建過(guò)程，了解了一種不等長(zhǎng)編碼的方法，用設(shè)斷點(diǎn)調(diào)試的方法更加熟練，同時(shí)熟悉了stl中string類型的用法，對(duì)c++更加熟悉