3.2 Создание списка
Для создания односвязного динамического списка в памяти обязательными являются несколько ключевых моментов.
Описание структурного типа, одним из полей которого будет указатель на структуру такого же типа;
struct list
{
string word;
string transl;
list *next;
};
Создание указателя на начало списка – то есть, на структуру, описанную в предыдущем пункте. В данном случае ─ указатель first.
list *first=NULL, *k;
В дальнейшем, при работе со списком, будет использоваться лишь этот указатель и описанный сначала структурный тип.
3.3 Просмотр списка
Для просмотра всего списка, то есть для какого-то действия, требующего перемещения по всем его элементам, используется такой алгоритм:
Создаётся временный указатель на элемент списка;
Этому временному указателю присваивается значение указателя на начало списка, чтобы не потерять значение начального указателя;
В цикле производится проход по всем элементам списка – при этом на каждой итерации цикла временному указателю присваивается значение следующего элемента списка. Условие выхода из цикла - указатель на следующий элемент равен значению NULL (признак конца односвязного списка).
В качестве примера – процедура ShowAll(), выводящая на экран весь список.
void ShowAll()
{
k=first;
while(k)
{
cout<<(*k).word<<" - "<<(*k).transl<<" # "<<(*k).next<<endl;
k=(*k).next;
}
}
3.4 Модификация списка
Рассмотрение изменения элементов в односвязном списке можно разделить на несколько логических операций: добавление элементов в список, изменение существующего в списке элемента, вставка элемента в список, и удаление элемента из списка. Теперь можно подробнее рассмотреть каждый из них.
Добавление элемента в список - новая запись в данной работе добавляется в начало этого списка. В результате этого алгоритма появляется временный указатель на первый элемент данного списка. В дальнейшем нужно при помощи операции new выделить память под новый элемент списка и присвоить адрес выделенной памяти указателю на первый элемент, а значение временного указателя присвоить указателю созданного элемента на следующий элемент
Если же добавляется первый элемент списка, адрес выделенной операцией new памяти нужно присвоить указателю на начало списка.
В качестве примера – процедура AddNew(), добавляющая новый элемент в зависимости от того, пуст список или имеет хотя бы 1 элемент.
void AddNew()
{
string s;
if (first==NULL)
{
first= new list;
cout<<"input word: ";
cin>>s;
(*first).word=s;
cout<<"input translation: ";
cin>>s;
(*first).transl=s;
(*first).next=NULL;
}
else
{
k=first;
first= new list;
(*first).next=k;
cout<<"input word: ";
cin>>s;
(*first).word=s;
cout<<"input translation: ";
cin>>s;
(*first).transl=s;
}
}
Изменение существующего в списке элемента - используется проход по всему списку до нужного элемента (обычно определяется каким либо условием – какое-то определённое значение поля, – либо порядковым номером элемента в списке), затем просто изменяются поля данной записи, которые не содержат указатель на последующие элементы.
В качестве примера – процедура RedWord(), позволяющая заменить слово и его перевод.
void RedWord()
{
string s;
cout<<"input word: ";
cin>>s;
k=first;
while(k)
{
if ((*k).word==s)
{
cout<<(*k).transl;
cout<<"input word: ";
cin>>s;
(*k).word=s;
cout<<"input translation: ";
cin>>s;
(*k).transl=s;
break;
}
k=(*k).next;
}
if (k==NULL) cout<<"No word in list"<<endl;
}
Удаление элементов из списка - применяется немного изменённый алгоритм прохода по всему списку – вместо одного временного указателя объявляется два. Второму временному указателю, на каждой итерации цикла будет присваиваться значение первого. По достижению нужной для удаления записи цикл прерывается, адресу указателя на следующий в списке элемент второго временного указателя присваивается адрес указателя на следующий в списке элемент первого временного указателя. Затем память по адресу первого временного указателя очищается функций delete. В случае если удаляется последний или первый элемент, применяется только один буферный указатель.
В качестве примера выступает процедура DeleteWord(), представленная в виде кода [см. Приложение 1, стр. 13] и графического отображения [см. Приложение 2, стр. 17, схема 1], а в упрощенном виде данное действие представленно в процедуре DeleteAll(), полностью удаляющей записи списка.
void DeleteAll()
{
while(first)
{
k=first;
first=(*first).next;
delete k;
}
}
Вставка элементов в список - применяется немного изменённый алгоритм добавления. Выполняется проход по списку до нужной записи, при этом запоминается еще и временный указатель на предшествующий (второму временному указателю, на каждой итерации цикла будет присваиваться значение первого). Затем в предшествующий элемент записывается адрес созданной функцией new записи. В указатель созданной записи записывается адрес следующего элемента, ранее бывшего текущим элементом (адрес на него хранится во временном указателе на текущий элемент). Графическое отображение можно увидеть на схеме 2 [см. Приложение 2, стр. 17, схема 2].
Вставка элемента в список описана чисто теоретически и в данной программе не реализовано, так как отсутствует сортировка списка по алфавиту.
ПРИЛОЖЕНИЕ
Приложение 1 ─ Полный код программы.
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
struct list {
string word;
string transl;
list *next;
}
list *first=NULL, *k;
string s;
void AddNew() {
string s;
if (first==NULL)//empty
{
first= new list;
cout<<"input word: ";
cin>>s;
(*first).word=s;
cout<<"input translation: ";
cin>>s;
(*first).transl=s;
(*first).next=NULL;
}
else {
k=first;
first= new list;
(*first).next=k;
cout<<"input word: ";
cin>>s;
(*first).word=s;
cout<<"input translation: ";
cin>>s;
(*first).transl=s;
}
}
void DeleteWord() {
list *prev;
string s;
bool f=false;
cout<<"input word: ";
cin>>s;
k=prev=first;
while(k) {
if ((*k).word==s) {
if (k==first) {
k=(*k).next;
delete first;
first=k;
f=true;
}
else {
(*prev).next=(*k).next;
delete k;
k=(*prev).next;
f=true;
}
}
if (f) {
break;
}
prev=k;
k=(*k).next;
}
if (f) cout<<"deleted"<<endl; else cout<<"error"<<endl;
}
void SizeList() {
int i=0;
k=first;
while(k) {
i++;
k=(*k).next;
}
cout<<i<<endl;
}
void ShowWord() {
string s;
cout<<"input word: ";
cin>>s;
k=first;
while(k) {
if ((*k).word==s) {cout<<(*k).transl<<endl; break;}
k=(*k).next;
}
if (k==NULL) cout<<"No word in list"<<endl;
}
void RedWord() {
string s;
cout<<"input word: ";
cin>>s;
k=first;
while(k) {
if ((*k).word==s) {
cout<<(*k).transl;
cout<<"input word: ";
cin>>s;
(*k).word=s;
cout<<"input translation: ";
cin>>s;
(*k).transl=s;
break;
}
k=(*k).next;
}
if (k==NULL) cout<<"No word in list"<<endl;
}
void ShowAll() {
k=first;
while(k) {
cout<<(*k).word<<" - "<<(*k).transl<<" # "<<(*k).next<<endl;
k=(*k).next;
}
}
void DeleteAll() {
while(first) {
k=first;
first=(*first).next;
delete k;
}
}
void ReadVocab() {
ifstream file("F://файл1.txt");
string str, sl, sp;
int l;
while(file) {
sl="", sp="";
bool f=false;
getline(file, str);
l=str.length();
for(int i=0; i<l;i++) {
if (str[i]!=' ') sl+=str[i]; else {i++; f=true; }
if(f) sp+=str[i];
}
cout<<sl<<" - "<<sp<<endl;
if (first==NULL) {
first=new list;
(*first).word=sl;
(*first).transl=sp;
(*first).next=NULL;
}
else {
k=first;
first=new list;
(*first).word=sl;
(*first).transl=sp;
(*first).next=k;
}
file.close();
}
void OutputVocab() {
ofstream out("F://file.txt");
if (!out) {
cout << "Cannot open file.\n";
}
k=first;
while(k) {
out << (*k).word << " " << (*k).transl << "\n";
k=(*k).next;
}
out.close ();
}
int main() {
setlocale(0,"RUS");
cout<<"Перечень команд:\n";
cout<<"Добавить новое слово\t"<<"add\n";
cout<<"удалить слово\t"<<"delete\n";
cout<<"Редактировать запись\t"<<"redact\n";
cout<<"Вывести перевод слова\t"<<"show\n";
cout<<"Вывести все записи\t"<<"all\n";
cout<<"Удалить все записи\t"<<"clear\n";
cout<<"Узнать количество слов в списке\t"<<"size\n";
cout<<"Окончить сессию\t"<<"stop\n";
cout<<"Считать данные из файла\t"<<"in\n";
cout<<"Занести данные в файл\t"<<"out\n";
string command="";
while (command!="stop") {
cout<<"input command: "; cin>>command;
if (command=="size") SizeList();
else if (command=="add") AddNew();
else if (command=="delete") DeleteWord();
else if (command=="all") ShowAll();
else if (command=="redact") RedWord();
else if (command=="show") ShowWord();
else if (command=="clear") DeleteAll();
else if (command=="in") ReadVocab();
else if (command=="out") OutputVocab();
else if (command!="stop") cout<<"No such command"<<endl;
}
cin.get();
return 0;
}
Приложение 2 ─ Схемы действий с элементами списка.
С
prev
k
хема 1 ─ Удаление записи из списка.
Схема 2 ─ Вставка записи в список.
prev
k
(new)
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
Партыка, Т.Л., Попов, И.И. Программирование на Си / изд. Инфра-М, 2008.-477-480 с.
Савацкий, А. Л. Основы управления ресурсами : учеб. пособие для вузов / А. Л. Савацкий. – 2005. – 130 с.
Павловская Т.А. С/С++. Программирование на языке высокого уровня. – СПб.: Питер, 2002. – 464с.
Топп У., Форд У. Структуры данных в С++: Пер. с англ. - М.: БИНОМ, 1994. – 816 с.