Just Like That .. (^-^)v

RSA Algorithm Preliminary

ช่วงนี้เขียนโปรแกรมที่บริษัทเกี่ยวกะการทำ licensing ให้ผู้ใช้แล้วเราก็เลยเลือกที่จะใช้ RSA public key encryption ไว้มีเวลาแล้วจะมา อัพเดท




 

Create Date : 16 พฤษภาคม 2549   
Last Update : 16 พฤษภาคม 2549 22:50:44 น.   
Counter : 181 Pageviews.  

เปิด file ใน directory (ภาคต่อ)

ใน blog ที่แล้วผมเขียนให้ เปิด file ใน directory โดยถ้า file ข้างในนั้นไม่เป็น directory แต่ถ้าต้องการให้ traverse ลึกเข้าไปใน directory ข้างในด้วยอาจจะต้องอาศัย recursive มาช่วย เขียนออกมาได้เป็นดังนี้


#include <stdio.h>
#include <fcntl.h>
#include <dirent.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <string.h>

void listfileindir(const char *path);

int main(int argc, char *argv[])
{
if(argc != 2)
{
fprintf(stderr, "%s [dir]\n", argv[0]);
return -1;
}

listfileindir(argv[1]);

return 0;
}

void listfileindir(const char *path)
{
DIR *dir;
struct dirent *dp;
struct stat st;
FILE *fp;
char filename[100] = {0};
dir = opendir(path);

if(dir != NULL)
{
while((dp = readdir(dir)) != NULL)
{
if(!strcmp(dp->d_name, ".") || !strcmp(dp->d_name, ".."))
{
continue;
}
sprintf(filename, "%s/%s", path, dp->d_name);
stat(filename, &st);
if(S_ISREG(st.st_mode))
{
if((fp = fopen(filename, "r")) != NULL)
{
printf("%s\n", filename);
fclose(fp);
}
}
else if(S_ISDIR(st.st_mode))
{
listfileindir(filename);
}
else
{
continue;
}
}
closedir(dir);
}
}




 

Create Date : 15 กุมภาพันธ์ 2549   
Last Update : 15 กุมภาพันธ์ 2549 14:49:09 น.   
Counter : 148 Pageviews.  

เปิด File ใน Directory

เคยเขียนตอบในกระทู้เรื่องการเข้าไป เปิด file ในแต่ละ folder (directory) เลยเอามาลงทิ้งไว้ ใช้ได้บน Solaris, Linux ...


#include <stdio.h>
#include <dirent.h>
#include <sys/types.h>

int main(int argc, char *argv[])
{
DIR *dir;
struct dirent *dp;
FILE *fp;
char filename[100] = {0};

if(argc != 2)
{
fprintf(stderr, "%s <dir>\n", argv[0]);
return -1;
}

dir = opendir(argv[1]);

if(dir != NULL)
{
while((dp = readdir(dir)) != NULL)
{
sprintf(filename, "%s/%s", argv[1], dp->d_name);
if((fp = fopen(filename, "r")) != NULL)
{
printf("%s\n", dp->d_name);
fclose(fp);
}
}
}

closedir(dir);

return 0;
}




 

Create Date : 15 กุมภาพันธ์ 2549   
Last Update : 15 กุมภาพันธ์ 2549 13:18:56 น.   
Counter : 136 Pageviews.  

doubly linked list in C

Code นี้เขียนเอาไว้นานมากแล้วตั้งแต่สมัยเรียน สมัย C++ ยังไม่เริ่มโด่งดัง

ขั้นแรกต้อง คิดก่อนว่า อะไรจะเป็นข้อมูลใน list คิดแบบ abstract ก็คือ node นั่นเอง ก็ทำการ กำหนดขึ้นมาว่า node มันเป็นอย่างไร สามารถทำอะไรมันได้บ้าง โดยสรุปก็คือ node จะประกอบไปด้วยส่วนที่เป็น data และส่วนที่เป็นตัวชี้ไปยัง node อื่น ข้างหน้า และ ข้างหลัง (เพื่อง่ายในการเขียนรูปแบบอื่นต่อไป) และ เืพื่อให้ยืดหยุ่น จึงกำหนด data เป็น (void *)

ก็สรุปออกมาเป็น file node.h


/* node.h */
#ifndef _NODE_H_
#define _NODE_H_
typedef struct node
{
struct node* next;
struct node* prev;
void *data;
} node_t;

node_t* node_create(void *data, int dtsize);

inline int node_delete(node_t *n);
#endif

แล้วก็เขียนโค้ดมันใน file node.c
เมื่อ create node ขึ้นมา ตัว node จะต้องกำหนดค่าที่จะส่งเข้ามา และก็หนด prev และ next ให้เป็น NULL ไปก่อน
เวลา delete node ก็ต้องทำการ free data ก่อนแล้วค่อย ทำลายตัวเองทิ้ง

/* node.c */
#include <stdio.h>
#include <string.h>
#include "node.h"

inline node_t* node_create(void *data, int dtsize)
{
node_t *n;
n = (node_t *)malloc(sizeof(node_t));
n->next = NULL;
n->prev = NULL;
n->data = (void *)malloc(dtsize);
memcpy(n->data, data, dtsize);
return n;
}

inline int node_delete(node_t *n)
{
free(n->data);
free(n);
return 0;
}


เมื่อได้ node แล้ว ต่อไปก็คิดว่า list เราจะมีหน้าตาอย่างไร ในที่นี้จะให้ list เป็นตัว เก็บ node เริ่มต้น และ node ท้ายสุด และมีการเก็บขนาดไว้
ส่วน operation ของ list ก็มีเยอะ (ดูใน code) เช่น add หน้า add หลัง pop หน้า pop หลัง add ที่ตำแหน่งใด ๆ remove ที่ตำแหน่งใด ๆ ฯลฯ


/* list.h */
#ifndef _LIST_H_
#define _LIST_H_

#include "node.h"

typedef struct list
{
struct node* head;
struct node* tail;
int length;
} list_t;

list_t* list_init();

inline int list_add_tail(list_t *l, node_t *n);
inline int list_add_head(list_t *l, node_t *n);

inline node_t* list_pop_tail(list_t *l);
inline node_t* list_pop_head(list_t *l);

inline int list_remove_tail(list_t *l);
inline int list_remove_head(list_t *l);

inline int list_add_nth(list_t *l, int index, node_t *n);
inline node_t* list_pop_nth(list_t *l, int index);
inline int list_remove_nth(list_t *l, int index);

inline int list_deinit(list_t *l);

inline void list_print(list_t *l);
#endif


ส่วนตัวโค้ดก็ตามนี้ อธิบายไม่หมด คงต้องไปศึกษาเพิ่มเติมเอง


/* list.c */
#include <stdio.h>
#include <string.h>
#include "list.h"

inline list_t* list_init()
{
list_t *l;
l = (list_t *)malloc(sizeof(list_t));
l->head = NULL;
l->tail = NULL;
l->length = 0;
return l;
}

inline int list_add_tail(list_t *l, node_t *n)
{
if(l->tail != NULL)
{
n->prev = l->tail;
l->tail->next = n;
l->tail = n;
}
else
{
l->head = n;
l->tail = n;
}
l->length++;
return 0;
}

inline int list_add_head(list_t *l, node_t *n)
{
if(l->head != NULL)
{
n->next = l->head;
l->head->prev = n;
l->head = n;
}
else
{
l->head = n;
l->tail = n;
}
l->length++;
return 0;
}



inline int list_deinit(list_t *l)
{
node_t* buff;
while(l->head != NULL && l->tail != NULL)
{
list_remove_tail(l);
}
free(l);
return 0;
}

inline node_t* list_pop_tail(list_t *l)
{
node_t *buff;
buff = l->tail;
l->tail = buff->prev;
if(l->tail != NULL) l->tail->next = NULL;
buff->next = NULL;
buff->prev = NULL;
l->length--;
return buff;
}

inline node_t* list_pop_head(list_t *l)
{
node_t *buff;
buff = l->head;
l->head = buff->next;
if(l->head != NULL) l->head->prev = NULL;
buff->next = NULL;
buff->prev = NULL;
l->length--;
return buff;
}

inline int list_remove_tail(list_t *l)
{
node_t *buff;
buff = list_pop_tail(l);
node_delete(buff);
return 0;
}

inline int list_remove_head(list_t *l)
{
node_t *buff;
buff = list_pop_head(l);
node_delete(buff);
return 0;
}

inline void list_print(list_t *l)
{
node_t *n = l->head;
printf("current length = %d: ", l->length);
while(n != NULL)
{
printf("%s ", (char *)(n->data));
n = n->next;
}
printf("\n");
}

inline int list_add_nth(list_t *l, int index, node_t *n)
{
node_t *t;
int i;
if(index > l->length || index < 0)
{
return -1;
}
else if(index == 0)
{
list_add_head(l, n);
}
else if(index == l->length )
{
list_add_tail(l, n);
}
else
{
for(t = l->head, i = 0; i != index; i++)
{
t = t->next;
}
t->prev->next = n;
n->next = t;
n->prev = t->prev;
t->prev = n;
l->length++;
}
return 0;
}

inline node_t* list_pop_nth(list_t *l, int index)
{
node_t *t;
node_t *n;
int i;
if(index >= l->length || index < 0)
{
return NULL;
}
else if(index == 0)
{
t = list_pop_head(l);
}
else if(index == l->length - 1)
{
t = list_pop_tail(l);
}
else
{
for(t = l->head, i = 0; i != index; i++)
{
t = t->next;
}
t->prev->next = t->next;
t->next->prev = t->prev;
t->next = NULL;
t->prev = NULL;
l->length--;
}
return t;
}

inline int list_remove_nth(list_t *l, int index)
{
node_t *n = list_pop_nth(l, index);
if(n != NULL) node_delete(n);
return (n == NULL)?-1:0;
}


จากการ design ในลักษณะนี้จะเห็นได้ว่า เราสามารถเพิ่ม stack กะ queue support ได้ไม่ยากเลย เพราะ list มี operation พร้อมหมดแล้ว สำหรับ ทั้ง?stack และ queue

ดังนี้


/* stack.h */
#include "node.h"
#include "list.h"

typedef list_t stack_t;

inline stack_t* stack_init();

inline int stack_push(stack_t *s, node_t *);
inline node_t* stack_pop(stack_t *s);

inline void stack_print(stack_t *s);

inline int stack_deinit(stack_t *s);

/* stack.c */
#include <stdio.h>
#include "stack.h"

inline stack_t* stack_init()
{
list_t* l;
l = list_init();
return l;
}

inline int stack_push(stack_t *s, node_t *n)
{
list_add_head(s, n);
return 0;
}

inline node_t* stack_pop(stack_t *s)
{
node_t *n;
n = list_pop_head(s);
return n;
}

inline void stack_print(stack_t *s)
{
list_print(s);
}

inline int stack_deinit(stack_t *s)
{
list_deinit(s);
return 0;
}

/* queue.h */
#include "node.h"
#include "list.h"

typedef list_t queue_t;

inline queue_t* queue_init();
inline int queue_push(queue_t *q, node_t *n);
inline node_t* queue_pop(queue_t *q);

inline void queue_print(queue_t* q);

inline int queue_deinit(queue_t* q);

/* queue.c */
#include <stdio.h>
#include "queue.h"

inline queue_t* queue_init()
{
list_t *l;
l = list_init();
return l;
}

inline int queue_push(queue_t *q, node_t *n)
{
list_add_head(q, n);
return 0;
}

inline node_t* queue_pop(queue_t *q)
{
node_t *n;
n = list_pop_tail(q);
return n;
}

inline void queue_print(queue_t* q)
{
list_print(q);
}

inline int queue_deinit(queue_t* q)
{
list_deinit(q);
return 0;
}


จะเห็นได้ว่าแทบไม่ต้องเขียนอะไรเลย แค่ reuse list operation เท่านั้น
ส่วนการเรียกใช้ก็

#include <stdio.h>
#include "node.h"
#include "list.h"
#include "stack.h"
#include "queue.h"

int main(int argc, char *argv[])
{
list_t *l;
stack_t *s;
queue_t *q;
node_t *n;
int i;

l = list_init();
printf("\n========== Start List =========\n");
for(i = 1; i < argc; i++)
{
printf("\tPushing: %s\n", argv[i]);
n = node_create((void *)(argv[i]), strlen(argv[i]) + 1);
list_add_tail(l, n);
list_print(l);
}
printf("\n");
if(l->length >= 3)
{
n = node_create((void *)"HELLO", sizeof("HELLO") + 1);
list_print(l);
printf("\tAdding: %s at %d\n", (char *)(n->data), 3);
list_add_nth(l, 3, n);

list_print(l);
n = list_pop_nth(l, 3);
printf("\tPopping at %d: %s\n", 3, (char *)(n->data));
list_print(l);
}
printf("\n========== End List =========\n");
list_deinit(l);

q = queue_init();
printf("\n========== Start Queue =========\n");
for(i = 1; i < argc; i++)
{
printf("\tPushing: %s\n", argv[i]);
n = node_create((void *)(argv[i]), strlen(argv[i]) + 1);
queue_push(q, n);
queue_print(q);
}
printf("\n");
for(i = 1; i < argc; i++)
{
queue_print(q);
n = queue_pop(q);
printf("\tPopping: %s\n", (char *)(n->data));
}
printf("\n========== End Queue =========\n");
queue_deinit(q);

s = stack_init();
printf("\n========== Start Stack =========\n");
for(i = 1; i < argc; i++)
{
printf("\tPushing: %s\n", argv[i]);
n = node_create((void *)(argv[i]), strlen(argv[i]) + 1);
stack_push(s, n);
stack_print(s);
}
printf("\n");
for(i = 1; i < argc; i++)
{
stack_print(s);
n = stack_pop(s);
printf("\tPopping: %s\n", (char *)(n->data));
}
printf("\n========== End Stack =========\n");
stack_deinit(s);

return 0;
}


ผลลัพธ์ที่ได้ เป็นดังนี้

khunpid@PETER2003:/home/khunpid/container> mainapp 1 2 3

========== Start List =========
Pushing: 1
current length = 1: 1
Pushing: 2
current length = 2: 1 2
Pushing: 3
current length = 3: 1 2 3

current length = 3: 1 2 3
Adding: HELLO at 3
current length = 4: 1 2 3 HELLO
Popping at 3: HELLO
current length = 3: 1 2 3

========== End List =========

========== Start Queue =========
Pushing: 1
current length = 1: 1
Pushing: 2
current length = 2: 2 1
Pushing: 3
current length = 3: 3 2 1

current length = 3: 3 2 1
Popping: 1
current length = 2: 3 2
Popping: 2
current length = 1: 3
Popping: 3

========== End Queue =========

========== Start Stack =========
Pushing: 1
current length = 1: 1
Pushing: 2
current length = 2: 2 1
Pushing: 3
current length = 3: 3 2 1

current length = 3: 3 2 1
Popping: 3
current length = 2: 2 1
Popping: 2
current length = 1: 1
Popping: 1

========== End Stack =========






 

Create Date : 14 กุมภาพันธ์ 2549   
Last Update : 14 กุมภาพันธ์ 2549 23:27:21 น.   
Counter : 349 Pageviews.  

หาค่าจำนวนเฉพาะด้วยวิธี Sieve of Eratosthenes

Eratosthenes เป็นนักคณิตศาสตร์ชาวกรีก ที่คิดค้นสิ่งต่าง ๆ ไว้มากพอสมควร แต่ วันนี้เราจะมาพูดกันถึง การหาค่า prime หรือจำนวนเฉพาะ ที่ใช้วิธีตัดออกทีละชุด (screen หรือ sieve นั่นเอง)
วิธีการของเค้าก็ง่าย ๆ ครับ คือ ในตัวเลขจำกัดจำนวนนึงเราสามารถหาค่า จำนวนเฉพาะได้โดยใช้ ตัวเลขเริ่มต้น (2) เพื่อที่จะนำไป หาค่าที่เป็นตัวคูณเพื่อ screen ตัวที่เป็น ค่าที่เกิดจากการคูณออกจากความน่าจะเป็นที่จะเป็น จำนวนเฉพาะ โดยตัวที่จะนำมาสกรีน ก็นำมาจถึงแค่ ตัวเลขที่ น้อยกว่าหรือเท่ากับ sqrt ของ ค่าสูงสุดที่ต้องการหา (ตรงนี้พิสูจน์ไม่ยาก)
เช่น หาจำนวนเฉพาะ จนถึง 20
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
ใช้ 2 screen (2^2 = 4 < 20)
2, 3, 5, 7, 9, 11, 13, 15, 17, 19
ใช้ 3 screen (3^2 = 9 < 20)
2, 3, 5, 7, 11, 13, 17, 19
5 ไม่ต้องนำมาสกรีนอีก เพราะ 5^2 > 20
เพราะฉะนั้นค่าที่ไม่ถูกตัดทิ้งทั้งหมดก็คือ เลขจำนวนเฉพาะ
เขียนด้วย C++ ได้ดังนี้


vector<bool> GetPrimeBitSets(int from, int to)
{
vector<bool> bs (to + 1); //Create a bool vector to hold a primality
for(int i = 0; i < to + 1; i++) //Initialize the primality vector
{
bs[i] = bool(i & 1); //even number will be set as false
}
int j = 0;
from = (from <= 3)? 3 : from;
bs[0] = false;
bs[1] = false;
bs[2] = true; //2 is prime
bs[3] = true; //3 is prime
for(int i = 3; i * i <= to; i += 2) //All odds numbers are considering
{
if(!bs[i]) continue; //if the number is not a prime then no need to do
for(j = i + i; j <= to; j += i) // populate all the multiply of i
{
bs[j] = false;
}
}
return bs; //when done, the left number are prime
}




 

Create Date : 26 ธันวาคม 2548   
Last Update : 27 ธันวาคม 2548 16:58:53 น.   
Counter : 2515 Pageviews.  

1  2  

Forsberg
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed

ผู้ติดตามบล็อก : 1 คน [?]


ผู้ติดตามบล็อก : 1 คน [?]




[Add Forsberg's blog to your web]