알고리즘 의 미소스 코드 발표 (7)
부록 중의 고전 필기시험, 면접 문제 참고 답안 은 다음 과 같 습 니 다.
http://blog.csdn.net/baimafujinji/article/details/50484683
In genel, 나 는 책 한 권 (기술 서) 을 펼 치 는 것 을 그다지 좋아 하지 않 는 다. 그 안에 빽빽 한 것 은 모두 코드 이다.그래서 나 도 내 책 에 원리 와 사고방식 을 토론 할 수 있 는 공간 을 더 많이 남 겼 으 면 좋 겠 다.물론 코드 도 중요 하 다. 모든 원 리 는 결국 코드 에 실 현 돼 야 한다.이 때문에 나 는 그들 을 모두 책 에 나열 해서 편폭 을 차지 하 는 것 이 아니 라 블 로그 에 코드 를 올 리 는 것 에 익숙 하 다.마지막 으로 저 는 알고리즘 과 데이터 구 조 를 잘 배 우려 는 학생 들 에 게 책 에서 언급 된 알고리즘 원 리 를 철저히 격파 하고 그 이 유 를 더 잘 알 도록 하 겠 습 니 다. 그래 야 당신 이 진정 으로 배 운 것 이 라 고 할 수 있 습 니 다. 그래 야 새로운 프로 그래 밍 문 제 를 만 났 을 때 속수무책 이 되 지 않 습 니 다.
만약 당신 이 이 책의 독자 라면 알고리즘 학습 군 (495573865) 에 가입 하 는 것 을 강력 히 건의 합 니 다. 그 안에 더 많은 자원 이 당신 을 기다 리 고 있 습 니 다. 그리고 당신 이 책 을 읽 으 면서 만난 의문 도 제 첫 번 째 시간의 해답 을 얻 을 수 있 습 니 다.본 블 로그 에 더 많은 관심 을 가지 고 있 습 니 다. 저 는 이 책의 모든 소스 코드 를 본 블 로그 에 계속 발표 할 것 입 니 다.
P238 그림 의 추상 적 데이터 구조
class Graph()
{
vector<Vertex> VertexSet; // ， vector
vector<Edge> EdgeSet; // ， vector
public:
Graph(); // ，
Graph(vector<Vertex> vertexes, vector<Edge> edges); //
~Graph(); //
bool IsEmpty(); // ， true， false
void InsertVertex(const Vertex& vertex); //
void InsertEdge(const Edge& edge); //
void DeleteVertex(Vertex& vertex); // ，
void DeleteEdge(Edge& edge); //
Vertex * getVertex(const string& nv); // ， NULL
Edge * getEdge(const string& ne); // ， NULL
int getEdgeValue(Edge& edge); //
Vertex * getEdgeSrc(Edge& edge); //
Vertex * getEdgeDst (Edge& edge); //
// vertex ， NULL
Vertex * getFirstAdjVex(Vertex& vertex);
// vertex1 vertex2 ， NULL
Vertex * getNextAdjVex(Vertex& vertex1, Vertex& vertex2);
// vertex
void DFSTraverse(Vertex& vertex);
// vertex
void BFSTraverse(Vertex& vertex);
// vertex1 vertex2
vector<Edge*> getShortPath(Vertex& vertex1, Vertex& vertex2);
}
정의 그림 정점 구조
class Vertex
{
string name_vertex;
Vertex(const string * n)
:name_vertex (n) {}
}
정의 그림 의 변 구조
class Edge
{
string name_edge;
Vertex * src;
Vertex * dst;
int cost;
Edge(const string * n, Vertex * s = NULL, Vertex * d = NULL, int c = 0)
: name_edge(n), src(s), dst(d), cost(c) {}
}
P241 인접 행렬 을 사용 하여 그림 의 저장 구조의 정 의 를 표시 합 니 다.
typedef int Vertex;
typedef int AdjMatrix;
class GraphMatrix
{
int n; //
Vertex * vexes; //
AdjMatrix * arcs[]; //
}
P243 인접 표 로 표 시 된 그림 저장 구조의 정 의 를 사용 합 니 다.
class EdgeNode;
typedef EdgeNode * EdgeList;
/* */
class EdgeNode
{
int vertexNum; //
int weight; //
EdgeNode * nextEdgeNode; // ，
};
/* */
class Vertex
{
char vertex; //
EdgeList edgeList; //
};
class GraphList
{
int n; //
Vertex * vertexes; //
};
P247 질문
#include <stdio.h>
#include <string.h>
#include "iostream"
using namespace std;
#define N 27
char str[1001];
int v[N];
int is[N][N];
int viii[N];
int dfs(int);
int counter;
int main() {
int x[N],f[N],j,len,y[N],i,test,flag,lengths,p,q=0;
int count=0;
scanf("%d",&test);
for(i=0;i<test;i++) {
memset(x,0,sizeof(x));memset(y,0,sizeof(y));
memset(f,0,sizeof(f));memset(v,0,sizeof(v));
memset(is,0,sizeof(is));
for(j=0;j<N;j++)is[j][j]=1;
scanf("%d",&len);counter=0;
memset(viii,0,sizeof(viii));
count=0;
for(j=0;j<len;j++){
scanf("%s",str);
lengths=strlen(str);
if(str[lengths-1]!=str[0]){
x[str[0]-'a']++;
y[str[lengths-1]-'a']++;
v[str[0]-'a']=v[str[lengths-1]-'a']=1;
count++;
is[str[0]-'a'][str[lengths-1]-'a']=1;
is[str[lengths-1]-'a'][str[0]-'a']=1;
}
else f[str[0]-'a']=1;
}
for(j=0,p=0,q=0,flag=0;j<N;j++){
if(x[j]!=y[j]) {
if(x[j]==y[j]+1) p++;else if(x[j]+1==y[j])q++; else
flag++;
}
}
if(count==0){
for(j=0;j<N;j++) if(f[j]) count++;
if(count==1)
printf("Ordering is possible.
");
else
printf("The door cannot be opened.
");
continue;
}
for(j=0;j<N;j++) if(v[j]) break;
dfs(j);
for(j=0;j<N;j++)
if(v[j]&&!viii[j]) {j=N+10;break;}
if(j==N+10) {
cout<<"The door cannot be opened."<<endl;continue;
}
if(!flag&&(p+q==0||p*q==1)) {
for(j=0;j<N;j++)
if(f[j]==1&&v[j]!=1) {j=N+10;break;}
if(j<N+2) printf("Ordering is possible.
");
else printf("The door cannot be opened.
");
}
else printf("The door cannot be opened.
");
}
return 0;
}
int dfs(int index) {
int i=0;
counter;viii[index]=1;
for(i=0;i<N;i++)
if(!viii[i]&&is[i][index]) {
dfs(i);
}
return 0;
}
P251 기사 주유 문제
#include "stdafx.h"
#include "conio.h"
#include <iostream>
using namespace std;
class Board
{
private:
int board[8][8]; //
int step; //
int No; //
int direct[8][2]; //
int wayCount[8][8]; //
int startX; // x
int startY; // y
int dir[8][8][8]; //
void init()
{
int i,j,k;
int x,y;
//
for(j=0;j<8;j++)
{
for(i=0;i<8;i++)
{
wayCount[j][i]=0;
for(k=0;k<8;k++)
{
x=i+direct[k][0];
y=j+direct[k][1];
if(check(x,y))
wayCount[j][i]++;
}
}
}
//
for(y=0;y<8;y++)
{
for(x=0;x<8;x++)
{
//
for(k=0;k<8;k++)
{
dir[y][x][k]=k;
}
//
for(i=0;i<7;i++)
{
k=i;
int x1=x+direct[dir[y][x][k]][0];
int y1=y+direct[dir[y][x][k]][1];
//
//
for(j=i+1;j<8;j++)
{
int x2=x+direct[dir[y][x][j]][0];
int y2=y+direct[dir[y][x][j]][1];
// j k k j
if( (!check(x1,y1) && check(x2,y2))
|| ( check(x1,y1) && check(x2,y2) &&
wayCount[x1][y1]>wayCount[x2][y2]) )
{
k=j;
x1=x+direct[dir[y][x][k]][0];
y1=y+direct[dir[y][x][k]][1];
}
}
j=dir[y][x][k];
dir[y][x][k]=dir[y][x][i];
dir[y][x][i]=j;
}
}
}
}
// x,y
int check(int x,int y)
{
if(x<0||x>7||y<0||y>7)
{
return 0;
}
else
{
return 1;
}
}
// (x,y)
void dg(int x, int y)
{
int i,nx,ny;
//
if(step==64)
{
printPath();
return;
}
//
for(i=0;i<8;i++)
{
nx=x+direct[dir[y][x][i]][0];
ny=y+direct[dir[y][x][i]][1];
if(nx>=0 && nx<8 && ny>=0 && ny<8)
{
//
if(board[ny][nx]<0)
{
board[ny][nx]=step;
step++;
dg(nx,ny);
board[ny][nx]=-1;
step--;
}
}
}
}
void printPath()
{
int i,j;
No++;
cout<<"No"<<No<<":"<<endl;
for(j=0;j<8;j++)
{
for(i=0;i<8;i++)
{
cout<<board[j][i]<<" ";
if(board[j][i]<10)
cout<<" ";
}
cout<<endl;
}
cout<<"Press anykey to continue...";
getch();
cout<<endl;
}
void printwc()
{
int i,j;
No++;
cout<<"No"<<No<<":"<<endl;
for(j=0;j<8;j++)
{
for(i=0;i<8;i++)
{
cout<<wayCount[j][i]<<" ";
if(wayCount[j][i]<10)
cout<<" ";
}
cout<<endl;
}
cout<<"Press anykey to continue...";
getch();
cout<<endl;
}
public:
Board(int x, int y)
{
int i,j;
startX=x;
startY=y;
direct[0][0]=1; direct[0][1]=-2;
direct[1][0]=2; direct[1][1]=-1;
direct[2][0]=2; direct[2][1]=1;
direct[3][0]=1; direct[3][1]=2;
direct[4][0]=-1; direct[4][1]=2;
direct[5][0]=-2; direct[5][1]=1;
direct[6][0]=-2; direct[6][1]=-1;
direct[7][0]=-1; direct[7][1]=-2;
step=1;
No=0;
for(j=0;j<8;j++)
{
for(i=0;i<8;i++)
{
board[j][i]=-1;
}
}
board[y][x]=0;
}
void GetPath()
{
init();
dg(startX,startY);
if(No==0)
{
cout<<"no result"<<endl;
}
}
};
int _tmain(int argc, _TCHAR* argv[])
{
int x,y;
cout<<"Please input the start point (x,y)."
<<endl<<"x=";
cin>>x;
getchar();
cout<<"y=";
cin>>y;
getchar();
Board board(x,y);
board.GetPath();
return 0;
}
P256 깊이 우선 옮 겨 다 니 기 및 넓이 우선 옮 겨 다 니 기
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <set>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;
//BFS
void bfs(vector< list<int> >& adj_lists, int start_node) {
queue<int> not_yet_explored;
set<int> discovered;
// ,
not_yet_explored.push(start_node);
discovered.insert(start_node);
while (! not_yet_explored.empty()) {
//
int node_to_explore = not_yet_explored.front();
not_yet_explored.pop();
//
list<int>::iterator edges = adj_lists[node_to_explore].begin();
for ( ; edges != adj_lists[node_to_explore].end(); edges++) {
if (discovered.count(*edges) == 0) {
//
discovered.insert(*edges);
not_yet_explored.push(*edges);
cout <<"Found "<< *edges <<" from "<<node_to_explore<<endl;
}
}
}
}
//DFS
void dfs_helper(vector< list<int> >& adj_lists, set<int>& discovered, int node) {
//
list<int>::iterator edges = adj_lists[node].begin();
for ( ; edges != adj_lists[node].end(); edges++) {
//
if (discovered.count(*edges) == 0) {
discovered.insert(*edges);
cout << "Found " << *edges << " from " << node << endl;
dfs_helper(adj_lists, discovered, *edges);
}
}
}
void dfs(vector< list<int> >& adj_lists, int start_node) {
//
set<int> discovered;
discovered.insert(start_node);
dfs_helper(adj_lists, discovered, start_node);
}
int _tmain(int argc, _TCHAR* argv[])
{
//
vector< list<int> > g(7, list<int>());
g[0].push_back(2);
g[0].push_back(1);
g[1].push_back(0);
g[1].push_back(2);
g[2].push_back(4);
g[2].push_back(3);
g[2].push_back(0);
g[2].push_back(1);
g[3].push_back(2);
g[3].push_back(4);
g[3].push_back(5);
g[4].push_back(6);
g[4].push_back(5);
g[4].push_back(3);
g[4].push_back(2);
g[5].push_back(4);
g[5].push_back(3);
g[6].push_back(4);
cout << "BFS" <<endl;
bfs(g, 0);
cout << endl << "DFS" <<endl;
dfs(g, 0);
system("PAUSE");
return 0;
}
P261 전형 적 인 문제 의 관광 교통 노선 문제
City. h 파일
#ifndef _CITY_H_
#define _CITY_H_
using namespace std;
class City {
public:
//
string name;
//
bool visited;
int total_fee;
int total_distance;
string from_city;
//
City() : name(""), visited(false), total_fee(0),
total_distance(0), from_city("") {}
City(string const &s): name(s), visited(false),
total_fee(0), total_distance(0), from_city("") {}
};
#endif
Road. h 파일
#ifndef _ROAD_H_
#define _ROAD_H_
#include <string>
using namespace std;
class Road {
public:
int fee;
int distance;
string destination;
Road(string city, int f, int d) : fee(f),
distance(d), destination(city) {}
}
;
#endif
RoadSystem. h 파일
#ifndef _ROADSYSTEM_H_
#define _ROADSYSTEM_H_
#include <iostream>
#include <fstream>
#include <map>
#include <list>
#include <queue>
#include <vector>
#include "Road.h"
#include "City.h"
using namespace std;
class Cheapest {
public:
Cheapest() {}
bool operator()(City* city1, City* city2) {
return city1->total_fee > city2->total_fee;
}
};
class RoadSystem {
private:
map<string, list<Road*> > outgoing_roads;
map<string, City*> cities;
void load_roads(const string& filename);
void reset(void);
string recover_route(const string& city);
pair<int, int> calc_route(string from, string to);
public:
RoadSystem(const string& filename);// ，
~RoadSystem(void);//
void output_cheapest_route(const string& from, const string& to, ostream& out);
bool is_valid_city(const string& name);
};
#endif
RoadSystem. cpp 파일
#pragma warning (disable:4786)
#pragma warning (disable:4503)
#include "RoadSystem.h"
void RoadSystem::reset(void) {
map<string, City*>::iterator it;
for(it=cities.begin();it!=cities.end();++it) {
it->second->visited = false;
it->second->total_fee = INT_MAX;
it->second->total_distance = INT_MAX;
it->second->from_city = "";
}
}
string RoadSystem::recover_route(const string& city) {
string route;
string current = city;
while (current != "") {
route = current + route;
string prev = cities[current]->from_city;
if (prev != "") {
route = " -> " + route;
}
current = prev;
}
return route;
}
RoadSystem::RoadSystem(string const &filename) {
load_roads(filename);
}
RoadSystem::~RoadSystem(void) {
//
map<string, City*>::iterator city_it = cities.begin();
for ( ; city_it != cities.end(); city_it++) {
delete city_it->second;
}
//
map<string, list<Road*> >::iterator roads_it =
outgoing_roads.begin();
for ( ; roads_it != outgoing_roads.end(); roads_it++) {
list<Road*>::iterator road_it = roads_it->second.begin();
for ( ; road_it != roads_it->second.end(); road_it++) {
delete *road_it;
}
}
}
void RoadSystem::load_roads(string const &filename) {
ifstream inf(filename.c_str());
string from, to;
int fee, distance;
while ( inf.good() ) {
// ， ，
inf >> from >> to >> fee >> distance;
if ( inf.good() ) {
Road* s = new Road(to, fee, distance);
// cities
if (cities.count(from) == 0) {
cities[from] = new City(from);
outgoing_roads[from] = list<Road*>();
}
if (cities.count(to) == 0) {
cities[to] = new City(to);
outgoing_roads[to] = list<Road*>();
}
//
outgoing_roads[from].push_back(s);
}
}
inf.close();
}
//
void RoadSystem::output_cheapest_route(const string& from,
const string& to, ostream& out) {
reset();
pair<int, int> totals = calc_route(from, to);
if (totals.first == INT_MAX) {
out <<" "<< from << " " << to << " 。"<<endl;
} else {
out << " " << from << " " << to << " "<< totals.first << " 。"<<endl;
out << " " << totals.second << " 。" <<endl;
cout << recover_route(to) << endl << endl;
}
}
bool RoadSystem::is_valid_city(const string& name) {
return cities.count(name) == 1;
}
//
pair<int, int> RoadSystem::calc_route(string from, string to) {
//
priority_queue<City*, vector<City*>, Cheapest> candidates;
City* start_city = cities[from];
//
start_city->total_fee = 0;
start_city->total_distance = 0;
candidates.push(start_city);
//
while(!candidates.empty()) {
City* visiting_city;
visiting_city = candidates.top();
candidates.pop();
if (! visiting_city->visited) {
visiting_city->visited = true;
//
list<Road*>::iterator it;
for(it= outgoing_roads[visiting_city->name].begin();
it != outgoing_roads[visiting_city->name].end(); ++it) {
City* next_city = cities[(*it)->destination];
int next_fee = (*it)->fee + visiting_city->total_fee;
//
if((next_fee < next_city->total_fee)
&& next_city->name != from ) {
next_city->total_fee = next_fee;
next_city->total_distance =
(*it)->distance + visiting_city->total_distance;
next_city->from_city = visiting_city->name;
candidates.push(next_city);
}
}
}
}
//
if (cities[to]->visited) {
return pair<int,int>(cities[to]->total_fee, cities[to]->total_distance);
} else {
return pair<int,int>(INT_MAX, INT_MAX);
}
}주 파일
#pragma warning (disable:4786)
#pragma warning (disable:4503)
#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <queue>
#include "City.h"
#include "Road.h"
#include "RoadSystem.h"
using namespace std;
int main() {
try {
RoadSystem rs("MapInformation.txt");
while (true) {
cerr << endl << endl <<" : ( 'quit')"<<endl;
string from, to;
cin >> from;
if (from == "quit") break;
cin >> to;
if (rs.is_valid_city(from) && rs.is_valid_city(to)) {
rs.output_cheapest_route (from, to, cout);
}
else {
cout << " , !"<<endl<<endl;
}
}
return EXIT_SUCCESS;
}
catch (exception& e) {
cerr << e.what() << endl;
}
catch (...) {
cerr << " , 。"<<endl;
}
return EXIT_FAILURE;
}
MapInformation. txt 파일
Deloraine Queenstown 42 176
Deloraine Oatlands 25 84
Deloraine Launceston 12 50
Hobart Oatlands 18 84
Launceston Deloraine 12 50
Launceston Swansea 35 134
Oatlands Deloraine 25 84
Oatlands Hobart 18 84
Oatlands Queenstown 60 260
Oatlands Swansea 22 113
Queenstown Oatlands 60 260
Queenstown Deloraine 42 176
Swansea Launceston 35 134
Swansea Oatlands 22 113
Burnie Devonport 10 49
Devonport Burnie 10 49
내용 소개: 비밀 알고리즘 세 계 를 탐색 하고 데이터 구조의 길 을 모색 한다.전형 적 인 문 제 를 모 아 프로 그래 밍 기법 의 취 미 를 즐 깁 니 다.구직 핫 이 슈 를 지적 하여 개업 계 의 유명 기업 의 문 을 두드리다.이 책 은 알고리즘 과 데이터 구조 라 는 화 제 를 중심 으로 현대 컴퓨터 기술 에서 자주 사용 하 는 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 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Visual Studio에서 파일 폴더 구분 (포함 경로 설정)Visual Studio에서 c, cpp, h, hpp 파일을 폴더로 나누고 싶었습니까? 어쩌면 대부분의 사람들이 있다고 생각합니다. 처음에 파일이 만들어지는 장소는 프로젝트 파일 등과 같은 장소에 있기 때문에 파일...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
