简单HashTable(取模法)

在 2016年7月21日2016年8月12日上张贴由 BestLove

//参考：http://www.php-internals.com/book/?p=chapt03/03-01-01-hashtable
//http://www.cunmou.com/phpbook/preface.md
//http://wiki.swoole.com/wiki/index/prid-7
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashtable.h"

int main(int argc, char const *argv[])
{
    HashTable *h = (HashTable *)malloc(sizeof(HashTable));
    hash_init(h);

    char * str1 = "key1";
    char * str2 = "key2";
    char * str3 = "key3";
    char * str4 = "key4";
    char * str5 = "key5";
    char * str6 = "key6";
    char * str7 = "key7";
    char * str8 = "key8";

    int num1 = 1;
    int num2 = 2;
    int num3 = 3;
    int num4 = 4;
    int num5 = 5;
    int num6 = 6;
    int num7 = 7;
    int num8 = 8;

    hash_insert(h, str1, &num1);
    hash_insert(h, str2, &num2);
    hash_insert(h, str3, &num3);
    hash_insert(h, str4, &num4);
    hash_insert(h, str5, &num5);
    hash_insert(h, str6, &num6);
    hash_insert(h, str7, &num7);
    hash_insert(h, str8, &num8);

    int *num11 = NULL;
    int *num22 = NULL;
    int *num33 = NULL;
    int *num44 = NULL;
    int *num55 = NULL;
    int *num66 = NULL;
    int *num77 = NULL;
    int *num88 = NULL;

    hash_lookup(h, str1, (void **)&num11);
    hash_lookup(h, str2, (void **)&num22);
    hash_lookup(h, str3, (void **)&num33);
    hash_lookup(h, str4, (void **)&num44);
    hash_lookup(h, str5, (void **)&num55);
    hash_lookup(h, str6, (void **)&num66);
    hash_lookup(h, str7, (void **)&num77);
    hash_lookup(h, str8, (void **)&num88);

    printf("find result key=%s value=%d \n", str1, *num11);
    printf("find result key=%s value=%d \n", str2, *num22);
    printf("find result key=%s value=%d \n", str3, *num33);
    printf("find result key=%s value=%d \n", str4, *num44);
    printf("find result key=%s value=%d \n", str5, *num55);
    printf("find result key=%s value=%d \n", str6, *num66);
    printf("find result key=%s value=%d \n", str7, *num77);
    printf("find result key=%s value=%d \n", str8, *num88);
 
    hash_destroy(h);
    return 0;
}

//参考：http://www.php-internals.com/book/?p=chapt03/03-01-01-hashtable

//http://www.cunmou.com/phpbook/preface.md

//http://wiki.swoole.com/wiki/index/prid-7

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "hashtable.h"

int main(int argc, char const *argv[])

{

HashTable *h = (HashTable *)malloc(sizeof(HashTable));

hash_init(h);

char * str1 = "key1";

char * str2 = "key2";

char * str3 = "key3";

char * str4 = "key4";

char * str5 = "key5";

char * str6 = "key6";

char * str7 = "key7";

char * str8 = "key8";

int num1 = 1;

int num2 = 2;

int num3 = 3;

int num4 = 4;

int num5 = 5;

int num6 = 6;

int num7 = 7;

int num8 = 8;

hash_insert(h, str1, &num1);

hash_insert(h, str2, &num2);

hash_insert(h, str3, &num3);

hash_insert(h, str4, &num4);

hash_insert(h, str5, &num5);

hash_insert(h, str6, &num6);

hash_insert(h, str7, &num7);

hash_insert(h, str8, &num8);

int *num11 = NULL;

int *num22 = NULL;

int *num33 = NULL;

int *num44 = NULL;

int *num55 = NULL;

int *num66 = NULL;

int *num77 = NULL;

int *num88 = NULL;

hash_lookup(h, str1, (void **)&num11);

hash_lookup(h, str2, (void **)&num22);

hash_lookup(h, str3, (void **)&num33);

hash_lookup(h, str4, (void **)&num44);

hash_lookup(h, str5, (void **)&num55);

hash_lookup(h, str6, (void **)&num66);

hash_lookup(h, str7, (void **)&num77);

hash_lookup(h, str8, (void **)&num88);

printf("find result key=%s value=%d \n", str1, *num11);

printf("find result key=%s value=%d \n", str2, *num22);

printf("find result key=%s value=%d \n", str3, *num33);

printf("find result key=%s value=%d \n", str4, *num44);

printf("find result key=%s value=%d \n", str5, *num55);

printf("find result key=%s value=%d \n", str6, *num66);

printf("find result key=%s value=%d \n", str7, *num77);

printf("find result key=%s value=%d \n", str8, *num88);

hash_destroy(h);

return 0;

}

#ifndef _HASH_TABLE_H_
#define _HASH_TABLE_H_
//初始化hashtable的默认长度，当hashtable的实际长度超过HASH_TABLE_INIT_SIZE时会以2倍的方式扩容
#define HASH_TABLE_INIT_SIZE 6
//以下宏配合hashtable.c中的hash_str函数，可以计算hash值(取模法)
#define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)
//如果定义了DEBUG常量，则LOG_MSG会使用printf，否则是一个空操作
#if defined(DEBUG)
#  define LOG_MSG printf
#else
#  define LOG_MSG(...)
#endif

#define SUCCESS 0
#define FAILED -1

typedef struct _Bucket
{
    char *key;                  //字符串key
    void *value;                //value指针，直接操作传入的指针，不返回value值
    struct _Bucket *next;
} Bucket;

typedef struct _HashTable
{
    int size;                    // 哈希表的大小
    int elem_num;                // 已经保存元素的个数
    Bucket **buckets;            // bucket指针数组
} HashTable;

int hash_init(HashTable *ht);
//**result(参数为二级指针，因为需要传入指针的引用)
int hash_lookup(HashTable *ht, char *key, void **result);
int hash_insert(HashTable *ht, char *key, void *value);
int hash_remove(HashTable *ht, char *key);
int hash_destroy(HashTable *ht);
#endif

#ifndef _HASH_TABLE_H_

#define _HASH_TABLE_H_

//初始化hashtable的默认长度，当hashtable的实际长度超过HASH_TABLE_INIT_SIZE时会以2倍的方式扩容

#define HASH_TABLE_INIT_SIZE 6

//以下宏配合hashtable.c中的hash_str函数，可以计算hash值(取模法)

#define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)

//如果定义了DEBUG常量，则LOG_MSG会使用printf，否则是一个空操作

#if defined(DEBUG)

# define LOG_MSG printf

#else

# define LOG_MSG(...)

#endif

#define SUCCESS 0

#define FAILED -1

typedef struct _Bucket

{

char *key; //字符串key

void *value; //value指针，直接操作传入的指针，不返回value值

struct _Bucket *next;

} Bucket;

typedef struct _HashTable

{

int size; // 哈希表的大小

int elem_num; // 已经保存元素的个数

Bucket **buckets; // bucket指针数组

} HashTable;

int hash_init(HashTable *ht);

//**result(参数为二级指针，因为需要传入指针的引用)

int hash_lookup(HashTable *ht, char *key, void **result);

int hash_insert(HashTable *ht, char *key, void *value);

int hash_remove(HashTable *ht, char *key);

int hash_destroy(HashTable *ht);

#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashtable.h"
//设置key时，检查下哈希表是否已满，已满的话，调用hash_resize方法
static void resize_hash_table_if_needed(HashTable *ht);
//将字符串key转换成数字(每个字符的ASCII累加)
static int hash_str(char *key);
//哈希表扩容方法，将哈希表扩容2倍
static int hash_resize(HashTable *ht);

int hash_init(HashTable *ht)
{
    ht->size 		= HASH_TABLE_INIT_SIZE;
    ht->elem_num 	= 0;
    ht->buckets		= (Bucket **)calloc(ht->size, sizeof(Bucket *));
    //分配内存失败，直接返回错误
    if(ht->buckets == NULL) return FAILED;
    LOG_MSG("[init]\tsize: %d\n", ht->size);
    return SUCCESS;
}

int hash_lookup(HashTable *ht, char *key, void **result)
{
    //把字符串的每个字符的ascii码累加后和hash表的size取模
    int index = HASH_INDEX(ht, key);
    //从buckets中获取bucket指针
    Bucket *bucket = ht->buckets[index];
    while(bucket)
    {
        if(strcmp(bucket->key, key) == 0)
        {
            *result = bucket->value;
            return SUCCESS;
        }
        bucket = bucket->next;
    }
    LOG_MSG("[lookup]\t key:%s\tfailed\t\n", key);
    return FAILED;
}

