Студопедия — Пример реализации односвязного списка с помощью массива структур
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Пример реализации односвязного списка с помощью массива структур






В рассматриваемом примере используется следующая структура

 

struct list

{ char book;

list *next; };

 

Предполагается, что память, отводимая под элемент списка, выделяется динамически, поэтому при реализации списков его длина ограничивается только доступным объёмом памяти. Информационное поле представляет собой символьную переменную по имени book. Признаком последующего элемента списка является наличие поля next, а признаком последнего элемента списка – равенство на NULL этого поля.

Следующая программа реализует операции:

· создает пустой список;

· добавляет элементы в список в алфавитном порядке;

· удаляет элементы из списка;

· проверяет, является ли список пустым;

· выводит список на экран.

Функция main организует запуск программы instructions для ввода кода необходимой операции над списком и вызывает функцию, которая выполняет эту операцию.

Операцию добавления элемента в список в алфавитном порядке выполняет функция insert, операцию удаления – функция del, операцию проверки, является ли список пустым, – IsEmpty, вывод списка на экран – printList.

 

Пример 12.1

#include " stdafx.h"

# include < stdio.h>

# include < stdlib.h>

struct list

{

char book;

struct list *next;

};

typedef struct list ListNode;

typedef ListNode *ListNodePtr;

void insert (ListNodePtr*, char);

char del (ListNodePtr*, char);

int IsEmpty (ListNodePtr);

void printList (ListNodePtr);

void instructions (void);

int main ()

{ ListNodePtr start = NULL;

int choice;

char elem;

instructions(); // вывести меню

printf("? ");

scanf(" %d", & choice);

while (choice! =3)

{

switch (choice)

{

case 1: /*Добавить значение в список*/

printf (" Enter an character: ");

scanf(" \n%c", & elem);

insert(& start, elem);

printList (start);

break;

case 2: /*Удалить значение из списка*/

if (! IsEmpty(start))

{ printf(" Enter character to be deleted: ");

scanf(" \n%c", & elem);

if (del(& start, elem))

{ printf(" %c deleted.\n", elem);

printList(start); }

else

printf(" %c not found.\n", elem);

}

else

printf(" List is empty.\n");

break;

default:

printf (" Invalid choice.\n");

instructions();

break;

}

printf("? ");

scanf(" %d", & choice);

}

printf(" End of run.\n");

return 0;

}

/*Вывести инструкции*/

void instructions(void)

{ printf(" Enter choice: \n"

" 1 insert an element into the list.\n"

" 2 delete an element from the list.\n"

" 3 end program.\n");

}

/*Вставить в список новое значение в алфавитном порядке */

void insert (ListNodePtr *s, char value)

{ ListNodePtr newP, previous, current;

NewP = (ListNodePtr) malloc (sizeof(ListNode));

if (newP! =NULL)

{ /*есть ли место? */

newP-> book =value;

newP-> next=NULL;

previous=NULL;

current=*s;

while (current! =NULL & & value > current-> book)

{ previous=current;

current=current-> next; }

if(previous==NULL)

{ newP-> next=*s;

*s=newP; }

else

{ previous-> next = newP;

newP-> next = current; }

}

else

printf(" %c not inserted. No memory available.\n", value);

}

/*Удалить элемент списка*/

char del (ListNodePtr *s, char value)

{ ListNodePtr previous, current, temp;

if (value == (*s)-> book)

{ temp=*s;

*s=(*s)-> next; // отсоединить узел

free(temp); // освободить отсоединенный узел

return value;

}

else

{ previous=*s;

current=(*s)-> next;

while (current! =NULL & & current-> book! = value)

{ previous=current; /*перейти.......*/

current=current-> next; /*...к следующему*/

}

if (current! =NULL)

{ temp=current;

previous-> next=current-> next;

free(temp);

return value; }

}

return '\0';

}

/*Возвратить 1, если список пуст, 0 в противном случае*/

int IsEmpty(ListNodePtr s)

{

return s==NULL;

}

/*Распечатать список*/

void printList (ListNodePtr current)

{

if (current==NULL)

printf(" The list is empty.\n");

else

{ printf(" The list is: \n");

while (current! =NULL)

{ printf(" %c--> ", current-> book);

current=current-> next; }

printf(" NULL\n");

}

}

 







Дата добавления: 2014-11-10; просмотров: 1050. Нарушение авторских прав; Мы поможем в написании вашей работы!



Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Методика обучения письму и письменной речи на иностранном языке в средней школе. Различают письмо и письменную речь. Письмо – объект овладения графической и орфографической системами иностранного языка для фиксации языкового и речевого материала...

Классификация холодных блюд и закусок. Урок №2 Тема: Холодные блюда и закуски. Значение холодных блюд и закусок. Классификация холодных блюд и закусок. Кулинарная обработка продуктов...

ТЕРМОДИНАМИКА БИОЛОГИЧЕСКИХ СИСТЕМ. 1. Особенности термодинамического метода изучения биологических систем. Основные понятия термодинамики. Термодинамикой называется раздел физики...

Броматометрия и бромометрия Броматометрический метод основан на окислении вос­становителей броматом калия в кислой среде...

Метод Фольгарда (роданометрия или тиоцианатометрия) Метод Фольгарда основан на применении в качестве осадителя титрованного раствора, содержащего роданид-ионы SCN...

Потенциометрия. Потенциометрическое определение рН растворов Потенциометрия - это электрохимический метод иссле­дования и анализа веществ, основанный на зависимости равновесного электродного потенциала Е от активности (концентрации) определяемого вещества в исследуемом рас­творе...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия