A PHP Error was encountered

Severity: 8192

Message: Function create_function() is deprecated

Filename: geshi/geshi.php

Line Number: 4698

Backtrace:

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/application/libraries/geshi/geshi.php
Line: 4698
Function: _error_handler

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/application/libraries/geshi/geshi.php
Line: 4621
Function: _optimize_regexp_list_tokens_to_string

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/application/libraries/geshi/geshi.php
Line: 1655
Function: optimize_regexp_list

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/application/libraries/geshi/geshi.php
Line: 2029
Function: optimize_keyword_group

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/application/libraries/geshi/geshi.php
Line: 2168
Function: build_parse_cache

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/application/libraries/Process.php
Line: 45
Function: parse_code

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/application/models/Pastes.php
Line: 517
Function: syntax

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/application/controllers/Main.php
Line: 551
Function: getPaste

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: Warning

Message: Cannot modify header information - headers already sent by (output started at /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/system/core/Exceptions.php:271)

Filename: view/raw.php

Line Number: 2

Backtrace:

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/themes/geocities/views/view/raw.php
Line: 2
Function: header

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/application/core/MY_Loader.php
Line: 173
Function: include

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/application/core/MY_Loader.php
Line: 43
Function: _ci_load

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/application/controllers/Main.php
Line: 558
Function: view

File: /home/httpd/vhosts/scratchbook.ch/geopaste.scratchbook.ch/index.php
Line: 315
Function: require_once

/** * 目的：实现AVL * 利用数组对左右儿子简化代码，但是对脑力难度反而增大不少，只适合acm模板 * 其实avl在acm中基本不用，基本被treap取代 * avl一般只要求理解思路，不要求写出代码，因为真心很烦 */ #include #include #include #include #include #include #include using namespace std; int COUNT; //统计树中不重复节点的个数 int HEIGHT; //统计数的高度 //数据节点 class DNode { public: int data; DNode():data(0){}; DNode(int d):data(d){} bool operator = (const DNode &d){ return data = d.data; } bool operator == (const DNode &d){ return data == d.data; } bool operator > (const DNode &d){ return data > d.data; } bool operator < (const DNode &d){ return data < d.data; } void show(){ cout << endl; cout << "***************" << endl; cout << "data: " << data << endl; } }; //treap的节点 template class AVLNode{ private: int hgt; //节点的高度 public: T data; int count; AVLNode *son[2]; //0是左儿子，1是右儿子 AVLNode(T data):data(data), count(1){ son[0] = son[1] = NULL; hgt = 1; } int max(int a, int b){return a > b ? a : b;} void show(){ data.show(); cout << "c hgt: " << this->height() << endl; cout << "l hgt: " << this->son[0]->height() << endl; cout << "r hgt: " << this->son[1]->height() << endl; cout << "count: " << count << endl; cout << endl; } int height(){ if(NULL == this) return 0; return _getHeight(this); } int _getHeight(AVLNode * cur){ if(NULL == cur) return 0; return 1 + max(_getHeight(cur->son[0]), _getHeight(cur->son[1])); } void setHeight(){ hgt = _getHeight(this); } }; //AVL Tree //这里的T是节点中的数据类型 template class AVLTree{ private: AVLNode * root; //根节点 int hgt; //树的高度 int size; //树中不重复节点数量 void _insert(AVLNode *& cur, T data); void _mid_travel(AVLNode *cur); //层次遍历 void _cengci_travel(AVLNode *cur); //单旋转（左左，右右）, 左旋不是想左旋转的意思，而是由于左子树的左儿子的高度太大 //与treap的旋转命名相反 void _singleRoate(AVLNode *& cur, int dir); //双旋转（两次单旋转） void _doubleRoate(AVLNode *& cur, int dir); int max(int a, int b){ return a > b ? a : b; } public: AVLTree():root(NULL), hgt(0){} void insert(const T & data); void mid_travel(); int height(){ return root->height(); } //层次遍历 void cengci_travel(){ _cengci_travel(root); }; }; /************* 私有方法开始**********************/ template void AVLTree::_insert(AVLNode *& cur, T data){ if(NULL == cur){ cur = new AVLNode(data); }else if(data == cur->data){ cur->count++; }else{ int dir = (data > cur->data); _insert(cur->son[dir], data); if(2 <= cur->son[dir]->height() - cur->son[!dir]->height()){ bool lr = (data > cur->data); lr ? _singleRoate(cur, dir) : _doubleRoate(cur, dir); } } cur->setHeight(); //cout << "set height: " << endl; //cur->show(); } template void AVLTree::_mid_travel(AVLNode * cur){ if(NULL != cur){ //先查找做子树 _mid_travel(cur->son[0]); //if(abs(cur->son[0]->height() - cur->son[1]->height()) >= 2) { cur->show(); } _mid_travel(cur->son[1]); } } //层次遍历， //如果节点为空就输出0 来占位 template void AVLTree::_cengci_travel(AVLNode * cur){ if(NULL == cur) return; queue*> q; q.push(cur); AVLNode *top = NULL; queue*> tmp; while(!q.empty()){ while(!q.empty()){ top = q.front(); q.pop(); if(NULL == top){ //用#代表该节点是空，#的后代还是# cout << '#' << " "; tmp.push(top); }else{ cout << top->data.data << " "; tmp.push(top->son[0]); tmp.push(top->son[1]); } } bool flag = false; while(!tmp.empty()){ if(NULL != tmp.front()) flag = true; q.push(tmp.front()); tmp.pop(); } cout << endl; if(!flag) break; } } //单旋转，即只旋转一次 //dir = 0时,左左旋转；否则为右右旋转 template void AVLTree::_singleRoate(AVLNode *& cur, int dir){ AVLNode *& k2 = cur, * k1 = k2->son[dir]; //k2 必须是引用 k2->son[dir] = k1->son[!dir]; k1->son[!dir] = k2; k2 = k1; k2->setHeight(); k1->setHeight(); } //双旋转，即调两次单旋转 //dir = 0是左右情况；否则为右左情况 template void AVLTree::_doubleRoate(AVLNode *& cur, int dir){ _singleRoate(cur->son[dir], !dir); _singleRoate(cur, dir); } /************* 公有方法（接口）开始**********************/ template void AVLTree::insert(const T & data){ _insert(root, data); } template void AVLTree::mid_travel(){ _mid_travel(root); } int main(){ AVLTree* avlt = new AVLTree(); const int num = 30; for(int i = 0; i < num; i++){ DNode * d = new DNode(i); avlt->insert(*d); } cout << "*************中序遍历***************" << endl; avlt->mid_travel(); cout << "**************中序遍历结束**********" << endl; cout << "*************层次遍历开始***************" << endl; avlt->cengci_travel(); cout << "**************层次遍历结束**********" << endl; cout << "树的高度是： " << avlt->height() << endl; return 0; }