第一篇 數據結構實驗報告650字
一.實驗內容：
實現哈夫曼編碼的生成算法。
二.實驗目的：
1、使學生熟練掌握哈夫曼樹的生成算法。
2、熟練掌握哈夫曼編碼的方法。
三.問題描述：
已知n個字符在原文中出現的頻率，求它們的哈夫曼編碼。
1、讀入n個字符，以及字符的權值，試建立一棵huffman樹。
2、根據生成的huffman樹，求每個字符的huffman編碼。并對給定的待編碼字符序列進行編碼，并輸出。
四.問題的實現
(1)郝夫曼樹的存儲表示
typedef struct{
unsigned int weight;
unsigned int parent，lchild，rchild;
}htnode，_huffmantree; //動態(tài)分配數組存儲郝夫曼樹
郝夫曼編碼的存儲表示
typedef char_ _huffmancode;//動態(tài)分配數組存儲郝夫曼編碼
(2)主要的實現思路：
a.首先定義郝夫曼樹的存儲形式，這里使用了數組
b.用select遍歷n個字符，找出權值最小的兩個
c.構造郝夫曼樹ht，并求出n個字符的郝夫曼編碼hc
總結
1.基本上沒有什么太大的問題，在調用select這個函數時，想把權值最小的兩個結點的序號帶回huffmancoding，所以把那2個序號設置成了引用。
2.在編程過程中，在什么時候分配內存，什么時候初始化花的時間比較長
3.最后基本上實現后，發(fā)現結果仍然存在問題，經過分步調試，發(fā)現了特別低級的輸入錯誤。把ht[i].weight=ht[s1].weight+ht[s2].weight;中的s2寫成了i
附：
//動態(tài)分配數組存儲郝夫曼樹
typedef struct{
int weight; //字符的.權值
int parent，lchild，rchild;
}htnode，_huffmantree;
//動態(tài)分配數組存儲郝夫曼編碼
typedef char_ _huffmancode;
//選擇n個(這里是k=n)節(jié)點中權值最小的兩個結點
void select(huffmantree &ht，int k，int &s1，int &s2)
{ int i;
i=1;
while(i<=k && ht[i].parent！=0)i++;
//下面選出權值最小的結點，用s1指向其序號
s1=i;
for(i=1;i<=k;i++)
{
if(ht[i].parent==0&&ht[i].weight
}
//下面選出權值次小的結點，用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
}
}
//構造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個結點
ht=(huffmantree)malloc((m+1)_sizeof(htnode)); //0號單元未用，預分配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); //選出當前權值最小的
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]='';//編碼結束符
for(i=1;i<=n;i++) //逐個字符求郝夫曼編碼
{
start=n-1; //編碼結束符位置
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復制編碼到hc
}
free(cd); //釋放工作空間
}
void main
{ int n，i;
int_ w; //記錄權值
char_ ch; //記錄字符
huffmantree ht;
huffmancode hc;
cout<<'請輸入待編碼的字符個數n=';
cin>>n;
w=(int_)malloc((n+1)_sizeof(int)); //記錄權值，號單元未用
ch=(char_)malloc((n+1)_sizeof(char));//記錄字符，號單元未用
cout<<'依次輸入待編碼的字符data及其權值weight'<
for(i=1;i<=n;i++)
{
cout<<'data['<
}
第二篇 北郵數據結構實驗報告線性表1050字
北郵數據結構實驗報告線性表
實驗報告;課程名稱：數據結構班級：軟件工程實驗成績：;1206;實驗名稱：打印機隊列模擬學號：20124848批;程序的設計;實驗編號：實驗一姓名：實驗日期：2024年5月2;一、實驗目的;對隊列的理解;對stl中的queue的使用;實驗仿真一個網絡打印過程;二、實驗內容與實驗步驟流程圖;這個任務隊列的測試使用stl隊列適配器;具體地說，每一行中包含的信息是
實 驗 報 告
課程名稱：數據結構 班級：軟件工程實驗成績：
1206
實驗名稱：打印機隊列模擬學號：20124848 批閱教師簽字：
程序的設計
實驗編號：實驗一 姓名： 實驗日期：2024年5 月 24 日
一、實驗目的
對隊列的理解
對stl中的queue的使用
實驗仿真一個網絡打印過程
二、實驗內容與實驗步驟流程圖
這個任務隊列的測試使用stl隊列適配器。程序要求完成模擬的實現共享打印機。這個打印機使用先進先出隊列。仿真是通過讀取和處理事件數據文件的列表。一個有效的數據文件中的每一行包含信息打印作業(yè)和提交這份工作的時間。
具體地說，每一行中包含的信息是提交工作的時間(以秒為單位)，和在頁面的工作長及工作的計算機的名稱。在模擬的開始，每個這些事件的每一個應該被程序所讀，存儲在繼承工作負載隊列。程序應該通過循環(huán)遞增計數器或while-loop模擬時間的流逝。程序應該將計數器初始化為零，然后依次增加1秒。當模擬等于當前時間的打印作業(yè)的提交時間在工作隊列的前面，一個打印作業(yè)完成。當這一切發(fā)生的時候，從工作隊列取出這個事件，然后把它放在另一個隊列對象。這個隊列對象存儲已完成的打印作業(yè)。當程序仿真其他的打印工作的時候，這些工作在隊列等待。
win8，visual c++ 6.0
四、實驗過程與分析
(1)實驗主要函數及存儲結構
main.cpp 包括主函數和主要的功能
simulator.h 仿真類的聲明
simulator.cpp 仿真類的定義
event.h 事件類的聲明
event.cpp - 事件類的定義
job.h 作業(yè)類的聲明
job.cpp 作業(yè)類的.定義
arbitrary.run 包括任意打印作業(yè)數的數據文件
arbitrary.out 輸出 arbitrary.run
bigfirst.run 包括打印較大作業(yè)的數據文件
bigfirst.out 輸出 bigfirst.run
(2)實驗代碼
#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;
}
五、實驗結果總結
經測試，功能較為完整。代碼流程簡圖如下：
通過這次實驗，我了解了有關隊列方面的知識。掌握了隊列的邏輯結構，抽象數據類型，隊列的存儲方式等。運用先進先出表，仿真了網絡打印隊列。這都使我對數據結構的學習有了新的認識與幫助。在實驗過程中，我也遇到了許多困難，從開始時對隊列運算的不熟悉，到逐漸查找資料，從而完成了實驗;六、附錄;-《數據結構與算法分析》以及網上資料;
逐漸查找資料，從而完成了實驗。在今后的學習中，我將繼續(xù)努力，加強對堆棧，隊列等知識的學習，以達到精益求精。
六、附錄
-《數據結構與算法分析》以及網上資料
第三篇 數據結構實驗報告實驗五650字
數據結構實驗報告 實驗五
一.實驗內容：
實現哈夫曼編碼的生成算法。
二.實驗目的：
1、使學生熟練掌握哈夫曼樹的生成算法。
2、熟練掌握哈夫曼編碼的方法。
三.問題描述：
已知n個字符在原文中出現的頻率，求它們的哈夫曼編碼。
1、讀入n個字符，以及字符的.權值，試建立一棵huffman樹。
2、根據生成的huffman樹，求每個字符的huffman編碼。并對給定的待編碼字符序列進行編碼，并輸出。
四.問題的實現
(1)郝夫曼樹的存儲表示
typedef struct{
unsigned int weight;
unsigned int parent，lchild，rchild;
}htnode，_huffmantree; //動態(tài)分配數組存儲郝夫曼樹
郝夫曼編碼的存儲表示
typedef char_ _huffmancode;//動態(tài)分配數組存儲郝夫曼編碼
(2)主要的實現思路：
a.首先定義郝夫曼樹的存儲形式，這里使用了數組
b.用select遍歷n個字符，找出權值最小的兩個
c.構造郝夫曼樹ht，并求出n個字符的郝夫曼編碼hc
總結
1.基本上沒有什么太大的問題，在調用select這個函數時，想把權值最小的兩個結點的序號帶回huffmancoding，所以把那2個序號設置成了引用。
2.在編程過程中，在什么時候分配內存，什么時候初始化花的時間比較長
3.最后基本上實現后，發(fā)現結果仍然存在問題，經過分步調試，發(fā)現了特別低級的輸入錯誤。把ht[i].weight=ht[s1].weight+ht[s2].weight;中的s2寫成了i
附：
//動態(tài)分配數組存儲郝夫曼樹
typedef struct{
int weight; //字符的權值
int parent，lchild，rchild;
}htnode，_huffmantree;
//動態(tài)分配數組存儲郝夫曼編碼
typedef char_ _huffmancode;
//選擇n個(這里是k=n)節(jié)點中權值最小的兩個結點
void select(huffmantree &ht，int k，int &s1，int &s2)
{ int i;
i=1;
while(i<=k && ht[i].parent！=0)i++;
//下面選出權值最小的結點，用s1指向其序號
s1=i;
for(i=1;i<=k;i++)
{
if(ht[i].parent==0&&ht[i].weight
}
//下面選出權值次小的結點，用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
}
}
//構造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個結點
ht=(huffmantree)malloc((m+1)_sizeof(htnode)); //0號單元未用，預分配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); //選出當前權值最小的
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]='';//編碼結束符
for(i=1;i<=n;i++) //逐個字符求郝夫曼編碼
{
start=n-1; //編碼結束符位置
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復制編碼到hc
}
free(cd); //釋放工作空間
}
void main
{ int n，i;
int_ w; //記錄權值
char_ ch; //記錄字符
huffmantree ht;
huffmancode hc;
cout<<'請輸入待編碼的字符個數n=';
cin>;>;n;
w=(int_)malloc((n+1)_sizeof(int)); //記錄權值，號單元未用
ch=(char_)malloc((n+1)_sizeof(char));//記錄字符，號單元未用
cout<<'依次輸入待編碼的字符data及其權值weight'<
for(i=1;i<=n;i++)
{
cout<<'data['<
}
第四篇 數據結構實驗報告總結1450字
# include
# define ma__operator_num 100 //運算符棧數組長度
# define ma__data_num 100 //運算數棧數組長度
typedef struct opstack //定義運算符棧
{
char opstack[ma__operator_num];
int top;
}opstack， _popstack;
typedef struct datastack //定義運算數棧
{
double stack[ma__data_num];
int top;
}datastack， _pdatastack;
void initpopstack(popstack &postack) //初始化運算符棧
{
if( ！(postack = (popstack)malloc(sizeof(opstack)))) //為運算符棧分配空間
{
printf('分配內存空間失敗！ ');
e_it(-1);
}
postack->;top = -1;
}
void initpdatastack(pdatastack &pdstack) //初始化運算數棧
{
if( ！(pdstack = (pdatastack)malloc(sizeof(datastack)))) //為運算數棧分配空間
{
printf('分配內存空間失敗！ ');
e_it(-1);
}
pdstack->;top = -1;
}
void pushopstack(popstack &postack， char ch) //運算符進棧
{
postack->;opstack[++(postack->;top)] = ch;
}
void popopstack(popstack &postack， char &ch) //運算符出棧
{
ch = postack->;opstack[postack->;top];
postack->;top--;
}
void pushdatastack(pdatastack &pdstack， double d) //運算數進棧
{
++(pdstack->;top);
pdstack->;stack[pdstack->;top] = d;
}
void popdatastack(pdatastack &pdstack， double &d) //運算數出棧
{
d = pdstack->;stack[pdstack->;top];
pdstack->;top--;
}
void clearpopstack(popstack &postack) //清空運算符棧
{
postack->;top = -1;
}
void clearpdatastack(pdatastack &pdstack) //清空運算數棧
{
pdstack->;top = -1;
}
char gettoppopstack(popstack &postack) //獲取運算符棧頂元素
{
return postack->;opstack[postack->;top];
}
double gettoppdatastack(pdatastack &pdstack) //獲取運算數棧頂元素
{
return pdstack->;stack[pdstack->;top];
}
bool isop(char &ch) //區(qū)分 運算符 和 運算數 的函數，是運算符時返回true，否則返回false
{ //判斷是否為符號
if ( (ch == '+') || (ch == '-') || (ch == '_') || (ch == '/') || (ch == '=') || (ch == 'a') || (ch == 's') || (ch == 'a') || (ch == 's') || (ch == '(') || (ch == ')') )
return true;
else
return false;
}
char precede(char op1， char op2) //參考《數據結構》(c語言版)第53頁 3.2.5表達式求值 表 3.1
{
char tab[9][10]; //定義字符串的二維數組來存放運算符優(yōu)先級的關系
strcpy( tab[0]， '>;>;<<;<;' );
strcpy( tab， '>;>;<<;<;' );
strcpy( tab， '>;;<;' );
strcpy( tab[3]， '>;;<;' );
strcpy( tab[4]， '<<<<<=<
strcpy( tab[5]， '>;e>;' );
strcpy( tab[6]， '>;;' );
strcpy( tab[7]， '>;;' );
strcpy( tab[8]， '<<<<
printf(' | ___歡迎您的下次使用！謝謝！___ | '); //退出使用
printf(' |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ');
}
double operate(double a， char theta， double b) //對出棧的運算符和運算數進行計算
{
double s;
switch(theta)
{
case '+':
s = a + b;
break;
case '-':
s = a - b;
break;
case '_':
s = a _ b;
break;
case '/':
if ( b ！= 0 ) //判斷除數是否為0，若為0，退出程序
{
s = a/b;
break;
}
else
{
printf(' #### 除數為0，非法運算。程序終止！ #### ');
e_it_e; //打印結束菜單
e_it(-1);
}
case 'a':
s = fabs(b); //調用fabs函數
break;
case 's':
if( b >;= 0) //判斷被開方數是否為0，若為0，退出程序
{
s = sqrt(b); //調用sqrt函數
break;
}
else
{
printf(' #### 求負數的平方根是非法運算。程序終止！ #### ');
e_it_e; //打印結束菜單
e_it(-1);
}
}
return s;
}
char changechar(char &c) //通過changechar函數來把a、s的小寫字母改為大寫的
{
if( c == 'a' )
c = 'a';
else if( c == 's' )
c = 's';
return c;
}
//參考《數據結構》(c語言版)第53頁 3.2.5表達式求值算法3.4 evaluatee_pression_r函數
void evaluatee_pression_r //計算函數：讀入表達式，并計算結果
{
popstack postack; //聲明運算符棧
pdatastack pdstack; //聲明運算數棧
double result; //存運算的結果
char _， theta， c; //c存放讀取的字符，_、theta存放運算符棧的棧頂元素
int flag， data; //標識符，用來讀入連續(xù)的數字
double s;
double getd; //存放gettop___的結果
double a， b， cc; //a，b存放數據棧出棧的棧頂元素， c存放運算結果
flag = 0; //初始化標識符，用來判斷字符串中的連續(xù)數字
data = 0; //
initpopstack(postack); //初始化運算符棧
initpdatastack(pdstack); //初始化運算數棧
pushopstack(postack， '='); //在運算符棧底放入'='
printf(' &請輸入表達式以'='結束：');
c = get); //讀入字符
changechar(c); //通過調用函數來實現把小寫的a、s改為大寫的a、s
while( c ！= '=' || gettoppopstack(postack) ！= '=')
{
if( ！isop(c) ) //不是運算符進棧
{
s = c - '0'; //把字符轉化為數字
if ( flag == 1 )
{
popdatastack(pdstack， getd);
s = getd_10 + s;
}
pushdatastack(pdstack， s);
flag = 1;
c = get);
changechar(c);
}
else
{
flag = 0;
switch( precede(gettoppopstack(postack)， c) ) //輸入元素和運算符棧頂元素比較
{
case '<': //棧頂元素優(yōu)先級低
pushopstack(postack， c);
c = get);
changechar(c);
break;
case '=': //托括號并接受下一個字符
popopstack(postack， _);
c = get);
changechar(c);
break;
case '>;': //退棧并將運算結果進棧
popopstack(postack， theta);
popdatastack(pdstack， b);
popdatastack(pdstack， a);
cc = operate(a， theta， b);
pushdatastack(pdstack， cc);
break;
}//switch
}//else
}//while
result = gettoppdatastack(pdstack); //運算結束時，運算數棧的棧底元素就是計算結果
clearpopstack(postack); //清空運算符棧
clearpdatastack(pdstack); //清空運算數棧
printf(' ->;計算結果為：%.2f '， result); //輸出運算結果
return ;
}
void print_user //歡迎界面
{
printf(' 歡迎使用c語言版模擬計算器 ');
printf('________________________________________________________________________ ');
printf(' |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ');
printf(' | 模擬計算器使用說明 | ');
printf(' | 作者：謝先斌 | ');
printf(' | 本程序包括對'+'、'-'、'_'、'/'、''的運算 | ');
printf(' | 本程序中abs算用a替代、sqrt運算用s代替 | ');
printf(' | 本程序中的一切字母均不區(qū)分大小寫 | ');
printf(' 正確的表達式如：1+a(7-8)+s(9_8)= ');
printf(' | 輸入'='表示表達式輸入結束！ | ');
printf(' | 歡迎使用！-->;-->; | ');
printf(' |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ');
printf('________________________________________________________________________ ');
}
int main //主函數
{
char in;
bool b; //標識符，用來標識是否結束程序
b = true; //初始化，不結束
print_user; //打印歡迎界面
printf(' _請確認使用計算器y/n:');
while(1)
{
scanf('%c'， &in); //確認是否繼續(xù)操作
get); //吃掉會車，避免干擾
switch(in)
{
case 'y':
case 'y':
{
evaluatee_pression_r; //進入計算函數：讀入表達式，并計算結果
break;
}
case 'n':
case 'n':
{
e_it_e;
b = false;
break;
}
//default:
// printf(' __輸入錯誤，請重新輸入y/n:');
// break;
}
if(b==false) //如果 b==false ，退出整個程序
break;
printf(' _您確定要繼續(xù)使用計算機y/n:');
get); //用getchar吃掉回車，避免對后續(xù)輸入中in的干擾
}
return 0;
}
第五篇 c數據結構實驗報告4350字
c數據結構實驗報告
數據結構(c語言版)實驗報告;專業(yè)：計算機科學與技術、軟件工程;學號:____201240703061_____;班級:_________軟件二班________;姓名:________朱海霞__________;指導教師:___劉遵仁_____________;青島大學信息工程學院;2024年10月;實驗1;實驗題目：順序存儲結構線性表的插入和刪除;實驗目
數據結構(c語言版) 實驗報告
專業(yè)：計算機科學與技術、軟件工程
學號:____201240703061___________________
班級:_________軟件二班______________
姓名:________朱海霞______________
指導教師:___劉遵仁________________
青島大學信息工程學院
2024年10月
實驗1
實驗題目：順序存儲結構線性表的插入和刪除
實驗目的：
了解和掌握線性表的邏輯結構和順序存儲結構，掌握線性表的基本算法及相關的時間性能分析。
實驗要求：
建立一個數據域定義為整數類型的線性表，在表中允許有重復的數據;根據輸入的數據，先找到相應的存儲單元，后刪除之。
實驗主要步驟：
1、分析、理解給出的示例程序。
2、調試程序，并設計輸入一組數據(3，-5，6，8，2，-5，4，7，-9)，測試程序的如下功能：根據輸入的數據，找到相應的存儲單元并刪除，顯示表中所有的數據。
程序代碼:
#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個數
listinsert_sq(l，3，24);
for(i=0;i<10;i++)
printf(' %d'，l.elem[i]);
printf(' ');//插入一個數
int e;
listdelete_sq(l，2， e);
for(i=0;i<9;i++)
printf(' %d'，l.elem[i]);//刪除一個數
printf(' ');
return 0;
}
實驗結果：
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é)省存儲空間;但是插入和刪除元素需要移動大量元素，消耗大量時間;需要一個連續(xù)的存儲空間;插入元素可能發(fā)生溢出;自由區(qū)中的存儲空間不能被其他數據共享 實驗2
實驗題目：單鏈表的插入和刪除
實驗目的：
了解和掌握線性表的邏輯結構和鏈式存儲結構，掌握單鏈表的基本算法及相關的時間性能分析。
實驗要求：
建立一個數據域定義為字符類型的單鏈表，在鏈表中不允許有重復的字符;根據輸入的字符，先找到相應的結點，后刪除之。
實驗主要步驟：
3、分析、理解給出的示例程序。
4、調試程序，并設計輸入數據(如：a，c，e，f，h，j，q，m)，測試程序的如下功能：不允許重復字符的插入;根據輸入的字符，找到相應的結點并刪除。
5、修改程序：
(1) 增加插入結點的功能。
(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[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->;ne_t;
while(p！=null){
printf('%c '，p->;data); p=p->;ne_t;
}//插入八個字符printf(' ;實驗結果：;acefhjqu;abcefhjqu;abefhjqu;心得體會：;單鏈表是通過掃描指針p進行單鏈表的操作;頭指針唯;實驗3;實驗題目：棧操作設計和實現;實驗目的：;1、掌握棧的順序存儲結構和鏈式存儲結構，以便在實;2、掌握棧的特點，即后進先出和先進先出的原則;3、掌握棧的'基本運算，如：入棧與出棧
}
}//插入八個字符 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; }//插入一個字符 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;
實驗結果：
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進行單鏈表的操作;頭指針唯一標識點鏈表的存在;插入和刪除元素快捷，方便。
實驗3
實驗題目：棧操作設計和實現
實驗目的：
1、掌握棧的順序存儲結構和鏈式存儲結構，以便在實際中靈活應用。
2、掌握棧的特點，即后進先出和先進先出的原則。
3、掌握棧的基本運算，如：入棧與出棧等運算在順序存儲結構和鏈式存儲結構上的實現。
實驗要求：
回文判斷：對于一個從鍵盤輸入的字符串，判斷其是否為回文。回文即正反序相同。如
“abba”是回文，而“abab”不是回文。
實驗主要步驟
(1)數據從鍵盤讀入;
(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; // 在棧構造之前和銷毀之后，base的值為null int _top; // 棧頂指針
int stacksize; // 當前已分配的存儲空間，以元素為單位
} sqstack;
int initstack(sqstack &s)
{ // 構造一個空棧s
if(！(s.base=(int _)malloc(stack_init_size_sizeof(int))))
e_it(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)
e_it(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('請輸入表達式: ');
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;
}
實驗結果：
請輸入表達式：
abcba
輸出：yes！
心得體會：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進后出的性質，這個固有性質使棧成為程序設計中的有用工具。
實驗4
實驗題目：二叉樹操作設計和實現
實驗目的：
掌握二叉樹的定義、性質及存儲方式，各種遍歷算法。
實驗要求：
采用二叉樹鏈表作為存儲結構，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結點總數的操作。
實驗主要步驟：
1、分析、理解程序。
2、調試程序，設計一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結點(空指針)，如abd###ce##f##，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結點總數。
程序代碼:
實驗結果：
心得體會：
實驗5
實驗題目：圖的遍歷操作
實驗目的：
掌握有向圖和無向圖的概念;掌握鄰接矩陣和鄰接鏈表建立圖的存儲結構;掌握dfs及bfs對圖的遍歷操作;了解圖結構在人工智能、工程等領域的廣泛應用。
實驗要求：
采用鄰接矩陣和鄰接鏈表作為圖的存儲結構，完成有向圖和無向圖的dfs和bfs操作。
實驗主要步驟：
設計一個有向圖和一個無向圖，任選一種存儲結構，完成有向圖和無向圖的dfs(深度優(yōu)先遍歷)和bfs(廣度優(yōu)先遍歷)的操作。
1. 鄰接矩陣作為存儲結構
#include'stdio.h'
#include'stdlib.h'
#define ma_verte_num 100 //定義最大頂點數
typedef struct{
char ve_s[ma_verte_num]; //頂點表
int edges[ma_verte_num][ma_verte_num]; //鄰接矩陣，可看作邊表 int n，e; //圖中的頂點數n和邊數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); //輸入頂點數和邊數
scanf('%c'，&a);
printf('input verte_ string:');
for(i=0;in;i++)
{
scanf('%c'，&a);
g->;ve_s[i]=a; //讀入頂點信息，建立頂點表
}
for(i=0;in;i++)
for(j=0;jn;j++)
g->;edges[i][j]=0; //初始化鄰接矩陣
printf('input edges，creat adjacency matri_ ');
for(k=0;ke;k++) { //讀入e條邊，建立鄰接矩陣
scanf('%d%d'，&i，&j); //輸入邊(vi，vj)的頂點序號
g->;edges[i][j]=1;;g->;edges[j][i]=1;//若為;//=========定義標志向量，為全局變量=;typedefenum{false，true}b;booleanvisited[ma_verte_;//========dfs：深度優(yōu)先遍歷的遞歸算;voiddfsm(mgraph_g，inti);{//以vi為出發(fā)點
g->;edges[i][j]=1;
g->;edges[j][i]=1; //若為無向圖，矩陣為對稱矩陣;若建立有向圖，去掉該條語句 }
}
//=========定義標志向量，為全局變量=======
typedef enum{false，true} boolean;
boolean visited[ma_verte_num];
//========dfs：深度優(yōu)先遍歷的遞歸算法======
void dfsm(mgraph _g，int i)
{ //以vi為出發(fā)點對鄰接矩陣表示的圖g進行dfs搜索，鄰接矩陣是0，1矩陣
給出你的編碼
//===========bfs：廣度優(yōu)先遍歷=======
void bfs(mgraph _g，int k)
{ //以vk為源點對用鄰接矩陣表示的圖g進行廣度優(yōu)先搜索
給出你的編碼
//==========主程序main =====
void main
{
int i;
mgraph _g;
g=(mgraph _)malloc(sizeof(mgraph)); //為圖g申請內存空間
creatmgraph(g); //建立鄰接矩陣
printf('print graph dfs: ');
dfs(g); //深度優(yōu)先遍歷
printf(' ');
printf('print graph bfs: ');
bfs(g，3); //以序號為3的頂點開始廣度優(yōu)先遍歷
printf(' ');
}
2. 鄰接鏈表作為存儲結構
#include'stdio.h'
#include'stdlib.h'
#define ma_verte_num 50 //定義最大頂點數
typedef struct node{ //邊表結點
int adjve_; //鄰接點域
struct node _ne_t; //鏈域
}edgenode;
typedef struct vnode{ //頂點表結點
char verte_; //頂點域
edgenode _firstedge; //邊表頭指針
}verte_node;
typedef verte_node adjlist[ma_verte_num]; //adjlist是鄰接表類型 typedef struct {
adjlist adjlist; //鄰接表
int n，e; //圖中當前頂點數和邊數
} algraph; //圖類型
//=========建立圖的鄰接表=======
void creatalgraph(algraph _g)
{
int i，j，k;
char a;
edgenode _s; //定義邊表結點
printf('input verte_num(n) and edgesnum(e): ');
scanf('%d，%d'，&g->;n，&g->;e); //讀入頂點數和邊數
scanf('%c'，&a);
printf('input verte_ string:');
for(i=0;in;i++) //建立邊表
{
scanf('%c'，&a);
g->;adjlist[i].verte_=a; //讀入頂點信息
g->;adjlist[i].firstedge=null; //邊表置為空表
}
printf('input edges，creat adjacency list ');
for(k=0;ke;k++) { //建立邊表
scanf('%d%d'，&i，&j); //讀入邊(vi，vj)的頂點對序號
s=(edgenode _)malloc(sizeof(edgenode)); //生成邊表結點
s->;adjve_=j; //鄰接點序號為j
s->;ne_t=g->;adjlist[i].firstedge;
g->;adjlist[i].firstedge=s; //將新結點_s插入頂點vi的邊表頭部
s=(edgenode _)malloc(sizeof(edgenode));
s->;adjve_=i; //鄰接點序號為i
s->;ne_t=g->;adjlist[j].firstedge;
g->;adjlist[j].firstedge=s; //將新結點_s插入頂點vj的邊表頭部
}
}
//=========定義標志向量，為全局變量=======
typedef enum{false，true} boolean;
boolean visited[ma_verte_num];
//========dfs：深度優(yōu)先遍歷的遞歸算法======
void dfsm(algraph _g，int i)
{ //以vi為出發(fā)點對鄰接鏈表表示的圖g進行dfs搜索
給出你的編碼
//==========bfs：廣度優(yōu)先遍歷=========
void bfs(algraph _g，int k)
{ //以vk為源點對用鄰接鏈表表示的圖g進行廣度優(yōu)先搜索
給出你的編碼
//==========主函數===========
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(' ');
}
實驗結果：
1. 鄰接矩陣作為存儲結構
2. 鄰接鏈表作為存儲結構
心得體會：
實驗6
實驗題目：二分查找算法的實現
實驗目的：
掌握二分查找法的工作原理及應用過程，利用其工作原理完成實驗題目中的內容。。
實驗要求：
編寫程序構造一個有序表l，從鍵盤接收一個關鍵字key，用二分查找法在l中查找key，若找到則提示查找成功并輸出key所在的位置，否則提示沒有找到信息。。
實驗主要步驟：
1. 建立的初始查找表可以是無序的，如測試的數據為{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。
2. 給出算法的遞歸和非遞歸代碼;
3. 如何利用二分查找算法在一個有序表中插入一個元素_，并保持表的有序性？
程序代碼
實驗結果：
心得體會：
實驗7
實驗題目：排序
實驗目的：
掌握各種排序方法的基本思想、排序過程、算法實現，能進行時間和空間性能的分析，根據實際問題的特點和要求選擇合適的排序方法。
實驗要求：
實現直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運行速度。
實驗主要步驟：
程序代碼
實驗結果：
心得體會：
第六篇 北郵數據結構實驗報告2150字
北郵數據結構實驗報告
北京郵電大學信息與通信工程學院
2009級數據結構實驗報告
實驗名稱： 實驗三哈夫曼編/解碼器的實現
學生姓名：陳聰捷
日 期： 2024年11月28日
1.實驗要求
一、實驗目的：
了解哈夫曼樹的思想和相關概念;
二、實驗內容：
利用二叉樹結構實現哈夫曼編/解碼器
1.初始化：能夠對輸入的任意長度的字符串s進行統(tǒng)計，統(tǒng)計每個字符的頻度，并建立哈夫曼樹。
2.建立編碼表：利用已經建好的哈夫曼樹進行編碼，并將每個字符的編碼輸出。
3.編碼：根據編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸出。
4.譯碼：利用已經建好的哈夫曼樹對編碼后的字符串進行譯碼，并輸出譯碼結果。
5.打印：以直觀的方式打印哈夫曼樹。
6.計算輸入的字符串編碼前和編碼后的長度，并進行分析，討論哈夫曼編碼的壓縮效果。
7.用戶界面可以設計成“菜單”方式，能進行交互，根據輸入的字符串中每個字符出現的次數統(tǒng)計頻度，對沒有出現的字符一律不用編碼。
2. 程序分析
2.1 存儲結構
二叉樹
template
class bitree
{
public:
bitree; //構造函數，其前序序列由鍵盤輸入
~bitree(void); //析構函數
binode_ getroot; //獲得指向根結點的指針
protected:
binode _root; //指向根結點的頭指針
};
//聲明類bitree及定義結構binode
data：
二叉樹是由一個根結點和兩棵互不相交的左右子樹構成
哈夫曼樹類的數據域，繼承節(jié)點類型為int的二叉樹 class huffmantree:public bitree
data:
hcode_ hcodetable;//編碼表
int tsize; //編碼表中的總字符數
二叉樹的節(jié)點結構
template
struct binode //二叉樹的結點結構 {
t data; //記錄數據
t lchild; //左孩子
t rchild; //右孩子
t parent; //雙親
};
編碼表的節(jié)點結構
struct hcode
{
char data; //編碼表中的字符
char code[100]; //該字符對應的編碼
};
待編碼字符串由鍵盤輸入，輸入時用鏈表存儲，鏈表節(jié)點為 struct node
{
char character; //輸入的字符
unsigned int count;//該字符的權值
bool used; //建立樹的時候該字符是否使用過
node_ ne_t; //保存下一個節(jié)點的地址
};
示意圖：
2.2 關鍵算法分析
1.初始化函數(void huffmantree::init(string input))
算法偽代碼：
1.初始化鏈表的頭結點
2.獲得輸入字符串的第一個字符，并將其插入到鏈表尾部，n=1(n記錄的是鏈表
中字符的個數)
3.從字符串第2個字符開始，逐個取出字符串中的字符
3.1 將當前取出的字符與鏈表中已經存在的字符逐個比較，如果當前取出
的字符與鏈表中已經存在的某個字符相同，則鏈表中該字符的權值加1。
3.2 如果當前取出的字符與鏈表中已經存在的字符都不相同，則將其加入
到鏈表尾部，同時n++
4.tsize=n(tsize記錄鏈表中字符總數，即哈夫曼樹中葉子節(jié)點總數)
5.創(chuàng)建哈夫曼樹
6.銷毀鏈表
源代碼：
void huffmantree::init(string input)
{
node _front=new node; //初始化鏈表的頭結點
if(！front)
throw e_ception('堆空間用盡');
front->;ne_t=null;
front->;character=null;
front->;count=0;
node _pfront=front;
char ch=input[0]; //獲得第一個字符
node_ new1=new node;
if(！new1)
throw e_ception('堆空間用盡');
new1->;character=ch; //將第一個字符插入鏈表
new1->;count=1;
new1->;ne_t=pfront->;ne_t;
pfront->;ne_t=new1;
bool replace=0; //判斷在已經寫入鏈表的字符中是否有與當前讀出的字符相同的字符 int n=1; //統(tǒng)計鏈表中字符個數
for(int i=1;i
{
ch=input[i]; //獲得第i個字符
do
{
pfront=pfront->;ne_t;
if((int)pfront->;character == (int)ch) //如果在鏈表中有與當前字符相同的字符，
該字符權值加1
{
pfront->;count++;
replace=1;
break;
}
}while(pfront->;ne_t);
if(！replace) //如果在鏈表中沒找到與當前字符相同的字符，則將該字符作為新成 員插入鏈表
{
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變量為默認值 replace=0;
}
tsize=n; //tsize記錄的是編碼表中字符個數
createhtree(front，n); //創(chuàng)建哈夫曼樹
pfront=front;
while(pfront) //銷毀整個鏈表
{
front=pfront;
pfront=pfront->;ne_t;
front;
}
時間復雜度：
若輸入的字符串長度為n，則時間復雜度為o(n)
2.創(chuàng)建哈夫曼樹(void huffmantree::createcodetable(node _p))
算法偽代碼：
1. 創(chuàng)建一個長度為2_tsize-1的三叉鏈表
2. 將存儲字符及其權值的鏈表中的字符逐個寫入三叉鏈表的前tsize個結點
的data域，并將對應結點的孩子域和雙親域賦為空
3. 從三叉鏈表的第tsize個結點開始，i=tsize
3.1 從存儲字符及其權值的鏈表中取出兩個權值最小的結點_，y，記錄其
下標_，y。
3.2 將下標為_和y的哈夫曼樹的結點的雙親設置為第i個結點
3.3 將下標為_的結點設置為i結點的左孩子，將下標為y的結點設置為
i結點的右孩子，i結點的權值為_結點的權值加上y結點的權值，i
結點的雙親設置為空
4. 根據哈夫曼樹創(chuàng)建編碼表
源代碼：
void huffmantree::createhtree(node _p，int n)
{
root= new binode[2_n-1]; //初始化哈夫曼樹
node _front=p->;ne_t;
if(n==0)
throw e_ception('沒有輸入字符');
for(int i=0;i
root[i].data=front->;count;
root[i].lchild=-1;
root[i].rchild=-1;
root[i].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中選出兩個權值最小的結點
root[new1].parent=root[new2].parent=i; //用兩個權值最小的結點生成新結點，
新節(jié)點為其雙親
root[i].data=root[new1].data+root[new2].data;//新結點的權值為其孩子的權值的和 root[i].lchild=new1;
root[i].rchild=new2;
root[i].parent=-1;
}
createcodetable(p); //創(chuàng)建編碼表
}
時間復雜度：
在選取兩個權值最小的結點的函數中要遍歷鏈表，時間復雜度為o(n)，故該函數
的時間復雜度為o(n^2)
3.創(chuàng)建編碼表(void huffmantree::createcodetable(node _p))
算法偽代碼：
1.初始化編碼表
2.初始化一個指針，從鏈表的頭結點開始，遍歷整個鏈表
2.1 將鏈表中指針當前所指的結點包含的字符寫入編碼表中
2.2 得到該結點對應的哈夫曼樹的葉子結點及其雙親
2.3 如果哈夫曼樹只有一個葉子結點，將其字符對應編碼設置為0
2.4 如果不止一個葉子結點，從當前葉子結點開始判斷
2.4.1 如果當前葉子結點是其雙親的左孩子，則其對應的編碼為0，否
則為1
2.4.2 child指針指向葉子結點的雙親，parent指針指向child指針的雙親，
重復2.4.1的操作
2.5 將已完成的編碼倒序
2.6 取得鏈表中的下一個字符
3.輸出編碼表
源代碼：
void huffmantree::createcodetable(node _p)
{
hcodetable=new hcode[tsize]; //初始化編碼表
node _front=p->;ne_t;
for(int i=0;i
{
hcodetable[i].data=front->;character; //將第i個字符寫入編碼表
int child=i; //得到第i個字符對應的葉子節(jié)點
int parent=root[i].parent; //得到第i個字符對應的葉子節(jié)點的雙親
int k=0;
if(tsize==1) //如果文本中只有一種字符，它的.編碼為0
{
hcodetable[i].code[k]='0';
k++;
}
while(parent！=-1) //從第i個字符對應的葉子節(jié)點開始，尋找它到根結點的路徑
{
if(child==root[parent].lchild) //如果當前結點為雙親的左孩子，則編碼為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->;ne_t; //得到下一個字符
}
cout<<'編碼表為：'<
for(i=0;i
{
cout<
parent=root[parent].lchild;
else //編碼為1則尋找右孩子
parent=root[parent].rchild;
i++;
}
if(tsize==1) //如果編碼表只有一個字符，則根結點即為葉子結點 i++;
d.append(1，hcodetable[parent].data);//將葉子節(jié)點對應的字符追加到解碼串中 }
cout<
}
時間復雜度：
設待解碼串長度為n，則復雜度為o(n)
8. 計算哈夫曼編碼的壓縮比(void huffmantree::calculate(string s1，string s2)) 算法偽代碼：
1. 獲得編碼前字符串的長度，即其占用的字節(jié)數
2. 獲得編碼后的字符串的長度，將其除以8然后向上取整，得到其占用的字
節(jié)數
3. 壓縮比將兩個相除
源代碼：
void huffmantree::calculate(string s1，string s2)
{
int cal1=s1.length;
int cal2=s2.length;
cal2=ceill((float)cal2/8); //將編碼串的比特數轉化為字節(jié)數 cout<<'編碼前的字符串長度：'<
cout<<'編碼后的字符串長度：'<
cout<<'壓縮比為：'<<((double)cal2/(double)cal1)_100<<'%'<
}
時間復雜度：
o(1)
9. 打印哈夫曼樹(void huffmantree::printtree(int treenode，int layer) ) 算法偽代碼：
1. 如果待打印結點為空，則返回
2. 遞歸調用函數打印當前結點的右子樹
3. 根據當前結點所在的層次確定其前面要輸出多少空格，先輸出空格，在打
印當前結點的權值
4. 遞歸調用函數打印當前結點的左子樹
源代碼：
void huffmantree::printtree(int treenode，int layer)
{
if(treenode==-1) //如果待打印結點為空，則返回 return;
else
{
printtree(root[treenode].rchild，layer+1); //先打印該結點的右子樹，layer記錄
的是該結點所在的層次
for(int i=0;i
空格
cout<<' ';
cout<
printtree(root[treenode].lchild，layer+1); //打印該結點的左子樹
}
}
時間復雜度：
中序遍歷哈夫曼樹，復雜度為o(n)
10. 菜單函數(void huffmantree::menu)
算法偽代碼：
1. 逐一讀取鍵盤緩存區(qū)中的字符，并將它們逐一追加到記錄輸入字符串的
string變量中，直到讀到回車輸入符為止
2. 刪除string變量末尾的回車輸入符
3.利用string變量創(chuàng)建哈夫曼樹，初始化編碼表。
4. 直觀打印哈夫曼樹
5. 對輸入的字符串進行編碼
6. 對編碼后的字符串進行解碼
7. 計算編碼前后的壓縮比并輸出
源代碼：
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); //根據輸入的字符串創(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); //計算編碼前后的壓縮比
}
2.3 其他
1.由于題目要求能輸入任意長的字符串，所以本程序采用了string變量來記錄輸入
的字符串，并采用string類的類成員函數來完成各項任務
2.打印哈夫曼樹時采用了遞歸函數，且采用了凹凸表的形式打印哈夫曼樹。
3.為了輸入空格，輸入時采取逐個字符輸入的方式
3. 程序運行結果
主函數流程圖：
運行結果：
各函數運行正常，沒有出現bug
4. 總結
經過這次實驗，我了解了哈夫曼樹的創(chuàng)建過程，了解了一種不等長編碼的方法，用設斷點調試的方法更加熟練，同時熟悉了stl中string類型的用法，對c++更加熟悉
