Однонаправленный список Опции

[Олежечег(быв. Олежик)]

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

Для каждого из вариантов необходимо разработать следующие функции:

1.Создание пустой структуры данных
2.Добавление нового элемента
для списка - в начало, в конец, после элемента с заданным номером (ключом).
для дерева - к указанной вершине дерева
3.Вывод на экран дисплея
4.Удаление элемента
для списка - из начала, из конца, с заданным номером (ключом).
5.Упорядочивание элементов структуры
6.Запись в файл
7.Уничтожение структуры данных
8.Чтение данных из файла


С удовольствием сам бы написал..
знаю списки на Паскале немного....

учил по FAQ..

а теперь реализация на си++
хочу разобраться.

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

Сообщение отредактировано: Олежечег(быв. Олежик) - 12.12.2007 1:54

[Тёмный Эльф]

реализация на си++
вы бы не могли найти помощь в создании однонаправленных списков..
именно шаблоны создания?

Вот на этом сайте хорошо изложено про создание списков на C++
Динамические структуры данных. C++

[Олежечег(быв. Олежик)]

Вчера (слава богу) сделали с знакомой списки..Только она делала себе....
А у неё была тема двусвязный список!!

#include <iostream>
#include <fstream>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;


struct Std
{
   char  Surname[25];
   char Name[15];
   int  Gryppa;
   int  Fakyltet;   
		   
};
   
struct Student
{
   Std Info;
   Student*  Next;
   Student*  Pred;	  
	   
};

   Student* Head=0;
   Student* Tail=0; 
   char Filename[80];
  
// Выделяет память для 1 элемента списка и возвращает указатель на этот участок
Student* Pyst_struct()
{
   Student* A=new(Student);
   (*A).Next=0;
   (*A).Pred=0;
   return (A);	   
}


// Проверка правильности ввода операции
bool Proverka_Koda(int a, int b, int c)
{
   if ((c>=a) && (c<=b))
	  return true; // Введен верный код
   else
	  return false;   //   Введен неверный код		
}


// Проверкка корректности ввода данных
bool Korrect(char *st)
{
   int i;
   bool otv;
   otv=true;
   i=0;
   // Выясняем, входят ли какие-нибудь символы кроме цифр
   while ((otv==true) && (st[i]!='\0'))
   {
	  if ((st[i]<48) || (st[i]>57)) 
		 otv=false; 
	  i++;
	}
   return otv;   
}


void Zapolnenie (Student* A)
{
   char st[5];
   cout<<endl;
   cout<<"ZAPOLNENIE ELEMENTA SPISKA:"<<endl;;
   cout<<"\nSurname of student is ";
   cin>>(*A).Info.Surname;
   cout<<"\nName of student is ";
   cin>>(*A).Info.Name;
   do
   {
	  cout<<"\nGroup is ";
	  cin>>st;
   }
   while (Korrect(st)==false);
   (*A).Info.Gryppa=atoi(st); 
   do
   {
	  cout<<"\nFakulty is ";
	  cin>>st;
   }
   while (Korrect(st)==false);
   (*A).Info.Fakyltet=atoi(st);  
}

// Функция возвращает указатель на элемент списка с заданным номером (ключом)
Student* Nelem(int k)
{
   int i;
   Student* A;
   A=Head;
   i=1;
   while (i!=k)
   {
	  A=(*A).Next;
	  i++;	  
   } 
   return A;			 
}




void DoTaskOne(Student* A) // Вставка элемента в начало списка
{
   if (Head==0)
   {
	  Head=A;
	  Tail=A;
   }   
   else 
   {
	  (*Head).Pred=A;
	  (*A).Next=Head;
	  Head=A; 
   }	
}


// Подсчет количества элементов в списке
int Kol_vo()
{
   int i;
   Student* A;
   i=0;
   A=Head;
   while (A!=0)
   {
	  i++;	
	  A=(*A).Next;			
   }
   return i;
}


// Вставка элемента в конец списка
void DoTaskTwo(Student* A) 
{
   if (Tail==0)
   {
	  Tail=A;
	  Head=A;
   }   
   else
   {
	  (*Tail).Next=A;
	  (*A).Pred=Tail;
	  Tail=A;	
   }	   
}

