Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- template <typename TElement>
- class Sequence { // <--- КЛАСС ПОСЛЕДОВАТЕЛЬНОСТЬ
- protected:
- int length;
- bool isEmpty;
- public:
- Sequence();
- ~Sequence();
- int getLength ();
- bool getIsEmpty ();
- virtual TElement Get (int index) = 0;
- virtual TElement GetFirst() = 0;
- virtual TElement GetLast () = 0;
- virtual void Append (TElement item) = 0;
- virtual void Prepend (TElement item) = 0;
- virtual void InsertAt (int index, TElement item) = 0;
- virtual void Remove (TElement item) = 0;
- };
- template <typename TElement>
- Sequence<TElement>:: Sequence() {
- length = 0;
- isEmpty = true;
- }
- template <typename TElement>
- Sequence<TElement>:: ~Sequence() {
- }
- template <typename TElement>
- int Sequence<TElement>:: getLength() {
- return length;
- }
- template <typename TElement>
- bool Sequence<TElement>::getIsEmpty() {
- return isEmpty;
- }
- template <typename TElement>
- class ArraySequence : public Sequence<TElement> { // <--- ПОДКЛАСС ПОСЛЕДОВАТЕЛЬНОСТЬ С МАССИВАМИ
- private:
- TElement *Array;
- public:
- ArraySequence();
- ~ArraySequence();
- TElement Get (int index);
- TElement GetFirst();
- TElement GetLast();
- ArraySequence<TElement> GetSubsequence (int startIndex, int endIndex);
- void Append (TElement item);
- void Prepend (TElement item);
- void InsertAt (int index, TElement item);
- void Remove (TElement item);
- void PrintAll ();
- };
- class ExceptionOutOfBounds : public exception { // <--- КЛАСС ИСКЛЮЧЕНИЙ выход за границу массива
- int wrongIndex;
- public:
- ExceptionOutOfBounds(int index);
- void what() {
- cout << "Индекс '" << wrongIndex << "' - выход за границы массива " << endl;
- }
- };
- ExceptionOutOfBounds:: ExceptionOutOfBounds(int index) {
- wrongIndex = index;
- }
- template <typename TElement>
- ArraySequence<TElement>:: ArraySequence():Sequence<TElement>() {
- Array = new TElement;
- }
- template <typename TElement>
- ArraySequence<TElement>:: ~ArraySequence() {
- delete Array;
- }
- template <typename TElement>
- TElement ArraySequence<TElement>:: Get (int index) {
- if (index < 0 || index >= this->length) {
- throw ExceptionOutOfBounds(index);
- }
- return Array[index];
- }
- template <typename TElement>
- TElement ArraySequence<TElement>:: GetFirst () {
- if (this->length == 0) {
- throw ExceptionOutOfBounds(0);
- }
- return Array[0];
- }
- template <typename TElement>
- TElement ArraySequence<TElement>:: GetLast () {
- if (this->length == 0) {
- throw ExceptionOutOfBounds(0);
- }
- return Array [this->length - 1];
- }
- template <typename TElement>
- void ArraySequence<TElement>:: Append(TElement item) { // Append. вставить в конец
- if (this->length == 0) {
- this->length ++;
- this->isEmpty = false;
- Array [0] = item;
- }
- else {
- this->length ++;
- //TElement *newArray = new TElement [this->length];
- //for (int i = 0; i < this->length - 1; i++) {
- // newArray[i] = Array [i];
- //}
- Array[this->length - 1] = item;
- //Array = newArray;
- }
- }
- template <typename TElement>
- void ArraySequence<TElement>:: Prepend(TElement item) { // Prepend. вставить в начало
- if (this->length == 0) {
- this->length ++;
- this->isEmpty = false;
- Array [0] = item;
- }
- else {
- this->length ++;
- TElement *newArray = new TElement [this->length];
- for (int i = 1; i < this->length; i++) {
- newArray[i] = Array [i-1];
- }
- newArray[0] = item;
- Array = newArray;
- }
- }
- template <typename TElement>
- void ArraySequence<TElement>:: InsertAt(int index, TElement item) {
- if (index < 0 || index > this->length) {
- throw ExceptionOutOfBounds(index);
- }
- else {
- this->length ++;
- TElement *newArray = new TElement [this->length];
- for (int i = 0; i < index; i ++) {
- newArray[i] = Array[i];
- }
- newArray[index] = item;
- for (int i = index + 1; i < this->length; i++) {
- newArray [i] = Array [i-1];
- }
- Array = newArray;
- }
- }
- template <typename TElement>
- void ArraySequence<TElement>:: Remove(TElement item) {
- for (int i = 0; i < this->length; i ++) {
- if (Array[i] == item) {
- this->length --;
- TElement *newArray = new TElement [this->length];
- for (int j = 0; j < i; j ++) {
- newArray[j] = Array [j];
- }
- for (int k = i; k < this->length; k ++) {
- newArray[k] = Array[k+1];
- }
- Array = newArray;
- i --;
- }
- }
- }
- template <typename TElement>
- ArraySequence<TElement> ArraySequence<TElement>:: GetSubsequence(int startIndex, int endIndex) {
- if (startIndex < 0 || startIndex >= this->length) {
- throw ExceptionOutOfBounds(startIndex);
- }
- if (endIndex < 0 || endIndex >= this->length) {
- throw ExceptionOutOfBounds(endIndex);
- }
- if (endIndex - startIndex < 0) {
- throw ExceptionOutOfBounds(endIndex - startIndex);
- }
- ArraySequence<TElement> Subsequence;
- for (int i = startIndex; i <= endIndex; i ++) {
- Subsequence.Append(Array[i]);
- }
- return Subsequence;
- }
- template <typename TElement>
- void ArraySequence<TElement>:: PrintAll() {
- cout << "Последовательность: ";
- for (int i = 0; i < this->length; i ++) {
- cout << Array[i] << " ";
- }
- cout << endl;
- }
- //////////////////////////////////////////////////////////////////////////////////////////////////
- template <typename TElement>
- struct Node {
- TElement field;
- Node *next;
- Node *prev;
- };
- template <typename TElement>
- class ListSequence: public Sequence <TElement> { // <--- ПОДКЛАСС ПОСЛЕДОВАТЕЛЬНОСТЬ С двусвязным СПИСКОМ
- Node<TElement> *First, *Last;
- public:
- ListSequence();
- ~ListSequence();
- void Append(TElement item);
- void Prepend(TElement item);
- TElement GetFirst();
- TElement GetLast();
- void InsertAt(int index, TElement item);
- TElement Get(int index);
- void Remove(TElement item);
- ListSequence<TElement> GetSubsequence(int startIndex, int endIndex);
- void PrintAll ();
- };
- template <typename TElement>
- ListSequence<TElement>:: ListSequence() : Sequence<TElement>() {
- First = NULL;
- Last = NULL;
- }
- template <typename TElement>
- ListSequence<TElement>:: ~ListSequence(){
- while (First) {
- Last = First->next;
- delete First;
- First = Last;
- }
- }
- template <typename TElement>
- TElement ListSequence<TElement>:: GetFirst() {
- if(First == NULL) {
- throw ExceptionOutOfBounds(0);
- }
- return First->field;
- }
- template <typename TElement>
- TElement ListSequence<TElement>:: GetLast() {
- if (Last == NULL) {
- throw ExceptionOutOfBounds(0);
- }
- return Last->field;
- }
- template <typename TElement>
- void ListSequence<TElement>:: Append(TElement item) {
- Node<TElement> *temp = new Node<TElement>;
- temp->next = NULL;
- temp->field = item;
- if(this->length != 0){
- temp->prev = Last;
- Last->next = temp;
- Last = temp;
- this->length++;
- }
- else {
- temp->prev = NULL;
- First = temp;
- Last = temp;
- this->length++;
- this->isEmpty = false;
- }
- }
- template <typename TElement>
- void ListSequence<TElement>:: Prepend(TElement item) {
- Node<TElement> *temp = new Node<TElement>;
- temp->prev = NULL;
- temp->field = item;
- if(this->length != 0) {
- temp->next=First;
- First->prev=temp;
- First=temp;
- this->length++;
- }
- else {
- temp->next=NULL;
- First=temp;
- Last=temp;
- this->length++;
- this->isEmpty = false;
- }
- }
- template <typename TElement>
- void ListSequence<TElement>:: InsertAt(int index, TElement item) {
- if(index < 0 || index > this->length) {
- throw ExceptionOutOfBounds(index);
- }
- if(this->isEmpty == true) this->isEmpty = false;
- if(index == 0) Prepend(item);
- else if(index == this->length - 1) Append(item);
- else {
- this->length++;
- Node<TElement> *temp=new Node<TElement>;
- temp->field = item;
- temp->next = First->next;
- temp->prev = First;
- while(index-2) {
- temp->prev = temp->prev->next;
- temp->next = temp->next->next;
- index --;
- }
- temp->prev->next = temp;
- temp->next->prev = temp;
- }
- }
- template <typename TElement>
- TElement ListSequence<TElement>:: Get(int index) {
- if (index < 0 || index > this->length - 1) {
- throw ExceptionOutOfBounds(index);
- }
- if(index == 0) return GetFirst();
- if(index == this->length - 1) return GetLast();
- else {
- Node<TElement> *temp = new Node<TElement>;
- temp->next = First->next;
- while(index - 1) {
- temp->next = temp->next->next;
- index --;
- }
- return temp->next->field;
- }
- }
- template <typename TElement>
- void ListSequence<TElement>:: Remove(TElement item) {
- int k = 0;
- while(k < this->length - 1) {
- Node<TElement> *temp = new Node<TElement>;
- int index = k;
- temp->next = First;
- while(temp->next->field != item && index < this->length - 1) {
- temp->next = temp->next->next;
- index ++;
- k ++;
- }
- if(temp->next->field == item) {
- temp = temp->next;
- if(temp->prev != 0) temp->prev->next = temp->next;
- else First = temp->next;
- if(temp->next != 0) temp->next->prev = temp->prev;
- else Last = temp->prev;
- if (this->length == 0) this->isEmpty = false;
- this->length--;
- delete temp;
- }
- }
- }
- template <typename TElement>
- ListSequence<TElement> ListSequence<TElement>:: GetSubsequence(int startIndex, int endIndex) {
- if (startIndex < 0 || startIndex > this->length + 1) {
- throw ExceptionOutOfBounds(startIndex);
- }
- if (endIndex < 0 || endIndex >= this->length + 1) {
- throw ExceptionOutOfBounds(endIndex);
- }
- if (endIndex - startIndex < 0) {
- throw ExceptionOutOfBounds(endIndex - startIndex);
- }
- ListSequence<TElement> Subsequence;
- Node<TElement> *temp = new Node<TElement>;
- temp = First;
- for (int i = 0; i < startIndex; i ++) temp = temp->next;
- for (int i = startIndex - 1; i < endIndex; i++) {
- Subsequence.Append(temp->field);
- temp = temp->next;
- }
- return Subsequence;
- }
- template <typename TElement>
- void ListSequence<TElement>:: PrintAll() {
- Node<TElement> *temp = new Node<TElement>;
- temp = First;
- cout << "Последовательность: " ;
- while (temp) {
- cout << temp->field << " ";
- temp = temp->next;
- }
- cout << endl;
- }
- void TestArraySequence() {
- cout << "--- НАЧАЛО ТЕСТИРОВАНИЯ (с массивами) ---" << endl;
- ArraySequence<int> testArray;
- if (testArray.getLength() == 0) cout << "Тест 1 - OK" << endl;
- else cout << "Тест 1 - Mistake" << endl;
- testArray.Append(23);
- testArray.PrintAll();
- if (testArray.getLength() == 1) cout << "Тест 2 - OK" << endl;
- else cout << "Тест 2 - Mistake" << endl;
- if (testArray.GetFirst() == 23) cout << "Тест 3 - OK" << endl;
- else cout << "Тест 3 - Mistake" << endl;
- if (testArray.GetLast() == 23) cout << "Тест 4 - OK" << endl;
- else cout << "Тест 4 - Mistake" << endl;
- try {
- if (testArray.Get(0) == 23) cout << "Тест 5 - OK" << endl;
- else cout << "Тест 5 - Mistake" << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- cout << testArray.Get(-1) << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- testArray.Get(1);
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- testArray.Append(43);
- testArray.PrintAll();
- if (testArray.getLength() == 2) cout << "Тест 6 - OK" << endl;
- else cout << "Тест 6 - Mistake" << endl;
- if (testArray.GetFirst() == 23) cout << "Тест 7 - OK" << endl;
- else cout << "Тест 7 - Mistake" << endl;
- if (testArray.GetLast() == 43) cout << "Тест 8 - OK" << endl;
- else cout << "Тест 8 - Mistake" << endl;
- try {
- if (testArray.Get(0) == 23) cout << "Тест 9 - OK" << endl;
- else cout << "Тест 9 - Mistake" << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- if (testArray.Get(1) == 43) cout << "Тест 10 - OK" << endl;
- else cout << "Тест 10 - Mistake" << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- testArray.Get(-1);
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- testArray.Get(2);
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- testArray.Prepend(53);
- testArray.PrintAll();
- if (testArray.getLength() == 3) cout << "Тест 11 - OK" << endl;
- else cout << "Тест 11 - Mistake" << endl;
- if (testArray.GetFirst() == 53) cout << "Тест 12 - OK" << endl;
- else cout << "Тест 12 - Mistake" << endl;
- if (testArray.GetLast() == 43) cout << "Тест 13 - OK" << endl;
- else cout << "Тест 13 - Mistake" << endl;
- try {
- if (testArray.Get(0) == 53) cout << "Тест 14 - OK" << endl;
- else cout << "Тест 14 - Mistake" << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- if (testArray.Get(1) == 23) cout << "Тест 15 - OK" << endl;
- else cout << "Тест 15 - Mistake" << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- testArray.Get(-1);
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- testArray.Get(3);
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- ArraySequence<int> testSubseq = testArray.GetSubsequence(1, 1);
- if (testSubseq.getLength() == 1) cout << "Тест 16 - OK" << endl;
- else cout << "Тест 16 - Mistake" << endl;
- if (testSubseq.GetFirst() == 23) cout << "Тест 17 - OK" << endl;
- else cout << "Тест 17 - Mistake" << endl;
- if (testSubseq.GetLast() == 23) cout << "Тест 18 - OK" << endl;
- else cout << "Тест 18 - Mistake" << endl;
- testSubseq.PrintAll();
- testSubseq.InsertAt(0, 1);
- testSubseq.InsertAt(2, 3);
- testSubseq.InsertAt(2, 5);
- testSubseq.PrintAll();
- if (testSubseq.getLength() == 4) cout << "Тест 19 - OK" << endl;
- else cout << "Тест 19 - Mistake" << endl;
- cout << "--- КОНЕЦ ТЕСТИРОВАНИЯ (с массивами) ---" << endl;
- }
- void TestListSequence() {
- cout << "--- НАЧАЛО ТЕСТИРОВАНИЯ (со списками) ---" << endl;
- ListSequence<int> testArray;
- if (testArray.getLength() == 0) cout << "1 - OK" << endl;
- else cout << "1 - Mistake" << endl;
- testArray.Append(23);
- if (testArray.getLength() == 1) cout << "2 - OK" << endl;
- else cout << "2 - Mistake" << endl;
- if (testArray.GetFirst() == 23) cout << "3 - OK" << endl;
- else cout << "3 - Mistake" << endl;
- if (testArray.GetLast() == 23) cout << "4 - OK" << endl;
- else cout << "4 - Mistake" << endl;
- try {
- if (testArray.Get(0) == 23) cout << "5 - OK" << endl;
- else cout << "5 - Mistake" << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- cout << testArray.Get(-1) << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- testArray.Get(1);
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- testArray.Append(43);
- if (testArray.getLength() == 2) cout << "6 - OK" << endl;
- else cout << "6 - Mistake" << endl;
- if (testArray.GetFirst() == 23) cout << "7 - OK" << endl;
- else cout << "7 - Mistake" << endl;
- if (testArray.GetLast() == 43) cout << "8 - OK" << endl;
- else cout << "8 - Mistake" << endl;
- try {
- if (testArray.Get(0) == 23) cout << "9 - OK" << endl;
- else cout << "9 - Mistake" << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- if (testArray.Get(1) == 43) cout << "10 - OK" << endl;
- else cout << "10 - Mistake" << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- testArray.Get(-1);
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- testArray.Get(2);
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- testArray.Prepend(53);
- if (testArray.getLength() == 3) cout << "11 - OK" << endl;
- else cout << "11 - Mistake" << endl;
- if (testArray.GetFirst() == 53) cout << "12 - OK" << endl;
- else cout << "12 - Mistake" << endl;
- if (testArray.GetLast() == 43) cout << "13 - OK" << endl;
- else cout << "13 - Mistake" << endl;
- try {
- if (testArray.Get(0) == 53) cout << "14 - OK" << endl;
- else cout << "14 - Mistake" << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- if (testArray.Get(1) == 23) cout << "15 - OK" << endl;
- else cout << "15 - Mistake" << endl;
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- testArray.Get(-1);
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- try {
- testArray.Get(3);
- }
- catch (ExceptionOutOfBounds ex){
- ex.what();
- }
- testArray.PrintAll();
- ListSequence<int> testSubseq = testArray.GetSubsequence(1, 1);
- if (testSubseq.getLength() == 1) cout << "16 - OK" << endl;
- else cout << "16 - Mistake" << endl;
- if (testSubseq.GetFirst() == 23) cout << "17 - OK" << endl;
- else cout << "17 - Mistake" << endl;
- if (testSubseq.GetLast() == 23) cout << "18 - OK" << endl;
- else cout << "18 - Mistake" << endl;
- testSubseq.PrintAll();
- testSubseq.InsertAt(0, 1);
- testSubseq.InsertAt(2, 3);
- testSubseq.InsertAt(2, 5);
- testSubseq.PrintAll();
- if (testSubseq.getLength() == 4) cout << "Тест 19 - OK" << endl;
- else cout << "Тест 19 - Mistake" << endl;
- cout << "--- КОНЕЦ ТЕСТИРОВАНИЯ (со списками) ---" << endl;
- }
- int main () {
- TestArraySequence();
- cout << endl;
- TestListSequence();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement