ТОР 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 */ } }
Не нашли, что искали? Воспользуйтесь поиском:
|