博文

求二叉树深度的算法(2011-04-17 11:22:00)

摘要:题目:二叉树用二叉链表表示,编写求二叉树深度的算法。
答案是:
int height(Bitree T)
{
  if (T==NULL) return 0;
  u=height(T->lchild);
  v=height(T->rchild);
   if (u>n) return (u+1)
  return (v+1)
}

关于递归,你可以看成是一句一句往下运行嘛。需要保存状态的时候,系统就会自动用栈帮你保存。就依你说得那个为例: n为全局变量,初值为0; 第一次调用height(T),假设T!=NULL 由于T!=NULL:跳过if (T==NULL) return 0; 关键到了u=height(T->lchild); 调用本身的函数:此时的T->lchild保存在栈中,既然是调用就得从函数开头执行: 看下这时候T2(其实就是T->lchild),if (T==NULL) return 0; 这里假设T不是NULL,就继续运行在遇到u=height(T->lchild); 在调这个函数本身—— 这里就假设它为T->lchild==NULL吧。这下可好,这个函数执行return 0; 慢着:第二次函数调用u=height(T->lchild)中的函数值已经计算出来啦。这时u=0; 你还记得第二次调用运行到了v=height(T->rchild); 这句话吧?好,这个过程就和u=height(T->lchild)完全一样。 这里也假设得到的v=0 则第二次调用到了if (u>n) return (u+1) return (v+1) 得到一个返回值,不如就假设u〉n,于是返回值1; 好,这一波完毕; 你还记得第一次调用的height吧,这时把返回值给u,u=1; 然后执行到第一次调用中的v=height(T->rchild); 了。分析同上。 这个过程的确比较复杂。慢慢琢磨吧。呵呵。 基本思路就......

阅读全文(6607) | 评论:2 | 复制链接

图的遍历(深度优先算法)(C语言程序)(2011-04-17 10:53:00)

摘要:图的遍历(深度优先算法)(C语言程序) 图的遍历是指按某条搜索路径访问图中每个结点,使得每个结点均被访问一次,而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法,最近阿杰做了关于图的遍历的算法,下面是图的遍历深度优先的算法(C语言程序):
#include<stdio.h>
#include<malloc.h>
#define MaxVertexNum 5
#define m 5
#define TRUE 1
#define NULL 0 typedef   struct   node
{
 int  adjvex;
 struct  node  *next;
}JD; typedef   struct  EdgeNode
{
 int   vexdata;
    JD  *firstarc;
}TD; typedef struct
{
 TD  ag[m];
 int n;
}ALGRAPH; void DFS(ALGRAPH *G,int i)
{
 JD *p;
 int visited[80];
 printf("visit vertex:%d->",G->ag[i].vexdata);
 visited[i]=1;
 p=G->ag[i].firstarc;
 while(p)
 {
  if (!visited[p->adjvex])
   DFS(G,p->......

阅读全文(5971) | 评论:1 | 复制链接

排序思想总结(2010-09-30 15:46:00)

摘要:花了很长时间终于把排序的基础学了一下,这段时间学了很多东西,总结一下:
学的排序算法有:插入排序,合并排序,冒泡排序,选择排序,希尔排序, 堆排序,快速排序,计数排序,基数排序,桶排序(没有实现)。比较一下学习后的心得。
我不是很清楚他们的时间复杂度,也真的不知道他们到底谁快谁 慢,因为书上的推导我确实只是小小了解,并没有消化。也没有完全理解他们的精髓,所以又什么错误的还需要高手指点。呵呵。
1.普及一下排序稳定, 所谓排序稳定就是指:如果两个数相同,对他们进行的排序结果为他们的相对顺序不变。例如A={1,2,1,2,1}这里排序之后是A = {1,1,1,2,2} 稳定就是排序后第一个1就是排序前的第一个1,第二个1就是排序前第二个1,第三个1就是排序前的第三个1。同理2也是一样。这里用颜色标明了。不稳定呢 就是他们的顺序不应和开始顺序一致。也就是可能会是A={1,1,1,2,2}这样的结果。
2. 普及一下原地排序:原地排序就是指不申请多余的空间来进行的排序,就是在原来的排序数据中比较和交换的排序。例如快速排序,堆排序等都是原地排序,合并排 序,计数排序等不是原地排序。
3.感觉谁最好,在我的印象中快速排序是最好的,时间复杂度:n*log(n),不稳定排序。原地排序。他的名字很 棒,快速嘛。当然快了。我觉得他的思想很不错,分治,而且还是原地排序,省去和很多的空间浪费。速度也是很快的,n*log(n)。但是有一个软肋就是如 果已经是排好的情况下时间复杂度就是n*n,不过在加入随机的情况下这种情况也......

阅读全文(1536) | 评论:1 | 复制链接

合并排序算法(2010-09-30 15:18:00)

摘要:合并排序在有些资料或书籍中又叫归并排序。合并排序算法的基本过程如下: 分解:把待排序的n个元素分解成两组,每组n/2个元素。如果n为奇数则一组(n – 1)/2个元素,另一组1 + (n – 1) / 2 ;
排序:用合并排序法递归的对上一步分解成的两个组进行排序;
合并:把上一步排序好的两组合并在一起。

第一次接触此排序算法时重点要理解上述过程的第二步,这里面存在一个递归思想。如果您对递归还不熟悉的话,请先学习递归的基本概念,然后再来看本算法。 假定有一组待排序整数:[7,3,2,6] 现在我们用合并排序来对这4个数进行模拟排序,让大家对该排序算法有一个更加直观的认识。 第1步,把原数组分解成两组:[7,3] [2,6] 第2步,用合并排序对前一步分解出来的两组进行排序,这一步又分为如下几步: 首先对[7,3]这一组再次利用合并排序算法: 第2.1步,把[7,3]分解成两组[7] [3] 第2.2步,在上一步分解出来的两步都只有一个元素,所以每一组都是已经排好序了的。因此我们不需要再次利用合并排序算法分别对这两组排序。 第2.3步,合并[7] [3]这两组得到结果[3, 7] 然后对[2,6]这一组再次利用合并排序算法: 第2.4步,把[2,6]分解成两组[2] [6] 第2.5步,在上一步分解出来的两步都只有一个元素,所以每一组都是已经排好序了的。因此我们不需要再次利用合并排序算法分别对这两组排序。 第2.6步,合并[2] [6]这两组得到结果[2, 6] 第3步,对已排序要的[3,7] [2,6]合并在一起形成[2,3,6,7] 如果上面这些文字说明还不够清晰,那么请看下面用c语言实现的合并排序算法,代码最能说明问题了^_^ void merge_sort(int a[], int p, int r)
{
if(p < r) {
int q = (p + r) / 2; //分解成两组
merge_sort(a, p, q); //递归的对前一组排序
merge_sort(a, q + 1, r); //递归的对后一组排序
merge(a, p, q, r); //合并结果
......

阅读全文(4165) | 评论:3 | 复制链接

链表的几个思考题(2010-03-24 22:00:00)

摘要:链表若干
1.怎么判断链表中是否有环?
(附:怎么快速检测出一个巨大的链表中的死链?) 2.给你一个单向循环链表,怎么找出这个链表循环部分的第一个节点? 3.链表逆序? 4.一个单向链表,不知道头节点,一个指针指向其中的一个节点,问如何删除这个指针指向的节点? 5.给定一个链表的头指针,在一次遍历中,找出这个链表中的中间节点并返回。 6.查找链表中倒数第k个节点(只允许遍历链表一次) 7.编写实现链表排序的一种算法 8.找两个链表的第一个公共节点 9 判断两个链表是否相交 ----------------------------
有几个脑壳瓜子都想破都没想一丁点头绪。。。。看来智力还是颇为有限。。。。。 1.怎么判断链表中是否有环?
(附:怎么快速检测出一个巨大的链表中的死链?)
两个指针
一个步长为1,一个步长为2,同时移动。判断其是否相等。
如果数据量巨大的话,http://topic.csdn.net/t/20040906/09/3343269.html 2.给你一个单向循环链表,怎么找出这个链表循环部分的第一个节点?
跟第一个略有不同。第一个只是判断是否有环,而这个是要找出第一个节点。
标记法不错。hash也可以,貌似 3.链表逆序?
略 4.一个单向链表,不知道头节点,一个指针指向其中的一个节点,问如何删除这个指针指向的节点?
把next节点的key区域复制到本节点,然后删除next节点 5.给定一个链表的头指针,在一次遍历中,找出这个链表中的中间节点并返回。
和1类似 6.查找链表中倒数第k个节点
两个指针,保持距离k 7.编写实现链表排序的一种算法
感觉,插入排序最直接。快排也行,要复杂些,貌似。 8.找两个链表的第一个公共节点
如果有公共节点,那么该节点后面的节点全部都是两链表公共部分。 9 判断两个链表是否相交 如果相交 从相交处开始 到最后一个节点必定重复 所以可以先遍历第一链表到最后个节点 然后再遍历第二个链表取得最后个节点 比较判断是不是相等 即可......

阅读全文(2014) | 评论:1 | 复制链接

什么叫二叉树前序遍历,中序遍历,后序遍历?(2010-03-24 16:30:00)

摘要:设2叉树,根结点是A,叶结点左B右C
前序:A->B->C
http://baike.baidu.com/view/1455146.htm
中序:B->A->C
http://baike.baidu.com/view/1455143.htm
后序:B->C->A


复杂的二叉树按照这个规律进行。

欢迎访问我的论坛:)
http://www.chinesebloger.com
期待您的支持:)   树是一种数据结构,二叉树是树的一种。他的结构是,根,左儿子,右儿子。。

前序,中序和后序是树遍历的三种不同形式
前序遍历,也叫先根遍历,遍历的顺序是,根,左子树,右子树
中序遍历,也叫中跟遍历,顺序是 左子树,根,右子树
后序遍历,也叫后跟遍历,遍历顺序,左子树,右子树,根......

阅读全文(3391) | 评论:2 | 复制链接

【原创】两个有序数组相关的算法(2010-03-17 23:09:00)

摘要:1、将两个有序数组合并为一个有序数组 int[] MergeArray(int[] arrayX, int[] arrayY)
{
    int arrayXCount = arrayX.Count;
    int arrayYCount = arrayY.Count;
    int totalCount = arrayXCount + arrayYCount;
    int[] mergedArray = new int[totalCount];
    int i=0,j=0;
    while((i!=arrayXCount)&&(j!=arrayYCount))
    {
        if(arrayX[i] <= arrayY[j])
        {
            mergedArray[i+j] = arrayX[i];
            i++;               
        }
        else
        {
   &nbs......

阅读全文(5654) | 评论:5 | 复制链接

数据结构学习感悟(2005-08-12 17:15:00)

摘要:    在上个学期学校里学习数据结构的时候,几乎没有用很大的心思。总是觉得这东西其实很简单,就像老师上课的时候那样的随意,自己上课听懂了,理解了,一定不会再有什么大的问题了。
    于是我去ACM上面做了一道题目,错误百出,这次发现自己许许多多的C地知识仍然很不足。我们学校那些ACM老鸟很认真的告诉我说,我的编程能力都还没有过关。我听了很受打击“我都快是一个大三的学生了阿。
    再回过头去看我的数据结构书,是啊,都懂,可是,你让我真正地去编写一个程序,,,结果是可想而知的吧。要知道,我其实基本的编程功底都差得很呢!
    我便下定决心,暑假里面要把数据结构补上来,正好又可以锻炼自己的编程功夫!
    一晃,暑假已经大半去了,我觉得自己在数据结构方面还是很薄弱,但是勿庸置疑,我现在的水平比起放假前是要好了很多。只是又觉得这门课程的学习太辛苦了,没有人带我,有时候难免会觉得很枯燥的,碰到不懂得东西,在这个论坛上进行讨论是我学习最大的乐趣了!!但是我又怎么可以放弃呢?我无时无刻不想到我的理想。虽然在成长的道路上面我遇到过许许多多的意想不到的挫折,经历了无数的人情世故。但是,理想,永远拥有着她的一片美丽的净土,在我的心中,她是那样神圣,没有什么东西可以阻挡我的前进。
    未来就在不远的地方。。。。。。
    我会继续我的奋斗,从C语言开始,从数据结构开始。无论我的未来会怎样,我都不会对于理想的光辉视而不见!我坚信!孜孜不倦的追求,是一种幸福,是一种心灵的升华!
......

阅读全文(4676) | 评论:5 | 复制链接