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

Задание на работу со односвязными списками - C++

Восстановить пароль Регистрация
 
DanShady
0 / 0 / 0
Регистрация: 14.04.2013
Сообщений: 18
11.09.2013, 00:47     Задание на работу со односвязными списками #1
Нужна помощь
Задание: В составе программы описать функцию которая меняет местами наибольший и наименьший элемент.
Проблема как раз в том что не знаю как тут с функцией быть...вообщем у меня пока есть программа которая выводит на экран элементы списка. Как поменять местами наибольший и наименьший представляю в принципе но не знаю как реализовать
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
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
struct list             // определение структурного типа list
    {   int dat;        // данные
        struct list *next;  // указатель на следующий эл-т списка
    };
 
typedef list *P_list;   // определение указателя на тип list
 
void main()
{   int N,i;        // N-количество элементов в списке
        
    P_list pb;      // указатель на начало списка
    P_list pt;      // указатель на текущий элемент списка
 
    time_t t;
    srand (time(&t));   // инициировать датчик случ. чисел
    cout << " N=";  // ввести размер списка (с клавиатуры)
    cin >> N;
    //_____________________ Создание списка
                    // создать первый элемент
    pb= new list;       // выделить память
    pb->dat = rand()%100;   // записать данные
    pt=pb;      // установить текущий указатель на начало
    for (i=1;i<N;i++)   // в цикле создать список
    {
        pt->next= new list;// очередной элемент (выделить память)
        pt=pt->next;       //текущий указатель-на вновь созданный элемент
        pt->dat = rand()%100;   // записать данные 
    }                   // создание списка завершено
    pt->next=NULL;          // записать признак конца списка
    //_______________________ печать списка в 10 колонок
    cout<<endl;
    for (pt=pb,i=1; pt!= NULL ;i++)
    {
        cout<< pt->dat; // печать информационного поля списка
        pt=pt->next;      //перемещение указателя на следующий элемент
        if (i%10==0) cout<<endl;       // форматирование (в 10 колонок)
         else cout<<"\t";
    }
    cout<< endl;
    }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.09.2013, 00:47     Задание на работу со односвязными списками
Посмотрите здесь:

Работа со списками C++
C++ Задание со списками
Задание на создание и работу с классами C++
Работа со списками. C++
Программа со списками C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
GoldenChild
28 / 28 / 4
Регистрация: 12.06.2013
Сообщений: 65
11.09.2013, 01:25     Задание на работу со односвязными списками #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
list *find_max(list *head) {
    int max = head->dat;
    for (list *p = head->next; p; p = p->next) {
        if (p->dat > max) {
            max = p->dat;
        }
    }
    return find(head, max); // надеюсь поиск по ключу вы сможете реализовать
}
 
list *find_min(list *head) {
    int min = head->dat;
    for (list *p = head->next; p; p = p->next) {
        if (p->dat < min) {
            min = p->dat;
        }
    }
    return find(head, min); // надеюсь поиск по ключу вы сможете реализовать
}
 
list *p1 = find_max(head);
list *p2 = find_min(head);
 
void *swap(p1, p2) {
    int tmp = p1->dat;
    p1->dat = p2->dat;
    p2->dat = tmp;
}
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
11.09.2013, 07:43     Задание на работу со односвязными списками #3
Кликните здесь для просмотра всего текста
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
165
166
167
168
169
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
 
struct list             // определение структурного типа list
{   int dat;            // данные
    struct list *next;  // указатель на следующий эл-т списка
};
 
typedef list *P_list;   // определение указателя на тип list
 
void show(P_list head); // вывод списка
void find_max_min(P_list head, P_list &pmax, P_list &pmin); // поиск в списке элементов с max и min
P_list find_prev(P_list head, P_list p); // поиск в списке элементов, стоящих перед элементами с max и min
void swap(P_list pmax, P_list pmin); // замена значений в элементах с max и min
void swap(P_list &head, P_list pmax, P_list pmin); // перестановка в списке элементов с max и min
void delete_list(P_list &head); // удаление списка
 
int main()
{   
    int N, i;        // N-количество элементов в списке
 
    P_list pb;      // указатель на начало списка
    P_list pt;      // указатель на текущий элемент списка
 
    time_t t;
    srand (time(&t));   // инициировать датчик случ. чисел
    cout << " N = ";  // ввести размер списка (с клавиатуры)
    cin >> N;
    //_____________________ Создание списка
    // создать первый элемент
    pb = new list;       // выделить память
    pb ->dat = rand()%100;   // записать данные
    pt = pb;      // установить текущий указатель на начало
    for (i = 1; i < N; i++)   // в цикле создать список
    {
        pt ->next = new list;     // очередной элемент (выделить память)
        pt = pt ->next;           //текущий указатель-на вновь созданный элемент
        pt ->dat = rand() % 100;  // записать данные 
    }                            // создание списка завершено
    pt ->next = NULL;            // записать признак конца списка
    //_______________________ печать списка в 10 колонок
    
    show(pb);
 
    P_list pmax = NULL; 
    P_list pmin = NULL;
    
    find_max_min(pb, pmax, pmin);
    swap(pmax, pmin);
 
    show(pb);
    
    find_max_min(pb, pmax, pmin);
    swap(pb, pmax, pmin);
 
    show(pb);
 
    delete_list(pb);
    
    return 0;
}
 
void show(P_list head)
{
    P_list pt;
    int i;
    cout << endl;
    for (pt = head, i = 1; pt != NULL ;i++)
    {
        cout << pt->dat; // печать информационного поля списка
        pt = pt ->next;      //перемещение указателя на следующий элемент
        if (i % 10 == 0) cout << endl;       // форматирование (в 10 колонок)
        else cout << "\t";
    }
}
 
void find_max_min(P_list head, P_list &pmax, P_list &pmin)
{
    pmax = pmin = head;
    int max, min;
    max = min = head ->dat;
    
    for (list *p = head ->next; p; p = p ->next) 
    {
        if (p ->dat > max)
        {
             max = p ->dat;
             pmax = p;
        }
        if (p->dat < min)
        {
             min = p ->dat;
             pmin = p;
        }
    }
    
}
 
void swap(P_list pmax, P_list pmin) 
{
    int tmp  = pmax ->dat;
    pmax ->dat = pmin ->dat;
    pmin ->dat = tmp;
}
 
P_list find_prev(P_list head, P_list p)
{
    if (p == head) return head;
    P_list pt;
    for (pt = head; pt ->next != p; pt = pt ->next);
        return pt;
}
 
void swap(P_list &head, P_list pmax, P_list pmin) 
{
    if (pmax == pmin) return;
    
    P_list prev_max = find_prev(head, pmax);
    P_list prev_min = find_prev(head, pmin);
    P_list temp;
 
    if (pmax != head && pmin != head)
    {
            prev_max ->next = pmin;
            prev_min ->next = pmax;
            temp = pmax ->next;
            pmax ->next = pmin ->next;
            pmin ->next = temp;
            return;
    }
    
    if (pmin == head)
    {
        temp = pmax;
        pmax = pmin;
        pmin = temp;
        temp = prev_max;
        prev_max = prev_min;
        prev_min = temp;
    }
    
    temp = pmax ->next;
    pmax ->next = pmin ->next;
    if (prev_min != pmax)
    {
        pmin ->next = temp;
        prev_min ->next = pmax;
    }
    else
    {
        pmax ->next = pmin ->next;
        pmin ->next = pmax;
    }
    
    head = pmin;
}
 
void delete_list(P_list &head)
{
    P_list temp;
    while (head)
    {
        temp = head ->next;
        delete head;
        head = temp;
    }
}
DanShady
0 / 0 / 0
Регистрация: 14.04.2013
Сообщений: 18
11.09.2013, 22:29  [ТС]     Задание на работу со односвязными списками #4
alsav22, Спасибо за программу, работает прекрасно. Единственное когда все разобрал понял что в данном случае замену элементов списка можно упростить. ПОлучилось вот так
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
#include <iostream>
#include <time.h>
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
 
