博文

二叉树的遍历问题(2006-10-29 22:41:00)

摘要:问题:某二叉树后序遍序是DACBE ,中序遍历序列是DEBAC,它的前序遍历是? 相关概念解析:概念中的前中后序都代表的是根节点在访问中的次序,左先于右的顺序不变。前序概念是:TLR(根左右)先访问根,再访问左"子树",再访问右"子树".访问左 "子树"也是按照这样的原则在左"子树"中前序的访问. 中序概念是:LTR(左根右)
后序概是:LRT(左右根).类似是很好理解的.

求解过程:
1)由后序序列,知根在最后,所以,E是根
2)由E为根,中序序列,知道左"子树"是D(在左边),右"子树"是BAC.(在右边)
3)右"子树"BAC中,由后序序列知,B为根,所以AC为根B的右"子树".(在右边)
4)在右"子树"AC中,由后序序列知,C为根,A为其左子树(在左边啊)
树很容易就画出来了(你自己画吧,我怎么画啊呵呵).然后,对它进行前序遍历.

答案:得到的前序序列是:EDBCA
......

阅读全文(4832) | 评论:1

 冒泡排序学习笔记(2006-10-24 20:58:00)

摘要: 冒泡排序算法:
 void BubleSort(SqList &L)
 {
  bool exchange;
  for (int i=2; i<=n; i++)
  {
   exchange = false;
   for (int j=1; j<=n-i+1; j++)
   {
    if (L.r[j].key>L.r[j+1].key)
    {
     exchange = true;
     L.r[0] = L.r[j+1];
     L.r[j+1] = L.r[j];
     L.r[j] = L.r[0];
    }
   }
   if (!exchange)
   {
    return;
   }
  }
 }......

阅读全文(3187) | 评论:1

快速排序学习笔记(2006-10-24 20:34:00)

摘要:  分解算法:每趟运算确保比枢轴pivot小的值都在其左边,大的都在右边。 int Partition(SqList &L, int low, int high)
 {
  L.r[0] = L.r[low];//子表中的第一个记录作为枢轴记录
  int pivot = L.r[low].key;//枢轴记录的关键字值
  while (low < high)
  {
   while (low < high && L.r[high].key>pivot)
   {
    high--;
   }
   L.r[low].key = L.r[high].key;
   while (low < high && L.r[low].key<pivot)
   {
    low++;
   }
   L.r[high].key = L.r[low].key;
  }
  L.r[low] = L.r[0];
  return low;
 } 求解过程:递归调用分解函数的过程。  void QSort(SqList &L,int low,int high)
 { // 对顺序表L中的子序列L.r[low..high]作快速排序。算法10.7
   int pivotloc;
   if(low<high)
   { // 长度大于1
     pivotloc=Partition(L,low,high); // 将L.r[low..high]一分为二
   ......

阅读全文(3662) | 评论:0

2_路插入排序学习笔记(2006-10-23 23:06:00)

摘要: 代码:  void P2_InsertSort(SqList &L)
 { // 2_路插入排序
   int i,j,first,final;
   RedType *d;
   d=(RedType*)malloc(L.length*sizeof(RedType)); // 生成L.length个记录的临时空间
   d[0]=L.r[1]; // 设L的第1个记录为d中排好序的记录(在位置[0])
   first=final=0; // first、final分别指示d中排好序的记录的第1个和最后1个记录的位置
   for(i=2;i<=L.length;++i)
   { // 依次将L的第2个~最后1个记录插入d中
     if(L.r[i].key<d[first].key)
     { // 待插记录小于d中最小值,插到d[first]之前(不需移动d数组的元素)
       first=(first-1+L.length)%L.length; // 设d为循环向量
       d[first]=L.r[i];
     }
     else if(L.r[i].key>d[final].key)
     { // 待插记录大于d中最大值,插到d[final]之后(不需移动d数组的元素)
       final=final+1;
       d[final]=L.r[i];
  &nbs......

阅读全文(3460) | 评论:0

折半插入排序学习笔记(2006-10-23 22:51:00)

摘要:  程序: void BInsertSort(SqList &L)  { // 对顺序表L作折半插入排序。算法10.2    int i,j,m,low,high;    for(i=2;i<=L.length;++i)    {      L.r[0]=L.r[i]; // 将L.r[i]暂存到L.r[0]      low=1;      high=i-1;      while(low<=high)      { // 在r[low..high]中折半查找有序插入的位置        m=(low+high)/2; // 折半        if LT(L.r[0].key,L.r[m].key)          high=m-1; // 插入点在低半区        else          low=m+1; // 插入点在高半区      }      for(j=i-1;j>=high+1;--j)        L.r[j+1]=L.r[j]; // 记录后移      L.r[high+1]=L.r[0]; // 插入    }  } 总结:此方法和直接插入排序所需的辅助空间相同,从时间上比较,仅减少了关键字比较的次数,记录的移动次数不变。所......

阅读全文(3453) | 评论:1

直接插入排序学习笔记(2006-10-23 22:48:00)

摘要: 直接插入排序程序: void InsertSort(SqList &L)  { // 对顺序表L作直接插入排序。算法10.1    int i,j;    for(i=2;i<=L.length;++i)//哨兵在0,所以从2开始排序      if (L.r[i].key < L.r[i-1].key) // "<",需将L.r[i]插入有序子表,确保待插入数据小于之前的最后一个,否则就不需要排序,进行下一个      {        L.r[0]=L.r[i]; // 待插入的数据复制为哨兵        for(j=i-1; L.r[0].key < L.r[j].key;--j)// 将每个数据和哨兵从右向左进行比较,直到哨兵大于该比较值          L.r[j+1]=L.r[j]; // 记录后移        L.r[j+1]=L.r[0]; // 插入到正确位置      }  } 总结:时间复杂度O(n2),空间复杂度O(1)。 思想:L.r[0]用于存储待插入的数据,即哨兵。先将第一个数据看成有序的序列,故从第二个开始开始比较,共需要n-1趟。需将L.r[i]插入有序子表,确保待插入数据小于之前的最后一个,即有序子序列的最后一个。否则就不需要排序,因为改数已经大于最后一个,则为子序列的最大值,应该放于最后。进行此趟排序前,先将i拷入哨兵,之后将每个数据和哨兵从右向左进行比较,若小于该值则将其后移,否则将哨兵拷入该位置即可,本趟排序结束。......

阅读全文(2578) | 评论:0