// Вставка после элемента с заданным номером
void DoTaskThree(Student* A) 
{
   Student* B;
   Student* Posr;
   int m;
   cout<<"Enter number of an element after which want to insert the given element: ";
   // Введите номер элемента, после которого вы хотите вставить данный элемент
   cin>>m;
   if ((Proverka_Koda(1,Kol_vo(),m)) && (Kol_vo!=0))
   {					  
	  B=Nelem(m); // Указатель на элемент, после которого требуется вставить наш элемент
	  if (B==Tail)
		 DoTaskTwo(A); // Вставка элемента в конец списка
	  else
	  {   
		 Posr=(*B).Next;
		 (*B).Next=A;
		 (*A).Pred=B;
		 (*A).Next=Posr; 
	  }   
   }
   else
	  cout<<"Number of operation is entered incorrectly!"<<endl;	   
}

// Удаление элемента из начала списка
void Del_begin()
{
   Student* A;
   if (Head!=0)
   {
	  if ((*Head).Next==0) // Если в спске один элемент
	  {
		 delete Head;
		 Head=0;  
		 Tail=0;				 
	  }
	  else
	  {
		 A=Head;
		 Head=(*Head).Next;
		 (*Head).Pred=0;
		 delete A; // Удаляем из памяти бывшую главу списка   
	  }
   }  
}

// Удаление элемента из конца списка

void Del_end()
{
   if (Head!=0) // Список пуст
   {
	  if ((*Head).Next==0) // Если в спске один элемент
	  {
		 delete Head;
		 Head=0;
		 Tail=0;
	  }
	  else
	  {
		 Student* A;
		 A=Tail;
		 Tail=(*Tail).Pred;
		 (*Tail).Next=0;
		 delete A; // Удаляем из памяти бывший коней списка   
	  }
   } 
}



// Удаление элемента с заданным номером (ключом)

void Del_klych()
{
	int n;
	char f[5];
	Student* A;
	cout<<"\nEnter number of an element which you want to delete  from the list: ";
	cin>>f;
	if (Korrect(f)==true)
	{
	   int n=atoi(f);
	   cout<<n;
	   if (Proverka_Koda(1,Kol_vo(),n)) // Если вы ввели номер элемента, который действительно пирсутствует в списке
	   {
		  A=Nelem(n); // Указатель на удаляемый элемент							 
		  if (A==Head)
			 Del_begin();
		  else
		  {
			 if (A==Tail)
				Del_end();  
			 else						   
			 {	  
				(*(*A).Pred).Next=(*A).Next;
				 delete A; // Удаляем из памяти 
			 }	
		  }
	   }
	   else
		  cout<<"Number of operation is entered incorrectly!"<<endl;  
	}
	else
	   cout<<"Number of operation is entered incorrectly!"<<endl; 
}

// Добавить запись
void Add(Student* B)
{
   char Nomer;
   cout<<endl;
   cout <<"ADDITION OF AN ELEMENT: "<<endl;// Добавить запись
   cout <<"Where you wont to insert an element?"<<endl; // Куда вы хотите добавить элемент?
   cout<<"   (1)In the beginning of the spisok..."<<endl; // В начало списка
   cout<<"   (2)In the end of the spisok..."<<endl; // В конец списка
   cout<<"   (3)After an element with set number..."<<endl; // После элемента с заданным номером
   cout<<"Nomber of operation: "; // В конец списка
   cin>>Nomer;
   if (Proverka_Koda((int)'1', (int)'3',int(Nomer)))
   {
	  switch (Nomer)
	  {
		case('1'):
		  DoTaskOne(B);
		  break;
		case('2'):
		  DoTaskTwo(B);
		  break;
		case('3'):	   
		  DoTaskThree(B);			  
		  break;  
	  }  
   }
   else
	  cout<<"Number of operation is entered incorrectly!"<<endl;	
}

void Delete ()
{
   char Nomer;
   cout<<endl;
   cout <<"DELETE ELEMENT FROM SPISOK:"<<endl;
   cout <<"What element want to delete? "; // Какой элемент вы хотите удалить?
   cout<<"\n  (1) From the begining of spisok..."; // Начальный элемент списка
   cout<<"\n  (2) From the end of spisok...  "; //  Конечный элемент списка
   cout<<"\n  (3) Element with set number... "; // Элемент с заданным номером
   cout<<"\nNomber of operation:  ";   // Введите номер операции
   cin>>Nomer;
   if (Proverka_Koda((int)'1', (int)'3',int (Nomer)))
   {
	  switch (Nomer)
	  {
		 case('1'):
		   Del_begin();
		   break;
		 case('2'):
		   Del_end();
		   break;
		case('3'):
		   Del_klych();
		   break;   
	   }   
   }
   else
	  cout<<"Number of operation is entered incorrectly!"<<endl;	  
}



