数据结构实验报告.docx

数据结构实验报告数据结构实验报告1一、实验目的及要求1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。本实验训练的要点是“栈”和“队列”的观点;二、实验内容1) 利用栈，实现数制转换。2) 利用栈，实现任一个表达式中的语法检查(选做)。3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);三、实验流程、操作步骤或核心代码、算法片段顺序栈=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,*;InitStack(S);flag=OK;printf(请输入要进栈或出栈的元素：);while(*= getchar)!=#flag)switch (*)case (:case :case :if(Push(S,*)=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 | e!=)flag=FALSE;break;if (flag*=#StackEmpty(S)return OK;elsereturn ERROR;链队列ne*t 为空ne*t;if (Q.rear = p)Q.rear = Q.front; /只有一个元素时(不存在指向尾指针)free (p);return OK;Status QueueTraverse(LinkQueue Q)QueuePtr p,q;if( QueueEmpty(Q)=OK)printf(这是一个空队列ne*t;while(p)q=p;printf(%dne*t;p=q;return OK;循环队列：Status InitQueue(SqQueue Q)Q.base=(QElemType*)malloc(MA*QSIZE*sizeof(QElemType);if(!Q.base)e*it(OWERFLOW);Q.front=Q.rear=0;return OK;Status EnQueue(SqQueue Q,QElemType e)if(Q.rear+1)%MA*QSIZE=Q.front)return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MA*QSIZE;return OK;Status DeQueue(SqQueue Q,QElemType e)if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MA*QSIZE;return OK;int QueueLength(SqQueue Q)return(Q.rear-Q.front+MA*QSIZE)%MA*QSIZE;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%MA*QSIZE!=Q.rear)printf(%d数据结构实验报告2一.实验内容：实现哈夫曼编码的生成算法。二.实验目的：1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。三.问题描述：已知n个字符在原文中出现的频率，求它们的哈夫曼编码。1、读入n个字符，以及字符的权值，试建立一棵Huffman树。2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。四.问题的实现(1)郝夫曼树的存储表示typedef structunsigned 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.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把HTi.weight=HTs1.weight+HTs2.weight;中的s2写成了i附：/动态分配数组存储郝夫曼树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下面选出权值最小的结点，用s1指向其序号s1=i;for(i=1;i下面选出权值次小的结点，用s2指向其序号for(i=1;i构造Huffman树，求出n个字符的编码void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)int m,c,f,s1,s2,i,start;char *cd;if(n个叶子n-1个结点HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0号单元未用，预分配m+1个单元HuffmanTree p=HT+1;w+; /w的号单元也没有值，所以从号单元开始for(i=1;ilchild=0;for(i=n+1;i选出当前权值最小的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逐个字符求郝夫曼编码start=n-1; /编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /从叶子到根逆向求编码if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间strcpy(HCi,cdstart);/从cd复制编码到HCfree(cd); /释放工作空间void main int n,i;int* w; /记录权值char* ch; /记录字符HuffmanTree HT;HuffmanCode HC;cout请输入待编码的字符个数n;w=(int*)malloc(n+1)*sizeof(int); /记录权值，号单元未用ch=(char*)malloc(n+1)*sizeof(char);/记录字符，号单元未用cout依次输入待编码的字符data及其权值weight