2020年12月24日

10年初搭建的原始的AOSP工程。不知道官网现在还能不能下载到。从内核到开发调试工具的所有东西都可以编译出来,包括:内核、虚拟机、Framework、Java应用、手机模拟器、log工具、调试工具、开发用的Eclipse插件、SDK、、NDK等。
链接:
https://gitee.com/zhulf753/repo/tree/master/Android/Ubuntu10.04
Drop here!
posted @ 2020-12-24 12:34 zlf 阅读(303) | 评论 (0)编辑 收藏

2018年6月23日

     摘要: 经过别人在板子上几天几夜的测试,跑了6、7个任务同时开了4、5个中断,CPU满负荷。完全没问题,已经用在产品上。主要就修改一个文件os_cpu_a.asm和任务创建时堆栈初始化代码。花了两天时间(以前没接触过cortex-m0也没写过汇编,多年没接触过单片机了)。以下是os_cpu_a.asm。有不少的草稿代码,应该不影响阅读的,请自行忽略。;***************************...  阅读全文
posted @ 2018-06-23 10:41 zlf 阅读(924) | 评论 (0)编辑 收藏

2016年11月1日

     摘要: 相关标准描述参考网站:http://www.fourcc.org/ 参考解析工具和图片参考网站:http://www.sunrayimage.com/examples.html 网上有很多解析YUV格式的工具,觉得还是sunrayimage的工具比较全还有示例图片。 只有代码,花半天时间折腾出来的。 Code highlighting produced by Actipro CodeHig...  阅读全文
posted @ 2016-11-01 18:01 zlf 阅读(1888) | 评论 (0)编辑 收藏

2008年1月11日

#include<iostream>
#include<deque>
#include <ctime>
using namespace std;
template<class _Ty, class _C = deque<_Ty> >
class zlfStack {
public:
 typedef unsigned _Ty;
 typedef _C::allocator_type allocator_type;
 typedef _C::value_type value_type;
 typedef _C::size_type size_type;
 typedef _C::iterator zlfIterator;
protected:
 _C c;
public:
inline
 const value_type& zlfTop2(){
  return *(c.end()-2);
 }
inline
 const value_type& zlfTop3(){
  return *(c.end()-3);
 }
inline
 void top_3(value_type& x,value_type& y,value_type& b)
 {
  b=*(c.end()-1);
  y=*(c.end()-2);
  x=*(c.end()-3);
 }
inline
void top_2(value_type& x,value_type& y)
{
 y=*(c.end()-2);
 x=*(c.end()-3);
}

 //zlfStack(){ }
 explicit zlfStack(const allocator_type& _Al = allocator_type())
  :c(_Al){}
 allocator_type get_allocator() const
 {return (c.get_allocator()); }
 bool empty() const
 {return (c.empty()); }
 size_type size() const
 {return (c.size()); }
 value_type& top()
 {return (c.back()); }
 const value_type& top() const
 {return (c.back()); }
 void push(const value_type& _X)
 {c.push_back(_X); }
inline
 void push_3(const value_type& x,const value_type& y,const value_type& b)
 {
  c.push_back(x);
  c.push_back(y);
  c.push_back(b);
 }
inline
 void pop()
 {c.pop_back(); }
 };///
enum{B0=0,B1=1,B2=2,B3=3};
int A(unsigned x,unsigned y)
{
 static count=0; 
 if (!x&&!y) {return ++count;return count;}
 if (x==0xffff) {count=0;return 0;}
 if (x) A(--x,y);
AB1: if(y) A(x,--y);
AB2:
  return count;
  
}
inline
void clear(){A(0xffff,0);}
zlfStack<unsigned> s;
inline
void push(unsigned x,unsigned y,unsigned b)
{
 s.push(x);
 s.push(y);
 s.push(b);
}
inline
void pop(unsigned& x,unsigned& y,unsigned& b)
{
 b=s.top();
 s.pop();
// y=s.top();
 s.pop();
// x=s.top();
 s.pop();
}


