Списки

[[MI_nor]]

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

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

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

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]?

И допустим мы имеем в руте начало списка, необходимо ведь чтобы каждое звено имело указатель на следующее, но ведь массив мы не отсортируем, тогда как ?

[pu4koff]

Сообщение от [MI_nor]

struct wr *next; - это указатель на следующее звено, но какой он имеет тип? wr?

У Вас же написано, что это указатель на структуру wr.
И причем здесь массивы вообще? Представьте очередь в больнице. Вы не знаете кто 5-й, кто 6-й. Знаете только кто перед Вами и всё. Тут та же история. Чтобы определить кто от вас пятый, вы спрашиваете у своего соседа: "кто четвертый?" Тот у своего соседа уже спросит: "кто третий?" и т.д. и к Вам вернется потом так же по цепочке ответ кто всёже пятый.
Потом, допустим, вашему соседу срочно на работу приспичило и он ушел из очереди. Вы просто меняете указатель next на его соседа и всё. Вообще списки не предназначены для обращения по индексу.
ЗЫ. Для сортировки больше двусвязный список подходит, т.к. там указатели в оба направления имеются и перемещение элементов списка проще будет

[[MI_nor]]

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

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

[pu4koff]

Сообщение от [MI_nor]

Хорошо, но если сосед ушел и не сказал кто был перед ним?)

Значит Вы потерялись из списка и будете весь день ждать своей очереди, но указатель на вас потерялся и потому очередь до вас не дойдет

Сообщение от [MI_nor]

И стоим мы в очереди не строго в линию первый, второй и.т.д, а в куче.

Ну и элементы списка в памяти не в одном месте располягаются

[pu4koff]

Сообщение от [MI_nor]

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

У Вас распараллеленное приложение, которое исполняется на многопроцессорной системе, что может такое произойти? Иначе выполнение идёт последовательно и такой ситуации не будет. Пришел первый человек, смотрит никого нет в очереди, значит он первый.
В программе что-то вроде:

if (root == NULL)
  root = new_item;

где root - указатель на первый элемент, а new_item - "пришедший человек"

[[MI_nor]]

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

[pu4koff]

Сообщение от [MI_nor]

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

Ну если это описана сортировка, то да. При обычном заполнении никаких проверок не требуется, кроме проверки на пустоту списка. Так же удобно хранить указатель не только на первый элемент, но и на последний элемент, чтобы при заполнении списка каждый раз от первого по цепочке не пробегать в поиска последнего

[[MI_nor]]

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

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;
		  }
	  }

}

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

[Nomlpppp]

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