我想只使用一個非常基本的,程序性的方法來創建一個字謎求解。我發現我可能應該使用類來完成這項工作,但現在已經太晚了,我的任務已經到期了。任何關於如何解決這個問題的建議都會很棒!字謎發生器C++(不使用STL)
基本上,這是該算法應該做的:
- 獲取字典中的所有單詞;將它們存儲在容器中
- 從用戶那裏獲取一個詞;退出如果合適
- 獲取用戶輸入的
- 地帶用戶從排列
- 地帶輸入的詞單詞的所有排列排列集合中不是也是我收集了一部分字典中的所有單詞1
現在對於最後一步,我必須確保我不顯示重複的anagrams(即包含相同字母的anagrams,例如「loop」)。我似乎無法得到此檢查的工作,這在TODO註釋塊下面註明。
任何建議將是真棒!
#include <iostream>
#include <fstream>
#include <string>
//
// Change size below to accomodate more anagrams and dictionary words
//
#define MAX_ANGM_SIZE 4096
#define MAX_WORD_SIZE 1048576
using namespace std;
//
// Determines whether anagram is valid or not; will not display word
// which user entered or words not contained in dictionary
//
bool isValidAnagram(string word, string userWord,
string dictionary[], unsigned int listIdx)
{
for(unsigned int idx = 0; idx < listIdx; ++idx)
{
if(word == userWord)
return false;
else if (word == dictionary[idx])
return true;
}
return false;
}
//
// Determines whether user's word is contained in the dictionary
// or not
//
bool isValidWord(string word, string dictionary[],
unsigned int listIdx)
{
for(unsigned int idx = 0; idx < listIdx; ++idx)
{
if(word == dictionary[idx])
return true;
}
return false;
}
//
// TODO:This function should test for duplicate anagrams and return
// true if duplicates are found.
//
bool isRepeated(string anagrams[], unsigned int anaIdx)
{
for(unsigned int idx = anaIdx; idx != 0; --idx)
{
if(anagrams[idx] == anagrams[anaIdx])
return true;
else
return false;
}
return false;
}
//
// Only display elements in array which aren't blank and don't
// display duplicate anagrams; notify user if no anagrams
// were found.
//
void displayAnagrams(string anagrams[], unsigned int next)
{
int flag = 0;
for (unsigned int idx = 0; idx < next; ++idx)
{
if((anagrams[idx] != "") || (!(isRepeated(anagrams, idx))))
{
if(idx == 1)
cout << " Anagrams: ";
if(idx > 0)
flag = 1;
cout << anagrams[idx] << " ";
}
else
continue;
}
if(flag == 0)
cout << " no anagrams found" << endl;
}
static void swap(char &c1, char &c2)
{
char temp = c1;
c1 = c2;
c2 = temp;
}
//
// Pass in word to be altered, the userWord for comparison, the array to store
// anagrams, the dictionary for comparison, the count for the number of anagrams
// and the count for number of dictionary words
//
static void permute(string word, string userWord, int k, string anagrams[],
string dictionary[], unsigned int &next, unsigned int listIdx)
{
if(k == word.length()-1)
{
if(isValidAnagram(word, userWord, dictionary, listIdx))
anagrams[next] = word;
++next;
}
else
{
for(int idx = k; idx < word.length(); ++idx)
{
swap(word[k], word[idx]);
permute(word, userWord, k+1, anagrams, dictionary, next, listIdx);
}
}
}
//
// Create container to store anagrams, validate user's word in dictionary, get all
// of the anagrams, then display all valid anagrams
//
void getAnagrams(string word, string dictionary[], unsigned int listIdx)
{
string anagrams[MAX_ANGM_SIZE];
unsigned int next = 0;
if(isValidWord(word, dictionary, listIdx))
{
permute(word, word, 0, anagrams, dictionary, next, listIdx);
}
else
{
cerr << " \"" << word << "\"" << " is not a valid word" << endl;
return;
}
displayAnagrams(anagrams, next);
}
//
// Read in dictionary file, store contents of file in a list, prompt
// the user to type in words to generate anagrams
//
int main()
{
string file;
string word;
string quit = "quit";
string dictionary[MAX_WORD_SIZE];
unsigned int idx = 0;
cout << "Enter a dictionary file: ";
cin >> file;
cout << "Reading file \"" << file << "\"" << endl;
cout << endl;
ifstream inFile(file.c_str());
if(!(inFile.is_open()))
{
cerr << "Can't open file \"" << file << "\""
<< endl;
exit(EXIT_FAILURE);
}
while(!inFile.eof())
{
inFile >> dictionary[idx];
++idx;
}
inFile.close();
while(true)
{
cout << "Enter a word: ";
cin >> word;
if(word == quit) break;
getAnagrams(word, dictionary, idx);
cout << endl;
}
return 0;
}
爲什麼要避免使用STL? (畢竟,你使用'string',它符合STL容器的大部分要求......) –
這實際上是一個STL類,但這是第一個任務,我還沒有使用STL。這項任務的目標是使用標準技術,然後在我們知道如何使用STL時,在術語末尾完成相同的任務。 – dtg
啊,我明白了。那麼,只是一個FYI - 'std :: string'暴露了一個主要是STL序列容器接口。 (但是,如果你想要學習迂迴,字符串庫早於STL加入標準) –