#c #linked-list
#c #связанный список
Вопрос:
Сегодня я пытался создать программу, которая вводила бы 15 случайных значений (от 100 до 120) в связанный список. Эта часть работает как шарм. Затем я пошел, чтобы найти максимальное и минимальное значения из этого списка и найти среднее значение.
Я хочу переместить все значения, превышающие среднее, в конец этого списка, который я пытался реализовать с помощью функции prebaci. Функция unos помещает все элементы в список, а функция unosK помещает все элементы в конец списка. Программа переходит в бесконечный цикл, и я не знаю почему. Можете ли вы помочь мне переместить все значения, превышающие среднее (107), в конец списка? Мой КОД:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct lista* Pozicija;
struct lista {
int el;
Pozicija next;
};
void unos(Pozicija P, int el);//input front
void ispis(Pozicija P);//print
int mini(Pozicija P);//find min
int maxi(Pozicija P);//find max
void prebaci(Pozicija P,int x);//function for transfering at the end
void unosK(Pozicija P,int x);//input end
int main() {
srand(time(0));
struct lista L;
L.next = NULL;
int min,max, i,j;
int prvi[21], drugi[15];
int avg;
for (i = 0;i < 21;i ) {
prvi[i] = i 100;
printf("%d ", prvi[i]);
}
for (i = 0;i < 15;i ) {
int temp = prvi[i];
int random = rand() % 15;
prvi[i] = prvi[random];
prvi[random] = temp;
}
printf("nn");
for (i = 0;i < 15;i ) {
//printf("%d ",prvi[i]);
unos(amp;L, prvi[i]);
}
printf("Ispisn");
ispis(L.next);
printf("nn");
min = mini(L.next);
printf("Minqi:%dn", min);
printf("nn");
max = maxi(L.next);
printf("Miaxi:%dn", max);
printf("nn");
avg = (min max) / 2;
printf("avg:%dn", avg);
printf("nn");
printf("Prebacaj:n");
prebaci(amp;L, avg);
ispis(L.next);
}
void unos(Pozicija P, int el) {
Pozicija q;
q = (Pozicija)malloc(sizeof(struct lista));
q->el = el;
q->next = P->next;
P->next = q;
}
void ispis(Pozicija P) {
while (P != NULL) {
printf("%d ", P->el);
P = P->next;
}
}
int mini(Pozicija P) {
int min;
min = INT_MAX;
while (P != NULL) {
if (min > P->el) {
min = P->el;
}
P = P->next;
}
return min;
}
int maxi(Pozicija P) {
int max;
max = INT_MIN;
while (P != NULL) {
if (max< P->el) {
max = P->el;
}
P = P->next;
}
return max;
}
void prebaci(Pozicija P,int x) {
P = P->next;
Pozicija t;
t = P;
while (t != NULL) {
if (t->el > x)
{
unosK(P, t->el);
t = t->next;
}
else if (t->el <= x) {
unos(P, t->el);
t = t->next;
}
}
}
void unosK(Pozicija P,int x) {
Pozicija q=NULL;
q = (Pozicija)malloc(sizeof(struct lista));
q->el = x;
while (P->next != NULL)
P = P->next;
q->next = P->next;
P->next = q;
} Комментарии:
1. Если вы выполняете итерацию по связанному списку и неоднократно добавляете элементы в конец этого списка, бесконечный цикл становится своего рода неизбежным.
2. Вы вычисляете среднее значение минимального и максимального значений, а не среднее значение по всему списку. Это намеренно?
3. @Jack Jones Почему в цикле используется число 15 вместо числа 21 для (i = 0;i < 15;i ) { //printf(«%d «,prvi[i]); unos(amp;L, prvi[i]); } ?
4. @Джек Джонс Плохая идея иметь фиктивный узел (первый узел) в списке.
5. Вы могли бы избежать бесконечного цикла, переместив элементы, превышающие среднее значение, в новый список, а затем добавив новый список в конец старого списка.
Ответ №1:
Вот рабочая, выпадающая замена исходной prebaci функции. Он по-прежнему имеет фиктивный узел в начале списка, но не выделяет никаких новых элементов.
Вместо того, чтобы вызывать unos и unosK выделять новые элементы, он манипулирует указателями в исходном списке, чтобы переместить элементы, превышающие среднее значение, в конец списка.
Сначала он перемещает элементы, превышающие среднее значение, из исходного списка в новый, изначально пустой список ( q ), а затем связывает последний элемент исходного списка с первым элементом нового списка, так что все элементы, превышающие среднее значение, теперь находятся в конце исходного списка.
Новый список ( q ) был реализован как указатель вместо фиктивного узла.
Функция использует указатели на указатели ( pp и pq ) для управления ссылками в исходном списке и новом списке.
void prebaci(Pozicija P,int x) {
Pozicija *pp = amp;P->next; /* pointer to link in original list */
Pozicija q = NULL; /* new list for elements greater than average */
Pozicija *pq = amp;q; /* pointer to end link of new list */
while (*pp != NULL) {
if ((*pp)->el > x) {
/* move element from original list to end of new list */
*pq = *pp; /* end of new list points to moved element */
*pp = (*pp)->next; /* remove element from original list */
pq = amp;(*pq)->next; /* update pointer to end link of new list */
}
else {
/* do not move this element */
pp = amp;(*pp)->next; /* advance to next link in original list */
}
}
*pq = NULL; /* terminate the new list */
*pp = q; /* append the new list to the end of the original list */
}
Комментарии:
1. Этот код создает среднее значение в качестве первого элемента. Я думаю, вы меня неправильно поняли, сэр. Спасибо за ваше время, я действительно ценю это, но я думал о том, чтобы моя программа перемещала только большие значения в конце списка. Таким образом, в списке должны быть только значения, превышающие среднее значение (107).
2. @JackJones Код разделяет список на две (неравные) половины таким образом, что все элементы, меньшие или равные среднему значению, попадают в первую половину, а все элементы, превышающие среднее значение, попадают во вторую половину.
3. @JackJones Например, если среднее значение равно 107, то список 100 103 102 113 112 108 114 109 105 106 104 101 111 110 107 будет изменен на 100 103 102 105 106 104 101 107 113 112 108 114 109 111 110. Все, что больше 107, было перемещено в конец списка.
4. вот и все. Я не думал об этом, ха-ха, я работаю над множеством других проектов, поэтому мой мозг был перегружен, и я потерял концентрацию. Спасибо за ваше время и помощь!