알고리즘 의 미소스 코드 발표 (9)
부록 중의 고전 필기시험, 면접 문제 참고 답안 은 다음 과 같 습 니 다.
http://blog.csdn.net/baimafujinji/article/details/50484683
In genel, 나 는 책 한 권 (기술 서) 을 펼 치 는 것 을 그다지 좋아 하지 않 는 다. 그 안에 빽빽 한 것 은 모두 코드 이다.그래서 나 도 내 책 에 원 리 를 토론 할 수 있 는 공간 을 더 많이 남 겼 으 면 좋 겠 다.물론 코드 도 중요 하 다. 모든 원 리 는 결국 코드 에 실 현 돼 야 한다.이 때문에 나 는 그들 을 모두 책 에 나열 해서 편폭 을 차지 하 는 것 이 아니 라 블 로그 에 코드 를 올 리 는 것 에 익숙 하 다.
만약 당신 이 이 책의 독자 라면 알고리즘 학습 군 (495573865) 에 가입 하 는 것 을 강력 히 건의 합 니 다. 그 안에 더 많은 자원 이 당신 을 기다 리 고 있 습 니 다. 그리고 당신 이 책 을 읽 으 면서 만난 의문 도 제 첫 번 째 시간의 해답 을 얻 을 수 있 습 니 다.본 블 로그 에 더 많은 관심 을 가지 고 있 습 니 다. 저 는 이 책의 모든 소스 코드 를 본 블 로그 에 계속 발표 할 것 입 니 다.
P327: 벡터 집합 성명 부분
Vectet. h 파일
#ifndef VECSET_H
#define VECSET_H
#include <iostream>
#include <assert.h>
using namespace std;
const int DefaultSize = 100;
class VecSet
{
int* contain;
int size;
public:
VecSet(int MaxSize = DefaultSize);
~VecSet();
void Add(int add);
void Del(int del);
void MakeEmpty();
int GetSize(){return size;}
bool IsMember(const int x);
VecSet& operator+(VecSet& another);
VecSet& operator-(VecSet& another);
VecSet& operator*(VecSet& another);
VecSet& operator=(VecSet& another);
bool operator==(VecSet& another);
friend ostream& operator<<(ostream& stream,VecSet& set);
};
#endifP329: 벡터 집합의 실현 부분
Vectet. cpp 파일
#include "VecSet.h"
VecSet::~VecSet()
{
if(contain != NULL)
delete [] contain;
}
VecSet::VecSet(int MaxSize):size(MaxSize){
assert(MaxSize>0);
contain = new int[size];
assert(contain != NULL);
MakeEmpty();
}
void VecSet::Add(int add){
assert(add>=0 && add<size);
contain[add]=1;
}
void VecSet::Del(int del){
assert(del>=0 && del<size);
contain[del]=0;
}
void VecSet::MakeEmpty(){
for(int i=0;i<size;i++){
contain[i]=0;
}
}
bool VecSet::IsMember(const int x)
{
assert(x >= 0 && x < size);
return contain[x] != 0;
}
VecSet& VecSet::operator+(VecSet& another){
assert(this->GetSize() == another.GetSize());
VecSet* temp = new VecSet(this->GetSize());
for(int i=0;i<size;i++){
(*temp).contain[i] = contain[i]||another.contain[i];
}
return *temp;
}
VecSet& VecSet::operator-(VecSet& another){
assert(this->GetSize() == another.GetSize());
VecSet* temp = new VecSet(this->GetSize());
for(int i=0;i<size;i++){
(*temp).contain[i] = contain[i]&&(!another.contain[i]);
}
return *temp;
}
VecSet& VecSet::operator*(VecSet& another){
assert(this->GetSize() == another.GetSize());
VecSet* temp = new VecSet(this->GetSize());
for(int i=0;i<size;i++){
(*temp).contain[i] = contain[i]&&another.contain[i];
}
return *temp;
}
VecSet& VecSet::operator=(VecSet& another){
assert(this->GetSize() == another.GetSize());
for(int i=0;i<size;i++){
contain[i] = another.contain[i];
}
return
*this;
}
bool VecSet::operator == (VecSet& another){
assert(this->GetSize() == another.GetSize());
for(int i=0;i<size;i++){
if(contain[i] != another.contain[i]){
return false;
}
}
return true;
}
ostream& operator<<(ostream& stream,VecSet& set){
for(int i=0;i<set.GetSize();i++){
if(set.IsMember(i)) cout<<i<<" ";
}
cout<<endl;
return
stream;
}
벡터 집합 테스트 프로그램
#include <iostream>
#include "VecSet.h"
using namespace std;
int main(int argc, char** argv) {
VecSet a(8);
VecSet b(8);
VecSet c(8);
for(int i=1; i<=5; i++){
a.Add(i);
}
b.Add(2);
b.Add(3);
b.Add(4);
b.Add(5);
b.Add(7);
b.Del(4);
cout<< a * b;
cout<< a + b;
cout<< a - b;
c = b;
cout<<c;
cout<<(c==b);
return 0;
}P332: 링크 집합 실현
ListSet. h 파일
#ifndef LISTSET_H
#define LISTSET_H
#include <iostream>
using namespace std;
template <class T> class ListSet;
template <class T>
class ListSetNode
{
friend class ListSet<T>;
T data;
ListSetNode<T>* link;
public:
ListSetNode() :link(NULL){}
ListSetNode(T value) :link(NULL), data(value){}
};
template <class T>
class ListSet
{
ListSetNode<T>* head;
ListSetNode<T>* tail;
public:
ListSet();
~ListSet();
ListSet(ListSet & lset);
void Add(T add);
void Del(T del);
bool IsEmpty();
void MakeEmpty();
ListSet<T>& operator+(ListSet<T>& another);
ListSet<T>& operator-(ListSet<T>& another);
ListSet<T>& operator*(ListSet<T>& another);
ListSet<T>& operator=(ListSet<T>& another);
bool operator==(ListSet<T>& another);
void Output();
ListSetNode<T>* GetHead(){ return head; }
};
template <class T>
ListSet<T>::ListSet()
{
this->head = new ListSetNode<T>();
this->tail = this->head;
}
template <class T>
ListSet<T>::~ListSet()
{
MakeEmpty();
delete head;
}
template <class T>
void ListSet<T>::Add(T value)
{
ListSetNode<T>* add = new ListSetNode<T>(value);
ListSetNode<T>* preCurrent = head; //
ListSetNode<T>* current = preCurrent->link; //
while (current != NULL && current->data < value) //
{
preCurrent = current;
current = preCurrent->link;
}
if (head == tail && current == NULL) //
{
head->link = add;
tail = add;
}
if (head != tail && current == NULL) // add
{
preCurrent->link = add;
add->link = NULL;
tail = add;
}
if (current != NULL && current->data == value) // add
{
return;
}
if (current != NULL && current->data > value)
{
preCurrent->link = add;
add->link = current;
}
}
template <class T>
void ListSet<T>::Del(T del)
{
ListSetNode<T>* preCurrent = head;
ListSetNode<T>* current = preCurrent->link;
while (current != NULL && current->data != del) //
{
preCurrent = current;
current = preCurrent->link;
}
if (current != NULL)
{
preCurrent->link = current->link;
if (current->link == NULL){ tail = preCurrent; } //
delete current;
}
}
template <class T>
bool ListSet<T>::IsEmpty()
{
return head == tail; //
}
template <class T>
void ListSet<T>::MakeEmpty()
{
ListSetNode<T>* current = head->link;
ListSetNode<T>* del = NULL;
while (head->link != NULL) //
{
head->link = current->link;
del = current;
current = current->link;
delete del; // delete
}
tail = head;
}
template <class T>
ListSet<T>& ListSet<T>::operator=(ListSet<T>& another)
{
MakeEmpty();
ListSetNode<T>* current = another.head->link;
while (current != NULL)
{
Add(current->data);
current = current->link;
}
return *this;
}
template <class T>
ListSet<T>::ListSet(ListSet<T>& lset)
{
this->head = new ListSetNode<T>();
this->tail = this->head;
ListSetNode<T>* current = lset.head->link;
while (current != NULL)
{
Add(current->data);
current = current->link;
}
}
template <class T>
ListSet<T>& ListSet<T>::operator+(ListSet<T>& another)
{
ListSet<T>* tmpSet = new ListSet(another);
ListSetNode<T>* current = this->head->link;
while (current != NULL)
{
tmpSet->Add(current->data);
current = current->link;
}
return *tmpSet; //
}
template <class T>
ListSet<T>& ListSet<T>::operator-(ListSet<T>& another)
{
ListSet<T>* tmpSet = new ListSet(*this);
ListSetNode<T>* current = another.head->link;
while (current != NULL)
{
tmpSet->Del(current->data);
current = current->link;
}
return *tmpSet;
}
template <class T>
ListSet<T>& ListSet<T>::operator*(ListSet<T>& another)
{
ListSet<T>* tmpSet = new ListSet(*this);
*tmpSet = *this - another;
*tmpSet = *this - *tmpSet;
return *tmpSet;
}
template <class T>
bool ListSet<T>::operator==(ListSet<T>& another)
{
ListSetNode<T>* current1 = head->link;
ListSetNode<T>* current2 = another.head->link;
while (current1 != NULL)
{
if (current2 == NULL){ return false; }
if (current1->data != current2->data){ return false; }
current1 = current1->link;
current2 = current2->link;
}
if (current2 != NULL){ return false; }
return true;
}
template <class T>
void ListSet<T>::Output()
{
ListSetNode<T>* current = this->GetHead()->link;
while(current != NULL){
cout << current->data << " ";
current = current->link;
}
cout << endl;
}
#endif링크 기반 집합 테스트 프로그램
#include "stdafx.h"
#include "ListSet.h"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
ListSet<int> listSetA;
ListSet<int> listSetB;
ListSet<int> listSetC;
for (int i = 1; i <= 5; i++)
{
listSetA.Add(i);
}
// cout << listSetA.IsEmpty()<<endl;
// listSetA.MakeEmpty();
// cout << listSetA.IsEmpty()<<endl;
// listSetC = listSetA;
// listSetC.Output();
ListSet<int> listSetD(listSetA);
cout << (listSetA == listSetD) << endl;
listSetB.Add(2);
listSetB.Add(3);
listSetB.Add(5);
listSetB.Add(7);
listSetB.Add(8);
listSetB.Add(5);
listSetB.Del(8);
listSetC = listSetA + listSetB;
listSetC.Output();
listSetC = listSetA - listSetB;
listSetC.Output();
listSetC = listSetA * listSetB;
listSetC.Output();
system("PAUSE");
return 0;
}P336: 사전
Item. h 파일
#ifndef _ITEM_H_
#define _ITEM_H_
#include <iostream>
#include <string.h>
using namespace std;
class Item {
string english;
string chinese;
Item* link;
public:
Item() : link(NULL){}
Item(string en, string ch) : link(NULL), english(en),chinese(ch) {}
~Item(){};
void SetLink(Item* next);
Item* GetLink();
string GetIndex();
string GetValue();
};
void Item::SetLink(Item* next){
link = next;
}
Item* Item::GetLink(){
return link;
}
string Item::GetIndex(){//
return english;
}
string Item::GetValue(){//
return chinese;
}
#endifDictionary. h 파일
#ifndef _DICTIONARY_H_
#define _DICTIONARY_H_
#include "Item.h"
class Dictionary{
Item* head;
Item* tail;
public:
Dictionary();
virtual ~Dictionary();
bool Add(string en, string ch);
bool Del(string en);
string Search(string en);
int GetCount();
void RemoveAll();
};
Dictionary::Dictionary()
{
head = new Item();
tail = head;
tail->SetLink(NULL);
}
Dictionary::~Dictionary()
{
RemoveAll();
delete head;
}
bool Dictionary ::Add(string en, string ch){
Item* add = new Item(en, ch);
tail->SetLink(add);
tail = tail->GetLink();
tail->SetLink(NULL);
if (tail != NULL)
return true;
else
return false;
}
bool Dictionary::Del(string en){
Item* cur, *curPre;
cur = head;
curPre = cur->GetLink();
while (cur != NULL){
if (curPre->GetIndex() == en)
break;
cur = cur->GetLink();
if (cur !=NULL)
curPre = curPre->GetLink();
}
if (tail == curPre)
tail = cur;
cur->SetLink(curPre->GetLink()); //
delete curPre;
if (curPre != NULL)
return true;
else
return false;
}
string Dictionary::Search(string en) {
Item* cur;
cur = head->GetLink();
while (cur != NULL){
if (en == cur->GetIndex())
break;
cur = cur->GetLink();
}
if (cur != NULL)
return cur->GetValue(); // value
else
return "Cannot find";
}
int Dictionary::GetCount() {
int count = 0;
Item* current = head->GetLink();
while (current != NULL) {
++count;
current = current->GetLink(); // cur
}
return count;
}
void Dictionary::RemoveAll() { //
Item* cur;
while (head->GetLink() != NULL) {
cur = head->GetLink();
head->SetLink(cur->GetLink());
delete cur;
}
tail = head; //
}
#endif사전 테스트 프로그램
#include "stdafx.h"
#include <iostream>
#include "Dictionary.h"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
Dictionary dic;
dic.Add("box", " ");
dic.Add("apple", " ");
dic.Add("tree", " ");
dic.Add("good", " ");
dic.Add("swim", " ");
dic.Add("interesting", " ");
cout << dic.Search("good").c_str() << endl;
cout << dic.Search("interesting").c_str() << endl;
dic.Del("box");
dic.Del("interesting");
cout << dic.Search("box").c_str() << endl;
cout << dic.Search("interesting").c_str() << endl;
cout << dic.Search("apple").c_str() << endl;
system("PAUSE");
return 0;
}P343
template <class T>
class Item{
int key;
T data;
public:
Item():key(-1){}
Item(int keyInput,T value):key(keyInput),data(value){assert(key>=0);}
int GetKey(){return key;}
T GetData(){return data;}
friend ostream& operator<<(ostream& stream,Item<T>& item);
};
template <class T>
class OrderSearch{
Item<T>* contain;
int size;
public:
OrderSearch():contain(NULL),size(0){}
OrderSearch(int maxSize);
void Add(Item<T> add);
int GetSize(){return size;}
Item<T>* GetContain(){return contain;}
Item<T>& Search(int k);
friend ostream& operator<<(ostream& stream,OrderSearch<T>& set);
};
P344
template <class T>
ostream& operator<<(ostream& stream,Item<T>& item){
cout<<"key:"<<item.GetKey()<<"\t"<<"data:"<<item.GetData()<<endl;
return stream;
}
P345
template <class T>
OrderSearch<T>::OrderSearch(int maxSize)
{
contain = new Item<T>[maxSize]; // ，
size = maxSize; //
for(int i=0;i<maxSize;i++) //
{
Item<T> ini;
contain[i] = ini;
}
}
template <class T>
void OrderSearch<T>::Add(Item<T> add)
{
assert(add.GetKey()>=0 && add.GetKey()<size); // key
contain[add.GetKey()] = add; //
}
template <class T>
Item<T>& OrderSearch<T>::Search(int k)
{
assert(k>=0 && k<size); // key
return contain[k]; //
}
template <class T>
ostream& operator<<(ostream& stream,OrderSearch<T>& set)
{
for(int i=0;i<set.GetSize();i++)
{
if(set.GetContain()[i].GetKey() != -1)
{
cout<<"key:"<<set.GetContain()[i].GetKey()<<"\t";
cout<<"data:"<<set.GetContain()[i].GetData()<<endl;
}
}
return stream;
}
P346
template <class T>
int BinarySearch(List<T>& dic, T& item) {
int lowKey = 0;
int highKey = dic.GetCount() - 1;
int midKey;
while (lowKey <= highKey)
{
midKey = (lowKey + highKey) / 2; //
if (dic.GetAt(midKey) < item)
{
lowKey = midKey + 1; //
}
else if (dic.GetAt(midKey) > item)
{
highKey = midKey - 1; //
}
else
return midKey;
}
return -1;
}
P351-1: BKDR 해시
테스트 프로그램 과 함께 드 립 니 다.이 알고리즘 은 C 언어 키 워드 를 처리 할 때 매우 작은 충돌 율 을 얻 을 수 있다 는 것 을 알 게 될 것 이다.예 를 들 어 우리 가 HASHSIZE 가 101 일 때 충돌 이 전혀 없 을 수 있다.
#include <iostream>
#include <string>
#include <iomanip>
#include <stdint.h>
using namespace std;
#define HASHSIZE 101
string keywords[] = {
"auto", "break", "case", "char", "const", "continue", "default", "do",
"double", "else", "enum", "extern", "float", "for", "goto", "if",
"int", "long", "register", "return", "short", "signed", "sizeof", "static",
"struct", "switch", "typedef", "union", "unsigned", "void", "volatile", "while"
};
unsigned long BKDRHash(const string& str)
{
unsigned long seed = 31;
unsigned long hashval = 0;
for(int i = 0; i < str.length(); i++)
hashval = hashval * seed + str[i];
return hashval % HASHSIZE;
}
int main(int argc, char** argv) {
int size, pos;
int count[HASHSIZE];
for(int i = 0; i < HASHSIZE; i++)
count[i] = 0;
size = sizeof(keywords) / sizeof(keywords[0]);
for(int i = 0;i < size; i++)
count[BKDRHash(keywords[i])]++;
for(int i = 0; i < size; i++) {
pos = BKDRHash(keywords[i]);
cout<<setw(8)<<keywords[i]<<setw(5)<<pos<<setw(5)<<count[pos]<<endl;
}
return 0;
}P351-2: RS 해시 (테스트 프로그램 과 함께 제공)
#include <iostream>
#include <string>
#include <iomanip>
#include <stdint.h>
using namespace std;
#define HASHSIZE 41
string keywords[] = {
"auto", "break", "case", "char", "const", "continue", "default", "do",
"double", "else", "enum", "extern", "float", "for", "goto", "if",
"int", "long", "register", "return", "short", "signed", "sizeof", "static",
"struct", "switch", "typedef", "union", "unsigned", "void", "volatile", "while"
};
unsigned long RSHash(const string& str)
{
unsigned long a = 31415, b = 27183;
unsigned long hashval = 0;
for(int i = 0; i < str.length(); i++)
{
hashval = (hashval * a + str[i])%HASHSIZE;
a = a * b % (HASHSIZE-1);
}
return hashval;
}
int main(int argc, char** argv) {
int size, pos;
int count[HASHSIZE];
for(int i = 0; i < HASHSIZE; i++)
count[i] = 0;
size = sizeof(keywords) / sizeof(keywords[0]);
size = 32;
for(int i = 0;i < size; i++)
count[RSHash(keywords[i])]++;
for(int i = 0; i < size; i++) {
pos = RSHash(keywords[i]);
cout<<setw(8)<<keywords[i]<<setw(5)<<pos<<setw(5)<<count[pos]<<endl;
}
return 0;
}P352: FNV 해시 (테스트 프로그램 과 함께 제공)
#include <iostream>
#include <string>
#include <iomanip>
#include <stdint.h>
using namespace std;
//const long offsetbasis32 = 2166136261;
#define FNV_32_INIT ((uint32_t)0x811c9dc5)
//const long FNVprime32 = 16777619;
#define FNV_32_PRIME ((uint32_t)0x01000193)
unsigned long FNV1a_32_Hash(const string& str)
{
unsigned long hashval = FNV_32_INIT;
for(int i = 0; i < str.length(); i++)
{
hashval = hashval ^ str[i];
// hashval = hashval * FNV_32_PRIME;
//
hashval += (hashval <<1) + (hashval <<4)
+ (hashval <<7) + (hashval <<8) + (hashval <<24);
}
return hashval;
}
//const long offsetbasis64 = 14695981039346656037;
//#define FNV_64_INIT ((uint64_t)0x14650FB0739D0383);
#define FNV_64_INIT ((uint64_t)0xcbf29ce484222325ULL);
//const long FNVprime64 = 1099511628211;
#define FNV_64_PRIME ((uint64_t)0x100000001b3ULL)
uint64_t FNV1a_64_Hash(const char* bp, size_t len)
{
uint64_t hval = FNV_64_INIT;
const char *be = bp + len;
while (bp < be) {
hval ^= (uint64_t) *bp++;
hval += (hval << 1) + (hval << 4) + (hval << 5) + (hval << 7) + (hval << 8) + (hval << 40);
}
return hval;
}
int main(int argc, char** argv) {
string str = "interesting";
cout<<hex<<FNV1a_32_Hash(str)<<endl;
cout<<hex<<FNV1a_64_Hash(str.c_str(), str.length())<<endl;
return 0;
}내용 소개: 비밀 알고리즘 세 계 를 탐색 하고 데이터 구조의 길 을 모색 한다.전형 적 인 문 제 를 모 아 프로 그래 밍 기법 의 취 미 를 즐 깁 니 다.구직 핫 이 슈 를 지적 하여 개업 계 의 유명 기업 의 문 을 두드리다.이 책 은 알고리즘 과 데이터 구조 라 는 화 제 를 중심 으로 현대 컴퓨터 기술 에서 자주 사용 하 는 40 여 개의 전형 적 인 알고리즘 과 역 추적 법, 분 치 법, 탐욕 법 과 동적 계획 등 알고리즘 디자인 사상 을 점차적으로 소개 했다.이 과정 에서 이 책 은 링크 (단 방향 링크, 단 방향 순환 링크 와 양 방향 순환 링크 포함), 스 택, 대기 열 (일반 대기 열 과 우선 순위 대기 열 포함), 트 리 (이 진 트 리, 하프 만 트 리, 더미, 레 드 블랙 트 리, AVL 트 리 와 사전 트 리 포함), 그림, 집합 (교차 하지 않 음 포함) 과 사전 등 상용 데이터 구 조 를 체계적으로 설명 했다.이 동시에 22 개의 전형 적 인 문제 (조세 프 링 문제, 한 노 타 문제, 8 황후 문제 와 기사 여행 문제 등 포함) 에 대한 설명 을 통 해 데이터 구조 뒤에 숨겨 진 알고리즘 원 리 를 점차적으로 밝 히 고 독자 들 이 지식 비축 을 다 지 는 데 도움 을 주 며 사고 기술 을 활성화 시 키 고 최종 적 으로 프로 그래 밍 능력 의 향상 을 방해 하 는 복잡 한 울 타 리 를 돌파 하려 고 한다.완전한 C++ 소스 코드 를 추가 하고 STL 의 각종 용 기 를 삽입 하여 소개 합 니 다.
인터넷 서점:
중국 - pub 중국 상호작용 출판 망:http://product.china-pub.com/4911922
당당 망:http://product.dangdang.com/23851244.html
아마 존:http://www.amazon.cn/%E7%AE%97%E6%B3%95%E4%B9%8B%E7%BE%8E-%E9%9A%90%E5%8C%BF%E5%9C%A8%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%83%8C%E5%90%8E%E7%9A%84%E5%8E%9F%E7%90%86-%E5%B7%A6%E9%A3%9E/dp/B01AGNUIE8/ref=sr_1_8?ie=UTF8&qid=1453527399&sr=8-8&keywords=%E5%B7%A6%E9%A3%9E
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
물체 검출의 평가 지표 IoU의 계산 방법Yolo나 SSD 등 물체 검출에서 평가 지표로 사용되는 IoU에 대해 조사했으므로 정리했습니다. IoU (Intersection over Union)는 두 영역이 얼마나 겹치는지를 나타내는 지표입니다. 두 영역의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
