Page 16 | 白菜君の技术库

ip_to_long

2017-03-15

字符串 ip 转长整形原理和实现

php 内置方法：ip2long

但是这个方法存在 bug，就是 010.0.3.198 的时候，计算的长整形并非正确的长整形。并且掌握实现原理，其实并不困难。

原理：

IPv4 地址我们知道的是这样子的形式： 192.168.2.10

这种形式我们称之为 点分十进制，当然还有我们的冒分十六进制，但是这个是适用于 IPv6 的

回到主题，点分十进制的写法其实是一个 4 个字节，32 位的整型组成的。

例如 : 10.0.3.198

二进制形式：00001010.00000000.00000011.11000001

说到这里，大家可能都知道了，为什么是 32 位了吧。那么二进制的 32 位转成十进制的时候，就是我们的长整形了。

转换结果为：167773121

协议, 网络, 算法协议 PHP 算法网络 IP

模拟从1亿个ip中访问次数最多的IP--PHP

2017-03-15

前提：

存储在一个文件中
内存有限，时间无限。

思路：

采用类似分表的办法，将文件拆分到各个文件中再做统计运算，提高检索速度，分散内存压力
涉及到 ip 的，首先要考虑的就是将 ip 转程长整形，理由是整型省内存，并且支持一般都支持整形索引，比字符串索引速度快
数组存储的数据结构，采用冗余的策略，记录一组数组中重复最多的 ip 和数据
独立小文件胜出的，再和分出来的其他的 N-1 个小文件胜出的比较

PHP PHP 算法大数据

C语言数据结构のAVL树

2017-02-20

实现

#ifndef _INCLUDE_BASE
#define _INCLUDE_BASE

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0
#endif

typedef int avl_elementType;

typedef struct avl
{
    avl_elementType data;
    struct avl *left;    // 左节点
    struct avl *right;   // 右节点
    avl_elementType hight;   // 以此为根的高度
}AVL,*PAVL;

//  ================================================================
    void RotateWithDoubleRight(PAVL *avl);    // RR 旋转平衡算法
    void RotateWithDoubleLeft(PAVL *avl);     // LL旋转平衡算法
    void RotateWithLeftRight(PAVL *avl);      // LR旋转平衡算法
    void RotateWithRightLeft(PAVL *avl);      // RL旋转平衡算法
    void InsertNode(PAVL *avl,int data);      // AVL插入算法
    int NodeHigh(PAVL avl);                   // 查询当前树节点的高度
    int compareHigh(PAVL a,PAVL b);           // 对比高度，取最大值
    void LeftBalance(PAVL *avl);              // 左平衡算法
    void RightBalance(PAVL *avl);             // 右平衡算法
    void print_inorder(PAVL avl);             // 中序排列打印
    void print_preorder(PAVL avl);            // 前序排列打印
    void print_houorder(PAVL avl);            // 后序排列打印
    void print_inhight(PAVL avl);             // 节点的高度
//  =================================================================

// main func
void main()
{
    PAVL root = (PAVL)malloc(sizeof(PAVL));
//    root->data = 3;

//    InsertNode(&root,2);
    InsertNode(&root,2);
    InsertNode(&root,1);
    InsertNode(&root,-1);
//    InsertNode(&root,0);
    InsertNode(&root,6);
    InsertNode(&root,7);
    InsertNode(&root,5);
    printf("中序排列节点的高度：");
    print_inhight(root);
    printf("\n");
    printf("中序排列：");
    print_inorder(root);
    printf("\n");
    printf("前序排列：");
    print_preorder(root);
}

void InsertNode(PAVL *avl,int data)
{
    if(!(*avl))
    {
        PAVL node = (PAVL)malloc(sizeof(PAVL));
        node->data = data;
        node->hight = 0;
        *avl = node;
        return ;
    }

    if(data > (*avl)->data)
    {
        InsertNode(&((*avl)->right),data);
        //判断是否破坏AVL树的平衡性
        if (NodeHeight((*avl)->right)-NodeHeight((*avl)->left)==2)
            RightBalance(avl);  //右平衡处理
    }else{
        InsertNode(&((*avl)->left),data);
        //判断是否破坏AVL树的平衡性
        printf("相减为:%d",NodeHeight((*avl)->left)-NodeHeight((*avl)->right));
        if (NodeHeight((*avl)->left)-NodeHeight((*avl)->right)==2)
            LeftBalance(avl);  //左平衡处理
        }
    (*avl)->hight = compareHigh((*avl)->left,(*avl)->right) + 1 ;
    printf("当前节点:%d , 高度:%d , left-高度:%d,right-高度:%d \n",(*avl)->data,(*avl)->hight,NodeHeight((*avl)->left),NodeHeight((*avl)->right));
}

