|
Pers.narod.ru. Обучение. Лекции по Си. Глава 12 |
Можно выделить следующие основные классы динамических объектов:
· упорядоченные совокупности характеризуются тем, что для них значим физический порядок встраивания элементов. Пример - массивы;
· неупорядоченные совокупности или коллекции - физический порядок объектов в представлении данных незначим, встраивание объектов в коллекцию произвольно. Примеры - хэши, одно‑ и двусвязные списки, деревья;
· последовательности - физический порядок объектов в представлении данных незначим, но значим порядок вставки/удаления, которые выполняются только в определенных точках последовательности. Примеры - стеки, очереди.
Существуют 2 основных возможности для организации динамических структур:
· библиотеки функций classlib;
· организация динамических наборов структур, связанных указателями на структурные типы.
Реализация динамических структур через предопределенные классы требует подключения библиотеки TCLASSS.LIB (если выбрана модель Small, также есть TCLASSL.LIB для Large) из папки BORLANDC\CLASSLIB\LIB к файлу проекта, а также включения в строку опций Include Directories маршрута \BORLANDC\CLASSLIB\INCLUDE. Если предположить, что среда установлена в папку d:\BORLANDC, настройки путей могут иметь следующий вид:
Include Directories:
d:\BORLANDC\INCLUDE; d:\BORLANDC\CLASSLIB\INCLUDE; d:\BORLANDC\TVISION\DEMOS;.
Library directories:
d:\BORLANDC\LIB;d:\BORLANDC\TVISION\LIB;
d:\BORLANDC\CLASSLIB\LIB;.
Output Directory: .
Source Directories: d:\BORLANDC\BIN;.
Подробное рассмотрение иерархии классов библиотек classlib можно найти в специальной литературе, в данном пособии мы подробнее рассмотрим независимое программирование динамических списков структур.
В простейшем виде элемент списка представляет собой структурную переменную, содержащую один или несколько указателей на следующие или предшествующие элементы и любое число других полей, называемых информационными. Если список располагается в оперативной памяти, то информацией для поиска следующего элемента служит адрес (указатель) в памяти. Если список хранится в файле, информация о следующем элементе может включать смещение от начала файла, относительное положение указателя записи/считывания файла, ключ записи и любую другую информацию, позволяющую однозначно отыскать следующий элемент.
В простейшем случае односвязный (однонаправленный) список имеет одно информационное поле и один указатель на следующий элемент:
typedef struct list {
list * next;
int info;
};
Для работы с элементами такого списка достаточно определить статический указатель на начало списка
list * head;
и хотя бы один "буферный" элемент, который будет служить для ввода и временного хранения данных:
list work;
Как минимум, функции работы с элементами списка, принимающие в качестве параметра указатель на некоторый его элемент, должны реализовывать операции вывода по порядку всех или избранного элемента, добавление и удаление элементов с выделением и высвобождением памяти, возможно, также поиск элементов, определение того, содержится ли уже в списке нужный элемент и т.п.
Например, функция вывода всех элементов списка, использующая глобальный указатель root на его вершину, могла бы иметь следующий вид:
struct list *root;
//Указатель на вершину списка
void List (void) {
struct list *iter = root;
int i = 0;
while(iter != NULL) {
//Пока указатель не пуст
printf ("\n элемент %2d: (%d)",
i++,iter->info);
//Напечатать очередной элемент списка
iter = iter->next;
//и перейти к след. элементу
}
}
Разумеется, сами поля списочной структуры также могут выделяться динамически, как показано в несложном примере ниже. В этом примере для простоты элементы добавляются всегда в конец списка и выводятся в порядке ввода. Ввод нуля с клавиатуры служит признаком конца ввода.
#include <stdio.h>
#include <alloc.h>
#include <string.h>
typedef struct list {
char *s;
list *next;
};
void main () {
list head, *ptr;
int i=0;
char s[80];
ptr=&head;
ptr->next=NULL;
do {
printf (" %d) ",i+1);
fgets (s,80,stdin);
if (!strcmp(s,"0\n")) {
break;
}
else {
ptr->s=(char *)malloc(strlen(s));
strcpy (ptr->s,s);
ptr->next=(list *)malloc(sizeof(list));
ptr=ptr->next;
ptr->next=NULL;
}
i++;
} while (1);
ptr=&head;
i=1;
while (ptr->next!=NULL) {
printf ("%d) %s",i++,ptr->s);
ptr=ptr->next;
}
}
В реальном спиcке может потребоваться множество дополнительных функций, таких как встраивание элементов в определенном порядке, перестановка, удаление, модификация и т. д. Приведем пример функции add(), добавляющий элемент, определяемый указателем new_ptr, в список с вершиной head. Встраивание элемента производится по возрастанию значения поля info, предполагается, что перед этим элемент уже проверен на уникальность функцией hasMember(). Использование указателя list **head в функции add() позволяет избежать прямого сравнения указателей в коде. При описании указателя на начало списка в виде list *head; и указателя на новый элемент list *new_ptr;, функция могла бы быть вызвана оператором вида add(&head, new_ptr);.
int add(list ** head, list * new_ptr) {
list * first, * second;
if ((*head)==NULL) { //список пуст
(* head) = new_ptr;
new_ptr -> next = NULL;
return 0;
}
if ((*head)->next == NULL) {
//в списке один элемент
if ( (*head)->info > new_ptr->info) {
// новый элемент - первый в списке
second = (*head);
// сохраним указатель на 2-й элемент
(*head) = new_ptr;
new_ptr -> next = second;
second -> next = NULL;
}
else { // новый элемент в конец списка
(*head) -> next = new_ptr;
new_ptr -> next = NULL;
}
return 1;
}
else { //в списке более 1 элемента
if ( (*head)->info > new_ptr->info) {
// новый элемент - первый в списке
second = (*head);
(*head) = new_ptr;
new_ptr -> next = second;
return 4;
}
first = (* head);
second = first -> next;
while (first->next != NULL) {
//цикл поиска места в списке
if (first->info <= new_ptr->info &&
second->info >= new_ptr->info) {
// вставляем элемент между
// first и second
first -> next = new_ptr;
new_ptr -> next = second;
return 2;
}
first = second;
second = first -> next;
}
// если добрались сюда,
// ставим элемент в конец списка
first -> next = new_ptr;
new_ptr -> next = NULL;
return 3;
}
}
int hasMember (list * head, list * work) {
while(head != NULL) {
// цикл сканирования списка
if (head->info == work -> info) return 1;
head = head -> next;
}
return(0);
}
Аналогичным образом с использованием структур и указателей могут быть реализованы другие динамические стуктуры данных. Приведем несложный пример на работу с деревом, каждый узел которого может иметь произвольное количество узлов-потомков.
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
typedef struct tree {
int info;
tree **childs;
unsigned count;
};
int const size1=sizeof(tree);
void error (int c) {
printf ("\nError: ");
switch (c) {
case 1: printf(" no memory"); break;
default: printf(" unknown"); break;
}
exit (c);
}
tree *init (tree *p,int info) {
p->info=info;
p->count=0;
p->childs=NULL;
return p;
}
void print1 (tree *p) {
printf ("\nnode %6d: %2d child(s)",
p->info,p->count);
}
void printnode (tree *p) {
print1 (p);
for (int i=0; i<p->count; i++)
print1 (p->childs[i]);
}
tree *searchnode (tree *t, int info) {
if (t->info == info) return t;
else if (t->count>0) {
for (int i=0; i<t->count; i++) {
tree *p=searchnode (t->childs[i],info);
if (p!=NULL) return p;
}
return NULL;
}
else return NULL;
}
tree *addnode (tree *ptr, int parentinfo,
int info) {
tree *p=searchnode (ptr,parentinfo);
if (p!=NULL) {
if (p->childs==NULL) {
p->childs = (tree **)malloc
(sizeof(tree *));
if (p->childs==NULL) error (1);
p->childs[0]=(tree *)malloc(size1);
if (p->childs[0]==NULL) error (1);
(p->count)=1;
}
else {
p->childs = (tree **)
realloc(p->childs,sizeof(tree *)
*(p->count+1));
if (p->childs==NULL) error (1);
p->childs[p->count]=(tree *)
malloc(size1);
if (p->childs[p->count]==NULL)
error (1);
(p->count)++;
}
return init (p->childs[p->count-1],info);
}
return NULL;
}
void main () {
tree head,temp,*ptr;
ptr=&head;
init(ptr,1);
addnode (ptr,1,2);
addnode (ptr,1,3);
addnode (ptr,2,4);
tree *s=searchnode (ptr,2);
printf ("\n With node after search:");
if (s!=NULL) printnode (s);
else printf ("\nNULL");
printf ("\n With root:");
printnode (ptr);
}
 гостевая; E-mail
|
