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

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

Войти
Регистрация
Восстановить пароль
 
 
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
#1

Как осуществить сортировку вставками в списках? - C++

21.10.2010, 00:41. Просмотров 879. Ответов 19
Метки нет (Все метки)

Необходимо отсортировать список по алфавиту, помогите пожалуйста.

Добавлено через 1 час 23 минуты
методом: из списка в массив и обратно меня чето не прикалоло сортировать
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.10.2010, 00:41
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как осуществить сортировку вставками в списках? (C++):

Сортировку вставками меняем на Пирамидальную сортировку и на Сортировку подсчётом - C++
Здравствуйте. Я не как не могу разобраться.Помогите. У меня есть листинг сортировки вставками: #include "stdafx.h" #include...

Как реализовать сортировку вставками? - C++
Дорогие форумчане. на учебе дали задание по сортировки вставками. Берется очередной элемент и извлекается из массива. Затем от начала...

Сортировку вставками меняем на сортировку слиянием - C++
Код программы выполняет сортировку массива вставками. Как сюда вставить код сортировки массива методом слияния, вместо метода вставками,что...

Реализовать сортировку вставками - C++
задание: Написать программу, реализующую один из простых методов сортировки (вставками) помогите девчонке) 1 курс

Безразмерный файл забить структурами и осуществить их сортировку - C++
Очень не понятно что в этой задачке от меня требуется)) Текст задачи: Безразмерный файл забить структурами и осуществить их...

Осуществить сортировку текстового файла по длине строк циклическим слиянием/разделением - C++
Осуществить сортировку текстового файла циклическим слиянием/разделением (по длине строк). Файл читается группами по n строк в динамический...

19
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,813
21.10.2010, 02:39 #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
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct STR {
    char * text;
    struct STR * next;
} str_t;
 
str_t * new_str(const char * buf){
    str_t * st;
 
    if ( ( st = (str_t *)malloc(sizeof(str_t)) ) == NULL )
        return NULL;
    if ( ( st->text = strdup(buf) ) == NULL ){
        free(st);
        return NULL;
    }
    st->next = NULL;
    
    return st;
}
 
str_t * del_str(str_t * st){
    str_t * ret = st->next;
    free(st->text);
    free(st);
    return ret;
}
 
typedef struct {
    str_t * first;
    str_t * last;
} list_t;
 
list_t * new_list(void){
    list_t * list;
    
    if ( ( list = (list_t *)malloc(sizeof(list_t)) ) == NULL )
        return NULL;
    list->first = NULL;
    list->last = NULL;
    
    return list;
}
 
int push_str(list_t * list, const char * buf){
    str_t * st;
    
    if ( ( st = new_str(buf) ) == NULL )
        return -1;
    if ( ! list->first )
        list->first = st;
    else 
        list->last->next = st;
    list->last = st;
    
    return 0;
}
 
void del_list(list_t * list){
    while ( list->first = del_str(list->first) )
        ;
    free(list);
}
 
void swap_strings(char ** a, char ** b){
    char * tmp = *a;
    *a = *b;
    *b = tmp;
}
 
str_t * min_str(str_t * start){
    str_t * cur, * min;
    
    min = start;
    for ( cur = start->next; cur; cur = cur->next )
        if ( strcmp(cur->text, min->text) < 0 )
            min = cur;
    return min;
}
 
void sort_list(list_t * list){
    str_t * st, * min;
    for ( st = list->first; st->next; st = st->next )
        if ( ( min = min_str(st) ) != st )
            swap_strings(&st->text, &min->text);
}
 
void print_list(const list_t * list){
    const str_t * st;
    for ( st = list->first; st; st = st->next )
        printf("%s\n", st->text);
}
 
int empty_list(list_t * list){
    return list->first == NULL;
}
 
int main(void){
    char buf[BUFSIZ], * p;
    list_t * list;
    
    if ( ( list = new_list() ) == NULL ){
        fprintf(stderr, "Can't create a new list!\n");
        exit(1);
    }
    
    printf("Enter some strings (empty - finish):\n");
    while ( printf("> ") && fgets(buf, BUFSIZ, stdin) ){
        if ( p = strrchr(buf, '\n') )
            *p = '\0';
        if ( ! *buf )
            break;
        if ( push_str(list, buf) ){
            fprintf(stderr, "Can't add string to list!\n");
            del_list(list);
            exit(1);
        }
    }
    
    if ( empty_list(list) ){
        fprintf(stderr, "List is empty!\n");
        exit(1);
    }
    
    printf("\nSorted ascendant:\n");
    sort_list(list);
    print_list(list);
    
    del_list(list);
    exit(0);
}
2
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
21.10.2010, 15:16  [ТС] #3
спасибо, буду разбираться

Добавлено через 2 часа 14 минут
чет я не подумал просто поля с фамилиями заменять..
кстати, почему в вашей проге работает ввод/вывод на русском языке ?
0
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,813
21.10.2010, 15:29 #4
Цитата Сообщение от KBAC Посмотреть сообщение
чет я не подумал просто поля с фамилиями заменять..
вообще-то, если структура содержит статические массивы (типа char name[BUFSIZ]) лучше создавать двусвязный список и менять указатели на элементы, а не содержимое массивов. У меня в структуре находится указатель на строку, поэтому проще так, как сделал...

Цитата Сообщение от KBAC Посмотреть сообщение
почему в вашей проге работает ввод/вывод на русском языке ?
а не должен бы?
0
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
21.10.2010, 15:56  [ТС] #5
Цитата Сообщение от easybudda Посмотреть сообщение
а не должен бы?
там ведь не стоит никаких setlocale, SetConsoleCP(1251), SetConsoleOutputCP(1251)О_о
0
IchMors
97 / 93 / 4
Регистрация: 16.05.2010
Сообщений: 310
21.10.2010, 16:03 #6
Вот мне просто интересно, а вот так не катит?
C++
1
2
3
4
5
6
7
8
9
int main()
{
    string mass = "faslkvg";
    cout << mass;
    cout <<endl;
    sort(mass.begin(), mass.end());
 
    cout << mass;
}
0
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,813
21.10.2010, 16:11 #7
IchMors, нужно не буквы в слове сортировать, а слова в списке.
0
IchMors
21.10.2010, 16:12
  #8

Не по теме:

аааа, ферштейн...

0
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
21.10.2010, 16:14  [ТС] #9
IchMors, я так понял эта функция для базовых классов данных, не для списков структур, тем она и не подходит, что ей не отсортируешь по фамилиям.

easybudda, ваш способ наверно все таки будет не очень крутым для сортировки таких структур
C++
1
2
3
4
5
6
7
8
struct WORKER {
        char familiya[15];
    char imya[15];
    char ot4estvo[15];
        char dolzhnost[25];
        int stage;
    WORKER* next;
} ;
надо создавать будет структуру tmp без поля некст и др. заморочки.. может, тут лучше будет ввести еще одно поле для указателей, которым я буду присваивать уже адреса в порядке алфавита?
0
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,813
21.10.2010, 17:04 #10
Цитата Сообщение от KBAC Посмотреть сообщение
ваш способ наверно все таки будет не очень крутым для сортировки таких структур
а это смотря, как делать...
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct WORKER {
        char familiya[15];
        char imya[15];
        char ot4estvo[15];
        char dolzhnost[25];
        int stage;
}worker_t;
 
typedef struct WORKER_HOLDER {
    worker_t * worker;
    struct WORKER_HOLDER * next;
} whold_t;
 
whold_t * new_worker(const worker_t * w){
    whold_t * wh;
 
    if ( ( wh = (whold_t *)malloc(sizeof(whold_t)) ) == NULL )
        return NULL;
    if ( ( wh->worker = (worker_t*)malloc(sizeof(worker_t)) ) == NULL ){
        free(wh);
        return NULL;
    }
    memcpy(wh->worker, w, sizeof(worker_t));
    wh->next = NULL;
    
    return wh;
}
 
whold_t * del_worker(whold_t * wh){
    whold_t * ret = wh->next;
    free(wh->worker);
    free(wh);
    return ret;
}
 
typedef struct {
    whold_t * first;
    whold_t * last;
} list_t;
 
list_t * new_list(void){
    list_t * list;
    
    if ( ( list = (list_t *)malloc(sizeof(list_t)) ) == NULL )
        return NULL;
    list->first = NULL;
    list->last = NULL;
    
    return list;
}
 
int push_worker(list_t * list, const worker_t * w){
    whold_t * wh;
    
    if ( ( wh = new_worker(w) ) == NULL )
        return -1;
    if ( ! list->first )
        list->first = wh;
    else 
        list->last->next = wh;
    list->last = wh;
    
    return 0;
}
 
void del_list(list_t * list){
    while ( list->first = del_worker(list->first) )
        ;
    free(list);
}
 
void swap_workers(whold_t * a, whold_t * b){
    worker_t * w = a->worker;
    a->worker = b->worker;
    b->worker = w;
}
 
