数据结构实验报告_数据结构实验报告

【fanwen.jxxyjl.com--实验报告】

　　想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是小编给大家整理收集的数据结构实验报告，供大家阅读参考。

　　一、实验目的及要求

　　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;

　　}

　　一.实验内容：

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

　　二.实验目的：

　　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["<

　　}

本文来源：https://fanwen.jxxyjl.com/shiyanbaogao/61663.html