int hash_insert(HashTable *ht, char *key, void *value)
{
    resize_hash_table_if_needed(ht);
    int index = HASH_INDEX(ht, key);
    Bucket *org_bucket = ht->buckets[index];
    Bucket *tmp_bucket = org_bucket;
    while(tmp_bucket)
    {
        if(strcmp(key, tmp_bucket->key) == 0)
        {
            tmp_bucket->value = value;
            return SUCCESS;
        }
        tmp_bucket = tmp_bucket->next;
    }
    Bucket *bucket = (Bucket *)malloc(sizeof(Bucket));
    bucket->key	  = key;
    bucket->value = value;
    bucket->next  = NULL;
    ht->elem_num++;
    if(org_bucket != NULL)
    {
        LOG_MSG("[collision]\tindex:%d key:%s\n", index, key);
        bucket->next = org_bucket;
    }
    ht->buckets[index] = bucket;
    LOG_MSG("[insert]\tindex:%d key:%s\tht(num:%d)\n", index, key, ht->elem_num);
    return SUCCESS;
}

int hash_remove(HashTable *ht, char *key)
{
    int index = HASH_INDEX(ht, key);
    Bucket *bucket  = ht->buckets[index];
    Bucket *prev	= NULL;
    if(bucket == NULL) return FAILED;
    while(bucket)
    {
        if(strcmp(bucket->key, key) == 0)
        {
            LOG_MSG("[remove]\tkey:(%s) index: %d\n", key, index);
            if(prev == NULL)
            {
                ht->buckets[index] = bucket->next;
            }
            else
            {
                prev->next = bucket->next;
            }
            free(bucket);
            ht->elem_num--;
            return SUCCESS;
        }
        prev   = bucket;
        bucket = bucket->next;
    }
    LOG_MSG("[remove]\t key:%s not found remove \tfailed\t\n", key);
    return FAILED;
}

int hash_destroy(HashTable *ht)
{
    int i;
    Bucket *cur = NULL;
    Bucket *tmp = NULL;
    for(i = 0; i < ht->size; ++i)
    {
        cur = ht->buckets[i];
        while(cur)
        {
            tmp = cur;
            cur = cur->next;
            free(tmp);
        }
    }
    free(ht->buckets);
    free(ht);
    return SUCCESS;
}

static int hash_str(char *key)
{
    int hash = 0;

    char *cur = key;

    while(*cur != '\0')
    {
        hash +=	*cur;
        ++cur;
    }

    return hash;
}

static int hash_resize(HashTable *ht)
{
    int org_size = ht->size;
    ht->size = ht->size * 2;
    ht->elem_num = 0;
    LOG_MSG("[resize]\torg size: %i\tnew size: %i\n", org_size, ht->size);
    Bucket **buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));
    Bucket **org_buckets = ht->buckets;
    ht->buckets = buckets;
    int i = 0;
    for(i = 0; i < org_size; ++i)
    {
        Bucket *cur = org_buckets[i];
        Bucket *tmp;
        //循环将原先的bucket指针删除，然后重新插入(因为扩容后，需要重新取模定位)
        while(cur)
        {
            hash_insert(ht, cur->key, cur->value);
            tmp = cur;
            cur = cur->next;
            free(tmp);
        }
    }
    free(org_buckets);
    LOG_MSG("[resize] done\n");
    return SUCCESS;
}

static void resize_hash_table_if_needed(HashTable *ht)
{
    if(ht->size - ht->elem_num < 1)
    {
        hash_resize(ht);
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "hashtable.h"

//设置key时，检查下哈希表是否已满，已满的话，调用hash_resize方法

static void resize_hash_table_if_needed(HashTable *ht);

//将字符串key转换成数字(每个字符的ASCII累加)

static int hash_str(char *key);

//哈希表扩容方法，将哈希表扩容2倍

static int hash_resize(HashTable *ht);

int hash_init(HashTable *ht)

{

ht->size = HASH_TABLE_INIT_SIZE;

ht->elem_num = 0;

ht->buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));

//分配内存失败，直接返回错误

if(ht->buckets == NULL) return FAILED;

LOG_MSG("[init]\tsize: %d\n", ht->size);

return SUCCESS;

}

int hash_lookup(HashTable *ht, char *key, void **result)

{

//把字符串的每个字符的ascii码累加后和hash表的size取模

int index = HASH_INDEX(ht, key);

//从buckets中获取bucket指针

Bucket *bucket = ht->buckets[index];

while(bucket)

{

if(strcmp(bucket->key, key) == 0)

{

*result = bucket->value;

return SUCCESS;

}

bucket = bucket->next;

}

LOG_MSG("[lookup]\t key:%s\tfailed\t\n", key);

return FAILED;

}

int hash_insert(HashTable *ht, char *key, void *value)

{

resize_hash_table_if_needed(ht);

int index = HASH_INDEX(ht, key);

Bucket *org_bucket = ht->buckets[index];

Bucket *tmp_bucket = org_bucket;

while(tmp_bucket)

{

if(strcmp(key, tmp_bucket->key) == 0)

{

tmp_bucket->value = value;

return SUCCESS;

}

tmp_bucket = tmp_bucket->next;

}

Bucket *bucket = (Bucket *)malloc(sizeof(Bucket));

bucket->key = key;

bucket->value = value;

bucket->next = NULL;

ht->elem_num++;

if(org_bucket != NULL)

{

LOG_MSG("[collision]\tindex:%d key:%s\n", index, key);

bucket->next = org_bucket;

}

ht->buckets[index] = bucket;

LOG_MSG("[insert]\tindex:%d key:%s\tht(num:%d)\n", index, key, ht->elem_num);

return SUCCESS;

}

int hash_remove(HashTable *ht, char *key)

{

int index = HASH_INDEX(ht, key);

Bucket *bucket = ht->buckets[index];

Bucket *prev = NULL;

if(bucket == NULL) return FAILED;

while(bucket)

{

if(strcmp(bucket->key, key) == 0)

{

LOG_MSG("[remove]\tkey:(%s) index: %d\n", key, index);

if(prev == NULL)

{

ht->buckets[index] = bucket->next;

}

else

{

prev->next = bucket->next;

}

free(bucket);

ht->elem_num--;

return SUCCESS;

}

prev = bucket;

bucket = bucket->next;

}

LOG_MSG("[remove]\t key:%s not found remove \tfailed\t\n", key);

return FAILED;

}

int hash_destroy(HashTable *ht)

{

int i;

Bucket *cur = NULL;

Bucket *tmp = NULL;

for(i = 0; i < ht->size; ++i)

{

cur = ht->buckets[i];

while(cur)

{

tmp = cur;

cur = cur->next;

free(tmp);

}

free(ht->buckets);

free(ht);

return SUCCESS;

}

static int hash_str(char *key)

{

int hash = 0;

char *cur = key;

while(*cur != '\0')

{

hash += *cur;

++cur;

}

return hash;

}

static int hash_resize(HashTable *ht)

{

int org_size = ht->size;

ht->size = ht->size * 2;

ht->elem_num = 0;

LOG_MSG("[resize]\torg size: %i\tnew size: %i\n", org_size, ht->size);

Bucket **buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));

Bucket **org_buckets = ht->buckets;

ht->buckets = buckets;

int i = 0;

for(i = 0; i < org_size; ++i)

{

Bucket *cur = org_buckets[i];

Bucket *tmp;

//循环将原先的bucket指针删除，然后重新插入(因为扩容后，需要重新取模定位)

while(cur)

{

hash_insert(ht, cur->key, cur->value);

tmp = cur;

cur = cur->next;

free(tmp);

}

free(org_buckets);

LOG_MSG("[resize] done\n");

return SUCCESS;

}

static void resize_hash_table_if_needed(HashTable *ht)

