Множество (тип данных)

Множество — тип и структура данных в информатике, является реализацией математического объекта множество.

Данные типа множество позволяют хранить ограниченное число значений определённого типа без определённого порядка. Повторение значений, как правило, недопустимо. За исключением того, что множество в программировании конечно, оно в общем соответствует концепции математического множества. Для этого типа в языках программирования обычно предусмотрены стандартные операции над множествами.

В зависимости от идеологии, разные языки программирования рассматривают множество как простой или сложный тип данных.

Реализации

Множество в Паскале

В языке Паскаль множество — составной тип данных, хранящий информацию о присутствии в множестве объектов любого счетного типа. Мощность этого типа определяет размер множества — 1 бит на элемент. В Turbo Pascal есть ограничение на 256 элементов, в некоторых других реализациях это ограничение ослаблено.

Пример работы с множествами:

type 
  {определяем базовые для множеств перечислимый тип и тип-диапазон}
  colors = (red,green,blue);
  smallnumbers = 0..10;
  {определяем множества из наших типов}
  colorset = set of colors;
  numberset = set of smallnumbers;
  {можно и не задавать тип отдельно}
  anothernumberset = set of 0..20;

{объявляем переменные типа множеств}
var 
  nset1,nset2,nset3:numberset;
  cset:colorset;
begin
  nset1 := [0,2,4,6,8,10]; {задаем в виде конструктора множества}
  cset  := [red,blue];     {простым перечислением элементов}
  nset2 := [1,3,9,7,5];    {порядок перечисления неважен}
  nset3 := [];             {пустое множество}
  include(nset3,7);        {добавление элемента}
  exclude(nset3,7);        {исключение элемента}
  nset1 := [0..5];         {возможно задавать элементы диапазоном}
  nset3 := nset1 + nset2;  {объединение}
  nset3 := nset1 * nset2;  {пересечение}
  nset3 := nset1 - nset2;  {разность}
  if (5 in nset2) or       {проверка на вхождение элемента}
    (green in cset) then
    {…}
end.

Множество в C++

Пример программы, использующей структуру set для реализации каталогов:

vector <string> vec;

void f(vector <string> vec1, int level) {
	set <string> sett;
	for (int i = 0; i < vec1.size(); i++) {
		int k = vec1[i].find('/');
		if (k != string::npos) {
			string s1 = vec1[i].substr(0, k);
			sett.insert(s1);
		}
	}
	
	for (set <string> :: iterator it = sett.begin(); it != sett.end(); it++) {
		vector <string> vec2;
		for (int i = 0; i < vec1.size(); i++) {
			int k = vec1[i].find('/');
			if (k != string::npos && vec1[i].substr(0, k) == (*it)) {
				string s1 = vec1[i];
				s1.erase(0, k + 1);
				vec2.push_back(s1);
			}
		}
		for (int i = 0; i < level; i++) {
			cout << '+';
		}
		cout << *it << endl;
		f(vec2, level + 1);
	}
}


int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		s += '/';
		vec.push_back(s);
	}

	f(vec, 0);
	return 0;
}

Отрывок, характеризующий Множество (тип данных)

«Что же это? я не подвигаюсь? – Я упал, я убит…» в одно мгновение спросил и ответил Ростов. Он был уже один посреди поля. Вместо двигавшихся лошадей и гусарских спин он видел вокруг себя неподвижную землю и жнивье. Теплая кровь была под ним. «Нет, я ранен, и лошадь убита». Грачик поднялся было на передние ноги, но упал, придавив седоку ногу. Из головы лошади текла кровь. Лошадь билась и не могла встать. Ростов хотел подняться и упал тоже: ташка зацепилась за седло. Где были наши, где были французы – он не знал. Никого не было кругом.
Высвободив ногу, он поднялся. «Где, с какой стороны была теперь та черта, которая так резко отделяла два войска?» – он спрашивал себя и не мог ответить. «Уже не дурное ли что нибудь случилось со мной? Бывают ли такие случаи, и что надо делать в таких случаях?» – спросил он сам себя вставая; и в это время почувствовал, что что то лишнее висит на его левой онемевшей руке. Кисть ее была, как чужая. Он оглядывал руку, тщетно отыскивая на ней кровь. «Ну, вот и люди, – подумал он радостно, увидав несколько человек, бежавших к нему. – Они мне помогут!» Впереди этих людей бежал один в странном кивере и в синей шинели, черный, загорелый, с горбатым носом. Еще два и еще много бежало сзади. Один из них проговорил что то странное, нерусское. Между задними такими же людьми, в таких же киверах, стоял один русский гусар. Его держали за руки; позади его держали его лошадь.
«Верно, наш пленный… Да. Неужели и меня возьмут? Что это за люди?» всё думал Ростов, не веря своим глазам. «Неужели французы?» Он смотрел на приближавшихся французов, и, несмотря на то, что за секунду скакал только затем, чтобы настигнуть этих французов и изрубить их, близость их казалась ему теперь так ужасна, что он не верил своим глазам. «Кто они? Зачем они бегут? Неужели ко мне? Неужели ко мне они бегут? И зачем? Убить меня? Меня, кого так любят все?» – Ему вспомнилась любовь к нему его матери, семьи, друзей, и намерение неприятелей убить его показалось невозможно. «А может, – и убить!» Он более десяти секунд стоял, не двигаясь с места и не понимая своего положения. Передний француз с горбатым носом подбежал так близко, что уже видно было выражение его лица. И разгоряченная чуждая физиономия этого человека, который со штыком на перевес, сдерживая дыханье, легко подбегал к нему, испугала Ростова. Он схватил пистолет и, вместо того чтобы стрелять из него, бросил им в француза и побежал к кустам что было силы. Не с тем чувством сомнения и борьбы, с каким он ходил на Энский мост, бежал он, а с чувством зайца, убегающего от собак. Одно нераздельное чувство страха за свою молодую, счастливую жизнь владело всем его существом. Быстро перепрыгивая через межи, с тою стремительностью, с которою он бегал, играя в горелки, он летел по полю, изредка оборачивая свое бледное, доброе, молодое лицо, и холод ужаса пробегал по его спине. «Нет, лучше не смотреть», подумал он, но, подбежав к кустам, оглянулся еще раз. Французы отстали, и даже в ту минуту как он оглянулся, передний только что переменил рысь на шаг и, обернувшись, что то сильно кричал заднему товарищу. Ростов остановился. «Что нибудь не так, – подумал он, – не может быть, чтоб они хотели убить меня». А между тем левая рука его была так тяжела, как будто двухпудовая гиря была привешана к ней. Он не мог бежать дальше. Француз остановился тоже и прицелился. Ростов зажмурился и нагнулся. Одна, другая пуля пролетела, жужжа, мимо него. Он собрал последние силы, взял левую руку в правую и побежал до кустов. В кустах были русские стрелки.