// 空节点为-1，否则返回树节点高度
int NodeHeight(PAVL avl)
{
    return avl == NULL ? -1 : avl->hight;
}

int compareHigh(PAVL a,PAVL b)
{
    if(!a || !b)
     return 0;
    return a->hight > b->hight ? a->hight : b->hight;
}


// 左平衡处理
void LeftBalance(PAVL *avl)
{
    if(NodeHeight((*avl)->left->left) - NodeHeight((*avl)->left->right) != -1)
    {
        RotateWithDoubleLeft(avl);
    }else
    {
        RotateWithLeftRight(avl);
    }
}

// 右平衡处理
void RightBalance(PAVL *avl)
{
    if(NodeHeight((*avl)->right->right) - NodeHeight((*avl)->right->left) != -1)
    {
        RotateWithDoubleRight(avl);
    }else
    {
        RotateWithRightLeft(avl);
    }
}

// LL旋转算法
void RotateWithDoubleLeft(PAVL *avl)
{
 PAVL p = *avl;
 PAVL q = p->left;
 p->left = q->right;
 q->right = p;

 p->hight = compareHigh(p->left,p->right) +1  ;
 q->hight = compareHigh(q->left,q->right) +1 ;

 *avl = q;
}

// RR旋转算法
void RotateWithDoubleRight(PAVL *avl)
{
  PAVL p = *avl;
  PAVL q = p->right;
  p->right = q->left;
  q->left = p;

  p->hight = compareHigh(p->left,p->right) +1  ;
  q->hight = compareHigh(q->left,q->right) +1 ;

  *avl = q;
}


// LR旋转算法
void RotateWithLeftRight(PAVL *avl)
{
    printf("\nLR\n");
    RotateWithDoubleRight(&((*avl)->left));
    RotateWithDoubleLeft(avl);
}

// RL旋转算法
void RotateWithRightLeft(PAVL *avl)
{
    printf("\nRL\n");
    RotateWithDoubleLeft(&((*avl)->right));
    RotateWithDoubleRight(avl);
}

void print_inorder(PAVL avl)
{
    if(avl)
    {
        print_inorder(avl->left);
        printf("%d - ",avl->data);
        print_inorder(avl->right);
    }
}

void print_inhight(PAVL avl)
{
    if(avl)
    {
        print_inhight(avl->left);
        printf("%d - ",avl->hight);
        print_inhight(avl->right);
    }
}

void print_preorder(PAVL avl)
{
    if(avl)
    {
        printf("%d - ",avl->data);
        print_preorder(avl->left);
        print_preorder(avl->right);
    }
}

void print_houorder(PAVL avl)
{
    if(avl)
    {
        print_houorder(avl->left);
        print_houorder(avl->right);
        printf("%d - ",avl->data);
    }
}

数据结构 C 数据结构 BST树

C语言数据结构のBST树(写法二:指针引用，递归)

2017-02-15

实现

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

typedef int elementType;

typedef struct bst
{
    elementType data;   // 数据域
    struct bst *left;   // 左指针
    struct bst *right;  // 右指针
}BST,*PBST;

PBST create_bst(int root_data);     // create include the root node tree
int insert_node(PBST *bst,int data); // insert into bst
void print_inorder(PBST tree);  

void main()
{
    int in;
    printf("请输入根节点的值");
    scanf("%d",&in);

    PBST bst = create_bst(in);
    insert_node(&bst,2);
    insert_node(&bst,3);
    insert_node(&bst,4);
    insert_node(&bst,5);
    insert_node(&bst,6);
//    printf("\n%d",bst->right == NULL);
//    printf("\n%d",bst->left->data);
    print_inorder(bst);
}

PBST create_bst(int root_data)
{
    // 申请内存，并且返回地址
    PBST bst = (PBST)malloc(sizeof(PBST));
    if(bst == NULL)
    {
        printf("malloc apply fail");
        exit(-1);
    }

    bst->data = root_data; // 默认为0
    bst->left = NULL; // 防止出现野指针
    bst->right = NULL; // 防止出现野指针

    return bst;
}

void create_node(PBST child,int data)
{
    child = (PBST)malloc(sizeof(PBST));
    child->data = data;
    child->left = child->right = NULL;
}

// 中序排列（递增排列）
int insert_node(PBST *bst,int data)
{
    if(!(*bst)) {
        PBST temp = (PBST)malloc(sizeof(PBST));
        temp->left = temp->right = NULL;
        temp->data = data;
        *bst = temp;
        return ;
    }

    if (data < (*bst)->data) {
        insert_node(&((*bst)->left),data);
    }else if (data > (*bst)->data) {
        insert_node(&((*bst)->right),data);
    }
}

void print_inorder(PBST tree) {
    if(tree) {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

数据结构 C 数据结构 BST树

C语言数据结构のBST树(写法一:非指针引用，非递归)

2017-02-15

实现

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

typedef int elementType;

typedef struct bst
{
    elementType data;   // 数据域
    struct bst *left;   // 左指针
    struct bst *right;  // 右指针
}BST,*PBST;

PBST create_bst(int root_data);     // create include the root node tree
int insert_node(PBST bst,int data); // insert into bst
PBST create_node(PBST child,int data);
void print_inorder(PBST tree);

void main()
{
    int in;
    printf("请输入根节点的值");
    scanf("%d",&in);

    PBST bst = create_bst(in);
    insert_node(bst,2);
//    insert_node(bst,3);
    insert_node(bst,4);
    insert_node(bst,1);
//    insert_node(bst,6);
//    printf("\n%d",bst->right == NULL);
//    printf("\n%d",bst->left->data);
    print_inorder(bst);
}

PBST create_bst(int root_data)
{
    // 申请内存，并且返回地址
    PBST bst = (PBST)malloc(sizeof(PBST));
    if(bst == NULL)
    {
        printf("malloc apply fail");
        exit(-1);
    }

    bst->data = root_data; // 默认为0
    bst->left = NULL; // 防止出现野指针
    bst->right = NULL; // 防止出现野指针

    return bst;
}

PBST create_node(PBST child,int data)
{
    child = (PBST)malloc(sizeof(PBST));
    if(child==NULL)
    {
        printf("malloc apply fail - child");
        exit(-1);
    }
    child->data = data;
    child->left = child->right = NULL;

    return child;
}

// 中序排列（递增排列）
int insert_node(PBST bst,int data)
{
    PBST current_node = bst;
        if(current_node->data > data)
        {
            while(true){
                if(current_node->left !=NULL)
                {
                    current_node = current_node->left;
                }else
                {
                    PBST child = (PBST)malloc(sizeof(PBST));
                    child = create_node(child,data);

                    printf("\nchild data : %d \n",child->data);

                    current_node->left = child;

                   break;
                }
            }
        }else{
            while(true){
                if(current_node->right !=NULL)
                {
                    current_node = current_node->right;
                }else
                {
                    PBST child = (PBST)malloc(sizeof(PBST));
                    child = create_node(child,data);

                    printf("\nchild data : %d \n",child->data);

                    current_node->right = child;

                  break;
                }
           }
        }
}

void print_inorder(PBST tree) {
    if(tree) {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

数据结构 C 数据结构 BST树

C语言数据结构の循环队列

2017-02-15

实现

#include <stdio.h>
#include <stdlib.h>

// because the C language does not has the type of boolean ,so , we use replace of which int,example 1 and 0 replace of the "true" and "false"
#define true 1
#define false 0

// alias name by int
typedef int elementType;

// design the queue data stuct
typedef struct queue
{
    elementType *content;
    elementType front;
    elementType rear;
    elementType maxSize;
}QUEUE,*PQUEUE;

// define the func
PQUEUE createQueue();                 // create one queue , return the queue
int isFull(PQUEUE queue);             // is Full
int isEmpty(PQUEUE queue);            // is Empty
int enQueue(PQUEUE queue,int data);   // EnQueue , include isFull
int deQueue(PQUEUE queue);            // DeQueue, include isEmpty
//void loop_print(PQUEUE queue);      // Loop Print the queue;

void main()
{
    // define the queue
    PQUEUE queue = NULL;

    printf(" Please Input the queue of length :");
    int length;
    scanf("%d",&length);

    // invoke func
    queue = createQueue(length);

    while(true)
    {
        printf(" Please Input which your want to enQueue the data:");
        int data ;
        scanf("%d",&data);
        if(data == 0)
        {
            break;
        }
        // invoke func
        enQueue(queue,data);
    }

    char *result = (char *)malloc(sizeof(char));
    while(true)
    {
        printf("deQueue :");
        int data = deQueue(queue);
        printf("data : %d\n",data);

        printf(" Go on ? [yes|no]\n");
        scanf("%s",result);
        if(strcmp(result,"yes") != 0)
        {
            break;
        }
    }
}


PQUEUE createQueue(int maxSize)
{
    PQUEUE p = (PQUEUE)malloc(sizeof(PQUEUE));
    if(p == NULL)
    {
        printf("malloc apply fail");
        exit(-1);
    }

    if(maxSize < 1)
    {
        printf("the queue size does not < 1");
        exit(-1);
    }
    maxSize++;

    // when the front end rear equals ,the queue is empty
    p->front = p->rear = 0;
    p->maxSize = maxSize;
    p->content = (elementType *)malloc(sizeof(elementType));         // init Mem

    // return the queue of point;
    return p;
}

int enQueue(PQUEUE queue,int data)
{
    if(isFull(queue)){
        printf("The queue is fullest,data : %d\n",data);
        exit(-1);
    }
    queue->content[queue->rear] = data;
    queue->rear = (queue->rear+1)%queue->maxSize;
}

int isFull(PQUEUE queue)
{
    if((((queue->rear)+1)%queue->maxSize == queue->front))
    {
        return true;
    }

    return false;
}

int isEmpty(PQUEUE queue)
{
    if(queue->rear == queue->front && queue->maxSize > 0)
    {
        return true;
    }

    return false;
}

int deQueue(PQUEUE queue)
{
    if(isEmpty(queue))
    {
        printf("队列为空");
        exit(-1);
    }

    int data = queue->content[queue->front];
    queue->front = (queue->front+1)%queue->maxSize;

    return data;
}

数据结构 C 数据结构循环队列

PHP7扩展开发のHello Wold

2017-02-10

简介

想要突破自我，必须深入了解 PHP，今天我们讲讲 PHP 扩展的开发，此路长长，需要多多积累 C 语言的知识，废话不多说，直入主题。

资源

先去 github 上下载 PHP 的源码，搜索 php-src

https://github.com/php/php-src

PHP PHP PHP扩展

C语言数据结构の单链表

2017-01-24

实现

#include <stdio.h>
#include <stdlib.h> // 声明exit函数

/* 单节点的数据结构 16个字节 */
typedef struct Node
{
 int data;            //数据域
 struct Node * pNext; //指针域
}NODE,*PNODE;

//函数声明
PNODE createLinkList(void);        //创建链表的函数
void traverseLinkList(PNODE pHead);      //遍历链表的函数

/**
 *  主函数入口 main
 */
void main()
{
    PNODE pHead = NULL;
    pHead = createLinkList();
    traverseLinkList(pHead);
}

/**
 *  创建链表
 */
PNODE createLinkList(void)
{
    int length;
    int i;
    int value;

    // 申请内存空间,头结点
    PNODE phead = (PNODE)malloc(sizeof(NODE));
     if(NULL == phead)
     {
      printf("内存分配失败，程序退出！\n");
      exit(-1);
     }

    // 尾节点
    PNODE pend = phead; // pend始终指向尾节点
    pend->pNext = NULL; // 单链表尾节点指针域为NULL

    printf("请输入链表的长度,len =");
    scanf("%d",&length);

    // 创建链表长度
    for(i= 0;i< length;i++){
        printf("请输入第%d个节点的值 :",i);
        scanf("%d",&value);
        PNODE pNew =(PNODE)malloc(sizeof(NODE));
        if(NULL == pNew)
        {
          printf("内存分配失败，程序退出！\n");
          exit(-1);
        }
        pNew->data = value;  // 把新值放入节点
        pend->pNext = pNew;  // 把尾节点指向新节点
        pNew->pNext = NULL;  // 尾节点指针域为NULL
        pend = pNew;
    }

    return phead;
}

void traverseLinkList(PNODE pHead)
{
 PNODE p = pHead->pNext;
 while(NULL != p)
 {
  printf("%d  ", p->data);
  p = p->pNext;
 }
 printf("\n");
}

数据结构 C 数据结构单链表

线性存储结构

2017-01-24

简介

线性结构是一个有序元素集合
常用的线性结构有：线性表，栈，队列，双队列，数组，串
关于广义表，是一种非线性数据结构
常见的非线性结构有：二维数组，多维数组，树（二叉树等），广义表，图。

数据结构数据结构线性存储结构

C 语言入门实录二

2017-01-21

C语言中的类型分为一下几种

序号	类型和描述
1	基本类型：算术类型，整数类型和浮点类型
2	枚举类型：也是算术类型，但是是一些离散固定的整数类型
3	void类型：表明没有可用的值
4	派生类型：指针类型，数组类型，结构类型，函数类型以及共用体类型

整数类型

类型	存储大小（1个字节(bit)占8位[bits]）	值的范围（由二进制得出）
char	1字节	-128~~127 或者 0~~255
unsigned char	1字节	0~255
signed char	1字节	-128~127
int	2字节(16位系统)或4字节(32/64位系统)	-32,768 到 32,767 或 -2,147,483,648 到 2,147,483,647
unsigned int	2字节(16位系统)或4字节(32/64位系统)	0 到 65,535 或 0 到 4,294,967,295
short	2字节	-32,768 到 32,767
unsigned short	2字节	0 到 65,535
long	4字节	-2,147,483,648 到 2,147,483,647
unsigned long	4字节	0 到 4,294,967,295

C C 学习记录