int main()
{
 unsigned x=1,y=1,b=1,c=0,z=0;
 unsigned temp=0;
 clock_t t1,t2;
 unsigned k=1;
 unsigned long sum1=0,sum2=0,time1=0,time2=0;

 cout<<"AAAA"<<endl;
 t1=clock();
 for (x=1;x<10;x++) {
  for (y=1;y<10;y++) { 
   clear();
   k=A(x,y);
   sum1+=k;
   cout<<k<<" ";
   cout<<"x="<<x<<" "<<"y="<<y<<endl;
  }
 }
 t2=clock();
 time1=t2-t1;
 cout<<endl;


 if (!x&&!y) return 0;//exit
 sum2 = 0;
 t1=clock();
 for (x=1;x<10;x++) { 
  for (y=1;y<10;y++) {// push(x,y,B3);
  s.push_3(x,y,B3);
  c=0;
  b=B0;
  while (!s.empty()) {
   switch(b) {
   case B0:if(x) {//push(--x,y,B1);
    s.push_3(--x,y,B1);
    b=B0;continue;}
   case B1:if(y) {//push(x,--y,B2);
    s.push_3(x,--y,B2);
    b=B0;continue;}
   case B2:if (!x&&!y) c++;
   default:;
   }//switch
  // pop(x,y,b);
   b=s.top();
   s.pop();
   s.pop(); 
   s.pop();
   if(b==B3) break;//return to main
  // pop(x,y,temp);
  // push(x,y,temp);
  // y=s.zlfTop2();
  // x=s.zlfTop3();
   s.top_2(x,y);
  }//while
  sum2+=c;
 // cout<<"c="<<c<<" "<<"x="<<x<<" "<<"y="<<y<<endl;
  }//y
 }//x
 t2=clock();
 time2=t2-t1;
 cout<<"time used :"<<time2<<"ms"<<endl;
 cout<<"routines :"<<sum2<<endl;
 cout<<endl<<endl;
 double t;
 cout<<"routines: "<<sum1<<"  time1: "<<time1<<endl;
 t=sum1/time1;
 cout<<t<<" rps"<<endl;
 cout<<"routines: "<<sum2<<"  time2: "<<time2<<endl;
 t=sum2/time2;
 cout<<t<<" rps"<<endl;
 return 0;
}

posted @ 2008-01-11 17:15 zlf 阅读(626) | 评论 (0)编辑 收藏

2008年1月10日

用http的get方法,构造要查询的url,get下来,分析结果页面即可
首先是构造url,以下是一些示例,主要看清楚?号后面的参数所代表的意思即可:
http://www.google.cn/search?num=100&&q=%E5%85%83%E6%90%9C%E7%B4%A2&start=10

http://www.baidu.com/s?wd=%D4%AA%CB%D1%CB%F7&rn=100&pn=10  //第二页pn

http://www.yahoo.cn/s?p=%E5%85%83%E6%90%9C%E7%B4%A2&b=10  //第二页b

http://search.yahoo.com/search?n=100&p=%E5%85%83%E6%90%9C%E7%B4%A2&b=101

http://cnweb.search.live.com/results.aspx?q=%E5%85%83%E6%90%9C%E7%B4%A2&first=51  //第二页first=51

http://p.zhongsou.com/p?w=%D4%AA%CB%D1%CB%F7&b=3  //b=3表示第三页

http://www.soso.com/q?w=%D4%AA%CB%D1%CB%F7&num=20&pg=1 //第一页,每页20个

第二步是解释搜索结果页面:

<meta http-equiv="content-type" content="text/html;charset=gb2312">

Google
搜索结果个数的字符串前缀:约有<b> //获取个数用字符串定位的方式
搜索结果开始的标签:<div id=res> //也可以用字符串定位的方式,要准确就用查找标签定位的方式
 各个搜索结果的开始标签:<div class=g> //字符串定位的方式
 
  搜索结果的url在第一个<a target=_blank class=l>标签里头
  搜索结果的标题在<a></a>的标签之间

  搜索结果的摘要在接下来的<table><tr><td>标签里头直到<b>...<b><br>
  搜索结果的重写的url在<b>...<b><br>之后的<span>标签里头,格式为:url,一个空格,网页大小
  搜索结果的网页快照在接下来的<a class=fl>的标签里头,属性中有url,标签之间有网页快照文字
  接下来还有类似网页等,都在<a class=fl>标签里头

 各个搜索结果的结束标签是</td></tr></table></div>

......................

相关搜索的开始标签:<p class=e>
在接下来的各个<a></a>标签之间的内容就是相关搜索的内容
直到标签<br clear=all>就可以结束了

 

Baidu
搜索结果个数的字符串前缀:<td align=\"righ,在定位该字符串后,直到</td>,即在这个td标签之内含有的字符串包含相关网页数和用时
搜索结果开始的标签:<DIV id=ScriptDiv></DIV>
 各个搜索结果的开始标签:<table

  搜索结果的url在第一个<a target=_blank class=l>标签里头
  搜索结果的标题在<a></a>的标签之间,以<br>标签结束
  
  搜索结果的摘要以<br>开始直到下一个<br>标签
  
  接下来的一行(<br>换行)的font标签中有搜索结果url的重写,一个空格,网页大小,网页时间
  在接下来会有一些<a>标签如百度快照,直到又一个<br>

 然后搜索结果的结束标签</table>

.........................

导航条的开始标签:<br clear=all>
导航条的内容在开始标签之后的<div class="p"></div>标签之间
相关搜索在接下来的<div>标签之间的各个<a>标签之内

其他考虑:对于字符串的匹配可以利用kmp,注意到匹配搜索结果各部分的时候所用到的模式字符串的最大前缀字符串最多是一个字符,这样可以避免求取最大前缀字符串从而提高效率;如果要精确地匹配还需要弄两个函数,一个用来构造标签,一个用来读取标签之间的文本。

posted @ 2008-01-10 20:50 zlf 阅读(1858) | 评论 (1)编辑 收藏

2007年10月8日

序列化探讨

主要就是解释readobject和writeobject函数,应该够了,至于在DOC/VIEW模型种使用的话,应该很简单的


0---
空指针   7FFF---大索引号标志,即后面的索引号是32位的

0X8000---保留以后使用   0XFFFF---新类的定义

小索引对象或者类的索引号:1~~~7FFE,但是类的最高位是1

对象的插入:writeobject函数:(全局插入<<函数只是调用了这个函数)首先插入类信息,然后是对象信息。每次写入(即一次writeobject函数的执行流程)是下面三种的之一:

1           若是未写过的类并且未被写过的对象:

1.1 写入新类标志:0XFFFF       *this << wNewClassTag;

1.2 写入类的版本号,写入类名的字符串长度:ar << (WORD)m_wSchema << nLen;

1.3 写入类名 ar.Write(m_lpszClassName, nLen*sizeof(char));

1.4 写入对象              ((CObject*)pOb)->Serialize(*this);

2           若是曾经写过的类并且未写过的对象:

2.1 写入类的索引号 nClassIndex = (DWORD)(*m_pStoreMap)[(void*)pClassRef]

如果是小索引类:则写入类*this << (WORD)(wClassTag | nClassIndex);

 如果是大索引类:则写入大索引号标志(7FFF)和32位的类索引号(最高位是1                     *this << wBigObjectTag;

                     *this << (dwBigClassTag | nClassIndex);

2.2   写入对象              ((CObject*)pOb)->Serialize(*this);

3           若是曾经写过的类并且曾经写过的对象:

3.1 写入对象的索引号

        如果是小索引对象:则直接写入索引号*this << (WORD)nObIndex;

        如果是大索引对象:则写入大索引号标志和32位的对象索引号(最高位是0

                     *this << wBigObjectTag;

                     *this << nObIndex;

以上3种情况的写入都是首先写入一个字,这个字的内容就代表了之后字节即类信息的意义或者可以只是一个对象的索引号(情况三),即是新类(字节为0xFFFF)还是已经定过的小索引类(索引号从0x8001—0xFFFE)又或者是已经定义过的大索引类以(字节0x7FFF后续两个字节为索引号)

 

对于读取上面文件格式的信息并且区分出将要读取的是类还是对象,是索引还是对象数据,在readObject

首先读取一个字如果0XFFFF则显然对应的是第一种情况,此时可以容易地读取数据;如果第一个字的最高位是1的话,很显然此时对应的就是第二种情况,即该字是一个类的索引号,而且是小索引类;如果0x7FFF则此时对应的就是第三种情况大索引号对象或者第二种情况大索引号类;如果最高位不是1则此时对应的也是第三种情况但是小索引对象;在区分了第一个字以后就可以容易地读取后面的数据。这样每次的readObject函数的调用都只是提取以往某次writeObject函数写入的数据。

 

对象的提取:ReadObject函数,因为在宏IMPLEMENT_SERIAL里定义的提取操作符只是简单地调用了这个函数。首先提取类信息,以便正确地动态生成对象,然后是对象信息。

PS:m_pStoreMap里即包含了已经序列化的类(CRuntimeClass)和对象的指针。

 

UINT CArchive::GetObjectSchema()函数只能调用一次,一般该函数在某个类(ar正在序列化的类)的Serialize函数里头调用,它返回读取的类的版本号。以下几行来自readObject:

              UINT nSchemaSave = m_nObjectSchema;

              m_nObjectSchema = nSchema;

              pOb->Serialize(*this);

              m_nObjectSchema = nSchemaSave;

一般地,也正是在serialize里头来处理各种版本的序列化。

FAQ:

1. 为什么可以定义全局的插入操作符,而提取操作符却要对每个类在宏里头声明?

插入操作的是在已知对象所有信息的情况下的操作,包括对象的类型和状态,类信息的写入使用CruntimeClass非静态成员函数Store来实现的,而GetCRuntime成员函数又是虚函数所以可以用指向COBJECT的指针来正确地获取,然后正确地调用STORE函数;而对于提取操作,将要提取出的对象的类型和状态都是未知,提取类信息主要是用CruntimeClass静态成员LOAD来获取,该成员获得文件中类信息之后通过查找全局的类型链表可以唯一地确定一个CrutimeClass类型的静态对象,通过该对象的createObject函数可以构造出即将提取的对象类型,然后利用动态构造的对象的序列化函数就可以正确地提取出对象,因为

11       在宏定义的提取操作符中classname参数是无法用COBJECT类来替换,因为如果替换的话则在提取信息过程中即使出现错误,比如说提取出的类型根本就不是可序列化的但是如果继承自COBJECT的话仍然可以通过错误检查。

posted @ 2007-10-08 11:00 zlf 阅读(1605) | 评论 (1)编辑 收藏

2007年10月5日

#include <math.h>
#include <vector>
using namespace std;
#define max(a,b)  ((a)>(b)?(a):(b))
template<typename E>
class AVL_TMP

 template <typename E>
 class AVL_NODE
 {
 public:
  AVL_NODE():ln(0),rn(0),depth(0){}
  AVL_NODE( const E& e):data(e),ln(0),rn(0),depth(0){}
  ~AVL_NODE(){ if (ln) delete ln; if (rn) delete rn; }

  bool operator < (E& e){  return data < e; }
  bool operator > (E& e){  return data > e; }
  bool operator == (E& e){ return data == e; }
  bool operator != (E& e){ return data != e; }

  E getdata(){return data;}
  
  E data;
  int depth;
  AVL_NODE<E> *ln,*rn;
 };
 
public: 
 typedef E dataType;
 typedef AVL_TMP<E> Myt;
 typedef AVL_NODE<E> n;
 typedef n* npos;
 typedef npos iterator;
 enum unbalanceType {LL,RR,LR,RL};
 AVL_TMP():root(0),size(0),depth(-1){}
 ~AVL_TMP(){ if(root) delete root; }

 iterator begin(){return root;}
 bool insert(const E& e);
 npos find(const E& e);
 npos findpre(const E& e);
 bool del(dataType);
 bool balance(AVL_TMP<E>::iterator pos){
  if(pos == NULL) throw 0;
  int lh,rh;
  if(pos->ln == NULL ) lh = -1;
  else lh = pos->ln->depth;
  if(pos->rn == NULL ) rh = -1;
  else rh = pos->rn->depth;
  return abs( lh - rh ) < 2 ;
 }
 virtual void frontOrder(){};
 virtual void midOrder(){ };

protected:
 void LLr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos);
 void LRr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos);
 void RRr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos);
 void RLr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos);
 void updateDepth(AVL_TMP<E>::iterator pos);
 bool delAux(E const& e,AVL_TMP<E>::iterator pos = NULL);
 iterator findMax(iterator );
 iterator findMin(iterator );
 bool upTree(int iDepth,iterator itRoot,unsigned long iSize){depth = iDepth;root = itRoot;size = iSize; return true;}
 bool upRoutineDepth(vector<iterator>&);
 bool adjust(iterator a,iterator b,iterator c,iterator prePos = NULL);
 npos root;
 int depth;
 unsigned long size;
};
template<typename E>
bool AVL_TMP<E>::adjust(iterator a,iterator b,iterator c,iterator prePos){
 bool b1,b2;
 b1 = b == a->ln;
 b2 = c == b->ln;
 unbalanceType ub;
 if(b1&&!b2)   ub = LR;
 if(!b1&&b2)   ub = RL;
 if(b1&&b2)    ub = LL;
 if(!b1&&!b2)  ub = RR;
 switch(ub) {
  case  LL :LLr(a,prePos);
   break;
  case  LR :LRr(a, prePos);
   break;
  case  RR :RRr(a,prePos);
   break;
  case  RL :RLr(a,prePos);
   break;
 }  //end switch
 return true;
}
template<typename E>
bool AVL_TMP<E>::upRoutineDepth(vector<iterator>&routine){
 //该函数主要是将路径节点的深度更新并且使得那些不平衡的节点平衡
 int size = routine.size();
 while (size--) {
  updateDepth(routine[size]);
  if (!balance(routine[size])) {//不平衡得调整
   iterator cur = routine[size],prePos = NULL;
   if(size-1>=0)
    prePos = routine[size-1];
   //检查当前不平衡节点的哪颗子树的高度更高
   bool bl = cur->ln != NULL;
   bool br = cur->rn != NULL;
   if (!bl) {//肯定有右孩子
    if(cur->rn->ln) RLr(cur,prePos);
    else RRr(cur,prePos);
   }
   else{//有左孩子
    if (!br) {//没右孩子
     if (cur->ln->ln) LLr(cur,prePos);
     else LRr(cur,prePos);
    }
    else{ //有右孩子,此时需要检查左右孩子的高度,则右子树高度至少为1
     //因此左子树高度至少为3,则左子树的节点个数肯定大于4
     if (cur->ln->depth > cur->rn->depth) LLr(cur,prePos);
     else RRr(cur,prePos);
    }
   }
  }
 }
 return true;
}
template<typename E>
AVL_TMP<E>::iterator AVL_TMP<E>::findMax(AVL_TMP<E>::iterator pos){//以pos为根的树的最大值的节点
 if (!pos) return NULL;
 iterator p = pos;
 while(p->rn) p = p->rn;
 return p;
}
template<typename E>
AVL_TMP<E>::iterator AVL_TMP<E>::findMin(AVL_TMP<E>::iterator pos){
 iterator p = pos;
 while (p->ln) p = p->ln;
 return p;
}
template<typename E>
void AVL_TMP<E>::updateDepth(AVL_TMP<E>::iterator pos){
 bool b1 = pos->ln == NULL,b2 = pos->rn ==NULL;
 switch(b1) {
 case true:
  if(b2) pos->depth = 0;
  else pos->depth = pos->rn->depth+1;
  break;
 default: //false
  if(b2)  pos->depth = pos->ln->depth+1;
  else pos->depth = max(pos->ln->depth , pos->rn->depth )+1;
 }
 if(pos == root) depth = pos->depth;
}
template<typename E>
void AVL_TMP<E>::LLr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos){
 typename AVL_TMP<E>::iterator t, a = pos, b = t = pos->ln ;
 pos->ln = t->rn;
 t->rn = pos;
 if(root == a) root = b;
 if(prePos != NULL)
  if(prePos->ln == a) prePos->ln = b;
  else prePos->rn =  b;
 updateDepth(a);updateDepth(b);
}
template<typename E>
void AVL_TMP<E>::LRr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos){
 AVL_TMP<E>::iterator a = pos,b = pos ->ln, c = b->rn;
 b->rn = c->ln ; a->ln = c->rn;
 c->ln = b;  c->rn =a;
 if(a == root ) root = c ;
 if(prePos != NULL)
  if(prePos->ln == a) prePos->ln = c;
  else prePos->rn =  c;
 updateDepth(a);updateDepth(b);updateDepth(c);
}
template<typename E>
void AVL_TMP<E>::RRr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos ){
 AVL_TMP<E>::iterator a = pos ,t, b = t = pos->rn ;
 pos->rn = t->ln;
 t->ln = pos;
 if(prePos != NULL)
  if(prePos->ln == a) prePos->ln = b;
  else prePos->rn =  b;
 if(root == a) root = b;
 updateDepth(a);updateDepth(b);
}
template<typename E>
void AVL_TMP<E>::RLr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos){
 AVL_TMP<E>::iterator a = pos, b = pos->rn , c = b->ln;
 a->rn = c->ln ;  b->ln = c->rn;
 c->ln = a; c->rn = b;
 if(prePos != NULL)
  if(prePos->ln == a) prePos->ln = c;
  else prePos->rn =  c;
 if( a == root) root = c;
 updateDepth(a);updateDepth(b);updateDepth(c);
}
template<typename E>
bool AVL_TMP<E>::insert(const E& e){
 if(root == NULL) {root = new AVL_NODE<E>(e); size++; depth = root->depth;return true;}
 bool bUpdateDepth = false;
 vector<AVL_TMP<E>::iterator> routin;
 typename AVL_TMP<E>::iterator p = root,pos,prePos;
 for (int i = 0 ; i < size ;i++ ) {
  routin.push_back(p);
  if(p->data > e){
   if ( p->ln == NULL ) {
    p->ln = pos = new AVL_NODE<E>(e);
    bUpdateDepth = p->rn == NULL;
    break;
   }
   else { p = p->ln ; continue;}
  }
  if(p->data  < e){
   if (p->rn == NULL) {
    p->rn = pos = new AVL_NODE<E>(e) ;
    bUpdateDepth = p->ln == NULL;
    break;
   }
   else {  p = p->rn ; continue;}
  }
  return false;   //already exists
 }  //insertion finished
 size++;
 if(size <= 2 ) {
  updateDepth(root);
  return true;
 }
 if(!bUpdateDepth) return true;   //balance
 
 bool unAdjusted = true;
 // check for balance and adjust depth
 for (i = routin.size()-1; i  >=0 ; i-- ) {
  if(!balance(routin.at(i)))
   if(unAdjusted) {  //  unbalance! get unbalance type
    if(i-1 >= 0) prePos = routin.at(i-1);
    else prePos = NULL;
    AVL_TMP<E>::iterator a = routin.at(i) , b = routin.at(i+1) , c;
    if(i+2 >= routin.size() ) c = pos;
    else c = routin.at(i+2);
    bool b1,b2;
    b1 = b == a->ln;
    b2 = c == b->ln;
    unbalanceType ub;
    if(b1&&!b2)   ub = LR;
    if(!b1&&b2)   ub = RL;
    if(b1&&b2)    ub = LL;
    if(!b1&&!b2)  ub = RR;

    switch(ub) {
     case  LL :LLr(routin.at(i),prePos);
      break;
     case  LR :LRr(routin.at(i),prePos);
      break;
     case  RR :RRr(routin.at(i),prePos);
      break;
     case  RL :RLr(routin.at(i),prePos);
      break;
    }  //end switch
    unAdjusted = false;
   }  //end if
 updateDepth(routin.at(i));  //update the depth of the node in the routin
 depth = root->depth;
 }//end for
 return true;
};
template<typename E>
AVL_TMP<E>::npos AVL_TMP<E>::find(const E& e){//search for position
   npos p=root;
   while (p&&p->data!=e)
    if(e>p->data) p=p->rn;
    else p= p->ln;
   return p;
}
template<typename E>
AVL_TMP<E>::npos AVL_TMP<E>::findpre(const E& e){//search for parent node position
   npos p,pre;
   p=pre=root;
   while (p&&p->data!=e) {
    pre = p;
    if (e>p->data) p=p->rn;
    else p = p->ln;
   }
   if(p) if(p->data==e) return NULL;//already existed
   return pre;
}
template<typename E>
bool AVL_TMP<E>::delAux(E const& e,AVL_TMP<E>::iterator pos){
 // 1.递归删除节点,直到删除的是叶子节点 
 // 2. 删除叶子节点,更新树的数据成员
 // 3. 更新路径上的节点深度并且检查平衡因子 
 static vector<iterator> routine;
 iterator p = pos;
 bool bUpdate = false;
 if(!pos){//第一次调用
  p = root;
  while (p&&e!=p->data) {//找到节点,并且将寻找路径存入表中
   routine.push_back(p);
   if(p->data > e) p = p->ln;
   else p = p->rn;
  }
  if(p == NULL){ //没找到
   routine.clear(); 
   return false;
  }
  else pos = p;
 }
 if (pos->ln||pos->rn) {//不是叶子节点,则该节点有孩子节点,可能是一个或者两个
  routine.push_back(pos);//还得往下删除
  if (pos->ln&&!pos->rn){ //情况一: 只有有左孩子
   //找到左子树中的最大值的位置
   iterator max = pos->ln;
   while (max->rn) { routine.push_back(max); max = max->rn;}
   bUpdate = false;
   //伪删除
   pos->data = max->data;
   delAux(max->data,max);
  }
  else if (!pos->ln&&pos->rn) { //情况二:只有右孩子
   //找到右子树中的最小值
   iterator min = pos->rn;
   while (min->ln) { routine.push_back(min); min = min->ln;}
   bUpdate = false;
   //伪删除
   pos->data = min->data;
   delAux(min->data,min);
  }
  else //情况三:有俩个孩子
  {
   //找到左子树中的最大值
   iterator max = pos->ln;
   while (max->rn) { routine.push_back(max); max = max->rn;}
   bUpdate = false;
   //伪删除
   pos->data = max->data;
   delAux(max->data,max);
  }
 }
 else
 {//是叶子节点
  //有三种情况,是其父节点的左子树且没有兄弟,是其父节点的右子树且没有兄弟,有兄弟
  //取得其父节点
  iterator parent = NULL;
  if (routine.size()) //有父节点
   parent = routine[routine.size()-1];
  else{//即该节点是根节点,无根节点
   delete root;
   routine.clear();
   upTree(-1,NULL,0);
   return true;
  }  //完成根节点的删除
  //有父节点
  if (pos == parent->ln&&!parent->rn) {//情况一:是父节点的左孩子且没兄弟
   //删除节点
   parent->ln = NULL;
   delete pos;
   //需要更新路径上的节点的深度
   bUpdate = true;
   upRoutineDepth(routine);
   upTree(root->depth,root,size-1);
   routine.clear();
   //改写父节点的孩子指针
  }//完成情况一叶子节点的删除
  else{
   if (pos == parent->rn && !parent->ln ) { //情况二:是父节点的右孩子且没兄弟
    parent->rn = NULL;
    delete pos; 
    bUpdate = true;
    upRoutineDepth(routine);
    upTree(root->depth,root,size-1);
    routine.clear();
   }//完成情况二叶子节点的删除
   else{//情况三:有兄弟
    //只需要将节点删除,并清理路径表就可以了
    if (pos == parent->ln) parent->ln = NULL;
    else parent->rn = NULL;
    delete pos;
    routine.clear();
   }//完成情况三的叶子节点删除
  }
 }
 return true;
}

template<typename E>
bool AVL_TMP<E>::del(dataType e){
 return delAux(e);
}

posted @ 2007-10-05 15:47 zlf 阅读(2570) | 评论 (2)编辑 收藏

2007年9月14日

#include <iostream.h>
#include<io.h>
const int QUENS = 7;
int getcol(int q[],int n,const int firstCol)
{//q表示每个皇后的列位置,firstCol是搜索列位置时的起始位置
//n表示正在搜索第n个皇后的列位置,皇后的名称从0--n编号,也是皇后的行号
 bool b = true;
 int i = firstCol;
 for (i = firstCol; i<=QUENS ; i++) {
  for (int j=0; j<n; j++) {
   if(q[j] == i || (n+q[j]==i+j)||(n+i == j+q[j])){
    b = false;
    break;
   }
  }
  if(j == n)
    return i;
  else if(firstCol > QUENS) return firstCol;
 }
 if(!b) return QUENS+1;
}
void EQ(int q[],int n){
 void disp(int[]);
 int col = QUENS+1;
 bool b = true;
 int firstCol = 0;
 while (QUENS >= (col=getcol(q,n,firstCol))){
  if(QUENS == n){
   q[n] = col;
   disp(q);
   return ;
  }
  else{
   q[n] = col;
   firstCol = col +1;
   EQ(q,n+1);
  }
 }
 
}
void disp(int q[])
{//显示一种排列
 static count = 0;
 count++;
 cout<<"number "<<count<<" : ";
 for (int i=0; i<=QUENS; i++)
  cout<<q[i]+1<<" ";
 cout<<endl;
}
void outTofile()
{//由于结果比较多,所以把结果重定向输出到文件里头了,文件名是EightQuen.txt
 int old = _dup(1);
 FILE* pf;
 pf = fopen("EightQuen.txt","w");
 if(!pf)  throw 0;
 _dup2((fileno(pf)),_fileno(stdout));
 int q[8];
 EQ(q,0);
fclose(pf);
 _dup2(old,_fileno(stdout));

}
void main()
{
outTofile();
}

posted @ 2007-09-14 14:41 zlf 阅读(587) | 评论 (0)编辑 收藏
仅列出标题  

导航

<2024年10月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

统计

常用链接

留言簿(1)

随笔档案

文章档案

搜索

最新评论

阅读排行榜

评论排行榜