Форум программистов, компьютерный форум CyberForum.ru

6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.81
tihonya
11 / 7 / 1
Регистрация: 30.05.2012
Сообщений: 107
30.05.2012, 01:42     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика #1
Разбираю 6-ю главу книги Роберт Седжвик: Фундаментальные алгоритмы C++. Части 1-4
Расматриваются простые методы сортировки, любых типов данных.
http://www.proklondike.com/books/cpp...l_algo1_4.html

В листингах 6.1-6.5 представлены методы сортировок, а в листингах 6.6-6.10 преставлена клиентская программа для любых типов данных типа Item.
В общем переписал вроде все правильно но выдает несколько ошибок типо:
" error LNK2019: unresolved external symbol "void __cdecl show<struct record>(struct record * const,int,int)" (??$show@Urecord@@@@YAXQAUrecord@@HH@Z) referenced in function _main c:\Users\Toha\documents\visual studio 2010\Projects\RobertSedjvik2\RobertSedjvik2\MainDriver.obj"

MainDriver.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdlib.h>
#include <iostream>
#include "Array.h"
#include "exch.h"
#include "Item.h"
using namespace std;
 
void main(int argc, char *argv[])
 
{ int N = atoi(argv[1]), sw = atoi (argv[2]);
 
 
    Item *a = new Item[N];
    if (sw) rand(a, N); else scan(a,N);
    sort(a, 0, N-1);
    show(a, 0, N-1);
}
OrgfunckArray.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <stdlib.h>
#include "Array.h"
template <class Item>
void rand(Item a[], int N)
{ for (int i=0; i<N; i++) rand(a[i]);}
template <class Item>
 void scan(Item a[], int &N)
 { for (int i=0; i <N; i++)
    if (!scan(a[i])) break;
 N =i;
 
 }
 template <class Item>
 void show (Item a[],int l, int r)
 {for (int i=l; i<=r; i++)
 show(a[i]);
 cout << endl;
 }
 template <class Item>
 void sort(Item a[], int l, int r){
     for (int i=l; i<r; i++){
         int f=0;
         for(int j=r; j>i; j--)
             f+=compexch(a[j-1], a[j]);
         for(int j=i+2;j<=r;j++)
             f+=compexch(a[j-1], a[j]);
         if (f==0)break;
     }
 }
exchange.cpp
C++
1
2
3
4
5
6
7
8
#include <iostream>
#include <stdlib.h>
template <class Item>
void exch (Item &A, Item &B)
{Item t = A; A= B; B=t;}
template <class Item>
 int compexch (Item &A,Item &B)
 { if (B < A) {exch(A, B); return 1;}else return 0; }
Itemcpp.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<stdlib.h>
#include "Item.h"
using namespace std;
int operator<(const Item& A, const Item& B)
{return A.key< B.key;}
int scan (Item& x)
{  
return (cin>>x.key>>x.info) !=0;}
void rand(Item& x)
{x.key = 1000*(1.0*rand()/100);
x.info=1.0 *rand()/100;}
void show (const Item x)
{cout <<x.key<<" "<<x.info<<endl; }
Array.h
C++
1
2
3
4
5
6
7
8
template <class Item>
void rand(Item a[], int N);
template <class Item>
void scan(Item a[], int &N);
template <class Item>
void show(Item a[], int l, int r);
template <class Item>
void sort (Item a[], int l, int r);
exch.h
C++
1
2
3
4
template <class Item>
void exch (Item &A, Item &B);
template <class Item>
 int compexch (Item &A,Item &B);
Item.h
C++
1
2
3
4
5
6
typedef struct record { int key; float info;} Item;
int operator <(const Item&, const Item&);
int scan(Item&);
void rand (Item&);
void show (const Item&);
using namespace std;
Подскажите пожалуйсто что не так?????? очень надо разобратся как это работает, и вообще... У меня экзамен в воскресенье.
Зы: Если что не так, я все исправлю, мы люди не месные и тп ).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.05.2012, 01:42     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика
Посмотрите здесь:

Не работает программа из книги Дейтела "Как программировать на с++" C++
Задача из книги "Програмирование - принцыпы и практика использования C++" C++
C++ Книги Седжвика
Седжвик Р. - Фундаментальные алгоритмы на C++. Объясните лемму C++
C++ Книги по С++ (что читать после книги Дейтела "Как программировать на С++")
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
tihonya
11 / 7 / 1
Регистрация: 30.05.2012
Сообщений: 107
31.05.2012, 01:09  [ТС]     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика #21
Цитата Сообщение от Avazart Посмотреть сообщение
При компиляции нет, после компиляции ( если не выдаст ошибку) можно через cmd экзешник запустить.

А вообще можно переделать в
C++
1
2
3
4
5
6
7
8
9
int main() // int вместо void обычно пишут
{ 
int N; 
int sw; 
cin>>N;
cin>>sw;
//...
return 0;
}
Такой вариант не пойдет, Правильно: Нажать в Solution Explorer правой кнопкой миши на название проэкта открыть Properties->Debugging->Command Arguments через пробел два числа(в моем случае(прм 25 1 ).

Так что мы имеем в сухом остатке:
Этот код работает.
C++
1
2
3
4
5
6
7
8
9
10
11
12
//MainDriver.cpp
#include <stdlib.h>
#include "Item.h"
#include "exch.h"
#include "Array.h"
void main(int argc, char *argv[])
{ int N = atoi(argv[1]), sw = atoi (argv[2]);
    Item *a = new Item[N];
    if (sw) rand(a, N); else scan(a,N);
    sort(a, 0, N-1);
    show(a, 0, N-1);
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
//Item.h
typedef struct record { int key; float info;} Item;
#include<iostream>
using namespace std;
int operator<(const Item& A, const Item& B)
{return A.key< B.key;}
int scan (Item& x)
{return (cin>>x.key>>x.info) !=0;}
void rand(Item& x)
{   x.key = (rand()%100);
x.info=1.0 *rand()/100;}
void show (const Item x)
{cout <<x.key<<" "<<x.info<<endl; }
C++
1
2
3
4
5
6
7
//exch.h
template <class Item>
void exch (Item &A, Item &B)
{Item t = A; A= B; B=t;}
template <class Item>
 int compexch (Item &A,Item &B)
 { if (B < A) {exch(A, B); return 1;}else return 0; }
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//Array.h
#include<time.h>
template <class Item>
void rand(Item a[], int N)
{srand(time(NULL));
 for (int i=0; i<N; i++) rand(a[i]);}
template <class Item>
 void scan(Item a[], int &N)
 { int i;
     for ( i=0; i <N; i++)
    if (!scan(a[i])) break;
 N =i;
  }
 template <class Item>
 void show (Item a[],int l, int r)
 {for (int i=l; i<=r; i++)
 show(a[i]);
 cout << endl;
 }
 template <class Item>
 void sort(Item a[], int l, int r){
     for (int i=l; i<r; i++){
         int f=0;
         for(int j=r; j>i; j--)
             f+=compexch(a[j-1], a[j]);
         for(int j=i+2;j<=r;j++)
             f+=compexch(a[j-1], a[j]);
         if (f==0)break;
     }
 }
Всетаки как-то хочется отделить заголовки template<class Item> void f(......); от исполняемой части, Как по мне было бы намного красивей, и понятней.
ЗЫ: дальше буду разбирать Седжвика...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
antoha398
155 / 155 / 3
Регистрация: 29.03.2012
Сообщений: 418
31.05.2012, 10:00     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика #22
tihonya, попробуй в конце заголовка подключить файл исходника с реализацией, например:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//Array.h
#ifndef ARRAY_H
#define ARRAY_H
template <class Item>
void rand(Item a[], int N);
template <class Item>
void scan(Item a[], int &N);
template <class Item>
void show(Item a[], int l, int r);
template <class Item>
void sort (Item a[], int l, int r);
 
#include "OrgfunckArray.cpp"
 
#endif
А вообще надо почитать про модели компиляции шаблона, и узнать какая из них реализована в твоем компиляторе.
tihonya
11 / 7 / 1
Регистрация: 30.05.2012
Сообщений: 107
01.06.2012, 14:07  [ТС]     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика #23
Цитата Сообщение от antoha398 Посмотреть сообщение
tihonya, попробуй в конце заголовка подключить файл исходника с реализацией, например:


А вообще надо почитать про модели компиляции шаблона, и узнать какая из них реализована в твоем компиляторе.
Спасибо , вот частично получилось, не получилось разделить Item.h, получается что-то с областью видимости struct -ы Item типа record:

C++
1
2
3
4
5
6
7
8
9
10
11
12
//MainDriver.cpp
#include <stdlib.h>
#include "Item.h"
#include "exch.h"
#include "Array.h"
void main(int argc, char *argv[])
{ int N = atoi(argv[1]), sw = atoi (argv[2]);
    Item *a = new Item[N];
    if (sw) rand(a, N); else scan(a,N);
    sort(a, 0, N-1);
    show(a, 0, N-1);
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
//Array.h
#ifndef ARRAY_H
#define ARRAY_H
template <class Item>
void rand(Item a[], int N);
template <class Item>
void scan(Item a[], int &N);
template <class Item>
void show(Item a[], int l, int r);
template <class Item>
void sort (Item a[], int l, int r);
#include "OrgfunckArray.cpp"
#endif
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//OrgfunckArray.cpp
#include <iostream>
#include<time.h>
using namespace std;
template <class Item>
void rand(Item a[], int N)
{srand(time(NULL));
 for (int i=0; i<N; i++) rand(a[i]);}
template <class Item>
 void scan(Item a[], int &N)
 { int i;
     for ( i=0; i <N; i++)
    if (!scan(a[i])) break;
 N =i; }
 template <class Item>
 void show (Item a[],int l, int r)
 {for (int i=l; i<=r; i++)
 show(a[i]);
 cout << endl;
 }
 template <class Item>
 void sort(Item a[], int l, int r){
     for (int i=l; i<r; i++){
         int f=0;
         for(int j=r; j>i; j--)
             f+=compexch(a[j-1], a[j]);
         for(int j=i+2;j<=r;j++)
             f+=compexch(a[j-1], a[j]);
         if (f==0)break;
     }
 }
C++
1
2
3
4
5
6
7
8
9
//exch.h
#ifndef EXCH_H
#define EXCH_H
template <class Item>
void exch (Item &A, Item &B);
template <class Item>
 int compexch (Item &A,Item &B);
#include "exchange.cpp"
#endif
C++
1
2
3
4
5
6
7
//exchange.cpp
template <class Item>
void exch (Item &A, Item &B)
{Item t = A; A= B; B=t;}
template <class Item>
 int compexch (Item &A,Item &B)
 { if (B < A) {exch(A, B); return 1;}else return 0; }
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//Item.h
//#ifndef ITEM_H
//#define ITEM_H
 struct record { int key; float info;};
 typedef record Item;
 //----------------------------------
int operator <(const Item&, const Item&);
int scan(Item&);
void rand (Item&);
void show (const Item&);
 //----------------------------------
#include<iostream>
using namespace std;
//#include<stdlib.h>
int operator<(const Item& A, const Item& B)
{return A.key< B.key;}
int scan (Item& x)
{return (cin>>x.key>>x.info) !=0;}
void rand(Item& x)
{   x.key = (rand()%100);
x.info=1.0 *rand()/100;}
void show (const Item &x)
{cout <<x.key<<" "<<x.info<<endl; }
//#include "Itemcpp.cpp"
//#endif
Есть какие-то предложения как разделить Item.h , на заголовок и исполняемую час, также я не понял как сделать видимой структуру в срр файле Itemcpp.cpp если она объявляется в Item.h.
antoha398
155 / 155 / 3
Регистрация: 29.03.2012
Сообщений: 418
01.06.2012, 14:20     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика #24
С Item.h делайте как обычно. в заголовке объявление сруктуры и функций; в исходнике в начале подключаете заголовок, потом пишите определение функций.
tihonya
11 / 7 / 1
Регистрация: 30.05.2012
Сообщений: 107
01.06.2012, 14:40  [ТС]     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика #25
Цитата Сообщение от antoha398 Посмотреть сообщение
С Item.h делайте как обычно. в заголовке объявление сруктуры и функций; в исходнике в начале подключаете заголовок, потом пишите определение функций.
Все получилось, правда с N-noй попытки, только что получилось:
Item.h
на 2 файла
C++
1
2
3
4
5
6
7
8
9
10
11
12
//Item.h
#ifndef ITEM_H
#define ITEM_H
 struct record {public: int key; float info;};
 typedef record Item;
 //----------------------------------
int operator <(const Item&, const Item&);
int scan(Item&);
void rand (Item&);
void show (const Item&);
 //----------------------------------
#endif
и на файл Itemcpp.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include "Item.h"
#include<iostream>
using namespace std;
int operator<(const Item& A, const Item& B)
{return A.key< B.key;}
int scan (Item &x)
{return (cin>>x.key>>x.info) !=0;}
void rand(Item& x)
{   x.key = (rand()%100);
x.info=1.0 *rand()/100;}
void show (const Item &x)
{cout <<x.key<<" "<<x.info<<endl; }
Все работает как надо! Я знал что Все Антоны классные парни, Спасибо теска )).
antoha398
155 / 155 / 3
Регистрация: 29.03.2012
Сообщений: 418
01.06.2012, 14:50     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика #26
Все работает как надо! Я знал что Все Антоны классные парни, Спасибо теска )).

Не по теме:

точно точно

tihonya
11 / 7 / 1
Регистрация: 30.05.2012
Сообщений: 107
11.08.2012, 21:35  [ТС]     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика #27
Цитата Сообщение от Avazart Посмотреть сообщение
Если пишишь шаблоны пиши их целиком в одном h-файле.
Цитата Сообщение от Avazart Посмотреть сообщение
Грамотно если это шаблоны...
Закинь содержимое OrgfunckArray.cpp в Array.h.
Все это не грамотно!!!!! Грамотно сделать вот так:
http://www.gamedev.ru/code/tip/?id=5303

Наконец-то отрыл, и решил поделится находкой, Все работает правильно корректно!!!

ЗЫ: Век-живи, век -учись!
Avazart
 Аватар для Avazart
6901 / 5141 / 252
Регистрация: 10.12.2010
Сообщений: 22,604
Записей в блоге: 17
11.08.2012, 22:33     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика #28
C++
1
2
3
4
5
6
7
8
// main.cpp
#include "Templ.h"
int main() {
    Templ<int> templ(0);
    Templ<float> templF(0.0f);
    Templ<double> templD(0.0);
    return 0;
}
C++
1
2
3
4
5
6
7
8
9
10
// Templ.h
#pragma once
 
template <typename T>
class Templ {
public:
    Templ(T t);
private:
    T x;
};
C++
1
2
3
4
5
6
7
8
9
10
// Templ.cpp
#include "Templ.h"
 
