| 标题 | 数据结构实验报告 |
| 范文 | 数据结构实验报告 想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是第一范文网小编给大家整理收集的数据结构实验报告，供大家阅读参考。 数据结构实验报告1一、实验目的及要求 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; } 数据结构实验报告2一.实验内容： 实现哈夫曼编码的生成算法。 二.实验目的： 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["< } |
| 随便看 |
|
范文大全网提供教案、简历、作文、工作总结等各类优秀范文及写作素材，是综合性免费范文平台。