Линейные списки на Си, Сортировка и подсчет по условию Опции

[Gera]

Для заданного варианта представления линейного списка составить и отладить программу, которая выполняет по выбору: первоначальное формирование списка, включение элемента в список, удаление элемента из списка, сортировку списка по заданному полю, печать списка и решение дополнительной задачи. Двунаправленный кольцевой список. Упорядочить список поездов в порядке убывания их номеров. Подсчитать количество поездов, отправляющихся до заданного пункта назначения. Список содержит сведения об отправлении поездов дальнего следования на железнодорожном вокзале (номер поезда, станция назначения, время отправления).
Вот текст получившейся у меня программы:

#include <stdio.h>		  /* podkluchenie bibliotek*/
#include <string.h>
#include <conio.h>
#include <alloc.h>
#include <dos.h>
#define LIST struct list
LIST
 {
	int Nomer;								/*nomer poezda*/
	char Stanc[25];		   /*stanciya naznacheniya*/
	float Vremya;			 /*vremya otpravleniya*/
	LIST *next, *pred;			  /*ykazateli na sledyushii i predudyshii elementu*/
 };
LIST *ptr_Beg;
void Insert_List(char Stc[],int Nmr,float Vrm)			   /*dobavlenie novogo elementa*/
 {
	LIST *ptrX,*ptr_Ls;
	ptrX = (LIST *) malloc(sizeof(LIST));
	strcpy(ptrX->Stanc,Stc);
	ptrX->Nomer=Nmr;
	ptrX->Vremya=Vrm;
	ptr_Ls=ptr_Beg;
	while (ptr_Ls->next != ptr_Beg)
	 {
		if(ptr_Ls->next->Nomer<Nmr)
		break;
		ptr_Ls=ptr_Ls->next;
	 }
	ptrX->next=ptr_Ls->next;
	ptrX->pred=ptr_Ls;
	ptr_Ls->next->pred=ptrX;
	ptr_Ls->next=ptrX;
	return;
 };
void Del_List (int Nmr) 			/*ydalenie elementa*/
 {
	LIST *ptr,*ptr_Ls;
	ptr=ptr_Beg->next;
	ptr_Ls=ptr_Beg;
	while (ptr != ptr_Beg) {
		if(ptr->Nomer >= Nmr)
		ptr_Ls->next=ptr->next;
		ptr_Ls=ptr;
		 ptr=ptr->next;
		}
	return;
 };
void Change(LIST *a,LIST *b) 			/*obmen mestami elementov*/
 {
	a->next=b->next;
	a->pred->next=b;
	b->next->pred=a;
	b->next=a;
	b->pred=a->pred;
	a->pred=b;
 };
void Sortirovka()				/*sortirovka spiska po nomery poezdov*/
 {
	LIST *ptr,*ptr_Ls;
	ptr= (LIST *) malloc(sizeof(LIST));
	ptr_Ls= (LIST *) malloc(sizeof(LIST));
	ptr_Ls=ptr_Beg->next;
	while (ptr_Ls != ptr_Beg) {
		ptr=ptr_Beg;
		while (ptr->next->next != ptr_Beg) {
			if(ptr->next->Nomer < ptr->next->next->Nomer)
				Change(ptr->next,ptr->next->next);
			ptr=ptr->next;
			}
		ptr_Ls=ptr_Ls->next;
	}
 return;
 };
void Print_List()								  /*pechat spiska*/
 {
	LIST *ptr_Ls;
	ptr_Ls=ptr_Beg;
	while (ptr_Ls->next != ptr_Beg) {
		ptr_Ls=ptr_Ls->next;
		printf("   %-15s%-12d%-4.2f\n", ptr_Ls->Stanc, ptr_Ls->Nomer, ptr_Ls->Vremya);
	 }
	return;
 };
void Pynkt_List (char *Stc)	 	/*podschet kolichestva poezdov do opredelennogo goroda*/
 {
	int Count=0;
	LIST *ptr_Ls;
	ptr_Ls=ptr_Beg->next;
	while (ptr_Ls != ptr_Beg) {
		if(ptr_Ls->Stanc == Stc)
		 Count++;
		 ptr_Ls=ptr_Ls->next;
	 }
	return;
 };
main()					  /*osnovnaya programma*/
 {
	char c,Stc[25];
	int Count,Nmr;
	float Vrm;
	LIST *ptr,*ptrX,*ptr_Ls;
 /*inicializaciya spiska*/
	ptr_Beg = (LIST *)malloc(sizeof(LIST));
	clrscr();
	do {					  /*vuvod na ekran menu*/
	 window(41,1,80,8);
	 gotoxy(1,1);puts("1.Formirovanie spiska");
	 gotoxy(1,2);puts("2.Vkluchenie elementa v spisok");
	 gotoxy(1,3);puts("3.Ydalenie elementa iz spiska");
	 gotoxy(1,4);puts("4.Nahojdenie kol-va poezdov do pynkta");
	 gotoxy(1,5);puts("5.Pechat' spiska");
	 gotoxy(1,6);puts("6.Vuhod");
		c = getch();			  /*ojidanie najatiya klavishi*/
		window(1,1,40,25);
		clrscr();
		switch© {			 /*vubor punkta menu*/
			case '1': {		   /*formirovanie spiska*/
				ptr=ptr_Beg;
				while(1) {
					printf("Vvedite pynkt naznacheniya: ");
					scanf("%s",Stc);
					if(strcmp(Stc,"*")==0) {
						ptr->next = ptr_Beg; break;
					 }
					printf("Vvedite nomer poezda: ");
					scanf("%d",&Nmr);
					printf("Vvedite vremya otpravleniya: ");
					scanf("%f",&Vrm);
					ptrX=(LIST *) malloc(sizeof(LIST));
					strcpy(ptrX->Stanc,Stc);
					ptrX->Nomer=Nmr;
					ptrX->Vremya=Vrm;
					ptr->next=ptrX;
					ptr=ptrX;
				 }
				Sortirovka();
				break;
			 }
			case '2': {
				printf("Vvedite pynkt nazn-ya, nomer i vremya: \n");
				scanf("%s%d%f",Stc,&Nmr,&Vrm);
				Insert_List(Stc,Nmr,Vrm);
				break;
			 }
			case '3': {		   /*ydalenie elementa iz spiska*/
				Del_List(300); break;
			 }
			case '4': {
				printf("Vvedite pynkt naznacheniya");
				scanf("%s",Stc);
				Pynkt_List(Stc);
				printf("Kol-vo poezdov do pynkta nazn-ya = %d\n",Count);
				break;
			 }
			case '5': {		   /*pechat' vseh elementov spiska*/
				printf("Pynkt nazn-ya Nomer p-da Vremya otpr-ya \n");
				Print_List();
				break;
			 }
			case '6': {		   /*vuhod*/
				break;
			 }
		 }
	 } while(c>'0' && c<'6');
 }

Проблем у меня несколько: формируется, печатается и добавляется все вроде нормально, а вот удаляется по заданному условию по очень странному алгоритму: когда я первый раз вызываю функцию удаления, то удаляются все элементы, кроме самого близкого к 300 (см.условие), а потом ещё раз вызываю функцию удаления и тот элемент тоже удаляется; что касается сортировки и поиска с подсчетом по условию, тут вообще беда - ничего не выходит.
Пожалуйста, помогите разобраться с этими проблемами, я уже столько раз пыталась что-то переделать...

[Алена]

Что-то у тебя накручено с программой... Я бы сделала вот так:
 LIST.CPP ( 4.92 килобайт ) Кол-во скачиваний: 344


Что неясно - спрашивай...

[Gera]

Большое спасибо, прямо спасла меня Алена. Программа может и составлена как-то не очень была, просто я делала по аналогии с примером, где был разобран однонаправленный линейный список, а там все оформлено так, как от нас требуют. Вся гадость в том, что надо, чтобы программа не просто работала, а был использован алгоритм, который симпатичен именно нашему преподавателю.
Вот только с удалением я не очень поняла. У меня не получается удалять; там как бы рассматривается если вдруг список нулевой? Это для того чтобы удалялся и первый элемент тоже?

[Алена]

У меня не получается удалять;

То есть? Моя программа не удаляет?

там как бы рассматривается если вдруг список нулевой? Это для того чтобы удалялся и первый элемент тоже?

Естественно... Список (любой) может содержать элементы, а может их и не содержать. Поэтому если в списке придется удалить первый элемент (и в итоге получить пустой список) - это тоже должно быть доступно.

[Gera]

То есть? Моя программа не удаляет?

Да, Ален, все чудесно кроме удаления... На вызов 3 пункта никакой реакции, ну т.е. я потом печатала список, чтобы проверить, а там нет изменений.

[Алена]

Странно. У меня удаляет. Смотри:
Запуск программы - выбираем 1 для инициализации... вот этими данными:

жму Enter. Все, список инициализирован... Проверяем:

Теперь 3 - для удаления (если есть) данных, подходящих под условие. Экран пустой, все верно... Проверяем (жмем 5):


Ты какие данные вводишь?

[Gera]

Ой, Алена, прости, да у тебя все правильно, просто я не заметила, что там условие равно 300, я то подразумевала условие: если >300, то удалять, так вот если в тот алгоритм вместо равно поставить в условие >=, т.е.

 void Del_List(int n) {

  LIST *p, *p2;

  if(ptr_Beg -> Nomer >= n) {
	p = ptr_Beg;
	if(ptr_Beg -> next == ptr_Beg) {
	  free(ptr_Beg); ptr_Beg = NULL; return;
	}

	for(; p -> next != ptr_Beg; p = p -> next);
	p2 = ptr_Beg;
	ptr_Beg = p2 -> next;
	p -> next = ptr_Beg;
	free(p2);
	return;
  }

  p = ptr_Beg;
  do {

	if(p -> next -> Nomer >= n) {
	  p2 = p -> next;
	  p -> next = p2 -> next;
	  free(p2); return;
	}
	p = p -> next;

  } while(p != ptr_Beg);

}

