Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.61/18: Рейтинг темы: голосов - 18, средняя оценка - 4.61
kompnet
41 / 1 / 2
Регистрация: 11.10.2011
Сообщений: 112
1

Челночная сортировка

10.05.2012, 21:44. Просмотров 3308. Ответов 17
Метки нет (Все метки)

Дан массив фамилий, требуется его упорядочить в алфавитном порядке, используя челночную сортировку.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.05.2012, 21:44
Ответы с готовыми решениями:

Челночная сортировка
Дан массив размером 10,000 сделать челночную сортировку!

челночная сортировка
доброго времени суток! кому не сложно объяснить по поводу алгоритма челночной...

Челночная сортировка / Список
Я бы хотел попросить о помощи более опытных людей в програмирование. сам...

Челночная сортировка элементов массива по убыванию
Есть пример сортировки по возрастанию, не пойму как сделать сортировку по...

Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется
Программа создает динамический массив с рандомным заполнением. Дальше выбор...

17
zitxbit
89 / 741 / 279
Регистрация: 11.04.2012
Сообщений: 971
11.05.2012, 16:32 2
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
#define N 10
 
void swap(int& n1, int& n2);
 
int main()
{
    int A[10] = { 7, 9, 6, 1, 5, 4, 3, 2, 8, 9 };
 
    for (int i = 0; i < N-1; i++)
        if (A[i] > A[i+1])
        {
            swap(A[i],A[i+1]);
            for (int k = i; (A[k] < A[k-1]) && (k >= 1); k--)
                swap(A[k],A[k-1]);
        }
 
    for (int q = 0; q < N; q++)
          printf("%d ",A[q]);
    printf("\n");
 
    return 0;
}
 
void swap(int& n1, int& n2)
{ int _t = n1; n1 = n2; n2 = _t; }
http://liveworkspace.org/code/b88b992f9f833b2a94ee64e48706c5ac
0
kompnet
41 / 1 / 2
Регистрация: 11.10.2011
Сообщений: 112
12.05.2012, 18:06  [ТС] 3
Это именно челночная сортировка?
0
zitxbit
89 / 741 / 279
Регистрация: 11.04.2012
Сообщений: 971
12.05.2012, 19:30 4
Да это именно челночная сортировка. http://wenegred.ru/forum/15-84-1
1
kompnet
41 / 1 / 2
Регистрация: 11.10.2011
Сообщений: 112
12.05.2012, 23:15  [ТС] 5
А как теперь все это реализовать со структурой данных? Как обращаться к конкретному эл-ту структуры?
0
zitxbit
89 / 741 / 279
Регистрация: 11.04.2012
Сообщений: 971
13.05.2012, 09:22 6
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
#define N 10
 
typedef struct Nums
{
    int n;
} NUMS;
 
void swapn(NUMS& n1, NUMS& n2); 
 
int main()
{
   static NUMS nums[] = { { 7 }, { 9 }, { 6 }, { 1 }, { 5 }, { 4 }, { 3 }, { 2 }, { 8 }, { 9 } }; 
  
   for (int i = 0; i < N-1; i++)
        if (nums[i].n > nums[i+1].n)
        {
            swapn(nums[i], nums[i+1]);
            for (int k = i; (nums[k].n < nums[k-1].n) && (k >= 1); k--)
                swapn(nums[k],nums[k-1]);
 
        }
 
    for (int q = 0; q < N; q++)
          printf("%d ",nums[q].n);
    printf("\n");
 
    return 0;
}
 
void swapn(NUMS& n1, NUMS& n2)
 { NUMS _tn = n1; n1 = n2; n2 = _tn; }
http://liveworkspace.org/code/e513185c04ac404851a8dbf208c43ba5
0
kompnet
41 / 1 / 2
Регистрация: 11.10.2011
Сообщений: 112
13.05.2012, 14:54  [ТС] 7
Хорошо. А если структура хранится в файле, т.е. она уже есть?
0
zitxbit
89 / 741 / 279
Регистрация: 11.04.2012
Сообщений: 971
13.05.2012, 15:17 8
В каком файле текстовом или бинарном?

Добавлено через 22 минуты
Запись структуры NUMS в бинарный файл input.dat:

C++
1
2
3
4
5
6
7
8
    const char* filename = "input.dat";
    ofstream ofs(filename, ofstream::binary);
 
    NUMS* pNums = new NUMS[N];
    for (int i = 0; i < N; i++)
        pNums[i].n = rand() % 9 + 1;
 
    ofs.write((char*)pNums, sizeof(NUMS) * N);
