Задание. Написать программу по работе сосвязанным списком, который заполнен числами, кратными вашему порядковому номеру в журнале

Написать программу по работе сосвязанным списком, который заполнен числами, кратными вашему порядковому номеру в журнале. Эти числа должны быть отсортированы в порядке убывания (способ сортировки выбирается по желанию).

Порядок выполнения работы

Написать программу, демонстрирующую работу с односвязным списком. Описать некоторые функции для работы с ним.

 

#include < stdio.h>

#include < alloc.h>

/* Структура для описания односвязного (однонаправленного) списка*/

typedef int ELEMTYPE;

typedefstruct node { ELEMTYPE elem; struct node * next; } *LIST;

/* Инициализация списка/ как пустого */

LIST init(LIST *l)

{ return *l=NULL; }

/* Добавление элемента в голову списка */

LIST cons (ELEMTYPE e, LIST l)

{ LIST news=(LIST)malloc(sizeof(struct node));

news-> elem=e;

news-> next=l;

returnnews;

}

/* Печать списка целых */

voidprintlist(LIST l)

{ printf(" \n");

while (l! =NULL) (printf(" %5d", l-> elem); l=l-> next;; }

}

 

/* Добавление элемента в конец списка */

LIST last(ELEMTYPE e, LIST l)

{ LIST head;

if (! l) { l=(LIST)malloc(sizeof(struct node));

l-> elem=e;

l-> next=NULL;

return l;

}

else { head=l;

while (l-> nexti=NULL) l=l-> next;

l-> next= (LIST) malloc (sizeof (struct node));

l=l-> next;

l-> elem=e;

l-> next=NULL;

return head;

}

}

 

/* Удвоить все вхождения данного элемента в список */

 

LIST doubleE(ELEMTYPE E, LIST l)

{ LIST head=l, tmp;

while (l)

if (l-> elem==E)

{/* вставить после него */

tmp=l-> next;

l-> next=(LIST)malloc(sizeof(struct node));

l-> next-> elem=l-> elem;

l-> next-> next=tmp;

l=tmp;

}

else l=l-> next;

return head;

}

 

/* Удалить из списка все вхождения заданного элемента */

LIST delE(ELEMTYPE E, LIST l)

{ LIST head=l, w;

if (! l) return head;

while (l-> next)

if (l-> next-> elem==E) {w=l-> next; l-> next=l-> next-> next; free(w); }

else l=l-> next;

return head;

}

/* Тестирующая программа */

voidmain(void)

{

LIST p;

init(& p);

p=last(0, p); p=cons(l, p); p==cons (2, p); p=cons(3, p); p=last(4, p);

p=last(5, p); p=last(6, p); p=cons(2, p); p=last(4, p);

printlist(p);

p=doubleE(2, p);

printlist(p);

p=doubieE(4, p);

printlist(p);

p=delE(4/p);

printlist (p);

}

 

Контрольные вопросы

1. Что представляют собой связанные списки и какие виды связанных списков вы знаете?

2. К каким структурам данным относятся связанные списки?

3. С помощью какой структуры данных можно наиболее эффективно решить задачу сортировки и почему?

4. Что представляет собой элемент динамической структуры данных?

5. Какие операции можно выполнять над списками?

Требования к отчету

Отчет должен содержать:

1. Тему и цель работы.

2. Задание.

3. Программу на языке программирования C++.

4. Скриншоты с результатами выполнения программы.

5. Ответы на контрольные вопросы.

6. Выводы о проделанной работе.

 

Лабораторная работа № 7

Стеки

Цель

Формирование навыков организации данных в виде стеков на языке программирования высокого уровня.