struct list             // определение структурного типа list
{   int dat;            // данные
    struct list *next;  // указатель на следующий эл-т списка
};
 
typedef list *P_list;   // определение указателя на тип list
 
void show(P_list head); // вывод списка
void find_max_min(P_list head, P_list &pmax, P_list &pmin); // поиск в списке элементов с max и min
void swap(int &a, int &b); // замена значений в элементах с max и min
void delete_list(P_list &head); // удаление списка
 
int main()
{   
    int N, i;        // N-количество элементов в списке
 
    P_list pb;      // указатель на начало списка
    P_list pt;      // указатель на текущий элемент списка
 
    time_t t;
    srand (time(&t));   // инициировать датчик случ. чисел
    cout << " N = ";  // ввести размер списка (с клавиатуры)
    cin >> N;
    if (N==0) exit(1); //если размер списка 0 то программа закрывается
    //_____________________ Создание списка
    // создать первый элемент
    pb = new list;       // выделить память
    pb ->dat = rand()%100;   // записать данные
    pt = pb;      // установить текущий указатель на начало
    for (i = 1; i < N; i++)   // в цикле создать список
    {
        pt ->next = new list;     // очередной элемент (выделить память)
        pt = pt ->next;           //текущий указатель-на вновь созданный элемент
        pt ->dat = rand() % 100;  // записать данные 
    }                            // создание списка завершено
    pt ->next = NULL;            // записать признак конца списка
    //_______________________ печать списка в 10 колонок
    
    show(pb); //функции шоу передать указатель на первый элемент списка
 
    P_list pmax = NULL; //создание переменных в стуктуре
    P_list pmin = NULL;
        
    find_max_min(pb, pmax, pmin);
    swap(pmax->dat, pmin->dat); //функция меняет элементы местами
 
    show(pb);
 
    delete_list(pb); //отчистить список
    system("PAUSE");
    return 0;
}
 
void show(P_list head)
{
    P_list pt;
    int i;
    cout << endl;
    for (pt = head, i = 1; pt != NULL ;i++)  //цикл будет длиться от первого элемента до посл. пока не появиться NULL 
    {
        cout << pt->dat; // печать информационного поля списка
        pt = pt ->next;      //перемещение указателя на следующий элемент
        if (i % 10 == 0) cout << endl;       // форматирование (в 10 колонок)
        else cout << "\t";
    }
}
 
void find_max_min(P_list head, P_list &pmax, P_list &pmin)
{
    pmax = pmin = head;
    int max, min;
    max = min = head ->dat;
    
    for (list *p = head ->next; p!=NULL; p = p ->next) //создаем указатель п , который указывает на 2 эл списка
    {
        if (p ->dat > max)
        {
             max = p ->dat;
             pmax = p; //указатель на промежуточное максимальное значение
        }
        if (p->dat < min)
        {
             min = p ->dat;
             pmin = p;
        }
    }
    
}
 
void swap(int &a, int &b)
{
    int tmp  = a;
    a = b;
    b = tmp;
}
 
void delete_list(P_list &head)
{
    P_list temp;
    while (head)
    {
        temp = head ->next;
        delete head;
        head = temp;
    }
}
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.09.2013, 01:53     Задание на работу со односвязными списками #5
Цитата Сообщение от DanShady Посмотреть сообщение
Единственное когда все разобрал понял что в данном случае замену элементов списка можно упростить. ПОлучилось вот так
Вы не поняли. Вы сделали то же, что делает, в моём коде, функция:
C++
1
void swap(P_list pmax, P_list pmin); // замена значений в элементах с max и min
Это не замена элементов списка. Это замена значений элементов. Не одно и то же. Это то, о чём пишет GoldenChild,
Цитата Сообщение от GoldenChild Посмотреть сообщение
Хотя конечно правильно менять сам элемент, а не его значение, тоесть заменять все ссылки. Но реализация более сложная,
Я, в своём коде, написал два варианта.
Yandex
Объявления
12.09.2013, 01:53     Задание на работу со односвязными списками
Ответ Создать тему
Опции темы

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