這個計畫的目的是找出子網路下有哪些主機提供服務, 目前只有簡單的偵測 Ping(ICMP), Web(80), DNS(open resolver), SSH(22), SMTP(25). 未來將陸續增加偵測服務的項目. 雖然已經有 nmap 等優秀軟體, 不過仍舊希望能發展出簡易的程式, 更希望能匯聚更多偵測點讓資料搜集時間縮短. 接下來將開始設計資料庫結構及提供查詢的API.
目前尚有資料來源的問題, 就是各國網段清單. 目前是從 ip2nation 計算出網段. 但是這個資料並不是即時資料, 所以如果有哪位大德知道去哪找免費的清單, 請不吝告訴在下.
專案網址: https://github.com/jengyic/IP_Research
Showing posts with label C++. Show all posts
Showing posts with label C++. Show all posts
Sunday, August 03, 2014
Thursday, June 26, 2014
嘗試將大量的 IPv4 位址放在記憶體且快速找到
首先, 這是個緊急的需求, 所以沒時間慢慢磨演算法. 第一時間想到的是變成無符號整數放到陣列, 初始化時使用 quick sort 排序, 搜尋使用 binary search. 果真是太嫩了, 實作出來之後, 效能非常普通.
陣列搜尋
好吧! 只好拿出記憶用起雜湊表, 雜湊函數十分簡單. 第一版: 取高低 16 bits 進行 XOR 取得 bucket 位置, 再建立單向鍊結串列. 第二版為了有效縮短串列, 使用 24 bits 進行 XOR.
第二版
測試數據為從某台 TLD NS 的某一段時間所有來訪的 IPv4 (524,860筆), 搜尋測試為 100,000 次(命中與不命中次數為 1:1, 唯一缺點就是沒有每次跑雜湊函式, 有空再來重作一次測試). 測試結果如下.
測試結果
結論是適合的演算法比較重要, 繼續尋找更快的演算法.
題外話: printf 真是超級耗時的, 可以從不輸出資料的測試結果看出.
陣列搜尋
好吧! 只好拿出記憶用起雜湊表, 雜湊函數十分簡單. 第一版: 取高低 16 bits 進行 XOR 取得 bucket 位置, 再建立單向鍊結串列. 第二版為了有效縮短串列, 使用 24 bits 進行 XOR.
第二版
測試數據為從某台 TLD NS 的某一段時間所有來訪的 IPv4 (524,860筆), 搜尋測試為 100,000 次(命中與不命中次數為 1:1, 唯一缺點就是沒有每次跑雜湊函式, 有空再來重作一次測試). 測試結果如下.
測試結果
結論是適合的演算法比較重要, 繼續尋找更快的演算法.
題外話: printf 真是超級耗時的, 可以從不輸出資料的測試結果看出.
Thursday, November 08, 2012
C範例程式 : 浮點數及雙精度浮點數轉換二進位字串
浮點數紀錄數字的格式如下 :
程式碼 : include stdio.h stdlib.h string.h limits.h
實際執行結果 :
x = 1.yyyy * 2 ^ z
_ ________ _______________________
1 8 23
+ 127+z 0.yyyy 用 *2 轉換為 binary
-
_ ___________ ____________________________________________________
1 11 52
+ 1023+z 0.yyyy 用 *2 轉換為 binary
-程式碼 : include stdio.h stdlib.h string.h limits.h
#define BTSIZE 256
void dec2bin(int);
void float2bin(float);
void double2bin(double);
int main()
{
int i;
float f;
double d = 1.0;
printf("%d\t",2);
dec2bin(2);
printf("\n%d\t",-2);
dec2bin(-2);
printf("\n%d\t",10);
dec2bin(10);
printf("\n%d\t",172);
dec2bin(172);
printf("\n%d\t",192);
dec2bin(192);
printf("\n%d\t",65535);
dec2bin(65535);
printf("\n%d\t",-65535);
dec2bin(-65535);
printf("\n");
printf("\n%f\t",2.0);
float2bin(2.0);
printf("\n%f\t",-2.0);
float2bin(-2.0);
printf("\n%f\t",1.2);
float2bin(1.2);
printf("\n%f\t",-1.2);
float2bin(-1.2);
printf("\n%f\t",1.0);
float2bin(1.0);
printf("\n%f\t",-1.0);
float2bin(-1.0);
printf("\n%f\t",0.5);
float2bin(0.5);
printf("\n%f\t",-0.5);
float2bin(-0.5);
printf("\n%f\t",0.25);
float2bin(0.25);
printf("\n%f\t",0.75);
float2bin(0.75);
printf("\n%f\t",0.125);
float2bin(0.125);
printf("\n%f\t",0.1);
float2bin(0.1);
printf("\n%f\t",0.01);
float2bin(0.01);
printf("\n");
printf("\n%lf\t",1.0);
double2bin(1.0);
printf("\n%lf\t",-1.0);
double2bin(-1.0);
printf("\n%lf\t",1.2);
double2bin(1.2);
printf("\n%lf\t",-1.2);
double2bin(-1.2);
printf("\n%lf\t",0.5);
double2bin(0.5);
printf("\n%lf\t",-0.5);
double2bin(-0.5);
printf("\n");
return 0;
}
void dec2bin(int data)
{
unsigned int t = (unsigned int)data;
int b = sizeof(t) * CHAR_BIT;
char bt[BTSIZE];
for(int i = 0; i < b; i++)
{
bt[i] = (t & 0x01) ? '1' : '0';
t>>=1;
}
for(int i = b-1; i >= 0; i--)
{
putchar(bt[i]);
if(!(i%8) && i)
printf(" ");
}
}
void float2bin(float f)
{
long l;
int b;
char bt[BTSIZE];
memcpy(&l, &f, sizeof(f));
b= sizeof(f) * CHAR_BIT;
for(int i = 0; i < b; i++)
{
bt[i] = (l & 0x01) ? '1' : '0';
l>>=1;
}
for(int i = b-1; i >= 0; i--)
{
putchar(bt[i]);
if(!(i%8) && i)
printf(" ");
}
}
void double2bin(double d)
{
int l;
int *iptr;
iptr = &d;
memmove(&l, iptr+1, sizeof(l));
dec2bin(l);
printf(" ");
memmove(&l, iptr, sizeof(l));
dec2bin(l);
}
實際執行結果 :
$ ./show_data
2 00000000 00000000 00000000 00000010
-2 11111111 11111111 11111111 11111110
10 00000000 00000000 00000000 00001010
172 00000000 00000000 00000000 10101100
192 00000000 00000000 00000000 11000000
65535 00000000 00000000 11111111 11111111
-65535 11111111 11111111 00000000 00000001
2.000000 01000000 00000000 00000000 00000000
-2.000000 11000000 00000000 00000000 00000000
1.200000 00111111 10011001 10011001 10011010
-1.200000 10111111 10011001 10011001 10011010
1.000000 00111111 10000000 00000000 00000000
-1.000000 10111111 10000000 00000000 00000000
0.500000 00111111 00000000 00000000 00000000
-0.500000 10111111 00000000 00000000 00000000
0.250000 00111110 10000000 00000000 00000000
0.750000 00111111 01000000 00000000 00000000
0.125000 00111110 00000000 00000000 00000000
0.100000 00111101 11001100 11001100 11001101
0.010000 00111100 00100011 11010111 00001010
1.000000 00111111 11110000 00000000 00000000 00000000 00000000 00000000 00000000
-1.000000 10111111 11110000 00000000 00000000 00000000 00000000 00000000 00000000
1.200000 00111111 11110011 00110011 00110011 00110011 00110011 00110011 00110011
-1.200000 10111111 11110011 00110011 00110011 00110011 00110011 00110011 00110011
0.500000 00111111 11100000 00000000 00000000 00000000 00000000 00000000 00000000
-0.500000 10111111 11100000 00000000 00000000 00000000 00000000 00000000 00000000C範例程式 : 堆疊與佇列
堆疊(stack) : 先進後出(First In Last Out, FILO), 可以將容器想像成桶子, 放進去的東西一層一層疊上去. 拿出來時自然就是後來進去的東西先拿出來.
佇列(queue) : 先進先出(First In First Out, FIFO),可以將容器想像成水管, 只從一頭放東西進去, 且只能從另一頭取出. 所以自然是先進入的東西先拿出來.
以上兩種資料結構都將以陣列及鍊結串列實現.
堆疊
陣列 include stdio.h
鍊結串列 include stdio.h malloc.h
佇列
陣列 include stdio.h
鍊結串列 include stdio.h malloc.h string.h
佇列(queue) : 先進先出(First In First Out, FIFO),可以將容器想像成水管, 只從一頭放東西進去, 且只能從另一頭取出. 所以自然是先進入的東西先拿出來.
以上兩種資料結構都將以陣列及鍊結串列實現.
堆疊
陣列 include stdio.h
#define ASIZE 5
int stack[ASIZE]={0};
int top=-1;
void push();
void pop();
void display();
void release();
int main()
{
int choice;
printf("陣列堆疊測試程式(可儲存資料筆數%d)\n", ASIZE+1);
while(1)
{
printf("1) 新增\t2) 刪除\t3) 顯示\t0) 結束 : ");
scanf("%d",&choice);
if(!choice)
break;
switch(choice)
{
case 1: push(); break;
case 2: pop(); break;
case 3: display(); break;
default: display(); break;
}
}
printf("清空堆疊\n");
release();
return 0;
}
void push()
{
int d;
if(top < ASIZE)
{
printf("請輸入資料(整數) : ");
scanf("%d",&d);
top++;
stack[top] = d;
}
else
{
printf("堆疊滿了\n");
}
}
void pop()
{
if(top >= 0)
{
printf("%3d\n",stack[top]);
top--;
}
else
{
printf("堆疊是空的\n");
}
}
void display()
{
int pos = top;
while(pos >= 0)
{
printf("%3d ",stack[pos]);
pos--;
}
printf("\n");
}
void release()
{
while(top >= 0)
pop();
}
鍊結串列 include stdio.h malloc.h
typedef struct _node * pnode;
struct _node{
int data;
pnode next;
}node;
pnode head;
void init();
void push();
void pop();
void display();
void release();
int main()
{
int choice;
init();
printf("串列堆疊測試程式\n");
while(1)
{
printf("1) 新增\t2) 刪除\t3) 顯示\t0) 結束 : ");
scanf("%d",&choice);
if(!choice)
break;
switch(choice)
{
case 1: push(); break;
case 2: pop(); break;
case 3: display(); break;
default: display(); break;
}
}
printf("清空堆疊\n");
release();
return 0;
}
void init()
{
head = NULL;
}
void push()
{
int d;
pnode p = (pnode)malloc(sizeof(node));
printf("請輸入資料(整數) ");
scanf("%d",&d);
p->data = d;
p->next = head;
head = p;
}
void pop()
{
pnode p;
if(head)
{
p = head;
head = head->next;
printf("刪除 %d \n",p->data);
free(p);
}
else
{
printf("堆疊是空的\n");
}
}
void display()
{
pnode p = head;
while(p)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
void release()
{
pnode p;
while(head)
{
p = head;
head = head->next;
free(p);
}
}
佇列
陣列 include stdio.h
#define QSIZE 5
int queue[QSIZE];
int head, tail;
void init();
int isFull();
int isEmpty();
void enqueue();
void dequeue();
void display();
void release();
int main()
{
int choice;
printf("陣列佇列測試程式(可儲存資料筆數%d)\n", QSIZE+1);
while(1)
{
printf("1) 新增\t2) 刪除\t3) 顯示\t0) 結束 : ");
scanf("%d",&choice);
if(!choice)
break;
switch(choice)
{
case 1: enqueue(); break;
case 2: dequeue(); break;
case 3: display(); break;
default: display(); break;
}
}
printf("清空串列\n");
release();
return 0;
}
void init()
{
head = tail = 0;
}
int isFull()
{
if((tail+1)%QSIZE == head)
{
printf("佇列已滿\n");
return 1;
}
return 0;
}
int isEmpty()
{
if(head%QSIZE == tail%QSIZE)
{
printf("佇列已空\n");
return 1;
}
return 0;
}
void enqueue()
{
int d;
if(!isFull())
{
printf("請輸入資料 ");
scanf("%d",&d);
tail++;
tail%=QSIZE;
queue[tail] = d;
}
}
void dequeue()
{
if(!isEmpty())
{
head++;
head%=QSIZE;
printf("刪除資料 %d\n",queue[head]);
}
}
void display()
{
for(int i = (head+1)%QSIZE; i != (tail+1)%QSIZE;)
{
printf("%d ",queue[i]);
i++;
i%=QSIZE;
}
printf("\n");
}
void release()
{
for(int i = (head+1)%QSIZE; i != (tail+1)%QSIZE;)
{
queue[i]=-1;
i++;
i%=QSIZE;
}
}
鍊結串列 include stdio.h malloc.h string.h
#define MAXSTR 50
typedef struct _node * pnode;
struct _node{
char name[MAXSTR];
char phone[MAXSTR];
pnode next;
}node;
pnode head, tail;
void init();
void enqueue();
void dequeue();
void display();
void release();
int main()
{
int choice;
printf("鍊結串列佇列測試程式\n");
while(1)
{
printf("1) 新增\t2) 刪除\t3) 顯示\t0) 結束 : ");
scanf("%d",&choice);
if(!choice)
break;
switch(choice)
{
case 1: enqueue(); break;
case 2: dequeue(); break;
case 3: display(); break;
default: display(); break;
}
}
printf("清空串列\n");
release();
return 0;
}
void init()
{
head = tail = NULL;
}
void enqueue()
{
pnode p = (pnode)malloc(sizeof(node));
if(p)
{
printf("請輸入姓名 ");
scanf("%s", p->name);
printf("請輸入電話 ");
scanf("%s", p->phone);
p->next = NULL;
if(head)
{
tail->next = p;
tail = p;
}
else
{
head = tail = p;
}
}
else
{
printf("無法取得記憶體空間新增資料\n");
}
}
void dequeue()
{
pnode p;
if(head)
{
p = head;
if(head->next)
head = head->next;
else
head = tail = NULL;
printf("刪除資料姓名 %s 電話 %s\n", p->name, p->phone);
free(p);
}
else
{
printf("串列已空\n");
}
}
void display()
{
pnode p;
p = head;
while(p)
{
printf("姓名 %s 電話 %s\n", p->name, p->phone);
p = p->next;
}
}
void release()
{
pnode p;
tail = NULL;
while(head)
{
p = head;
head = head->next;
free(p);
}
}
C範例程式 : 鍊結串列 linked list
使用結構(struct)實作節點(node). 串列建立在主程式中, 使用 nodep * 型態傳進函式進行 push 及 pop.
程式碼 include stdio.h stdlib.h
程式碼 include stdio.h stdlib.h
#define DIRTYPE 8
// Define structure pointer
typedef struct node * nodep;
// Define structure
struct node {
int x;
int y;
int dir;
nodep next;
};
// Add new node to linked list : addr. of head, addr. of tail, new node
void pushnode(nodep*,nodep*,nodep);
// Pop end node of linked list : addr. of head, addr. of tail
void popendnode(nodep*,nodep*);
// Pop begin node of linked list : addr. of head, addr. of tail
void popheadnode(nodep*,nodep*);
// Show linked list from begin to end
void show(nodep);
int main()
{
nodep head = NULL;
nodep tail = NULL;
nodep tmp = NULL;
int tx, ty, td, nc = 0;
int clean = 0;
while(1)
{
tmp = (nodep)malloc(sizeof(struct node));
printf("請輸入三個正整數 X座標 Y座標 方向 (輸入 0 0 0 結束程式) ");
scanf("%d %d %d", &tx, &ty, &td);
if(!tx && !ty && !td)
{
printf("選擇結束程式.\n");
break;
}
tmp->x=tx;
tmp->y=ty;
tmp->dir=td%DIRTYPE;
tmp->next=NULL;
pushnode(&head, &tail, tmp);
nc++;
printf("====== 串列成員如下 ======\n");
show(head);
printf("====== ====== ======\n");
}
if(!nc)
exit(0);
printf("====== 串列最終成員如下 ======\n");
show(head);
printf("====== ====== ======\n");
printf("請問如何清除串列 : \n 1) 從尾端清除 \n 2) 從頭端清除 ");
scanf("%d", &clean);
if(clean != 1 && clean != 2)
{
clean = 1;
printf("選項錯誤 使用預設 從尾端清除 \n");
}
printf("\n清除串列\n");
for(int i = nc; i > 0; i--)
{
if(clean == 1)
popendnode(&head, &tail);
else
popheadnode(&head, &tail);
printf("\n====== 串列成員如下 ======\n");
show(head);
printf("====== ====== ======\n\n");
//if(!tail)
// head = tail;
//if(!head)
// tail = head;
}
printf("清除串列完畢\n");
printf("\n====== 串列最終成員如下 ======\n");
show(head);
printf("====== ====== ======\n");
return 0;
}
void pushnode(nodep *h, nodep *t, nodep n)
{
//printf(" push node \n");
if(!*h)
{
//printf(" add to empty list \n");
*h = n;
*t = n;
}
else
{
//printf(" add to non-empty list \n");
(*t)->next = n;
*t = n;
}
/* printf("h = %x\n", h);
printf("t = %x\n", t);
printf("&h = %x\n", &h);
printf("&t = %x\n", &t);*/
//return t;
}
void show(nodep h)
{
while(h)
{
printf("( %d, %d )(dir = %d)\n", h->x, h->y, h->dir);
h = h->next;
}
}
void popendnode(nodep *h, nodep *t)
{
nodep p, out;
if(*h && *t)
{
p = *h;
while(p != *t && p->next != *t)
p = p->next;
if(p->next)
{
out = p->next;
*t = p;
p->next = NULL;
}
else
{
out = p;
*h = NULL;
*t = NULL;
}
printf("倒出最後一個 node ( %d, %d )(dir = %d)\n", out->x, out->y, out->dir);
free(out);
}
}
void popheadnode(nodep *h, nodep *t)
{
nodep out;
if(*h && *t)
{
out = *h;
printf("倒出第一個 node ( %d, %d )(dir = %d)\n", out->x, out->y, out->dir);
if(out->next)
{
*h = out->next;
}
else
{
*h = NULL;
*t = NULL;
}
free(out);
}
}
C 語言範例程式
範例一 插入排序 include stdio.h stdlib.h time.h conio.h
範例二 計算 LCM include stdio.h stdlib.h conio.h
範例三 計算費氏級數 include stdio.h stdlib.h
範例四 尋找質數 include stdio.h stdlib.h stdbool.h
範例五 單字排序 include stdio.h stdlib.h string.h
範例六 蝸牛方陣 include stdio.h stdlib.h
範例七 魔方陣 include stdio.h stdlib.h
// 定義排序陣列大小
#define ASIZE 5
// 主程式 開始
int main()
{
// 初始化排序陣列
int a[ASIZE];
// 定義變數 : 已排序位置, 比較大小的位置, 輸出陣列的位置
int i, j, k, tmp;
// 判斷是否繼續使用程式的變數
char choice;
// 程式重複執行區塊 開始
while(1)
{
printf("亂數產生陣列元素\n");
srand(time(NULL));
// 亂數產生陣列元素
for(i = 0; i < ASIZE; i++)
{
a[i] = rand() % 100;
}
// 輸出排序前陣列
printf("排序前陣列 : ");
for(k = 0; k < ASIZE; k++)
printf("%2d ", a[k]);
printf("\n\n排序\n");
// 排序的外層迴圈 : 已排序
for(i = 1; i<=ASIZE; i++)
{
// 輸出目前已完成排序的位置
printf("i:%d, ",i);
// 輸出排序中陣列
for(k = 0; k < ASIZE; k++)
printf("%2d ", a[k]);
//printf("\n");
getchar();
// 由右往左比大小排序
for(j = i; j > 0; j--)
{
// 若比左方大, 代表一定比左方所有已排序的數字大. 不需繼續比較直接跳離此回合排序.
// 若比左方小, 則需要交換位置. 並繼續向左方比大小, 直到比左方數字大為止.
if(a[j-1] < a[j]){
break;
}else{
tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
// 輸出排序後陣列
printf("\n排序後陣列 : ");
for(k = 0; k < ASIZE; k++)
printf("%2d ", a[k]);
printf("\n");
printf("\n請問是否要繼續排序陣列 ? (按任意鍵繼續, 輸入 N / n 離開) ");
choice=getche();
if(choice == 'N' || choice == 'n')
break;
printf("\n\n");
// 程式重複執行區塊 結束
}
printf("\n感謝您的使用.\n");
// 暫停畫面 (For Windows)
system("pause");
return 0;
// 主程式 結束
}
範例二 計算 LCM include stdio.h stdlib.h conio.h
// 計算 GCD 函式原型
int gcd(int,int);
// 計算 LCM 函式原型
int lcm(int,int);
// 主程式 開始
int main()
{
// 定義存放使用者輸入數字的變數
int x, y;
// 定義是否繼續的變數
char choice;
// 程式重複執行區塊 開始
while(1)
{
// 使用者輸入
printf("請輸入兩個整數 : ");
scanf("%d %d", &x, &y);
// 呼叫 LCM 函式並且
printf("LCM(%d, %d) = %d\n", x, y, lcm(x,y));
printf("\n請問是否要繼續計算 LCM ? (按任意鍵繼續, 輸入 N / n 離開) ");
choice=getche();
if(choice == 'N' || choice == 'n')
break;
printf("\n\n");
// 程式重複執行區塊 結束
}
printf("\n感謝您的使用.\n");
system("pause");
return 0;
// 主程式 結束
}
// 計算 GCD 函式 開始
int gcd(int x, int y)
{
// 定義暫存數字
int z;
if(x<0) x=-x;
// 輾轉相除法
while(z=x%y)
{ x=y; y=z; }
return y;
// 計算 GCD 函式 結束
}
// 計算 LCM 函式 開始
int lcm(int x, int y)
{
int rx, ry, gcdnum;
// 呼叫計算 GCD 函式
gcdnum = gcd(x,y);
// 計算個別數字為 GCD 的倍數 rx ry
rx = x/gcdnum;
ry = y/gcdnum;
// 數學公式 : LCM = GCD * (X/GCD) * (Y/GCD)
return gcdnum * rx * ry;
// 計算 LCM 函式 結束
}
範例三 計算費氏級數 include stdio.h stdlib.h
// 計算費氏數列函式原型 - 遞迴
int rfib(int);
// 計算費氏數列函式原型 - 非遞迴
int fib(int);
// 主程式 開始
int main()
{
// 定義存放使用者輸入數字的變數
int x;
// 定義是否繼續的變數
char choice;
printf("費伯納數列計算程式 : ");
// 程式重複執行區塊 開始
while(1)
{
// 使用者輸入
printf("請輸入一個正整數 : ( 輸入 0 離開程式 ) ");
scanf("%d", &x);
if(x == 0)
{
printf("結束使用程式.\n");
break;
}
printf("\n 遞迴計算 Fib(%d) = %d\n", x, rfib(x));
printf("\n非遞迴計算 Fib(%d) = %d\n", x, fib(x));
//printf("\n請問是否要繼續計算費伯納數列 ? (按任意鍵繼續, 輸入 N / n 離開) ");
//choice=getche();
//if(choice == 'N' || choice == 'n')
// break;
printf("\n\n");
// 程式重複執行區塊 結束
}
printf("\n感謝您的使用.\n");
//system("pause");
return 0;
// 主程式 結束
}
// 計算費氏數列函式原型 - 遞迴 開始
int rfib(int n)
{
// fib(0) = 0
if(n == 0)
return 0;
// fib(1) = 1
else if(n == 1)
return 1;
// 數學公式 fib(n) = fib(n-1) + fib(n-2)
else
return rfib(n-1)+rfib(n-2);
// 計算費氏數列函式原型 - 遞迴 結束
}
int fib(int n)
{
// 定義變數 fib(n-2) fib(n-1)
int x = 0, y = 1, tmp;
// fib(0) = 0
if(n == 0)
return 0;
if(n == 1)
return 1;
else
{
for(int i = 2; i <= n; i++)
{
tmp = y;
y+=x;
x = tmp;
}
return y;
}
}
範例四 尋找質數 include stdio.h stdlib.h stdbool.h
// 定義每發現多少個質數就擴大陣列
#define PSTEPNUM 100
// 主程式 開始
int main()
{
// 定義質數陣列指標及暫存用陣列指標
int *prime, *tmp;
// 定義使用者輸入的最大數字, 已找到質數個數, 舊的質數陣列最大數字, 質數陣列最大數字
int unum, pc, oldpcmax, pcmax;
// 是否為質數的旗標
bool pflag;
// 判斷是否繼續使用程式的變數
char choice;
printf("找質數程式 : \n\n");
// 程式重複執行區塊 開始
while(1)
{
// 初始化變數
unum = -1;
pc = 0;
// 質數陣列最大數字(預設值為 PSTEPNUM)
pcmax = PSTEPNUM;
printf("請輸入一個正整數, 找比它小的質數 : (輸入 0 離開程式)");
scanf("%d", &unum);
// 使用者輸入數字錯誤處理
if(unum == 0)
{
printf("正常關閉程式.\n");
break;
}
else if(unum < 0)
{
printf("輸入數字不合規定.\n");
exit(0);
}
// 動態取得質數陣列空間
prime = (int*)malloc(sizeof(int)*pcmax);
// 從 2 開始找質數
for(int i = 2; i < unum; i++)
{
// 2 就是第一個質數
if(i == 2)
{
prime[pc] = 2;
pc++;
printf("p");
}
else
{
// 質數已放滿質數陣列
if(pc >= pcmax)
{
// 動態取得暫存用陣列
oldpcmax = pcmax;
tmp = (int*)malloc(sizeof(int)*oldpcmax);
// 複製質數陣列到暫存用陣列
for(int j = 0; j < oldpcmax; j++)
{
tmp[j] = prime[j];
}
// 清除質數陣列
free(prime);
// 動態取得新的質數陣列
pcmax+=PSTEPNUM;
prime = (int*)malloc(sizeof(int)*pcmax);
// 複製暫存用陣列到新的質數陣列
for(int j = 0; j < oldpcmax; j++)
{
prime[j] = tmp[j];
}
// 清除暫存用陣列
free(tmp);
printf("+");
}
else
{
// 預設數字是質數
pflag = true;
// 找質數迴圈 : 逐一檢查是否為已發現質數的倍數
for(int k = 0; k < pc; k++)
{
if(!(i%prime[k]))
{
// 發現為質數的倍數, i 就不是質數. 跳出找質數迴圈
pflag = false;
break;
}
}
// 若發現質數則記錄質數
if(pflag)
{
prime[pc] = i;
pc++;
printf("p");
}
}
}
}
printf("\n\n發現質數個數 : %d\n", pc);
// 輸出質數陣列
for(int i = 0; i < pc; i++)
{
printf("%6d ", prime[i]);
if(!((i+1)%10))
printf("\n");
}
printf("\n");
// 清除質數陣列
free(prime);
//printf("\n請問是否要繼續找質數 ? (按任意鍵繼續, 輸入 N / n 離開) ");
//choice=getche();
//if(choice == 'N' || choice == 'n')
// break;
//printf("\n\n");
// 程式重複執行區塊 結束
}
printf("\n感謝您的使用.\n");
system("pause");
return 0;
// 主程式 結束
}
範例五 單字排序 include stdio.h stdlib.h string.h
// 定義單字最長的長度
#define MAXWLEN 512
// 排序單字函式原型
void sortWordCard(char**,int,int);
// 主程式 開始
int main()
{
// 定義單字個數, 使用者輸入單字個數結果, 排序方式
int word_count, uin, sort_type;
// 定義二維單字陣列指標, 暫存用一維單字陣列
char **wordcard, tmpword[MAXWLEN];
printf("單字排序程式\n");
// 程式重複執行區塊 開始
while(1)
{
// 初始化單字個數, 使用者輸入單字個數結果
word_count = uin = 0;
// 使用者輸入單字個數
printf("\n1. 請輸入要排序的單字(長度需小於 %d)個數 ? (輸入 0 離開程式)", MAXWLEN);
uin = scanf("%d", &word_count);
// 單字個數錯誤處理, 結束程式
if(uin == 0 || word_count < 0 )
{
printf("輸入個數不合規定.\n");
break;
}
else if( word_count == 0)
{
// 結束程式
break;
}
// 輸入排序方式
printf(" 請輸入排序方式\n 1) 按字母大小排序(大寫字母排在最前面).\n 2) 按字母大小反向排序(小寫字母排在最前面). 請選擇 : ");
uin = scanf("%d", &sort_type);
// 排序方式錯誤處理
if(uin == 0)
{
printf("輸入排序方式不合規定.使用預設排序:按字母大小排序(大寫字母排在最前面).\n");
sort_type = 1;
}
// 排序方式對應傳遞參數
switch(sort_type)
{
case 1: sort_type = 1; break; // 大寫字母排在最前面且按字母大小排序
case 2: sort_type = -1; break; // 小寫字母排在最前面且按字母大小反向排序
default: printf("輸入排序方式不合規定.使用預設排序:按字母大小排序(大寫字母排在最前面).\n");
sort_type = 1; break; // 預設排序方式
}
// 動態取得二維單字陣列第一層陣列, 儲存第二層單字陣列第一個元素的位址
wordcard = (char**)malloc(sizeof(char*)*word_count);
// 接收使用者輸入的單字
printf("\n2. 請輸入要排序的單字(使用空白分隔)\n");
for(int i = 0; i < word_count; i++)
{
// 先使用暫存用一維單字陣列
scanf("%s",tmpword);
// 動態取得二維單字陣列第二層陣列, 儲存單字
wordcard[i] = (char*)malloc(sizeof(char)*strlen(tmpword));
// 複製暫存用一維單字陣列到單字陣列
strcpy(wordcard[i],tmpword);
//scanf("%s",wordcard[i]);
}
// 清掉所有尚未使用的輸入
fflush(stdin);
printf("\n3. 排序單字\n");
// 呼叫排序程式
sortWordCard(wordcard, word_count, sort_type);
// 顯示排序結果
printf("\n\n4. 依序顯示輸入單字\n");
for(int i = 0; i < word_count; i++)
{
printf("%s\n",wordcard[i]);
}
// 程式重複執行區塊 結束
}
printf("\n感謝您的使用.\n");
system("pause");
return 0;
// 主程式 結束
}
// 排序單字函式實作 開始
void sortWordCard(char** w, int l, int st)
{
char *tmp;
// 預設排序 : 依照字母順序
if(st != 1 && st != -1)
st = 1;
/* 除錯使用
for(int i=0; i0; j--)
{
// 使用 strcmp() 比較是否需要交換位置
if(strcmp(*(w+(j-1)),*(w+j)) == st)
{
// 將 w 視為一個儲存字串起點的陣列, 使用一個 tmp 指標交換指向位址
tmp = w[j];
w[j] = w[j-1];
w[j-1] = tmp;
}
}
printf(".");
}
// 排序單字函式實作 結束
}
範例六 蝸牛方陣 include stdio.h stdlib.h
// 主程式 開始
int main()
{
// 判斷是否繼續使用程式的變數
char choice;
// 定義陣列指標, 方陣大小, X軸位置, Y軸位置, 順時針/逆時針方向, 起點位置, 由小到大或由大到小, 輸入檢查
int **snail, size, x, y, clock, dir, start, sob, uin;
printf("蝸牛矩陣產生程式 : \n\n");
while(1)
{
fflush(stdin);
printf("請輸入方陣大小 : (輸入 0 離開程式) ");
uin = scanf("%d", &size);
// 使用者輸入數字錯誤處理
if(size == 0)
{
printf("正常關閉程式.\n");
break;
}
else if(size < 0 || uin == 0)
{
printf("輸入數字不合規定.\n");
exit(0);
}
fflush(stdin);
printf("請問要 1) 順時針 / 2) 逆時針方向走 : ");
uin = scanf("%d", &clock);
if(uin == 0)
{
clock = 1;
printf("輸入方向不合規定. 使用預設值 順時針\n");
}
//起點位置
switch(clock)
{
case 1:
case 2: x = -1; y = 0; dir = 0; break;
default: x = -1; y = 0; dir = 0; clock = 1;
printf("輸入方向不合規定. 使用預設值 順時針\n"); break;
}
fflush(stdin);
printf("請問起點在 1) 左上 2) 左下 3) 右上 4) 右下 : ");
uin = scanf("%d", &start);
if(start < 1 || start > 4 || uin == 0)
{
start = 1;
printf("起點選擇錯誤, 使用預設值 左上起點\n");
}
fflush(stdin);
printf("請問要 1) 由小到大 / 2) 由大到小 : ");
uin = scanf("%d", &sob);
if(sob != 1 && sob !=2 || uin == 0)
{
sob = 1;
printf("大小排序選擇錯誤, 使用預設值 由小到大\n");
}
/// For Debug ///
//printf("(%d)(%d)(%d)\n", dir, clock, size);
// 動態取得質數陣列空間
snail = (int **)malloc(sizeof(int *)*size);
for(int i = 0; i < size; i++)
{
snail[i] = (int *)malloc(sizeof(int)*size);
}
// 初始化方陣
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size; j++)
{
snail[i][j] = 0;
}
}
/// For Debug ///
//printf("(%d)(%d)(%d)\n", dir, clock, size);
// 使用老鼠走迷宮方式探測方陣
for(int i = 1; i <= size*size; i++)
{
// 順時針 右 0 下 1 左 2 上 3 逆時針 下 3 右 2 上 1 左 0
// 先按照既定方向走一格
/// For Debug ///
//printf("(%d)(x=%d)(y=%d)\n", dir, x, y);
switch(dir%4)
{
case 0: x++; break;
case 1: y++; break;
case 2: x--; break;
case 3: y--; break;
}
// 檢查 X 軸是否越界, 越界就退回並轉向
if(x >= size)
{
x--; dir++; y++;
}
else if(x < 0)
{
x++; dir++; y--;
}
// 檢查 Y 軸是否越界, 越界就退回並轉向
if(y >= size)
{
y--; dir++; x--;
}
else if(y < 0)
{
y++; dir++; x++;
}
// 下一站已經填了數字 : 回頭 -> 轉向 -> 定位
if(snail[x][y])
{
switch(dir%4)
{
case 0: x--; dir++; y++; break;
case 1: y--; dir++; x--; break;
case 2: x++; dir++; y--; break;
case 3: y++; dir++; x++; break;
}
}
snail[x][y] = (sob%2) ? i : size*size-i+1;
}
printf("\n");
// 輸出方陣
if(start == 1)
{
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size; j++)
{
if(clock == 1)
printf("%3d ", snail[j][i]);
else
printf("%3d ", snail[i][j]);
if(j == size - 1)
printf("\n");
}
}
}
else if(start == 2)
{
for(int i = size -1; i >= 0; i--)
{
for(int j = 0; j < size; j++)
{
if(clock == 1)
printf("%3d ", snail[i][j]);
else
printf("%3d ", snail[j][i]);
if(j == size - 1)
printf("\n");
}
}
}
else if(start == 3)
{
for(int i = 0; i < size; i++)
{
for(int j = size - 1; j >= 0; j--)
{
if(clock == 1)
printf("%3d ", snail[i][j]);
else
printf("%3d ", snail[j][i]);
if(j == 0)
printf("\n");
}
}
}
else if(start == 4)
{
for(int i = size-1; i >= 0; i--)
{
for(int j = size-1; j >= 0; j--)
{
if(clock == 1)
printf("%3d ", snail[j][i]);
else
printf("%3d ", snail[i][j]);
if(j == 0)
printf("\n");
}
}
}
//printf("\n請問是否要繼續產生蝸牛矩陣 ? (按任意鍵繼續, 輸入 N / n 離開) ");
//choice=getche();
//if(choice == 'N' || choice == 'n')
// break;
printf("\n");
// 程式重複執行區塊 結束
}
// 主程式 結束
}
範例七 魔方陣 include stdio.h stdlib.h
int main()
{
int size = 0, uin, x, y, nx, ny;
int **magicmatrix;
while(1)
{
size = uin = 0;
printf("請輸入方陣大小, 必須為奇數的正整數 ( 輸入 0 結束程式 ) ");
uin = scanf("%d", &size);
if(size == 0)
{
printf("結束使用程式.\n");
break;
}
else if(size < 0 || !(size%2))
{
continue;
}
else if(uin == 0)
{
printf("方陣大小不符規定.\n");
exit(0);
}
printf("產生空的方陣\n");
magicmatrix = (int **)malloc(sizeof(int*)*size);
for(int i = 0; i < size; i++)
{
magicmatrix[i] = (int *)malloc(sizeof(int)*size);
}
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size; j++)
{
magicmatrix[i][j] = 0;
}
}
printf("開始填方陣\n");
//起點
x = size/2;
y = 0;
magicmatrix[x][y] = 1;
//
for(int i = 2; i <= size*size; i++)
{
// 先往右上
nx = (x + 1) % size;
ny = (y+size-1) % size;
if(magicmatrix[nx][ny])
{
// 碰壁填下方
nx = x;
ny = (y+1) % size;
}
/// For Debug ///
//printf("x=%d y=%d nx=%d ny=%d\n", x, y, nx, ny);
// 開始填方陣
x = nx;
y = ny;
magicmatrix[x][y] = i;
}
printf("輸出結果\n");
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size; j++)
{
printf("%3d ", magicmatrix[j][i]);
}
printf("\n");
}
printf("\n");
}
printf("感謝使用.\n");
return 0;
}
Friday, September 21, 2012
C範例程式 : 判斷 IP 是否在給定的 subnet
為了搭配自己的 shell script 寫了這隻小程式, 沒有做一些多餘的錯誤檢查(因為 shell script 餵過去的資料已經處理過).只支援 IPv4 及一種 subnet 表示法. (只用了 stdio.h stdlib.h string.h )
程式碼
使用範例
程式碼
#include
#include
#include
int main(int argc, char **argv)
{
int uip[4], dst[4], nm[4], i = 0, netmask;
char *delim = ".";
char *dstdelim = "/";
char * pch;
char * dstip;
char * mask;
int j = 128;
/* Check number of argc */
if(argc != 3){
printf("Usage : ipinsubnet UIP DSTIP/NETMASK\n");
printf("Example : ipinsubnet 192.168.0.1 192.168.0.0/24\n");
return 1;
}
/* For uip */
i = 0;
pch = strtok(argv[1], delim);
while (pch != NULL){
uip[i] = atoi(pch);
pch = strtok(NULL, delim);
i++;
}
/* For dst IP and netmask */
i = 0;
/* Get dst IP */
dstip = strtok(argv[2], dstdelim);
/* Get netmask */
mask = strtok(NULL, dstdelim);
netmask = atoi(mask);
pch = strtok(dstip, delim);
while (pch != NULL){
dst[i] = atoi(pch);
pch = strtok(NULL, delim);
i++;
}
/* Generate netmask */
i = 0;
while((netmask - 8) >= 0){
nm[i] = 255;
netmask-=8;
i++;
}
if( netmask > 0 ){
nm[i] = 0;
for(; netmask > 0; netmask--){ nm[i] = nm[i] | j; j >>= 1; }
i++;
}
for(;i < 4; i++){ nm[i] = 0; }
/* Compare uip and dst with netmask */
for(i = 0; i < 4; i++){
if( (uip[i] & nm[i]) != (dst[i] & nm[i]) ){ printf("F\n"); return 0; }
}
printf("T\n");
return 0;
}
使用範例
$ ./ipinsubnet
Usage : ipinsubnet UIP DSTIP/NETMASK
Example : ipinsubnet 192.168.0.1 192.168.0.0/24
$ ./ipinsubnet 192.168.68.1 192.168.78.0/16
T
$ ./ipinsubnet 192.168.68.1 192.168.78.0/20
T
$ ./ipinsubnet 192.168.68.1 192.168.78.0/21
F
$ ./ipinsubnet 192.168.68.1 192.168.78.0/22
F
Subscribe to:
Posts (Atom)