Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections;
- class HelloWorld {
- static void Main() {
- Console.WriteLine("test list");
- test_list();
- Console.WriteLine("test set");
- test_set();
- }
- static void test_list() { /********** TEST LIST **********/
- //1
- Console.WriteLine("1 test");
- Console.WriteLine("Создайте пустой список S1. Добавьте элемент 1 в голову, добавьте элемент 10 в хвост. Выведите S1 на экран (используя функцию Print)");
- List<int> s1 = new List<int>();
- s1.push_front(1);
- s1.push(10);
- Console.Write("s1 = ");
- s1.Print();
- //2
- Console.WriteLine("2 test");
- Console.WriteLine("Создайте список S2 из 6 случайных чисел. Выведите список S2 на экран, используя потоковый вывод. Найдите в S2 max и min элемент. Отсортируйте S2.");
- List<int> s2 = new List<int>();
- Random rnd = new Random();
- for(int i = 0; i < 6; i++) {
- s2.push(rnd.Next() % 15);
- }
- Console.Write("s2 = ");
- s2.Print();
- // a[1] = 3;
- Console.WriteLine("min: "+ s2.min().getData()+ " max: "+ s2.max().getData());
- s2 = s2.mergesort();
- Console.Write("s2 = ");
- s2.Print();
- //3
- Console.WriteLine("3 test");
- Console.WriteLine("Найдите в S2 2-й элемент и выведите его на экран. Удалите 2-й элемент списка S2.");
- Console.WriteLine(s2[1].getData());
- s2.delete(1);
- Console.Write("s2 = ");
- s2.Print();
- //4
- Console.WriteLine("4 test");
- Console.WriteLine("Найдите в S2 6-й элемент (т.е. убедитесь, что в списке осталось меньше 6 элементов). Удалите элемент из хвоста S2.");
- Console.Write("s2[5] = ");
- Console.WriteLine(s2[5]);
- s2.pop();
- Console.Write("s2 = ");
- s2.Print();
- //5
- Console.WriteLine("5 test");
- Console.WriteLine("Создайте пустой список S3. Инициализируйте его значением S1. Проверьте равенство списков S1 и S3. Проверьте, есть ли в S3 элемент 15.");
- List<int> s3 = s1.clone();
- Console.Write("s3 = ");
- s3.Print();
- Console.Write("s3 == s1 ");
- Console.WriteLine(s3 == s1);
- Console.WriteLine("s3.find(15) == null ");
- Console.WriteLine(s3.find(15) == null);
- //6
- Console.WriteLine("6 test");
- Console.WriteLine("Удалите элемент из головы списка S3. Удалите из списка S3 элемент 10. Выведите S3 на экран. Проверьте S3 на пустоту.");
- s3.pop_front();
- s3.delete_value(10);
- Console.Write("s3 = ");
- s3.Print();
- Console.Write("s3.IsNull() ");
- Console.WriteLine(s3.IsNull());
- // 7
- Console.WriteLine("7 test");
- Console.WriteLine("Создайте последовательность из 6 случайных чисел, меньших 20. Превратите ее в список S4 и выведите его на экран. Проверьте, есть ли в S4 элемент 25. Добавьте элемент 25 четвертым в список.");
- List<int> s4 = new List<int>();
- for(int i = 0; i < 6; i++) {
- s4.push(rnd.Next() % 20);
- }
- Console.Write("s4 = ");
- s4.Print();
- Console.Write("s4.find(25) == null ");
- Console.WriteLine(s4.find(25) == null);
- s4.insert(25, 3);
- Console.Write("s4 = ");
- s4.Print();
- //8
- Console.WriteLine("8 test");
- Console.WriteLine("Создайте список S5, проинициализировав его при создании списком S2. Выведите S5 на экран. Проверьте, есть ли в S5 элемент 4 и если есть – удалите его, если нет – добавьте элемент 4 в хвост.");
- List<int> s5 = s2.clone();
- Console.Write("s5 = ");
- s5.Print();
- Console.Write("s5.find(4) == null ");
- Console.WriteLine(s5.find(4) == null);
- if (s5.find(4) != null) {
- s5.delete_value(4);
- }
- else {
- s5.push(4);
- }
- Console.Write("s5 = ");
- s5.Print();
- //9
- Console.WriteLine("9 test");
- Console.WriteLine("Измените S5, записав в него 4 числа: 11, 12, 13, 14 (числа вводятся с клавиатуры). Сравните S5 и S4.");
- s5.read_input();
- Console.Write("s5 = ");
- s5.Print();
- Console.Write("s5 == s4 ");
- Console.WriteLine(s5 == s4);
- //10
- Console.WriteLine("10 test");
- Console.WriteLine("Добавьте в хвост S5 список S4. Добавьте в голову S5 список S1.");
- Console.Write("s5 = ");
- s5.Print();
- s5 = s5 + s4;
- Console.Write("(s5 + s4) s5 = ");
- s5.Print();
- s5 = s1 + s5;
- Console.Write("(s1 + s5) s5 = ");
- s5.Print();
- }
- static void test_set() { /********** TEST SET **********/
- //1
- Console.WriteLine("1 test");
- Console.WriteLine("Создайте множество S1, из 10 случайных чисел. Выведите S1 на экран");
- Set<int> s1 = new Set<int>();
- Random rnd = new Random();
- int j = 0;
- while(j < 10) {
- int val = rnd.Next(20);
- if (s1.find(val) == null) {
- s1.push(val);
- j += 1;
- }
- }
- Console.Write("s1 = ");
- s1.Print();
- //2
- Console.WriteLine("2 test");
- Console.WriteLine("Создайте множество S2 и инициализируйте его (при создании) значением S1. Выведите S2 на экран (используйте потоковый вывод). Проверьте равенство множеств S1 и S2.");
- Set<int> s2 = new Set<int>(s1.clone());
- Console.Write("s2 = ");
- s2.Print();
- Console.Write("s1 == s2 ");
- Console.WriteLine(s1 == s2);
- //3
- Console.WriteLine("3 test");
- Console.WriteLine("Проверьте, есть ли в S1 элемент 5. Создайте множество S3, которое получается удалением/добавлением из S1 элемента 5. Проверьте, что S1 и S3 – не равны.");
- Console.Write("s1.find(5) != null ");
- Console.WriteLine(s1.find(5) != null);
- Set<int> s3 = new Set<int>(s1.clone());
- if (s3.find(5) != null) {
- s3.delete_value(5);
- }
- else {
- s3.push(5);
- }
- Console.Write("s3 = ");
- s3.Print();
- Console.Write("s1 == s3 ");
- Console.WriteLine(s1 == s3);
- //4
- Console.WriteLine("4 test");
- Console.WriteLine("Создайте пустое множество S4. Проверьте его на пустоту. Добавьте в S4 последовательно числа 5, 10, 15, 5. Выведите S4 на экран.");
- Set<int> s4 = new Set<int>();
- Console.Write("s4.IsNull() ");
- Console.WriteLine(s4.IsNull());
- s4.push(5);
- s4.push(10);
- s4.push(15);
- s4.push(5);
- Console.Write("s4 = ");
- s4.Print();
- //5
- Console.WriteLine("5 test");
- Console.WriteLine("Создайте пустое множество S5. Инициализируйте его множеством S4. Проверьте, что во множестве S5 есть элемент 15 и удалите его. Выведите получившееся множество на экран.");
- Set<int> s5 = new Set<int>(s4);
- Console.Write("s5 = ");
- s4.Print();
- Console.Write("s5.find(15) != null ");
- Console.WriteLine(s5.find(15) != null);
- s5.delete_value(15);
- Console.WriteLine("15 deleted");
- Console.Write("s5 = ");
- s5.Print();
- //6
- Console.WriteLine("6 test");
- Console.WriteLine("Создайте список T, из 20 случайных чисел. Выведите T на экран. Создайте из T множество S6. Выведите S6 на экран. Определите количество элементов в S6.");
- List<int> t = new List<int>();
- for(int i = 0; i < 20; i++) {
- t.push(rnd.Next() % 30);
- }
- Console.Write("t = ");
- t.Print();
- Set<int> s6 = new Set<int>(t);
- Console.Write("s6 = ");
- s6.Print();
- Console.Write("s6.len() = ");
- Console.WriteLine(s6.len());
- //7
- Console.WriteLine("7 test");
- Console.WriteLine("Найдите S7 – дополнение S6 до универсального. Найдите множество S8=S7∩S6.");
- Console.WriteLine("Будем считать, что множество состоит из 30 эелементов");
- Set<int> s7 = new Set<int>();
- for(int i = 0; i < 30; i++) {
- if (s6.find(i) == null) s7.push(i);
- }
- Console.Write("s7 = ");
- s7.Print();
- Set<int> s8 = Set<int>.intersection(s7, s6);
- Console.Write("s8 = ");
- s8.Print();
- //8
- Console.WriteLine("8 test");
- Console.WriteLine("Создайте множество \nS9={1,3,5,7,9,11,13,15,17,19,21,23,25,27,29}\n(используйте потоковый ввод). Найдите V1 =S7 ∩ S9, V2 = S7 ∪ S9, V3 = S7 \\ S9.");
- Set<int> s9 = new Set<int>();
- s9.read_input();
- Console.Write("s9 = ");
- s9.Print();
- Set<int> v1 = Set<int>.intersection(s7, s9);
- Console.Write("v1 = ");
- v1.Print();
- Set<int> v2 = Set<int>.union(s7, s9);
- Console.Write("v2 = ");
- v2.Print();
- Set<int> v3 = Set<int>.difference(s7, s9);
- Console.Write("v3 = ");
- v3.Print();
- //9
- Console.WriteLine("9 test");
- Console.WriteLine("Измените V1, объединив его с V3. Сравните V1 с S7.");
- v1 = Set<int>.union(v1, v3);
- Console.Write("v1 = ");
- v1.Print();
- Console.Write("v1 == v7 ");
- Console.WriteLine(v1 == s7);
- //10
- Console.WriteLine("10 test");
- Console.WriteLine("Измените множество V2, заменив его разностью V2 и V3. Сравните V2 с S9");
- v2 = Set<int>.difference(v2, v3);
- Console.Write("v2 = ");
- v2.Print();
- Console.Write("v2 == s9 ");
- Console.WriteLine(v2 == s9);
- }
- }
- class Node {
- protected int data;
- private Node next;
- public void nextSet(Node a) {
- next = a;
- }
- public Node nextGet() {
- return next;
- }
- public Node(int d) {
- data = d;
- nextSet(null);
- }
- public Node clone()
- {
- return new Node(data);
- }
- public Node setData(int newdata) {
- data = newdata;
- }
- public Node getData() {
- return data;
- }
- }
- class List {
- protected Node head;
- // Конструкторы
- public List(int d) {
- head = new Node(d);
- }
- public List(Node d) {
- head = d;
- }
- public List() {
- head = null;
- }
- public List clone() {
- if (head == null) return new List();
- List cl = new List(new Node(head.getData()));
- Node curr = head;
- Node curr2 = cl.head;
- while(curr.nextGet() != null) {
- curr = curr.nextGet();
- curr2.nextSet(new Node(curr.getData()));
- curr2 = curr2.nextGet();
- }
- return cl;
- }
- public void push(int d) {
- Node temp = new Node(d);
- if (IsNull()) {
- head = temp;
- return;
- }
- Node tail = head;
- while(tail.nextGet()!= null) {
- tail = tail.nextGet();
- }
- tail.nextSet(temp);
- }
- public void push_front(int d) {
- Node temp = new Node(d);
- if (IsNull()) {
- head = temp;
- return;
- }
- temp.nextSet(head);
- head = temp;
- }
- public Node pop() {
- if (head == null) {return null;}
- Node tail = head.nextGet();
- if (head.nextGet()== null) {
- head = null;
- return tail;
- }
- Node prev = head;
- while(tail.nextGet()!= null) {
- tail = tail.nextGet();
- prev = prev.nextGet();
- }
- Node res = tail;
- tail = prev;
- tail.nextSet(null);
- return res;
- }
- public Node pop_front() {
- if (IsNull()) {return null;}
- Node res = head;
- if (head.nextGet()== null) {
- Node temp = new Node(head.getData());
- head = null;
- return temp;
- }
- else {
- head = head.nextGet();
- }
- return res;
- }
- public Node insert(int a, int n) {
- Node ins = new Node(a);
- Node cur = head;
- if (cur == null) {
- if (n == 0) {
- head = ins;
- return ins;
- }
- else return null;
- }
- for(int i = 1; i < n; i++) {
- if (cur.nextGet()== null) return null;
- cur = cur.nextGet();
- }
- ins.nextSet(cur.nextGet());
- cur.nextSet(ins);
- return ins;
- }
- public Node insert_after_key(int a, int key) {
- Node ins = new Node(a);
- Node cur = find(key);
- if (cur == null) return null;
- ins.nextSet(cur.nextGet());
- cur.nextSet(ins);
- return ins;
- }
- public Node this[int n] {
- get {
- Node temp = head;
- for(int i = 0; i < n; i++) {
- if(temp == null) {return null;}
- temp = temp.nextGet();
- }
- return temp;
- }
- set {
- if (head == null && n == 0) {head = value; return;}
- Node temp = head;
- for(int i = 0; i < n; i++) {
- if(temp == null) {throw new NullReferenceException("List size is smaller than n");}
- temp = temp.nextGet();
- }
- temp.getData() = value.getData();
- }
- }
- public Node delete(int n) {
- if (head == null) return null;
- Node temp = head;
- Node prev = head;
- for(int i = 0; i < n; i++) {
- if (temp.nextGet() == null) return null;
- prev = temp;
- temp = temp.nextGet();
- }
- prev.nextSet(temp.nextGet());
- return temp;
- }
- public Node delete_value(int value) {
- if (head == null) return null;
- Node temp = head;
- Node prev = null;
- do {
- if (temp.getData().CompareTo(value) == 0) {
- if (prev == null) head = temp.nextGet();
- else prev.nextSet(temp.nextGet());
- return temp;
- }
- prev = temp;
- temp = temp.nextGet();
- } while(temp != null);
- return null;
- }
- public void delete_values(int value) {
- if (head == null) return;
- Node temp = head;
- Node prev = null;
- while (temp != null && temp.getData().CompareTo(value) == 0) {
- head = temp.nextGet();
- temp = head;
- }
- while (temp != null) {
- while (temp != null && temp.getData().CompareTo(value) != 0) {
- prev = temp;
- temp = temp.nextGet();
- }
- if (temp == null)
- return;
- prev.nextSet(temp.nextGet());
- temp = prev.nextGet();
- }
- }
- public Node find(int value) {
- if (IsNull()) {return null;}
- Node temp = head;
- while (temp != null) {
- if (temp.getData().CompareTo(value) == 0) {return temp;} //temp.data == value
- temp = temp.nextGet();
- }
- return temp;
- }
- public Node min() {
- if (IsNull()) {return null;}
- Node temp = head;
- Node min = head;
- while(temp != null) {
- if (min.detData().CompareTo(temp.getData()) > 0) {min = temp;}
- temp = temp.nextGet();
- }
- return min;
- }
- public Node max() {
- if (IsNull()) {return null;}
- Node temp = head;
- Node max = head;
- while(temp != null) {
- if (max.getData().CompareTo(temp.getData()) < 0) {max = temp;}
- temp = temp.nextGet();
- }
- return max;
- }
- public bool IsNull() {
- return head == null;
- }
- public void clear() {
- head = null;
- }
- public void read_input() {
- head = null;
- Console.Write("Enter number of nodes : ");
- int n = (int)Convert.ChangeType(Console.ReadLine(), typeof(int));
- Console.WriteLine(n);
- for (int i = 0; i < n; i++) {
- Node temp = (int)Convert.ChangeType(Console.ReadLine(), typeof(int));
- push(temp);
- Console.WriteLine("pushed " + temp);
- }
- }
- Node getmiddle() {
- if (head == null) return head;
- Node slow = head, fast = head;
- while(fast.nextGet()!= null && fast.nextGet().nextGet()!= null) {
- slow = slow.nextGet();
- fast = fast.nextGet().nextGet();
- }
- return slow;
- }
- static List merge(List left, List right) {
- if (left.IsNull()) return right;
- if (right.IsNull()) return left;
- List result = new List();
- if (left.head.getData().CompareTo(right.head.getData()) <= 0) {
- result = left;
- result.head.nextSet(merge(new List(left.head.nextGet()), right).head);
- }
- else {
- result = right;
- result.head.nextSet(merge(left, new List(right.head.nextGet())).head);
- }
- return result;
- }
- public List mergesort() {
- if (head == null || head.nextGet()== null) return (new List(head));
- Node middle = getmiddle();
- List middle_next = new List(middle.nextGet());
- middle.nextSet(null);
- List left = mergesort();
- List right = middle_next.mergesort();
- // Console.WriteLine("debug");
- // left.Print();
- // right.Print();
- List result = merge(left, right);
- // result.Print();
- head = result.head;
- return result;
- }
- public void Print() {
- if (IsNull()) {
- Console.Write("null\n");
- return;
- }
- Node temp = head;
- Console.Write("[" + temp.getData());
- temp = temp.nextGet();
- while(temp != null) {
- Console.Write(", " + temp.getData());
- temp = temp.nextGet();
- }
- Console.Write("]\n");
- }
- public static List operator + (List a, List b) {
- if (a.head == null) return b;
- if (b.head == null) return a;
- List result = a;
- Node temp = result.head;
- while(temp.nextGet()!= null) {
- temp = temp.nextGet();
- }
- temp.nextSet(b.head);
- return result;
- }
- public static bool operator == (List a, List b) {
- Node f = a.head;
- Node s = b.head;
- if (f == null ^ s == null) return false;
- if (f == null && s == null) return true;
- while(f.nextGet() != null && s.nextGet() != null) {
- if (f.getData().CompareTo(s.getData()) != 0) return false;
- f = f.nextGet();
- s = s.nextGet();
- }
- if (f.nextGet() == null ^ s.nextGet() == null) return false;
- return true;
- }
- public static bool operator != (List a, List b) {
- return !(a==b);
- }
- }
- class Set : List {
- public Set() {
- }
- public Set(Node a) {
- head = a.clone();
- }
- public Set(int a) {
- head = new Node(a);
- }
- public Set(List a) {
- head = a.clone()[0];
- delete_repetitions();
- }
- void delete_repetitions() {
- Node ptr1 = head;
- Node ptr2 = null;
- while (ptr1 != null && ptr1.nextGet() != null) {
- ptr2 = ptr1;
- while (ptr2.nextGet() != null) {
- if (ptr1.getData().CompareTo(ptr2.nextGet().getData()) == 0) ptr2.nextSet(ptr2.nextGet().nextGet());
- else ptr2 = ptr2.nextGet();
- }
- ptr1 = ptr1.nextGet();
- }
- }
- public new void push(int d) {
- if (base.find(d) == null)
- base.push(d);
- }
- public new void push_front(int d) {
- if (base.find(d) == null)
- base.push_front(d);
- }
- public new Node insert(int a, int n) {
- if (base.find(a) == null)
- return base.insert(a, n);
- return null;
- }
- public new Node insert_after_key(int a, int key) {
- if (base.find(a) == null)
- return base.insert_after_key(a, key);
- return null;
- }
- public new void read_input() {
- base.clear();
- Console.Write("Enter number of nodes : ");
- int n = (int)Convert.ChangeType(Console.ReadLine(), typeof(int));
- Console.WriteLine(n);
- for (int i = 0; i < n; i++) {
- Node temp = (int)Convert.ChangeType(Console.ReadLine(), typeof(int));
- push(temp);
- Console.WriteLine("pushed " + temp);
- }
- }
- public static Set union(Set a, Set b) {
- if (a.IsNull()) return (Set)b.clone();
- if (b.IsNull()) return (Set)a.clone();
- Set res = new Set(a.clone());
- foreach(Node item in b) {
- res.push(item.clone().getData());
- }
- return res;
- }
- public static Set intersection(Set a, Set b) {
- if (a.IsNull() && b.IsNull()) return null;
- Set res = new Set();
- foreach(Node item in b) {
- if (a.find(item.getData()) != null) res.push(item.getData());
- }
- foreach(Node item in a) {
- if (b.find(item.getData()) != null) res.push(item.getData());
- }
- return res;
- }
- public static Set difference(Set a, Set b) {
- if (a.IsNull()) return null;
- if (b.IsNull()) return new Set(a.clone());
- Set res = new Set(a.clone());
- foreach(Node item in b) {
- res.delete_value(item.getData());
- }
- return res;
- }
- public new Node this[int n] {
- get {return base[n];}
- set {
- if (find(value.getData()) != null)
- base[n] = value;
- }
- }
- public int len() {
- int i = 0;
- foreach(Node item in this) i++;
- return i;
- }
- // public static bool operator == (Set<T> a, Set<T> b) {
- // if (a.head == null ^ b.head == null) return false;
- // if (a.head == null && b.head == null) return true;
- // Set<T> temp = new Set<T>(b);
- // foreach(Node<T> item in a) {
- // if (temp.delete_value(item.data) == null) return false;
- // }
- // return temp.IsNull();
- // }
- public new void Print() {
- this.mergesort();
- base.Print();
- }
- public static bool operator == (Set a, Set b) {
- a.mergesort();
- b.mergesort();
- return ((List)a == (List)b);
- }
- public static bool operator != (Set a, Set b) {
- return !(a == b);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement