国产麻豆9l精品三级站,亚洲欧美春色,亚洲全黄一级网站

HuffmanTree的创建及�~�码

Marcky — Mon, 28 Sep 2009 09:49:00 GMT

typedef struct _HTNode {
    unsigned int weight;        /* 权�?nbsp;*/
    unsigned int parent;        /* 父节点烦�?nbsp;*/
    unsigned int lchild;        /* 左孩子烦�?nbsp;*/
    unsigned int rchild;        /* 叛_��子烦�?nbsp;*/
} HTNode, *HuffmanTree;         /* 动态分配数�l�存储哈夫曼�?nbsp;*/

typedef char **HuffmanCode;     /* 动态分配数�l�存储哈夫曼�~�码�?nbsp;*/

/* 从ht�?～n的节点中扑և�权值最��的两个节点�Q�分别存于s1, s2�?nbsp;*/
void Select(HuffmanTree ht, int n, int *s1, int *s2)
{
    int i;

    *s1 = 0;
    *s2 = 0;
    /*讄��s1, s2到开始两个parent�{�于0的节点位�|?/span>*/
    for (i = 1; i <= n; ++i) {
        if (*s1 != 0 && *s2 != 0)
            break;

        if (ht[i].parent == 0)
            *s1 == 0 ? *s1 = i : *s2 = i;
    }
    /*扑և�ht中parent�{�于0�Q�且权值最��的两个节点位置�Q�分别存于s1, s2�?/span>*/
    for ( ; i <= n; ++i) {
        if (ht[i].parent != 0) continue;

        if ( (ht[*s1].weight > ht[*s2].weight) && (ht[*s1].weight > ht[i].weight))
            *s1 = i;
        else if ( (ht[*s2].weight > ht[*s1].weight) && (ht[*s2].weight > ht[i].weight))
            *s2 = i;
    }
}

/* 通过w存储的n个权��|��来创��Z��颗哈夫曼�? ht_ptr指向�q�颗哈夫曼树 */
void CreateHuffmanTree(HuffmanTree *ht_ptr, int *w, int n)
{
    int m;
    int i;
    int s1, s2;
    HuffmanTree p;

    if (n <= 1) return;
    m = 2 * n - 1;              /* n个字�W�，需�?n-1个空间来存储整颗huffman tree */
    *ht_ptr = (HuffmanTree)malloc( (m + 1) * sizeof(HTNode)); /* 0号单元不�?nbsp;*/

    for (p = *ht_ptr + 1, i = 1; i <= n; ++i, ++p, ++w) { /* 初始化数�l�中前n个单元存储的字符 */
        p->weight = *w;
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    for ( ; i <= m; ++i, ++p) { /* 初始化数�l�中剩余的单�?nbsp;*/
        p->weight = 0;
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }

    for (i = n + 1; i <= m; ++i) {
        Select(*ht_ptr, i - 1, &s1, &s2);
        /* 讄��s1, s2的父亲�ؓi */
        (*ht_ptr + s1)->parent = i;
        (*ht_ptr + s2)->parent = i;
        /* 讄��i的左孩子为s1, 叛_��子�ؓs2 */
        (*ht_ptr + i)->lchild = s1;
        (*ht_ptr + i)->rchild = s2;
        /* 讄��i的权��gؓs1, s2之和 */
        (*ht_ptr + i)->weight = (*ht_ptr + s1)->weight + (*ht_ptr + s2)->weight;
    }
}

/* 对ht_ptr存储的哈夫曼树的n个叶子节点进行哈夫曼�~�码 */
void HuffmanCoding(HuffmanTree *ht_ptr, HuffmanCode *hc_ptr, int n)
{
    int i;
    int start;
    char *cd = NULL;

    *hc_ptr = (HuffmanCode)malloc( (n + 1) * sizeof(char *));

    cd = (char *)malloc(n * sizeof(char));
    cd[n - 1] = '\0';

    for (i = 1; i <= n; ++i) {
        start = n - 1;

        int current, father;
        for (current = i, father = (*ht_ptr + i)->parent; /* 从叶子节点开始，�q�取得父节点father */
             father != 0;                                 /* 父节点�ؓ0时及到达了根节点 */
             current = father, father = (*ht_ptr + father)->parent) { /* 逐渐向根节点靠拢 */
            if ( (*ht_ptr + father)->lchild == current) /* 当前节点为左孩子 */
                cd[--start] = '0';
            else
                cd[--start] = '1';

        }

        *(*hc_ptr + i) = (char *)malloc( (n - start) * sizeof(char));
        strcpy(*(*hc_ptr +i), &cd[start]);
    }
    free(cd);
}

Marcky 2009-09-28 17:49 发表评论

Marcky — Thu, 24 Sep 2009 14:33:00 GMT

typedef enum _STATUS {ERROR, OK} STATUS;

typedef struct _BiTNode {
    char data;
    struct _BiTNode *lchild;
    struct _BiTNode *rchild;
} BiTNode, *BiTree;

/*创徏二叉�?/span>*/
STATUS CreateBiTree(BiTree *T)
{/*按先序次序输入二叉树节点的��|��I�格表示�I�树�?/span>*/
    char ch;

    scanf("%c", &ch);
    if (ch == ' ') {
        *T = NULL;
    } else {
        if ( !(*T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(-1);
        (*T)->data = ch;                     //生成根节�?/span>
        CreateBiTree(&((*T)->lchild));       //构造左子树
        CreateBiTree(&((*T)->rchild));       //构造右子树
    }
    return OK;
}

/*中序遍历二叉�?/span>*/
STATUS InOrderTraverse(BiTree *T)
{
    if (*T) {
        if (InOrderTraverse(&((*T)->lchild)))
            printf("%c ", (*T)->data);
            if (InOrderTraverse(&((*T)->rchild)))
                return OK;
        return ERROR;
    } else {
        return OK;
    }
}

Marcky 2009-09-24 22:33 发表评论

Marcky — Wed, 26 Aug 2009 08:44:00 GMT

利用Python的多元赋值方式可以无��M��时中间变量实��C��个变量值的交换�?br>代码�Q?br>

(x, y) = (1, 2) #x = 1, y = 2
(x, y) = (y, x) #x = 2, y = 1

Marcky 2009-08-26 16:44 发表评论

system V IPC —�?�׃�n内存(�?

Marcky — Thu, 20 Aug 2009 06:57:00 GMT

使用�׃�n内存和记录锁实例。本例中�Q�父�q�程创徏一�D�共享内存，然后向其中追加字�W�串"Parent"(在写�?#8220;Parent”的时候，采用一个字�W�一个字�W�的写入�Q�目的是��Z��验证记录锁对父子�q�程同步的正��?�Q�子�q�程向共享内存中�q�加字符�?#8220;Child”�Q�同��h��一个一个的字符写入�Q�。由于记录锁是针�Ҏ(gu��)��件的�Q�所以得先创��Z��个空文�g作�ؓ记录锁的操作对象�Q�作为共享内存访问的辅助工具�Q�如果一个进�E�对�q�个�I�文件加写锁成功后，��开始访问共享内存，讉K��l�束��对文�g解锁�?br>
代码如下�Q?br>

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

#include <unistd.h>
#include <sys/types.h>

#include <sys/wait.h>
#include <fcntl.h>

#include <sys/ipc.h>
#include <sys/shm.h>

#define SHM_SIZE 1024            /* shared memory size(bytes) */
#define SHM_MODE 0600            /* user read/write */

#define WRITE_LOCK(fd) regLock((fd), F_SETLKW, F_WRLCK, 0, SEEK_SET, 0)
#define UN_LOCK(fd) regLock((fd), F_SETLK, F_UNLCK, 0, SEEK_SET, 0)
/* 创徏一个文�?nbsp;*/
int createFile()
{
    int fd;

    if ( (fd = open("/tmp/emptyfile4shm", O_RDWR | O_CREAT, 0666)) < 0) {
        fprintf(stderr, "Create a empty file failed!\n");
        exit(EXIT_FAILURE);
    }

    return fd;
}
/* 在文件fd上加锁或解锁*/
int regLock(int fd, int cmd, int type, off_t offset, int whence, off_t len)
{
    struct flock lock;

    lock.l_type = type;         /* lock type: F_RDLCK, F_WRLCK, F_UNLCK */
    lock.l_start = offset;      /* byte offset relative to l_whence */
    lock.l_whence = whence;    /* it's value : SEEK_SET, SEEK_CUR, SEEK_END */
    lock.l_len = len;           /* bytes (0 means to EOF) */

    return fcntl(fd, cmd, &lock);
}

int main(void)
{
    int shmid;
    int filed;
    pid_t pid;
    char *shmptr = NULL;

    filed = createFile();

    if ( (shmid = shmget(IPC_PRIVATE, SHM_SIZE, SHM_MODE)) < 0) { /* Create shared memory */
        fprintf(stderr, "Create shared memory failed!\n");
        exit(EXIT_FAILURE);
    }

    if ( (pid = fork()) < 0) {  /* Create a child process */
        fprintf(stderr, "Create child process failed!\n");
        exit(EXIT_FAILURE);
    }

    if (pid == 0) {             /* In child process */
        if ( (shmptr = shmat(shmid, 0, 0)) == (void *)-1) {
            fprintf(stderr, "Attached shared memory failed!\n");
            exit(EXIT_FAILURE);
        }
        while (1) {
            WRITE_LOCK(filed);  /* add a write lock to filed */
            /* shared memory 剩余的空间不能存�?Child"字符串和�l�束�W?时就退出��@�?nbsp;*/
            if (SHM_SIZE - strlen(shmptr) < strlen("Child") + 1) break;
            strcat(shmptr, "C"); /* �׃��加了锁，每个Child��会�q�箋出现 */
            strcat(shmptr, "h");
            strcat(shmptr, "i");
            strcat(shmptr, "l");
            strcat(shmptr, "d");
            UN_LOCK(filed);     /* release lock */
        }
        printf("child process:\n\t%s\n", shmptr); /* child process print shared memory */

        exit(0);
    }

    /* In parent process */
    if ( (shmptr = shmat(shmid, 0, 0)) == (void *)-1) { /* Attached shared memory */
        fprintf(stderr, "Attached shared memory failed!\n");
        exit(EXIT_FAILURE);
    }

    while (1) {
        WRITE_LOCK(filed);
        /* shared memory 剩余的空间不能存�?Parent"字符串和�l�束�W?时就退出��@�?nbsp;*/
        if (SHM_SIZE - strlen(shmptr) < strlen("Parent") + 1) break;
        strcat(shmptr, "P");/* �׃��加了锁，每个Parent��会�q�箋出现 */
        strcat(shmptr, "a");
        strcat(shmptr, "r");
        strcat(shmptr, "e");
        strcat(shmptr, "n");
        strcat(shmptr, "t");
        UN_LOCK(filed);
    }
    printf("parent process:\n\t%s\n", shmptr); /* parent print shared memory */

    wait(0);
    exit(0);
}

Marcky 2009-08-20 14:57 发表评论

system V IPC —�?�׃�n内存(�?

Marcky — Thu, 20 Aug 2009 06:48:00 GMT

�׃�n内存允许多个�q�程�׃�n一�l�定的存储区。因为数据不需要在两个�q�程之间�q�行copy�Q�所以这是最快的一�U�IPC。��用共享内存技术的时候，需要掌握好的是多个�q�程之间如何同步。信号量和记录锁可以用来实现�׃�n内存的多个进�E�之间的同步�?br>
linux内核定义的shared memory�l�构shmid_ds如下�Q?br>

struct shmid_ds {
    struct ipc_perm  shm_perm;  /*权限*/
    size_t           shm_segsz; /*大小*/
    pid_t            shm_lpid;
    pid_t            shm_cpid;  /*创徏者pid*/
    shmatt_t         shm_nattch;/*�q�接到此�D�内存的�q�程�?/span>*/
    time_t           shm_atime;
    time_t           shm_dtime;
    time_t           shm_ctime;

};

1、创建或使用一�D�共享内存��用shmget函数�Q�此函数��返回共享内存标�C�符�?br>

#include <sys/shm.h>
int shmget(key_t key, size_t size, int flag);

如果key取��gؓIPC_PRIVATE或者key当前为和特定�c�d��的IPC�l�构相结合，�q�且flag指定了IPC_CREAT位，则创��Z��个新的share memory�l�构�?br>size为共享内存段的长度（字节�Q��?br>
2、对一个共享内存段�q�行操作使用shmctl�?br>

#include <sys/shm.h>
int shmctl(int shmid, int cmd, struct shmid_ds *buf);

shmid指定需要操作的shared memory
cmd指定需要进行的操作
IPC_STAT取得此段的shmid_ds�l�构攑օ�buf中�?br> IPC_SET用buf的��D��|�此�D�中的：shm_perm.uid�Q�shm_perm.gid�Q�shm_perm.mode�?br> IPC_RMID从系�l�中删除此共享内存段�?br> SHM_LOCK��共享内存锁定到内存中�?br> SHM_UNLOCK解锁�׃�n内存�D�c�?br>
3、将一个共享内存段�q�接到自��q��地址�I�间使用shmat�Q?br>

#include <sys/shm.h>
void *shmat(int shmid, const void *addr, int flag);

推荐addr�?��|��此�D�连接到内核选择的第一个可用的地址上。增加程序的可移植性�?br>
4、对�׃�n内存操作�l�束后，要脱��该�D는�shmdt�Q?br>

#include <sys/shm.h>
int shmdt(void *addr);

addr是shmat的返回倹{�?br>

Marcky 2009-08-20 14:48 发表评论

安全讉K��数组的指针类模板

Marcky — Thu, 13 Aug 2009 10:29:00 GMT

在用数组作�ؓ数据�l�构存储数据的时候，一不小心就讉K��界了，�q�类错误有时候很不容易发现。�ؓ此自己封装一个专门用来访问数�l�元素的指针�c�L��ѝ��此�c�L��杉K��要数�l�的元素�c�d��Q��v始地址�Q�大��来构造一个安全的Ptr2T指针对象�Q�此对象讉K��数组的方法不但与普通的指针相同�Q�同时还增加了越界的安全��查�?br>

#include <iostream>
#include <stdexcept>

using namespace std;

template<typename T>
class Ptr2T {
public:
//构造函敎ͼ�形参为数�l��v始地址和大��?/span>
    Ptr2T(T *p, int size)
        : m_p(p), m_array(p), m_size(size) { };

    Ptr2T& operator++();                //前缀++
    const Ptr2T operator++(int);        //后缀++

    Ptr2T& operator--();                //前缀--
    const Ptr2T operator--(int);        //后缀--

    Ptr2T& operator+=(int n);
    Ptr2T& operator -=(int n);
//安全的数�l�元素访问操�?/span>
    T& operator*() const;
private:
    T *m_p;           //讉K��数组的指�?/span>
    T *m_array;       //保存数组的�v始地址
    int m_size;       //保存数组的大��?/span>
};

template<typename T>
inline Ptr2T<T>& Ptr2T<T>::operator++()
{
    m_p += 1;
    return *this;
}

template<typename T>
inline const Ptr2T<T> Ptr2T<T>::operator++(int)
{
    Ptr2T current = *this;
    ++(*this);       //用重载的前缀++来实�?/span>

    return current;
}

template<typename T>
inline Ptr2T<T>& Ptr2T<T>::operator--()
{
    m_p -= 1;
    return *this;
}

template<typename T>
inline const Ptr2T<T> Ptr2T<T>::operator--(int)
{
    Ptr2T current = *this;
    --(*this);       //用重载的前缀--来实�?/span>

    return current;
}

template<typename T>
inline T& Ptr2T<T>::operator*() const
{
    if (m_p < m_array || m_p > m_array + m_size - 1) {  //��界��?/span>
        throw out_of_range("out of range");
    }

    return *m_p;
}

template<typename T>
inline Ptr2T<T>& Ptr2T<T>::operator+=(int n)
{
    m_p += n;
    return *this;
}

template<typename T>
inline Ptr2T<T>& Ptr2T<T>::operator-=(int n)
{
    m_p -= n;
    return *this;
}

template<typename T>
Ptr2T<T> operator+(const Ptr2T<T> &p, const int n)
{
    return Ptr2T<T>(p) += n;   //用重载的+=来实�?/span>
}

template<typename T>
Ptr2T<T> operator+(const int n, const Ptr2T<T> &p)
{
    return p + n;
}

template<typename T>
Ptr2T<T> operator-(const Ptr2T<T> &p, const int n)
{
    return Ptr2T<T>(p) -= n;  //用重载的-=来实�?/span>
}

//使用�Ҏ(gu��)��
int main(void)
{
    char a[5] = {'a', 'b', 'c', 'd', 'e'};
    int b[5] = {1, 2, 3, 4, 5};

    Ptr2T<char> pc(a, 5);
    Ptr2T<int> pi(b, 5);

    cout << *pc++ << endl;
    pi--;
    pi += 2;
    cout << *(pi - 1) << endl;

    *++pi = 100;
    cout << *pi << endl;

    return 0;
}

Marcky 2009-08-13 18:29 发表评论

昄��构造函��C��转换�q�算�W�的合作

Marcky — Thu, 13 Aug 2009 06:39:00 GMT

在设计一个Date�cȝ��时候，我们使用int�c�d��来表�C�年份，如果我们需要对�q�䆾�q�行一些特�D�的操作�Q�如�Q�检查，保护�{�）�Q�就很需要定义一个Year�c�，如下�Q?br>

class Year {
    int m_y;
public:
//explicit限制int到Year的隐式�{�?/span>
    explicit Year(int y)
        : y(m_y) { }
//Year到int的类型�{�?nbsp;
    operator int() const
        { return m_y; }
    //other funtion
}

class Date {
public :
    Date(int d, Month m, Year y);
    //
};

Date d1(1987, feb, 21);   //error, 21不能隐式转换为Year
Date d2(21, feb, Year(1987)); //ok

在这里Year��只是包裹住了int�Q�对int提供一层保护而已。由于operator int()的存在，只要需要，Year可以隐式的�{化�ؓint出现�q�算表达式中参加�q�算。而通过�l�构造函数声明�ؓexplicit�Q�就能够保证�Q�int到Year的�{化只能在明确无误的情况进行，避免了意外的赋倹{�?br>
昄��构造函数和转换�q�算�W�的合作�Q�让Year可以当int使用�Q�同时又对Year�q�行一定的保护。。�?br>

Marcky 2009-08-13 14:39 发表评论

Allocating Arrays Using Placement new (zz)

Marcky — Wed, 12 Aug 2009 16:48:00 GMT

An additional version of operator new enables you to construct an object or an array of objects at a predetermined memory position. This version is called placement new and has many useful applications, including building a custom-made memory pool or a garbage collector. Additionally, it can be used in mission-critical applications because there's no danger of allocation failure; the memory that's used by placement new has already been allocated. Placement new is also faster because the construction of an object on a preallocated buffer takes less time.

You already know how to use placement new to allocate a single object on a predetermined memory address. However, some programming tasks require the allocation of arrays on a predetermined memory address. Here's how you do it.

Placement `new` Overview

Mobile devices, embedded systems and custom garbage collectors are only a few instances of programming environments that may require placement new allocation of arrays. Before I discuss the details of such array allocations, let's remind ourselves briefly how scalar (i.e. non-array) placement new works.

The scalar version of placement new takes a user-supplied address on which it constructs a single object. Unlike the ordinary version of the new operator, placement new doesn't allocate storage for the object; it merely constructs the object on the memory address you provide:

#include <new> //required for using placement new
class Widget {
public:
    Widget();
    virtual ~Widget
    virtual void Draw();
};
char* buf=new char [sizeof (Widget)];//preallocate
Widget* widget= new(buf) Widget; //construct Widget on buf
widget->Draw(); //use Widget

To destroy widget you first have to invoke its destructor explicitly:

widget->~Widget(); //explicit destructor invocation

Next, reclaim the raw memory like this:

delete[] buf;

Array Allocation

Allocating arrays with placement new follows the same steps more or less, but you have to pay attention to additional nuances. Here is a step-by-step guide:

First, allocate a buffer large enough to hold an array of the desired type:

const int ARRSIZE = 15;
char * buf= new [sizeof(Widget)*ARRSIZE];

Don't be tempted to calculate the size manually; always use sizeof to ensure that the buffer is properly aligned and has the right size.

Next, construct an array of ARRSIZE objects on the buffer using placement new[] :

Widget* widgets=new(buf) Widget[ARRSIZE];//construct an array

You can now use the allocated array as usual:

for (int i=0; i<ARRSIZE; i++)
{
 widgets[i].Draw();
}
Make sure that your target class --
Widget in this example -- has a public default constructor. Otherwise, it would be impossible to create arrays thereof.

Destroying the Array

To destroy such an array allocated by placement new you have to call the destructor for each element explicitly:

int i=ARRSIZE;
while (i)
widgets[--i].~Widget();

The while -loop uses a descending order to preserve the canonical destruction order of C++ -- the object that was constructed last must be destroyed first. To comply with this requirement, the element with the highest index is destroyed first.

Finally, you release the raw memory on which the array resided by calling delete[] :

delete[] buf;

Performance Tuning

The array placement new has a potential performance problem: it initializes every element in the array unconditionally. If your app deals with large arrays, this isn't the most efficient way. In some apps only a portion of the array is actually used, and in other apps the elements are assigned a different value immediately after their construction. In these cases, you want to postpone, or even completely avoid, the automatic initialization of array elements. To avoid the initialization of placement new arrays, follow the following steps:

As before, begin with an allocation of a raw buffer with the appropriate size. This time however, use the global operator new instead of the new operator:

Widget * warr=
static_cast<Widget*> (::operator new ( sizeof(Widget)* ARRSIZE));

The global operator new , very much like C's malloc() , merely allocates raw bytes of memory from the free-store, without initializing them. It returns void * rather than Widget* which is why you need to cast the result explicitly.

At this stage, warr is a pointer to raw memory. You can't access its elements because they haven't been initialized yet. To initialize individual elements, call placement new once more, for each element you want initialized:

void assign(Widget arr[], size_t & sz,  const Widget& init)
{
    new (&arr[sz++]) Widget (init); //invoke copy ctor
}

assign() passes the address of an individual element to placement new which in turn invokes Widget 's copy constructor. The copy-constructor initializes that element with init . Using this technique, you can initialize elements selectively, leaving the rest of the array uninitialized.

To destroy such an array, invoke the destructor of every initialized object. Then call the global operator delete to reclaim the raw storage:

void destroy(Widget arr[], size_t & sz)
{
    while (sz)
    {
        arr[--sz].~Widget();//destroy all initialized elements
    }
     ::operator delete (arr); //reclaim raw storage
}

Summary

The techniques I've presented here are bug prone. Therefore, they should be encapsulated in higher-level classes that hide the implementation details from users. These techniques aren't rarely-used as they might seem. STL allocators use them under the hood to avoid object initialization and minimize reallocations.

Marcky 2009-08-13 00:48 发表评论

一个Python文本处理�E�序

Marcky — Wed, 22 Jul 2009 08:33:00 GMT

摘要: 文本内容��Z��行一个单词，如下�Q?
some
are
born
great 阅读全文

Marcky 2009-07-22 16:33 发表评论

国产麻豆9l精品三级站,亚洲欧美春色,亚洲全黄一级网站

HuffmanTree的创建及�~�码

system V IPC —�?�׃�n内存(�?

system V IPC —�?�׃�n内存(�?

安全讉K��数组的指针类模板

昄���构造函��C��转换�q�算�W�的合作

Allocating Arrays Using Placement new (zz)

Placement new Overview

Destroying the Array

Performance Tuning

Summary

一个Python文本处理�E�序

昄��构造函��C��转换�q�算�W�的合作

Placement `new` Overview