Advertisement
amsavchenko

Untitled

Sep 19th, 2018
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 19.41 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4.  
  5. template <typename TElement>
  6. class Sequence { // <--- КЛАСС ПОСЛЕДОВАТЕЛЬНОСТЬ
  7. protected:
  8. int length;
  9. bool isEmpty;
  10. public:
  11. Sequence();
  12. ~Sequence();
  13. int getLength ();
  14. bool getIsEmpty ();
  15. virtual TElement Get (int index) = 0;
  16. virtual TElement GetFirst() = 0;
  17. virtual TElement GetLast () = 0;
  18. virtual void Append (TElement item) = 0;
  19. virtual void Prepend (TElement item) = 0;
  20. virtual void InsertAt (int index, TElement item) = 0;
  21. virtual void Remove (TElement item) = 0;
  22.  
  23. };
  24. template <typename TElement>
  25. Sequence<TElement>:: Sequence() {
  26. length = 0;
  27. isEmpty = true;
  28. }
  29.  
  30. template <typename TElement>
  31. Sequence<TElement>:: ~Sequence() {
  32.  
  33. }
  34. template <typename TElement>
  35. int Sequence<TElement>:: getLength() {
  36. return length;
  37. }
  38. template <typename TElement>
  39. bool Sequence<TElement>::getIsEmpty() {
  40. return isEmpty;
  41. }
  42.  
  43.  
  44. template <typename TElement>
  45. class ArraySequence : public Sequence<TElement> { // <--- ПОДКЛАСС ПОСЛЕДОВАТЕЛЬНОСТЬ С МАССИВАМИ
  46. private:
  47. TElement *Array;
  48. public:
  49. ArraySequence();
  50. ~ArraySequence();
  51. TElement Get (int index);
  52. TElement GetFirst();
  53. TElement GetLast();
  54. ArraySequence<TElement> GetSubsequence (int startIndex, int endIndex);
  55. void Append (TElement item);
  56. void Prepend (TElement item);
  57. void InsertAt (int index, TElement item);
  58. void Remove (TElement item);
  59. void PrintAll ();
  60. };
  61.  
  62. class ExceptionOutOfBounds : public exception { // <--- КЛАСС ИСКЛЮЧЕНИЙ выход за границу массива
  63. int wrongIndex;
  64. public:
  65. ExceptionOutOfBounds(int index);
  66. void what() {
  67. cout << "Индекс '" << wrongIndex << "' - выход за границы массива " << endl;
  68. }
  69. };
  70. ExceptionOutOfBounds:: ExceptionOutOfBounds(int index) {
  71. wrongIndex = index;
  72. }
  73.  
  74.  
  75. template <typename TElement>
  76. ArraySequence<TElement>:: ArraySequence():Sequence<TElement>() {
  77. Array = new TElement;
  78. }
  79.  
  80. template <typename TElement>
  81. ArraySequence<TElement>:: ~ArraySequence() {
  82. delete Array;
  83. }
  84.  
  85. template <typename TElement>
  86. TElement ArraySequence<TElement>:: Get (int index) {
  87. if (index < 0 || index >= this->length) {
  88. throw ExceptionOutOfBounds(index);
  89. }
  90. return Array[index];
  91.  
  92. }
  93.  
  94.  
  95. template <typename TElement>
  96. TElement ArraySequence<TElement>:: GetFirst () {
  97. if (this->length == 0) {
  98. throw ExceptionOutOfBounds(0);
  99. }
  100. return Array[0];
  101. }
  102.  
  103. template <typename TElement>
  104. TElement ArraySequence<TElement>:: GetLast () {
  105. if (this->length == 0) {
  106. throw ExceptionOutOfBounds(0);
  107. }
  108. return Array [this->length - 1];
  109. }
  110.  
  111.  
  112. template <typename TElement>
  113. void ArraySequence<TElement>:: Append(TElement item) { // Append. вставить в конец
  114. if (this->length == 0) {
  115. this->length ++;
  116. this->isEmpty = false;
  117. Array [0] = item;
  118. }
  119. else {
  120. this->length ++;
  121. //TElement *newArray = new TElement [this->length];
  122. //for (int i = 0; i < this->length - 1; i++) {
  123. // newArray[i] = Array [i];
  124. //}
  125. Array[this->length - 1] = item;
  126. //Array = newArray;
  127. }
  128. }
  129.  
  130. template <typename TElement>
  131. void ArraySequence<TElement>:: Prepend(TElement item) { // Prepend. вставить в начало
  132. if (this->length == 0) {
  133. this->length ++;
  134. this->isEmpty = false;
  135. Array [0] = item;
  136. }
  137. else {
  138. this->length ++;
  139. TElement *newArray = new TElement [this->length];
  140. for (int i = 1; i < this->length; i++) {
  141. newArray[i] = Array [i-1];
  142. }
  143. newArray[0] = item;
  144. Array = newArray;
  145. }
  146. }
  147.  
  148. template <typename TElement>
  149. void ArraySequence<TElement>:: InsertAt(int index, TElement item) {
  150. if (index < 0 || index > this->length) {
  151. throw ExceptionOutOfBounds(index);
  152. }
  153. else {
  154. this->length ++;
  155. TElement *newArray = new TElement [this->length];
  156. for (int i = 0; i < index; i ++) {
  157. newArray[i] = Array[i];
  158. }
  159. newArray[index] = item;
  160. for (int i = index + 1; i < this->length; i++) {
  161. newArray [i] = Array [i-1];
  162. }
  163. Array = newArray;
  164. }
  165. }
  166.  
  167.  
  168. template <typename TElement>
  169. void ArraySequence<TElement>:: Remove(TElement item) {
  170. for (int i = 0; i < this->length; i ++) {
  171. if (Array[i] == item) {
  172. this->length --;
  173. TElement *newArray = new TElement [this->length];
  174. for (int j = 0; j < i; j ++) {
  175. newArray[j] = Array [j];
  176. }
  177. for (int k = i; k < this->length; k ++) {
  178. newArray[k] = Array[k+1];
  179. }
  180. Array = newArray;
  181. i --;
  182. }
  183. }
  184. }
  185.  
  186. template <typename TElement>
  187. ArraySequence<TElement> ArraySequence<TElement>:: GetSubsequence(int startIndex, int endIndex) {
  188. if (startIndex < 0 || startIndex >= this->length) {
  189. throw ExceptionOutOfBounds(startIndex);
  190. }
  191. if (endIndex < 0 || endIndex >= this->length) {
  192. throw ExceptionOutOfBounds(endIndex);
  193. }
  194. if (endIndex - startIndex < 0) {
  195. throw ExceptionOutOfBounds(endIndex - startIndex);
  196. }
  197. ArraySequence<TElement> Subsequence;
  198. for (int i = startIndex; i <= endIndex; i ++) {
  199. Subsequence.Append(Array[i]);
  200. }
  201. return Subsequence;
  202. }
  203.  
  204. template <typename TElement>
  205. void ArraySequence<TElement>:: PrintAll() {
  206. cout << "Последовательность: ";
  207. for (int i = 0; i < this->length; i ++) {
  208. cout << Array[i] << " ";
  209. }
  210. cout << endl;
  211. }
  212.  
  213. //////////////////////////////////////////////////////////////////////////////////////////////////
  214.  
  215. template <typename TElement>
  216. struct Node {
  217. TElement field;
  218. Node *next;
  219. Node *prev;
  220. };
  221.  
  222. template <typename TElement>
  223. class ListSequence: public Sequence <TElement> { // <--- ПОДКЛАСС ПОСЛЕДОВАТЕЛЬНОСТЬ С двусвязным СПИСКОМ
  224. Node<TElement> *First, *Last;
  225. public:
  226. ListSequence();
  227. ~ListSequence();
  228. void Append(TElement item);
  229. void Prepend(TElement item);
  230. TElement GetFirst();
  231. TElement GetLast();
  232. void InsertAt(int index, TElement item);
  233. TElement Get(int index);
  234. void Remove(TElement item);
  235. ListSequence<TElement> GetSubsequence(int startIndex, int endIndex);
  236. void PrintAll ();
  237. };
  238.  
  239. template <typename TElement>
  240. ListSequence<TElement>:: ListSequence() : Sequence<TElement>() {
  241. First = NULL;
  242. Last = NULL;
  243. }
  244.  
  245. template <typename TElement>
  246. ListSequence<TElement>:: ~ListSequence(){
  247. while (First) {
  248. Last = First->next;
  249. delete First;
  250. First = Last;
  251. }
  252. }
  253.  
  254. template <typename TElement>
  255. TElement ListSequence<TElement>:: GetFirst() {
  256. if(First == NULL) {
  257. throw ExceptionOutOfBounds(0);
  258. }
  259. return First->field;
  260. }
  261.  
  262. template <typename TElement>
  263. TElement ListSequence<TElement>:: GetLast() {
  264. if (Last == NULL) {
  265. throw ExceptionOutOfBounds(0);
  266. }
  267. return Last->field;
  268. }
  269.  
  270. template <typename TElement>
  271. void ListSequence<TElement>:: Append(TElement item) {
  272. Node<TElement> *temp = new Node<TElement>;
  273. temp->next = NULL;
  274. temp->field = item;
  275. if(this->length != 0){
  276. temp->prev = Last;
  277. Last->next = temp;
  278. Last = temp;
  279. this->length++;
  280. }
  281. else {
  282. temp->prev = NULL;
  283. First = temp;
  284. Last = temp;
  285. this->length++;
  286. this->isEmpty = false;
  287. }
  288. }
  289.  
  290. template <typename TElement>
  291. void ListSequence<TElement>:: Prepend(TElement item) {
  292. Node<TElement> *temp = new Node<TElement>;
  293. temp->prev = NULL;
  294. temp->field = item;
  295. if(this->length != 0) {
  296. temp->next=First;
  297. First->prev=temp;
  298. First=temp;
  299. this->length++;
  300. }
  301. else {
  302. temp->next=NULL;
  303. First=temp;
  304. Last=temp;
  305. this->length++;
  306. this->isEmpty = false;
  307. }
  308. }
  309.  
  310. template <typename TElement>
  311. void ListSequence<TElement>:: InsertAt(int index, TElement item) {
  312. if(index < 0 || index > this->length) {
  313. throw ExceptionOutOfBounds(index);
  314. }
  315. if(this->isEmpty == true) this->isEmpty = false;
  316. if(index == 0) Prepend(item);
  317. else if(index == this->length - 1) Append(item);
  318. else {
  319. this->length++;
  320. Node<TElement> *temp=new Node<TElement>;
  321. temp->field = item;
  322. temp->next = First->next;
  323. temp->prev = First;
  324. while(index-2) {
  325. temp->prev = temp->prev->next;
  326. temp->next = temp->next->next;
  327. index --;
  328. }
  329. temp->prev->next = temp;
  330. temp->next->prev = temp;
  331. }
  332. }
  333.  
  334. template <typename TElement>
  335. TElement ListSequence<TElement>:: Get(int index) {
  336. if (index < 0 || index > this->length - 1) {
  337. throw ExceptionOutOfBounds(index);
  338. }
  339. if(index == 0) return GetFirst();
  340. if(index == this->length - 1) return GetLast();
  341. else {
  342. Node<TElement> *temp = new Node<TElement>;
  343. temp->next = First->next;
  344. while(index - 1) {
  345. temp->next = temp->next->next;
  346. index --;
  347. }
  348. return temp->next->field;
  349. }
  350. }
  351.  
  352. template <typename TElement>
  353. void ListSequence<TElement>:: Remove(TElement item) {
  354. int k = 0;
  355. while(k < this->length - 1) {
  356. Node<TElement> *temp = new Node<TElement>;
  357. int index = k;
  358. temp->next = First;
  359. while(temp->next->field != item && index < this->length - 1) {
  360. temp->next = temp->next->next;
  361. index ++;
  362. k ++;
  363. }
  364. if(temp->next->field == item) {
  365. temp = temp->next;
  366. if(temp->prev != 0) temp->prev->next = temp->next;
  367. else First = temp->next;
  368. if(temp->next != 0) temp->next->prev = temp->prev;
  369. else Last = temp->prev;
  370. if (this->length == 0) this->isEmpty = false;
  371. this->length--;
  372. delete temp;
  373. }
  374. }
  375. }
  376.  
  377. template <typename TElement>
  378. ListSequence<TElement> ListSequence<TElement>:: GetSubsequence(int startIndex, int endIndex) {
  379. if (startIndex < 0 || startIndex > this->length + 1) {
  380. throw ExceptionOutOfBounds(startIndex);
  381. }
  382. if (endIndex < 0 || endIndex >= this->length + 1) {
  383. throw ExceptionOutOfBounds(endIndex);
  384. }
  385. if (endIndex - startIndex < 0) {
  386. throw ExceptionOutOfBounds(endIndex - startIndex);
  387. }
  388. ListSequence<TElement> Subsequence;
  389. Node<TElement> *temp = new Node<TElement>;
  390. temp = First;
  391. for (int i = 0; i < startIndex; i ++) temp = temp->next;
  392. for (int i = startIndex - 1; i < endIndex; i++) {
  393. Subsequence.Append(temp->field);
  394. temp = temp->next;
  395. }
  396. return Subsequence;
  397. }
  398.  
  399. template <typename TElement>
  400. void ListSequence<TElement>:: PrintAll() {
  401. Node<TElement> *temp = new Node<TElement>;
  402. temp = First;
  403. cout << "Последовательность: " ;
  404. while (temp) {
  405. cout << temp->field << " ";
  406. temp = temp->next;
  407. }
  408. cout << endl;
  409. }
  410.  
  411.  
  412. void TestArraySequence() {
  413. cout << "--- НАЧАЛО ТЕСТИРОВАНИЯ (с массивами) ---" << endl;
  414. ArraySequence<int> testArray;
  415.  
  416. if (testArray.getLength() == 0) cout << "Тест 1 - OK" << endl;
  417. else cout << "Тест 1 - Mistake" << endl;
  418.  
  419. testArray.Append(23);
  420. testArray.PrintAll();
  421.  
  422. if (testArray.getLength() == 1) cout << "Тест 2 - OK" << endl;
  423. else cout << "Тест 2 - Mistake" << endl;
  424.  
  425. if (testArray.GetFirst() == 23) cout << "Тест 3 - OK" << endl;
  426. else cout << "Тест 3 - Mistake" << endl;
  427.  
  428. if (testArray.GetLast() == 23) cout << "Тест 4 - OK" << endl;
  429. else cout << "Тест 4 - Mistake" << endl;
  430.  
  431. try {
  432. if (testArray.Get(0) == 23) cout << "Тест 5 - OK" << endl;
  433. else cout << "Тест 5 - Mistake" << endl;
  434. }
  435. catch (ExceptionOutOfBounds ex){
  436. ex.what();
  437. }
  438.  
  439. try {
  440. cout << testArray.Get(-1) << endl;
  441. }
  442. catch (ExceptionOutOfBounds ex){
  443. ex.what();
  444. }
  445.  
  446. try {
  447. testArray.Get(1);
  448. }
  449. catch (ExceptionOutOfBounds ex){
  450. ex.what();
  451. }
  452.  
  453. testArray.Append(43);
  454. testArray.PrintAll();
  455.  
  456. if (testArray.getLength() == 2) cout << "Тест 6 - OK" << endl;
  457. else cout << "Тест 6 - Mistake" << endl;
  458.  
  459. if (testArray.GetFirst() == 23) cout << "Тест 7 - OK" << endl;
  460. else cout << "Тест 7 - Mistake" << endl;
  461.  
  462. if (testArray.GetLast() == 43) cout << "Тест 8 - OK" << endl;
  463. else cout << "Тест 8 - Mistake" << endl;
  464.  
  465. try {
  466. if (testArray.Get(0) == 23) cout << "Тест 9 - OK" << endl;
  467. else cout << "Тест 9 - Mistake" << endl;
  468. }
  469. catch (ExceptionOutOfBounds ex){
  470. ex.what();
  471. }
  472.  
  473. try {
  474. if (testArray.Get(1) == 43) cout << "Тест 10 - OK" << endl;
  475. else cout << "Тест 10 - Mistake" << endl;
  476. }
  477. catch (ExceptionOutOfBounds ex){
  478. ex.what();
  479. }
  480.  
  481. try {
  482. testArray.Get(-1);
  483. }
  484. catch (ExceptionOutOfBounds ex){
  485. ex.what();
  486. }
  487.  
  488. try {
  489. testArray.Get(2);
  490. }
  491. catch (ExceptionOutOfBounds ex){
  492. ex.what();
  493. }
  494.  
  495. testArray.Prepend(53);
  496. testArray.PrintAll();
  497.  
  498. if (testArray.getLength() == 3) cout << "Тест 11 - OK" << endl;
  499. else cout << "Тест 11 - Mistake" << endl;
  500.  
  501. if (testArray.GetFirst() == 53) cout << "Тест 12 - OK" << endl;
  502. else cout << "Тест 12 - Mistake" << endl;
  503.  
  504. if (testArray.GetLast() == 43) cout << "Тест 13 - OK" << endl;
  505. else cout << "Тест 13 - Mistake" << endl;
  506.  
  507. try {
  508. if (testArray.Get(0) == 53) cout << "Тест 14 - OK" << endl;
  509. else cout << "Тест 14 - Mistake" << endl;
  510. }
  511. catch (ExceptionOutOfBounds ex){
  512. ex.what();
  513. }
  514.  
  515. try {
  516. if (testArray.Get(1) == 23) cout << "Тест 15 - OK" << endl;
  517. else cout << "Тест 15 - Mistake" << endl;
  518. }
  519. catch (ExceptionOutOfBounds ex){
  520. ex.what();
  521. }
  522.  
  523. try {
  524. testArray.Get(-1);
  525. }
  526. catch (ExceptionOutOfBounds ex){
  527. ex.what();
  528. }
  529.  
  530. try {
  531. testArray.Get(3);
  532. }
  533. catch (ExceptionOutOfBounds ex){
  534. ex.what();
  535. }
  536.  
  537.  
  538. ArraySequence<int> testSubseq = testArray.GetSubsequence(1, 1);
  539.  
  540. if (testSubseq.getLength() == 1) cout << "Тест 16 - OK" << endl;
  541. else cout << "Тест 16 - Mistake" << endl;
  542.  
  543. if (testSubseq.GetFirst() == 23) cout << "Тест 17 - OK" << endl;
  544. else cout << "Тест 17 - Mistake" << endl;
  545.  
  546. if (testSubseq.GetLast() == 23) cout << "Тест 18 - OK" << endl;
  547. else cout << "Тест 18 - Mistake" << endl;
  548.  
  549. testSubseq.PrintAll();
  550.  
  551. testSubseq.InsertAt(0, 1);
  552. testSubseq.InsertAt(2, 3);
  553. testSubseq.InsertAt(2, 5);
  554. testSubseq.PrintAll();
  555. if (testSubseq.getLength() == 4) cout << "Тест 19 - OK" << endl;
  556. else cout << "Тест 19 - Mistake" << endl;
  557.  
  558.  
  559.  
  560. cout << "--- КОНЕЦ ТЕСТИРОВАНИЯ (с массивами) ---" << endl;
  561.  
  562. }
  563.  
  564. void TestListSequence() {
  565. cout << "--- НАЧАЛО ТЕСТИРОВАНИЯ (со списками) ---" << endl;
  566. ListSequence<int> testArray;
  567.  
  568. if (testArray.getLength() == 0) cout << "1 - OK" << endl;
  569. else cout << "1 - Mistake" << endl;
  570.  
  571. testArray.Append(23);
  572.  
  573. if (testArray.getLength() == 1) cout << "2 - OK" << endl;
  574. else cout << "2 - Mistake" << endl;
  575.  
  576. if (testArray.GetFirst() == 23) cout << "3 - OK" << endl;
  577. else cout << "3 - Mistake" << endl;
  578.  
  579. if (testArray.GetLast() == 23) cout << "4 - OK" << endl;
  580. else cout << "4 - Mistake" << endl;
  581.  
  582. try {
  583. if (testArray.Get(0) == 23) cout << "5 - OK" << endl;
  584. else cout << "5 - Mistake" << endl;
  585. }
  586. catch (ExceptionOutOfBounds ex){
  587. ex.what();
  588. }
  589.  
  590. try {
  591. cout << testArray.Get(-1) << endl;
  592. }
  593. catch (ExceptionOutOfBounds ex){
  594. ex.what();
  595. }
  596.  
  597. try {
  598. testArray.Get(1);
  599. }
  600. catch (ExceptionOutOfBounds ex){
  601. ex.what();
  602. }
  603.  
  604. testArray.Append(43);
  605.  
  606. if (testArray.getLength() == 2) cout << "6 - OK" << endl;
  607. else cout << "6 - Mistake" << endl;
  608.  
  609. if (testArray.GetFirst() == 23) cout << "7 - OK" << endl;
  610. else cout << "7 - Mistake" << endl;
  611.  
  612. if (testArray.GetLast() == 43) cout << "8 - OK" << endl;
  613. else cout << "8 - Mistake" << endl;
  614.  
  615. try {
  616. if (testArray.Get(0) == 23) cout << "9 - OK" << endl;
  617. else cout << "9 - Mistake" << endl;
  618. }
  619. catch (ExceptionOutOfBounds ex){
  620. ex.what();
  621. }
  622.  
  623. try {
  624. if (testArray.Get(1) == 43) cout << "10 - OK" << endl;
  625. else cout << "10 - Mistake" << endl;
  626. }
  627. catch (ExceptionOutOfBounds ex){
  628. ex.what();
  629. }
  630.  
  631. try {
  632. testArray.Get(-1);
  633. }
  634. catch (ExceptionOutOfBounds ex){
  635. ex.what();
  636. }
  637.  
  638. try {
  639. testArray.Get(2);
  640. }
  641. catch (ExceptionOutOfBounds ex){
  642. ex.what();
  643. }
  644.  
  645. testArray.Prepend(53);
  646.  
  647. if (testArray.getLength() == 3) cout << "11 - OK" << endl;
  648. else cout << "11 - Mistake" << endl;
  649.  
  650. if (testArray.GetFirst() == 53) cout << "12 - OK" << endl;
  651. else cout << "12 - Mistake" << endl;
  652.  
  653. if (testArray.GetLast() == 43) cout << "13 - OK" << endl;
  654. else cout << "13 - Mistake" << endl;
  655.  
  656. try {
  657. if (testArray.Get(0) == 53) cout << "14 - OK" << endl;
  658. else cout << "14 - Mistake" << endl;
  659. }
  660. catch (ExceptionOutOfBounds ex){
  661. ex.what();
  662. }
  663.  
  664. try {
  665. if (testArray.Get(1) == 23) cout << "15 - OK" << endl;
  666. else cout << "15 - Mistake" << endl;
  667. }
  668. catch (ExceptionOutOfBounds ex){
  669. ex.what();
  670. }
  671.  
  672. try {
  673. testArray.Get(-1);
  674. }
  675. catch (ExceptionOutOfBounds ex){
  676. ex.what();
  677. }
  678.  
  679. try {
  680. testArray.Get(3);
  681. }
  682. catch (ExceptionOutOfBounds ex){
  683. ex.what();
  684. }
  685.  
  686. testArray.PrintAll();
  687.  
  688. ListSequence<int> testSubseq = testArray.GetSubsequence(1, 1);
  689.  
  690. if (testSubseq.getLength() == 1) cout << "16 - OK" << endl;
  691. else cout << "16 - Mistake" << endl;
  692.  
  693. if (testSubseq.GetFirst() == 23) cout << "17 - OK" << endl;
  694. else cout << "17 - Mistake" << endl;
  695.  
  696. if (testSubseq.GetLast() == 23) cout << "18 - OK" << endl;
  697. else cout << "18 - Mistake" << endl;
  698.  
  699. testSubseq.PrintAll();
  700.  
  701. testSubseq.InsertAt(0, 1);
  702. testSubseq.InsertAt(2, 3);
  703. testSubseq.InsertAt(2, 5);
  704. testSubseq.PrintAll();
  705. if (testSubseq.getLength() == 4) cout << "Тест 19 - OK" << endl;
  706. else cout << "Тест 19 - Mistake" << endl;
  707.  
  708.  
  709.  
  710. cout << "--- КОНЕЦ ТЕСТИРОВАНИЯ (со списками) ---" << endl;
  711.  
  712. }
  713.  
  714.  
  715. int main () {
  716.  
  717. TestArraySequence();
  718. cout << endl;
  719. TestListSequence();
  720. return 0;
  721.  
  722. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement