Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
monoxpom
0 / 0 / 3
Регистрация: 23.04.2009
Сообщений: 13
#1

Рекурсия - пояснить назначение функции - C (СИ)

24.05.2009, 14:16. Просмотров 568. Ответов 1
Метки нет (Все метки)

Обьясните, плииз, поподробнее, что делает функция qs

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <stdio.h>
#include <tchar.h>
#include <conio.h>
#include <stdlib.h>
#include <windows.h>
 
struct soldier
{
    int nNumber;
    BYTE bWeight;
    BYTE bHeight;
};
 
int compare(const void *sld1, const void *sld2);
void qs(int nFirst, int nLast, BYTE *pbArr, int nElSize);
void swap (void *pObj1, void *pObj2, int nObjSize, void *pTmp);
void quik_sort (void *pArr, int n, int nElSize);
 
void *pTmp;                             //временный буфер
 
int _tmain(int argc, _TCHAR* argv[])
{
    soldier sldList[] = { 
                        { 1, 65, 172},
                        { 2, 67, 172},
                        { 3, 69, 180},
                        { 4, 71, 180},
                        { 5, 79, 175},
                        { 6, 64, 175},
                        { 7, 85, 180},
                        { 8, 56, 163},
                        { 9, 71, 172},
                        {10, 69, 175},
                        {11, 73, 163},
                        {12, 76, 172},
                        {13, 70, 192},
                        {14, 73, 192},
                        {15, 42, 163},
                        {16, 80, 175},
                        {17, 93, 192},
                        {18, 70, 192},
                        {19, 77, 175},
                        {20, 63, 163},
                        {21, 47, 159}
                        };
    int nSoldiers = sizeof(sldList)/sizeof(soldier);
 
    //сортируем список солдат
    quik_sort (sldList, nSoldiers, sizeof(soldier));
 
    //список отсортирован - выведем его
    printf ("\n#   H    W\n");
    for (int i=0; i<nSoldiers; i++)
        printf ("%03d %d %d\n",sldList[i].nNumber, sldList[i].bHeight, sldList[i].bWeight);
    
    _getch ();
 
    return 0;
}   //int _tmain(int argc, _TCHAR* argv[])
 
int compare(const void *sld1, const void *sld2)
{
    //функция для сравнения элементов массива
    //функция должна возвращать значение <0, если первый элемент меньше второго, 0 - если
    //элементы равны и значение >0, если первый аргумент больше второго
    soldier *pSld1 = (soldier*) sld1;
    soldier *pSld2 = (soldier*) sld2;
    
 
    //а это более очевидный и всегда работающий способ, но гораздо более тормозной
    if (pSld1->nHeight > pSld2->nHeight)
        return 1;
 
    if (pSld1->nHeight < pSld2->nHeight)
        return -1;
 
    //если мы тут, то у солдат одинаковый рост. Сравним вес
    if (pSld1->nWeight > pSld2->nWeight)
        return 1;
 
    if (pSld1->nWeight < pSld2->nWeight)
        return -1;
 
    //у нас два совсем одинаковых солдата
    return 0;
 
    return 0;
}   //int compare( void *pEmpty, const void *sld1, const void *sld2)
 
void qs(int nFirst, int nLast, BYTE *pArr, int nElSize)
{
    //реализация алгоритма быстрой сортировки
    //Эта функция отличается от классической тем, что оперирует сразу байтовыми массивами по nElSize байт.
    //Эта версия заточена под сортировку массивов структур.
    //Первый аргумент - номер первого элемента в массиве, второй - номер последнего, pArr - массив объектов, nElSize - размер 1 объекта в байтах
    int i = nFirst*nElSize, j = nLast*nElSize;
    int idx = nFirst, jdx = nLast;
    int nMean = (nLast - nFirst)/2+nFirst;  //номер элемента из середины массива
    BYTE *x = pArr + nMean*nElSize;         //и указатель на него - с ним и происходят все сравнения
     
    do {
        while (compare(pArr+i, x)<0)    //если очередной элемент по индексу i "меньше" срединного - все в порядке,
        {
            i+=nElSize;                 //перемещаем индекс на один элемент в сторону хвоста массива
            idx++;          
        }
        while (compare(pArr+j, x)>0)    //если очередной элемент по индексу j "больше" срединного - все в порядке,          
        {
            j-=nElSize;                 //перемещаем индекс на один элемент в сторону начала массива
            jdx--;          
        }
        
        //в результате этих действий у нас "левее" i лежат все эелементы "меньше" *x, а "правее" j - элементы "больше"  
        if(idx <= jdx)
        {            
            if (idx < jdx) 
            {
                swap(pArr + i, pArr + j,nElSize, pTmp);
                //если мы производим обмен с опорным элементом, то нужно запомнить, что он "переехал"       
                if (nMean == idx)
                {
                    nMean = jdx;
                    x = pArr + nMean*nElSize;
                }
                else if (nMean == jdx)
                {
                    nMean = idx;
                    x = pArr + nMean*nElSize;
                }
            }
            i+=nElSize;
            idx++;
            j-=nElSize;
            jdx--;
        }
    } while (idx <= jdx);
 
    if (nFirst < jdx)
        qs(nFirst,jdx,pArr,nElSize);    //теперь то же самое делаем с левой половинкой массива
    if (idx < nLast)
        qs(idx, nLast,pArr,nElSize);    //и с правой
}   //void qs(int first, int last)
 
void swap (void *pObj1, void *pObj2, int nObjSize, void *pTmp)
{
    //побайтовы обмен двух областей памяти, каждая размером в nObjSize байт.
    //Внимание! pTmp должен указывать на буфер размером не менее nObjSize байт, он нужен для
    //временного хранения одного элемента. Вся ответственность за выделение памяти под него - на вызывающей
    //стороне
    memcpy_s (pTmp, nObjSize, pObj1, nObjSize);
    memcpy_s (pObj1, nObjSize, pObj2, nObjSize);
    memcpy_s (pObj2, nObjSize, pTmp, nObjSize); 
}   //void swap (void *pObj1, void *pObj2, int nObjSize)
 
void quik_sort (void *pArr, int n, int nElSize)
{
    //эта функция служит для первого вызова более низкоуровневой функции qs
    //также здесь выделяется память под временный буфер (см. функцию swap)
    pTmp = new char [nElSize];
 
    qs (0, n-1, (BYTE*)pArr, nElSize);
 
    delete pTmp;
}   //void quik_sort (void *pArr, int n, int nElSize, void*())

http://www.cyberforum.ru/c-beginners/thread1087662.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.05.2009, 14:16
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Рекурсия - пояснить назначение функции (C (СИ)):

Объяснить назначение функции
что делает следующая функция int CmpDate(const DATE *d1,const DATE *d2) {...

Функции и рекурсия: вычислить значение составной функции
Помогите решить задачку, с использованием операторов ветвления if, if-else и...

Рекурсия: нахождение n-ой производной функции
Найти рекурсивную n-производную f(x)=exp(-x*x/2) для заданого х

Рекурсия: вычисление функции Аккермана
Написать программу, реализующую составленный алгоритм на языке программирования...

Функции. Нахождение цифрового корня числа. Рекурсия
Нужно написать две программы, которые находят цифровой корень числа. Первая...

1
vet
175 / 176 / 54
Регистрация: 08.04.2009
Сообщений: 1,309
24.05.2009, 14:55 #2
C++
1
2
3
4
5
 if (nFirst < jdx)
        qs(nFirst,jdx,pArr,nElSize);    //теперь то же самое делаем с левой половинкой массива
        if (idx < nLast)
        qs(idx, nLast,pArr,nElSize);    //и с правой
}       //void qs(int first, int last)

Этот кусок и есть рекурсия
По моему делает следующие: Сначала массив делим пополам и вызываем ф-цию qs в первый раз , а затем вызываем qs снова для каждой половины и выполням qs для каждой из них и так далее пока все не переберем и не отсортируем. Вроде бы так
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2009, 14:55
Привет! Вот еще темы с решениями:

Пояснить сортировку слиянием
Что выполняет???мне нужн ответ... +можете написать обозначение функции(если...

Пояснить строку кода
int *(*(*x()(); Транслятор пропускает без вопросов) Сначало я подумал что...

Пояснить строку программы
if (!OpenDialog1-&gt;Execute()) return; Объясните, пожалуйста, эту запись.....

Пояснить объявления в структуре
увидел сие где то что то подобное в винапишных структурах, никогда раньше не...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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