精华内容
下载资源
问答
  • 哈工大数据结构
    千次阅读 多人点赞
    2020-12-07 09:59:01

    // 12.15 更新,昨天数据结构出分、自认为考的还行,更新一波,分享一下我的解法。
    考完人没了,听说老师觉得以前总是有学生一个小时就交卷子,他们觉得很没面子所以今年就加大难度了,总算是没人提前交卷子了,他们觉得卷子出得很成功……老师也说要海底捞了,呜呜呜,好吧,昨天刚考完,趁还记得题目给后来的兄弟姐妹提个醒

    总共四道类型大题
    一.选择题 5道10分
    二.填空题 10道10分
    三.简答题 3道20分
    四.算法题 3道30分

    一.选择题 ( 五个每个两分)

    1.循环链表逆置的时间复杂度
    2.有向图中,按照字典序列深度搜索的生成二叉树为(字典序列就是a、b、c… )
    < a , b > , < a , d > , < b , c > , < c , e > , < d , f > , < e , g >;
    则下列哪个一定不是该有向图中的边:< b , g > , < g , a > , < c , f > , < d , a >
    (点 大概是这样的,记不太清了)
    3.拓扑排序,若该图的邻接矩阵只有上三角,那么拓扑序列是不是唯一?
    5.225个序列块用分块查找后再使用顺序查找,最短平均比较次数是多少(16次,分块查找平均8次,查找到某一块后顺序查找平均8次)

    二.填空题 (十个每个一分)

    1.1表示进栈,0表示出栈,入栈顺序为 a、b、c、d、e,经过1101011操作后的出栈顺序。
    2.一个n个元素的小根堆,求其中获得最大和最小元素需要比较总次数(个人感觉最小元素不需要比较可以直接得出,最大元素肯定在后 n/2 里面、需要比较)
    3.11个初始序列段,四路归并需要添加的序列段个数(套公式就完了)
    4.构造哈希表的标准什么的
    5.高度为n的AVL树的节点问题
    6.一个n个节点的搜索树,搜索一个数,求最少和最多比较次数
    10.若遍历 边密集的图 最好用哪个算法?(肯定是Prim啊)

    三.简答题

    1. 画出AOE图,关键路径问题,和15年考的差不多。(8分) // 另外老师上课也会着重讲解,比较容易考
    2. 为什么B树的根可以为2,却不规定为m/2。 (5分)
    3. 线性探测建立哈希表问题,并求出平均失败、成功比较次数 (7分)//比较重要,经常考

    四.算法题 (三个每个十分)

    1. 给定任意一个含有n个字符的 0-9 数字串,例如“1236” 、“4568125”,删除其中k个使得数字最小,比如15367删除其中两个就是136,写出算法。(算法:由前向后遍历,遇到某个值比它后面的值要大的时候,就删除该值、注意删除了后,不要马上后移比较、还得往前比较,比如 5793456,第一次肯定删除了9,然后得回退比较 7 和 3 ,就这样一直比较下去,若是遍历完,删除元素的个数没有 k 个,那么此时就直接删尾部的元素、直到删到k个)
    2. 给定任意一棵二叉树,求根结点到叶节点的最长路径。
      这道题若是没有经验很容易做不出来,不幸中的万幸是笔者在复习中正好涉及,做了总结,传送门:六.根叶路径(这是递归写的),不幸中的万幸中的不幸是笔者没记住。。。 ( 个人认为该题用后序遍历非递归很简单、因为栈里面存储的就是根到该节点路径 也就是它的祖宗 ,可以直接进行比较,不懂可以琢磨一下)
    3. 新冠病毒传染问题,若传染者与被传染者之间存在一条有向边,这样形成一副有向图,求0号传染源到其他人被传染者的最短传染路径,写出算法。(不就是最短路径吗)

    A . 根据笔者做题总结:考试一般会出选择填空类的小题,包含学过的各个知识点,而且比较详细,需要理解,但是会了就不难,最重要的一点是,老师们出的题感觉有点创新性,虽然不难。比较着重考的有链表,栈的运算,(循环)队列运算,B树,AVL树的左旋右旋(一般不会考代码编写,就是考一考怎么旋转),内部排序也非常重要!!!考试必考(尤其是选择、归并和堆等等都很重要)!可以参考一下我总结的排序: 内部排序专题 ,外部排序考的虽然没有内排多,但是也是很重要,而且可能考大题!外部排序我也做了归纳:外部排序专题
    再就是简答题算法题了。
    简答题一般就是一些关键路径,拓扑排序,哈希表之类的,不难。
    算法题最好记住图,树的各种遍历方法,最短路径的两种算法(Dijkstra,Floyd),最小生成树的两种算法(Prim,Kraskal)还是传送门:重点算法总结

    B.以上的算法总结都是笔者啃书,啃网课(B站王道考研,慕课 武大李春葆的数据结构)为期末准备做的笔记,有一些自己的看法,各位兄弟姐妹可以参考。

    想要拿高分最好还是多刷题,考前一两个星期就要开始刷题了,纸张记忆那里的题很多没答案而且乱七八糟,题目还非常老,还要9块钱一本。。。实在没办法可以买一本不过也可以找一些学长要资源的(以前的期末题)。我也要感谢一些学长提供的资源让我对考试重点有一个大概的了解不至于考前比较盲目复习。

    以上就是笔者这次考试的经验了,希望对后来的兄弟姐妹有些帮助。

    ps:好像从来没考过KMP及其优化算法。。。笔者还以为老师们留着给我们第一次考考试一试呢,亏我还认真看了。不过不代表不会考!这一点需要警惕啊。

    有一些忘了的题目代表不难……想起来再加

    更多相关内容
  • 哈工大数据结构
  • 国家精品课程网上有相应的视频教程,这是对应的ppt讲义,分别由刘杨、李秀坤、张岩等几位老师轮流授课,个人觉得是数据结构讲的比较好的
  • 哈工大张岩老师班级的实验,第一个,算术表达式求值,第二个,树,第三个,图;里面有报告。学弟学妹们参考吧!乐学网查出抄袭本人概不负责,特此声明。
  • 哈工大数据结构课件

    2013-10-16 10:57:52
    哈工大数据结构课件,和大家分享一下。讲得都挺好的,感谢老师。
  • 2020年秋哈工大数据结构作业3树形结构及其应用源代码
  • 爱课程上面的PPT,从校内网站下载,国家精品课程网上有相应的视频教程,这是对应的ppt讲义,分别由刘杨、李秀坤、张岩等几位老师轮流授课。
  • 哈工大数据结构实验三——图形结构及其应用

    千次阅读 多人点赞 2020-11-03 11:21:14
    数据结构实验三目录0.实验要求1.实验思路1.1实现图的存储1.1.1 图的邻接矩阵存储1.1.2 使用图的邻接矩阵建立一个图1.1.3 图的邻接表存储1.1.4 使用图的邻接表建立一个图 0.实验要求 1.实验思路 1.1实现图的存储 ...

    0.实验要求

    在这里插入图片描述

    1.实验思路

    1.1实现图的存储

    1.1.1 图的邻接矩阵存储

    图的邻接矩阵存储就是,把图看成是一个二维矩阵,矩阵A[i][j]的值就表示节点i和节点j之间的边的权重,如果顶点i和顶点j之间没有边,则设置A[i][j] = 正无穷大。
    因此,用邻接矩阵的形式存储图的结构,我们需要以下三个信息

    1. 邻接矩阵
    2. 所有的顶点的信息
    3. 图的顶点个数和边的个数
    #include<iostream>
    #include<fstream>
    #include<queue>
    #include<stack>
    #define max 100
    typedef int data;//权重的数据类型 
    using namespace std;
    bool visited[max];
    int dfn[max];//顶点的先深编号 
    int count=1;
    //邻接矩阵的存储结构 
    typedef struct{
     int vertex[max];//邻接矩阵的顶点数组
     data edge[max][max];//邻接矩阵的边值 
     int n,e;//邻接矩阵的顶点和边的个数 
    }mygraph;

    看一个实例,假设边的权重为1表示两个顶点之间有边,边的权重为0表示两个顶点之间没有边。

    在这里插入图片描述

    1.1.2 使用图的邻接矩阵建立一个图

    1. 指定图的顶点的个数和边的个数
    2. 初始化邻接表和邻接矩阵
    3. 根据给定的顶点和顶点的权重改变邻接矩阵的值。 注意:对于无向图来说,邻接矩阵是对称的,所以如果顶点i , j之间权重为k,则A[i][j] = A[j][i] = k
    void CreateGraph(mygraph *G){// 创建邻接矩阵 
     int i,j,k,w;
        cout<<"输入顶点个数和边的个数"<<endl;
        cin>>G->n>>G->e;//输入顶点个数和边的个数;
        for(i=0;i<G->n;i++){
          G->vertex[i]=i;
       } 
       for(i=0;i<G->n ;i++)
         for(j=0;j<G->n ;j++)
             G->edge[i][j]=0;//初始化邻接矩阵 
       for(k=0;k<G->e;k++){
         cout<<"输入边(i,j)和权重w"<<endl;
         cin>>i>>j>>w;
         G->edge[i][j]=w;//输入边(i,j)和权重w 
         G->edge[j][i]=w;
     }
    }
    void wenjianCreateGraph(mygraph *G){// 从文件创建邻接矩阵 
        fstream in;
        in.open("tu1.txt");
        int i,j,k,w;
        in>>G->n>>G->e;//输入顶点个数和边的个数;
        for(i=0;i<G->n;i++){
          G->vertex[i]=i;
       } 
       for(i=0;i<G->n ;i++)
         for(j=0;j<G->n ;j++)
           G->edge[i][j]=0;//初始化邻接矩阵 
       for(k=0;k<G->e;k++){
         in>>i>>j>>w;
         G->edge[i][j]=w;//输入边(i,j)和权重w 
         G->edge[j][i]=w;
       }
       in.close();
    }

    算法时间复杂度:O(n^2+n+2e )//n个顶点初始化,n^2个边的初始化,输入无向图的2e条边
    算法空间复杂度:O(n^2+n )//存储n个顶点及n^2个边值信息

    void shuchugraph(mygraph *t){//打印邻接矩阵的信息 
       for(int i=0;i<t->n ;i++){
          cout<<"\t"<<i; 
      }
      cout<<endl;
      for(int i=0;i<t->n ;i++){
          cout<<i<<"\t";
        for(int j=0;j<t->n ;j++){
           if(t->edge[i][j]==0){
             cout<<"∞\t";
           }
           else
             cout<<t->edge[i][j]<<"\t";
        }
        cout<<endl;
     }
    }

    在这里插入图片描述

    1.1.3 图的邻接表存储

    图的邻接表存储,就是对于每个顶点v来说,和这个顶点v相连的所有邻接点构成一个线性表。

    我们需要把顶点分成两类,一类是主顶点,一类是和顶点链接的边顶点。

    对于每个主顶点,我们需要存储以下信息:

    1. 有一个指针域,指向的是和顶点v邻接的第一个顶点。
    2. 顶点的下标,指明了顶点的编号
    3. 一个标记布尔类型的值,标记这个顶点是否被访问过(用于图的遍历)
    typedef struct {//顶点表节点 
       int dingdian;//顶点表节点
       bool zouguo;//标记节点是否被访问过 
       Edgenode *firstedge;//边链表头指针 
    }Vertex;

    对于每一个边顶点,我们需要存储以下信息。

    1. 顶点下标
    2. 和主顶点邻接的边的权重
    3. 指向下一边表节点的指针
    typedef struct node{//边表节点 
      int xiabiao;//顶点下标
      data cost;/和主顶点邻接的边的权重
      struct node *next;//指向下一边表节点的指针 
    }Edgenode; 

    那么整个图就可以用一个主顶点数组来表示,同时需要指明图的边的个数和顶点的个数。

    typedef struct {//图的邻接表 
        Vertex vexlist[max];//顶点数组 
        int n,e;//顶点个数和边的个数 
    }adjgraph;

    看一个例子
    在这里插入图片描述

    1.1.4 使用图的邻接表建立一个图

    输入顶点个数和边的个数
    初始化顶点邻接表
    根据给定的邻接顶点i和j,创建边顶点p和q分别存储顶点i和j的信息,让主顶点i指向q,且让主顶点j指向边顶点q。

    void CreateadjGraph(adjgraph *G){// 创建邻接表
         int i,k,j;
         data weight;
         cout<<"请输入顶点个数和边的个数"<<endl; 
         cin>>G->n >>G->e ; 
        for(i=0;i<G->n;i++){
           G->vexlist[i].dingdian=i;
           G->vexlist[i].firstedge=NULL;//初始化邻接表 
     }
        for(k=0;k<G->e ;k++){
          cout<<"输入边(i,j)和权重w"<<endl;
          cin>>i>>j>>weight;
          Edgenode* p=new Edgenode;
          p->xiabiao =j;p->cost =weight; 
          p->next =G->vexlist[i].firstedge ;
          G->vexlist[i].firstedge =p;
          Edgenode* q=new Edgenode;
          q->xiabiao =i;q->cost =weight; 
          q->next =G->vexlist[j].firstedge ;
         G->vexlist[j].firstedge =q;
     }
    }
    void wenjianCreateadjGraph(adjgraph *G){// 从文件创建邻接表
          fstream in;
          in.open("tu2.txt");
          int i,k,j;
          data weight;
          in>>G->n >>G->e ; 
          for(i=0;i<G->n;i++){
             G->vexlist[i].dingdian=i;
             G->vexlist[i].firstedge=NULL;//初始化邻接表 
     }
         for(k=0;k<G->e ;k++){
             in>>i>>j>>weight;
             Edgenode* p=new Edgenode;
             p->xiabiao =j;p->cost =weight; 
    	 p->next =G->vexlist[i].firstedge ;
             G->vexlist[i].firstedge =p;
             Edgenode* q=new Edgenode;
             q->xiabiao =i;q->cost =weight; 
             q->next =G->vexlist[j].firstedge ;
            G->vexlist[j].firstedge =q;
     }
     	in.close();
    }
    void shuchuadjgraph(adjgraph *t){//打印邻接表 
        for(int i=0;i<t->n ;i++){
          cout<<i<<":\t";
          Edgenode *p;
          p=t->vexlist[i].firstedge;
          while(p!=NULL){
            cout<<p->xiabiao<<"\t";
            p=p->next ;
         }
          cout<<endl;  
       } 
    }

    1.2. 图的邻接矩阵和图的邻接表两种存储结构的转换

    1.2.1 图的邻接矩阵转向图的邻接表

    1. 思路很简单,先初始化邻接矩阵,根据顶点个数和边的个数。
    2. 然后遍历邻接矩阵,如果A[i][j] 不等于0 , 则表示顶点i 和 顶点j
      之间邻接,边权重为A[i][j],然后用之前讲过的邻接表创建图的方法来创建邻接表。
    void jzhuanhuanb(mygraph *G,adjgraph *T){//将邻接矩阵G转化为邻接表T 
         T->n=G->n ;//初始化邻接表 
         T->e =G->e;//初始化邻接表 
         for(int i=0;i<G->n;i++ ){//初始化邻接表
            T->vexlist[i].dingdian =i;
            T->vexlist[i].firstedge=NULL;
         }
         for(int j=0;j<G->n;j++){
            for(int k=0;k<G->n ;k++){
              if(G->edge[j][k]!=0){
                  Edgenode *p=new Edgenode;
                  p->xiabiao=G->vertex[k];//顶点赋值 
                  p->cost =G->edge[j][k];  //边权重赋值 
                  p->next =T->vexlist[j].firstedge  ;
                  T->vexlist[j].firstedge=p;
             }  
          }
        }  
    }

    在这里插入图片描述

    1.2.2 图的邻接表转向图的邻接矩阵

    思路同上,先初始化,然后遍历每个顶点的邻接顶点,然后给邻接矩阵赋值即可。

    void bzhuanhuanj(mygraph *G,adjgraph *T){//将邻接表转换为邻接矩阵
        Edgenode *p;
        G->n =T->n;//初始化邻接矩阵
        G->e =T->e ;//初始化邻接矩阵
        int i,j;
        for(i=0;i<G->n;i++){
           for( j=0;j<G->n;j++){
              G->edge[i][j]=0;//初始化邻接矩阵 
          }
         }
         for(int k=0;k<G->n;k++){
            p=T->vexlist[k].firstedge ;
            while(p!=NULL){
               G->edge[k][p->xiabiao]=p->cost;//将边权重赋值 
              p=p->next ;
          }
         }
    }

    在这里插入图片描述

    1.3 图的深度优先遍历

    1.3.1 邻接矩阵表示的图的深度优先遍历

    1.3.1.1 递归

    思路:借助一个标记数组,标记了每个顶点是否被访问过。

    1. 首先对每个顶点标记为未访问过。
    2. 然后对于顶点v,如果顶点v没有被访问过,则访问这个顶点,并且把这个顶点标记为访问过,然后递归的访问这个顶点邻接的顶点。
    3. 访问完顶点v的所有邻接的节点后,把森林的个数加1,然后再去访问没有访问过的顶点k,再转2.
    void DFSX(mygraph *G,int x){//辅助深度递归 (通过邻接矩阵)
        visited[x]=true;
        cout<<G->vertex[x]<<" ";
        for(int j=0;j<G->n;j++){
           if(!visited[j]&&G->edge[x][j]!=0)
              DFSX(G,G->vertex[j]);
        }
       }
    void diguishen(mygraph *G){    //邻接矩阵深度递归算法 
         for(int i=0;i<G->n;i++){//将每个节点标记为未访问过 
            visited[i]=false;
        }
         int count=1;//森林个数 
         for(int i=0;i<G->n;i++){
           if(!visited[i]){
             cout<<"森林"<<count++<<":"; 
             DFSX(G,i);
             cout<<endl;
         }  
        }
     }

    1.3.1.2 非递归

    一般对于所有的递归算法来说,要把它变成非递归算法,则要利用栈。
    算法原理:

    1. 首先对每个顶点标记为未访问过。
    2. 然后遍历所有的顶点,对于顶点v,如果顶点v没有被访问过,则访问这个顶点,并且把这个顶点标记为访问过,并且把这个顶点压入栈中。
    3. 当栈不为空时,取栈顶顶点t,然后访问所有和顶点t邻接的顶点x。如果顶点x没有被访问过,则访问这个顶点,并且把这个顶点标记为访问过,并且把这个顶点x压入栈中。然后再去访问顶点x邻接的所有顶点。
    4. 考察完顶点v所邻接的所有顶点之后,再去访问没有访问过的顶点。
    void feidiguishen2(mygraph *G){ //邻接矩阵深度非递归算法 
        for(int l=0;l<G->n ;l++)//将每个节点标记为未访问过 
           visited[l]=false;
        stack<int>s;
        int count=1;//森林个数 
         for(int j=0;j<G->n;j++){
           if(!visited[j]){
            cout<<"森林"<<count++<<":";
            visited[j]=true;
            s.push(j);
           cout<<G->vertex[j]<<" ";
           while(!s.empty() ){
             int t = s.top();
             bool flag = false;
             for(int k=0;k<G->n ;k++){
               if(G->edge[t][k]!=0){
                 if(!visited[k]){
                   visited[k]=true;
                   cout<<G->vertex[k]<<" ";
                   s.push(k);
                   flag = true;
                 break ;
              }
            }
        }
           if (flag == false )
           s.pop() ;    
        }
            cout<<endl;
      } 
     }
    } 

    1.3.2 邻接表表示的图的深度优先遍历

    思路一样,就是代码不一样

    1.3.2.1 递归

    void DFSX2(adjgraph *G,int x){//邻接表深度递归辅助算法 
        Edgenode *p;
        visited[x]=true;//标记为访问过 
        cout<<G->vexlist[x].dingdian<<" ";
        p=G->vexlist[x].firstedge;
        while(p){
         if(!visited[p->xiabiao])
           DFSX2(G,p->xiabiao);
           p=p->next ;
    }
    }
    void diguishen2(adjgraph *G){//邻接表深度递归算法 
        for(int i=0;i<G->n;i++){//将每个节点标记为未访问过 
            visited[i]=false;
        }
        int count=1;
        for(int i=0;i<G->n;i++){//遍历每一个节点 
           if(!visited[i]){
             cout<<"森林"<<count++<<":"; 
             DFSX2(G,i);
            cout<<endl;
         }  
       }
    }

    1.3.2.2 非递归

    void feidiguishen(adjgraph *G){//邻接表深度非递归算法 
        stack<int>s;
        Edgenode *p;
        for(int j=0;j<G->n;j++){//将每个节点标记为未访问过 
          visited[j]=false; }
          int count=1;//森林数目 
          for(int i=0;i<G->n;i++){//遍历每个节点 
             if(!visited[i]){
             cout<<"森林"<<count<<":"; 
             visited[i]=true;
             s.push(i);
             cout<<G->vexlist[i].dingdian<<" ";
             p=G->vexlist[i].firstedge;
             while(!s.empty()){
                p=G->vexlist[s.top()].firstedge ;
                bool flag = false;
                while(p){
                 if(!visited[p->xiabiao ]){
                     visited[p->xiabiao ]=true;
                     cout<<G->vexlist[p->xiabiao].dingdian<<" ";//输出该节点 
         		 s.push(p->xiabiao );  
        		 p=G->vexlist[p->xiabiao].firstedge ;
        		 flag = true;
         		break;
        }
        	else{
        		 p=p->next ;
       	 }
      	 }
       	if(flag == false){
        	 s.pop() ;
        }
      } 
      cout<<endl;
      count++;
      }
     } 
    } 

    1.4图的广度优先遍历

    广度优先遍历和我们之前将的二叉树的层序遍历几乎一样。有一个不同的地方就是图不一定是连通的,可能有几个森林,而二叉树一定是连通的。
    思路:借助队列来实现。

    1. 首先对每个顶点标记为未访问过。
    2. 然后遍历所有的顶点,对于顶点v,如果顶点v没有被访问过,则访问这个顶点,并且把这个顶点标记为访问过,并且把这个顶点压入队列中。
    3. 当队列不为空时,取队首顶点t,然后访问所有和顶点t邻接的顶点x。如果顶点x没有被访问过,则访问这个顶点,并且把这个顶点标记为访问过,把这个顶点x压入队列中。每一次访问顶点就从队首取出一个顶点即可。
    4. 当队列为空时,再去考察其他没有访问过的顶点。

    1.4.1 邻接矩阵表示的图的广度优先遍历

    void guangdu2(mygraph *G) {//邻接矩阵广度优先遍历 
        for(int j=0;j<G->n;j++){
           visited[j]=false;
       }
        queue<int>s;
        int count=1;
        for(int i=0;i<G->n;i++){
           if(!visited[i]){
           cout<<"森林"<<count++<<":"; 
           visited[i]=true;
           cout<<G->vertex[i]<<" ";
           s.push(G->vertex[i]);
        while(!s.empty() ){
            int k=s.front()  ;
            s.pop() ;
            for(int j=0;j<G->n;j++){
              if(G->edge [k][j]!=0){
                 if(!visited[j]){
                    visited[j]=true;
                   cout<<G->vertex[j]<<" ";
                   s.push(G->vertex[j]); 
            }      
           } 
          }
        }
       cout<<endl;
       }   
      }
    }

    1.4.2邻接表表示的图的广度优先遍历

    void guangdu(adjgraph *G){//邻接表广度优先遍历 
        for(int j=0;j<G->n;j++){
          visited[j]=false;
        }
        queue<int>s;
        Edgenode *p;
        int count=1;
        for(int i=0;i<G->n;i++){
          if(!visited[i]){
            cout<<"森林"<<count++<<":"; 
            visited[i]=true;
            cout<<G->vexlist[i].dingdian<<" ";
            s.push(G->vexlist[i].dingdian);
            while(!s.empty() ){
               p=G->vexlist[s.front()].firstedge;
               s.pop() ;
               while(p!=NULL){
                 if(!visited[p->xiabiao]){
                    visited[p->xiabiao]=true;
              	cout<<G->vexlist[p->xiabiao].dingdian<<" ";
          		 s.push(p->xiabiao); 
         		}
             p=p->next;    
          } 
         }
          cout<<endl;
       } 
      
      }
     }

    1.5主程序

    void zrh(){
          int x=0;//用来判断当前的无向图是用邻接矩阵还是邻接表来表示的,0代表邻接矩阵,1代表邻接表 
         cout<<"-----------------------------------------------------------------"<<endl;
         cout<<"0.退出                                                          |"<<endl;
        cout<<"1.通过从文件读入创建一个无向图的邻接矩阵                        |"<<endl;
        cout<<"2.通过从文件读入创建一个无向图的邻接表                          |"<<endl;
        cout<<"3.通过输入创建一个无向图的邻接矩阵                              |"<<endl;
        cout<<"4.通过输入创建一个无向图的邻接表                                |"<<endl;
        cout<<"5.显示邻接矩阵                                                  |"<<endl;
        cout<<"6.显示邻接表                                                    |"<<endl;
        cout<<"7.将邻接矩阵转化为邻接表并显示                                  |"<<endl;
        cout<<"8.将邻接表转化为邻接矩阵并显示                                  |"<<endl;
        cout<<"9.深度优先递归遍历无向图                                        |"<<endl;
        cout<<"10.深度优先非递归遍历无向图                                     |"<<endl;
        cout<<"11.广度优先遍历无向图                                           |"<<endl;
        cout<<"-----------------------------------------------------------------"<<endl; 
        mygraph g;//创建无向图 的邻接矩阵 
        adjgraph t;//创建无向图的邻接表 
        int n;
        cin>>n;
        while(n){
          switch(n){
            case 1:
              wenjianCreateGraph(&g);
              x=0;
             break;
           case 2:
            wenjianCreateadjGraph(&t);
            x=1;
            break;   
          case 3:
             CreateGraph(&g);
           x=0;
          break;  
         case 4:
            CreateadjGraph(&t);
            x=1;
            break;  
         case 5:
           shuchugraph(&g);
           x=0;
           break;  
         case 6:
           shuchuadjgraph(&t);
             x=1;
            break;  
        case 7:
           adjgraph t1;
           cout<<"邻接矩阵为:"<<endl; 
           shuchugraph(&g);
           cout<<"转化为邻接表后为:"<<endl ;
          jzhuanhuanb(&g,&t1);
         shuchuadjgraph(&t1);
         break;
        case 8:
          mygraph t2;
          cout<<"邻接表为:"<<endl; 
          shuchuadjgraph(&t);
          cout<<"转化为邻接矩阵后为:"<<endl ;
          bzhuanhuanj(&t2,&t);
          shuchugraph(&t2);
          break;
        case 9:
        if(x==1){ 
           diguishen2(&t);
       }   
        else{
           diguishen(&g);
        }     
           break;
         case 10:
           if(x==1){
            feidiguishen(&t); 
         }
          else{
             feidiguishen2(&g);
         } 
         break;
        case 11:
           if(x==0){
               guangdu2(&g);
          }
         else{
             guangdu(&t);
          } 
          break;
         default :
          n=0;
         break;                      
     }
     cout<<"-----------------------------------------------------------------"<<endl;
     cout<<"0.退出                                                          |"<<endl;
     cout<<"1.通过从文件读入创建一个无向图的邻接矩阵                        |"<<endl;
     cout<<"2.通过从文件读入创建一个无向图的邻接表                          |"<<endl;
     cout<<"3.通过输入创建一个无向图的邻接矩阵                              |"<<endl;
     cout<<"4.通过输入创建一个无向图的邻接表                                |"<<endl;
     cout<<"5.显示邻接矩阵                                                  |"<<endl;
     cout<<"6.显示邻接表                                                    |"<<endl;
     cout<<"7.将邻接矩阵转化为邻接表并显示                                  |"<<endl;
     cout<<"8.将邻接表转化为邻接矩阵并显示                                  |"<<endl;
     cout<<"9.深度优先递归遍历无向图                                        |"<<endl;
     cout<<"10.深度优先非递归遍历无向图                                     |"<<endl;
     cout<<"11.广度优先遍历无向图                                           |"<<endl;
     cout<<"-----------------------------------------------------------------"<<endl; 
     if(x==0)
      cout<<"当前无向图为邻接矩阵表示法,请根据提示选择正确的操作:"<<endl;
     else
       cout<<"当前无向图为邻接表表示法,请根据提示选择正确的操作:"<<endl;
     if(n!=0)
      cin>>n;
     } 
    }   

    1.6结果分析

    展开全文
  • 实验项目:图型结构的建立与搜索 实验题目:图的存储结构的建立与搜索 实验内容 1: 图的搜索(遍历)算法是图型结构相关算法的基础,本实验要求编写程序 演示无向图典型存储结构的建立和搜索(遍历)过程。 实验...
  • 哈工大数据结构
  • 排序方法是数据处理的最基本和最重要的操作。其目的是将一组“无序”的 记录序列调整为“有序”的记录序列。 实验题目:排序方法的实现与实验比较 实验内容: 实现一组经典的排序算法,通过实验数据的设计,考察...
  • 哈工大数据结构
  • 哈尔滨工业大学最新版的数据结构与算法课件,内容覆盖全书
  • 哈工大数据结构实验3比赛图,使用矩阵行列变换的思想做的,老师评价很好。
  • 实验项目:线性表的链式存储结构与应用 实验题目:一元多项式计算器 实验内容: 设计线性表的动态或者静态链式存储结构,并实现一个一元多项式的计算器。 实验要求: 以动态或者静态链表存储一元多项式,在此基础上...
  • 哈工大数据结构与算法全部实验汇总,包括代码和实验报告,供给广大学弟学妹。学艺不精,有不足的地方希望大家多多包涵,进行改进。
  • C语言所写源代码有注释,哈工大数据结构实验课自己所作,仅供参考
  • 实验项目:查找结构的实验比较 实验题目:BST 查找结构与折半查找方法的实现与实验比较 实验内容: 本实验要求编写程序实现 BST 存储结构的建立(插入)、删除、查找和排 序算法;实现折半查找算法;比较 BST 查找...
  • 图形结构及其应用
  • 哈尔滨工业大学数据结构试题
  • 实验项目:树型结构的建立、遍历和应用 实验题目:二叉树存储结构的建立、遍历和应用 实验内容: 树型结构的遍历是树型结构算法的基础,本实验要求编写程序演示二叉树 的存储结构的建立方法、遍历过程以及应用。 ...
  • 哈工大03年数据结构期末试卷答案,望对大家有益
  • 第一章 绪论.ppt 第二章 线性表.ppt 第三章 树.ppt 第四章 图及算法.ppt 第五章 查找.ppt 第六章 内排序.ppt
  • 哈工大数据结构实验二——哈夫曼编码与译码方法

    千次阅读 多人点赞 2020-10-22 22:00:03
    发现解码前和解码后一模一样 别忘了点个关注 其他的实验链接 哈工大数据结构实验一 线性结构及其应用 哈工大数据结构实验1 算术表达式求值 哈工大数据结构实验2——二叉树存储结构的建立、遍历和应用 哈工大2019秋...

    哈工大数据结构、算法设计、计算机系统、软件构造等所有实验我都会发布在博客上,我会慢慢更新的,如果对你有帮助的话,可以多多关注一下。


    其他的实验链接

    哈工大数据结构实验一 线性结构及其应用
    哈工大数据结构实验1 算术表达式求值
    哈工大数据结构实验2——二叉树存储结构的建立、遍历和应用
    哈工大2019秋数据结构期末试题

    在这里插入图片描述

    对于本次实验,无非要解决的就是以下几个问题:

    1. 用什么数据结构去表示哈夫曼树

    2. 如何构造哈夫曼树

    3. 构造了哈夫曼树之后如何根据哈夫曼树将文本文件进行哈夫曼编码以及如何解码

    本文将逐一阐述上述问题如何解决

    1. 首先,来看一下哈夫曼树的定义
      定义:给定n个权值作为n个子叶节点,若树的带权路径最短,则这课树被称为哈夫曼树。
    2. 这里要注意的几个点有:
      ①只有叶节点才有权重,非叶节点不存储字符,也不带权重
      ②什么是带全路径?带权路径就是叶节点到根节点的路径长度乘以叶节点所带的权重。比如下面这个二叉树的带权路径为:
      2x10 + 2x20 + 2x50 + 2x100 = 360
      ③哈夫曼树是带权路径最短的二叉树。

    在这里插入图片描述
    3. 好的,现在你已经知道哈夫曼树的定义,也了解了带权路径的定义。那么我们现在的目标就是构造出最短带权路径的二叉树。相信看到这里你已经有了构思,对于权重越大的叶节点,如果它离根节点越近,那么这个权重很大的叶节点对总的带权路径长度影响就越小。(right!)
    比如对于上面的那个二叉树,对于权重为100的节点,如果我们把它放在离根节点最近的地方,50这个节点放在离根节点次近的地方,那么我们可以构造出一棵权重路径更小的二叉树。如图所示。
    这棵树的权重路径为: 1x100 + 2x50 + 3x20 + 3x10 = 100 + 100 + 60 + 30 = 290 < 350。
    在这里插入图片描述

    看到这里,咱们的思路就清晰了,现在正式开始讲具体步骤。

    假设有n个权重,构造出n个叶节点,n个权重分别为w1,w2…wn,哈夫曼树的构造规则如下:

    1. 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
    2. 在森林中选出根结点的权值最小的两棵树进行合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
    3. 从森林中删除选取的两棵树,并将新树加入森林;
    4. 重复(02)、(03)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。

    以{5,6,7,8,15}为例,咱们试着构造一棵二叉树。

    在这里插入图片描述

    ① 首先选出权值最小的两棵树进行合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;也就是选出5和6,合并成11,剩下的树的节点权重为{7,8,11,15}

    在这里插入图片描述

    ②在剩下的树的节点权重为{7,8,11,15},选出最小的两个权重{7,8}构造棵新树,权重为15,剩下的节点权重为{11,15,15}

    在这里插入图片描述
    ③同理,在剩下的节点权重为{11,15,15}选出{11,15},构造新的节点,其权重为26,剩下的节点为{15,26}

    在这里插入图片描述

    ④最后,选择{15,26}构造根节点即可。

    在这里插入图片描述
    上述构造出的 二叉树就是哈夫曼树。
    正确性证明点击这里看即可,本篇不在阐述

    好的,现在重新回到我们开始提出的三个问题。

    1.用什么数据结构去表示哈夫曼树

    首先,每个节点需要存储权重,以及左右儿子,同时,为了讲两个节点合并构造一个新的父节点,我们也需要在每个节点存储父节点。

    最好的数据结构就是使用静态三叉链表。
    所有节点构成一个数组,节点的父子关系可以用数组下标表示。

    #define N 53  //带权重的n个叶子节点数,根据文件中字符种类的个数来确定 
    #define M 2*N-1 //n个叶子节点的哈夫曼树具有2*n-1个节点 
    typedef struct{
         	float weight;//权重
     	int lchild;//左儿子
     	int rchild;//右儿子
     	int parent;//父亲  
    }node;//静态三叉链表 
    typedef node huffman[M]; //哈夫曼树 
    typedef char *huffmancode[N];//存储每个字符的哈夫曼编码表 

    2. 如何构造哈夫曼树

    我的思路是:

    1. 给定n个权重,那么叶节点就有n个,非叶节点n-1个。那么首先初始化n个叶节点,包括初始化叶节点的权重,左儿子、右儿子、父亲初始化为-1。父亲为-1表示一开始所有的叶节点还没有选中来构造树。
    2. 然后就开始选择两个叶节点来构造一个新的节点,这个节点的权重为两个儿子的权重之和。选择策略是:从所有的没有父亲的节点找出两个权重最小的节点。这个功能我在函数selectmin中实现,其中参数s1,和s2传递的是引用,在函数内改变s1和s2的值,会直接改变函数外s1和s2的值。

    具体实现如下:

    void selectmin(huffman &T,int k,int &s1,int &s2):选出权重最小的两个节点

    void selectmin(huffman &T,int k,int &s1,int &s2){//选出两个权重最小的节点 
    	int min=1000000,tmp=0;
      	for(int i=0;i<=k;i++){
      	   if(T[i].parent==-1){
        	      if(min>T[i].weight){
         		 min=T[i].weight;
        		 tmp=i;
                    }
       	   }
      	}
     	s1=tmp;
     	min=100000;
     	tmp=0;
      	for(int j=0;j<=k;j++){
       	   if((T[j].parent==-1)&&(j!=s1)){
       	      if(min>T[j].weight){
         		  min=T[j].weight;
          		  tmp=j;
        	      }
      	    }
     	 }
      	s2=tmp;  
    }
    void CreatTree(huffman &T,float *w,int n) {//构造哈夫曼树 
     	if(n<=1)
      	    return ;
      	int i;
     	for( i=0;i<n;i++){//初始化哈夫曼树的n个叶节点并赋予权重 
      	    T[i].weight=w[i];
                T[i].lchild=-1;
     	    T[i].rchild=-1;
      	    T[i].parent=-1;
     	}
    	for(;i<M;i++){ //初始化哈夫曼树的非叶节点 
      	   T[i].weight=0;
     	   T[i].lchild=-1;
      	   T[i].rchild=-1;
     	   T[i].parent=-1;
     	} 
     	for(i=n;i<M;i++){
     	   int s1=0,s2=0;
     	   selectmin(T,i-1,s1,s2);//选出权重最小的叶节点 
     	  T[s1].parent=i;
              T[s2].parent=i;
              T[i].lchild=s1;
      	  T[i].rchild=s2;  
      	  T[i].weight=T[s1].weight+T[s2].weight;
     	}
    }

    3.哈夫曼编码

    1. 对于一棵哈夫曼树来说,编码方式就是:从根节点开始,往左走,就讲路径编码为0,往右走就讲路径编码为1,这样从根节点到叶节点所经过的所有01串就是对应叶节点的哈夫曼编码。如图所示,那么15:编码为0,5:编码为10,依次类推。
    2. 具体实现思路:对于每一个节点,都开始递归的找父亲节点(直到找到根节点停止递归),如果这个节点是父亲的右儿子,则编码为1,否则编码为0。将编码01保存在一个临时的数组cd内即可。字符串数组HT[i]存储了第i个叶节点的编码01串。

    在这里插入图片描述

    void bianma(huffman T,huffmancode &HT){//对每个叶节点进行编码 
      	char cd[N];//临时保存每个节点的哈夫曼编码 
      	cd[N-1]='\0';
      	int start,c,f;
      	for(int i=0;i<N;i++){
      	   start=N-1;
       	   c=i;
       	   f=T[i].parent;
       	   while(f!=-1){
       	 	 if(T[f].lchild==c){
         		 cd[--start]='0';
        	  }
       	 else{
         	     cd[--start]='1';
        	}
       	 c=f;
       	 f=T[f].parent;//递归查找
       	} 
       	HT[i]=(char*)malloc((N-start)*sizeof(char));
       	strcpy(HT[i],&cd[start]);
      	} 
    }
    void yasuo(huffmancode HC,char ch[]){//将英文文件压缩为哈夫曼编码文件 
     	fstream in,out;
    	 in.open("hafuman.txt"); //打开英文文件 
    	 out.open("bianma.txt"); //打开要压缩的哈夫曼编码文件 
    	 char a[100000];
    	 in.getline(a,100001);//读出英文文件的内容 
    	 int len1=strlen(a);
     	 int len2=strlen(ch);
    	 for(int i=0;i<len1;i++){
     	    for(int j=0;j<len2;j++){
       		if(ch[j]==a[i]){
        		out<<HC[j];//将每个字符的哈夫曼编码输入到哈夫曼编码文件中 
       		 cout<<HC[j];
                     }
     	     }
    	 }
     	in.close() ;//关闭文件 
     	out.close() ; //关闭文件 
    }

    4.哈夫曼解码

    哈夫曼解码:根据01串,从根节点开始在哈夫曼树搜索,0就往左走1就往右走,直到走到根节点为止。

    void jiema(huffman T,char *ch,char test[],char *result) {
    	 int p=M-1;//根节点 
    	 int i=0;//指示串的第i个字符 
    	 int j=0;//解码出的第j个字符 
    	 int len=strlen(test); 
    	 while(i<len){
     	    if(test[i]=='0'){
      	         p=T[p].lchild;
     	    }
      	   if(test[i]=='1'){
     	         p=T[p].rchild;
     	   }  
    	  if(p<N){//说明此时为叶节点
     		 result[j]=ch[p];
     	  	 j++;
     		 p=M-1;//重新指向根节点 
     	  }
    	   i++;
          }
     	result[j]='\0';
    }
    void jiemawenjian(huffman T,char *ch){//将从文件读入的哈夫曼编码解码为英文文件 
    	 fstream in,out;
    	 in.open("bianma.txt");
    	 out.open("hafumanbianma.txt");  
    	 char a[100000];
    	 in.getline(a,100001);
    	 char c[100000] ;
    	 jiema(T,ch,a,c);
    	 out<<c;
    	// cout<<"哈夫曼编码文件中的内容为:"<<endl;
    	// cout<<a<<endl;
    	 cout<<"解压为英文文件后的内容为:"<<endl;
    	 cout<<c<<endl;
     	in.close();
    	 out.close();
    }
    void dayincode(huffmancode HC,char ch[]){//打印哈夫曼树的叶节点对应的编码 
          cout<<endl;
          cout<<"每个字符的哈夫曼编码为:"<<endl<<endl;
          cout<<"字符"<<"\t"<<"\t"<<"哈夫曼编码"<<"\t"<<"\t"<<endl; 
          for(int i=0;i<N;i++){
               cout<<ch[i]<<"\t"<<"\t"<<HC[i]<<"\t"<<"\t"<<endl;
     }
         cout<<endl;
    }
       void dayinshu(huffman T,char ch[]){
          cout<<endl;
          cout<<"节点"<<"\t"<<"\t"<<"字符"<<"\t"<<"\t"<<"权重"<<"\t"<<"\t"<<"父亲    "<<"\t"<<"\t"<<"左儿子"<<"\t"<<"\t"<<"右儿子"<<"\t"<<"\t"<<endl;
         for(int i=0;i<M;i++){
           if(i<N){          cout<<i<<"\t"<<"\t"<<ch[i]<<"\t"<<"\t"<<setprecision(9)<<T[i].weight<<"\t"<<"\t"<<T[i].parent<<"\t"<<"\t"<<T[i].lchild<<"\t"<<"\t"<<T[i].rchild<<"\t"<<"\t"<<endl; 
      }
      else{
          cout<<i<<"\t"<<"\t"<<"-1"<<"\t"<<"\t"<<T[i].weight<<"\t"<<"\t"<<T[i].parent<<"\t"<<"\t"<<T[i].lchild<<"\t"<<"\t"<<T[i].rchild<<"\t"<<"\t"<<endl; 
      }
     }   
    }

    main函数

    int main(){
    	 huffman T;
     	char a[10000];//读取文件中的字符个数 
    	 fstream in;
     	in.open("hafuman.txt");//打开文件 
     	if(in.fail() ){//判断是否成功打开文件 
     	     cout<<"error"<<endl;
    
    	 }
     	else{
      		 in.getline(a,10001);//从文件读入10000个字符 
    	 }
     	cout<<"从文件读入的字符总数为:"<<strlen(a)<<endl;
    	 int x=strlen(a);
    	 int len[1000]={0};
    	 for(int i=0;i<x;i++){//将读入的字符频数记录下来 
    		int m=int(a[i]);
      		len[m]++;//字符ascall码为m的字符频数 
    	 }
    	 int g=0;//记录字符个数 
    	 char ch[1000];//每个字符
    	 for(int i=0;i<x;i++){
     	     if(len[i]!=0){
        	     ch[g]=char(i);//将字符ascall码转化为字符并保存在字符数组中 
        	     g++;
       	}
     }
     
    	 cout<<"文件中的不同的字符个数为:"<<g<<endl;
     	 int str[1000];//字符出现的频数 
    	 int k=0;
    	 for(int i=0;i<x;i++){
    	     if(len[i]!=0){
       		str[k]=len[i];
      	         k++;
                 }
     	 }
    	 str[k]='\0';//字符出现的频数 
    	 ch[k]='\0'; 
    	 float w[1000];//字符频率 
    	 int t=strlen(ch);
    	 cout<<"字符\t"<<"\t"<<"频数\t"<<"\t"<<"权重\t"<<"\t"<<endl; 
    	 for(int i=0;i<t;i++){
    	     w[i]=(float(str[i]))/x;
     	     cout<<ch[i]<<"\t"<<"\t"<<str[i]<<"\t"<<"\t"<<w[i]<<"\t"<<"\t"<<endl;
     	}
    	 w[t]='\0'; 
    	 in.close() ;
     	 CreatTree(T,w,N);//构建哈夫曼树
    	 dayinshu(T,ch); //打印哈夫曼树 
    	 huffmancode HC;//构建哈夫曼编码 
    	 bianma(T,HC);//对哈夫曼树进行编码 
     	 dayincode(HC,ch);//打印每个叶节点的编码 
    	 float sum=0.0;//哈夫曼树平均编码长度 
    	 for(int i=0;i<N;i++){
     	    sum+=strlen(HC[i])*w[i];
    	 }
    	 cout<<"哈夫曼树平均编码长度为"<<sum<<endl;
    	 cout<<"哈夫曼树的压缩率为:"<<1 - sum / 8<<endl;  	 
     	 int n=0;
     	cout<<"-------------------------------------------"<<endl;
    	cout<<"0.退出                                     |"<<endl;
    	cout<<"1.将英文文件进行压缩为哈夫曼编码文件并显示 |" <<endl;
     	cout<<"2.将哈夫曼编码文件解压为英文文件并显示     |"<<endl;
     	cout<<"3.比较英文文件和解压后的英文文件           |"<<endl;
     	cout<<"-------------------------------------------|"<<endl;
    	 cin>>n;
    	 while(n){
     	     switch(n){
     	 	case 1:
     	  	   cout<<"哈夫曼编码文件为:"<<endl;
       		   yasuo(HC,ch);//将英文文件压缩为哈夫曼编码文件 
      		   break;
      		case 2:
      	           jiemawenjian(T,ch);//将从文件读入的哈夫曼编码解压为英文文件 
      		    break;
      		case 3:
      		   cout<<"读入的文件内容为:"<<endl;
       		   cout<<a<<endl<<endl<<endl;
      	 	   jiemawenjian(T,ch); 
      		case 0:
     		   n=0;
      	 	   break;
      	       default :
      		   break;  
     }
    	  cout<<"-------------------------------------------"<<endl;
    	  cout<<"0.退出                                     |"<<endl;
    	  cout<<"1.将英文文件进行压缩为哈夫曼编码文件并显示 |" <<endl;
    	  cout<<"2.将哈夫曼编码文件解压为英文文件并显示     |"<<endl;
    	  cout<<"3.比较英文文件和解压后的英文文件           |"<<endl;
    	  cout<<"-------------------------------------------|"<<endl;
    	  cin>>n;
    }

    5.最终结果展示

    1. 从文件中读入任意一篇英文文本文件,分别统计英文文本文件中各字符(包括标点符号和空格)的使用频率;

    读入的英文文本文件:
    在这里插入图片描述

    1. 统计各个字符的使用频率
      在这里插入图片描述在这里插入图片描述

    2. 根据已统计的字符使用频率构造哈夫曼编码树,并给出每个字符的哈夫曼编码(字符集的哈夫曼编码表);
      在这里插入图片描述在这里插入图片描述
      在这里插入图片描述

    3. 每个字符的哈夫曼编码
      在这里插入图片描述

    4. 将文本文件利用哈夫曼树进行编码,存储成压缩文件(哈夫曼编码文件);
      在这里插入图片描述
      在这里插入图片描述

    5. 计算哈夫曼编码文件的压缩率
      在这里插入图片描述

    6. 将哈夫曼编码文件译码为文本文件,并与原文件进行比较。

    在这里插入图片描述

    读入的英文文本文件:

    在这里插入图片描述

    哈夫曼编码文件的译码文件:

    在这里插入图片描述
    在这里插入图片描述

    6.发现解码前和解码后一模一样

    别忘了点个关注

    展开全文
  • 该源码用于学习交流,给没有思路的同学提供一些思路,坚决抵制抄袭。源码用clion写的,如果用其他集成开发环境运行可能需要改一下txt文档的相对路径,到时自行百度。
  • 数据结构实验一,2013年~包含两次小实验
  • 哈尔滨工业大学2012级软件学院数据结构实验代码
  • C语言所写源代码有注释,哈工大数据结构实验课自己所作,仅供参考
  • 哈工大数据结构严蔚敏数据结构C语言PPT学习教案.pptx
  • 哈尔滨工业大学数据结构与算法2012年的期末考试试题以及答案,供备考的同学们使用。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,904
精华内容 3,961
关键字:

哈工大数据结构

数据结构 订阅