Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 26.04.2009, 22:00   #1
[MI_nor]
Пользователь
 
Регистрация: 03.11.2008
Сообщений: 94
По умолчанию Списки

Прошу помочь разобраться в формировании линейных списков, ибо в учебниках ничерта не понятно. Язык Си

Как я понял список это цепочка звеньев.

Допустим имеется структура:

Код:
typedef struct wr
	       { 
		 int num;
		 struct wr *next;
	       } ;
wr BUF[11]; //массив заполнененный разной ерундой
struct wr *next; - это указатель на следующее звено, но какой он имеет тип? wr?

Если мы обьявим к примеру:
Код:
struct wr *root;
т.е это будет указатель на первое звено в цепочке.

если наш массив BUF заполнен случайными числами например {1,6,3,2,7,9,3,0,3,5}
и нам нужно создать список, упорядоченный по убыванию, то найти первое звено в цепочке не составляет труда, но как присваивать root значение его индекса? root->next=BUF[i]?

И допустим мы имеем в руте начало списка, необходимо ведь чтобы каждое звено имело указатель на следующее, но ведь массив мы не отсортируем, тогда как ?
[MI_nor] вне форума Ответить с цитированием
Старый 26.04.2009, 22:17   #2
pu4koff
Старожил
 
Аватар для pu4koff
 
Регистрация: 22.05.2007
Сообщений: 9,520
По умолчанию

Цитата:
Сообщение от [MI_nor] Посмотреть сообщение
struct wr *next; - это указатель на следующее звено, но какой он имеет тип? wr?
У Вас же написано, что это указатель на структуру wr.
И причем здесь массивы вообще? Представьте очередь в больнице. Вы не знаете кто 5-й, кто 6-й. Знаете только кто перед Вами и всё. Тут та же история. Чтобы определить кто от вас пятый, вы спрашиваете у своего соседа: "кто четвертый?" Тот у своего соседа уже спросит: "кто третий?" и т.д. и к Вам вернется потом так же по цепочке ответ кто всёже пятый.
Потом, допустим, вашему соседу срочно на работу приспичило и он ушел из очереди. Вы просто меняете указатель next на его соседа и всё. Вообще списки не предназначены для обращения по индексу.
ЗЫ. Для сортировки больше двусвязный список подходит, т.к. там указатели в оба направления имеются и перемещение элементов списка проще будет
pu4koff вне форума Ответить с цитированием
Старый 26.04.2009, 22:26   #3
[MI_nor]
Пользователь
 
Регистрация: 03.11.2008
Сообщений: 94
По умолчанию

Хорошо, но если сосед ушел и не сказал кто был перед ним?) И стоим мы в очереди не строго в линию первый, второй и.т.д, а в куче.

Или представим другой вариант. Пришла толпа в больницу. Как обьяснить одному человеку что он первый, а вот тот человек за ним стоит, тому что этот человек перед ним а вот тот что вдалеке после него и т д. Т.е в самой программе как это указывается? какими функциями?

Последний раз редактировалось [MI_nor]; 26.04.2009 в 22:37.
[MI_nor] вне форума Ответить с цитированием
Старый 26.04.2009, 22:38   #4
pu4koff
Старожил
 
Аватар для pu4koff
 
Регистрация: 22.05.2007
Сообщений: 9,520
По умолчанию

Цитата:
Сообщение от [MI_nor] Посмотреть сообщение
Хорошо, но если сосед ушел и не сказал кто был перед ним?)
Значит Вы потерялись из списка и будете весь день ждать своей очереди, но указатель на вас потерялся и потому очередь до вас не дойдет
Цитата:
Сообщение от [MI_nor] Посмотреть сообщение
И стоим мы в очереди не строго в линию первый, второй и.т.д, а в куче.
Ну и элементы списка в памяти не в одном месте располягаются
pu4koff вне форума Ответить с цитированием
Старый 26.04.2009, 22:41   #5
pu4koff
Старожил
 
