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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.60
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
10.05.2012, 21:44     Челночная сортировка #1
Дан массив фамилий, требуется его упорядочить в алфавитном порядке, используя челночную сортировку.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 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/b88b99...ee64e48706c5ac
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
12.05.2012, 18:06  [ТС]     Челночная сортировка #3
Это именно челночная сортировка?
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
12.05.2012, 19:30     Челночная сортировка #4
Да это именно челночная сортировка. http://wenegred.ru/forum/15-84-1
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
12.05.2012, 23:15  [ТС]     Челночная сортировка #5
А как теперь все это реализовать со структурой данных? Как обращаться к конкретному эл-ту структуры?
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 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/e51318...a8dbf208c43ba5
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
13.05.2012, 14:54  [ТС]     Челночная сортировка #7
Хорошо. А если структура хранится в файле, т.е. она уже есть?
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 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);
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
17.05.2012, 16:28  [ТС]     Челночная сортировка #9
А для фамилий как? В файле есть структура в которой массив фамилий, необходимо отсортировать по возрастанию
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
19.05.2012, 19:55  [ТС]     Челночная сортировка #10
??????????????????/????
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 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/f90d74...47e3084ff25f4a
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
20.05.2012, 14:42  [ТС]     Челночная сортировка #12
Фамилии уже есть в бинарном файле
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
20.05.2012, 16:21     Челночная сортировка #13
Формат бинарного файла?
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
20.05.2012, 17:09  [ТС]     Челночная сортировка #14
. txt

Добавлено через 11 минут
Я вам в личку прислал сообщение
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
20.05.2012, 17:11     Челночная сортировка #15
Так я не понял бинарный файл или текстовый (.txt)?
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
20.05.2012, 17:23  [ТС]     Челночная сортировка #16
посмотрите свою личку
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 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; }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2012, 21:17     Челночная сортировка
Еще ссылки по теме:

C++ Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется
Быстрая сортировка (сортировка методом Хоара) C++
Челночная сортировка C++

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

Или воспользуйтесь поиском по форуму:
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
20.05.2012, 21:17  [ТС]     Челночная сортировка #18
Спасибо, теперь буду разбираться=)
Yandex
Объявления
20.05.2012, 21:17     Челночная сортировка
Ответ Создать тему
Опции темы

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