Краткие теоретические сведения
односвязный список
Во многих задачах требуется использовать данные у которых конфигурация, размеры, состав могут изменяться в процессе выполнения программы. Для их представления используют динамические информационные структуры.
Наиболее простая информационная структура – это односвязный список, элементами которого служат объекты структурного типа. Например
struct имя_структурного_типа
{
элементы_структуры_данные;
имя_структурного_типа *указатель;
}
В каждую структуру такого типа входит указатель на объект того же типа, что и определяемая структура.
beg
Примеры:
1. Описание структуры
struct point
{
int key;
point* next;
};
Поле key содержит информационную часть структуры point, а поле next содержит адрес следующего элемента списка.
2. Функция для формирования однонаправленного списка
point* make_point( int n)
{
point *first, *p;
first=NULL;
for (int i=n; i>0; i--)
{
p=new(point);
p->key=i;
p->next=first;
first=p;
}
return first;
}
В качестве параметра в функцию передается количество элементов в списке, а результатом является указатель на первый элемент этого списка. Указатель р указывает на вновь создаваемый элемент.
Для обращения к полям используется операция доступа к элементу структуры, с которой связан указатель ->.
Существует вторая возможность обращения к полю динамической структуры: (*p).key или (*p).next. В информационное поле key заносится порядковый номер элемента в списке. Добавление новых элементов осуществляется в начало списка.
3. Функция для печати однонаправленного списка
point* print_point(point*first)
{
if (first==NULL) return NULL;
point* p = first;
while(p!=NULL)
{
cout << p->key << "\n";
p = p->next;
}
return first;
}
При печати сформированного списка осуществляется проход по списку с помощью вспомогательной переменной р до тех пор, пока она не станет равна NULL.
Пример реализации (учебный пример)
#include <string.h>
#include <stdio.h>
struct ss
{ int n;
char z[80];
ss*next;
};
int main(int argc, char* argv[])
{
ss*top;
ss*tek;
top=new ss();
top->n=1;
strcpy(top->z,"zap-01");
top->next=NULL;
printf("top=%4x\n",top);
for (int i=1;i<=10;i++)
{
tek=top;
while(tek->next!=NULL)
tek=tek->next;
tek->next=new ss();
tek=tek->next;
tek->n=i;
sprintf(tek->z,"zap-%02d",i);
tek->next=NULL;
};
/////печать
printf("после создания списка\n");
tek=top;
int k=1;
while(tek->next!=NULL)
{ printf("tek=%4x zap=%2d {n=%2d z=<%s> next=%4x}\n",
tek, k, tek->n, tek->z, tek->next);
tek=tek->next;
k++;
};
/////поиск
k=1;
int find=5;
ss*zfind=NULL;
tek=top;
while(tek->next!=NULL)
{ if(tek->n==find)
{ zfind=tek;
printf("find=%2d tek=%4x tek->n=%2d tek->z=<%s> tek->next=%4x\n",
find, tek, tek->n, tek->z, tek->next);
break;
};
tek=tek->next;
k++;
};
if(zfind==NULL)
printf("not found.....find=%d\n", find);
else
printf("!!!found find=%d\n", find);
printf("zfind=%4x\n",zfind);
/////удаление
ss * last;
ss * zdel=NULL;
tek=top;
last=tek;
while (tek->next!=NULL)
{ if (tek->n==5) // что ищем......
{
zdel=tek;
break ;
};
last=tek;
tek=tek->next;
};
if(zdel!=NULL)
{ if (top==tek)
{delete top;
top=NULL;
printf("delete 1-st zap --- spis is lost......\n");
return 555;
};
if(zdel->next==NULL)
{ last->next=NULL;
delete zdel;
}
else
{ last->next=zdel->next;
delete zdel;
};
};
/////печать
printf("после удаления 5-й записи\n");
tek=top;
k=1;
while(tek->next!=NULL)
{ printf("tek=%4x zap=%2d {n=%2d z=<%s> next=%4x}\n",
tek, k, tek->n, tek->z, tek->next);
tek=tek->next;
k++;
};
/// вставка новой записи.....
// ss * last;
zfind=NULL;
tek=top;
last=tek;
ss * newadd;
while (tek->next!=NULL)
{ if (tek->n==6) // что ищем
{
zfind=tek;
break ;
};
last=tek;
tek=tek->next;
};
// zfind add next zap
if (zfind != NULL)
{
printf("!!!found zfind=%d\n", zfind);
printf("zfind->n=%2d zfind->z=<%s> zfind->next=%4x\n",
zfind->n, zfind->z, zfind->next);
//getchar();// return 6;
newadd = new ss();
strcpy(newadd->z,"новая запись после 6 zap ****");
newadd->next=zfind->next;
zfind->next=newadd;
}
else printf("zap not found,,,,,\n");
/////печать
printf("после вставки новой записи списка\n");
tek=top;
k=1;
while(tek->next!=NULL)
{ printf("tek=%4x zap=%2d {n=%2d z=<%s> next=%4x}\n",
tek, k, tek->n, tek->z, tek->next);
tek=tek->next;
k++;
};
/*****************************************************/
///// удаление списка из памяти
ss*temp;
tek=top;
while(tek->next!=NULL)
{temp=tek;
tek=tek->next;
delete temp;
};
return 0;
}
C:\Test\cpp\!!пример программы по структурам>spis-1
top=842d60
после создания списка
tek=842d60 zap= 1 {n= 1 z=<zap-01> next=842dbc}
tek=842dbc zap= 2 {n= 1 z=<zap-01> next=842e18}
tek=842e18 zap= 3 {n= 2 z=<zap-02> next=842e74}
tek=842e74 zap= 4 {n= 3 z=<zap-03> next=842ed0}
tek=842ed0 zap= 5 {n= 4 z=<zap-04> next=842f2c}
tek=842f2c zap= 6 {n= 5 z=<zap-05> next=842f88}
tek=842f88 zap= 7 {n= 6 z=<zap-06> next=842fe4}
tek=842fe4 zap= 8 {n= 7 z=<zap-07> next=843040}
tek=843040 zap= 9 {n= 8 z=<zap-08> next=84309c}
tek=84309c zap=10 {n= 9 z=<zap-09> next=8430f8}
find= 5 tek=842f2c tek->n= 5 tek->z=<zap-05> tek->next=842f88
!!!found find=5
zfind=842f2c
после удаления 5-й записи
tek=842d60 zap= 1 {n= 1 z=<zap-01> next=842dbc}
tek=842dbc zap= 2 {n= 1 z=<zap-01> next=842e18}
tek=842e18 zap= 3 {n= 2 z=<zap-02> next=842e74}
tek=842e74 zap= 4 {n= 3 z=<zap-03> next=842ed0}
tek=842ed0 zap= 5 {n= 4 z=<zap-04> next=842f88}
tek=842f88 zap= 6 {n= 6 z=<zap-06> next=842fe4}
tek=842fe4 zap= 7 {n= 7 z=<zap-07> next=843040}
tek=843040 zap= 8 {n= 8 z=<zap-08> next=84309c}
tek=84309c zap= 9 {n= 9 z=<zap-09> next=8430f8}
!!!found zfind=8662920
zfind->n= 6 zfind->z=<zap-06> zfind->next=842fe4
после вставки новой записи списка
tek=842d60 zap= 1 {n= 1 z=<zap-01> next=842dbc}
tek=842dbc zap= 2 {n= 1 z=<zap-01> next=842e18}
tek=842e18 zap= 3 {n= 2 z=<zap-02> next=842e74}
tek=842e74 zap= 4 {n= 3 z=<zap-03> next=842ed0}
tek=842ed0 zap= 5 {n= 4 z=<zap-04> next=842f88}
tek=842f88 zap= 6 {n= 6 z=<zap-06> next=842f2c}
tek=842f2c zap= 7 {n=8651072 z=<новая запись после 6 zap ****> next=842fe4}
tek=842fe4 zap= 8 {n= 7 z=<zap-07> next=843040}
tek=843040 zap= 9 {n= 8 z=<zap-08> next=84309c}
tek=84309c zap=10 {n= 9 z=<zap-09> next=8430f8}