数据结构实验报告_1.docx

《数据结构实验报告_1.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告_1.docx（20页珍藏版）》请在三一文库上搜索。

1、数据结构实验报告 数据结构实验报告 想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是自查报告网我给大家整理收集的数据结构实验报告，供大家阅读参考。 一、实验目的及要求 1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。 本实验训练的要点是“栈”和“队列”的观点; 二、实验内容 1) 利用栈，实现数制转换。 2) 利用栈，实现任一个表达式中的语法检查(选做)。 3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列); 三、实验流程、操作步骤或核心代码、算法片段 顺序栈： Status InitStack(SqS

2、tack 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.to

3、p) 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+=STACKINCREMEN

4、T; *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,ElemTyp

5、e 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;

6、 InitStack(S); flag=OK; printf(请输入要进栈或出栈的元素：); while(x= getchar)!=#flag) switch (x) case (: case : case : if(Push(S,x)=OK) printf(括号匹配成功!nn); 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 |

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

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

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

10、OR; 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 Que

11、ueTraverse(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(Sueue Q) Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType); if(!Q.base) exit(OWERFLOW); Q.front=Q.rear=0

12、; return OK; Status EnQueue(Sueue Q,QElemType e) if(Q.rear+1)%MAXQSIZE=Q.front) return ERROR; Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; Status DeQueue(Sueue Q,QElemType e) if(Q.front=Q.rear) return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK; int QueueLength(Sueue Q)

13、 return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; Status DestoryQueue(Sueue Q) free(Q.base); return OK; Status QueueEmpty(Sueue Q) /判空 if(Q.front =Q.rear) return OK; return ERROR; Status QueueTraverse(Sueue Q) if(Q.front=Q.rear) printf(这是一个空队列!); while(Q.front%MAXQSIZE!=Q.rear) printf(%d- ,Q.baseQ.front);

14、Q.front+; return OK; 一.实验内容： 实现哈夫曼编码的生成算法。 二.实验目的： 1、使学生熟练掌握哈夫曼树的生成算法。 2、熟练掌握哈夫曼编码的方法。 三.问题描述： 已知n个字符在原文中出现的频率，求它们的哈夫曼编码。 1、读入n个字符，以及字符的权值，试建立一棵Huffman树。 2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。 四.问题的实现 (1)郝夫曼树的存储表示 typedef struct unsigned int weight; unsigned int parent,lchild,rchild;

15、HTNode,*HuffmanTree; /动态分配数组存储郝夫曼树 郝夫曼编码的存储表示 typedef char* *HuffmanCode;/动态分配数组存储郝夫曼编码 (2)主要的实现思路： a.首先定义郝夫曼树的存储形式，这里使用了数组 b.用select遍历n个字符，找出权值最小的两个 c.构造郝夫曼树HT，并求出n个字符的郝夫曼编码HC 总结 1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding，所以把那2个序号设置成了引用。 2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长 3.最后基本上实现后

16、，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把HTi.weight=HTs1.weight+HTs2.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

17、=1; while(i=k HTi.parent!=0)i+; /下面选出权值最小的结点，用s1指向其序号 s1=i; for(i=1;i=k;i+) if(HTi.parent=0HTi.weight /下面选出权值次小的结点，用s2指向其序号 for(i=1;i=k;i+) if(HTi.parent=0i!=s1)break; s2=i; for(i=1;i=k;i+) if(HTi.parent=0i!=s1HTi.weight /构造Huffman树，求出n个字符的编码 void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,i

18、nt 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=

19、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=(char*)malloc(n*sizeof(char); /分配求编码的工作空间 cdn-1=0;/编码结束符 for(i=1;i=n

20、;i+) /逐个字符求郝夫曼编码 start=n-1; /编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /从叶子到根逆向求编码 if(HTf.lchild=c)cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间 strcpy(HCi,cdstart);/从cd复制编码到HC free(cd); /释放工作空间 void main int n,i; int* w; /记录权值 char* ch; /记录字符 HuffmanTree HT; HuffmanCode HC; cout请输入待编码的字符个数n=; cinn; w=(int*)malloc(n+1)*sizeof(int); /记录权值，号单元未用 ch=(char*)malloc(n+1)*sizeof(char);/记录字符，号单元未用 cout依次输入待编码的字符data及其权值weight for(i=1;i=n;i+) coutdata