Создание набора ADT в C

Я пытаюсь создать ADT.Создание набора ADT в C

Это динамический набор конечных элементов. Он должен быть реализован с использованием массивов и связанных списков.

Некоторые операции включают add(set, x) и remove(set, x).

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

Тем не менее, я не уверен относительно структуры этого типа данных. Что я должен включить?

struct test { 
    int x; 
    char y; 
};

Нечто подобное? Или предположим, что я делаю набор эксклюзивным для целых чисел, какова будет структура данных?

Справка была бы принята с благодарностью. Благодаря!

источник

2014-01-10 Anonymous

Нужна дополнительная информация. Вы думаете о конечном множестве в математическом смысле (где допускаются повторяющиеся элементы) или 'set()' как в Python/Java/и т. Д. (только имеет уникальные элементы)? Вы пытаетесь выбрать структуру данных для оптимизации операций 'add()' и 'remove()' или, возможно, других, таких как 'union()' или 'intersect()'? Почему массивы * и * связаны списки? У вас есть много структур данных на выбор, почему «нужно» это реализовать с ними? – Keeler

Я думаю в математическом смысле. В принципе, все, что мне нужно сделать, это добавить или удалить элемент, а затем попробовать такие функции, как check_if_element_is_present(), union(), intersection(), cardinality() ... –

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

Поскольку это для школы, я не собираюсь дать вам реализацию, но я укажу вам в праве направление. Использование массивов и списков хеш-таблиц криков. См. this answer за хорошую информацию.

Для простоты предположим, что это набор целых чисел. По существу, вам нужен массив hash_table из N 'buckets', т. Е. Списки. Чтобы добавить элемент x, вы делаете hash_table[hash(x) % N], чтобы получить «ведро» (список) x, и нужно добавить его в этот список, если его еще нет в списке.

Чтобы удалить x, сделайте hash_table[hash(x) % N], чтобы получить ваше ведро, и удалите x, если он есть.

Если вы можете их реализовать, search(set, x) тривиально. Вы также можете попробовать реализовать union(setA, setB), intersect(setA, setB), difference(setA, setB), isSubset(setA, setB) и т. Д. Вы также можете ознакомиться с the Wikipedia article on the Set ADT и выполнить запись в The Algorithm Design Manual, которая содержит ссылки на реализации внизу.

Удачи и счастливого кодирования. Если вы застряли, всегда в порядке спрашивать здесь о SO, просто отправьте код в следующий раз. :)

источник

2014-01-10 16:57:26 Keeler

Aaa, огромное спасибо! Действительно полезный и информативный. Я подниму голову. Оценил! –

Это принцип структуры, вы можете поместить все тип переменной, которую вы хотите в нем ..

Я думаю, что вы хотите создать массив междунар. Декларирование как:

int tab["number of int you want"];

И доступ к нему вроде:

tab["number of case of the int you want to access"];

источник

2014-01-10 14:37:43 Laykker

Если бы я только сделал набор чисел, я бы потерял цель структуры, нет? –

Структура похожа на переменную. Вы можете поместить в него «int», «char» и т. Д. И посмотреть или изменить значение этой структуры в вашем коде. – Laykker

О, да, имеет смысл. В принципе, массив является структурой, например. –

Создание набора ADT в C

ответ

Смежные вопросы