char Main_menu()
{
   char st; 
   cout<<endl;
   cout<<"VOZMOJNIE OPERACII:"<<endl; // Операции
   cout<<"  (1) Add new element in spisok..."<<endl;   // Добавить запись
   cout<<"  (2) Delite element from spisok..."<<endl;   // Удалить запись
   cout<<"  (3) Yporyadochivanie spiska..."<<endl;   // Упорядочить элементы структуры
   cout<<"  (5) Write to file... "<<endl;   // Прочитать данные в файл
   cout<<"  (6) Conclushion to the screen..."<<endl;  
   cout<<"  (7) End of work of the program... "<<endl;   // Конец работы
   do 
   {   
	  cout<<"Nomber of operation:  ";   // Введите номер операции
	  cin>>st;
   }
   while (Proverka_Koda((int)'1', (int)'7',(int)st)==false);
   return st;   
}


void Poryadok_Surname() // Упорядочевание списка по фамилиям
{
   bool flag;
   Student* A;
   Student* B;
   Student* Posr=new(Student);
   char* st1;
   char* st2;
   do 
   {	  
	  flag=false;
	  A=Head;
	  B=(*Head).Next;
	  while (A!=Tail)
	  {
		 st1=(*A).Info.Surname;
		 st2=(*B).Info.Surname;
		 int rez=strcmp(st1,st2);
		 if (rez>0)
		 {
			(*Posr).Info=(*A).Info;
			(*A).Info=(*B).Info;
			(*B).Info=(*Posr).Info;
			flag=true;
		 }
		 A=(*A).Next;
		 B=(*B).Next;	 
	  }
   }
   while (flag==true); 
   delete Posr;
   A=Head;
   B=(*Head).Next;
   if (A==0)
	  cout<<"Spisok pyst! Yporyadochivanie NEvjzmojno!";
   if (B==0)
	  cout<<"V spiske prisytstvyet vsego 1 element! Yporyadochivanie NE trebyetcya! ";  
}

void Poryadok_Gryppa() // Упорядочевание списка по группе
{
	bool flag;
	Student* A;
	Student* B;
	Student* Posr=new(Student);
	char* st1;
	char* st2;
	do
	{
	   flag=false;
	   A=Head;
	   B=(*Head).Next;
	   while (A!=Tail)
	   {
		  if ((*A).Info.Gryppa>(*B).Info.Gryppa)
		  {
			 (*Posr).Info=(*A).Info;
			 (*A).Info=(*B).Info;
			 (*B).Info=(*Posr).Info;
			 flag=true;	
		  }
		  A=(*A).Next;
		  B=(*B).Next;	 
	   }
	}  
	while (flag==true);
	delete Posr;
	A=Head;
	B=(*Head).Next;
	if (A==0)
	   cout<<"Spisok pyst! Yporyadochivanie NEvjzmojno!";
	if (B==0)
	   cout<<"V spiske prisytstvyet vsego 1 element! Yporyadochivanie NE trebyetcya! ";	
}

void Poryadok_Fakyltet() // Упорядочевание списка по факультету
{
   bool flag;
   Student* A;
   Student* B;
   Student* Posr=new(Student);
   char* st1;
   char* st2;
   do
   {
	  flag=false;
	  A=Head;
	  B=(*Head).Next;
	  while (A!=Tail)
	  {
		 if ((*A).Info.Fakyltet>(*B).Info.Fakyltet)
		 {
			(*Posr).Info=(*A).Info;
			(*A).Info=(*B).Info;
			(*B).Info=(*Posr).Info;
			flag=true;
		 }
		 A=(*A).Next;
		 B=(*B).Next;	 
	  }
   }
   while (flag==true);
   delete Posr;
   A=Head;
   B=(*Head).Next;
   if (A==0)
	  cout<<"Spisok pyst! Yporyadochivanie NEvjzmojno!";
   if (B==0)
	  cout<<"V spiske prisytstvyet vsego 1 element! Yporyadochivanie NE trebyetcya! ";	
}

void  Poryadok()   // Упорядочивание списка
{
   char nom;
   cout<<endl;
   cout<<"YPORYADOCHIVANIE SPISKA!"<<endl;
   cout<<"  (1) Surname... "<<endl;   
   cout<<"  (2) Gryppa..."<<endl;   
   cout<<"  (3) Fakyltet..."<<endl; 
   cout<<"Nomber of operation:  ";   // Введите номер операции
   cin>>nom;
   switch (nom)
   {
	  case('1'):
		 Poryadok_Surname();
		 break;
	  case('2'):
		 Poryadok_Gryppa();
		 break;
	  case('3'):
		 Poryadok_Fakyltet();
		 break;   
   }			
	  
}

void Ydalenie()
{
   Student* A;
   while (Head!=0)
   {
	  A=(*Head).Next;
	  delete Head;
	  Head=A;
   }   
}


void Write_to_file()
{
   cout<<"Please enter the filename: ";
   cin>>Filename; 
   ofstream fout(Filename);
   Student* A=Head;
   while (A!=0)
   {
	  fout<<(*A).Info.Surname<<"  "<<(*A).Info.Name<<"  "<<(*A).Info.Gryppa<<"  "<<(*A).Info.Fakyltet<<endl;
	  A=(*A).Next;
   }
   fout.close();
} 

  
void Vivod()
{
   Student* A=Head; 
   while (A!=0)
   {
	  cout<<(*A).Info.Surname<<" "<<(*A).Info.Name<<" "<<(*A).Info.Gryppa<<" "<<(*A).Info.Fakyltet<<endl;
	  A=(*A).Next;	   
	}	 
}

  
 main ()
{ 
   char st;
   int a;
   while (st!='7')
   {
	  system("cls"); // Очистка экрана
	  st=Main_menu(); // Код выбранной операции
	  system("cls"); // Очистка экрана
	  switch (st)
	  {
		 case('1'):
		 {
			Student* B;
			B=Pyst_struct(); // Указатель на пустую структуру данных	
			Zapolnenie (B); // Заполнение созданной структуры	   
			Add(B); 
			a=getch();	   
			break;
		 }
		 case('2'):
			Delete();
			a=getch(); 
			break;
		 case('3'):
			Poryadok();   // Упорядочивание списка
			a=getch(); 
			break;	
		 case('5'):
			Write_to_file(); // Записать данные в файл
			a=getch(); 
			break; 
		 case('6'):
			Vivod();
			a=getch(); 
			break;  
		 case('7'): 
			 void Ydalenie(); // При выходе удаляем список из памяти
			 break;		   
	  } 
   }			 
   
}

Вроде правильно!
Скажите..что мне надо именно переделать!!
Как я понял..
1.Мне надо убрать все pred, оставить только next.

И это всё?
И можете ещё кое что сказать..
Куда файл заисывается???
У неё он вроде в одном месте..у меня в другом каталоге..где , незнаю(

Сообщение отредактировано: volvo - 7.04.2010 10:47

[Олежечег(быв. Олежик)]

Удалил все преды...
вроде все работает.получился однонаправленный список..
только вот с функцией удалить из списка..немного не работает.
Помогите..пожалуйста!
Очень прошу.

[andriano]

При удалении из однонаправленного списка удаление со сложностью O(1) делается только для ЭЛЕМЕНТА, СЛЕДУЮЩЕГО ЗА УКАЗАННЫМ. Я бы назвал функцию DeleteNext и на этом считал, что функция уделения реализована.

[Олежечег(быв. Олежик)]

C этим..да..проблем нет..
Удаление работает..
Не работает удаление определённого номера!!!
Что делать?

// Удаление элемента с заданным номером (ключом)

void Del_klych()
{
	int n;
	char f[5];
	Student* A;
	cout<<"\nEnter number of an element which you want to delete  from the list: ";
	cin>>f;
	if (Korrect(f)==true)
	{
	   int n=atoi(f);
	   cout<<n;
	   if (Proverka_Koda(1,Kol_vo(),n)) // Если вы ввели номер элемента, который действительно пирсутствует в списке
	   {
		  A=Nelem(n); // Указатель на удаляемый элемент							 
		  if (A==Head)
			 Del_begin();
		  else
		  {
			 if (A==Tail)
				Del_end();  
			 else						   
			 {	  
				delete A; // Удаляем из памяти 
			 }	
		  }
	   }
	   else
		  cout<<"Number of operation is entered incorrectly!"<<endl;  
	}
	else
	   cout<<"Number of operation is entered incorrectly!"<<endl; 
}

else
{
delete A; // Удаляем из памяти

Скорее всего тут ошибка!!!
Я не уверен.
Помогите!!

Сообщение отредактировано: volvo - 7.04.2010 10:43