{

if(ht->size - ht->elem_num < 1)

{

hash_resize(ht);

}

all:
	#-DDEBUG指定常量DEBUG，hashtable.h中 #if defined(DEBUG) 有用到
	gcc -DDEBUG main.c hashtable.c -o hashtable.out
test: all
	./hashtable.out
clean:
	rm -rf hashtable.out

all:

#-DDEBUG指定常量DEBUG，hashtable.h中 #if defined(DEBUG) 有用到

gcc -DDEBUG main.c hashtable.c -o hashtable.out

test: all

./hashtable.out

clean:

rm -rf hashtable.out

gdb简单使用

在 2016年7月7日2016年7月8日上张贴由 BestLove

#include <stdio.h>
void hello(void);
int main(int argc, char const *argv[])
{
    int i;
    int a = 13;
    printf("before for %d\n", a);
    for (i = 1; i < 3; ++i)
    {
        printf("before hello %d\n", i);
        hello();
        printf("after hello %d\n", i);
    }
    return 0;
}
void hello(void)
{
    puts("hello");
}

#include <stdio.h>

void hello(void);

int main(int argc, char const *argv[])

{

int i;

int a = 13;

printf("before for %d\n", a);

for (i = 1; i < 3; ++i)

{

printf("before hello %d\n", i);

hello();

printf("after hello %d\n", i);

}

return 0;

}

void hello(void)

{

puts("hello");

}

//-g表示将源码信息编译到可执行文件中，便于gdb调试
gcc a.c -g
//启动gdb
gdb
//使用file命令载入被调试的文件
file a.out
//运行(run)正常输出
r
//在第7行设置断点(break)
b 7

//再次运行
r
//输出如下：
Starting program: /home/wwwroot/c/a.out 
Breakpoint 1, 0x08048461 in main ()

//按s步进一步(step)
s
//输出如下：
Single stepping until exit from function main,
which has no line number information.
before for 13
before hello 1
hello
after hello 1
before hello 2
hello
after hello 2
0x00147d36 in __libc_start_main () from /lib/libc.so.6

//由于没有第2个断点，程序直接走完了
//在hello函数处设置断点
b hello

//再次运行后按c(continue)
//s(step)：一行一行执行 n(next)：函数内部一行一行执行 c(continue)：越过当前断点至下一个断点处中断
c
//输出如下：
Continuing.
before for 13
before hello 1
Breakpoint 2, 0x080484c5 in hello ()

//再按2次c(如下)
Breakpoint 2, 0x080484c5 in hello ()
(gdb) c             //第一次
Continuing.
hello
after hello 1
before hello 2
Breakpoint 2, 0x080484c5 in hello ()
(gdb) c             //第二次
Continuing.
hello
after hello 2
Program exited normally.

//info b能查看断点设置
(gdb) info b
Num     Type           Disp Enb Address    What
1       breakpoint     keep y   0x08048461 a.c:7
    breakpoint already hit 1 time
2       breakpoint     keep y   0x080484c5 <hello+6>
    breakpoint already hit 2 times

//使用d删除断点，删除指定断点可以输入d num(号码)

//-g表示将源码信息编译到可执行文件中，便于gdb调试

gcc a.c -g

//启动gdb

gdb

//使用file命令载入被调试的文件

file a.out

//运行(run)正常输出

//在第7行设置断点(break)

b 7

//再次运行

//输出如下：

Starting program: /home/wwwroot/c/a.out

Breakpoint 1, 0x08048461 in main ()

//按s步进一步(step)

//输出如下：

Single stepping until exit from function main,

which has no line number information.

before for 13

before hello 1

hello

after hello 1

before hello 2

hello

after hello 2

0x00147d36 in __libc_start_main () from /lib/libc.so.6

//由于没有第2个断点，程序直接走完了

//在hello函数处设置断点

b hello

//再次运行后按c(continue)

//s(step)：一行一行执行 n(next)：函数内部一行一行执行 c(continue)：越过当前断点至下一个断点处中断

//输出如下：

Continuing.

before for 13

before hello 1

Breakpoint 2, 0x080484c5 in hello ()

//再按2次c(如下)

Breakpoint 2, 0x080484c5 in hello ()

(gdb) c //第一次

Continuing.

hello

after hello 1

before hello 2

Breakpoint 2, 0x080484c5 in hello ()

(gdb) c //第二次

Continuing.

hello

after hello 2

Program exited normally.

//info b能查看断点设置

(gdb) info b

Num Type Disp Enb Address What

1 breakpoint keep y 0x08048461 a.c:7

breakpoint already hit 1 time

2 breakpoint keep y 0x080484c5 <hello+6>

breakpoint already hit 2 times

//使用d删除断点，删除指定断点可以输入d num(号码)

//启动gdb(带上php执行文件)，也可以使用file子命令
gdb /usr/local/php7/bin/php
//设置需要调试的php文件
set args ./test.php
//通过help子命令可以了解指定子命令的用法
help set
help set args
//设置php断点的时候，行号和函数名必须是C源码中的行号和函数名
//可以指定文件名:行号或文件名:函数名 可以通过搜索PHP源代码PHP_FUNCTION(php函数名)定位
b basic_functions.c:5475
b zend.c:zend_print_zval_r      //搜索源代码PHP_FUNCTION(print_r)定位
//还有种更简单的方法，增加 zif_ 前缀，可以直接定位到PHP_FUNCTION(php函数名)
b zif_print_r
//在断点处暂停后可以通过l(list)来查看上下文源码
//也可以通过 l 文件:行号 或 l 函数名 来查看指定位置的源代码
l basic_functions.c:5475
l zif_print_r
//在断点处p(print_r)可以打印list处源码的变量值
p  do_return
//如果打印出来的值不符合预期，可以用set进行动态设置调试
set do_return=13
//观察l出来的变量，如果变量被修改过，会把Old value和New value都输出
watch do_return
//(bt)backtrace查看程序执行的堆栈信息
//finish执行到当前函数的结束
//q(quit)退出
//gdb调试进程gdb -p 进程ID

//启动gdb(带上php执行文件)，也可以使用file子命令

gdb /usr/local/php7/bin/php

//设置需要调试的php文件

set args ./test.php

//通过help子命令可以了解指定子命令的用法

help set

help set args

//设置php断点的时候，行号和函数名必须是C源码中的行号和函数名

//可以指定文件名:行号或文件名:函数名可以通过搜索PHP源代码PHP_FUNCTION(php函数名)定位

b basic_functions.c:5475

b zend.c:zend_print_zval_r //搜索源代码PHP_FUNCTION(print_r)定位

//还有种更简单的方法，增加 zif_ 前缀，可以直接定位到PHP_FUNCTION(php函数名)

b zif_print_r

//在断点处暂停后可以通过l(list)来查看上下文源码

//也可以通过 l 文件:行号或 l 函数名来查看指定位置的源代码

l basic_functions.c:5475

l zif_print_r

//在断点处p(print_r)可以打印list处源码的变量值

p do_return

//如果打印出来的值不符合预期，可以用set进行动态设置调试

set do_return=13

//观察l出来的变量，如果变量被修改过，会把Old value和New value都输出

watch do_return

//(bt)backtrace查看程序执行的堆栈信息

//finish执行到当前函数的结束

//q(quit)退出

//gdb调试进程gdb -p 进程ID

php扩展类

在 2016年7月7日2016年7月12日上张贴由 BestLove

/*
  +----------------------------------------------------------------------+
  | PHP Version 7                                                        |
  +----------------------------------------------------------------------+
  | Copyright (c) 1997-2016 The PHP Group                                |
  +----------------------------------------------------------------------+
  | This source file is subject to version 3.01 of the PHP license,      |
  | that is bundled with this package in the file LICENSE, and is        |
  | available through the world-wide-web at the following url:           |
  | http://www.php.net/license/3_01.txt                                  |
  | If you did not receive a copy of the PHP license and are unable to   |
  | obtain it through the world-wide-web, please send a note to          |
  | license@php.net so we can mail you a copy immediately.               |
  +----------------------------------------------------------------------+
  | Author:                                                              |
  +----------------------------------------------------------------------+
*/

/* $Id$ */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "php.h"
#include "php_ini.h"
#include "ext/standard/info.h"
#include "php_myclass.h"

static int le_myclass;

//声明zend_class_entry结构体的指针，用于指向自定义类(下面会讲到)
zend_class_entry * myclass_ce;
//声明自定义类方法setField
PHP_METHOD(myclass, setField);
//指定类方法参数
//第一个参数与myclass_methods中对应
//第二、三参数填0即可
//第四个参数表示方法参数的个数
ZEND_BEGIN_ARG_INFO_EX(arginfo_myclass_setField, 0, 0, 1)
//第一个参数表示是否引用传递方法参数
//第二个参数与类方法实现中的参数指针名一致
    ZEND_ARG_INFO(0, fieldName)
ZEND_END_ARG_INFO()
//注册类方法(类名，方法名，与上面参数指定一致，访问类型)
const zend_function_entry myclass_methods[] = {
    PHP_ME(myclass, setField, arginfo_myclass_setField, ZEND_ACC_PUBLIC)
    //下面这行告诉Zend引擎函数列表已完毕
    {NULL, NULL, NULL}
};
//实现类方法(类名，方法名)
PHP_METHOD(myclass, setField)
{
    char * fieldName=NULL;
    size_t fieldName_len;
    if (zend_parse_parameters(ZEND_NUM_ARGS(), "s", &fieldName, &fieldName_len) == FAILURE) {
        return;
    }
    //将参数设置为字段field的值
    zend_update_property_string(myclass_ce,  getThis(), "field", sizeof("field") - 1, fieldName);
}

PHP_MINIT_FUNCTION(myclass)
{
    // 声明zend_class_entry结构体(zend.h中可以看到结构)
    zend_class_entry ce;
    // 初始化类
    // 第一个参数：类容器(就是上面声明的结构)
    // 第二个参数：类名
    // 第三个参数：上面注册的zend_function_entry数组，用于存放自定义方法
    INIT_CLASS_ENTRY(ce, "myclass", myclass_methods);
    // 注册类
    // 返回一个zend_class_entry的指针，指向上面声明的myclass_ce
    myclass_ce = zend_register_internal_class(&ce);
    // 定义属性
    // 第一个参数：注册类后返回的zend_class_entry指针
    // 第二个参数：属性名
    // 第三个参数：属性名的长度
    // 第四个参数：属性的访问类型
    zend_declare_property_null(myclass_ce, "field", sizeof("field") - 1, ZEND_ACC_PUBLIC);
    return SUCCESS;
}

PHP_MSHUTDOWN_FUNCTION(myclass)
{
	return SUCCESS;
}

PHP_RINIT_FUNCTION(myclass)
{
#if defined(COMPILE_DL_MYCLASS) && defined(ZTS)
	ZEND_TSRMLS_CACHE_UPDATE();
#endif
	return SUCCESS;
}

PHP_RSHUTDOWN_FUNCTION(myclass)
{
	return SUCCESS;
}

PHP_MINFO_FUNCTION(myclass)
{
	php_info_print_table_start();
	php_info_print_table_header(2, "myclass support", "enabled");
	php_info_print_table_end();
}

zend_module_entry myclass_module_entry = {
	STANDARD_MODULE_HEADER,
	"myclass",
	NULL,      //NULL表示没有扩展函数，如果需要在类外写扩展函数，填myclass_functions，然后实现后注册它
	PHP_MINIT(myclass),
	PHP_MSHUTDOWN(myclass),
	PHP_RINIT(myclass),		
	PHP_RSHUTDOWN(myclass),	
	PHP_MINFO(myclass),
	PHP_MYCLASS_VERSION,
	STANDARD_MODULE_PROPERTIES
};

#ifdef COMPILE_DL_MYCLASS
#ifdef ZTS
ZEND_TSRMLS_CACHE_DEFINE()
#endif
ZEND_GET_MODULE(myclass)
#endif

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

+----------------------------------------------------------------------+

| PHP Version 7 |

+----------------------------------------------------------------------+

| This source file is subject to version 3.01 of the PHP license, |

| that is bundled with this package in the file LICENSE, and is |

| available through the world-wide-web at the following url: |

| http://www.php.net/license/3_01.txt |

| If you did not receive a copy of the PHP license and are unable to |

| obtain it through the world-wide-web, please send a note to |

| license@php.net so we can mail you a copy immediately. |

+----------------------------------------------------------------------+

| Author: |

+----------------------------------------------------------------------+

/* $Id$ */

#ifdef HAVE_CONFIG_H

#include "config.h"

#endif

#include "php.h"

#include "php_ini.h"

#include "ext/standard/info.h"

#include "php_myclass.h"

static int le_myclass;

//声明zend_class_entry结构体的指针，用于指向自定义类(下面会讲到)

zend_class_entry * myclass_ce;

//声明自定义类方法setField

PHP_METHOD(myclass, setField);

//指定类方法参数

//第一个参数与myclass_methods中对应

//第二、三参数填0即可

//第四个参数表示方法参数的个数

ZEND_BEGIN_ARG_INFO_EX(arginfo_myclass_setField, 0, 0, 1)

//第一个参数表示是否引用传递方法参数

//第二个参数与类方法实现中的参数指针名一致

ZEND_ARG_INFO(0, fieldName)

ZEND_END_ARG_INFO()

//注册类方法(类名，方法名，与上面参数指定一致，访问类型)

const zend_function_entry myclass_methods[] = {

PHP_ME(myclass, setField, arginfo_myclass_setField, ZEND_ACC_PUBLIC)

//下面这行告诉Zend引擎函数列表已完毕

{NULL, NULL, NULL}

};

//实现类方法(类名，方法名)

PHP_METHOD(myclass, setField)

{

char * fieldName=NULL;

size_t fieldName_len;

if (zend_parse_parameters(ZEND_NUM_ARGS(), "s", &fieldName, &fieldName_len) == FAILURE) {

return;

}

//将参数设置为字段field的值

zend_update_property_string(myclass_ce, getThis(), "field", sizeof("field") - 1, fieldName);

}

PHP_MINIT_FUNCTION(myclass)

{

// 声明zend_class_entry结构体(zend.h中可以看到结构)

zend_class_entry ce;

// 初始化类

// 第一个参数：类容器(就是上面声明的结构)

// 第二个参数：类名

// 第三个参数：上面注册的zend_function_entry数组，用于存放自定义方法

INIT_CLASS_ENTRY(ce, "myclass", myclass_methods);

// 注册类

// 返回一个zend_class_entry的指针，指向上面声明的myclass_ce

myclass_ce = zend_register_internal_class(&ce);

// 定义属性

// 第一个参数：注册类后返回的zend_class_entry指针

// 第二个参数：属性名

// 第三个参数：属性名的长度

// 第四个参数：属性的访问类型

zend_declare_property_null(myclass_ce, "field", sizeof("field") - 1, ZEND_ACC_PUBLIC);

return SUCCESS;

}

PHP_MSHUTDOWN_FUNCTION(myclass)

{

return SUCCESS;

}

PHP_RINIT_FUNCTION(myclass)

{

#if defined(COMPILE_DL_MYCLASS) && defined(ZTS)

ZEND_TSRMLS_CACHE_UPDATE();

#endif

return SUCCESS;

}

PHP_RSHUTDOWN_FUNCTION(myclass)

{

return SUCCESS;

}

PHP_MINFO_FUNCTION(myclass)

{

php_info_print_table_start();

php_info_print_table_header(2, "myclass support", "enabled");

php_info_print_table_end();

}

zend_module_entry myclass_module_entry = {

STANDARD_MODULE_HEADER,

"myclass",

NULL, //NULL表示没有扩展函数，如果需要在类外写扩展函数，填myclass_functions，然后实现后注册它

PHP_MINIT(myclass),

PHP_MSHUTDOWN(myclass),

PHP_RINIT(myclass),

PHP_RSHUTDOWN(myclass),

PHP_MINFO(myclass),

PHP_MYCLASS_VERSION,

STANDARD_MODULE_PROPERTIES

};

#ifdef COMPILE_DL_MYCLASS

#ifdef ZTS

ZEND_TSRMLS_CACHE_DEFINE()

#endif

ZEND_GET_MODULE(myclass)

#endif

<?php 
//类名不区分大小写
$a = new MyClass();
//输出NULL
var_dump($a->field);
$a->setField("a");
//输出a
var_dump($a->field);

<?php

//类名不区分大小写

$a = new MyClass();

//输出NULL

var_dump($a->field);

$a->setField("a");

//输出a

var_dump($a->field);

php运行流程

在 2016年7月6日2016年7月6日上张贴由 BestLove

#php的生命周期，无论从init脚本中调用还是从命令行启动
#都会依次经过Module init、Request init、Request shutdown、Module shutdown
#当然，这之间还会执行脚本自己的逻辑。
#两种init和两种shutdown各执行多少次、各自的执行频率，取决于php用什么SAPI与宿主通信
#最常见的四种启动php的方式如下：
#直接以CLI/CGI模式调用
#多进程模块
#多线程模块
#Embedded(嵌入式，在自己的C程序中调用Zend Engine)

#SAPI(Server abstraction API，服务器抽象化接口)提供一个接口，使PHP可以和其他应用进行交互数据

#命令行运行一个php程序的主要流程如下(php5)：
php -f test.php
Call each extension's MINIT                 '//
//上面过程在扩展被载入时调用，一般写在扩展的以下函数中
PHP_MINIT_FUNCTION(myext)
{
    //注册常量或者类等初始化操作
    return SUCCESS;
}
Request test.php
//上面过程请求test.php文件，初始化执行脚本的基本环境(例如创建一个执行环境，
//包括保存PHP运行过程中变量名称和变量值内容的符号表，以及当前所有函数以及类等信息的符号表)
Call each extension's RINIT                 '//
//然后PHP会调用所有模块的RINIT函数，在这个阶段各个模块也可以执行一些相关的操作
PHP_RINIT_FUNCTION(myext)
{
    /*
        例如记录请求开始时间
        随后在请求结束的时候记录结束时间
        这样就能够记录下处理请求所花费的时间了
    */
    return SUCCESS;
}
Execute test.php
//执行PHP，主要是把PHP编译成Opcodes，然后在PHP虚拟机下执行
Call each extension's RSHUTDOWN             '//
//请求结束(RSHUTDOWN)
PHP_RSHUTDOWN_FUNCTION(myext)
{
    //例如记录请求结束时间，并把相应的信息写入到日志文件中
    return SUCCESS;
}
Finish cleaning up after test.php
//完成清理(回收)
Call each extension's MSHUTDOWN             '//
//SAPI生命周期结束(MSHUTDOWN)
PHP_MSHUTDOWN_FUNCTION(myext)
{
    //注销一些持久化的资源
    return SUCCESS;
}
Terminate php
//结束PHP

#php的生命周期，无论从init脚本中调用还是从命令行启动

#都会依次经过Module init、Request init、Request shutdown、Module shutdown

#当然，这之间还会执行脚本自己的逻辑。

#两种init和两种shutdown各执行多少次、各自的执行频率，取决于php用什么SAPI与宿主通信

#最常见的四种启动php的方式如下：

#直接以CLI/CGI模式调用

#多进程模块

#多线程模块

#Embedded(嵌入式，在自己的C程序中调用Zend Engine)

#SAPI(Server abstraction API，服务器抽象化接口)提供一个接口，使PHP可以和其他应用进行交互数据

#命令行运行一个php程序的主要流程如下(php5)：

php -f test.php

Call each extension's MINIT '//

//上面过程在扩展被载入时调用，一般写在扩展的以下函数中

PHP_MINIT_FUNCTION(myext)

{

//注册常量或者类等初始化操作

return SUCCESS;

}

Request test.php

//上面过程请求test.php文件，初始化执行脚本的基本环境(例如创建一个执行环境，

//包括保存PHP运行过程中变量名称和变量值内容的符号表，以及当前所有函数以及类等信息的符号表)

Call each extension's RINIT '//

//然后PHP会调用所有模块的RINIT函数，在这个阶段各个模块也可以执行一些相关的操作

PHP_RINIT_FUNCTION(myext)

{

例如记录请求开始时间

随后在请求结束的时候记录结束时间

这样就能够记录下处理请求所花费的时间了

return SUCCESS;

}

Execute test.php

//执行PHP，主要是把PHP编译成Opcodes，然后在PHP虚拟机下执行

Call each extension's RSHUTDOWN '//

//请求结束(RSHUTDOWN)

PHP_RSHUTDOWN_FUNCTION(myext)

{

//例如记录请求结束时间，并把相应的信息写入到日志文件中

return SUCCESS;

}

Finish cleaning up after test.php

//完成清理(回收)

Call each extension's MSHUTDOWN '//

//SAPI生命周期结束(MSHUTDOWN)

PHP_MSHUTDOWN_FUNCTION(myext)

{

//注销一些持久化的资源

return SUCCESS;

}

Terminate php

//结束PHP

php扩展入门

在 2016年7月6日2016年7月7日上张贴由 BestLove

#下载相应版本的php源码 php.net
#目录描述
ext         //所有扩展的目录
main        //包含PHP的主要宏定义
pear        //"php扩展与应用库"目录。包含pear核心文件
sapi        //包含不同服务器抽象层的代码
TSRM        //ZEND和PHP的"线程安全资源管理器"目录
Zend        //包含Zend引擎的所有文件。所有Zend API定义和宏等

#重要头文件
main/php.h          //包含绝大部分PHP宏以及PHP API定义
Zend/zend.h         //包含绝大部分Zend宏以及Zend API定义
Zend/zend_API.h     //包含Zend API的定义

#ext目录下执行如下命令(test7是自定义扩展名)
./ext_skel --extname=test7
cd test7
vim config.m4
#去掉--with的注释(如果你的扩展引用一些外部的东西)
PHP_ARG_WITH(test7, for test7 support,
[  --with-test7             Include test7 support])
#或者去掉--enable的注释(否则使用它，如果--enable编译失败，改用--with)
PHP_ARG_ENABLE(test7, whether to enable test7 support,
[  --enable-test7           Enable test7 support])
#接着可以编译测试了，PHP为我们提供了一个测试的扩展函数(confirm_test7_compiled)
phpize
./configure --with-php-config=/usr/local/php/bin/php-config 
make
make install
vim /usr/local/php/etc/php.ini
extension=test7.so
/etc/init.d/php-fpm restart
#编译一个测试php文件
vim test.php
<?php
echo confirm_test7_compiled("hello test");
#测试运行
php test.php
#输出如下：扩展测试成功！
#Congratulations! You have successfully modified ext/test7/config.m4. Module hello test is now compiled into PHP.

#接着我们实现一个自己的扩展函数(test7.c)
#实现自定义扩展函数
PHP_FUNCTION(my_ext_func)
{
    long num1;
    long num2;
    char * s;
    int s_len;
    zend_string *strg;
    // lls表示参数分别为long long string(string必须附加strlen)
    if (zend_parse_parameters(ZEND_NUM_ARGS(), "lls", &num1, &num2, &s, &s_len) == FAILURE) {
        return;
    }
    strg = strpprintf(0, "%s=%d", s, num1 * num2);
    RETURN_STR(strg);
}
#注册自定义扩展函数my_ext_func
const zend_function_entry test7_functions[] = {
    PHP_FE(confirm_test7_compiled,  NULL)       /* For testing, remove later. */
    PHP_FE(my_ext_func,  NULL)
    PHP_FE_END  /* Must be the last line in test7_functions[] */
};
#注意代码顺序，先实现函数，再注册它
#重新make make install 重启php
#修改test.php
<?php
echo my_ext_func(13, 14, "13*14");
#运行php test.php 输出：13*14=182

#下载相应版本的php源码 php.net

#目录描述

ext //所有扩展的目录

main //包含PHP的主要宏定义

pear //"php扩展与应用库"目录。包含pear核心文件

sapi //包含不同服务器抽象层的代码

TSRM //ZEND和PHP的"线程安全资源管理器"目录

Zend //包含Zend引擎的所有文件。所有Zend API定义和宏等

#重要头文件

main/php.h //包含绝大部分PHP宏以及PHP API定义

Zend/zend.h //包含绝大部分Zend宏以及Zend API定义

Zend/zend_API.h //包含Zend API的定义

#ext目录下执行如下命令(test7是自定义扩展名)

./ext_skel --extname=test7

cd test7

vim config.m4

#去掉--with的注释(如果你的扩展引用一些外部的东西)

PHP_ARG_WITH(test7, for test7 support,

[ --with-test7 Include test7 support])

#或者去掉--enable的注释(否则使用它，如果--enable编译失败，改用--with)

PHP_ARG_ENABLE(test7, whether to enable test7 support,

[ --enable-test7 Enable test7 support])

#接着可以编译测试了，PHP为我们提供了一个测试的扩展函数(confirm_test7_compiled)

phpize

./configure --with-php-config=/usr/local/php/bin/php-config

make

make install

vim /usr/local/php/etc/php.ini

extension=test7.so

/etc/init.d/php-fpm restart

#编译一个测试php文件

vim test.php

<?php

echo confirm_test7_compiled("hello test");

#测试运行

php test.php

#输出如下：扩展测试成功！

#Congratulations! You have successfully modified ext/test7/config.m4. Module hello test is now compiled into PHP.

#接着我们实现一个自己的扩展函数(test7.c)

#实现自定义扩展函数

PHP_FUNCTION(my_ext_func)

{

long num1;

long num2;

char * s;

int s_len;

zend_string *strg;

// lls表示参数分别为long long string(string必须附加strlen)

if (zend_parse_parameters(ZEND_NUM_ARGS(), "lls", &num1, &num2, &s, &s_len) == FAILURE) {

return;

}

strg = strpprintf(0, "%s=%d", s, num1 * num2);

RETURN_STR(strg);

}

#注册自定义扩展函数my_ext_func

const zend_function_entry test7_functions[] = {

PHP_FE(confirm_test7_compiled, NULL) /* For testing, remove later. */

PHP_FE(my_ext_func, NULL)

PHP_FE_END /* Must be the last line in test7_functions[] */

};

#注意代码顺序，先实现函数，再注册它

#重新make make install 重启php

#修改test.php

<?php

echo my_ext_func(13, 14, "13*14");

#运行php test.php 输出：13*14=182

二叉搜索树

在 2016年7月5日上张贴由 BestLove

#ifndef _TREE_H_

#define _TREE_H_

#include <stdbool.h>

typedef struct item
{
    char petname[20];
    char petkind[20];
} Item;

#define MAXITEMS 10

typedef struct node
{
    Item item;
    struct node * left;
    struct node * right;
} Node;

typedef struct tree
{
    Node * root;                    //指向树根的指针
    int size;                       //树中项目的个数
} Tree;

/*
    操作：把一个树初始为空树
    操作前：ptree指向一个树
    操作后：该树已被初始化为空树
*/
void InitializeTree(Tree * ptree);

/*
    操作：确定树是否为空
    操作前：ptree指向一个树
    操作后：如果树为空则返回true，否则返回false
*/
bool TreeIsEmpty(const Tree * ptree);

/*
    操作：确定树是否已满
    操作前：ptree指向一个树
    操作后：如果树已满则返回true，否则返回false
*/
bool TreeIsFull(const Tree * ptree);

/*
    操作：确定树中项目的个数
    操作前：ptree指向一个树
    操作后：返回树中项目的个数
*/
int TreeItemCount(const Tree * ptree);

/*
    操作：向树中添加一个项目
    操作前：pi是待添加的项目的地址
            ptree指向一个已经初始化的树
    操作后：如果可能，函数把该项目添加到
            树中并返回true，否则返回false
*/
bool AddItem(const Item * pi, Tree * ptree);

/*
    操作：在树中查找一个项目
    操作前：pi指向一个项目
            ptree指向一个已经初始化的树
    操作后：如果该项目在树中，则函数返回true，
            否则返回false
*/
bool InTree(const Item * pi, const Tree * ptree);

/*
    操作：从树中删除一个项目
    操作前：pi是待删除的项目的地址
            ptree指向一个已经初始化的树
    操作后：如果可能，函数从树中删除该项目
            并返回true，否则返回false
*/
bool DeleteItem(const Item * pi, Tree * ptree);

/*
    操作：把一个函数作用于树中每一个项目
    操作前：ptree指向一棵树
            pfun指向一个没有返回值的函数
            该函数接受一个Item作为参数
    操作后：pfun指向的函数被作用于树中每个项目一次
*/
void Traverse(const Tree * ptree, void(* pfun)(Item item));

/*
    操作：从树中删除所有节点
    操作前：ptree指向一个已经初始化的树
    操作后：该树为空树
*/
void DeleteAll(Tree * ptree);

#endif

#ifndef _TREE_H_

#define _TREE_H_

#include <stdbool.h>

typedef struct item

{

char petname[20];

char petkind[20];

} Item;

#define MAXITEMS 10

typedef struct node

{

Item item;

struct node * left;

struct node * right;

} Node;

typedef struct tree

{

Node * root; //指向树根的指针

int size; //树中项目的个数

} Tree;

操作：把一个树初始为空树

操作前：ptree指向一个树

操作后：该树已被初始化为空树

void InitializeTree(Tree * ptree);

操作：确定树是否为空

操作前：ptree指向一个树

操作后：如果树为空则返回true，否则返回false

bool TreeIsEmpty(const Tree * ptree);

操作：确定树是否已满

操作前：ptree指向一个树

操作后：如果树已满则返回true，否则返回false

bool TreeIsFull(const Tree * ptree);

操作：确定树中项目的个数

操作前：ptree指向一个树

操作后：返回树中项目的个数

int TreeItemCount(const Tree * ptree);

操作：向树中添加一个项目

操作前：pi是待添加的项目的地址

ptree指向一个已经初始化的树

操作后：如果可能，函数把该项目添加到

树中并返回true，否则返回false

bool AddItem(const Item * pi, Tree * ptree);

操作：在树中查找一个项目

操作前：pi指向一个项目

ptree指向一个已经初始化的树

操作后：如果该项目在树中，则函数返回true，

否则返回false

bool InTree(const Item * pi, const Tree * ptree);

操作：从树中删除一个项目

操作前：pi是待删除的项目的地址

ptree指向一个已经初始化的树

操作后：如果可能，函数从树中删除该项目

并返回true，否则返回false

bool DeleteItem(const Item * pi, Tree * ptree);

操作：把一个函数作用于树中每一个项目

操作前：ptree指向一棵树

pfun指向一个没有返回值的函数

该函数接受一个Item作为参数

操作后：pfun指向的函数被作用于树中每个项目一次

void Traverse(const Tree * ptree, void(* pfun)(Item item));

操作：从树中删除所有节点

操作前：ptree指向一个已经初始化的树

操作后：该树为空树

void DeleteAll(Tree * ptree);

#endif

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

//局部数据类型
typedef struct pair
{
   Node * parent;
   Node * child; 
} Pair;

static Node * MakeNode(const Item * pi);
static bool ToLeft(const Item * i1, const Item * i2);
static bool ToRight(const Item * i1, const Item * i2);
static void AddNode(Node * new_node, Node * root);
static void InOrder(const Node * root, void(*pfun)(Item item));
static Pair SeekItem(const Item * pi, const Tree * ptree);
static void DeleteNode(Node **ptr);
static void DeleteAllNodes(Node * ptr);

void InitializeTree(Tree * ptree)
{
    ptree->root = NULL;
    ptree->size = 0;
}

bool TreeIsEmpty(const Tree * ptree)
{
    if (ptree->root == NULL)
    {
        return true;
    } else {
        return false;
    }
}

bool TreeIsFull(const Tree * ptree)
{
    if (ptree->size == MAXITEMS)
    {
        return true;
    } else {
        return false;
    }
}

int TreeItemCount(const Tree * ptree)
{
    return ptree->size;
}

bool AddItem(const Item * pi, Tree * ptree)
{
    Node * new_node;
    if (TreeIsFull(ptree))
    {
        fprintf(stderr, "Tree is full\n");
        return false;
    }
    if (SeekItem(pi, ptree).child != NULL)
    {
        fprintf(stderr, "Attempted to add duplicate item\n");
        return false;
    }
    new_node = MakeNode(pi);
    if (new_node == NULL)
    {
        fprintf(stderr, "Could't create Node\n");
        return false;
    }
    ptree->size++;
    if (ptree->root == NULL)        //树为空树
    {
        ptree->root = new_node;
    } else {
        AddNode(new_node, ptree->root);
    }
    return true;
}

bool InTree(const Item * pi, const Tree * ptree)
{
    return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

bool DeleteItem(const Item * pi, Tree * ptree)
{
    Pair look;
    look = SeekItem(pi, ptree);
    if (look.child == NULL)
    {
        return false;
    }
    if (look.parent == NULL)    //删除根项目
    {
        DeleteNode(&ptree->root);
    } else if(look.parent->left == look.child) {
        DeleteNode(&look.parent->left);
    } else {
        DeleteNode(&look.parent->right);
    }
    ptree->size--;
    return true;
}

void Traverse(const Tree * ptree, void(*pfun)(Item item))
{
    if (ptree != NULL)
    {
        InOrder(ptree->root, pfun);
    }
}

void DeleteAll(Tree * ptree)
{
    if (ptree != NULL)
    {
        DeleteAllNodes(ptree->root);
    }
    ptree->root = NULL;
    ptree->size = 0;
}

static void InOrder(const Node * root, void(*pfun)(Item item))
{
    if (root != NULL)
    {
        InOrder(root->left, pfun);
        (*pfun)(root->item);
        InOrder(root->right, pfun);
    }
}

static void DeleteAllNodes(Node * root)
{
    Node * pright;
    if (root != NULL)
    {
        pright = root->right;
        DeleteAllNodes(root->left);
        free(root);
        DeleteAllNodes(pright);
    }
}

static void AddNode(Node * new_node, Node * root)
{
    // new_node->item的指针，不是new_node的指针->item
    if (ToLeft(&new_node->item, &root->item))
    {
        if (root->left == NULL)                 //空子数
        {
            root->left = new_node;              //因此把节点添加到此处
        } else {
            AddNode(new_node, root->left);      //否则处理该子树
        }
    } else if (ToRight(&new_node->item, &root->item)) {
        if (root->right == NULL)
        {
            root->right = new_node;
        } else {
            AddNode(new_node, root->right);
        }
    } else {                                    //不允许含有相同的项目
        fprintf(stderr, "location error in AddNode()\n");
        exit(1);
    }
}

static bool ToLeft(const Item * i1, const Item * i2)
{
    int comp1;
    if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)
    {
        return true;
    } else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0) {
        return true;
    } else {
        return false;
    }
}

