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

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

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


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

учил по FAQ..

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

Завтра выложу приблизительный свой пример..
а вы пока бы не могли найти помощь в создании однонаправленных списков..
именно шаблоны создания?
Тёмный Эльф
Цитата(Олежечег(быв. Олежик) @ 12.12.2007 1:53) *

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

Вот на этом сайте хорошо изложено про создание списков на 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.

И это всё?
И можете ещё кое что сказать..
Куда файл заисывается???
У неё он вроде в одном месте..у меня в другом каталоге..где , незнаю(
Олежечег(быв. Олежик)
Удалил все преды...
вроде все работает.получился однонаправленный список..
только вот с функцией удалить из списка..немного не работает.
Помогите..пожалуйста!
Очень прошу.
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; // Удаляем из памяти


Скорее всего тут ошибка!!!
Я не уверен.
Помогите!!
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.