• 软件测试技术
  • 软件测试博客
  • 软件测试视频
  • 开源软件测试技术
  • 软件测试论坛
  • 软件测试沙龙
  • 软件测试资料下载
  • 软件测试杂志
  • 软件测试人才招聘
    暂时没有公告

字号: | 推荐给好友 上一篇 | 下一篇

程序员考试补课笔记-第十三天

发布: 2007-5-26 13:59 | 作者: 未知 | 来源: 互联网 | 查看: 22次 | 进入软件测试论坛讨论

领测软件测试网
  今天特别的兴奋,起床也起得特别的早。在走之前我把电脑开了,那当然是为了做服务器,我不知道我开学后能不能够这样做,因为家里的一些因素。不过只要能为大家服务我已经很开心了,而且也一种强激的幸福感,这种幸福并不是一般的家庭幸福。我为坚持做下去的,我也常常问一些网友关于这件事,他们都说只有你自己可以就行了,他们都支持我坚持做下去。好吧,说远了离题了,我说说今天的补课吧。

  今天的课程也令我吃了一惊,是讲数据结构里的树。为什么队列和堆栈都没有讲就直接讲树呢?会不会太快了一点,而且我们刚放完假有些人都没有集中精神到课堂来。不过我会相信老师的选择的,应该有他的理由。那么就来讲讲树的一些基本概念,大家都知道树是数据结构里的非线性结构之一,和之前说的链表是完全不同的,链表就只有前驱和后继结点,但树就不是了,他可以有很多的结点,称为分支结点,而且他的分支结点又可以有分支结点。因为树接触到的概念太多了,只好自己看一下书才行。树运用得很广范,像我们操作系统里文件管理就是了,多级的目录。二级目录就像树的子树,而且子树里可能还有很多的子树,越往下就越多级。

  我们来试试定义一个树的结构,一般树都分得很随意,所有我们这里也随便画一个树来说一下。看图第十三天图一我们看到圆圈就代表一个结点,而且最顶的那个就是根结点,往下的就是子结点。子结点的上一个就是父结点,同一级的结点左右都是为兄弟结点。我们按照这样的结构定义一个,如下:
  struct tree
  {
    int data;
    struct tree *next; /*右兄弟结点*/
    struct tree *pre; /*左兄弟结点*/
    struct tree *up; /*父结点*/
    struct tree *down; /*子结点*/
  };
下面来看看如何建立一棵树。
  struct tree *p,*r;
  r=(struct tree *)malloc(sizeof(struct tree)); /*建立根结点空间*/
  r->data=3; /*根结点赋值*/
  r->next=r->pre=r->up=NULL;
  p=(struct tree *)malloc(sizeof(struct tree)); /*建立第二个结点*/
  r->down=p; /*根结点的子结点连向新的子结点*/
  p->data=5; /*子结点赋值*/ 
  p->pre=NULL;
  p->next=(struct tree *)malloc(sizeof(struct tree));
  p->next->data=2;
  p->next->pre=p;
     :
     :
     :
  因为结点多而无规律性,所有这种建立方法是不能采用的,现在只是拿出来研究一下一棵树是如何建立起来的。

  现在说说另一种树“二叉树”。因为二叉树与一般的树结构比较,二叉树在结构上更规范和更有确定性,因此,应用也比树更为广泛。二叉树与树不同,首先二叉树可以为空,空的二叉树没有结点;另外,在二叉树中,结点的子树是有序的,分左、右两棵子二叉树。
二叉树又是如何建立的呢?这里很简单,因为二叉树有其规律性,下面请看
  typedef struct bnode
  {
    int data;
    struct bnode *left,*right;
  }btree;

  void creat(btree *b)
  {
    int x;
    btree *s;
    b=NULL;
  do
  {
    scanf("%d",&x);
    s=(btree *)malloc(sizeof(btree));
    s->data=x;
    s->left=s->right=NULL;
    insert(b,s);
  }
}

  void insert(btree *b,btree *s)
  {
    if(b==NULL) b=s;
    else if(s-data==b->data) return();
    else if(s-data<b->data) insert(b->left,s);
    else if(s-data>b->data) insert(b->right,s);
  }
  这条程序不单只建立了一个树,而且还给排好了序(左小右大)。输入相应的数值看看结果,如图第十三天图二。
  今天也就是这些了,还有得就是要多看些递归的程序,因为树的建立和操作离不开递归。还有的就是大家做做如下一题,就是已知有一个无序的二叉树,让我们用中序遍历排列成由大到小的程序。大家一齐起吧,写好发答案到我的论坛上http://zhgpa.vicp.net或者E-mail:zhgpa@sohu.com多谢大家支持。


延伸阅读

文章来源于领测软件测试网 https://www.ltesting.net/


关于领测软件测试网 | 领测软件测试网合作伙伴 | 广告服务 | 投稿指南 | 联系我们 | 网站地图 | 友情链接
版权所有(C) 2003-2010 TestAge(领测软件测试网)|领测国际科技(北京)有限公司|软件测试工程师培训网 All Rights Reserved
北京市海淀区中关村南大街9号北京理工科技大厦1402室 京ICP备2023014753号-2
技术支持和业务联系:info@testage.com.cn 电话:010-51297073

软件测试 | 领测国际ISTQBISTQB官网TMMiTMMi认证国际软件测试工程师认证领测软件测试网