数据结构实验报告

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

数据结构实验报告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("括号匹配成功!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 && 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]='';//编码结束符

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

  }

原创文章,作者:fanwen,如若转载,请注明出处:https://fanwen.hongwu.com/18623.html

(0)
上一篇 2022年8月1日 下午5:09
下一篇 2022年8月1日 下午5:13

相关推荐

  • 打电话的实验报告

      一、实验名称:杯子话筒   二、实验目的:打电话   三、实验器材:大回形针、绳子、杯子   四、实验原理:声音可以通过棉线来传播,但是线一定要拉直。   五、实验过程步骤: …

    实验报告 2022年9月11日
  • 弱酸电离度与电离常数的测定实验报告范文

      篇一:无机化学实验六 醋酸电离度和电离常数的测定   一、实验目的   1.测定醋酸的电离度和电离常数;   2.学习pH计的使用。 [教学重点]   醋酸的电离度、电离常数的…

    实验报告 2022年8月16日
  • 大连理工大学电工实验报告

      一、 选课要求   实验选课前需确认在教务选课系统中选择该课程。电工学实验实行网上选课,=   二、 预习要求   课前认真阅读实验教程,复习相关理论知识,学习本节实验预备知识…

    实验报告 2022年7月27日
  • 电机实验报告模板

      课程名称: 电机拖动基础 班 级: 电气11-2   指导老师:   实验一 单相变压器实验   实验名称:单相变压器实验   实验目的:1.通过空载和短路实验测定变压器的变比…

    实验报告 2022年11月21日
  • 大学物理实验报告

      物理学习想必少不了实验证明吧,那么,下面是第一范文网小编给大家整理收集的大学物理实验报告,供大家阅读参考。 大学物理实验报告1   实验目的:通过演示来了解弧光放电的原理   …

    实验报告 2022年10月9日
  • 电焊焊接实验报告

      篇一:电焊实验报告   实习目的:   1、简单了解焊工的工作原理及其工作方式;   2、学会正确的焊接,并能正确使用一种焊接工件方式。   原理:   1、简介:焊接,就是用…

    实验报告 2022年11月8日
  • 机械实验报告

      班级_____姓名_____学号_____   一、 实验内容:   1、传动系统的功能  能量分配  转速的改变 运动形式的改变   2、传动系统的基本构…

    实验报告 2022年7月11日
  • 思修的实验报告

      实践名称:   我与国魂有个约定。   实践内容摘要:   时光荏苒,辛亥革命距今已是百年,为了更好的回顾这百年辛亥,特参加由甘肃省博物馆主办的辛亥革命专题展览会。   实践的…

    实验报告 2022年12月19日
  • 会计软件应用实验报告模板

      篇一:会计软件运用实验报告   会计软件运用实验报告 一、实验目的: 通过用友ERP-U8软件掌握如何正确建立账套,设置用户的权限以及账套数据的输入,系统地学习总账日常业务处理…

    实验报告 2022年12月15日
  • 高中化学固态究竟的制取和碘水中碘的萃取实验报告

      篇一:高中化学实验报告   xx中学化学实验报告   高x届x班   固体酒精的制取   指导教师: 实验小组成员: 实验日期:–   一、实验题目:固态酒精的制取…

    实验报告 2022年7月10日

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注