這個計畫的目的是找出子網路下有哪些主機提供服務, 目前只有簡單的偵測 Ping(ICMP), Web(80), DNS(open resolver), SSH(22), SMTP(25). 未來將陸續增加偵測服務的項目. 雖然已經有 nmap 等優秀軟體, 不過仍舊希望能發展出簡易的程式, 更希望能匯聚更多偵測點讓資料搜集時間縮短. 接下來將開始設計資料庫結構及提供查詢的API.
目前尚有資料來源的問題, 就是各國網段清單. 目前是從 ip2nation 計算出網段. 但是這個資料並不是即時資料, 所以如果有哪位大德知道去哪找免費的清單, 請不吝告訴在下.
專案網址: https://github.com/jengyic/IP_Research
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 真是超級耗時的, 可以從不輸出資料的測試結果看出.
Saturday, October 19, 2013
目錄下大量檔案 piconv 轉碼的簡易 shell script
之前為了將一些 Big-5 資料庫檔案轉成 UTF-8 用過 iconv 但是遇到某些字元就會出錯無法完成翻譯。後來找到 piconv 可以完整將所有資料庫匯出檔案轉碼。今天為了看 SGU Season 1 找到簡體字幕，沒想到用 piconv 一樣沒出錯完成轉碼。
Google雲端硬碟公開分享 檔名 piconvTrans.sh
Google雲端硬碟公開分享 檔名 piconvTrans.sh
Friday, April 12, 2013
Sunday, December 30, 2012
FreeBSD下用 shell script 建立ZFS snapshot 更新版
此次更新的目的是讓 ZFS 不使用 ls /PATH/.zfs/snapshot 目錄判斷快照數量(為了避開 Bad file descriptor 問題). 中間版本曾經使用 /usr/local/bin/snapshot list 進行, 但是速度較慢. 好在這個檔案是 shell script. 看了一下 op_list 函式的內容看到取得目前已有的快照方法, 也了解到這隻程式慢在還要查詢及計算使用空間等數據. 所以將查詢改用 zfs list -H -t snapshot -o name | grep "ZPOOL_NAME/ZVOL_NAME@". (ZPOOL_NAME/ZVOL_NAME 可以使用 zfs list -H -o name ${volpath} 查詢得到)
使用 SSHFS 掛載遠端目錄
1. 安裝 SSHFS
FreeBSD 下請安裝 /usr/ports/sysutils/fusefs-sshfs
Ubuntu/Debian 下請 apt-get install sshfs
Mount :
sshfs RemoteServerAccountName@SSHServerName:/Remote/path /Mount/path -o follow_symlinks
Umount :
FreeBSD : umount /Mount/path
Ubuntu/Debian : fusermount -u /Mount/path
2. 使用掛載 shell script
目前暫時不做作業系統版本判斷. 所以有以下的兩組 shell script:
FreeBSD 下請安裝 /usr/ports/sysutils/fusefs-sshfs
Ubuntu/Debian 下請 apt-get install sshfs
Mount :
sshfs RemoteServerAccountName@SSHServerName:/Remote/path /Mount/path -o follow_symlinks
Umount :
FreeBSD : umount /Mount/path
Ubuntu/Debian : fusermount -u /Mount/path
2. 使用掛載 shell script
目前暫時不做作業系統版本判斷. 所以有以下的兩組 shell script:
Friday, December 14, 2012
讓 cron 可以每隔幾秒執行 shell script
之前使用每五分鐘檢查是否有嘗試入侵的機器, 發現有些機器會一下送來一堆連線. 所以只好將執行時間降到以秒為單位. 由於檢查用的 shell script 約在幾秒內完成, 所以就用下列的 shell script 來達成.
C++範例程式 : 四則運算計算機
這隻程式主要測試程式設計師對以鍊結串列形成的堆疊進行操作的能力(事實上檢查輸入字串的部份有佇列的概念-先進先出 FIFO). 另外也對四則運算的基本原理進行了解, 並使用堆疊完成正確的計算. 實際上寫這隻程式之前應該有另一個版本的程式 : 先將計算式轉成後序式, 再使用後序式進行計算(只需要一個堆疊即可). 不過我們並不需要輸出後序式, 所以搭配兩個堆疊直接算出結果.
程式困難的地方在:
1. 檢查輸入的計算式產生已完成檢查的鍊結串列 : 哪些運算符號(運算子 operator)是可以使用的? 運算元(數字 operand)的規格?
2. 操作運算元及運算子的堆疊 : 根據不同符號及優先權決定是否放入堆疊或是先計算再放入堆疊. 最後還要記得清空堆疊, 再輸出結果.
程式碼如下:
C++範例程式 : 約瑟夫問題
這個題目是用來測試程式設計師對環狀單向鍊結串列操作是否熟悉. 建立環狀鍊結串列是本程式中簡單的任務, 重點放在如何將環狀鍊結串列成員正確的刪除並保持串列完整性.
程式碼如下 :
程式碼如下 :
Tuesday, November 27, 2012
開放式課程網站
以下是個人花不少時間蒐集的數位學習網站. 上面有非常大量的數位學習內容, 相信未來還會有能互動的數位學習網站/內容興起.
]
### WorldWide
MYOOPS
Berkeley
MIT
Standford
Harvard
Utah
Washington
JHSPH
Coursera
CodeSchool
OCWConsortium
### Taiwan
TOCWC
NTU
NTHU
NCTU
NCKU
NCU
KMU
Saturday, November 17, 2012
透過 VPN 買 Android apps FX Plus
本來想要用免費軟體玩 Android, 沒想到還是刷了第一筆 USD 2.99 買個免費軟體(File Explorer)的 sshfs
模組(FX Plus). 這個軟體不只是可以 sshfs 還可以掛雲端硬碟(Google Drive, Dropbox, Box,
SkyDrive, SugarSync 前三個測試過). 其實之前用 NFS 掛伺服器的目錄就很好用了, 但是遇到伺服器(Ubuntu)的硬碟是
NTFS|FAT|FAT16 目錄權限會限縮到只有 Owner 可以看, 從 NFS client (Android)看到的就是
Permission denied. 有了 sshfs 就可以遨遊自己的個人目錄(連 symbolic link 也可以進去).
使用 VPN 繞過官商打架.
FX Plus
在 Windows (2003 不可用, XP以上) 上可以使用 win-sshfs.(symbolic link : OK)
http://code.google.com/p/win-sshfs/
接下來就是找windows server 2003 的 sshfs 解法, 對於使用者就可以不一定要用 SAMBA 了. 讓 SAMBA 變成公用目錄或暫存用目錄, 就可以不用 ACL 在那邊傷腦筋.
其實本來是想用 BlueStacks (http://www.pigo.idv.tw/archives/1641) 突破的. 但是在Win XP VM搞半天 BlueStacks 就是看到黑畫面. 才放棄這個方法改用上述的方法(VPN連線不能使用加密還真是 OOXX).
使用 VPN 繞過官商打架.
FX Plus
在 Windows (2003 不可用, XP以上) 上可以使用 win-sshfs.(symbolic link : OK)
http://code.google.com/p/win-sshfs/
接下來就是找windows server 2003 的 sshfs 解法, 對於使用者就可以不一定要用 SAMBA 了. 讓 SAMBA 變成公用目錄或暫存用目錄, 就可以不用 ACL 在那邊傷腦筋.
其實本來是想用 BlueStacks (http://www.pigo.idv.tw/archives/1641) 突破的. 但是在Win XP VM搞半天 BlueStacks 就是看到黑畫面. 才放棄這個方法改用上述的方法(VPN連線不能使用加密還真是 OOXX).
在 FreeBSD 建立樣版功能的 jail 環境
0. 準備步驟 :
0.0. 準備 Host 的網路環境
0.0.0. 綁 IP 到 Host : 編輯 /etc/rc.conf 加上 IP alias 設定
ifconfig_em0_alias1="192.168.66.66 netmask 255.255.255.255"
0.0.1. 設定 natd (如果是只有一片網卡的機器就可以不用, 此步驟適用機器有跨在兩個網路(一內一外)上)
Edit /etc/rc.conf
gateway_enable="YES"
firewall_enable="YES"
firewall_type="/etc/my.firewall"
firewall_script="/etc/my.firewall"
firewall_logging="YES"
natd_enable="YES"
natd_interface="re0"
natd_flags="-l -f /etc/natd.conf"
Edit /etc/my.firewall (請依照實際需求更改)
#!/bin/sh -
fwcmd="/sbin/ipfw"
INTIF="re0"
LANIF0="em0"
${fwcmd} -f flush
#For NATD
${fwcmd} add 00030 divert natd all from any to any via ${INTIF}
...
${fwcmd} add 65000 pass all from any to any
Edit /etc/natd.conf
use_sockets yes
same_ports yes
dynamic yes
Edit /etc/services
natd 8668/divert # Network Address Translation
接著 Host 重新啟動.
0.1. 在 /usr/src 編譯整個環境.
# cd /usr/src; make buildworld
1. 設定樣板存放位置且安裝樣板
# zfs create storage/jail
# zfs set mountpoint=/storage/jail storage/jail
# zfs set dedup=on storage/jail
# zfs set quota=300G storage/jail
# zfs create storage/jails
# zfs set mountpoint=/storage/jails storage/jails
# zfs set dedup=on storage/jails
# zfs set quota=300G storage/jails
# zfs set mountpoint=/storage/jails storage/jails
# zfs set dedup=on storage/jails
# zfs set quota=300G storage/jails
# mkdir -p /storage/jail/mroot
# cd /usr/src
# make installworld DESTDIR=/storage/jail/mroot
2. 複製 src 及 ports
# cd /storage/jail/mroot
# mkdir usr/ports
# portsnap -p /storage/jail/mroot/usr/ports fetch extract
# cpdup /usr/src /storage/jail/mroot/usr/src
3. 建立樣板環境
# mkdir /storage/jail/skel /storage/jail/skel/home /storage/jail/skel/usr-X11R6 /storage/jail/skel/distfiles /storage/jail/skel/packages
# mv etc /storage/jail/skel
# mv usr/local /storage/jail/skel/usr-local
# mv tmp /storage/jail/skel
# mv var /storage/jail/skel
# mv root /storage/jail/skel
4. 產生設定檔
# mergemaster -t /storage/jail/skel/var/tmp/temproot -D /storage/jail/skel -i
# cd /storage/jail/skel
# rm -R bin boot lib libexec mnt proc rescue sbin sys usr dev
5. 建立個別環境可寫入的目錄
#cd /storage/jail/mroot
#mkdir s
#ln -s s/etc etc
#ln -s s/home home
#ln -s s/root root
#ln -s ../s/usr-local usr/local
#ln -s ../s/usr-X11R6 usr/X11R6
#ln -s ../../s/distfiles usr/ports/distfiles
#ln -s ../../s/packages usr/ports/packages
#ln -s s/tmp tmp
#ln -s s/var var
6. 建立 jailed O.S. 的 make.conf
# Add /storage/jail/skel/etc/make.conf
# WRKDIRPREFIX?= /s/portbuild
以下是每個 jailed O.S. 都要做一次
7. 設定 Host 每次開機為 jailed O.S. 掛上目錄
[FreeBSD 9 labdata2] (Why: 開機時因 ZFS 來不及掛載而無法在 /etc/fstab 處理)
Edit /etc/rc.local
### For jail
/sbin/mount -t nullfs -r /storage/jail/mroot /storage/jail/labdata2
/sbin/mount -t nullfs -rw /storage/jails/labdata2 /storage/jail/labdata2/s
[FreeBSD 8 localdata2]
Edit /etc/fstab
#/storage/jail/mroot /storage/jail/localdata2 nullfs ro 0 0
#/storage/jails/localdata2 /storage/jail/localdata2/s nullfs rw 0 0
8. 編輯 Host 的 /etc/rc.conf
###20121004
jail_enable="YES"
jail_set_hostname_allow="NO"
### 以下是清單, 有幾台 jailed O.S. 就登記幾台
jail_list="localdata2"
### 以下是每一台 jailed O.S. 的設定記得每一台都要有一組設定.(前四行是必要的)
jail_localdata2_hostname="localdata2.DOMAIN_NAME"
jail_localdata2_ip="192.168.66.66"
jail_localdata2_interface="em0"
jail_localdata2_rootdir="/storage/jail/localdata2"
jail_localdata2_devfs_enable="YES"
### 20121113 解決 netstat -rn 查詢問題
#jail_localdata2_devfs_ruleset="devfsrules_jail"
jail_localdata2_devfs_ruleset="devfsrules_jail2"
jail_localdata2_exec_start="/bin/sh /etc/rc"
jail_localdata2_exec_stop="/bin/sh /etc/rc.shutdown"
jail_localdata2_fdescfs_enable="YES"
jail_localdata2_procfs_enable="YES"
9. 建立系統目錄
mkdir /storage/jail/localdata2
mkdir /storage/jails/localdata2
cpdup /storage/jail/skel /storage/jails/localdata2
mkdir /storage/jail/localdata2/s
10. [Optional] 在 Host 編輯 /etc/sysctl.conf 開放 jailed O.S. 使用 ping.
Edit /etc/sysctl.conf
###20121113 For jail to fix ping icmp socket: Operation not permitted
security.jail.allow_raw_sockets=1
11. [Optional] 在 Host 編輯 /etc/default/devfs.rules 開放 jailed O.S. 使用 pts pty mem bpf
11.1. Edit /etc/default/devfs.rules
[devfsrules_unhide_login=3]
...
add path pts unhide
add path 'pts/*' unhide
add path pty unhide
add path 'pty/*' unhide
11.2. Edit /etc/devfs.rules
###
### http://forums.freebsd.org/archive/index.php/t-24581.html
### http://forums.freebsd.org/archive/index.php/t-5693.html
###
###
[devfsrules_unhide_mem=5]
add path mem unhide
add path kmem unhide
[devfsrules_unhide_bpf=6]
add path bpf unhide
# Devices usually found in a jail.
#
[devfsrules_jail2=7]
add include $devfsrules_hide_all
add include $devfsrules_unhide_basic
add include $devfsrules_unhide_login
add include $devfsrules_unhide_mem
add include $devfsrules_unhide_bpf
12. 掛載目錄
[FreeBSD 9]
/sbin/mount -t nullfs -r /storage/jail/mroot /storage/jail/labdata2
/sbin/mount -t nullfs -rw /storage/jails/labdata2 /storage/jail/labdata2/s
[FreeBSD 8]
mount /storage/jail/localdata2
mount /storage/jail/localdata2/s
13. 啟動 jail
# /etc/rc.d/jail start
查詢啟動的 jailed O.S.
# jls
進入 jailed O.S.
# jexec #JID tcsh (或 jexec #JID /ur/bin/su -)
14. 編輯 jailed O.S. 的系統設定
Edit /etc/rc.conf
Edit /etc/resolv.conf
...
參考資料
1. FreeBSD 使用手冊 15.6 Jail 的應用
2. Forums.freebsd.org : [Solved] jails with vnet in rc.conf
3. Forums.freebsd.org : jail nat route
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++, Java運算子優先權列表
C++
Java
:: 範圍解析 -
:: 全域範圍解析 -
------ ------ ------
() 呼叫函數 左
[] 陣列標註 左
. 成員選擇 左
-> 成員選擇(指標) 左
++ 後置遞增 左
-- 後置遞減 左
------ ------ ------
! 邏輯 NOT 右
~ 位元補數 右
+ 正 右
- 負 右
sizeof 型別大小 右
++ 前置遞增 右
-- 前置遞減 右
& 位址 右
* 間接參照 右
new 建立新物件 右
delete 刪除物件 右
------ ------ ------
() 成員(cast) 右
------ ------ ------
% 取餘數 左
* 乘 左
/ 除 左
------ ------ ------
+ 加 左
- 減 左
------ ------ ------
<< 位元左移 左
>> 位元右移 左
> 大於 左
>= 大於等於 左
< 小於 左
<= 小於等於 左
------ ------ ------
== 相等 左
!= 不等於 左
------ ------ ------
& AND位元運算 左
------ ------ ------
| OR位元運算 左
------ ------ ------
^ XOR位元運算 左
------ ------ ------
&& 邏輯AND 左
------ ------ ------
|| 邏輯OR 左
------ ------ ------
?: 條件式 右
------ ------ ------
= 指定 右
------ ------ ------
, 逗號 左
------ ------ ------
Java
() 引數 左
[] 陣列存取 左
. 成員存取 左
++ 後置遞增 左
-- 後置遞減 左
------ ------ ------
! 邏輯 NOT 右
~ 位元補數 右
+ 正 右
- 負 右
++ 前置遞增 右
-- 前置遞減 右
------ ------ ------
new 建立新物件 右
() 強制轉型(cast) 右
------ ------ ------
% 取餘數 左
* 乘 左
/ 除 左
------ ------ ------
+ 加 左
- 減 左
------ ------ ------
<< 位元左移 左
>> 位元右移 左
>>> 無符號位元右移 左
------ ------ ------
> 大於 左
>= 大於等於 左
< 小於 左
<= 小於等於 左
instanceof 資料型態比較 左
------ ------ ------
== 相等 左
!= 不等於 左
------ ------ ------
& AND位元運算 左
------ ------ ------
^ XOR位元運算 左
------ ------ ------
| OR位元運算 左
------ ------ ------
&& 邏輯AND 左
------ ------ ------
|| 邏輯OR 左
------ ------ ------
?: 條件式 右
------ ------ ------
= 指定 右
複合指定運算子 右
+= -= *= /= %=
&= |= ^= <<= >>= >>>=
------ ------ ------
C++ 範例程式 : 類別, 物件, 繼承, 類別成員, 類別函式, 多載, 覆載
類別 : Car, RacingCar
物件 : car1, mcar1, ...
類別成員 : sum
類別函式 : showSum()
多載 : Car(), RacingCar()
覆載 : show()
程式碼 include iostream
物件 : car1, mcar1, ...
類別成員 : sum
類別函式 : showSum()
多載 : Car(), RacingCar()
覆載 : show()
程式碼 include iostream
using namespace std;
#define ASIZE 3
class Car {
protected:
int num;
double gas;
public:
static int sum;
Car();
Car(int);
Car(int,double);
int setNum(int);
int setGas(double);
void setCar(int,double);
int getNum(){ return num; } //inline function
double getGas(){ return gas; } //inline function
virtual void show();
static void showSum();
};
class RacingCar : public Car {
private:
int course;
public:
static int sum;
RacingCar();
RacingCar(int);
RacingCar(int,double,int);
void setCourse(int);
int getCourse(){ return course; } //inline function
void show();
static void showSum();
};
// For class Car
int Car::sum=0;
Car::Car()
{
sum++;
cout << "製造一輛車" << endl;
num = 0;
gas = 0.0;
}
Car::Car(int n)
{
sum++;
cout << "製造一輛車" << endl;
setNum(n);
gas = 0.0;
}
Car::Car(int n, double g)
{
sum++;
cout << "製造一輛車" << endl;
setNum(n);
setGas(g);
}
int Car::setNum(int n)
{
if(n > 0)
{
num = n;
cout << "設定車輛編號 " << num << endl;
return 0;
}
else
{
cout << "無法設定車輛編號, 數值必須大於 0." << endl;
return -1;
}
}
int Car::setGas(double g)
{
if(g > 0)
{
gas = g;
cout << "設定油量 " << gas << endl;
return 0;
}
else
{
cout << "無法設定油量, 數值必須大於 0." << endl;
return -1;
}
}
void Car::setCar(int n, double g)
{
setNum(n);
setGas(g);
}
void Car::show()
{
cout << "車輛編號 " << num << " 油量 " << gas << endl;
}
void Car::showSum()
{
cout << "一共生產 " << sum << " 輛車" << endl;
}
// For class RacingCar
int RacingCar::sum = 0;
RacingCar::RacingCar()
{
sum++;
cout << "改造成一輛賽車" << endl;
course = 0;
}
RacingCar::RacingCar(int c)
{
sum++;
cout << "改造成一輛賽車" << endl;
setCourse(c);
}
RacingCar::RacingCar(int n, double g, int c) : Car(n, g)
{
sum++;
cout << "改造成一輛賽車" << endl;
setCourse(c);
}
void RacingCar::setCourse(int c)
{
if(c > 0)
{
course = c;
cout << "設定賽車跑道 " << course << endl;
}
else
{
cout << "設定賽車跑道號碼必須大於零 " << endl;
}
}
void RacingCar::show()
{
cout << "車輛編號 " << num << " 油量 " << gas << endl;
cout << "賽車跑道 " << course << endl;
}
void RacingCar::showSum()
{
cout << "一共生產 " << sum << " 輛賽車" << endl;
}
// main function
void buy(Car&);
int main()
{
Car car1;
cout << "設定 car1 資訊" << endl;
car1.setNum(1);
car1.setGas(5168.88);
cout << "已設定車輛編號 " << car1.getNum() << " 油量 " << car1.getGas() << endl;
cout << "查詢 car1 資訊" << endl;
car1.show();
cout << endl;
Car cara[ASIZE];
cout << "設定 cara 資訊" << endl;
for(int i = 0; i < ASIZE; i++)
{
cara[i].setNum(i+2);
cara[i].setGas(1000*(i+1)+688);
cout << "已設定車輛編號 " << cara[i].getNum() << " 油量 " << cara[i].getGas() << endl;
}
cout << "查詢 cara 資訊" << endl;
for(int i = 0; i < ASIZE; i++)
{
cara[i].show();
}
cout << endl;
Car *pCar;
pCar = new Car;
cout << "設定 pCar 資訊" << endl;
pCar->setNum(5);
pCar->setGas(3600);
cout << "已設定車輛編號 " << pCar->getNum() << " 油量 " << pCar->getGas() << endl;
cout << "查詢 pCar 資訊" << endl;
pCar->show();
cout << endl;
cout << "肌肉車 mcar 生產資訊" << endl;
Car mcar1(6);
mcar1.setGas(6000);
Car mcar2 = Car(7, 6800);
cout << "查詢肌肉車 mcar 資訊" << endl;
mcar1.show();
mcar2.show();
Car::showSum();
cout << "\n購買汽車" << endl;
buy(car1);
buy(cara[0]);
buy(*pCar);
//
// RacingCar
//
cout << "\n\n生產賽車 racar1" << endl;
RacingCar racar1;
racar1.setCar(8, 3600.0);
racar1.setCourse(5);
cout << "查詢賽車 racar1 資訊" << endl;
racar1.show();
RacingCar::showSum();
Car::showSum();
cout << "\n\n生產賽車 racar2" << endl;
RacingCar racar2 = RacingCar(9, 3000.0, 6);
cout << "查詢賽車 racar2 資訊" << endl;
racar2.show();
RacingCar::showSum();
Car::showSum();
cout << "\n\n賽車指標 pRacar1" << endl;
Car* pRacar1;
pRacar1 = &racar1;
pRacar1->show();
RacingCar::showSum();
Car::showSum();
cout << "\n\n車輛指標陣列 pCarArr" << endl;
Car* pCarArr[3];
cout << "車輛指標陣列 pCarArr[0] 指向 racar1" << endl;
pCarArr[0] = &racar1;
cout << "車輛指標陣列 pCarArr[1] 指向 racar2" << endl;
pCarArr[1] = &racar2;
cout << "車輛指標陣列 pCarArr[2] 生產一輛賽車" << endl;
pCarArr[2] = new RacingCar(10, 3000.0, 7);
RacingCar::showSum();
Car::showSum();
cout << "\n\n查詢車輛指標陣列 pCarArr" << endl;
for(int i = 0; i < 3; i++)
{
pCarArr[i]->show();
}
RacingCar::showSum();
Car::showSum();
cout << "\n\n賽車指標陣列 pRaCarArr" << endl;
RacingCar* pRaCarArr[3];
cout << "車輛指標陣列 pRaCarArr[0] 指向 racar1" << endl;
pRaCarArr[0] = &racar1;
cout << "車輛指標陣列 pRaCarArr[1] 指向 racar2" << endl;
pRaCarArr[1] = &racar2;
cout << "車輛指標陣列 pRaCarArr[2] 生產一輛賽車" << endl;
//pRaCarArr[2] = pCarArr[2];
//car_class_inheritence_protected-baseptr.cpp:282:26: error: invalid conversion from ‘Car*’ to ‘RacingCar*’
pRaCarArr[2] = new RacingCar(11, 5000.0, 8);
RacingCar::showSum();
Car::showSum();
cout << "\n\n查詢賽車指標陣列 pRaCarArr" << endl;
for(int i = 0; i < 3; i++)
{
pRaCarArr[i]->show();
}
RacingCar::showSum();
Car::showSum();
return 0;
}
void buy(Car& c)
{
cout << "購買了車輛編號 " << c.getNum() << " 油量 " << c.getGas() << endl;
}
C++ 範例程式 : try-catch
程式隨機產生整數, 並判斷是奇數或偶數.
程式碼 include iostream cstdlib ctime
程式碼 include iostream cstdlib ctime
using namespace std;
void func(int);
void errHandle(int);
int main()
{
char choice;
int num;
srand(time(0));
while(choice != 'N' && choice != 'n')
{
try{
num = rand()%100+1;
cout << "### " << num << " ";
func(num);
}
catch(int errValue){
errHandle(errValue);
}
cout << endl << "想要繼續玩嗎? ( Y / N ) ";
cin >> choice;
cout << endl;
}
return 0;
}
void func(int a)
{
if(a%2)
throw 7777777;
else
throw 5168888;
}
void errHandle(int e)
{
switch(e)
{
case 7777777: cout << "發現奇數" << endl; break;
case 5168888: cout << "發現偶數" << endl; break;
default: cout << "不明狀態碼" << endl; break;
}
}
C++ 範例程式: 排序程式 (一)
包含三種排序方法 : 插入排序, 氣泡排序(一般, 崗哨法), 選擇排序.
標頭檔(Header)
程式碼實作
標頭檔(Header)
void insertion_sort(int *, int);
void bubble_sort(int *, int);
void bubble_sort_sentinel(int *, int);
void selection_sort(int *, int);程式碼實作
void insertion_sort(int *a, int size)
{
// From left to right : sorted position
for(int i = 0; i < size; i++)
{
// From right to left : move small number to left
for(int j = i; j > 0; j--)
{
if(*(a+j-1) > *(a+j))
{ // a = a^b; b = a^b; a = a^b;
*(a+j-1) = *(a+j-1) ^ *(a+j);
*(a+j) = *(a+j-1) ^ *(a+j);
*(a+j-1) = *(a+j-1) ^ *(a+j);
}
}
}
}
void selection_sort(int *a, int size)
{
// Define min number of each run
int minpos;
// Find the x-th small number
for(int i = 0; i < size-1; i++)
{
// Suppose first number is the small number
minpos = i;
// From left to right : find the x-th small number
for(int j = i; j < size; j++)
{
if(*(a+j) < *(a+minpos))
minpos = j;
}
// Because using XOR exchange, you must skip this condition.
// Otherwise you will get 0. The first line of XOR exchange will do it.
if(minpos == i)
{
continue;
}
*(a+i) = *(a+i) ^ *(a+minpos);
*(a+minpos) = *(a+i) ^ *(a+minpos);
*(a+i) = *(a+i) ^ *(a+minpos);
}
}
void bubble_sort(int *a, int size)
{
for(int i = size - 1; i > 0; i--)
{
for(int j = 0; j < i; j++)
{
if(*(a+j) > *(a+j+1))
{
*(a+j) = *(a+j) ^ *(a+j+1);
*(a+j+1) = *(a+j) ^ *(a+j+1);
*(a+j) = *(a+j) ^ *(a+j+1);
}
}
}
}
void bubble_sort_sentinel(int *a, int size)
{
// Define the last swap position : sentinel
int lastswap;
// Define the position of x-th big number
for(int i = size - 1; i > 0;)
{
// Reset last swap position
lastswap = 0;
// From left to right : check each pair of numbers
for(int j = 0; j < i; j++)
{
if(*(a+j) > *(a+j+1))
{
*(a+j) = *(a+j) ^ *(a+j+1);
*(a+j+1) = *(a+j) ^ *(a+j+1);
*(a+j) = *(a+j) ^ *(a+j+1);
lastswap = j;
}
}
// Set the last swap position as the border
// Because numbers at right head had been sorted
i = lastswap;
}
}
C範例程式 : 堆疊與佇列
堆疊(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);
}
}
Subscribe to:
Posts (Atom)