一、符號表
定義：符號表是一種存儲鍵值對的數(shù)據(jù)結構，支持兩種操作：插入(put)着饥，即將一組新的兼職對存入表中探膊；查找(get)，即根據(jù)給定的鍵得到相應的值奴潘。
創(chuàng)建符號表
無序符號表
符號表即是鍵值對的存儲結構，結合最近剛學習的類的定義，將符號表寫成類的形式喉誊，對用戶隱藏了鍵值對的數(shù)據(jù)，留給用戶一下接口調(diào)用鍵值對纵顾。
首先是創(chuàng)建一個無序表伍茄，無序表的創(chuàng)建比較簡單。輸入什么鍵值對便存儲什么鍵值對施逾。
// JunzHeader.h
#ifndef JunzHeader_H_
#define JunzHeader_H_
struct DATA
{
char key;
int value;
};
typedef DATA DataType;
class SLType
{
private:
enum { MAX = 100 }; // define the max length of table
DataType data[MAX];
int TbLength; // length at present
public:
SLType(); // create an empty table
int CalculateLength(); // calculate the length of Table
bool insertNode(); // insert a node
bool deleteNode(DataType kv); // delete a node
int searchNode(DataType kv); // search a node
void show() const; // display table
};
#endif // !JunzHeader_H_
//JunzHeader.cpp
#include<iostream>
#include"JunzHeader.h"
// create an empty table
SLType::SLType()
{
for (int i = 0; i < MAX; i++)
data[i] = { '0', 0 };
TbLength = 0;
}
int SLType::CalculateLength()
{
return TbLength;
}
bool SLType::insertNode()
{
using std::cout;
using std::cin;
if (TbLength >= MAX - 1)
return false;
else
{
cout << "Please input the key: ";
cin >> data[TbLength].key;
cout << "Please input the value: ";
cin >> data[TbLength].value;
TbLength = TbLength + 1;
return true;
}
}
int SLType::searchNode(DataType kv)
{
int temp = -2;
if (TbLength == 0)
{
return -1;
}
else
{
for (int i = 0; i < TbLength; i++)
{
if (kv.key == data[i].key)
temp = i;
else
continue;
}
return temp;
}
}
bool SLType::deleteNode(DataType kv)
{
if (TbLength == 0)
return false;
else
{
int temp = searchNode(kv);
if (temp == -2)
return false;
else
{
for (int j = temp + 1; j < TbLength; j++)
{
data[j - 1].key = data[j].key;
data[j - 1].value = data[j].value;
}
TbLength = TbLength - 1;
return true;
}
}
}
void SLType::show() const
{
using std::cout;
using std::endl;
for (int i = 0; i < TbLength; i++)
{
cout << data[i].key << " " << data[i].value << endl;
}
}
//Main.cpp
#include <iostream>
#include "JunzHeader.h"
using namespace std;
const int NUM = 5;
int main()
{
SLType ST; // create an empty table
bool flag;
for (int i = 0; i < NUM; i++)
{
flag = ST.insertNode();
if (flag == false)
{
cout << "Input Error in " << i + 1 << "step!" << endl;
break;
}
}
cout << "A:10 is in " << ST.searchNode({ 'A',10 }) + 1 << endl;
ST.deleteNode({ 'A',10 });
cout << "A:10 is delete!" << endl;
ST.show();
system("pause");
return 0;
}
有序符號表
上面這種符號表僅實現(xiàn)了<Key,Value>對的存儲敷矫。經(jīng)過咨詢做服務器的同學例获，這種存儲有時候需要使有序的，有序可以是鍵的有序曹仗，也可以是值的有序榨汤。但是<Key,Value>中強調(diào)的是通過Key尋求對應的Value值，因此整葡，采用鍵有序是比較合理的件余。順序符號表的好處是易查找。但是它需要在插入和刪除表元素中付出較無序表更加高昂的代價遭居。
//JunzHeader.h
#ifndef JunzHeader_H_
#define JunzHeader_H_
struct DATA
{
char key;
int value;
};
typedef DATA DataType;
class SLType
{
private:
enum { MAX = 100 }; // define the max length of table
DataType data[MAX];
int TbLength; // length at present
public:
SLType(); // create an empty table
int CalculateLength(); // calculate the length of Table
bool insertNode(); // insert a node
bool deleteNode(DataType kv); // delete a node
int searchNode(DataType kv); // search a node
void show() const; // display table
};
#endif // !JunzHeader_H_
//JunzFuncDef.cpp
#include<iostream>
#include"JunzHeader.h"
// create an empty table
SLType::SLType()
{
for (int i = 0; i < MAX; i++)
data[i] = { '0', 0 };
TbLength = 0;
}
int SLType::CalculateLength()
{
return TbLength;
}
bool SLType::insertNode()
{
using std::cout;
using std::cin;
int Lc = TbLength;
DataType temp;
if (TbLength >= MAX - 1)
return false;
else
{
cout << "Please input the key: ";
cin >> data[TbLength].key;
cout << "Please input the value: ";
cin >> data[TbLength].value;
temp = data[TbLength];
for (int i = TbLength; i >= 0; i--)
{
if (data[TbLength].key < data[i].key)
Lc = i;
else
continue;
}
if (Lc != TbLength)
{
for (int j = TbLength; j > Lc; j--)
{
data[j] = data[j - 1];
}
data[Lc] = temp;
}
TbLength = TbLength + 1;
return true;
}
}
int SLType::searchNode(DataType kv)
{
int temp = -2;
if (TbLength == 0)
{
return -1;
}
else
{
for (int i = 0; i < TbLength; i++)
{
if (kv.key == data[i].key)
temp = i;
else
continue;
}
return temp;
}
}
bool SLType::deleteNode(DataType kv)
{
if (TbLength == 0)
return false;
else
{
int temp = searchNode(kv);
if (temp == -2)
return false;
else
{
for (int j = temp + 1; j < TbLength; j++)
{
data[j - 1].key = data[j].key;
data[j - 1].value = data[j].value;
}
TbLength = TbLength - 1;
return true;
}
}
}
void SLType::show() const
{
using std::cout;
using std::endl;
for (int i = 0; i < TbLength; i++)
{
cout << data[i].key << " " << data[i].value << endl;
}
}
//Main.cpp
#include <iostream>
#include <fstream>
#include <string>
#include "JunzHeader.h"
using namespace std;
const int NUM = 5;
int main()
{
SLType ST; // create an empty table
bool flag;
for (int i = 0; i < NUM; i++)
{
flag = ST.insertNode();
if (flag == false)
{
cout << "Input Error in " << i + 1 << "step!" << endl;
break;
}
}
ST.show();
cout << "A:10 is in " << ST.searchNode({ 'A',10 }) + 1 << endl;
ST.deleteNode({ 'A',10 });
cout << "A:10 is delete!" << endl;
ST.show();
system("pause");
return 0;
}
符號表的應用
符號表的其中一種應用是詞頻統(tǒng)計啼器。上面的符號表需要根據(jù)詞頻統(tǒng)計的需求進行一定的修改。
1俱萍、插入鍵值對不再需要鍵入進行插入端壳，而是從txt文本中按字符串插入。
2枪蘑、尋找鍵值對需要通過鍵進行搜尋损谦，并非通過鍵值對。
3岳颇、需要加入一個修改value值的函數(shù)照捡，對詞頻進行計數(shù)。
4话侧、需要在插入時判斷key是否已經(jīng)存在栗精。
//JunzHeader.h
#include <iostream>
#ifndef JunzHeader_H_
#define JunzHeader_H_
struct DATA
{
std::string key;
int value;
};
typedef DATA DataType;
class SLType
{
private:
enum { MAX = 100 }; // define the max length of table
DataType data[MAX];
int TbLength; // length at present
public:
SLType(); // create an empty table
int CalculateLength(); // calculate the length of Table
bool insertNode(std::string & str); // insert a node
int searchNode(std::string & str); // search a node
bool ModifyVal(std::string & str); // modify the value in a certain key
void show() const; // display table
};
#endif // !JunzHeader_H_
//JunzFuncDef.cpp
#include<iostream>
#include<string>
#include"JunzHeader.h"
// create an empty table
SLType::SLType()
{
for (int i = 0; i < MAX; i++)
data[i] = { "0000", 0 };
TbLength = 0;
}
int SLType::CalculateLength()
{
return TbLength;
}
bool SLType::insertNode(std::string & s)
{
using std::cout;
using std::cin;
int Lc = TbLength;
DataType temp;
if (TbLength >= MAX - 1)
return false;
else
{
data[TbLength].key = s;
data[TbLength].value += 1;
temp = data[TbLength];
for (int i = TbLength; i >= 0; i--)
{
if (data[TbLength].key < data[i].key)
Lc = i;
else
continue;
}
if (Lc != TbLength)
{
for (int j = TbLength; j > Lc; j--)
{
data[j] = data[j - 1];
}
data[Lc] = temp;
}
TbLength = TbLength + 1;
return true;
}
}
int SLType::searchNode(std::string & str)
{
int temp = -2;
if (TbLength == 0)
{
return -1;
}
else
{
for (int i = 0; i < TbLength; i++)
{
if (str == data[i].key)
temp = i;
else
continue;
}
return temp;
}
}
void SLType::show() const
{
using std::cout;
using std::endl;
for (int i = 0; i < TbLength; i++)
{
cout << data[i].key << " " << data[i].value << endl;
}
}
bool SLType::ModifyVal(std::string & str)
{
int index_tmp = searchNode(str);
if (index_tmp < 0)
return false;
else
{
data[index_tmp].value += 1;
return true;
}
}
//Main.cpp
#include <iostream>
#include <fstream>
#include <string>
#include "JunzHeader.h"
using namespace std;
const int NUM = 5;
int main()
{
SLType ST;
bool flag1,flag2;
ifstream ifs("tinyTale.txt");
string temp;
while (ifs >> temp)
{
if (ST.searchNode(temp) < 0)
{
flag1 = ST.insertNode(temp);
if (flag1 == false)
{
cout << "Input Error!!!" << endl;
break;
}
}
else
flag2 = ST.ModifyVal(temp);
}
ifs.close();
ST.show();
system("pause");
return 0;
}
所采用的tinyTale.txt文件采用了狄更斯的《雙城記》中的一段話:
it was the best of time it was the worst of times
it was the age of wisdom it was the age of foolishness
it was the epoch of belief it was the epoch of incredulity
it was the season of light it was the season of darkness
it was the spring of hope it was the winter of despair
最后統(tǒng)計可以得到如下結果：
不僅統(tǒng)計了詞頻，而且單詞是按照字母排序的瞻鹏。
當然悲立，C++有更加高級的<Key,Value>模板可供選擇，本人的這個程序只是對符號表理解后新博，結合類的思想薪夕，對其進行一個簡單的實現(xiàn)。
C++可以使用unordered_map來實現(xiàn)<Key,Value>模板赫悄！更高效快捷地創(chuàng)建符號表原献。
查找算法
無序鏈表的順序查找
無序鏈表的順序查找的思路非常簡單。通過遍歷搜索和比較埂淮，查找到對應的鍵值對嚼贡。
這種方法實現(xiàn)比較簡單，之前的代碼就是通過順序查找的方法對相應值進行搜尋的同诫。但無序鏈表的順序查找算法的復雜度比較高，不利于實際的搜索樟澜。因此误窖，我們需要尋找一些更加便捷的算法叮盘。
向一個空表中插入N個不同的鍵需要~N^2/2次比較
有序數(shù)組的二分查找
1、二分查找所使用的符號表的數(shù)據(jù)結構是一對平行的數(shù)組霹俺，一個數(shù)組存儲鍵柔吼，一個數(shù)組存儲值。這樣方便查找數(shù)據(jù)丙唧。
2愈魏、使用有序數(shù)組存儲鍵值對的好處上面已經(jīng)提到，雖然在插入時步驟比較麻煩想际，但是在查詢時能夠使用復雜度更低的算法培漏。
二分查找可以用兩種方法實現(xiàn)：
--根據(jù)之前的學習，通常對數(shù)組一分為二胡本，再二分為四等等的方法讓我想到了歸并排序以及快速排序的處理牌柄。沒錯，這樣的處理能采用遞歸思想侧甫。
--但遞歸算法比較麻煩珊佣，遞歸算法對我們這些小白特別不友好。因此披粟，可以采用迭代的方法進行處理咒锻。
先來看一個遞歸的版本,只需要在頭文件處加入聲明二分查找函數(shù)的語句：
// addition in JunzHeader.h
int Binarysearch(char k, int lo, int hi);
然后在定義中加入該二分查找函數(shù)即可：
// JunzFuncDef.cpp
#include<iostream>
#include<string>
#include"JunzHeader.h"
// create an empty table
SLType::SLType()
{
for (int i = 0; i < MAX; i++)
{
Key[i] = '0';
Value[i] = 0;
}
TbLength = 0;
}
int SLType::CalculateLength()
{
return TbLength;
}
bool SLType::insertNode()
{
using std::cout;
using std::cin;
int Lc = TbLength;
char temp1;
int temp2;
if (TbLength >= MAX - 1)
return false;
else
{
cout << "Please Input the Key: ";
cin >> Key[TbLength];
cout << "Please Input the value: ";
(cin >> Value[TbLength]).get();
temp1 = Key[TbLength];
temp2 = Value[TbLength];
int index = Binarysearch(Key[TbLength], 0, TbLength);
Lc = index;
if (Lc != TbLength)
{
for (int j = TbLength; j > Lc; j--)
{
Key[j] = Key[j - 1];
Value[j] = Value[j - 1];
}
Key[Lc] = temp1;
Value[Lc] = temp2;
}
TbLength = TbLength + 1;
return true;
}
}
int SLType::Binarysearch(char k, int lo, int hi)
{
if (hi <= lo)
return lo;
int mid = (hi - lo) / 2 + lo;
if (k < Key[mid])
return Binarysearch(k, lo, mid - 1);
else if (k > Key[mid])
return Binarysearch(k, mid + 1, hi);
else
return mid;
}
std::ostream & operator<<(std::ostream & os, const SLType & s)
{
for (int i = 0; i < s.TbLength; i++)
{
os << s.Key[i] << " " << s.Value[i] << "\n";
}
return os;
}
遞歸固然能幫助理解思路，但是迭代更加高效守屉。所以二分查找也有迭代版本：
//
int SLType::Binarysearch(char k, int lo, int hi)
{
int mid = 0;
while (true)
{
if (hi <= lo)
break;
mid = lo + (hi - lo) / 2;
if (Key[mid] < k)
{
lo = mid + 1;
continue;
}
else if (Key[mid] > k)
{
hi = mid - 1;
continue;
}
else
return mid;
}
return lo;
}
這里在編程的時候惑艇，return lo處我一開始編寫的是return mid。這樣是不對的胸梆，因為mid有可能會因為lo和hi取到前半段而變小敦捧。此時，mid已經(jīng)失去了元素可插入位置的信息碰镜。所以兢卵，應該采用lo作為返回值。
這里我總結一下我理解的迭代和遞歸在算法中的實現(xiàn)绪颖。
遞歸即是通過函數(shù)重復有規(guī)律的步驟秽荤。
迭代即是通過循環(huán)改變某些變量，以重復相同的步驟柠横。
遞歸是為了減少繁雜的邏輯而想出的巧妙的解決方法窃款。一般我們說“天才程序員使用遞歸”。比如漢諾塔游戲牍氛，如果采用非遞歸方法實現(xiàn)的話晨继，太繁雜。而使用遞歸僅用幾行代碼便可實現(xiàn)搬俊。但是遞歸的性能比較差紊扬，因此不是所有的算法都用遞歸實現(xiàn)就可以蜒茄。
迭代是以邏輯來設計的解決方法。雖然說使用遞歸比較帥餐屎，比較牛檀葛。但是有時候迭代的性能要比遞歸高的多。
所以使用迭代還是遞歸腹缩，需要取決實際屿聋。
一般情況下二分查找都比順序查找快得多，它也是眾多實際應用程序的最佳選擇藏鹊。
