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

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

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");

}

}

Варианты индивидуальных заданий.

Доп. теория Дейтел:12.4, стр. 531

Требование: использование меню и функций.

Написать следующие функции работы со списком:

countList – Функцию подсчета числа элементов;

findMax – Функцию поиска максимального элемента списка;

findMin - Функцию поиска максимального элемента списка;

deleteDouble – Функцию удаления повторяющихся элементов

DeleteList –Функцию удаления списка;

1) добавления элемента в список (по алфавиту);

2) удаление элемента из списка;

Выход.

4) …

1. Список «Автосервис»: регистрационный номер автомобиля, марка, пробег, сумма ремонта

2. Список «Сотрудник»: фамилия, имя, отчество; должность; год рождения; заработная плата.

3. Список «Государство»: название; столица; численность населения; занимаемая площадь.

4. Список «Человек»: фамилия, имя, отчество; домашний адрес; номер телефона; возраст.

5. Список «Читатель»: Фамилия И.О., номер читательского билета, название книги, срок возврата.

6. Список «Школьник»: фамилия, имя, отчество; класс; номер телефона; средний балл.

7. Список «Студент»: фамилия, имя, отчество; домашний адрес; группа; рейтинг.

8. Список «Покупатель»: фамилия, имя, отчество; домашний адрес; номер телефона; номер кредитной карточки.

9. Список «Пациент»: фамилия, имя, отчество; домашний адрес; номер медицинской карты; номер страхового полиса.

10. Список «Информация»: носитель; объем; название; автор.

11. Список «Клиент банка»: Фамилия И.О., номер счета, сумма на счете, дата последнего изменения.

12. Список «Склад»: наименование товара, цена, количество, процент торговой надбавки.

13. Список «Авиарейсы»: номер рейса, пункт назначения, время вылета, дата вылета, стоимость билета.

14. Список «Вокзал»: номер поезда, пункт назначения, дни следования, время прибытия, время стоянки.

15. Список «Кинотеатр»: название кинофильма, сеанс, стоимость билета, количество зрителей.