数据结构实验报告

1、数据结构实验报告想必学计算机专业的学生都知道数据结构是一门比较重要的课程，那么，下面是小编给大家收拾收集的数据结构试验报告，供大家阅读参考。数据结构试验报告1一、试验目的及要求1)把握栈和队列这两种特别的线性表，认识它们的特性，在实际问题背景下灵便运用它们。本试验训练的要点是栈和队列的观点;二、试验内容1) 利用栈，实现数制转换。2) 利用栈，实现任一个表达式中的语法检查(选做)。3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);三、试验流程、操作步骤或核心代码、算法片段挨次栈：status initstack(sqstack &s)s.base=

2、(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

3、 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

4、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

5、=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

6、);flag=ok;printf("请输入要进栈或出栈的元素：");while(x= getchar)!=&39;&39;&&flag)switch (x)case &39;(&39;:case &39;&39;:case &39;&39;:if(push(s,x)=ok)printf("括号匹配胜利!nn");break;case &39;)&39;:if(pop(s,e)=error | e!=&39;(&39;)printf("没有满足条件n");flag=false;break;case &39;&39;:if

7、 ( pop(s,e)=error | e!=&39;&39;)flag=false;break;case &39;&39;:if ( pop(s,e)=error | e!=&39;&39;)flag=false;break;if (flag && x=&39;&39; && stackempty(s)return ok;elsereturn error;链队列：status initqueue(linkqueue &q)q.front =q.rear=(queueptr)malloc(sizeof(qnode);if (!q.front) retur

8、n 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

9、;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

10、=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 =

11、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;pri

12、ntf("%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.baseq.

13、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.baseq.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 o

14、k;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.baseq.front);q.front+;return ok;数据结构试验报告2一.试验内容：实现哈夫曼编码的生成算法。二.试验目的：1、使同学娴熟把握哈夫曼树的生成算

15、法。2、娴熟把握哈夫曼编码的办法。三.问题描述：已知n个字符在原文中浮现的频率，求它们的哈夫曼编码。1、读入n个字符，以及字符的权值，试建立一棵huffman树。2、按照生成的huffman树，求每个字符的huffman编码。并对给定的待编码字符序列举行编码，并输出。四.问题的实现(1)郝夫曼树的存储表示typedef structunsigned int weight;unsigned int parent,lchild,rchild;htnode,*huffmantree; /动态分配数组存储郝夫曼树郝夫曼编码的存储表示typedef char* *huffmancode;/动态分配数组存

16、储郝夫曼编码(2)主要的实现思路：a.首先定义郝夫曼树的存储形式，这里用法了数组b.用select遍历n个字符，找出权值最小的两个c.构造郝夫曼树ht，并求出n个字符的郝夫曼编码hc总结1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回huffmancoding，所以把那2个序号设置成了引用。2.在编程过程中，在什么时候分配内存，什么时候初始化花的时光比较长3.最后基本上实现后，发觉结果仍然存在问题，经过分步调试，发觉了特殊低级的输入错误。把hti.weight=hts1.weight+hts2.weight;中的s2写成了i附：/动态分配数组存储郝夫

17、曼树typedef structint 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 && hti.parent!=0)i+;/下面选出权值最小的结点，用s1指向其序号s1=i;for(i=1;i<=

18、k;i+)if(hti.parent=0&&hti.weight/下面选出权值次小的结点，用s2指向其序号for(i=1;i<=k;i+)if(hti.parent=0&&i!=s1)break;s2=i;for(i=1;i<=k;i+)if(hti.parent=0&&i!=s1&&hti.weight/构造huffman树，求出n个字符的编码void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n)int m,c,f,s1,s2,

19、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); /选出当前权值最小的hts1.parent=i;hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;/从叶子到根逆向求每个字符的郝夫曼编码hc=(huffmancode)malloc(n+1)*sizeof(char*); /分配n个字符编码的头指针变量cd=(ch