Аватар для pu4koff
 
Регистрация: 22.05.2007
Сообщений: 9,520
По умолчанию

Цитата:
Сообщение от [MI_nor] Посмотреть сообщение
Или представим другой вариант. Пришла толпа в больницу. Как обьяснить одному человеку что он первый, а вот тот человек за ним стоит, тому что этот человек перед ним а вот тот что вдалеке после него и т д. Т.е в самой программе как это указывается? какими функциями?
У Вас распараллеленное приложение, которое исполняется на многопроцессорной системе, что может такое произойти? Иначе выполнение идёт последовательно и такой ситуации не будет. Пришел первый человек, смотрит никого нет в очереди, значит он первый.
В программе что-то вроде:
Код:
if (root == NULL)
  root = new_item;
где root - указатель на первый элемент, а new_item - "пришедший человек"
pu4koff вне форума Ответить с цитированием
Старый 26.04.2009, 22:48   #6
[MI_nor]
Пользователь
 
Регистрация: 03.11.2008
Сообщений: 94
По умолчанию

хм, иначе говоря если к примеру у этих больных есть номерные карточки то приходит человек видит очередь, спрашивает у последнего его номер, если он меньше дает по морде и залазит на его место, а другой встает за ним, и.т.д ???
[MI_nor] вне форума Ответить с цитированием
Старый 26.04.2009, 22:51   #7
pu4koff
Старожил
 
Аватар для pu4koff
 
Регистрация: 22.05.2007
Сообщений: 9,520
По умолчанию

Цитата:
Сообщение от [MI_nor] Посмотреть сообщение
хм, иначе говоря если к примеру у этих больных есть номерные карточки то приходит человек видит очередь, спрашивает у последнего его номер, если он меньше дает по морде и залазит на его место, а другой встает за ним, и.т.д ???
Ну если это описана сортировка, то да. При обычном заполнении никаких проверок не требуется, кроме проверки на пустоту списка. Так же удобно хранить указатель не только на первый элемент, но и на последний элемент, чтобы при заполнении списка каждый раз от первого по цепочке не пробегать в поиска последнего
pu4koff вне форума Ответить с цитированием
Старый 26.04.2009, 23:02   #8
[MI_nor]
Пользователь
 
Регистрация: 03.11.2008
Сообщений: 94
По умолчанию

Хм, появился еще аопрос. Пытаюсь сортировать односвязный список:

Код:
void  sort (struct wr *start, int quant)
{
int i,j;
struct wr* kino;
struct wr* tmp=NULL;
tmp=(struct wr *)malloc(sizeof(struct wr));
kino=start; 
for (i=0; i<quant; i++)
	for (j=0; j<quant-i; j++)
	  {
		if ((kino->next)->time>kino->time)
		  {
			tmp=kino;
			kino->next=(kino->next)->next; 
			kino=kino->next;
			kino->next=tmp;
		  }
	  }

}
Но каждый раз выходит что не каждый элем списка имеет связи с отальными. Как отсортировать список?

Последний раз редактировалось [MI_nor]; 27.04.2009 в 05:12.
[MI_nor] вне форума Ответить с цитированием
Старый 27.04.2009, 06:56   #9
Nomlpppp
Пользователь
 
Регистрация: 26.02.2009
Сообщений: 51
По умолчанию

http://www.programmersforum.ru/showthread.php?t=43720Смотри здесь

Последний раз редактировалось Nomlpppp; 27.04.2009 в 06:58.
Nomlpppp вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
с++ списки Blizzz Общие вопросы C/C++ 3 04.12.2008 21:19
Списки Bremlin Microsoft Office Excel 10 04.11.2008 15:13
списки Влдислаав3911 Паскаль, Turbo Pascal, PascalABC.NET 5 10.05.2008 17:35
Списки AVer Паскаль, Turbo Pascal, PascalABC.NET 6 06.12.2006 23:05