想必學計算機專業的同學都知道數據結構是一門比較重要的課程，那么，下面是小編給大家整理收集的數據結構實驗報告，供大家閱讀參考。
數據結構實驗報告1
一、實驗目的及要求
1)掌握棧和佇列這兩種特殊的線性表，熟悉它們的特性，在實際問題背景下靈活運用它們。
本實驗訓練的要點是“棧”和“佇列”的觀點;
二、實驗內容
1) 利用棧，實現數制轉換。
2) 利用棧，實現任一個表達式中的語法檢查(選做)。
3) 編程實現佇列在兩種存儲結構中的基本操作(佇列的初始化、判佇列空、入佇列、出佇列);
三、實驗流程、操作步驟或核心代碼、算法片段
順序棧：
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("請輸入要進棧或出棧的元素：");
while((x= getchar)!='#'&&flag)
{
switch (x)
{
case '(':
case '[':
case '{':
if(Push(S,x)==OK)
printf("括弧匹配成功!\n\n");
break;
case ')':
if(Pop(S,e)==ERROR || e!='(')
{
printf("沒有滿足條件\n");
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;
}
鏈佇列：
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("這是一個空佇列!\n");
return ERROR;
}
p=Q.front->next;
while(p)
{
q=p;
printf("%d<-\n",q->data);
q=p->next;
p=q;
}
return OK;
}
循環佇列：
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("這是一個空佇列!");
while(Q.front%MAXQSIZE!=Q.rear)
{
printf("%d<- ",Q.base[Q.front]);
Q.front++;
}
return OK;
}
數據結構實驗報告2
一.實驗內容：
實現哈夫曼編碼的生成算法。
二.實驗目的：
1、使學生熟練掌握哈夫曼樹的生成算法。
2、熟練掌握哈夫曼編碼的方法。
三.問題描述：
已知n個字元在原文中出現的頻率，求它們的哈夫曼編碼。
1、讀入n個字元，以及字元的權值，試建立一棵Huffman樹。
2、根據生成的Huffman樹，求每個字元的Huffman編碼。並對給定的待編碼字元序列進行編碼，並輸出。
四.問題的實現
(1)郝夫曼樹的存儲表示
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //動態分配數組存儲郝夫曼樹
郝夫曼編碼的存儲表示
typedef char* *HuffmanCode;//動態分配數組存儲郝夫曼編碼
(2)主要的實現思路：
a.首先定義郝夫曼樹的存儲形式，這裡使用了數組
b.用select遍歷n個字元，找出權值最小的兩個
c.構造郝夫曼樹HT，並求出n個字元的郝夫曼編碼HC
總結
1.基本上沒有什麼太大的問題，在調用select這個函式時，想把權值最小的兩個結點的序號帶回HuffmanCoding，所以把那2個序號設定成了引用。
2.在編程過程中，在什麼時候分配記憶體，什麼時候初始化花的時間比較長
3.最後基本上實現後，發現結果仍然存在問題，經過分步調試，發現了特別低級的輸入錯誤。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2寫成了i
附：
//動態分配數組存儲郝夫曼樹
typedef struct{
int weight; //字元的權值
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
//動態分配數組存儲郝夫曼編碼
typedef char* *HuffmanCode;
//選擇n個(這裡是k=n)節點中權值最小的兩個結點
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]='\0';//編碼結束符
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["<
}