Однонаправленные связанные списки

Стек

Введение в структуры данных

Результат работы программы

Указатель стека	после ввода	числа	1200 2204
Указатель стека	после ввода	числа	13 2212
Указатель стека	после ввода	числа	125 2220
peek(stl)=125
pop(stl)=125
pop(stl)=13
pop(stl)=1200
pop(stl)=0
peek(stl)=0

Резюме:

1. Каждый элемент стека содержит два поля: поле информации info и поле следующего адреса next.

2. Поле адреса содержит указатель на следующий элемент стека.

3. Доступ к стеку осуществляется через указатель stl, который содержит адрес верхнего элемента стека.

4. Поле адреса последнего элемента должно содержать нулевое значение, как свидетельство того, что в стеке больше нет элементов.

Глава 2. Структуры данных

Во второй главе мы рассмотрели основные структуры данных языка Си: переменные, массивы, структуры, объединения. Структуры данных называются основными, поскольку они часто используются в практике программирования, и из них можно образовывать более сложные объекты.

Переменные, массивы, структуры, объединения при объявлении получают имя и тип — под них выделяются ячейки оперативной памяти, в которые можно записывать некоторые значения. Таким образом, данные объекты имеют неизменяемую (статическую) структуру. Существует, однако, много задач, в которых требуются данные с более сложной структурой. Для них характерно, что в процессе вычислений изменяются не только значения объектов, но даже и сама структура хранения информации. Поэтому такие объекты стали называть динамическими информационными структурами. Их компоненты на некотором уровне детализации представляют собой объекты со статической структурой, т. е. они принадлежат к одному из основных типов данных. Эта глава посвящена проектированию объектов с динамической структурой, анализу и работе с ними [1,3,8,11].

Стеком называется упорядоченный набор элементов, в котором размещение новых и удаление существующих элементов происходит с одного конца, называемого вершиной. Иными словами, в стеке реализуется дисциплина обслуживания LIFO (last input — first output; первым вошел — последним вышел) [11].

Над стеком реализованы следующие операции [3, 8, 11]:

1) помещение элемента в стек push(,s, /), где s — стек, / — помещаемый элемент;

2) удаление элемента из стека / = pop(s);

3) определение верхнего элемента без его удаления / = stacktop(s), которая эквивалентна операциям / = pop(s) и push(,s, /);

4) определение пустоты стека emty(,s), которая возвращает true, если стек пустой к false в противном случае.

Существует несколько способов реализации стека:

1) с помощью одномерного массива конечного размера, распределенного статически;

2) с помощью одномерного массива, распределенного динамически;

3) в виде связанного списка.

Стек можно реализовать в виде следующей структуры:

#defme NMAX100 struct stack

{ float elem[NMAX\;

integer top;

};,

где NMAX — максимальное количество элементов в стеке; elem — массив из NMAX чисел типа float, предназначенный для хранения элементов стека; top — индекс элемента, находящегося на вершине стека.

Пример. Необходимо написать программу-калькулятор, вычисляющую значение выражения, записанного в постфиксной форме [7]. При записи выражения допускаются операции «+», «-», «*», «/» и знак «=» — для выдачи результата. Выражение типа

(1-2)*(4+5) запишется в следующем виде:

12-45 + * — круглые скобки при этом не нужны.

Реализация оказывается весьма простой. Каждый операнд помещается в стек; когда поступает знак операции, нужное количество операндов вынимается из стека, к ним применяется операция и результат направляется обратно в стек. Так, в приведенном выше примере 1 и 2 помещаются в стек и затем заменяются их разностью, -1. После этого 4 и 5 вводятся в стек и затем заменяются своей суммой 9; далее числа -1 и 9 заменяются в стеке на их произведение, равное -9. Операция «=» печатает верхний элемент стека, не удаляя его (так что промежуточные вычисления могут быть проверены).

Сами операции помещения чисел в стек и их извлечения оформляются в виде функций. Кроме того, используется отдельная функция для выборки из ввода следующей операции или операнда. Требуемая структура программы приведена ниже [7].

while(поступает операция или операнд, а не конец файла) if(число)

поместить его в стек else if(операция)

вынуть операнды из стека выполнить операцию поместить результат в стек else

ошибка

Операции «взять из стека» и «послать в стек» реализуем в виде функция. Добавим механизм обнаружения и нейтрализации ошибок [7].

/^максимальный размер оператора*/ /^признак числа*/

#include<stdlib.h> #include<stdio.h> #include<ctype.h> #include<math.h> #include <string.h> #define MAXOP 100 #define NUMBER 0 #define IDENTIFIER 1 #define TRUE 1 #define FALSE 0 int Getop(char s[]); void push(double val); double pop(void);

void showTop(void);

void duplicate(void);

void swapltems(void);

void clearStack();

void dealWithName(char s[]);

int main(void)

{

int type; double op2; char s[MAXOP]; int flag = TRUE;

while((type = Getop(s))!= EOF)

{

switch(type)

{

case NUMBER:

push(atof(s));

break; case IDENTIFIER:

dealWithName(s);

break; case ' + ':

push(pop () + pop ());

break; case ' * ':

push(pop () * pop ());

break;

case '- ':
op2 = pop();
push(pop()- op2);
break;
case '/':
op2 = pop ();
if(op2)
push(pop() / op2);
else
printf("\пОшибка! Деление на ноль.");
break;
case ' % ':
op2 = pop();
if(op2)
push(fmod(pop(), op2));
else
printf("\пОшибка! Деление на ноль.");
break;
case '? ':
showTop();
break;
case '# ':
duplicate ();
break;
case '~':
swapltems();
break;
case '! ':
clearStack();
case '\n':
printf("\n\t%.8g\n", pop ());
break;
default:
printf("\пОшибка! Неизвестная операция. %s	An",
s);
break; }
} return EXIT SUCCESS;
}

Поскольку операции «+» и «*» коммутативны, то порядок, в котором операнды берутся из стека, не важен. Однако, в случае операций «-» и «/» левый и правый операнды должен различаться. Так, в строке

push(pop() -popQ);

порядок, в котором выполняются обращения к рор() не определен. Для гарантии правильного порядка первое значение из стека присваивается ор2.

#define MAXVAL 100	/^максимальная глубина стека*/
int sp = 0;	/* позиция следующего свободного */
	/* элемента стека*/
double val[MAXVAL];	/* стек */
/* push: поместить f	в стек */
void push(double f) { if(sp < MAXVAL)
val[sp++] = f;
else
printf("\пОшиб	ка: стек полон, элемент %д не
помещается!\n", f); }
/*pop: взять значение с вершины стека.*/
double pop(void) { if(sp > 0)
return val[--s	р];
else { printf("\пОшиб
ка! Стек пуст. \п");
return 0.0; } }

Стек и индекс стека которые должны быть доступны для push и pop определены вне этих функций. Но так как в main не используют ни стек, ни индекс, то они скрыты от main.

Займемся реализацией getop — функции, получающей следующий оператор или операнд. Требуется пропустить пробелы и табуляции; если следующая литера — не цифра и не десятичная точка, то выдать ее; в противном случае накопить цепочку цифр с десятичной точкой, если она есть, и выдать признак числа NUNBER в качестве результата.

int getch(void); void unGetch(int);

/* Getop() получает следующий int Getop(char s[])

{

int i = 0; int c; int next; /*size_t len;*/

/* пропуск пробела */ while((s[0] = с = getch()) s[l] = '\0';

if(isalpha(c))

{

i = 0;

while(isalpha(s[i++] =

с = getch(); s[i - 1] = '\0'; if(c!= EOF)

unGetch(c); return IDENTIFIER;

оператор или операнд */

с == '\t');

))

/* He число, но, возможно, if(!isdigit(с) && с!= '.' return с;

if(с == '-')

{

next = getch();

if(!isdigit(next) && ne

{

return c;

}

с = next;

} else

с = getch();

while(isdigit(s[++i] = c))

с = getch();
if(c =='.') /* н

while(isdigit(s[++i] =

содержит унарный минус */ && с!= '-')

t! =

капливаем дробную часть */ = getch()))

ПО

	r
	s[i] =	'\0';
	if(c!=	EOF)
	unGetch(c);
	return	NUMBER;
}
s[i	]='\0';
if	(c!=EOF)
ung	etch (c);
ret	urn NUMBER	•
}

Как работают функции getch и ungetchl Во многих случаях программа не может определить прочла ли она все, что требуется, пока не прочтет лишнего. Поэтому getch читает очередную литеру из ввода, ungetch отправляет «лишнюю» литеру назад.

Поскольку функции совместно используют буфер и индекс, то они являются внешними по отношению к ним.

#с!е	;fine BUFSIZE 100
char buf[BUFSIZE];
int	. bufp = 0;
/*	Getch: получить символ. *	/
int { }	. getch(void)
return (bufp > 0)? buf [-	-bufp]:	getchar	О;
/*	unGetch: поместить символ	назад	в стек.	*/
voi {	о! unGetch (int с)
if(bufp >= BUFSIZE)
	printf(" \nUnGetch: слишком много символов.\n");
	else
}	buf[bufp++] = c;

Функции showTop, dublicate, swapltem, clearStack и dealWithName.

void showTop(void)

if(sp > 0)

printf("На вершине стека лежит: %8g\n", val[sp-l]); else

printf("Стек пуст!\п"); }

void duplicate(void)

{

double temp = pop();

push(temp); push(temp);

void swapltems(vo

{

double iteml = double item2 =

push(iteml); push(item2);

id)

pop(); pop();

void clearStack(void)

{

sp = 0;

}

/^Функция работы с математическими функциями.*/ void dealWithName(char s[])

{

double op2;

if(0 == strcmp(s, "sin"))

push(sin(pop())); else if(0 == strcmp(s, "cos"))

push(cos(pop ())); else if (0 == strcmp(s, "exp"))

push(exp(pop ())); else if(!strcmp(s, "pow"))

{

op2 = pop ();

push(pow(pop (), op2));

}

else

printf("Функция %s не поддерживаетсяО.\n", s); }

Связанный список является простейшим типом данных динамической структуры. Компоненты связанного списка можно помещать и исключать произвольным образом [1,3,8,11]. Графическое представление связанного списка показано на рис. 2.1.

Элемент списка называется узлом. Каждый узел содержит два поля: поле информации info и поле следующего адреса ptrn. Поле адреса хранит указатель на следующий элемент. Доступ к списку осуществляется через указатель 1st, который содержит адрес первого элемента. Поле адреса последнего элемента хранит нулевое значение NULL. Пустой список инициализируется как 1st = NULL.

1st|					ptrn =	NULL
[nfo	ptrn	—^	info	ptrn		... —+■	Info	ptrn|

Рис. 2.1

Введем обозначения [11]: пусть р — указатель на элемент списка; тогда mfo(p) — ссылка на информационную часть элемента; ptrn(/?) — ссылка на адрес следующего элемента; р = getnode() — выделение участка оперативной памяти под элемент списка; freenode(p) — освобождение участка оперативной памяти, отведенного под элемент списка.

Дата добавления: 2014-11-29