Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Организация данных в виде стека.

Линейные списки.

 

Использование указателей на структуры позволяет использовать весьма сложно организованные данные типа различного рода списков, очередей и деревьев. Рассмотрим так называемые линейные списки.

Линейный список - это упорядоченная структура данных, каждый элемент которой содержит ссылку (указатель), связывающую его со следующим элементом.

Для организации списков служат структуры, состоящие из двух смысловых частей: основной, содержащей полезную информацию, и дополнительной, содержащей ссылку на следующий элемент списка. Графически это можно представить следующим образом:

В виде списков удобно представлять большие объемы информации, размер которых заранее неизвестен.

Рассмотрим, например, как можно было бы организовать хранение информации о товарах для программы "магазин".

typedef struct _GOODS{

char name[21];

int number;

float price;

struct _GOODS *next; } GOODS;

Очевидно, программа должна иметь переменную - указатель на первый элемент списка. Последний элемент списка отличается тем, что в поле next имеет константу 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( !input_goods(q) ) { free(q);

break; }

q->next = top; top = q;

}

return top;

}

Обращение к этой программе будет выглядеть так:

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->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(!input_goods(q)) {free(q); return top;}

 

q->next = NULL; top = q;

q=new_GOODS(); if(!input_goods(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(!input_goods(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 input_goods( 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( !input_goods(q) ) { free(q);

return top; }

q->next = top; top = q;

}

}

int input_goods( 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 input_goods( 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(!input_goods(q)) {free(q); return top;}

q->next = NULL; top = q;

q=new_GOODS(); if(!input_goods(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(!input_goods(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 input_goods( 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");

}

 

Организация данных в виде стека.

 

Понятие стека ("магазина"): первый пришел, последний ушел.

LIFO (LAST IN FIRST OUT)

Описание стека как списка:

typedef struct _LIST

{

info_t info; /* тип данных для информации */

struct _LIST *next;

} LIST;

В вызывающей функции стек должен быть описан так:

LIST *head = NULL; /* голова списка */

Действия со стеком определяется несколькими функциями:

1. Помещение элемента в стек (в голову списка)

void add_head (LIST **head, info_t a)

{

LIST *t;

if (t=(LIST*) malloc (sizeof (LIST)))

{

t->info = a; /* 1 */

t->next = (*head); /* 2 */

(*head) = t; /* 3 */

}

}

 
 

 


2. Извлечение из стека (из головы списка)

info_t get_head (LIST **head)

{

LIST *t; info_t a;

if ( *head)

{

a = (*head)->info; /* 1 */

t = (*head); /* 2 */

(*head) = (*head)->next; /* 3 */

free (t);

}

return a;

}

 
 

 

 


Организация данных в виде очереди.

 

Понятие очереди: первый пришел, первый ушел.

FIFO (FIRST IN FIRST OUT).

Описание очереди: такое же, что и стека, но надо хранить и начало и хвост очереди.

 
 

 


Тогда в вызывающей программе очередь описывается так:

LIST *head = NULL, *tail = NULL;

Помещение элемента в очередь (в хвост списка):

 

1-ый элемент:

 

Остальные:

 
 

 


void add_tail (LIST **head, LIST **tail, info_t a)

{

LIST*t;

if (t = (LIST*) malloc (sizeof (LIST)))

{

t->info = a; /* 1 */

t->next = NULL; /* 2 */

if (*head) == NULL) (*head) = t; /* 3а */

else (*tail)->next = t;/* 3б */

(*tail) = t; /* 4 */

}

}

 

<== предыдущая лекция | следующая лекция ==>
Текстовый и двоичный (бинарный) режим работы файлов | 

Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2019 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных