Линейные списки.
Использование указателей на структуры позволяет использовать весьма сложно организованные данные типа различного рода списков, очередей и деревьев. Рассмотрим так называемые линейные списки.
Линейный список - это упорядоченная структура данных, каждый элемент которой содержит ссылку (указатель), связывающую его со следующим элементом.
Для организации списков служат структуры, состоящие из двух смысловых частей: основной, содержащей полезную информацию, и дополнительной, содержащей ссылку на следующий элемент списка. Графически это можно представить следующим образом:
......... ......... ......... ......... ...........
: : : : : : : : : : : : : :NULL:
......... ......... ......... ......... ...........
В виде списков удобно представлять большие объемы информации, размер которых заранее неизвестен.
Рассмотрим, например, как можно было бы организовать хранение информации о товарах для программы "магазин".
typedef struct _GOODS{
char name[21];
int number;
float price;
struct _GOODS *next;
} GOODS;
Очевидно, программа должна иметь переменную - указатель на первый элемент списка. Последний элемент списка отличается тем, что в поле next имеет константу NULL - то есть пустой указатель. Тогда список может быть представлен так:
......... ......... ......... ...........
TOP : : : : : : : : : : :NULL:
......... ......... ......... ...........
Программа формирования списка товаров выглядит следующим образом:
GOODS *new_GOODS ( void)
{
GOODS *p;
p = (GOODS* ) malloc( sizeof(GOODS) );
if (p==NULL) {printf("Недостаточно памяти\n");
exit(1);}
return p;
}
GOODS *in_goods( void )
{
GOODS *top, *q;
printf("Введите характеристики товаров в виде:\n" \
"наименование количество цена\n" \
"-------окончание ввода \"end\"-------\n");
top = NULL;
while (1)
{
q = new_GOODS(); if( !in_goods1(q) ) { free(q);
return top; }
q->next = top; top = q;
}
}
Обращение к этой программе будет выглядеть так:
top = in_goods();
Вспомогательная программа new_GOODS осуществляет все необходимые действия по выделению памяти и контролю за ее наличием.
Достоинство такой организации данных в том, что используется ровно столько памяти, сколько надо (накладные расходы - поле адреса). Вместе с тем список может быть сколь угодно большим. Ограничение - память ЭВМ. Недостаток - мы не имеем возможности прямого доступа к памяти.
Рассмотрим процедуру вывода на печать содержимого списка. Обратить внимание на то, что содержимое выводится в порядке обратном вводу (в принципе можно было бы и наоборот).
void out_goods( GOODS *top)
{
printf("*--------------------------------------*\n");
printf("| Наименование | Кол-во | Цена |\n");
printf("|--------------------|--------|--------|\n");
while( top != NULL )
{
printf( "| %20s | %10.2f |\n",
top->name, top->number, top->price );
top = top->next;
}
printf("*--------------------------------------*\n");
}
Головная функция должна выглядеть следующим образом:
void main( void )
{
GOODS *top;
top = in_goods();
out_goods ( top );
}
Как же быть с сортировкой, а ее вообще не надо делать, так как можно в процессе ввода получить отсортированный список, вставляя очередную запись в нужное место.
Рассмотрим вспомогательную задачу: необходимо вставить запись, на которую указывает указатель g в список за записью, на которую указывает указатель p.
g .........
: :. :
......|..
2 ^ | 1
| V
TOP ......... ......... ......... ......... ..........
: : : : : p : : : : : : : : :NULL:
......... ......... ......... 2 ......... ..........
p
g->next = p->next; 1
p->next = g; 2
Текст программы выглядит следующим образом:
GOODS *in_goods( void )
{
GOODS *top, *q, *p;
printf("Введите характеристики товаров в виде:\n" \
"наименование количество цена\n" \
"-------окончание ввода \"end\"-------\n");
/* Получение списка из двух элементов */
top = NULL;
q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}
q->next = NULL; top = q;
q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}
if(q->price < top->price ) { q->next = top; top = q; }
else { q->next = NULL; top->next = q; }
/* Получение списка из остальных элементов */
while( 1 )
{
q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}
if(q->price < top->price )
{ q->next = top; top = q; }
else
{
p = top;
while(p->next && (q->price > p->next->price)) p=p->next;
q->next = p->next; p->next = q;
}
}
}
/* Пример использования списка # 1 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <alloc.h>
#include <math.h>
typedef struct _GOODS{
char name[21];
int number;
float price;
struct _GOODS *next;
} GOODS;
GOODS in_goods ( void );
GOODS new_goods ( void );
int in_goods1 ( GOODS *g );
void out_goods (GOODS *top );
void main( void )
{
GOODS *top;
top = in_goods();
out_goods ( top );
{ float f=0; sin(f); }
}
GOODS *new_GOODS ( void )
{
GOODS *p;
p = (GOODS*) malloc( sizeof(GOODS) );
if (p==NULL) {printf("Недостаточно памяти\n");
exit(1);}
return p;
}
GOODS *in_goods( void )
{
GOODS *top, *q;
printf("Введите характеристики товаров в виде:\n" \
"наименование количество цена\n" \
"-------окончание ввода \"end\"-------\n");
top = NULL;
while (1)
{
q = new_GOODS(); if( !in_goods1(q) ) { free(q);
return top; }
q->next = top; top = q;
}
}
int in_goods1( GOODS *g )
{
scanf( "%s", q->name );
if ( strcmp(g->name, "end")== ) return 0;
scanf( "%d%f", &g->number, &g->price );
return 1;
}
void out_goods( GOODS *top)
{
printf("*--------------------------------------*\n");
printf("| Наименование | Кол-во | Цена |\n");
printf("|--------------------|--------|--------|\n");
while( top != NULL )
{
printf( "| %20s | %10.2f |\n",
top->name, top->number, top->price );
top = top->next;
}
printf("*--------------------------------------*\n");
}
/* Пример использования списка с сортировкой */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <alloc.h>
#include <math.h>
typedef struct _GOODS{
char name[21];
int number;
float price;
struct _GOODS *next;
} GOODS;
GOODS in_goods ( void );
GOODS new_goods ( void );
int in_goods1 ( GOODS *g );
void out_goods (GOODS *top );
void main( void )
{
GOODS *top;
top = in_goods();
out_goods ( top );
{ float f=0; sin(f); }
}
GOODS *new_GOODS ( void )
{
GOODS *p;
p = (GOODS*) malloc( sizeof(GOODS) );
if (p==NULL) {printf("Недостаточно памяти\n");
exit(1);}
return p;
}
GOODS *in_goods( void )
{
GOODS *top, *q, *p;
printf("Введите характеристики товаров в виде:\n" \
"наименование количество цена\n" \
"-------окончание ввода \"end\"-------\n");
/* Получение списка из двух элементов */
top = NULL;
q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}
q->next = NULL; top = q;
q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}
if(q->price < top->price ) { q->next = top; top = q; }
else { q->next = NULL; top->next = q; }
/* Получение списка из остальных элементов */
while( 1 )
{
q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}
if(q->price < top->price )
{ q->next = top; top = q; }
else
{
p = top;
while(p->next && (q->price > p->next->price)) p=p->next;
q->next = p->next; p->next = q;
}
}
}
int in_goods1( GOODS *g )
{
scanf( "%s", q->name );
if ( strcmp(g->name, "end")== ) return 0;
scanf( "%d%f", &g->number, &g->price );
return 1;
}
void out_goods( GOODS *top)
{
printf("*--------------------------------------*\n");
printf("| Наименование | Кол-во | Цена |\n");
printf("|--------------------|--------|--------|\n");
while( top != NULL )
{
printf( "| %20s | %10.2f |\n",
top->name, top->number, top->price );
top = top->next;
}
printf("*--------------------------------------*\n");
}
Дата добавления: 2014-12-18; просмотров: 921;