数据结构实验报告

本文格式为Word版下载后可任意编辑和复制第第页数据结构实验报告想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是我给大家整理收集的数据结构试验报告，供大家阅读参考。

数据结构试验报告1一、试验目的及要求

1)把握栈和队列这两种特别的线性表，熟识它们的特性，在实际问题背景下敏捷运用它们。

本试验训练的要点是“栈”和“队列”的观点;

二、试验内容

1)利用栈，实现数制转换。

2)利用栈，实现任一个表达式中的语法检查(选做)。

3)编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);

三、试验流程、操作步骤或核心代码、算法片段

挨次栈：

StatusInitStack(SqStack&S)

{

S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!S.base)

returnERROR;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}

StatusDestoryStack(SqStack&S)

{

free(S.base);

returnOK;

}

StatusClearStack(SqStack&S)

{

S.top=S.base;

returnOK;

}

StatusStackEmpty(SqStackS)

{

if(S.base==S.top)

returnOK;

returnERROR;

}

intStackLength(SqStackS)

{

returnS.top-S.base;

}

StatusGetTop(SqStackS,ElemType&e)

{

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

{

S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base)returnERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;

}

StatusPush(SqStack&S,ElemTypee)

{

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

{

S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base)

returnERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;

}

StatusPop(SqStack&S,ElemType&e)

{

if(S.top==S.base)

returnERROR;

e=*--S.top;

returnOK;

}

StatusStackTraverse(SqStackS)

{

ElemType*p;

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

if(!p)returnERROR;

p=S.top;

while(p!=S.base)//S.top上面一个...

{

p--;

printf("%d",*p);

}

returnOK;

}

StatusCompare(SqStack&S)

{

intflag,TURE=OK,FALSE=ERROR;

ElemTypee,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))

returnOK;

else

returnERROR;

}

链队列：

StatusInitQueue(LinkQueue&Q)

{

Q.front=Q.rear=

(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)returnERROR;

Q.front->next=NULL;

returnOK;

}

StatusDestoryQueue(LinkQueue&Q)

{

while(Q.front)

{

Q.rear=Q.front->next;

free(Q.front);

Q.front=Q.rear;

}

returnOK;

}

StatusQueueEmpty(LinkQueue&Q)

{

if(Q.front->next==NULL)

returnOK;

returnERROR;

}

StatusQueueLength(LinkQueueQ)

{

inti=0;

QueuePtrp,q;

p=Q.front;

while(p->next)

{

i++;

p=Q.front;

q=p->next;

p=q;

}

returni;

}

StatusGetHead(LinkQueueQ,ElemType&e)

{

QueuePtrp;

p=Q.front->next;

if(!p)

returnERROR;

e=p->data;

returne;

}

StatusClearQueue(LinkQueue&Q)

{

QueuePtrp;

while(Q.front->next)

{

p=Q.front->next;

free(Q.front);

Q.front=p;

}

Q.front->next=NULL;

Q.rear->next=NULL;

returnOK;

}

StatusEnQueue(LinkQueue&Q,ElemTypee)

{

QueuePtrp;

p=(QueuePtr)malloc(sizeof(QNode));

if(!p)

returnERROR;

p->data=e;

p->next=NULL;

Q.rear->next=p;

Q.rear=p;//p->next为空

returnOK;

}

StatusDeQueue(LinkQueue&Q,ElemType&e)

{

QueuePtrp;

if(Q.front==Q.rear)

returnERROR;

p=Q.front->next;

e=p->data;

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

if(Q.rear==p)

Q.rear=Q.front;//只有一个元素时(不存在指向尾指针)

free(p);

returnOK;

}

StatusQueueTraverse(LinkQueueQ)

{

QueuePtrp,q;

if(QueueEmpty(Q)==OK)

{

printf("这是一个空队列!\n");

returnERROR;

}

p=Q.front->next;

while(p)

{

q=p;

printf("%ddata);

q=p->next;

p=q;

}

returnOK;

}

循环队列：

StatusInitQueue(SqQueue&Q)

{

Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));

if(!Q.base)

exit(OWERFLOW);

Q.front=Q.rear=0;

returnOK;

}

StatusEnQueue(SqQueue&Q,QElemTypee)

{

if((Q.rear+1)%MAXQSIZE==Q.front)

returnERROR;

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;

returnOK;

}

StatusDeQueue(SqQueue&Q,QElemType&e)

{

if(Q.front==Q.rear)

returnERROR;

e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

returnOK;

}

intQueueLength(SqQueueQ)

{

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;

}

StatusDestoryQueue(SqQueue&Q)

{

free(Q.base);

returnOK;

}

StatusQueueEmpty(SqQueueQ)//判空

{

if(Q.front==Q.rear)

returnOK;

returnERROR;

}

StatusQueueTraverse(SqQueueQ)

{

if(Q.front==Q.rear)

printf("这是一个空队列!");

while(Q.front%MAXQSIZE!=Q.rear)

{

printf("%dQ.front++;

}

returnOK;

}

数据结构试验报告2一.试验内容：

实现哈夫曼编码的生成算法。

二.试验目的：

1、使同学娴熟把握哈夫曼树的生成算法。

2、娴熟把握哈夫曼编码的方法。

三.问题描述：

已知n个字符在原文中消失的频率，求它们的哈夫曼编码。

1、读入n个字符，以及字符的权值，试建立一棵Huffman树。

2、依据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。

四.问题的实现

(1)郝夫曼树的存储表示

typedefstruct{

unsignedintweight;

unsignedintparent,lchild,rchild;

}HTNode,*HuffmanTree;//动态安排数组存储郝夫曼树

郝夫曼编码的存储表示

typedefchar**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

附：

//动态安排数组存储郝夫曼树

typedefstruct{

intweight;//字符的权值

intparent,lchild,rchild;

}HTNode,*HuffmanTree;

//动态安排数组存储郝夫曼编码

typedefchar**HuffmanCode;

//选择n个(这里是k=n)节点中权值最小的两个结点

voidSelect(HuffmanTree&HT,intk,int&s1,int&s2)

{inti;

i=1;

while(i//下面选出权值最小的结点，用s1指向其序号

s1=i;

for(i=1;i{

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

}

//下面选出权值次小的结点，用s2指向其序号

for(i=1;i{

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

}

s2=i;

for(i=1;i{

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

}

}

//构造Huffman树，求出n个字符的编码

voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)

{

intm,c,f,s1,s2,i,start;

char*cd;

if(nm=2*n-1;//n个叶子n-1个结点

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用，预安排m+1个单元

HuffmanTreep=HT+1;

w++;//w的号单元也没有值，所以从号单元开头

for(i=1;i{

p->weight=*w;

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

}

for(;i{

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

}

for(i=n+1;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].weig