whold_t * min_fam(whold_t * start){
    whold_t * cur, * min;
    
    min = start;
    for ( cur = start->next; cur; cur = cur->next )
        if ( strcmp(cur->worker->familiya, min->worker->familiya) < 0 )
            min = cur;
    return min;
}
 
void sort_list(list_t * list){
    whold_t * wh, * min;
    for ( wh = list->first; wh->next; wh = wh->next )
        if ( ( min = min_fam(wh) ) != wh )
            swap_workers(wh, min);
}
 
void print_list(const list_t * list){
    const whold_t * wh;
    for ( wh = list->first; wh; wh = wh->next ){
        printf("%s ", wh->worker->familiya);
        printf("%s ", wh->worker->imya);
        printf("%s ", wh->worker->ot4estvo);
        printf("%s ", wh->worker->dolzhnost);
        printf("%d\n", wh->worker->stage);
    }
}
 
int empty_list(list_t * list){
    return list->first == NULL;
}
 
int main(void){
    worker_t worker;
    list_t * list;
    char answ;
    
    if ( ( list = new_list() ) == NULL ){
        fprintf(stderr, "Can't create a new list!\n");
        exit(1);
    }
    
    while ( 1 ){
        printf("Familiya: ");
        scanf("%14[^\n]%*c", &worker.familiya);
        printf("Imya: ");
        scanf("%14[^\n]%*c", &worker.imya);
        printf("Otchestvo: ");
        scanf("%14[^\n]%*c", &worker.ot4estvo);
        printf("Dolzhnost: ");
        scanf("%24[^\n]%*c", &worker.dolzhnost);
        printf("Stage: ");
        scanf("%d%*c", &worker.stage);
 
        if ( push_worker(list, &worker) ){
            fprintf(stderr, "Can't add worker to list!\n");
            del_list(list);
            exit(1);
        }
        printf("\nAdd another? (y/n): ");
        scanf("%c%*c", &answ);
        if ( answ != 'y' && answ != 'Y' )
            break;
    }
    
    if ( empty_list(list) ){
        fprintf(stderr, "List is empty!\n");
        exit(1);
    }
    
    printf("\nSorted ascendant:\n");
    sort_list(list);
    print_list(list);
    
    del_list(list);
    exit(0);
}
проверкой вводимых данных и красивостью вывода особо не заморачивался - нам же важнее, чтобы список по фамилиям сортировался
Всё ещё работает с русскими буквами
2
IchMors
97 / 93 / 4
Регистрация: 16.05.2010
Сообщений: 310
21.10.2010, 17:06 #11
Опять таки может я ошибаюсь, но:
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
#include <conio.h>
#include <iostream.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <functional>
 
using namespace std;
 
struct WORKER {
        char familiya[15];
        char imya[15];
        char ot4estvo[15];
        char dolzhnost[25];
        int stage;
        WORKER* next;
} ;
 
struct func//определение сортировки
{
  bool operator()(WORKER a, WORKER b)
  { return strcmp(a.familiya,b.familiya) < 0; }
};
 
void out(WORKER a)//вывод
{
    cout << "familiya: ";
    puts(a.familiya);
    cout << "imya: ";
    puts(a.imya);
    cout << "ot4estvo: ";
    puts(a.ot4estvo);
    cout << "dolzhnost: ";
    puts(a.dolzhnost);
    cout << "stage: ";
    cout << a.stage << endl;
}
 
int main()
{   
    vector <WORKER> departament(3);
    func f;
 
//как то там заполняем
    strcpy(departament[0].familiya, "Petrov");
    strcpy(departament[1].familiya, "Zero");
    strcpy(departament[2].familiya, "Sidorov");
//собсна сортировка
    sort(departament.begin(), departament.end(), f);
 
    for(int i = 0; i< departament.size();i++)
        out(departament[i]);
    
    _getch();
//  cin.ignore();
    return 0;
}
0
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,813
21.10.2010, 17:22 #12
Цитата Сообщение от IchMors Посмотреть сообщение
Опять таки может я ошибаюсь, но:
Цитата Сообщение от IchMors Посмотреть сообщение
vector <WORKER> departament(3);
оно же массив, а не список! при таком подходе
Цитата Сообщение от IchMors Посмотреть сообщение
WORKER* next;
нафиг не нужно

да и цель всей этой свистопляски, скорее всего - научиться руками списки делать...
0
IchMors
97 / 93 / 4
Регистрация: 16.05.2010
Сообщений: 310
21.10.2010, 18:04 #13
да, согласен...
Цитата Сообщение от easybudda Посмотреть сообщение
и цель всей этой свистопляски, скорее всего - научиться руками списки делать...
вот KBAC, и делает ручками
0
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
22.10.2010, 11:38  [ТС] #14
вобщем, попробовал перелопатить на свой лад, вот что получилось :
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
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<Windows.h>
#include<stdlib.h>
#include<fstream>
 
using namespace std;
 
char fname[] = "e:\\Workers.txt";
 
struct WORKER {
        char familiya[15];
    char imya[15];
    char ot4estvo[15];
        char dolzhnost[25];
        int stage;
    WORKER* next;
} ;
 
typedef char* pch;
typedef WORKER* pw;
 
void WORKER_add(pw &head,ifstream &fin)
{
    if (head==NULL)
    {
        head=new WORKER;
        head->next=NULL;
        fin >> head->familiya;
        fin >> head->imya;
        fin >> head->ot4estvo;
        fin >> head->dolzhnost;
        fin >> head->stage;
    }
    else 
    {
        pw p;
        p=head;
        while (p->next!=NULL)
            p=p->next;
        p->next=new WORKER;
        p->next->next=NULL;
        fin >> p->next->familiya;
        fin >> p->next->imya;
        fin >> p->next->ot4estvo;
        fin >> p->next->dolzhnost;
        fin >> p->next->stage;
    }
}
pw input_data(pw &head)
{
    ifstream fin;
    fin.open(fname);
    if (!fin)
    {
             cout<<"\aОткрытие файла не удалось! Попытайтесь снова!";
             return head;
    }
    else    
    {
        while(!fin.eof())
                WORKER_add(head,fin);
        fin.close();
     }
     return head;
}
pw min_fam(pw start)
{
    pw p,min;
    min=start;
    for(p=start;p;p=p->next)
        if(strcmp(p->familiya, min->familiya) < 0)
            min=p;
    return min;
}
struct _tmp{
    char familiya[15];
    char imya[15];
    char ot4estvo[15];
    char dolzhnost[25];
    int stage;
};
void exchange(pw &p,pw &min)
{
    _tmp A;
    A.dolzhnost=p->dolzhnost;
    A.familiya=p->familiya;
    A.imya=p->imya;
    A.ot4estvo=p->ot4estvo;
    A.stage=p->stage;
    p->dolzhnost=min->dolzhnost;
    p->familiya=min->familiya;
    p->imya=min->imya;
    p->ot4estvo=min->ot4estvo;
    p->stage=min->stage;
    min->dolzhnost=A.dolzhnost;
    min->familiya=A.familiya;
    min->imya=A.imya;
    min->ot4estvo=A.ot4estvo;
    min->stage=A.stage;
}
pw sort(pw &head)
{
    pw p,min;
    p=head;
    for(p;p->next;p=p->next)
        if(min=min_fam(p)!=p)
            exchange(p,min);
    return head;
}
 
int main()
{ 
        SetConsoleCP(1251); 
        SetConsoleOutputCP(1251);
 
        pw head=NULL;
                head=input_data(head);
        head=sort(head);
        pw p =head;
        cout<<"База работников:\n";
        while (p!=NULL)
        {
            cout<<p->familiya<<' '<<p->imya<<' '<<p->ot4estvo<<endl;
            p=p->next;
        }
        
        return 0;
}
да, еще проблема что не компилируется не пойму, его не устраивает(Великого Компилятора) левые операнды в exchange'е.

Добавлено через 16 часов 16 минут
Помогите пожалуйста!
0
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,813
22.10.2010, 13:26 #15
Цитата Сообщение от KBAC Посмотреть сообщение
Помогите пожалуйста!
А чем моя-то програмка не устроила? Работает же... При чём сортировку должна делать достаточно быстро за счёт того, что меняются только значения указателей, а данные не перемещаются...
0
22.10.2010, 13:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.10.2010, 13:26
Привет! Вот еще темы с ответами:

Подскажите как эту сортировку переделать в сортировку по алфавиту? - C++
Подскажите как эту сортировку переделать в сортировку по алфавиту?? vector&lt;std::pair&lt;string, int&gt;&gt; popularAuthor; ...

сортировку по Tag и сортировку по Eng - C++
Есть структура: struct _1C { string Tag; string Rus; string Eng; _1C(const string &amp;Tag, const string &amp;Rus, const string...

Как заполнить файл и как осуществить посимвольное чтение - C++
решила задачу с файлами на высоком уровне, а нужно на низком, помогите плиз!!!не могу разобраться как заполнить файл и как осуществить...

как осуществить статус загрузки? - C++
помогите пожалуйста мне нужен код для проги чтобы код показывал статускакой то работы...скажем прога работает с файлом и закончит через...


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

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

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