汇编写启动代码之关看门狗

本文使用的开发板是九鼎创展的X210 iNand版本。

 

一、查阅数据手册

 

 

由上图可得出以下几点信息:

(1)操作看门狗的寄存器是WTCON

(2)WTCON寄存器的地址是0xE2700000

(3)WTCON的bit5是看门狗的开关,0代表关,1代表开

 

注意:

(1)在S5PV210内部的iROM代码(BL0)中,其实已经将看门狗关闭了,所以启动代码中不去关闭看门狗也没关系。

(2)我们这里将WTCON的所有bit位都置0,因为bit5置0后看门狗就关闭了,其它位的值也就没有意义了。

 

二、代码实现

 

#define WTCON 0xE2700000

.global _start					
_start:
	ldr r0, =WTCON
	ldr r1, =0x0
	str r1, [r0]

    b .

 

 

 

PHP扩展之资源的使用

先描述下{资源}类型在内核中的结构:

//每一个资源都是通过它来实现的。

typedef struct _zend_rsrc_list_entry

{

    void *ptr;

    int type;

    int refcount;

}zend_rsrc_list_entry;

在真实世界中,我们经常需要操作一些不好用标量值表现的数据,比如某个文件的句柄,而对于C来说,它也仅仅是个指针而已。

#include <stdio.h>

int main(void)

{

    FILE *fd;

    fd = fopen(“/home/jdoe/.plan”, “r”);

    fclose(fd);

    return 0;

}

C语言中stdio的文件描述符(file descriptor)是与每个打开的文件相匹配的一个变量,它实际上十一个FILE类型的指针,它将在程序与硬件交互通讯时使用。我们可以使用fopen函数来打开一个文件获取句柄,之后只需把这个句柄传递给feof()、fread()、fwrite()、fclose()之类的函数,便可以对这个文件进行后续操作了。既然这个数据在C语言中就无法直接用标量数据来表示,那我们如何对其进行封装才能保证用户在PHP语言中也能使用到它呢?这便是PHP中资源类型变量的作用了!所以它也是通过一个zval结构来进行封装的。 资源类型的实现并不复杂,它的值其实仅仅是一个整数,内核将根据这个整数值去一个类似资源池的地方寻找最终需要的数据。

资源类型变量的使用

资源类型的变量在实现中也是有类型区分的!为了区分不同类型的资源,比如一个是文件句柄,一个是mysql链接,我们需要为其赋予不同的分类名称。首先,我们需要先把这个分类添加到程序中去。这一步的操作可以在MINIT中来做:

#define PHP_SAMPLE_DESCRIPTOR_RES_NAME “山寨文件描述符”

static int le_sample_descriptor;

ZEND_MINIT_FUNCTION(sample)

{

    le_sample_descriptor = zend_register_list_destructors_ex(NULL, NULL, PHP_SAMPLE_DESCRIPTOR_RES_NAME,module_number);

    return SUCCESS;

}

//附加资料

#define register_list_destructors(ld, pld) zend_register_list_destructors((void (*)(void *))ld, (void (*)(void *))pld, module_number);

ZEND_API int zend_register_list_destructors(void (*ld)(void *), void (*pld)(void *), int module_number);

ZEND_API int zend_register_list_destructors_ex(rsrc_dtor_func_t ld, rsrc_dtor_func_t pld, char *type_name, int module_number);

接下来,我们把定义好的MINIT阶段的函数添加到扩展的module_entry里去,只需要把原来的”NULL, /* MINIT */”一行替换掉即可:

ZEND_MINIT(sample), /* MINIT */

ZEND_MINIT_FUNCTION()宏用来帮助我们定义MINIT阶段的函数,这我们已经在第一章里描述过了,但将会在第12章和第三章有更详细的描述。 What’s important to know at this juncture is that the MINIT method is executed once when your extension is first loaded and before any requests have been received. Here you’ve used that opportunity to register destructor functionsthe NULL values, which you’ll change soon enoughfor a resource type that will be thereafter known by a unique integer ID. 看到zend_register_list_destructors_ex()函数,你肯定会想是不是也存在一个zend_register_list_destructors()函数呢?是的,确实有这么一个函数,它的参数中比前者少了资源类别的名称。那这两这的区别在哪呢?

eaco $re_1;

//resource(4) of type (山寨版File句柄)

echo $re_2;

//resource(4) of type (Unknown)

创建资源

我们在上面向内核中注册了一种新的资源类型,下一步便可以创建这种类型的资源变量了。接下来让我们简单的重新实现一个fopen函数,现在叫sample_open:

PHP_FUNCTION(sample_fopen)

{

    FILE *fp;

    char *filename, *mode;

    int filename_len, mode_len;

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, “ss”,&filename, &filename_len,&mode, &mode_len) == FAILURE)

    {

        RETURN_NULL();

    }

    if (!filename_len || !mode_len)

    {

        php_error_docref(NULL TSRMLS_CC, E_WARNING,”Invalid filename or mode length”);

            RETURN_FALSE;

    }

    fp = fopen(filename, mode);

    if (!fp)

    {

        php_error_docref(NULL TSRMLS_CC, E_WARNING,”Unable to open %s using mode %s”,filename, mode);

            RETURN_FALSE;

    }

    //将fp添加到资源池中去,并标记它为le_sample_descriptor类型的。

    ZEND_REGISTER_RESOURCE(return_value,fp,le_sample_descriptor);

}

如果前面章节的知识你都看过的话,应该可以猜出最后一行代码是干啥的了。它创建了一个新的le_sample_descriptor类型的资源,此资源的值是fp,另外它把这个资源加入到一个存储资源的HashTable中,并把此资源在其中对应的数字Key赋给return_value。

资源并不局限于文件句柄,我们可以申请一块内存,并它指向它的指针来作为一种资源。所以资源可以对应任意类型的数据。

销毁资源

世间万物皆有喜有悲,有生有灭,到了我们探讨如何销毁资源的时候了。最简单的一种莫过于仿照fclose写一个sample_close()函数,在它里面实现对某种{资源:专指PHP的资源类型变量代表的值}的释放。

但是,如果用户端的脚本通过unset()函数来释放某个资源类型的变量会如何呢?它们可不知道它的值最终对应一个FILE指针啊,所以也无法使用fclose()函数来释放它,这个FILE句柄很有可能会一直存在于内存中,直到PHP程序挂掉,由OS来回收。但在一个平常的Web环境中,我们的服务器都会长时间运行的。 难道就没有解决方案了吗?当然不是,谜底就在那个NULL参数里,就是我们在上面为了生成新的资源类型,调用的zend_register_list_destructors_ex()函数的第一个参数和第二个参数。这两个参数都各自代表一个回调参数。第一个回调函数会在脚本中的相应类型的资源变量被释放掉的时候触发,比如作用域结束了,或者被unset()掉了。

第二个回调函数则是用在一个类似于长链接类型的资源上的,也就是这个资源创建后会一直存在于内存中,而不会在request结束后被释放掉。它将会在Web服务器进程终止时调用,相当于在MSHUTDOWN阶段被内核调用。有关persistent resources的事宜,我们将在下一节里详述。

我们先来定义第一种回调函数。

static void php_sample_descriptor_dtor(zend_rsrc_list_entry *rsrc TSRMLS_DC)

{

    FILE *fp = (FILE*)rsrc->ptr;

    fclose(fp);

}

然后用它替换掉zend_register_list_destructors_ex()函数的第一个参数NULL:

le_sample_descriptor = zend_register_list_destructors_ex(

        php_sample_descriptor_dtor,

        NULL,

        PHP_SAMPLE_DESCRIPTOR_RES_NAME,

        module_number);

现在,如果脚本中得到了一个上述类型的资源变量,当它被unset的时候,或者因为作用域执行完被内核释放掉的时候都会被内核调用底层的php_sample_descriptor_dtor来预处理它。这样一来,貌似我们根本就不需要sample_close()函数了!

< php

  $fp = sample_fopen(“/home/jdoe/notes.txt”, “r”);

  unset($fp);

 >

unset($fp)执行后,内核会自动的调用php_sample_descriptor_dtor函数来清理这个变量对应的一些数据。 当然,事情绝对没有这么简单,让我们先记住这个疑问,继续往下看。

Decoding Resources

我们把资源变量比作书签,可如果仅有书签的话绝对没有任何作用啊!我们需要通过书签找到相应的页才行。对于资源变量,我们必须能够通过它找到相应的最终数据才行!

ZEND_FUNCTION(sample_fwrite)

{

    FILE *fp;

    zval *file_resource;

    char *data;

    int data_len;

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, “rs”,&file_resource, &data, &data_len) == FAILURE )

    {

        RETURN_NULL();

    }

    /* Use the zval* to verify the resource type and

     * retrieve its pointer from the lookup table */

    ZEND_FETCH_RESOURCE(fp,FILE*,&file_resource,-1,PHP_SAMPLE_DESCRIPTOR_RES_NAME,le_sample_descriptor);

    

    /* Write the data, and

     * return the number of bytes which were

     * successfully written to the file */

    RETURN_LONG(fwrite(data, 1, data_len, fp));

}

zend_parse_parameters()函数中的r占位符代表着接收资源类型的变量,它的载体是一个zval*。然后让我们看一下ZEND_FETCH_RESOURCE()宏函数。

#define ZEND_FETCH_RESOURCE(rsrc, rsrc_type, passed_id,default_id, resource_type_name, resource_type)

    rsrc = (rsrc_type) zend_fetch_resource(passed_id TSRMLS_CC,default_id, resource_type_name, NULL,1, resource_type);

    ZEND_VERIFY_RESOURCE(rsrc);

//在我们的例子中,它是这样的:

fp = (FILE*) zend_fetch_resource(&file_descriptor TSRMLS_CC, -1,PHP_SAMPLE_DESCRIPTOR_RES_NAME, NULL,1, le_sample_descriptor);

if (!fp)

{

    RETURN_FALSE;

}

zend_fetch_resource()是对zend_hash_find()的一层封装,它使用一个数字key去一个保存各种{资源}的HashTable中寻找最终需要的数据,找到之后,我们用ZEND_VERIFY_RESOURCE()宏函数校验一下这个数据。从上面的代码中我们可以看出,NULL、0是绝对不能作为一种资源的。 上面的例子中,zend_fetch_resource()函数首先获取le_sample_descriptor代表的资源类型,如果资源不存在或者接收的zval不是一个资源类型的变量,它便会返回NULL,并抛出相应的错误信息。 最后的ZEND_VERIFY_RESOURCE()宏函数如果检测到错误,便会自动返回,使我们可以从错误检测中脱离出来,更加专注于程序的主逻辑。现在我们已经获取到了相应的FILE*了,下面就用fwrite()向其中写入点数据吧!。

To avoid having zend_fetch_resource() generate an error on failure, simply pass NULL for the resource_type_name parameter. Without a meaningful error message to display, zend_fetch_resource() will fail silently instead.

我们也可以通过另一种方法来获取我们最终想要的数据。

ZEND_FUNCTION(sample_fwrite)

{

    FILE *fp;

    zval *file_resource;

    char *data;

    int data_len, rsrc_type;

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, “rs”,&file_resource, &data, &data_len) == FAILURE ) {

        RETURN_NULL();

    }

    fp = (FILE*)zend_list_find(Z_RESVAL_P(file_resource),&rsrc_type);

    if (!fp || rsrc_type != le_sample_descriptor) {

        php_error_docref(NULL TSRMLS_CC, E_WARNING,”Invalid resource provided”);

        RETURN_FALSE;

    }

    RETURN_LONG(fwrite(data, 1, data_len, fp));

}

可以根据自己习惯来选择到底使用哪一种形式,不过推荐使用ZEND_FETCH_RESOURCE()宏函数。

Forcing Destruction

在上面我们还有个疑问没有解决,就是类似于我们上面实现的unset($fp)真的是万能的么?当然不是,看一下下面的代码:

< php

  $fp = sample_fopen(“/home/jdoe/world_domination.log”, “a”);

  $evil_log = $fp;

  unset($fp);

 >

这次,$fp和$evil_log共用一个zval,虽然$fp被释放了,但是它的zval并不会被释放,因为$evil_log还在用着。也就是说,现在$evil_log代表的文件句柄仍然是可以写入的!所以为了避免这种错误,真的需要我们手动来close it!sample_close()函数是必须存在的!

PHP_FUNCTION(sample_fclose)

{

    FILE *fp;

    zval *file_resource;

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, “r”,&file_resource) == FAILURE ) {

        RETURN_NULL();

    }

    

    /* While it’s not necessary to actually fetch the

     * FILE* resource, performing the fetch provides

     * an opportunity to verify that we are closing

     * the correct resource type. */

    ZEND_FETCH_RESOURCE(fp, FILE*, &file_resource, -1,PHP_SAMPLE_DESCRIPTOR_RES_NAME, le_sample_descriptor);

    

    /* Force the resource into self-destruct mode */

    zend_hash_index_del(&EG(regular_list),Z_RESVAL_P(file_resource));

    RETURN_TRUE;

}

这个删除操作也再次说明了资源数据是保存在HashTable中的。虽然我们可以通过zend_hash_index_find()或者zend_hash_next_index_insert()之类的函数操作这个储存资源的HashTable,但这绝不是一个好主意,因为在后续的版本中,PHP可能会修改有关这一部分的实现方式,到那时上述方法便不起作用了,所以为了更好的兼容性,请使用标准的宏函数或者api函数。 当我们在EG(regular_list)这个HashTable中删除数据的时候,回调用一个dtor函数,它根据资源变量的类别来调用相应的dtor函数实现,就是我们调用zend_register_list_destructors_ex()函数时的第一个参数。

在很多地方,我们都会看到一个专门用来删除的zend_list_delete()宏函数,因为它考虑了资源数据自己的引用计数。

线性表的顺序存储—顺序表

      线性表的顺序存储结构:把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。

      这样,线性表中第一个元素的存储位置就是指定的存储位置,第i+1个元素(1≤i≤n-1)的存储位置紧接在第i个元素的存储位置的后面。

      说明:由于C中数组的下标从0开始,线性表的第i个元素ai存放顺序表的第i-1位置上。为了清楚,将ai在逻辑序列中的位置称为逻辑位序,在顺序表中的位置称为物理位序。

线性表<—-> 逻辑结构

顺序表 <—> 存储结构

 

优点:

无须为表示表中元素之间的逻辑关系而增加额外的存储空间。

可以快速地存取表中任意位置的元素。

 

缺点:

插入和删除操作需要移动大量元素。

当线性表长度变化较大时,难以确定存储空间的容量。

容易造成存储空间的“碎片”。

 

 

#define LIST_INIT_SIZE 100  // 线性表存储空间的初始分配量
#define LISTINCREMENT 10    // 线性表存储空间的分配增量
#define OK 0
#define ERROR 1
#define OVERFLOW 0
typedef int ElemType;

/** 线性表的动态分配顺序存储结构 */
typedef struct
{
    ElemType *elem;  // 存储空间基址
    int length;  // 当前长度
    int listsize;  //当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;

/*************************************************
 * Function: InitList
 * Description: 初始化空间
 * param: L SqList* 顺序表
 * Return: int
 * Others: 时间复杂度为O(1)
 *************************************************/
int InitList(SqList *L)
{
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if(!L->elem)
        exit(OVERFLOW);  //存储分配失败
    L->length = 0;  // 空表长度为0
    L->listsize = LIST_INIT_SIZE;  // 初始存储容量
    return OK;
}
/*************************************************
 * Function: AddListSize
 * Description: 为顺序表增加空间
 * param: L SqList* 顺序表
 * Return: int
 * Others: 时间复杂度为O(1)
 *************************************************/
int AddListSize(SqList *L)
{
    ElemType *newbase = (ElemType *)realloc(L->elem,(L->listsize + LISTINCREMENT) * sizeof(ElemType));
    if(!newbase)
    {
        exit(OVERFLOW);
    }
    L->elem = newbase;
    L->listsize += LISTINCREMENT;
    return OK;
}
/*************************************************
 * Function: CreateList
 * Description: 为顺序表赋值
 * param: L SqList* 顺序表
          a[] ElemType 数组
          n int 长度
 * Others: 时间复杂度为O(n)
 *************************************************/
void CreateList(SqList *L, ElemType a[], int n)
{
    int i;

    /** 如果顺序表没有容量,初始化容量 */
    if(L->listsize == 0)
    {
        InitList(L);  //调用初始化函数
    }

    /** 如果顺序表的容量小于长度,增加容量 */
    if(L->listsize < n)
    {
        AddListSize(L);  // 调用增加容量函数
    }

    /** 顺序表赋值 */
    for(i = 0; i < n; i++)
    {
        L->elem[i] = a[i];
    }
    L->length = n;  // 线性表长度赋值
}

 /*************************************************
 * Function: ListInSert
 * Description: 在顺序表中第i个位置前插入新元素e,
 * param: L SqList* 顺序表
 *        i int 插入的位置
 *        e ElemType 插入的元素
 * Return: int
 * Others: 时间复杂度为O(n)
 *************************************************/
int ListInSert(SqList *L, int i, ElemType e)
{
    int k;

    /** 如果顺序表的长度大于或等于现象表的容量,增加容量 */
    if(L->length >= L->listsize)
    {
        AddListSize(L);  // 调用增加容量函数
    }

    /** 位置应该从1开始到表长+1,位置i如果小于1或者大于顺序表的长度,函数结束 */
    if(i < 1 || i > L->length+1)
    {
        return ERROR;
    }

    /** 插入位置以及之后的元素后移 */
    for(k = L->length-1; k >= i-1; k--)  //
    {
        L->elem[k+1] = L->elem[k];
    }
    L->elem[i-1] = e;  // 插入元素
    L->length +=1;  //表长加1
    return OK;
}

/*************************************************
 * Function: ListDelete
 * Description: 删除顺序表中第i个位置的元素并将删除的元素赋值给e
 * param: L SqList* 顺序表
 *        i int 删除的位置
 *        e ElemType 删除的元素
 * Return: int
 * Others: 时间复杂度为O(n)
 *************************************************/
int ListDelete(SqList *L, int i, ElemType *e)
{
    int k;

    /** 如果顺序表的长度为零,顺序表中没有元素,函数结束 */
    if(L->length == 0)
    {
        return ERROR;
    }

    /** 位置应该从1开始到表长+1,位置i如果小于1或者大于顺序表的长度,函数结束 */
    if(i < 1 || i > L->length)
    {
        return ERROR;
    }

    *e = L->elem[i-1];  // 将删除的元素给e

    /** 删除位置之后的元素前移 */
    for(k = i; k < L->length; k++)
    {
        L->elem[k-1] = L->elem[k];
    }
    L->length--;  // 线性表的长度-1
    return OK;
}

/*************************************************
 * Function: DestroyList
 * Description: 删除顺序表,释放存储空间
 * param: L SqList* 顺序表
 * Return: int
 * Others: 时间复杂度为O(1)
 *************************************************/
void DestroyList(SqList *L)
{
    L->length = 0; // 长度0
    L->listsize = 0; // 容量0
    free(L);  // 释放空间
}

/*************************************************
 * Function: ClearList
 * Description: 清空顺序表中的元素
 * param: L SqList* 顺序表
 * Return: int
 * Others: 时间复杂度为O(1)
 *************************************************/
int ClearList(SqList *L)
{
    L->length = 0;  // 线性表的长度设置为0
    return OK;
}

/*************************************************
 * Function: ListEmpty
 * Description: 顺序表是否为空
 * param: L SqList* 顺序表
 * Return: int 0代表顺序表为空,1代表顺序表不为空
 * Others: 时间复杂度为O(1)
 *************************************************/
int ListEmpty(SqList *L)
{
    if(L->length >0)
    {
        return ERROR;
    }
    else
    {
        return OK;
    }
}

/*************************************************
 * Function: ListLength
 * Description: 顺序表的长度
 * param: L SqList* 顺序表
 * Return: int 顺序表的长度
 * Others: 时间复杂度为O(1)
 *************************************************/
int ListLength(SqList *L)
{
    return L->length;
}

/*************************************************
 * Function: GetElem
 * Description: 获取顺序表中第i个位置的元素,并赋值给e
 * param: L SqList* 顺序表
 *        i int 元素的位置
 *        e ElemType 元素
 * Return: int
 * Others: 时间复杂度为O(1)
 *************************************************/
int GetElem(SqList *L,int i, ElemType *e)
{
    /** 位置应该从1开始到表长+1,位置i如果小于1或者大于顺序表的长度,函数结束 */
    if(i <1 || i > L->length)
    {
        return ERROR;
    }
    *e = L->elem[i-1];  // 逻辑位置i 物理位置应为i-1
    return OK;
}

/*************************************************
 * Function: LocateElem
 * Description: 获取顺序表中元素所在的位置
 * param: L SqList* 顺序表
 *        e ElemType 元素
 * Return: int 元素所在的位置
 * Others: 时间复杂度为O(n)
 *************************************************/
int LocateElem(SqList *L, ElemType e)
{
    int i = 0;

    /** 循环顺序表的长度,找出元素。 */
    while(i < L->length && L->elem[i] != e)
    {
        i++;
    }

    /** 循环结束后,i大于或等于顺序表的长度,说明没有找到,函数结束 */
    if(i >= L->length)
    {
        return ERROR;
    }

    return i+1;  // 逻辑位置i从1开始,物理位置从0开始,返回逻辑位置。
}

/*************************************************
 * Function: DispList
 * Description: 输出显示显示顺序表
 * param: L SqList* 顺序表
 * Others: 时间复杂度为O(n)
 *************************************************/
void DispList(SqList *L)
{
    int i;

    /** 如果顺序表的长度为零,顺序表中没有元素,函数结束 */
    if(L->length == 0)
    {
        return ERROR;
    }

    /** 循环顺序表,输出元素。 */
    for(i = 0; i < L->length; i++)
    {
        printf("%d,",L->elem[i]);
    }
    printf("\n");
}

/*************************************************
 * Function: unionList
 * Description: 合并两个顺序表,将说有在顺序表LB中但不在LA中的元素插入到LA中
 * param: LA SqList* 顺序表
 * param: LB SqList* 顺序表
 * Others: 时间复杂度为O(ListLength(LA)*ListLength(LB))
 *************************************************/
void unionList(SqList *LA, SqList *LB)
{
    int lalen = LA->length;  // 获得顺序表LA的长度
    int lblen = LB->length;  // 获取顺序表LB的长度
    int i;
    ElemType e;

    /** 循环顺序表LB 找出在LB中但不在LA中的元素插入到LA中 */
    for(i = 1; i <= lblen; i++)
    {
        GetElem(LB,i,e);  // 调用GetElem函数,取LB中第i个数据元素赋给e

        /** LA中不存在和e相同者,插入到LA中 */
        if(!LocateElem(LA,e))
        {
            ListInSert(LA,++lalen,e);
        }
    }
}

/*************************************************
 * Function: Inverse
 * Description: 顺序表的逆置
 * param: L SqList* 顺序表
 * Others: 时间复杂度为O(n)
 *************************************************/
void Inverse(SqList *L)
{
    int low=0,high=L->length-1;
    ElemType temp;
    int i;
    for(i=0; i<L->length/2; i++)
    {
        temp=L->elem[low];
        L->elem[low++]=L->elem[high];
        L->elem[high--]=temp;
    }
}
int main()
{
    SqList L;
    int length,a,i,pos;
    ElemType temp;
    InitList(&L);
    printf("请先初始化顺序表\n");
    printf("输入顺序表的长度:");
    scanf("%d",&length);
    printf("输入顺序表的元素:");
    for(i=0; i<length; i++)
    {
        scanf("%d",&temp);
        ListInSert(&L,i+1,temp);
    }
    printf("创建好的顺序表L=");
    DispList(&L);
    while(1)
    {
        printf("功能:\n");
        printf("\t【1】显示顺序表元素\n\t【2】插入元素\n\t【3】删除元素\n\t【4】查找元素\n\t【5】显示顺序表长度\n\t【6】倒置顺序表\n\t【0】退出\n");
        printf("请选择功能:");
        scanf("%d",&a);
        if(a == 0)
        {
            return 0;
        }
        else if(a == 1)
        {
            printf("创建好的顺序表La=");
            DispList(&L);
        }
        else if(a == 2)
        {
            printf("请输入插入位置:");
            scanf("%d",&pos);
            printf("请输入插入元素:");
            scanf("%d",&temp);
            int is = ListInSert(&L,pos,temp);
            if( is == 0)
            {
                printf("插入成功!\n");
            }
            else
            {
                printf("插入失败!\n");
            }
        }
        else if(a == 3)
        {
             printf("请输入删除元素的位置:");
             scanf("%d",&pos);
             int is = ListDelete(&L, pos, &temp);
             if(is == 0)
             {
                 printf("删除的元素为%d!\n",temp);
             }
             else
             {
                 printf("删除失败!\n");
             }
        }
        else if(a == 4)
        {
            printf("请输入要查找的元素:");
            scanf("%d",&temp);
            printf("要查找的元素在:%d\n",LocateElem(&L,temp));
        }
        else if(a == 5)
        {
            printf("顺序表的长度为:%d\n",ListLength(&L));
        }
        else if(a == 6)
        {
            Inverse(&L);
            printf("倒置后的顺序表L=");
            DispList(&L);
        }
    }
    return 0;
}

 

 

二叉树平衡二叉树转载

平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉树:它的左子树和右子树的深度之差的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。

平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1<=bf<=1;

很显然,平衡二叉树是在二叉排序树(BST)上引入的,就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降,那么AVL就保持住了(BST)的最好时间复杂度O(logn),所以每次的插入和删除都要确保二叉树的平衡,那么怎么保持平衡呢?

我努力看了看数据结构上的讲解,但是看的只晕+_+!我对他的讲解很无语,他所谓的“旋转”操作讲的不明不白,看的我气的蛋疼!你说你旋转,你得说清是如何旋转?以那个结点为中心,那些或者说那个结点转了,那些结点不动。你就在哪里旋转来旋转去的,谁知道你是咋转的,你在哪慢慢转吧!哥转不过你,另找高明!于是在网上找啊找,只为想搞明白是到底怎么转的!点击打开链接让我对“旋转”有所领悟,表示感谢!

 

插入时:

那究竟是如何“转”的呢?

 

首先必须明白一个核心操作,不让它叫“旋转”!而叫——>“两个结点的变换”

如图:

就拿第一个来说->点100和101的变换:

点101占据点100的位置,点100换到了101的对面的位置,其他点的相对位置不变。

我们可以更直观的理解为:把101结点“上提”一下!

分析:101>100,所以100可以作为101的左孩子;

也就是在二叉排序树中,两个结点这样的变换操作是可行的,是符合二叉排序树的性质。

不仅这个简单的图,任何复杂的二叉排序树都可以,你可以试试,也许你会说如果点101左边有孩子怎么办?别着急~,当然有办法!

 

下边正式说这个图的四种不平衡情况(插入时)及操作:

首先还需要明白一个概念->最小不平衡子树的根结点:也就是当你进行插入操作时,找到该需要插入结点的位置并插入后,从该结点起向上寻找(回溯),第一个不平衡的结点即平衡因子bf变为-2或2。

为什么要引入这个最小不平衡根结点的概念,因为在插入时,对该子树进行保持平衡操作后,其它的结点的平衡因子不会变,也就是整棵树又恢复平衡了。为什么呢?

你想想不平衡点的bf一定是-2或2吧,经过平衡操作后,他会把一边子树的一个结点分给另一边的子树,也就是一边的深度分给另一边,这样就平衡了!

比如,插入前:左边是深度1,右边深度是0;插入后左边深度是2,右边深度是0,经过平衡后左边深度是1,右边深度是1;

那么你说插入前和插入后该根结点所领导的子树的深度变没??仍是1,显然没变!那么就仍保持了这棵树的平衡了!

 

下面即四种情况分别为:左左、右右、左右、右左,每种情况又有两个图:①、②,①是该情况的最简单的图形,②是该情况的一般的图形;

设x为最小不平衡子树的根结点,y为刚插入的点

 

左左:

即在x的左孩子a的左孩子c上插入一个结点y(该结点也可以是c,如图①),即y可以是c,也可以是c的左孩子(如图②),也可以是c的右孩子(不在画出)

                                  

图①就不用说了,结点x和结点a变换,则树平衡了;那么图②就是树中的一般情况了a结点有右孩子d,那要进行x和a变换,那么a的右孩子放哪啊?

很简单,如图放在x的左孩子上;分析:x>d,d>a,所以d可作为x的左孩子,且可作为a的右孩子中的孩子。下边这样的类似情况不再一一分析,自己分析分析~

实现:找到根结点x,与它的左孩子a进行交换即可使二叉树树再次平衡;

 

 

右右:

即在x的右孩子a的右孩子c上插入一个结点y(该结点也可以是c,如图①),即y可以是c,也可以是c的右孩子(如图②),也可以是c的左孩子(不在画出)

实现:找到根结点x,与它的右孩子a进行交换即可使二叉树树再次平衡;

 

 

左右:

即在x的左孩子a的右孩子c上插入一个结点y(该结点也可以是c,如图①),即y可以是c,也可以是c的右孩子(如图②),也可以是c的左孩子(不在画出)

 

 

这个左右和下边的右左,稍微复杂了点,需要进行两次交换,才能达到平衡,注意这时y是c的右孩子,最终y作为x的左孩子;若y是c的左孩子,最终y作为a

的右孩子,画图分析一下~~下边类似,不再敖述。

 

实现:找到根结点x,让x的左孩子a与x的左孩子a的右孩子c进行交换,然后再让x与x此时的左孩子c进行交换,最终达到平衡;

 

右左:

即在x的右孩子a的左孩子c上插入一个结点y(该结点也可以是c,如图①),即y可以是c,也可以是c的右孩子(如图②),也可以是c的左孩子(不在画出)

 

实现:找到根结点x,让x的右孩子a与x的右孩子a的左孩子c进行交换,然后再让x与x此时的右孩子c进行交换,最终达到平衡;

 

上边的四种情况包含了所有插入时导致不平衡的情况,上面给出的仅仅是一棵大树中的最小不平衡子树,一定要想清楚,别迷了!

另外一定要注意这个交换操作,比如a与b交换(a在上,b在下),b一定要占据a的位置!什么意思?就是b要放在(覆盖)储存a的那块内存上,

再通俗点说,若a是x的左孩子,则交换后b要做x的左孩子;这就是所谓的b占据a的位置!

 

那么如何找到最小不平衡子树的根结点x,并判断出它是属于那种情况的?

 

插入一个结点时,我们首先找到需要插入的位置,并插入;数据结构上用的是递归,不要说递归太浪费时空,你想想一个含2^31个结点的平衡二叉树的深度大约是31吧,它递归再多也不就是31层!而且递归代码短小、精悍、富含艺术之美!所以我认为对于这个平衡二叉树,用递归很合适!

显然插入之后就要检查是否出现不平衡的结点,那么如何检查?

我们知道,你插入的时候用的是递归,一条线找到要插的位置,并插入;那么谁的平衡因子的有可能变呢?

不难想象,只有该条线上的结点的平衡因子有可能改变!那么我们在回溯的时候不就可以找到第一个不平衡的子树的结点?!

可是我们如何判断该结点的平衡因子是否应该改变,显然要看它被插入结点的一边的深度是否增加;

如何看它被插入结点的一边的深度是否增加?

如上图,如何看x的右孩子a(即被插入结点的一边)的深度增加?我们知道在a的右孩子上插入了结点y那么a的bf是一定要减1

那么x结点的bf?可根据a的bf决定是否改变!

若a:bf=-1或1,那么a之前一定为0,表示a的深度增加了,那么x的bf可根据a是x哪一边的孩子决定+1或-1;

若a:bf=0,那么a之前一定为-1或1,表示a的深度每增加,那么不仅x的bf就不用变,该条线上的所有结点的bf都不用变,直接返回即可;

 

当然了,那么找到最小不平衡子树的根结点x了,如何判断它属于哪种不平衡呢?

①根据上边的几种情况,我们需要知道两个方向,在回溯时可以记录一下该结点到下一个结点的方向0:左、1:右为第二个方向,传递给上一层中,那么上层中的方向就是一个方向,有了这两个方向就能确定是哪种不平衡了。

还就上边的图说吧~可以定义一个全局变量secdirection(第二个方向),也可在递归中定义一个局部变量,返回给上一层。在回溯到a中时,secdirection=1,到x的时候

x->a的方向也为1,定义firdirection=1;而这时x:bf=-2;那么就找到了最小不平衡子树的根结点x,又知道了两个方向,那么进行相应的平衡操作不就行了。

②其实我代码中的就是按照①写的,可是刚又想了,其实不用用个变量记录第二个方向,可以根据a的bf确定它的第二个方向,a:bf=-1说明右孩子的深度增加,y加到右孩子上;

a:bf=1;说明左孩子的深度增加,y加到左孩子上;

 

好了,找到了最小不平衡子树的根结点x了,也知道了那种不平衡,调用keepbalance(…)就使树平衡了,可是某些结点的平衡因子在变换是变了~~咋办?

我就是一种一种情况推出来的,不知道别人怎么变的,每一种情况都有固定的几个点变了,变成了一个固定的值!谁有更好的办法,请多多指教!

 

下边一一列出(插入操作中)变换后bf改变的结点及值:

左左:前a->bf=1 后 x->bf=0,a->bf=0;右右:前a->bf=-1 后x->bf=0,a->bf=0;显然左左与右右的x与a变换后的bf都为0;

左右、右左中结点bf的改变要根据之前c的bf!

左右:若c->bf=1,则x->bf=-1,a->bf=0,c->bf=0;若c->bf=-1,则x->bf=0,a->bf=1,c->bf=0;若c->bf=0,则x->bf=0,a->bf=0,c->bf=0;

右左:若c->bf=1,则x->bf=0,a->bf=-1,c->bf=0;若c->bf=-1,则x->bf=1,a->bf=0,c->bf=0;若c->bf=0,则x->bf=0,a->bf=0,c->bf=0;

可以发现,当左右、右左的c->bf相同时x与a的bf刚好取相反的值。

 

好了,到现在插入一个结点的二叉树终于平衡了,相应的平衡因子也修改了!插入算是完成了!!

 

删除时:

删除类似插入的操作,蛋又不同,删除会有一些特殊情况需要特殊处理,当然核心操作“保持平衡”是不变的!

 

删除时少一个结点,也就是该结点所在的子树深度可能会减小,而插入时多一个结点,该结点所在的子树深度可能会增加,

所以递归删除一个结点时,回溯时找到最小不平衡子树的根结点时,要向相反的方向去找属于哪种情况;

如图:

y为要删除的结点;

图①:y结点删除后,回溯到x结点x:bf=-1变为x:bf=-2;则需从相反方向即从x的右孩子的方向向下检查属于哪种情况,显然第一个方向为1:右;

第二个方向看a:bf的值——若为1时,那就相当于插入时‘右左’的情况;若为-1时,那就相当于插入时‘左左’的情况;可现在a:bf既不是1也不是-1

而是0,这就是删除的特殊情况了!我们不妨试试对他进行类似于插入时的‘右右’操作,看怎么样~    如上图,经过变换后该子树平衡了!但是因子的

修改就跟插入时的‘右右’不一样了!此时变为:x:bf=-1,a:bf=1;所以我们不妨就把a:bf=0也归纳为删除的‘右右’或‘左左’(如图②,不再敖述)操作;

那么删除时因子的改变需在插入时因子的改变中添加上:

左左:前a:bf=0 后x:bf=1,a:bf=-1; 右右:前a:bf=0 后x:bf=-1,a:bf=1;其他不变!

 

插入时结束结点平衡因子的修改,直接返回(也就是该树已经平衡了):

回溯时发现儿子结点的平衡因子为0(当发现不平衡结点,并进行平衡操作后,平衡后根结点的bf一定为0,也结束了)

但是删除时结束结点平衡因子的修改,直接返回,就与插入时不一样了:回溯时发现儿子结点的平衡因子为-1或1!

再删除操作中,平衡一个子树后,该子树的深度不一定不变,而只有上边那种特殊情况该子树的深度不变,其他都会变!

可以想象,其实是很简单的道理:除了特殊情况其他都与插入的情况一模一样,说白了就是把深度大的子树(根结点的其中一个)向深度小子树贡献一个深度,

那么这样一来,该子树(对于根结点所领导的树)的深度是不是比原来的小1了?!所以要继续向上一个一个进行检索,直到根结点为止!

 

好了,到这里删除也算是说完了,可以贴代码了吧~

 

平衡二叉树的C实现:

View Code

那个位操作函数,使程序好像很复杂似的,完全可以用一个外部结构体替换!只是我不想用外部变量,尽量在函数内完成吧

由于本人比较笨,写了很长时间~~有什么不正确的,欢迎指正!!!

这些图费了很大功夫才弄好,本来在编辑框里画的好好的,可是一发表,那些图有些就乱了,刚开始我还试着一个一个对照着修改,看最终发现还是不行……最后忽然想到我怎么不在编辑框中截图呢?最后在编辑框中一个一个截图一个一个上传,这样效果好多了!费这么大功夫只为一点:让读者看着舒服,容易理解。

我还想说:开这个博客园以来,也没多长时间,蛋把我气的不浅!每次都是搞好程序,准备到这里写博客时,就是打不开!气死我了!卡死啦!有时候确实是我网速慢,但有时候网速好了也很难打开啊!你说你还是程序员的家园!看你卡的,我都无语了!网速稍微慢点就打不开,就这浪费了我很多时间!我对博客园很失望!!

朋友们,你们感觉呢?

 

转自:http://www.cnblogs.com/fornever/archive/2011/11/15/2249492.html

python调用C程序的结构体和函数

C代码如下:

 

#include <stdio.h>  

  

typedef struct TestDLL_  

{  

    int a;  

    char *b;  

} testdll;  

  

testdll test(testdll t)  

{  

    t.a=t.a+t.a;  

    printf(“%d\n%s\n”,t.a,t.b);  

    return t;  

}

 

python代码如下:

 

from ctypes import *  

 

#绝对路径 

dllpath=’test.dll’  

dll=CDLL(dllpath)  

 

#python内部参数赋值

a=c_int(125)  

b=c_char_p(‘Hello world,Hello Chengdu’)  

  

#定义结构体

class testdll(Structure):  

    _fields_=[(‘a’,c_int),  

             (‘b’,c_char_p)]  

 

#实例化并赋值

t=testdll()  

t.a=a  

t.b=b  

  

#设置返回值类型

dll.test.restype=testdll  

  

#测试

t=dll.test(t)  

print t.a  

print t.b  

x=raw_input(‘any key to continue’)

C语言随笔_printf输出多行

想在printf中,输出多行数据,如果写成下面这样:

printf(“line 1\n

line 2\n

line 3\n”);

编译器会报错“error C2001: newline in constant”。

可以这样写:

printf(“line 1\

line 2\

line 3\n”);

或者

printf(“line 1”

“line 2”

“line 3\n”); 

杭电—2141

Problem Description

Give you three sequences of numbers A, B, C, then we give you a number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X.

Input

There are many cases. Every data case is described as followed: In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers.

Output

For each case, firstly you have to print the case number as the form “Case d:”, then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print “YES”, otherwise print “NO”.

Sample Input

3 3 3

1 2 3

1 2 3

1 2 3

3

1

4

10

Sample Output

Case 1:

NO

YES

NO

运用二分的思想;

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define maxn 510

int a[maxn],b[maxn],c[maxn];

int sum[maxn*maxn];

int bin_search(int y,int cnt)

{

    int left=0,right=cnt-1;

    int mid;

    while(left<=right)

    {

        mid=(left+right)/2;

        if(sum[mid]==y) return 1;

        if(sum[mid]<y) left= mid+1;

        if(sum[mid]>y) right=mid-1;

    }

    return 0;

}

int main ()

{

    int l,m,n;

    int k=1;

    while(~scanf(“%d%d%d”,&l,&m,&n))

    {

        for(int i=0; i<l; i++)

            scanf(“%d”,&a[i]);

        for(int i=0; i<m; i++)

            scanf(“%d”,&b[i]);

        for(int i=0; i<n; i++)

            scanf(“%d”,&c[i]);

        int cnt=0;

        for(int i=0; i<l; i++ )

            for(int j=0; j<m; j++)

            {

                sum[cnt++]=a[i]+b[j];

            }

        sort(sum,sum+cnt);\\sort是一个排序函数,可以自己百度了解一下

        int s;

        scanf(“%d”,&s);

        printf(“Case %d:\n”,k++);

        while(s–)

        {

            int x;

            scanf(“%d”,&x);

            int flag=0;

            for(int i=0; i<n; i++)

            {

                if(bin_search(x-c[i],cnt))

                {

                    flag=1;

                    break;

                }

            }

            if(flag==1)printf(“YES\n”);

            else printf(“NO\n”);

        }

    }

    return 0;

}

\\Ai+Bj+Ck = X可以写成Ai+Bj=X-Ck;

使用switch条件语句需要注意的几点

1. 当满足条件的case中没有break,程序将依次执行其后的每种条件(包括default)直到遇到break跳出

int main()
{
    int n = 1;
    switch(n) {
    case 1:
        printf("--1--\n");
    default:
        printf("default\n");
    case 2:
        printf("--2--\n");
        break;
    case 3:
        printf("--3--\n");

    }

    return 0;
}

输出结果:

–1–

default

–2–

2. 当没有发现满足条件的case,程序将跳转到default,如果default没有break,程序将依次执行其后的每种条件,直到遇到break跳出

int main()
{
    int n = 4;
    switch(n) {
    case 1:
        printf("--1--\n");
    default:
        printf("default\n");
    case 2:
        printf("--2--\n");
    case 3:
        printf("--3--\n");

    }

    return 0;
}

输出结果:

default

–2–

–3–