Чтение структуры NUMS из бинарного файла input.dat:

C++
1
2
3
4
5
6
7
    NUMS* pNums = new NUMS[N];
 
    ifstream ifs(filename,ifstream::binary);
    ifs.read((char*)pNums, sizeof(NUMS) * N);
 
    for (int i = 0; i < N; i++)
        printf("%d ",pNums[i].n);
0
kompnet
41 / 1 / 2
Регистрация: 11.10.2011
Сообщений: 112
17.05.2012, 16:28  [ТС] 9
А для фамилий как? В файле есть структура в которой массив фамилий, необходимо отсортировать по возрастанию
0
kompnet
41 / 1 / 2
Регистрация: 11.10.2011
Сообщений: 112
19.05.2012, 19:55  [ТС] 10
??????????????????/????
0
zitxbit
89 / 741 / 279
Регистрация: 11.04.2012
Сообщений: 971
19.05.2012, 20:37 11
Как только сделаю размещу. Ждите.

Добавлено через 22 минуты
Как только сделаю сразу размещу, ждите.

Добавлено через 17 минут
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
#include <string.h>
#include <locale.h>
 
#define N 10
 
typedef struct Person
{
    char name[256];
} PERSON;
 
void swaps(char* psz1, char* psz2);
bool iseqkey(char* psz1, char* psz2, int pos);
 
int main()
{
   setlocale(LC_ALL,"Russian");
 
   static PERSON pers[] = { { "Ivanov"  }, { "Petrov"  }, { "Stepanov" }, { "Sidorov" }, 
                            { "Rybakov" }, { "Abramov" }, { "Archipov" }, { "Pavlov"  }, 
                            { "Petuhov" }, { "Isakov"  } }; 
  
   for (int q = 0; q < 256; q++)
       for (int i = 0; i < N-1; i++)
            if (pers[i].name[q] > pers[i+1].name[q] && 
                iseqkey(pers[i].name,pers[i+1].name, q))
            {
                swaps(pers[i].name, pers[i+1].name);
                for (int k = i; (pers[k].name[q] < pers[k-1].name[q]) && (k >= 1); k--)
                     if (iseqkey(pers[k].name,pers[k-1].name, q))
                         swaps(pers[k].name,pers[k-1].name);
            }
 
    for (int q = 0; q < N; q++)
        printf("%s\n",pers[q].name);
 
    return 0;
}
 
bool iseqkey(char* psz1, char* psz2, int pos)
{
    for (int i = pos-1; i >= 0; i--)
        if (psz1[i] != psz2[i])
            return false;
 
    return true;
}
 
void swaps(char* psz1, char* psz2)
{
    static char* psztemp = new char[256];
    strcpy(psztemp, psz1);
    strcpy(psz1, psz2); 
    strcpy(psz2, psztemp);
}
http://liveworkspace.org/code/f90d743e2578b06b5b47e3084ff25f4a
0
kompnet
41 / 1 / 2
Регистрация: 11.10.2011
Сообщений: 112
20.05.2012, 14:42  [ТС] 12
Фамилии уже есть в бинарном файле
0
zitxbit
89 / 741 / 279
Регистрация: 11.04.2012
Сообщений: 971
20.05.2012, 16:21 13
Формат бинарного файла?
0
kompnet
41 / 1 / 2
Регистрация: 11.10.2011
Сообщений: 112
20.05.2012, 17:09  [ТС] 14
. txt

Добавлено через 11 минут
Я вам в личку прислал сообщение
0
zitxbit
89 / 741 / 279
Регистрация: 11.04.2012
Сообщений: 971
20.05.2012, 17:11 15
Так я не понял бинарный файл или текстовый (.txt)?
0
kompnet
41 / 1 / 2
Регистрация: 11.10.2011
Сообщений: 112
20.05.2012, 17:23  [ТС] 16
посмотрите свою личку
0
zitxbit
89 / 741 / 279
Регистрация: 11.04.2012
Сообщений: 971
20.05.2012, 17:58 17
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
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <locale.h>
 
struct gai
{char marka[15];
char FIO[25];
char color[10];
char nomer[10];
};
 
gai st[100];
FILE *f;
 
void swaps(gai& st1, gai& st2);
bool iseqkey(char* psz1, char* psz2, int pos);
 
void input()
//функция ввода и хранения данных 
{char s='\0';
int i;
f=fopen("d:\\gai.txt","r+");
system("cls");
if (f)
{do
{fflush(stdin);
printf("\n База существует! Выберите действие\n");
printf("0 - создать заново\n");
printf("1 - добавить данные\n");
printf("2 - отказаться от ввода\n");
s=getchar();
if (s=='0')
f=fopen("d:\\gai.txt","w+");
else
if (s=='1') 
f=fopen("d:\\gai.txt","a+");
}
while (s!='0' && s!='1' && s!='2');
}
else
printf("Для окончания в каждом поле введите \"0\"\n");
f=fopen("d:\\gai.txt","wb+");
if (s!='2')
{
int i = 0;
while (i < 100)
{
fflush(stdin);
printf("\nФамилия И.О.: ");
gets(st[i].FIO);
if (*st[i].FIO == '0') break;
printf("\nМарка: ");
gets(st[i].marka);
if (*st[i].marka == '0') break;
printf("\nНомер: ");
gets(st[i].nomer);
if (*st[i].nomer == '0') break;
printf("\nЦвет: ");
gets(st[i].color);
if (*st[i].color == '0') break;
i++;
}
for (int q = 0; q < i; q++)
    fprintf(f,"%s %s %s %s\n",st[q].FIO,
        st[q].marka,st[q].nomer,st[q].color);
fclose(f); 
}
}
 
void select()
{ FILE* f=fopen("d:\\gai.txt","rb+");
system("cls");
int x = 0;
for (x = 0; !feof(f); x++)
    fscanf(f,"%s %s %s %s",st[x].FIO,st[x].marka,
        st[x].nomer,st[x].color);
//а здесь челночная сортировка
   for (int q = 0; q < 256; q++)
       for (int i = 0; i < x-1; i++)
            if (st[i].FIO[q] > st[i+1].FIO[q] && 
                iseqkey(st[i].FIO,st[i+1].FIO, q))
            {
                swaps(st[i], st[i+1]);
                for (int k = i; (st[k].FIO[q] < st[k-1].FIO[q]) && (k >= 1); k--)
                     if (iseqkey(st[k].FIO, st[k-1].FIO, q))
                         swaps(st[k],st[k-1]);
            }
 
    for (int q = 0; q < x; q++)
        printf("%s %s %s %s\n",st[q].FIO, 
            st[q].marka,st[q].nomer,st[q].color);
}
 
void select2()
//Функция выдачи полной информации об автомобиле владельца
{gai st;
int k=0;
char FIO[25];
f=fopen("d:\\gai.txt","rb");
system("cls");
if (!f)
{printf("Нет данных! Нажмите любую клавишу");
getch();
}
else
{fflush(stdin);
printf("Фамилию владельца: ");
gets(FIO);
printf("\n|-----------------|--------|--------|----------|");
printf("\n| Фамилия И.О. | марка | цвет | номер |");
printf("\n|-----------------|--------|--------|----------|");
while(fread(&st,sizeof(st),1,f)) { }
//здесь должен быть бинарный поиск
}
}
 
int main()
{//главная функция
setlocale(LC_ALL,"Russian");
char s='\0';
do 
{system("cls");
fflush(stdin);
printf("\n\nБаза данных ГАИ\n");
printf("Выберите действие: \n");
printf("1 - Ввод данных \n");
printf("2 - Выдача таблицы данных в алфавитном порядке\n"); 
printf("3 - Выдача полной информации об автомобиле владельца\n");
printf("4 - Выход\n");
s=getchar();
switch(s)
{
case '1':input();break;
case '2':select();break;
case '3':select2();break;
}
}
while (s!='4');
} 
 
bool iseqkey(char* psz1, char* psz2, int pos)
{
    for (int i = pos-1; i >= 0; i--)
        if (psz1[i] != psz2[i])
            return false;
 
    return true;
}
 
void swaps(gai& st1, gai& st2)
{ gai _t = st1; st1 = st2; st2 = _t; }
0
kompnet
41 / 1 / 2
Регистрация: 11.10.2011
Сообщений: 112
20.05.2012, 21:17  [ТС] 18
Спасибо, теперь буду разбираться=)
0
20.05.2012, 21:17
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2012, 21:17

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит...

Быстрая сортировка (сортировка Хоара) для связных списков
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива
Мне нужно отсортировать фрагмент массива, расположенный между первым и...


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

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

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