幾天不寫程序手就有點生，整理了一段把圖片轉成ASCII碼的程序。暫時只支持24位真彩色圖片，ASCII碼可以自行擴充。大體算法就是把整個位圖分成8*16的小塊，計算小塊的灰度值總和，然后匹配一個灰度值接近的字符。具體算法細節可以參考網上資料。
程序源代碼可以在
這里下載。
posted @
2008-06-29 18:03 小四 閱讀(3969) |
評論 (11) |
編輯 收藏打算做一個開源的矢量繪圖軟件(類似MS Visio)，花了幾天把程序框架做了出來，自認比DrawCLI的稍微好一點點。支持基本圖形繪制，旋轉，縮放，串行化。使用MFC、STL、GDI/GDI+和一點點設計模式。
自知做一個堪用的矢量繪圖軟件是個非常艱巨的事情，不過還是打算用一些業余時間把這件事情做了，對自己以往掌握的知識，也是一個總結。
編譯好的可執行程序程序0.01版本源代碼在
這里可以下載
posted @
2008-01-29 18:16 小四 閱讀(11670) |
評論 (37) |
編輯 收藏The barrier to change is not too little caring; it is too much complexity.
To turn caring into action, we need to see a problem, see a solution, and see the impact. But complexity blocks all three steps.
If we can really see a problem, which is the first step, we come to the second step: cutting through the complexity to find a solution.
Cutting through complexity to find a solution runs through four predictable stages: determine a goal, find the highest-leverage approach, discover the ideal technology for that approach, and in the meantime, make the smartest application of the technology that you already have — whether it's something sophisticated, like a drug, or something simpler, like a bednet.
The final step – after seeing the problem and finding an approach – is to measure the impact of your work and share your successes and failures so that others learn from your efforts.
But if you want to inspire people to participate, you have to show more than numbers; you have to convey the human impact of the work – so people can feel what saving a life means to the families affected.
posted @
2008-01-15 10:04 小四 閱讀(346) |
評論 (0) |
編輯 收藏GDI+的顏色矩陣由一個5*5的float型數組構成，用來對每一個像素的顏色(R,G,B,A)做線性變換，每個像素顏色與矩陣相乘。把一幅彩色圖轉成灰度圖的算法是，假設像素點顏色為(r,g,b)，轉換成灰度圖三個顏色分量是一樣的，稱作灰階，灰階的計算是 r*0.299+g*0.587+b*0.114。我們可以逐個像素轉換，也可以使用顏色矩陣。所以彩色圖轉灰度圖的顏色矩陣為
ColorMatrix matrix =
{0.299, 0.299, 0.299, 0, 0,
0.587, 0.587, 0.587, 0, 0,
0.114, 0.114, 0.114, 0, 0,
0, 0, 0, 1, 0,
0, 0, 0, 0, 0}
這樣轉換后，灰度圖的灰階分布在0~255之間。如果想把一幅彩色圖渲染成雙色圖，定義一個深顏色darker，一個淺顏色lighter,那么灰度圖只是一個darker是黑色而lighter是白色的特例。本來分布在0~255的灰階，這樣應該分別分布在(lighter.r~darker.r),(lighter.g~darker.g),(lighter.b~darker.b)。
編寫代碼如下，使用白色和紫色。
void CDuotoneDlg::OnButton1()
{
Bitmap img(L"c:\\test1.jpg");
Graphics graphix(this->GetDC()->m_hDC);
Color darker(0);
Color lighter(8414370);
const float gray_r = 0.299f;
const float gray_g = 0.587f;
const float gray_b = 0.114f;
float offset_r = (float)darker.GetR() / 255;
float offset_g = (float)darker.GetG() / 255;
float offset_b = (float)darker.GetB() / 255;
float r = (float)(lighter.GetR() - darker.GetR()) / 255;
float g = (float)(lighter.GetG() - darker.GetG()) / 255;
float b = (float)(lighter.GetB() - darker.GetB()) / 255;
ImageAttributes imgatt;
ColorMatrix matrix =
{
gray_r*r, gray_r*g, gray_r*b, 0, 0,
gray_g*r, gray_g*g, gray_g*b, 0, 0,
gray_b*r, gray_b*g, gray_b*b, 0, 0,
0, 0, 0, 1, 0,
offset_r, offset_g, offset_b, 0, 1
};
imgatt.SetColorMatrix(&matrix, ColorMatrixFlagsDefault, ColorAdjustTypeBitmap);
int iWidth = img.GetWidth();
int iHeight = img.GetHeight();
graphix.DrawImage(
&img,
Rect(0, 0, iWidth, iHeight),
0.0f,
0.0f,
iWidth,
iHeight,
UnitPixel,
&imgatt);
graphix.ReleaseHDC(this->GetDC()->m_hDC);
}
渲染圖片測試
posted @
2008-01-05 14:01 小四 閱讀(652) |
評論 (0) |
編輯 收藏
摘要: 表達式求值的關鍵點在于中綴表達式轉后綴表達式，算法書上都有明確介紹就不多說了。動手實現了一個表達式解析器，支持括號、多位整數以及表達式合法性判斷。今天的狀態實在很差，本想對表達式進行合法性判斷的時候使用一些類似哈希表的技巧，比如使用一個大的bool數組，合法字符ASC碼對應的項設置為1，比如可以直接判斷CHARS['+']是否為true,省去查找的時間。后來發現一共就支持那幾個字符，這樣做未免有點...
閱讀全文
posted @
2008-01-04 19:59 小四 閱讀(697) |
評論 (0) |
編輯 收藏二叉排序樹，又稱二叉查找樹，左子樹結點值一律小于父結點，右子樹結點值一律大于父結點，查找平均算法復雜度為O(logn)。
還是那道統計單詞數目的題目，使用二叉排序樹來解決，查找和插入以及統計數目使用一個函數解決，比使用哈希表的優勢在于，中序遍歷輸出結果，單詞是有序的。
程序中需要注意的地方，釋放樹結點的時候，要使用后續遍歷，先釋放子結點后才釋放根結點。
/**//* -------------------------------------------------------------------------
// 文件名 ： binarytree.h
// 創建者 ： dj
// 創建時間 ： 2008-1-1
// 功能描述 ： 二叉排序樹
// -----------------------------------------------------------------------*/
#ifndef __BINARYTREE_H__
#define __BINARYTREE_H__
#define SAFE_DELETE(p) {if(p) { delete [] (p); (p) = NULL;}}
struct TreeNode
{
TreeNode(const char* s):
counter(1), left(NULL), right(NULL)
{
name = new char[strlen(s)+1];
strcpy(name, s);
}
~TreeNode()
{
SAFE_DELETE(name);
}
char* name;
int counter;
TreeNode* left;
TreeNode* right;
};
class BinaryTree
{
public:
BinaryTree():m_pRoot(NULL)
{}
~BinaryTree()
{
FreeTree(m_pRoot);
}
void Lookup(const char* sName)
{
TreeNode** p = &m_pRoot;
while(*p)
{
int cmp = strcmp(sName, (*p)->name);
if (cmp<0)
p = &((*p)->left);
else if (cmp>0)
p = &((*p)->right);
else //found the word
{
((*p)->counter)++; //increase the counter
return;
}
}
// not found, then add the word node.
TreeNode* pNode = new TreeNode(sName);
*p = pNode;
}
void Dump(const char* sFile)
{
ofstream f(sFile);
Travel(m_pRoot, f);
f.close();
}
private:
void Travel(TreeNode* pNode, ofstream& f)
{
if (!pNode)
return;
Travel(pNode->left, f);
f<<pNode->name<<" "<<pNode->counter<<endl;
Travel(pNode->right, f);
}
void FreeTree(TreeNode* pNode)
{
if(!pNode)
return;
FreeTree(pNode->left);
FreeTree(pNode->right);
delete pNode;
}
private:
TreeNode* m_pRoot;
};
#endif //__BINARYTREE_H__
int main(int argc, char* argv[])
{
BinaryTree tree;
ifstream f("c:\\ip.txt");
string s;
while(f>>s)
{
tree.Lookup(s.c_str());
}
tree.Dump("c:\\stat.txt");
return 0;
}
posted @
2008-01-01 21:49 小四 閱讀(418) |
評論 (0) |
編輯 收藏
折半查找又叫二分查找，要求查找表本身必須是有序的。查找算法復雜度為O(logn)。C標準庫提供折半查找的庫函數，聲明如下
bsearch(const void *, const void *, size_t, size_t, int (__cdecl *)(const void *, const void *));
最后一個參數要求一個指向比較函數的指針。程序設計實踐上寫道，為bsearch提供一個key就這么費勁，寫一個好的通用的排序程序也不容易，即使這樣，使用bsearch而不是自己另外寫仍然是個好主意。
多年的歷史證明，程序員能把二分檢索程序寫正確也是很不容易的(Over the years, binary search has proven surprisingly hard for programmer to get right)。
于是自己用模板寫一個折半查找函數，寫好一個十幾行的程序，也不是看上去那么簡單的事情。
template<typename T>
int binarysearch(const T* tab, int ntab, const T& value)
{
int low = 0;
int high = ntab;
while(low <= high)
{
int mid = (low+high)/2;
if(value<tab[mid])
high = mid - 1;
else if (value>tab[mid])
low = mid + 1;
else
return mid;
}
return -1;
}
測試程序
int main(int argc, char* argv[])
{
int a[] = {2, 4, 6, 7, 8, 9, 13};
int aa = sizeof(a);
int n = binarysearch(a, sizeof(a)/sizeof(a[0]), 4);
cout<<n<<endl;
return 0;
}
posted @
2008-01-01 17:59 小四 閱讀(1072) |
評論 (0) |
編輯 收藏
摘要: 寫了一個哈希表模板類，用于統計一篇文章中不同單詞出現的次數。哈希表使用char*作為key,使用桶式鏈表指針數組(指向結點鏈表的指針數組)來索引，字符串哈希函數是在網上搜來的。模板參數一個是值類型，另一個NBARREL是指針數組的大小，通常是越大哈希值沖突就越少，結點鏈表長度也就越短，當然查找就越快。
為了方便統計，為哈希表增加了一個IncValue函數，提高效率。統計的時候使用了快速排序，為了...
閱讀全文
posted @
2007-12-30 15:13 小四 閱讀(544) |
評論 (0) |
編輯 收藏在程序設計實踐上看到這個簡單的快速排序，用模板重新寫了一遍，加深一下印象。平均算法復雜度為O(nlogn)。
其中尋找支點元素pivot有多種方法，不同的方法會導致快速排序的不同性能。根據分治法平衡子問題的思想，希望支點元素可以使p[m..n]盡量平均地分為兩部分，但實際上很難做到。下面給出幾種尋找pivot的方法。
1.選擇p[m..n]的第一個元素p[m]的值作為pivot；
2.選擇p[m..n]的最后一個元素p[n]的值作為pivot；
3.選擇p[m..n]中間位置的元素p[k]的值作為pivot；
4.選擇p[m..n]的某一個隨機位置上的值p[random(n-m)+m]的值作為pivot；
按照第4種方法隨機選擇pivot的快速排序法又稱隨機化版本的快速排序法，在實際應用中該方法的性能也是最好的。本程序使用第4種方法。要求節點類型支持比較運算符。
template<typename T>
void quicksort(T* v, int n)
{
if (n<=1)
return;
int last = 0;
int pivot = rand()%n;
swap(v, 0, pivot);
for (int i = 1; i < n; i++)
{
if (v[i]<v[0])
swap(v, ++last, i);
}
swap(v, last, 0);
quicksort(v, last);
quicksort(v+last+1, n-last-1);
}
template<typename T>
void swap(T* v, int i, int j)
{
T tmp = v[i];
v[i] = v[j];
v[j] = tmp;
}
隨手寫一個不太好看的測試程序
struct str
{
str(const char* a)
{
assert(a);
v = new char[strlen(a)+1];
strcpy(v, a);
}
str(const str& a)
{
assert(a.v);
v = new char[strlen(a.v)+1];
strcpy(v, a.v);
}
~str()
{
delete [] v;
}
void operator = (const str& a)
{
if (this == &a)
return;
assert(a.v);
delete [] v;
v = new char[strlen(a.v)+1];
strcpy(v, a.v);
}
bool operator == (const str& a) const
{
return (strcmp(v, a.v)==0);
}
bool operator > (const str& a) const
{
return (strcmp(v, a.v)>0);
}
bool operator < (const str& a) const
{
return (strcmp(v, a.v)<0);
}
char* v;
};
int main(int argc, char* argv[])
{
int* array = new int [10];
for(int i = 0; i < 10; i++)
array[i] = rand();
quicksort(array, 10);
for(i = 0; i < 10; i++)
{
cout<<array[i]<<endl;
}
str s[] = {"bd", "e", "ba", "a"};
quicksort(s, 4);
for(i = 0; i < 4; i++)
{
cout<<s[i].v<<endl;
}
return 0;
}
posted @
2007-12-29 14:31 小四 閱讀(405) |
評論 (0) |
編輯 收藏復習一下數據結構，用鏈表實現了一個堆棧模板類。
寫的過程中用到一些知識點，碰到一些問題，隨手記下來。
1：mystack<int> s; mystack<int> s2 = s;
編譯器會把s2 = s編譯成拷貝構造函數s2(s)，此時調用的是拷貝構造函數，而不是賦值函數(切記)。
另外有時候編譯器這種自做聰明，自動調用符合參數類型的構造函數會帶來很難發現的錯誤，為了防止編譯器這么做，可以在構造函數聲明前加explicit關鍵字。
2：不改變成員變量值的函數，例如empty()，要聲明為const,這點很重要，不然當一個const mystack&類型的對象調用empty()的時候，會編不過。
3：拷貝構造函數最好要先判斷是否是拷貝自身，不然有時候就出錯。
4：拷貝構造函數也別忘了成員變量初始化列表。
template<typename T>
class mystack
{
public:
mystack();
mystack(const mystack& src);
~mystack();
bool push(const T& data);
T pop();
bool empty() const;
void clear();
mystack& operator = (const mystack& src);
private:
void copystack(mystack& dst, const mystack& src);
struct stacknode
{
T data;
stacknode* pnext;
};
stacknode* phead;
};
template<typename T>
mystack<T>::mystack():phead(NULL)
{}
template<typename T>
mystack<T>::mystack(const mystack<T>& src):
phead(NULL)
{
copystack(*this, src);
}
template<typename T>
mystack<T>::~mystack()
{
clear();
}
template<typename T>
void mystack<T>::clear()
{
while(!empty())
{
pop();
}
}
template<typename T>
void mystack<T>::copystack(mystack& dst, const mystack& src)
{
stacknode* p = src.phead;
mystack<T> tmp;
while(p)
{
tmp.push(p->data);
p = p->pnext;
}
while(!tmp.empty())
{
dst.push(tmp.pop());
}
}
template<typename T>
mystack<T>& mystack<T>::operator=(const mystack& src)
{
if (this == &src)
return *this;
clear();
copystack(*this, src);
return *this;
}
template<typename T>
bool mystack<T>::empty() const
{
return(phead == NULL);
}
template<typename T>
bool mystack<T>::push(const T& data)
{
stacknode* p = new stacknode;
if (!p) return false;
p->data = data;
p->pnext = phead;
phead = p;
return true;
}
template<typename T>
T mystack<T>::pop()
{
assert(!empty());
T data;
data = phead->data;
stacknode* tmp = phead;
phead = phead->pnext;
delete tmp;
return data;
}
int main(int argc, char* argv[])
{
mystack<int> s;
for (int i = 0; i < 1000; i++)
s.push(rand());
mystack<int> s2(s);
while(!s2.empty())
{
cout<<s2.pop()<<endl;
}
return 0;
}
posted @
2007-12-27 13:15 小四 閱讀(376) |
評論 (1) |
編輯 收藏