数据结构实验报告

      时间:2021-04-07 15:08?????? 来源: 未知
      数据结构实验报告

      数据结构实验报告

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

      数据结构实验报告

        一数据结构实验报告、实验目的及要求

        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("括号匹配成功! ");

        break;

        case ')':

        if(Pop(S,e)==ERROR || e!='(')

        {

        printf("没有满足条件 ");

        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("这是一个空队列! ");

        return ERROR;

        }

        p=Q.front->next;

        while(p)

        {

        q=p;

        printf("%d<- ",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;

        }

        一.实验内容:

        实现哈夫曼编码的生成算法。

        二.实验目的:

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

        }

      【数据结构实验报告】相关文章:

      1.实验报告芯片解剖实验报告

      2.解剖实验报告

      3.大物实验报告

      4.实验报告格式

      5.实验报告大全

      6.实验报告

      7.精馏实验报告

      8.机能实验报告

      数据结构实验报告

      文章来源: http://www.xzhuajun.com

      原文地址:http://www.xzhuajun.com/hyby/5613.html

      ? 上一篇:描写蒲葵树的作文
      ? 下一篇:男士珠宝魅力的散文阅读

      相关推荐

      
      

          狼群在线资源www,狼群在线看片中文字幕HD版,狼群视频在线资源高清免费,狼群视频在线观看日本 百度 好搜 搜狗

          警告:本站明確包含成人内容,未滿18嵗游客禁止觀看!收藏本站:請使用Ctrl+D進行收藏