Това е реализацията на списък чрез структура и динамични променливи, която обсъждахме в часа:
#include <iostream> using namespace std; struct ListNode { int value; // данни ListNode * next; // указател към следващия елемент }; void init(ListNode* &pStart) { pStart = NULL; } void insertFirst(ListNode* &pStart, int aValue) {// вмъква елемент в началото ListNode* pnew = new ListNode ; // заделяме памет за новия елемент pnew->value = aValue; // записваме в него данните pnew->next = pStart; // следващият след него е стария първи елемент pStart = pnew; // запомняме новия елемент като първи } void insertLast(ListNode* &pStart, int aValue) {// вмъква елемент в края if(!pStart) // ако списъкът е празен insertFirst(pStart, aValue); // вмъкваме в началото else { ListNode* p = pStart; // започваме от първия while (p->next) p = p->next; // и търсим елемент без следващ (т.е. последния) ListNode* pnew = new ListNode ; // заделяме памет за новия елемент pnew->value = aValue; // записваме в него данните pnew->next = NULL; // той няма следващ елемент, защото е последен p->next = pnew; // но досегашният последен вече сочи към новия } } ListNode* nodeAt(ListNode* &pStart, int aPos) { // връща указател към елемент на зададена позиция if(aPos < 0) { // проверка за невалидна позиция cout << "Posiciata triabva da e >= 0!" << endl; return NULL; } if(!pStart) { // проверка за празен списък cout << "Spisaka e prazen!" << endl; return NULL; } if(aPos == 0) { // ако позицията е 0 return pStart; // връщаме указател към първия елемент } ListNode* p = pStart; // насочваме указател за обхождане към началото int i = 0; // декларираме брояч на елементите while(i != aPos && p) { // докато не достигнем желаната позиция и списъкът не е свършил p = p->next; // преминаваме на следващия елемент i++; // и увеличаваме брояча } if(!p) { // ако сме излезли от горния цикъл, защото p е станало NULL cout << "Nevalidna pozicia " << aPos << ", ima samo " << i << " elementa!" << endl; return NULL; } return p; // връщаме указател към открития елемент } bool insertAt(ListNode* &pStart, int aPos, int aValue) { // вмъква елемент на зададена позиция if(aPos == 0) { // ако позицията е 0 insertFirst(pStart, aValue); // ползваме наготово insertFirst return true; // и излизаме } ListNode* p = nodeAt(pStart, aPos-1); // намираме предишният елемент (на позиция APos-1) if(!p) return false; // ако няма такъв, явно има грешка ListNode* pNew = new ListNode ; // заделяме памет за новия елемент pNew->value = aValue; // записваме данните pNew->next = p->next; // 'следващ' на новия ще е елемента на позиция aPos p->next = pNew; // елемента на позиция aPos-1 ще сочи към новия return true; // вмъкването е успешно } bool removeFirst(ListNode* &pStart) { // премахва елемента в началото if(!pStart) { cout << "Spisaka e prazen!" << endl; return false; } ListNode* temp = pStart; // запомняме кой е първия елемент pStart = pStart->next; // насочваме началото към 'следващия' му delete temp; // изтриваме първия return true; } bool removeLast(ListNode* &pStart) { // премахва елемента в края if(!pStart) { cout << "Spisaka e prazen!" << endl; return false; } else if(!pStart->next) { delete pStart; pStart = NULL; return true; } else { ListNode* p = pStart; // започваме от първия while(p->next && p->next->next) p = p->next;// и търсим предпоследния елемент delete p->next; // изтриваме ел. след него (т.е. последния) p->next = NULL; // предпоследният вече няма следващ return true; } } bool removeAt(ListNode* &pStart, int aPos) {// премахва елемента на зададена позиция if(aPos == 0) { // ако позицията е 0 return removeFirst(pStart); // ползваме наготово removeFirst } ListNode* p = nodeAt(pStart, aPos-1); // намираме предишният елемент (на позиция APos-1) if(!p) return false; // ако няма такъв, явно има грешка ListNode* temp = p->next; // насочваме временен указател към ел. който ще премахваме p->next = temp->next; // 'следващ' за елемента преди изтривания ще е 'следващия' на изтривания ел. // т.е. изключваме елемента, който ще премахваме от списъка delete temp; // изтриваме елемента return true; } void removeAll(ListNode* &pStart) { // премахва всички елементи от списъка ListNode * temp; while(pStart) { // докато има нещо в списъка temp = pStart; // насочваме временния указател към първия елемент pStart = pStart->next; // насочваме началото към неговия 'следващ' delete temp; // изтриваме първия } } bool isEmpty(ListNode* pStart) { // проверява дали списъка е празен return !pStart; // ако началото не сочи на никъде значи е празен } bool getValueAt(ListNode* pStart, int aPos, int &aValue) {// прочитане на стойност на ел. на дадена позиция ListNode* p = nodeAt(pStart, aPos); if(!p) return false; aValue = p->value; return true; } bool setValueAt(ListNode* pStart, int aPos, int aValue) {// промяна на стойност на ел. на дадена позиция ListNode* p = nodeAt(pStart, aPos); if(!p) return false; p->value = aValue; return true; } void print(ListNode* &pStart) { // помощен метод за отпечатване на екран ListNode* p = pStart; while(p) { cout << p->value << ' '; // след последния елемент също се извежда интервал p = p->next; // с малка промяна на кода това може да се избегне } cout<<endl; } int main(void) { ListNode* L; init(L); cout<<"insertFirst(2)\n"; insertFirst(L, 2); print(L); cout<<"insertLast(4)\n"; insertLast(L, 4); print(L); cout<<"insertAt(-1, 0)\n"; insertAt(L, -1, 0); cout<<"insertAt(0, 1)\n"; insertAt(L, 0, 1); print(L); cout<<"insertAt(2, 3)\n"; insertAt(L, 2, 3); print(L); cout<<"insertAt(5, 6)\n"; insertAt(L, 5, 6); cout<<"removeAt(-1)\n"; removeAt(L, -1); cout<<"removeAt(0)\n"; removeAt(L, 0); print(L); cout<<"removeAt(1)\n"; removeAt(L, 1); print(L); cout<<"removeAt(5)\n"; removeAt(L, 5); cout<<"removeFirst\n"; removeFirst(L); print(L); cout<<"removeLast\n"; removeLast(L); print(L); cout<<"insert(1, 2, 3)\n"; insertLast(L, 1); insertLast(L, 2); insertLast(L, 3); print(L); int aValue; cout<<"getValueAt(1)\n"; if(getValueAt(L, 1, aValue)) cout<<"Tam ima zapisano "<<aValue<<endl; cout<<"setValueAt(1, 20)\n"; if(setValueAt(L, 1, 20)) cout<<"Uspeshen zapis\n"; print(L); return 0; }
Ехее, реализация с класове :-) Много добре, Калояне! С два класа, и с private полета за което е нужно, и с методи за достъп – всичко е както трябва да е. Можеше да сложиш коментари обаче по твоите промени, за да е ясно и за другите защо си направил това или онова…
P.S. Всъщност като се замисля, само ListNode.next е по-добре да е private. Другото е перфектно!
Добавих деструктор за списъка.
Да, правилно :-) В деструктора обаче може просто да извикваш removeAll…
Ами да, аз почнах с идеята за деструктор и съм забравил ( не съм видял), че има вече готов метод.