Advertisement
force1987

Односвязный список

Jun 23rd, 2021
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.66 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. struct Element
  4. {
  5. //Данные
  6. char data;
  7. //Адрес следующего элемента списка
  8. Element* Next;
  9. };
  10. //Односвязный список
  11. class List
  12. {
  13. //Адрес головного элемента списка
  14. Element* Head;
  15. //Адрес концевого элемента списка
  16. Element* Tail;
  17. //Количество элементов списка
  18. int Count;
  19. public:
  20. //Конструктор
  21. List();
  22. //Деструктор
  23. ~List();
  24. //Добавление элемента в список
  25. //(Новый элемент становится последним)
  26. void Add(char data);
  27. //Удаление элемента списка
  28. //(Удаляется головной элемент)
  29. void AddTarget(int num, char data);
  30. void Del();
  31. void DelTarget(int num);
  32. //Удаление всего списка
  33. void DelAll();
  34. //Распечатка содержимого списка
  35. //(Распечатка начинается с головного элемента)
  36. void Print();
  37. //Получение количества элементов,
  38. //находящихся в списке
  39. int GetCount();
  40. };
  41. List::List()
  42. {
  43. //Изначально список пуст
  44. Head = Tail = NULL;
  45. Count = 0;
  46. }
  47. List::~List()
  48. {
  49. //Вызов функции удаления
  50. DelAll();
  51. }
  52. int List::GetCount()
  53. {
  54. //Возвращаем количество элементов
  55. return Count;
  56. }
  57. void List::Add(char data)
  58. {
  59. //создание нового элемента
  60. Element* temp = new Element;
  61. //заполнение данными
  62. temp->data = data;
  63. //следующий элемент отсутствует
  64. temp->Next = NULL;
  65. //новый элемент становится последним элементом списка
  66. //если он не первый добавленный
  67. if (Head != NULL) {
  68. Tail->Next = temp;
  69. Tail = temp;
  70. }
  71. //новый элемент становится единственным
  72. //если он первый добавленный
  73. else {
  74. Head = Tail = temp;
  75. }
  76. Count++;
  77. }
  78.  
  79. void List::AddTarget (int num, char data)
  80. {
  81. if (num > Count + 1 || num < 1)
  82. {
  83. cout << "Error!\n\n";
  84. return;
  85. }
  86.  
  87. if (Head == NULL || num == Count - 1)
  88. {
  89. Add(data);
  90. return;
  91. }
  92.  
  93. if (num == 1)
  94. {
  95. Element* newEl = new Element;
  96. newEl->data = data;
  97. newEl->Next = Head;
  98. Head = newEl;
  99. Count++;
  100. return;
  101. }
  102. Element* ptr= Head;
  103. for (int i = 1; i < num-1; ++i)
  104. {
  105. ptr = ptr->Next;
  106. }
  107.  
  108. Element* newEl = new Element;
  109. newEl->data = data;
  110. newEl->Next = ptr->Next;
  111. ptr->Next = newEl;
  112. Count++;
  113. }
  114.  
  115. void List::Del()
  116. {
  117. //запоминаем адрес головного элемента
  118. Element* temp = Head;
  119. //перебрасываем голову на следующий элемент
  120. Head = Head->Next;
  121. //удаляем бывший головной элемент
  122. delete temp;
  123. Count--;
  124. }
  125.  
  126. void List::DelTarget(int num)
  127. {
  128. if (num > Count || num < 1 || Head == NULL)
  129. {
  130. cout << "Error!\n\n";
  131. return;
  132. }
  133.  
  134. if (num == 1)
  135. {
  136. Del();
  137. return;
  138. }
  139.  
  140. Element* ptr = Head;
  141. for (int i = 1; i < num-1; ++i)
  142. {
  143. ptr = ptr->Next;
  144. }
  145.  
  146. Element* temp = ptr->Next;
  147. if (num == Count - 1)
  148. {
  149. ptr->Next = NULL;
  150. Tail = ptr;
  151. }
  152. else
  153. ptr->Next = temp->Next;
  154. delete temp;
  155. Count--;
  156. }
  157.  
  158. void List::DelAll()
  159. {
  160. //Пока еще есть элементы
  161. while (Head != 0)
  162. //Удаляем элементы по одному
  163. Del();
  164. }
  165. void List::Print()
  166. {
  167. //запоминаем адрес головного элемента
  168. Element* temp = Head;
  169. //Пока еще есть элементы
  170. while (temp != 0)
  171. {
  172. //Выводим данные
  173. cout << temp->data << " ";
  174. //Переходим на следующий элемент
  175. temp = temp->Next;
  176. }
  177. cout << "\n\n";
  178. }
  179. //Тестовый пример
  180. int main()
  181. {
  182. //Создаем объект класса List
  183. List lst;
  184. //Тестовая строка
  185. char s[] = "Hello, world!";
  186. //Выводим строку
  187. cout << s << "\n\n";
  188. //Определяем длину строки
  189. int len = strlen(s);
  190. //Загоняем строку в список
  191. for (int i = 0; i < len; i++)
  192. lst.Add(s[i]);
  193. //Распечатываем содержимое списка
  194. lst.Print();
  195. lst.Del();
  196. lst.Del();
  197. lst.Del();
  198. //Удаляем три элемента списка
  199. //Распечатываем содержимое списка
  200. lst.Print();
  201. lst.AddTarget(1,'7');
  202. lst.Print();
  203. lst.DelTarget(3);
  204. lst.Print();
  205. lst.DelTarget(10);
  206. lst.Print();
  207. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement