邢栋博客

数据：描述客观事物的符号，如文本、图片、视频
数据元素：组成数据的，有一定意义的基本单位
数据项：一个数据元素可以由若干个数据项组成
数据对象：性质相同的数据元素的组合
数据结构：数据结构是计算机用来组织和存储数据的方式。具体定义：数据结构是指相互之间存在着一种或者多种关系的数据元素的集合和该集合中数据元素的关系组成

数据结构：
逻辑结构 
1.线性结构 (线性表、栈、队、串、数组)
2.非线性结构  树结构和图结构
物理（存储）结构
1.顺序结构
2.链式结构
3.索引结构
4.散列结构
数据运算
1.插入运算
2.删除运算
3.修改运算
4.查找运算
5.排序运算

时间复杂度
1.一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数T(n)
注：如果一个循环次数n次的for语句，如果里面有3条赋值语句，那么总执行次数就是3n，所以这个函数T(n)就是循环次数,T(n)=3n，语句的执行次数(频度)*单位执行时间 就是总执行时间

2.从T(n)中找到同数量级(同阶)函数记作f(n)，例如T(n)= 3n的同数量级的函数f(n)=n
注:如果T(n)=n^3+n^2+n,则 f(n)=n^3

3.这个时候我们能够计算出时间复杂度了 T(n)=O(f(n))
用T(n)/f(n)，然后求极限值--------  (n^3+n^2+n)/n^3 = 1+1/n+1/n^2  ，求极限值 是一个常数，那么时间复杂度就是 O(f(n)),也就是O(n^3)

简单推导时间复杂度
1.用常数1取代执行时间中的所有加法常数
2.在修改后的执行次数函数中，只保留最高阶项
3.如果最高阶存在且不是1，则去掉他的系数
4.得到的结果就是大O阶
简单说就是 最高阶的执行次数


线性表的特点
定义：零个或多个数据元素的有限序列
除首尾外，均只有一个直接前驱和直接后继

一个数组元素可以有若干数据项组成
线性表有顺序存储和链式存储两种数据结构 
堆栈、队列、串、数组等都是线性表

单链表
head -> A -> B -> C -> D -> E
data-next 
节点包括 1、data数据域,存放节点的值 2、next指针域,存放节点的直接后继的地址
插入节点:头插/尾插，也叫前插和后插，其实就是head所指向节点不一样，当然他们的时间复杂度也不一样
删除节点:先找到要删除的节点位置，将父节点的next指向其子节点，然后删除该节点
查询节点:从head开始一级一级往下找
编辑节点:从head开始一级一级往下找,找到后编辑内容
节点排序:。


双链表
head <-> A <-> B <-> C <-> D <-> E
pre-data-next 
节点包括 1、data数据域,存放节点的值 2、pre指针域,存放节点的直接前驱的地址 3、next指针域,存放节点的直接后继的地址

队列QUEUE
队列是只允许在一端进行插入，则在另外一端进行删除的运算受限的线性表
1.允许删除的一端成为队头(Front)
2.允许插入的一端为队尾(Rear)
3.队列中没有元素成为空队列
4.队列亦称作先进先出的线性表,简称FIFO表

堆栈
先进后出


树
它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做树是是因为它看起来像一颗倒挂的树
特点
1.每个节点有零个或者多个子节点
2.没有父节点的节点成为根节点
3.每一个非根节点有且只有一个父节点
4.除了根节点外，每个子节点可以分为多个不相符的子树

无序树：树中任意节点的子节点之间没有顺序关系，这种树叫做无序树，也叫做自由树
有序数: 树中任意节点的子节点之间有顺序关系，成为有序树
二叉树:每个节点最多包含两个子树的树称为二叉树 完全二叉树：对于一颗二叉树，假设其深度d(d>1).除了第d层外，其他各层的节点，数目均已达最大值，且第d层所有节点从左向右连续的紧密排列，这样的二叉树称为完全二叉树
满二叉树：对于上述的完全二叉树，如果去掉其第d层的所有节点，那么剩下的部分就构成一个满二叉树(此时该满二叉树的深度为d-1)
霍夫曼树：带全路径最短的二叉树称为霍夫曼树或者最优二叉树



遍历二叉树
    A
  B    C
D E   F
  G H  I
1.先序遍历 ABCDEFGHI  首先访问根结点，然后遍历左子树，然后遍历右子树。简称 根-左-右
2.中序遍历 DBAGECHFI  首先遍历左子树，然后访问根节点，然后遍历右子树。简称 左-根- 右
3.后序遍历 DBGEHIFCA   首先遍历左子树，然后遍历右子树，最后访问根节点。简称 左-右-根

二叉排序数
二叉排序树又称二叉查找数，也成二叉搜索树，它或者是一颗空树；或者是具有下列性质的二叉树：
1.若左子树不空，则左子树上所有节点的值均小于它的根节点的值
2.若右子树不空，则右子树上所有节点的值均小于他的根节点的值
3.左、右子树也分别为二叉排序树



快速排序
通过一趟排序，将待排序部分记录分隔成独立的两部分，其中一部分记录的关键字均比另外一部分记录的关键值小，在分别对这两部分记录进行下一趟排序，以达到整个序列有序。
快速排序就是比较适合用递归来处理的。


简单选择排序
排序思想:设所排序序列的记录个数为n。i取1,2，。。。。n-1,从所有n-i+1个记录中找到排序码最小的记录，与第i个记录交换。执行n-1趟后完成了记录序列的排序。

直接插入排序
每次从无序表中取出第一个元素，把他插入到有序表的合适位置，使有序表依然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中;第二趟把第三个数据与前两个数从前向后扫描，第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后完成了整个排序过程。

<?php
    class node{
        //初始化变量，包括存储的内容和下一个数据的指针
        public $id = 0;
        public $data = '';
        public $next = null;
        //构造函数,设置存储内容的数据
        public function __construct($id,$nodedata){
            $this->id = $id;
            $this->data = $nodedata;
        }
    }


    class singleLink{
        public $head = '';
        public $size = 0;
        public function  insert($id,$value,$prenodeid = 0){

            $node = new node($id,$value);
            //如果是空链表，直接添加
            if($this->size == 0){
                $this->head = $node;
            }elseif($prenodeid == 0){
                //如果不是空链表，且并没有指定在某一个节点前添加，则在当前节点前添加
                $node->next = $this->head;
                $this->head = $node;
            }else{
                //在某一个节点后添加新节点
                $currentnode = $this->head;
                while($currentnode->next != null) {
                    if ($currentnode->next->id == $prenodeid) {
                        $node->next = $currentnode->next;
                        $currentnode->next = $node;
                        break;
                    }
                    $currentnode = $currentnode->next;
                }
            }

            $this->size++;

            return $this;
        }

        public function edit($id,$value){
            $flag = false;
            $current = $this->head;
            while(@$current->id != null){
                if($current->id == $id){
                    $current->data = $value;
                    $flag = true;
                    break;
                }
                $current = $current->next;
            }
            return $flag;
        }


        public function get($id=0){
            $current = $this->head;
            while(@$current->id != null){
                if($id != 0 && $current->id == $id){
                    $node = $current;
                    break;
                }else{
                    $node[] = array($current->id,$current->data);
                }
                $current = $current->next;
            }
            return $node;
        }


        public function delete($id){
            $flag = false;
            $current = $this->head;
            while(@$current->id != null){
                if($current->next->id == $id){
                    $current->next = $current->next->next;
                    $this->size--;
                    $flag = true;
                    break;
                }

                $current = $current->next;
            }
            return $flag;
        }

    }


    $linklist = new singleLink();
    $linklist->insert(1,'hello1');
    $linklist->insert(2,'hello2');
    $linklist->insert(3,'hello3');
    $linklist->insert(4,'hello4');
    $linklist->insert(5,'hello5');
    $linklist->insert(6,'hello6',2);
    $linklist->insert(7,'hello7');

    $linklist->delete(5);

    $linklist->insert(8,'hello8')->insert(9,'hello9')->insert(10,'hello10');

    echo "<pre>";
    print_r($linklist);
    print_r($linklist->get());

<?php
    //php使用mongo的GridFS存储文件
    $conn = new MongoClient();
    $db = $conn->photos;
    $collection = $db->getGridFS();

    //存储文件
    $id = $collection->storeFile('./logo22.png');

    //存储文件二进制流
//    $data = file_get_contents('./logo22.png');
//    $id = $collection->storeBytes($data,array('param'=>'logo图片'));

    //保存
    //$id = $collection->storeUpload('upfile');
    //相当于
    //$id = $collection->storeFile($_FILES['upfile']['tmp_name']);

    //读取
    $logo = $collection->findOne(array('_id'=>$id));
    header('Content-type:image/png');//输出图片头
    //var_dump($logo);
    echo $logo->getBytes();

<?php

//unset($_SERVER['PHP_AUTH_DIGEST']);

$username = 'xingdong'; //用户名
$userpass = '123456'; //面膜
$secret = 'xingdong365'; //秘钥

$realm = '401test';

$opaque = md5($secret.$_SERVER['HTTP_USER_AGENT'].$_SERVER['REMOTE_ADDR']);

if (!isset($_SERVER['PHP_AUTH_DIGEST']) || empty($_SERVER['PHP_AUTH_DIGEST'])) {
    header('HTTP/1.1 401 Unauthorized');
    header('WWW-Authenticate: Digest realm="'.$realm.'",qop="auth",nonce="'.uniqid().'",opaque="'.$opaque.'"');
    die;
}

$needed_parts = array(
    'nonce'    => 1,
    'nc'       => 1,
    'cnonce'   => 1,
    'qop'      => 1,
    'username' => 1,
    'uri'      => 1,
    'response' => 1
);

$data = array();
$keys = implode('|', array_keys($needed_parts));

preg_match_all('/('.$keys.')=(?:([\'"])([^\2]+?)\2|([^\s,]+))/', $_SERVER['PHP_AUTH_DIGEST'], $matches, PREG_SET_ORDER);

foreach ($matches as $m) {
    $data[$m[1]] = $m[3] ? $m[3] : $m[4];
    unset($needed_parts[$m[1]]);
}

//检测用户名
if ($data['username'] != $username){
    header('HTTP/1.1 401 Unauthorized');
    header('WWW-Authenticate: Digest realm="'.$realm.'",qop="auth",nonce="'.uniqid().'",opaque="'.$opaque.'"');
    die('Invalid username.');
}

$password = md5($username.':'.$realm.':'.$userpass);

$response = md5($password.':'.$data['nonce'].':'.$data['nc'].':'.$data['cnonce'].':'.$data['qop'].':'.md5($_SERVER['REQUEST_METHOD'].':'.$data['uri']));



if ($data['response'] != $response) {
    header('HTTP/1.1 401 Unauthorized');
    header('WWW-Authenticate: Digest realm="'.$realm.'",qop="auth",nonce="'.uniqid().'",opaque="'.$opaque.'"');
    die('Invalid password.');
}


echo "success";

php代码的执行过程

扫描->解析->编译->执行->输出

1.扫描(scanning) 将index.php内容变成一个个语言片段(token)

<?php

$code =<<<'PHP_CODE'
<?php
//这是注释
echo "hello world\n";
$data = 1+1;
eval("echo 'Inception lvl 1...\n';");
echo $data;
PHP_CODE;
echo "<pre>";
print_r(token_get_all($code));

echo token_name(319);//输出 T_ECHO  ,260 T_EVAL(eval不是函数)

/*
 *   [16] => Array
        (
            [0] => 319  //tokenid,也就是词的id
            [1] => echo  //词具体的内容
            [2] => 5 //所在的位置,行数
        )
 *
 */

?>

2.解析(parsing) 将一个个语言片段变成有意义的表达式
3.编译(complication) 将表达式编译成中间码(opcode)  //可以使用vld扩展或者parsekit扩展查看
4.执行(execution) 将中间码一条条的执行
如果执行的是某内置函数，会调用对应的函数;
如果调用的是扩展，则会将控制权交给这些扩展，扩展执行完成后将结果返回给 zend engine
全部执行完成后zend engine将结果返回给php内核，内核再返回给sapi，最后返回给服务器，通过服务器httpresponse返回到浏览器

5.输出(output buffer) 将要输出的内容输出到缓冲区

shell函数说明

1.函数调用时，脚本的位置函数($* $@ $# $1...)会被替换为函数的参数，函数执行完毕后，会恢复原值

2.函数中的变量默认为全局作用域，除非使用local关键字定义

3.通过return 命令可以让函数返回数字值，常用于表示函数执行是否成功。如果返回字符串值，则需要在函数中使用echo，然后再在函数外使用$()捕获；或者将字符串存在一个变量中，函数执行完毕后读取该变量

4.如果函数中没有使用 return 指定返回值，则函数返回值为最后一条命令的退出码($?捕获返回值) 

5.简单事例

#!/bin/bash

foo()
{
  echo "is your name  $* ?"
  while true
  do
    echo -n "enter yes or no:"
    read x
    case $x in
        y|yes) return 0;;
        n|no) return 1;;
        *) echo "answer yes or no"
    esac
  done
}

echo "your parameters is $*"
if foo "$1"
then
  echo "hi $1,nice name"
else
  echo "never mind"
fi

exit 0

新建xml.xml

<?xml version="1.0" encoding="utf-8"?>  
<shows>  
    <show>  
        <name>action</name>
        <age>18</age>
        <sex>男</sex>
    </show>  
    <show>  
        <name>yiyi</name>
        <age>20</age>
        <sex>女</sex>
    </show>  
</shows>  

xml.php如下

<?php
    $items = [];
    $reader = new XMLReader();
    $reader->open('xml.xml','utf-8');

    while($reader->read()){
        if($reader->name == 'show' && $reader->nodeType == XMLReader::ELEMENT){
            $item = [];
            while($reader->read() && $reader->name != 'show'){
                if($reader->nodeType != XMLReader::ELEMENT)continue;

                $name = $reader->name;
                $value = $reader->readString();
                $item[$name]  = $value;
            }
            $items[] = $item;

        }

    }
    echo "<pre>";
    print_r($items);

文本文件和二进制文件有什么不同

1.文本文件是基于字符编码的文件
2.除了文本文件以外的文件成为二进制文件
3.二进制文件编码是变长的，灵活利用率高
4.两者读写差别仅体现在回车换行符的处理上
5.文本文件是一种特殊的二进制文件

php写入和读取二进制文件 简单事例

//写入方式1
// $fh = fopen('my.db','w'); 
// $name  = pack('A20','zsf');//长度不足20会以空格补充
// $age = pack('S',1);
// $email = pack('a20','xingdong365@qq.com');//长度不足20会以null补充

// fwrite($fh,$name.$age.$email);

//写入方式2,同上
$fh = fopen('my_1.db','w');
$data = pack('A20Sa20','zsf',1,'xingdong365@qq.com');
fwrite($fh,$data);


$tmp = file_get_contents('my_1.db');
$data = unpack('A20name/Sage/a20email',$tmp);


print_r($data);

文件指针的定位操作

fseek() 在文件指针中定位
ftell() 返回文件指针读/写的位置
rewind() 返回文件指针的位置
feof() 测试文件指针是否达到了文件结束的位置