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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.81
tihonya
11 / 7 / 1
Регистрация: 30.05.2012
Сообщений: 107
#1

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

30.05.2012, 01:42. Просмотров 2138. Ответов 29
Метки нет (Все метки)

Разбираю 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++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Книги по С++ (что читать после книги Дейтела "Как программировать на С++") - C++
Добрый день господа!!! Я от можно сказать дочитываю Дейтела &quot;Как программировать на С++&quot; 5 издание, и от думаю какую следующую книгу...

Книги Седжвика - C++
вечер добрый есть ли существенная разница между этими книгами? 1) http://www.ozon.ru/context/detail/id/1425749/ 2)...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Седжвик Р. - Фундаментальные алгоритмы на C++. Объясните лемму - C++
Большая просьба ко всем, кто читал или читает эту книгу помочь мне.(я читаю 3-ю редакцию) Очень долго мучаюсь, но никак не могу понять...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Avazart
Эксперт С++
7152 / 5329 / 278
Регистрация: 10.12.2010
Сообщений: 23,584
Записей в блоге: 17
30.05.2012, 03:22 #16
Это особенность шаблонов на большенстве компиляторов нельзя размещать объявление шаблонов и их реализацию в разных файлах - они должны быть в одном файле
tihonya
11 / 7 / 1
Регистрация: 30.05.2012
Сообщений: 107
30.05.2012, 03:23  [ТС] #17
ЛАдно хорошо переделаю, прогу, чтоб работала, и еще один вопрос по этому же коду. Функция мэйн получает параметры
C++
1
2
3
void main(int argc, char *argv[])
 
{ int N = atoi(argv[1]), sw = atoi (argv[2]);
и их сразу использует, где оно должно брать эти параметры?? И для чего таким образом обьявляется мэйн, по крайней мере в книге (этой-же ) всегда так пишится..
Avazart
Эксперт С++
7152 / 5329 / 278
Регистрация: 10.12.2010
Сообщений: 23,584
Записей в блоге: 17
30.05.2012, 03:27 #18
int argc - количество аргументов
char *argv[] массив аргументов

Это параметры которые надо передать... точнее которые принимает твоя прога в командной строке.

Т.е например если у тебя винда выполняешь команду cmd потом пишиш имя твоей проги и через пробел перечисляешь параметры.
Запускается прога сразу с какими- то данными и выводит результат
tihonya
11 / 7 / 1
Регистрация: 30.05.2012
Сообщений: 107
30.05.2012, 03:33  [ТС] #19
Цитата Сообщение от Avazart Посмотреть сообщение
int argc - количество аргументов
char *argv[] массив аргументов

Это параметры которые надо передать твоей проге в командной строке.
А как это сделать (у меня 2010 студия) Она у меня нече не спрашивает, или это какбы ключи, параметры после запуска ЕХЕ файла? типо *.ехе -2 -34, 45
Но все равно как при компиляции передать эти аргументы в мейн?
Avazart
Эксперт С++
7152 / 5329 / 278
Регистрация: 10.12.2010
Сообщений: 23,584
Записей в блоге: 17
30.05.2012, 03:39 #20
При компиляции нет, после компиляции ( если не выдаст ошибку) можно через 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;
}
tihonya
11 / 7 / 1
Регистрация: 30.05.2012
Сообщений: 107
31.05.2012, 01:09  [ТС] #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 #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  [ТС] #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 #24
С Item.h делайте как обычно. в заголовке объявление сруктуры и функций; в исходнике в начале подключаете заголовок, потом пишите определение функций.
tihonya
11 / 7 / 1
Регистрация: 30.05.2012
Сообщений: 107
01.06.2012, 14:40  [ТС] #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 #26
Все работает как надо! Я знал что Все Антоны классные парни, Спасибо теска )).

Не по теме:

точно точно

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

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

ЗЫ: Век-живи, век -учись!
Avazart
Эксперт С++
7152 / 5329 / 278
Регистрация: 10.12.2010
Сообщений: 23,584
Записей в блоге: 17
11.08.2012, 22:33 #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  [ТС] #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>;
 
...
...
И со всеми этими тапами код будет работать.
Avazart
Эксперт С++
7152 / 5329 / 278
Регистрация: 10.12.2010
Сообщений: 23,584
Записей в блоге: 17
11.08.2012, 23:24 #30
В столбик перечисляешь все Типы данных с которыми будешь работать и код работает со всеми из них, хоть 200 штук и один код!
В том то и дело что нужно лезть в реализацию шаблона своими руками при появлении новых типов!

К примеру посмотрите в хедеры STL они явно не так организованы, в них не нужно лезть и что-то прописывать что бы добавить новую специализацию...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2012, 23:24
Привет! Вот еще темы с ответами:

Ответы к упражнениям из книги Сэджвика "Фундаментальные алгоритмы на С++" части 1-4 - C++
Привет! Читаю данную книгу, в конце каждой главы имеются упражнения, но нет ответов на них. На решение некоторых задач просто нехватает...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
11.08.2012, 23:24
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru