Good evening, gentlemen, in general, I wrote a list here, like this:

#include <iostream> #include <conio.h> using namespace std; struct link { int data; link* next; } ; class linklist // список { private: link* first; public: linklist ( ) { first = NULL; } void additem ( int d ); void display ( ); }; void linklist::additem ( int d ) { link* newlink = new link; newlink->data = d; newlink->next = first; first = newlink; } void linklist::display ( ) { link* current = first; while( current ) { cout << current->data << endl; current = current->next; } } int main ( ) { int el,n,k; linklist li; cout<<"input number of element"; cin>>n; while (n>0) { cout<<"input current element"; cin>>el; li.additem ( el ); n--; } li.display ( ); getch(); return 0; }

In general, the program can enter the required number of elements, + the display function I don’t know how to insert an element into the list, it’s easy to insert it into the beginning, and I don’t know how to add it to a certain position either, + other elements are shifted when inserted. And I don’t know how to deduce an element according to its index ..... The most important thing with insertion would be to understand) help someone, and it’s time to take the test.

  • @ Ilya Bobryshev, To format a code, select it with the mouse and click on the {} button of the editor. - Donil
  • one
    @ Ilya Bobyshev, of course, most likely you need to write your own program (for training purposes), but if you want, you can familiarize yourself with the implementation of lists in Linux . - avp
  • thanks for the stuff. - 389bito

4 answers 4

https://github.com/sitev/cjCore/blob/master/src/object.cpp

Look here for the implementation of the List class, it will suddenly come up ...

  • Have you looked at the date of the question? I suspect that in almost 3 years the author (by the way, never again visited us this way) has completely lost interest in this topic. - avp
  • yes, it happens) - sitev_ru
 void linklist::insert(int pos, int value) { link* pCurrent = first; int nIndex = 0; while(nIndex<pos) { if(!pCurrent) { //Всё плохо, количество элементов меньше чем нужно //Можно бросить что-нибудь или выйти как-то иначе //throw smthg(); } pCurrent = pCurrent->next; ++nIndex; } link* pNewItem = new link; pNewItem->next = pCurrent->next; pNewItem->data = value; pCurrent->next = pNewItem; }

You also urgently need a destructor! You do not delete your list after use.

  • I would also like to note that your implementation can of course be any, but in my practice in most cases it is more convenient to store a pointer to the last element (to insert at the end, not at the beginning, as in the above code). Plus it is convenient to have a count of the number of items in the list. Well, this is nagging. - Andrey Buran
  • Thanks for the good advice) - 389bito

Start a method in which you loop through the elements of a list one by one in a cycle. As you move to the next element, you increase some integer variable in which you store the number of the current element. When this variable becomes equal to the required index, change the next pointer of the current element to the inserted one, and the next of the inserted element to the one that the current one pointed to before. Finish the cycle. Something like that.

    Once in the beginnings he wrote this. May be useful. ps. Destructor still have to write yourself. And there are extra things. Understand, I think you need.

     template <typename valueType> class List { // конструктор List(valueType Value = 0, List *Next = NULL) { this->Value = Value; this->Next = Next; } void Clone(List *to) { } // Возврат длины списка unsigned int GetLength() { unsigned int i = 1; List *tmp = this; while(tmp->Next) { tmp = tmp->Next; ++i; } return i; } // Возврат значения по номеру valueType GetValue(unsigned int index) { if(!index) return this->Value; List *tmp = this; for(unsigned int i = 0; i < index; ++i) tmp = tmp->Next; return tmp->Value; } // Вставка значения в начало списка void Put(valueType Value) { List *newValue = new List(this->Value, this->Next); this->Value = Value; this->Next = newValue; } // Вставка узла в начало списка List *Put(List *node) { node->Next = this; return node; } // Вставка значения по индексу void Insert(valueType Value, unsigned int index) { List *newValue = new List(Value); if(!index) { newValue->Value = this->Value; newValue->Next = this->Next; this->Value = Value; this->Next = newValue; return; } List *tmp = this; --index; for(unsigned int i = 0; i < index; ++i) tmp = tmp->Next; newValue->Next = tmp->Next; tmp->Next = newValue; } // Вставка значения в конец списка void Append(valueType Value) { List *newValue = new List(Value); List *tmp = this; while(tmp->Next) tmp = tmp->Next; tmp->Next = newValue; } // Удаление из списка по номеру void Delete(unsigned int index) { List *tmp = this; if(!index) { tmp = this->Next; this->Value = this->Next->Value; this->Next = this->Next->Next; delete tmp; return; } List *tmpDeleted; for(int i = 0; i < index - 1; ++i) tmp = tmp->Next; tmpDeleted = tmp->Next; tmp->Next = tmp->Next->Next; delete tmpDeleted; } // перестановка элементов List *Move(int from, int to) { List *newHead = this, *tmp = this, *tmpMoved, *tmpHead; int i = 0; // Вырезать элемент, который надо переместить if(from) { for(--from; i < from; ++i) tmp = tmp->Next; tmpMoved = tmp->Next; tmp->Next = tmp->Next->Next; // Чтобы лишний раз не перемещаться по списку if(from > to - 1) { tmp = newHead; i = 0; } } else // Если надо переместить голову { tmpMoved = tmp; newHead = newHead->Next; } // Если надо переместить в начало if(!to) { tmpHead = newHead; newHead = tmpMoved; newHead->Next = tmpHead; return newHead; } // Переместить на нужную позицию for(--to; i < to; ++i) tmp = tmp->Next; tmpHead = tmp->Next; tmp->Next = tmpMoved; tmp->Next->Next = tmpHead; return newHead; } // Поиск элемента в массиве возврат индекса, если нет вхождений возврат -1 int FindValue(valueType Value, unsigned int from = 0) { List *tmp = this; int i = 0; for(; i < from; ++i) tmp = tmp->Next; for(; tmp; tmp = tmp->Next) { if(Value == tmp->Value) return i; ++i; } return -1; } // Поиск максимального элемента, возврат адреса List *FindMax(List **beforeMax = NULL) { List *maxNode = this; List *tmp = this->Next; List *beforeTmp = this; for(; tmp; tmp = tmp->Next) { if(maxNode->Value < tmp->Value) { *beforeMax = beforeTmp; maxNode = tmp; } beforeTmp = beforeTmp->Next; } if(maxNode == this) *beforeMax = NULL; return maxNode; } // Поиск максимального элемента, возврат индекса unsigned int FindMax(unsigned int from = 0) { valueType maxValue = this->Value; List *tmp = this->Next; unsigned int maxIndex = from, i = 1; if(from) { for(; i < from; ++i) tmp = tmp->Next; maxValue = tmp->Value; } for(; tmp; tmp = tmp->Next) { if(maxValue < tmp->Value) { maxValue = tmp->Value; maxIndex = i; } ++i; } return maxIndex; } // Поиск минимального элемента, возврат индекса unsigned int FindMin(unsigned int from = 0) { valueType minValue = this->Value; List *tmp = this->Next; unsigned int minIndex = from, i = 1; if(from) { for(; i < from; ++i) tmp = tmp->Next; minValue = tmp->Value; } for(; tmp; tmp = tmp->Next) { if(minValue > tmp->Value) { minValue = tmp->Value; minIndex = i; } ++i; } return minIndex; } // Сортировка по возрастанию List *SortByAsc() { List *tmp = this; List *max; List *maxPrev; List *newHead; max = tmp->FindMax(&maxPrev); if(maxPrev) maxPrev->Next = max->Next; else tmp = tmp->Next; max->Next = NULL; newHead = max; while(tmp) { max = tmp->FindMax(&maxPrev); if(maxPrev) maxPrev->Next = max->Next; else tmp = tmp->Next; newHead = newHead->Put(max); } return newHead; } // Сортировка по убыванию List *SortByDesc() { List *newHead = this; unsigned int min = newHead->FindMin(); unsigned int i = 1, length = this->GetLength(); if(min) newHead = newHead->Move(min, 0); while(i < length) { min = newHead->FindMin(i); newHead = newHead->Move(min, 0); ++i; } return newHead; } // Построчный вывод значений элементов массива void ShowList() { List *tmp = this; for(unsigned int i = 0; tmp; tmp = tmp->Next, ++i) cout << "Value[" << i << "] = " << tmp->Value << endl; } valueType Value; List *Next; };
    • This is a useful build, useful) - 389bito