static bool ToRight(const Item * i1, const Item * i2)
{
    int comp1;
    if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)
    {
        return true;
    } else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0) {
        return true;
    } else {
        return false;
    }
}

static Node * MakeNode(const Item * pi)
{
    Node * new_node;
    new_node = (Node *) malloc(sizeof(Node));
    if (new_node != NULL)
    {
        new_node->item = *pi;
        new_node->left = NULL;
        new_node->right = NULL;
    }
    return new_node;
}

static Pair SeekItem(const Item * pi, const Tree * ptree)
{
    Pair look;
    look.parent = NULL;
    look.child = ptree->root;

    if (look.child == NULL)
    {
        return look;
    }
    while(look.child != NULL)
    {
        if (ToLeft(pi, &(look.child->item)))
        {
            look.parent = look.child;
            look.child = look.child->left;
        } else if (ToRight(pi, &(look.child->item))) {
            look.parent = look.child;
            look.child = look.child->right;
        } else {
            //break出循环，说明在树中找到了相关项
            //如果循环到look.child == NULL，表示没有找到相关项
            break;
        }
    }
    return look;
}

static void DeleteNode(Node **ptr)      //ptr是指向目标节点的父节点指针成员的地址
{
    Node * temp;
    puts((*ptr)->item.petname);
    if((*ptr)->left == NULL)
    {
        // 左节点为空，将其右节点顶上
        temp = *ptr;
        *ptr = (*ptr)->right;
    } else if ((*ptr)->right == NULL) {
        // 右节点为空，将其左节点顶上
        temp = *ptr;
        *ptr = (*ptr)->left;
    } else {
        //被删除的节点有两个子节点
        //从左节点起，一路向子节点的右节点寻找，直到找到一个空位(NULL)
        //将右节点顶在左节点的最右子节点的空位上
        //将左节点顶为根节点
        for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)
        {
            continue;
        }
        temp->right = (*ptr)->right;
        temp = *ptr;
        *ptr = (*ptr)->left;
    }
    //释放需要删除的节点(地址指向临时节点)
    free(temp);
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

#include "tree.h"

//局部数据类型

typedef struct pair

{

Node * parent;

Node * child;

} Pair;

static Node * MakeNode(const Item * pi);

static bool ToLeft(const Item * i1, const Item * i2);

static bool ToRight(const Item * i1, const Item * i2);

static void AddNode(Node * new_node, Node * root);

static void InOrder(const Node * root, void(*pfun)(Item item));

static Pair SeekItem(const Item * pi, const Tree * ptree);

static void DeleteNode(Node **ptr);

static void DeleteAllNodes(Node * ptr);

void InitializeTree(Tree * ptree)

{

ptree->root = NULL;

ptree->size = 0;

}

bool TreeIsEmpty(const Tree * ptree)

{

if (ptree->root == NULL)

{

return true;

} else {

return false;

}

bool TreeIsFull(const Tree * ptree)

{

if (ptree->size == MAXITEMS)

{

return true;

} else {

return false;

}

int TreeItemCount(const Tree * ptree)

{

return ptree->size;

}

bool AddItem(const Item * pi, Tree * ptree)

{

Node * new_node;

if (TreeIsFull(ptree))

{

fprintf(stderr, "Tree is full\n");

return false;

}

if (SeekItem(pi, ptree).child != NULL)

{

fprintf(stderr, "Attempted to add duplicate item\n");

return false;

}

new_node = MakeNode(pi);

if (new_node == NULL)

{

fprintf(stderr, "Could't create Node\n");

return false;

}

ptree->size++;

if (ptree->root == NULL) //树为空树

{

ptree->root = new_node;

} else {

AddNode(new_node, ptree->root);

}

return true;

}

bool InTree(const Item * pi, const Tree * ptree)

{

return (SeekItem(pi, ptree).child == NULL) ? false : true;

}

bool DeleteItem(const Item * pi, Tree * ptree)

{

Pair look;

look = SeekItem(pi, ptree);

if (look.child == NULL)

{

return false;

}

if (look.parent == NULL) //删除根项目

{

DeleteNode(&ptree->root);

} else if(look.parent->left == look.child) {

DeleteNode(&look.parent->left);

} else {

DeleteNode(&look.parent->right);

}

ptree->size--;

return true;

}

void Traverse(const Tree * ptree, void(*pfun)(Item item))

{

if (ptree != NULL)

{

InOrder(ptree->root, pfun);

}

void DeleteAll(Tree * ptree)

{

if (ptree != NULL)

{

DeleteAllNodes(ptree->root);

}

ptree->root = NULL;

ptree->size = 0;

}

static void InOrder(const Node * root, void(*pfun)(Item item))

{

if (root != NULL)

{

InOrder(root->left, pfun);

(*pfun)(root->item);

InOrder(root->right, pfun);

}

static void DeleteAllNodes(Node * root)

{

Node * pright;

if (root != NULL)

{

pright = root->right;

DeleteAllNodes(root->left);

free(root);

DeleteAllNodes(pright);

}

static void AddNode(Node * new_node, Node * root)

{

// new_node->item的指针，不是new_node的指针->item

if (ToLeft(&new_node->item, &root->item))

{

if (root->left == NULL) //空子数

{

root->left = new_node; //因此把节点添加到此处

} else {

AddNode(new_node, root->left); //否则处理该子树

}

} else if (ToRight(&new_node->item, &root->item)) {

if (root->right == NULL)

{

root->right = new_node;

} else {

AddNode(new_node, root->right);

}

} else { //不允许含有相同的项目

fprintf(stderr, "location error in AddNode()\n");

exit(1);

}

static bool ToLeft(const Item * i1, const Item * i2)

{

int comp1;

if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)

{

return true;

} else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0) {

return true;

} else {

return false;

}

static bool ToRight(const Item * i1, const Item * i2)

{

int comp1;

if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)

{

return true;

} else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0) {

return true;

} else {

return false;

}

static Node * MakeNode(const Item * pi)

{

Node * new_node;

new_node = (Node *) malloc(sizeof(Node));

if (new_node != NULL)

{

new_node->item = *pi;

new_node->left = NULL;

new_node->right = NULL;

}

return new_node;

}

static Pair SeekItem(const Item * pi, const Tree * ptree)

{

Pair look;

look.parent = NULL;

look.child = ptree->root;

if (look.child == NULL)

{

return look;

}

while(look.child != NULL)

{

if (ToLeft(pi, &(look.child->item)))

{

look.parent = look.child;

look.child = look.child->left;

} else if (ToRight(pi, &(look.child->item))) {

look.parent = look.child;

look.child = look.child->right;

} else {

//break出循环，说明在树中找到了相关项

//如果循环到look.child == NULL，表示没有找到相关项

break;

}

return look;

}

static void DeleteNode(Node **ptr) //ptr是指向目标节点的父节点指针成员的地址

{

Node * temp;

puts((*ptr)->item.petname);

if((*ptr)->left == NULL)

{

// 左节点为空，将其右节点顶上

temp = *ptr;

*ptr = (*ptr)->right;

} else if ((*ptr)->right == NULL) {

// 右节点为空，将其左节点顶上

temp = *ptr;

*ptr = (*ptr)->left;

} else {

//被删除的节点有两个子节点

//从左节点起，一路向子节点的右节点寻找，直到找到一个空位(NULL)

//将右节点顶在左节点的最右子节点的空位上

//将左节点顶为根节点

for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)

{

continue;

}

temp->right = (*ptr)->right;

temp = *ptr;

*ptr = (*ptr)->left;

}

//释放需要删除的节点(地址指向临时节点)

free(temp);

}

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "tree.h"

char menu(void);
void addpet(Tree * pt);
void droppet(Tree * pt);
void showpets(const Tree * pt);
void findpet(const Tree * pt);
void printitem(Item item);
void uppercase(char * str);

int main(int argc, char const *argv[])
{
    /*
            数组                                      链表    
    优点：  C对其直接支持                             运行时决定其大小                            
            提供随机访问                              快速插入和删除元素

    缺点：  编译时决定其大小                          不能随机访问(如果你要
            插入和删除元素很费时                      查找链表中的某个值，需要                  
            (需要在数组头部或中间位置，               遍历链表，直到找到为止)
            插入或删除元素时，需要调整                用户必须提供编程支持
            后面的所有元素)

    总结：如果需要频繁插入和删除元素，并且不需要经常搜索，链表是更好的选择
          如果列表基本稳定，只是偶尔插入或删除一些元素，但却需要经常搜索，则数组是更好的选择

          如果需要两者兼备，二叉搜索树，可能正是你所需要的
          二叉搜索树(binary search tree)是一种结合了折半搜索策略的链接结构
    */
    Tree pets;
    char choice;
    InitializeTree(&pets);
    while((choice = menu()) != 'q')
    {
        switch(choice)
        {
            case 'a': addpet(&pets);break;
            case 'l': showpets(&pets);break;
            case 'f': findpet(&pets);break;
            case 'n': printf("%d pets in club\n", TreeItemCount(&pets));break;
            case 'd': droppet(&pets);break;
            default : puts("switching error");
        }
    }
    DeleteAll(&pets);
    puts("Bye.");
    return 0;
}

char menu(void)
{
    int ch;
    puts("Nerfville Pet Club Membership Program");
    puts("Enter the letter corresponding to your choice");
    puts("a) add a pet");
    puts("l) show list of pets");
    puts("n) number of pets");
    puts("f) find pets");
    puts("d) delete a pet");
    puts("q) quit");

    while((ch = getchar()) != EOF)
    {
        while(getchar() != '\n') continue;  //丢弃输入行的剩余部分
        ch = tolower(ch);
        if (strchr("alrfndq", ch) == NULL)
        {
            puts("Please enter an a,l,f,n,d or q");
        } else {
            break;
        }
    }

    if (ch == EOF)          //令EOF导致程序退出
    {
        ch = 'q';
    }
    return ch;
}

void addpet(Tree * pt)
{
    Item temp;
    if (TreeIsFull(pt))
    {
        puts("No room in the club!");
    } else {
        puts("Please enter name of pet");
        gets(temp.petname);
        puts("Please enter pet kind");
        gets(temp.petkind);
        uppercase(temp.petname);
        uppercase(temp.petkind);
        AddItem(&temp, pt);
    }
}

void showpets(const Tree * pt)
{
    if (TreeIsEmpty(pt))
    {
        puts("No entries!");
    } else {
        Traverse(pt, printitem);
    }
}

void printitem(Item item)
{
    printf("Pet:%-19s Kind:%-19s\n", item.petname, item.petkind);
}

void findpet(const Tree * pt)
{
    Item temp;
    if (TreeIsEmpty(pt))
    {
        puts("No entries!");
        return;
    }
    puts("Please enter name of pet you wish to find");
    gets(temp.petname);
    puts("Please enter pet kind");
    gets(temp.petkind);
    uppercase(temp.petname);
    uppercase(temp.petkind);
    printf("%s the %s\n", temp.petname, temp.petkind);
    if (InTree(&temp, pt))
    {
        printf("is a member\n");
    } else {
        printf("is not a member\n");
    }
}

void droppet(Tree * pt)
{
    Item temp;
    if (TreeIsEmpty(pt))
    {
        puts("No entries");
        return;
    }
    puts("Please enter name of pet you wish to delete");
    gets(temp.petname);
    puts("Please enter pet kind");
    gets(temp.petkind);
    uppercase(temp.petname);
    uppercase(temp.petkind);
    printf("%s the %s\n", temp.petname, temp.petkind);
    if (DeleteItem(&temp, pt))
    {
        printf("is dropped from the club\n");
    } else {
        printf("is not a member\n");
    }
}

void uppercase(char * str)
{
    while(*str)
    {
        *str = toupper(*str);
        str++;
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include "tree.h"

char menu(void);

void addpet(Tree * pt);

void droppet(Tree * pt);

void showpets(const Tree * pt);

void findpet(const Tree * pt);

void printitem(Item item);

void uppercase(char * str);

int main(int argc, char const *argv[])

{

数组链表

优点： C对其直接支持运行时决定其大小

提供随机访问快速插入和删除元素

缺点：编译时决定其大小不能随机访问(如果你要

插入和删除元素很费时查找链表中的某个值，需要

(需要在数组头部或中间位置，遍历链表，直到找到为止)

插入或删除元素时，需要调整用户必须提供编程支持

后面的所有元素)

总结：如果需要频繁插入和删除元素，并且不需要经常搜索，链表是更好的选择

如果列表基本稳定，只是偶尔插入或删除一些元素，但却需要经常搜索，则数组是更好的选择

如果需要两者兼备，二叉搜索树，可能正是你所需要的

二叉搜索树(binary search tree)是一种结合了折半搜索策略的链接结构

Tree pets;

char choice;

InitializeTree(&pets);

while((choice = menu()) != 'q')

{

switch(choice)

{

case 'a': addpet(&pets);break;

case 'l': showpets(&pets);break;

case 'f': findpet(&pets);break;

case 'n': printf("%d pets in club\n", TreeItemCount(&pets));break;

case 'd': droppet(&pets);break;

default : puts("switching error");

}

DeleteAll(&pets);

puts("Bye.");

return 0;

}

char menu(void)

{

int ch;

puts("Nerfville Pet Club Membership Program");

puts("Enter the letter corresponding to your choice");

puts("a) add a pet");

puts("l) show list of pets");

puts("n) number of pets");

puts("f) find pets");

puts("d) delete a pet");

puts("q) quit");

while((ch = getchar()) != EOF)

{

while(getchar() != '\n') continue; //丢弃输入行的剩余部分

ch = tolower(ch);

if (strchr("alrfndq", ch) == NULL)

{

puts("Please enter an a,l,f,n,d or q");

} else {

break;

}

if (ch == EOF) //令EOF导致程序退出

{

ch = 'q';

}

return ch;

}

void addpet(Tree * pt)

{

Item temp;

if (TreeIsFull(pt))

{

puts("No room in the club!");

} else {

puts("Please enter name of pet");

gets(temp.petname);

puts("Please enter pet kind");

gets(temp.petkind);

uppercase(temp.petname);

uppercase(temp.petkind);

AddItem(&temp, pt);

}

void showpets(const Tree * pt)

{

if (TreeIsEmpty(pt))

{

puts("No entries!");

} else {

Traverse(pt, printitem);

}

void printitem(Item item)

{

printf("Pet:%-19s Kind:%-19s\n", item.petname, item.petkind);

}

void findpet(const Tree * pt)

{

Item temp;

if (TreeIsEmpty(pt))

{

puts("No entries!");

return;

}

puts("Please enter name of pet you wish to find");

gets(temp.petname);

puts("Please enter pet kind");

gets(temp.petkind);

uppercase(temp.petname);

uppercase(temp.petkind);

printf("%s the %s\n", temp.petname, temp.petkind);

if (InTree(&temp, pt))

{

printf("is a member\n");

} else {

printf("is not a member\n");

}

void droppet(Tree * pt)

{

Item temp;

if (TreeIsEmpty(pt))

{

puts("No entries");

return;

}

puts("Please enter name of pet you wish to delete");

gets(temp.petname);

puts("Please enter pet kind");

gets(temp.petkind);

uppercase(temp.petname);

uppercase(temp.petkind);

printf("%s the %s\n", temp.petname, temp.petkind);

if (DeleteItem(&temp, pt))

{

printf("is dropped from the club\n");

} else {

printf("is not a member\n");

}

void uppercase(char * str)

{

while(*str)

{

*str = toupper(*str);

str++;

}

唐晓锋–BLOG

This is just a personal note.

月份：2016年7月

简单HashTable(取模法)

gdb简单使用

php扩展类

php运行流程

php扩展入门

二叉搜索树