`
junjie314
  • 浏览: 60246 次
  • 性别: Icon_minigender_1
  • 来自: 宁波
文章分类
社区版块
存档分类
最新评论

程序员数据结构笔记(三)

阅读更多
想想下面这个算法:求链表所有数据的平均值(我也没试过),不许偷懒,用递归试试哦!
  递归程序员考试题目类型:1)就是链表的某些操作(比如上面的求平均值)
              2)二叉树(遍历等) 
  例2.判断数组元素是否递增
     int jidge(int a[],int n) {
      if(n==1) return 1;
      else
       if(a[0]>a[1]) return 0;
       else return jidge(a+1,n-1);
     }
  例3.求二叉树的高度(根据二叉树的递归性质:(左子树)根(右子树))
     int depth(nodetype *root) {
      if(root==NULL) 
       return 0;
      else {
       h1=depth(root->lch);
       h2=depth(root->rch);
       return max(h1,h2)+1;
      }
      }
  自己想想求二叉树结点个数(与上例类似)
  例4.已知中序遍历和后序遍历,求二叉树.
   设一二叉树的:
   中序 S:E D F B A G J H C I
      ^start1 ^j ^end1
   后序 T:E F D B J H G I C A
      ^start2 ^end2
    node *create(char *s,char *t, int start1,int start2,int end1,int end2) 
    { if (start1>end1) return NULL; //回归条件
     root=(node *)malloc(sizeof(node));
     root->data=t[end2];
     找到S中T[end2]的位置为 j
     root->lch=create(S,T,s1,j-1,start1,j+start2-start1-1);
     root->rch=create(S,T,j+1,end1,j+start2-start1,end2-1);
     return root;
    }
  例5.组合问题
   n 个数: (1,2,3,4,…n)求从中取r个数的所有组合.
   设n=5,r=3;
   递归思想:先固定一位 5 (从另四个数当中选二个)
              5,4 (从另三个数当中选一个)
              5,4,3 (从另二个数当中选零个)
   即:n-2个数中取r-2个数的所有组合
     …
  程序:
   void combire(int n,int r) {
    for(k=n;k>=n+r-1;k--) {
     a[r]=k;
     if(r==0) 打印a数组(表示找到一个解);
     else combire(n-1,r-1);
    }
   }
回溯法:
  回溯跟递归都是程序员考试里常出现的问题,大家必须掌握!
  回溯法的有关概念:
  1) 解答树:叶子结点可能是解,对结点进行后序遍历.
  2) 搜索与回溯
  五个数中任选三个的解答树(解肯定有三层,至叶子结点): 
               ROOT 虚根
        /      /    |    
        1      2     3  4   5
    /  |  |    / |     /  |
    2  3  4  5 3 4 5  4 5  5
   /|  / |  / | |
   3 4 5 4 5 5 4 5 5 5
  回溯算法实现中的技巧:栈
  要搞清回溯算法,先举一个(中序遍历二叉树的非递归算法)来说明栈在非递归中所起的作用。
      A 过程:push()->push()->push()->push()栈内结果:ABDE(E为叶子,结束进栈)
     /    pop()   ABD(E无右孩子,出栈)
     B  C   pop()   AB(D无右孩子,出栈) 
    /     pop()   A(B有右孩子,右孩子进栈)
    D F     .      .
   / /     .      .
   E G H    .      .
  /        .      .
  I        最后结果: EDBGFIHAC
  简单算法:
    …
   if(r!=NULL) //树不空
   { while(r!=NULL) 
    { push(s,r);
     r=r->lch;   //一直向左孩子前进
    }
    while(!empty(s)) // 栈非空,出栈
    { p=pop(s);
     printf(p->data);
     p=p->rch;   //向右孩子前进
     while(p!=NULL)
     { push(s,p);
      p=p->lch; //右孩子进栈
     }
    } 
   } //这就是传说中的回溯,嘻嘻……没吓着你吧
5选3问题算法:
  思想: 进栈:搜索
  出栈:回溯
  边建树(进栈)边遍历(出栈)
  基本流程: 
  太复杂了,再说我不太喜欢用WORD画图(有损形象),以后再整理!
  程序: n=5;r=3
     ……
     init(s)  //初始化栈
     push(s,1) //根进栈
     while(s.top<r-1)&&(s.data[s.top]!=n) //有孩子
      push(s,s.data[s.top]+1); //孩子入栈
     while(!empty(s))
     { if(s.top=r-1)
      判断该"解"是否为解.
      x=pop(s); //保留x,判断是否为最大值n,如果是n,则出栈
      while(x==n)
      x=pop(s);
      push(s,x+1);
      while(s.top<r-1)&&(s.data[s.top]!=n)
      push(s,s.data[s.top]+1);
     }
  背包问题: TW=20 , w[5]={6,10,7,5,8} 
  解的条件:1) 该解答树的叶子结点
  2) 重量最大
  解答树如下:   ROOT
       / | | | 
          6 10   7   5  8
        / | |   / |   /  | 
        10 7 5 8 7 5 8 5  8 8
         | |      | 
         5 8      8
分享到:
评论

相关推荐

    程序员数据结构笔记

    在程序员数据结构的学习中,以下几个关键知识点不容忽视: 1. **数据结构的基本概念**:数据结构指的是数据的组织方式,它定义了数据之间的关系以及操作这些数据的方法。在学习数据结构时,我们需要理解对象的定义...

    程序员数据结构笔记 程序员数据结构笔记

    本篇笔记主要涵盖数据结构的基本概念、线性结构、树形结构、集合与排序,以及与数组相关的算法。 1. **数据结构的定义**: 数据结构是指一组数据的存储结构,包括数据对象、数据关系和对数据的操作。数据结构的选择...

    程序员数据结构笔记 知识 能力 过程

    程序员在面对纷繁复杂的编程挑战时,数据结构的知识和能力是他们手中最锋利的武器。数据结构不仅是计算机科学的基石,更是程序员高效编程的保障。在深入理解数据结构的过程中,程序员需要关注知识的掌握、能力的提升...

    程序员数据结构笔记.doc

    总的来说,程序员数据结构笔记涵盖了数据结构的基本概念、常见数据结构的操作及其时间复杂度分析,同时提供了具体的编程实例,帮助程序员理解和应用数据结构。掌握这些知识对于提升编程能力,特别是解决复杂问题的...

    程序员 数据 结构 笔记

    程序员在日常工作中,无论是开发系统软件、应用程序还是处理大数据,都需要掌握数据结构的相关知识。 首先,我们要理解数据结构中的“对象”指的是在计算机中表示的数据单元,它们可以是基本类型如整数、字符,也...

    程序员数据结构笔记很好很强大!

    程序员在日常工作中,无论是开发系统软件、应用软件还是进行数据分析,都会频繁地与各种数据结构打交道。下面我们将深入探讨数据结构的一些核心知识点。 首先,数据结构中的对象定义指的是数据的组织形式,它可以是...

    软考程序员数据结构笔记.doc

    在软考程序员的准备过程中,理解并掌握数据结构是必不可少的。以下是一些关于数据结构的关键知识点: 1. **数据结构的定义**:数据结构指的是数据的逻辑结构、存储结构以及在其上定义的操作的集合。它可以是简单的...

    黑马程序员Javase笔记

    在集合框架部分,Java提供了多种数据结构,如ArrayList、LinkedList、HashSet、TreeSet等。这些集合允许我们高效地存储和操作数据。并发修改异常(ConcurrentModificationException)通常发生在迭代集合时尝试修改...

    程序员数据结构学习笔记

    数据结构是计算机科学中至关...总之,数据结构的学习涵盖了各种抽象数据类型及其操作,理解和熟练掌握这些知识对于程序员来说至关重要,无论是在学术研究还是实际开发中,都能帮助我们设计出更高效、更优雅的解决方案。

    数据结构笔记

    这篇“数据结构笔记”可能包含了关于这个主题的深入理解和实践应用。结合给出的标签“源码”和“工具”,我们可以推测这份文档不仅讨论了理论知识,可能还涉及到了实际编程实现和相关工具的使用。 在数据结构的学习...

    程序员面试宝典笔记总结

    1. **数据结构**:线性结构(数组、链表、队列、栈),树结构(二叉树、AVL树、红黑树),图结构,哈希表等,理解它们的特性及操作。 2. **算法**:排序(快速排序、归并排序、堆排序)、查找(二分查找、哈希查找...

    程序员考试补课笔记(doc格式)

    在程序员考试中,指针相关的知识点无疑是非常重要的,尤其是在数组、字符串以及数据结构等方面的应用。 第二天的补课内容主要集中在数据类型的复习上,包括整型、字符型和浮点型等。作者通过数据类型表格对这些基础...

    程序员考试补课笔记,程序员考试补课笔记

    - 数据结构:数组、链表、栈、队列、树(二叉树、平衡树)、图等,以及它们的操作和应用。 - 算法:排序(冒泡、选择、插入、快速、归并)、搜索(线性、二分、深度优先、广度优先)等基本算法的理解与实现。 2. ...

    程序员面试宝典(C/C++&数据结构&网络&数据库&操作系统)

    程序员面试宝典(C/C++&数据结构&网络&数据库&操作系统)

Global site tag (gtag.js) - Google Analytics