то он жутко возмущается. Как тогда поступить?

[Алена]

он жутко возмущается

Каким образом? У меня все нормально и в случае ">=" вместо "==". Только что проверила.

[Gera]

Мне прямо неудобно, я уже замучала наверное своей тупостью, но у меня вопрос он у тебя сразу все удаляет, которые больше 300. Вот попробуй набрать такие данные, где не один, а сразу 2 или 3 не подходят, вот он их удаляет как-то постепенно.

[Алена]

А, вот ты о чем... Тогда замени старые функции на новые:

void Del_List(int n) {

  LIST *p, *p2;
  int found;

  do {
    found = 0;

    if(ptr_Beg -> Nomer >= n) {
      found = 1;
      p = ptr_Beg;
      if(ptr_Beg -> next == ptr_Beg) {
        free(ptr_Beg); ptr_Beg = NULL; return;
      }

      for(; p -> next != ptr_Beg; p = p -> next);
      p2 = ptr_Beg;
      ptr_Beg = p2 -> next;
      p -> next = ptr_Beg;
      free(p2); continue;
    }

    p = ptr_Beg;
    do {

      if(p -> next -> Nomer >= n) {
        found = 1;

        p2 = p -> next;
        p -> next = p2 -> next;
        free(p2); // return;
      }
      else p = p -> next;

    } while(p != ptr_Beg);

  } while(found);

}

и

void Print_List()
{
    LIST *ptr_Ls;

    if(!ptr_Beg) {
      printf("<empty list>\n");
      return;
    }

    ptr_Ls = ptr_Beg;
    do {

      printf("   %-15s%-12d%-4.2f\n",
        ptr_Ls->Stanc, ptr_Ls->Nomer, ptr_Ls->Vremya);
      ptr_Ls = ptr_Ls -> next;

    } while(ptr_Ls != ptr_Beg);
};

(чтобы не выбрасывало дамп памяти - пусть лучше дает сообщение, что список пуст)

[Gera]

Еще раз спасибо, теперь вроде все работает, надеюсь, у меня примут задачку с таким оформлением.

[Gera]

У меня новая головная боль; оказывается, надо было добавлять не в отсортированный список по нужному месту, а в любое место списка. Таким образом, сортировка является отдельной седьмой функцией в программе, а в добавлении надо учесть, куда вставлять: до элемента или после по его порядковому номеру, т.е., например, хочу добавить перед таким-то элементом, и в уже распечатанном списке считаю какой он и выполняю добавление.

 LIST *ptr_Beg;
void Insert_List(char Stc[],int Nmr,float Vrm)			   /*dobavlenie novogo elementa*/
{
	LIST *ptrX,*ptr_Ls;
	int k,n;
	ptrX = (LIST *) malloc(sizeof(LIST));
	strcpy(ptrX->Stanc,Stc);
	ptrX->Nomer=Nmr;
	ptrX->Vremya=Vrm;
	ptr_Ls=ptr_Beg;
	while (ptr_Ls->next != ptr_Beg)
	 {
		if(k==n)
		break;
		k++;
		ptr_Ls=ptr_Ls->next;
	 }
	ptrX->next=ptr_Ls->next;
	ptrX->pred=ptr_Ls;
	ptr_Ls->next->pred=ptrX;
	ptr_Ls->next=ptrX;
	return;
};
 ... 
case '2': {
				printf("Vvedite nomer elementa ");
				scanf("%d",n)
				printf("Vvedite pynkt nazn-ya, nomer i vremya: \n");
				scanf("%s%d%f",Stc,&Nmr,&Vrm);
				Insert_List(Stc,Nmr,Vrm);
				break;
			 }

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

[volvo]

Gera, смотри:
 LIST_2.CPP ( 5.58 килобайт ) Кол-во скачиваний: 390


Что изменилось?

1. Добавлено меню (шестым пунктом) сортировка, выход перенесен на №7
2. Подкорректирована функция Insert_List, теперь она отражает тот факт, что список двухсвязный, то есть заполняется и поле prev.
3. Как вызывать вставку перед/после определенного элемента. Я сделал так: просишь ввести число, идентифицирующее позицию, в которой стоит элемент, относительно которого будет производиться вставка. Причем, если введено число отрицательное - то элемент будет вставлен перед указанным, а если положительное - то после него. То есть, если у меня уже есть список:

moscow 123 12.05
moscow 114 14.10

, и я введу "-2" или "1" (число с плюсом, то есть положительное), то элемент добавится перед вторым (соответственно, после первого):

moscow 123 12.05
new_elem 345 12.20
moscow 114 14.10

, а если "2" - то после второго:

moscow 123 12.05
moscow 114 14.10
new_elem 345 12.20

Детально не тестировал, только на списке из трех элементов пару раз прогнал - вроде работает... Будут замечены баги - говори, исправим...

[Gera]

Спасибо, volvo, все гениальное, оказывается, просто, но до меня почему-то не доходит все время. Надеюсь, теперь примут задачу.