template Templ<int>;
template Templ<float>;
 
template <typename T>
Templ<T>::Templ(T t) : x(t) {
 
}
1. Код не переносим из-за #pragma once

2. Смысл такого шаблона когда приходится тут же конкретизировать template Templ<int> ?
tihonya
11 / 7 / 1
Регистрация: 30.05.2012
Сообщений: 107
11.08.2012, 23:04  [ТС]     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика #29
Цитата Сообщение от Avazart Посмотреть сообщение
1. Код не переносим из-за #pragma once

.
Пункт 1) к чему это не понимаю(можно как угодно сделать #pragma once студия сама генерирует) . Здесь по поводу раздельной компиляции шаблонов говорится.
Цитата Сообщение от Avazart Посмотреть сообщение

2. Смысл такого шаблона когда приходится тут же конкретизировать template Templ<int> ?
В столбик перечисляешь все Типы данных с которыми будешь работать и код работает со всеми из них, хоть 200 штук и один код!

Добавлено через 15 минут
вот так:
C++
1
2
3
4
5
6
7
8
//Templ.cpp
#include "Templ.h"
template Templ<int>;
template Templ<float>;
template Templ<char>;
 
...
...
И со всеми этими тапами код будет работать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2012, 23:24     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика
Еще ссылки по теме:

C++ Heap Corruption Detected в листинге 19.6 из книги "Освой с++ за 21 день"
Алгоритмы поиска. "Блудный сын" C++
Что подразумевает требование "алгоритмы и структуры данных" в описании вакансий? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Avazart
 Аватар для Avazart
6901 / 5141 / 252
Регистрация: 10.12.2010
Сообщений: 22,604
Записей в блоге: 17
11.08.2012, 23:24     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика #30
В столбик перечисляешь все Типы данных с которыми будешь работать и код работает со всеми из них, хоть 200 штук и один код!
В том то и дело что нужно лезть в реализацию шаблона своими руками при появлении новых типов!

К примеру посмотрите в хедеры STL они явно не так организованы, в них не нужно лезть и что-то прописывать что бы добавить новую специализацию...
Yandex
Объявления
11.08.2012, 23:24     6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика
Ответ Создать тему
Опции темы

Текущее время: 09:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru