Реализация на списък чрез структура

5 Responses to Реализация на списък чрез структура

1. dreanor каза:

   27 март, четвъртък в 23:23

   #include <iostream>
   
   using namespace std;
   
   class ListNode {
    public:
     int value;        // данни
     ListNode * next;  // указател към следващия елемент
   };
   
   class List {
   private:
       ListNode* pStart;
       int size;
   public:
       List();
       void insertFirst(int value);
       void insertLast(int aValue);
       ListNode* nodeAt(int aPos) const;
       bool insertAt(int aPos, int aValue);
       bool removeFirst();
       bool removeLast();
       bool removeAt(int aPos);
       void removeAll();
       bool isEmpty() const;
       bool getValueAt(int aPos, int &aValue) const;
       bool setValueAt(int aPos, int aValue);
       void print() const;
       int sizeOf() const;
   
   };
   
   List::List(){
     pStart = NULL;
     size=0;
   }
   
   void List::insertFirst(int aValue) {            // вмъква елемент в началото
     ListNode* pnew = new ListNode ;               // заделяме памет за новия елемент
     pnew->value = aValue;                         // записваме в него данните
     pnew->next = pStart;                          // следващият след него е стария първи елемент
     pStart = pnew;                                // запомняме новия елемент като първи
     size++;
   }
   
   void List::insertLast(int aValue) {             // вмъква елемент в края
     if(!pStart)                                   // ако списъкът е празен
       insertFirst(aValue);                        // вмъкваме в началото
     else {
       ListNode* p = pStart;                       // започваме от първия
       while (p->next)
         p = p->next;                              // и търсим елемент без следващ (т.е. последния)
       ListNode* pnew = new ListNode ;             // заделяме памет за новия елемент
       pnew->value = aValue;                       // записваме в него данните
       pnew->next = NULL;                          // той няма следващ елемент, защото е последен
       p->next = pnew;                             // но досегашният последен вече сочи към новия
       size++;
     }
   }
   
   ListNode* List::nodeAt(int aPos) const {        // връща указател към елемент на зададена позиция
     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 List::insertAt(int aPos, int aValue) {     // вмъква елемент на зададена позиция
     if(aPos == 0) {                               // ако позицията е 0
       insertFirst(aValue);                        // ползваме наготово insertFirst
       return true;                                // и излизаме
     }
     ListNode* p = nodeAt(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 ще сочи към новия
     size++;
     return true;                                  // вмъкването е успешно
   }
   
   bool List::removeFirst() {                      // премахва елемента в началото
     if(!pStart) {
       cout << "Spisaka e prazen!" << endl;
       return false;
     }
     ListNode* temp = pStart;                      // запомняме кой е първия елемент
     pStart = pStart->next;                        // насочваме началото към 'следващия' му
     delete temp;                                  // изтриваме първия
     size--;
     return true;
   }
   
   bool List::removeLast() {                       // премахва елемента в края
     if(!pStart) {
       cout << "Spisaka e prazen!" << endl;
       return false;
     }
     else if(!pStart->next) {
       delete pStart;
       pStart = NULL;
       size--;
       return true;
     }
     else {
       ListNode* p = pStart;                       // започваме от първия
       while(p->next && p->next->next) p = p->next;// и търсим предпоследния елемент
       delete p->next;                             // изтриваме ел. след него (т.е. последния)
       p->next = NULL;                             // предпоследният вече няма следващ
       size--;
       return true;
     }
   }
   
   bool List::removeAt(int aPos) {             // премахва елемента на зададена позиция
     if(aPos == 0) {                           // ако позицията е 0
       return removeFirst();                   // ползваме наготово removeFirst
     }
     ListNode* p = nodeAt(aPos-1);             // намираме предишният елемент (на позиция APos-1)
     if(!p) return false;                      // ако няма такъв, явно има грешка
     ListNode* temp = p->next;                 // насочваме временен указател към ел. който ще премахваме
     p->next = temp->next;                     // 'следващ' за елемента преди изтривания ще е 'следващия' на изтривания ел.
                                               // т.е. изключваме елемента, който ще премахваме от списъка
     delete temp;                              // изтриваме елемента
     size--;
     return true;
   }
   
   void List::removeAll() {                    // премахва всички елементи от списъка
     ListNode * temp;
     while(pStart) {                           // докато има нещо в списъка
       temp = pStart;                          // насочваме временния указател към първия елемент
       pStart = pStart->next;                  // насочваме началото към неговия 'следващ'
       delete temp;                            // изтриваме първия
     }
     size=0;
   }
   
   bool List::isEmpty() const {                // проверява дали списъка е празен
     return !pStart;                           // ако началото не сочи на никъде значи е празен
   }
   
   bool List::getValueAt(int aPos, int &aValue) const {    // прочитане на стойност на ел. на дадена позиция
     ListNode* p = nodeAt(aPos);
     if(!p) return false;
     aValue = p->value;
     return true;
   }
   
   bool List::setValueAt(int aPos, int aValue) {// промяна на стойност на ел. на дадена позиция
     ListNode* p = nodeAt(aPos);
     if(!p) return false;
     p->value = aValue;
     return true;
   }
   
   void List::print() const {      // помощен метод за отпечатване на екран
     ListNode* p = pStart;
     while(p) {
       cout << p->value << ' ';    // след последния елемент също се извежда интервал
       p = p->next;                // с малка промяна на кода това може да се избегне
     }
     cout<<endl;
   }
   
   int List::sizeOf() const{       // връща броя елементи в списъка
       return size;
   }
   
   int main(void) {
     List L;
     cout<<"insertFirst(2)\n";
     L.insertFirst(2);
     L.print();
     cout<<"insertLast(4)\n";
     L.insertLast(4);
     L.print();
     cout<<"insertAt(-1, 0)\n";
     L.insertAt(-1, 0);
     cout<<"insertAt(0, 1)\n";
     L.insertAt(0, 1);
     L.print();
     cout<<"insertAt(2, 3)\n";
     L.insertAt(2, 3);
     L.print();
     cout<<"insertAt(5, 6)\n";
     L.insertAt(5, 6);
   
     cout<<"removeAt(-1)\n";
     L.removeAt(-1);
     cout<<"removeAt(0)\n";
     L.removeAt(0);
     L.print();
     cout<<"removeAt(1)\n";
     L.removeAt(1);
     L.print();
     cout<<"removeAt(5)\n";
     L.removeAt(5);
     cout<<"removeFirst\n";
     L.removeFirst();
     L.print();
     cout<<"removeLast\n";
     L.removeLast();
     L.print();
   
     cout<<"insert(1, 2, 3)\n";
     L.insertLast(1);
     L.insertLast(2);
     L.insertLast(3);
     cout<<"Spisukut sudurja "<<L.sizeOf()<<" elementa:\n";
     L.print();
     int aValue;
     cout<<"getValueAt(1)\n";
     if(L.getValueAt(1, aValue))
     cout<<"Tam ima zapisano "<<aValue<<endl;
     cout<<"setValueAt(1, 20)\n";
     if(L.setValueAt(1, 20))
     cout<<"Uspeshen zapis\n";
     L.print();
     return 0;
   }
   

   Влезте, за да отговорите
   • Данаил каза:

     28 март, петък в 11:06

     Ехее, реализация с класове :-) Много добре, Калояне! С два класа, и с private полета за което е нужно, и с методи за достъп – всичко е както трябва да е. Можеше да сложиш коментари обаче по твоите промени, за да е ясно и за другите защо си направил това или онова…

     P.S. Всъщност като се замисля, само ListNode.next е по-добре да е private. Другото е перфектно!

     Влезте, за да отговорите
2. dreanor каза:

   11 април, петък в 22:17

   #include <iostream>
   
   using namespace std;
   
   class ListNode {
    public:
     int value;        // данни
     ListNode * next;  // указател към следващия елемент
   };
   
   class List {
   private:
       ListNode* pStart;
       int size;
   public:
       List();
       void insertFirst(int value);
       void insertLast(int aValue);
       ListNode* nodeAt(int aPos) const;
       bool insertAt(int aPos, int aValue);
       bool removeFirst();
       bool removeLast();
       bool removeAt(int aPos);
       void removeAll();
       bool isEmpty() const;
       bool getValueAt(int aPos, int &aValue) const;
       bool setValueAt(int aPos, int aValue);
       void print() const;
       int sizeOf() const;
       ~List();
   
   };
   
   List::List(){
     pStart = NULL;
     size=0;
   }
   
   void List::insertFirst(int aValue) {            // вмъква елемент в началото
     ListNode* pnew = new ListNode ;               // заделяме памет за новия елемент
     pnew->value = aValue;                         // записваме в него данните
     pnew->next = pStart;                          // следващият след него е стария първи елемент
     pStart = pnew;                                // запомняме новия елемент като първи
     size++;
   }
   
   void List::insertLast(int aValue) {             // вмъква елемент в края
     if(!pStart)                                   // ако списъкът е празен
       insertFirst(aValue);                        // вмъкваме в началото
     else {
       ListNode* p = pStart;                       // започваме от първия
       while (p->next)
         p = p->next;                              // и търсим елемент без следващ (т.е. последния)
       ListNode* pnew = new ListNode ;             // заделяме памет за новия елемент
       pnew->value = aValue;                       // записваме в него данните
       pnew->next = NULL;                          // той няма следващ елемент, защото е последен
       p->next = pnew;                             // но досегашният последен вече сочи към новия
       size++;
     }
   }
   
   ListNode* List::nodeAt(int aPos) const {        // връща указател към елемент на зададена позиция
     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 List::insertAt(int aPos, int aValue) {     // вмъква елемент на зададена позиция
     if(aPos == 0) {                               // ако позицията е 0
       insertFirst(aValue);                        // ползваме наготово insertFirst
       return true;                                // и излизаме
     }
     ListNode* p = nodeAt(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 ще сочи към новия
     size++;
     return true;                                  // вмъкването е успешно
   }
   
   bool List::removeFirst() {                      // премахва елемента в началото
     if(!pStart) {
       cout << "Spisaka e prazen!" << endl;
       return false;
     }
     ListNode* temp = pStart;                      // запомняме кой е първия елемент
     pStart = pStart->next;                        // насочваме началото към 'следващия' му
     delete temp;                                  // изтриваме първия
     size--;
     return true;
   }
   
   bool List::removeLast() {                       // премахва елемента в края
     if(!pStart) {
       cout << "Spisaka e prazen!" << endl;
       return false;
     }
     else if(!pStart->next) {
       delete pStart;
       pStart = NULL;
       size--;
       return true;
     }
     else {
       ListNode* p = pStart;                       // започваме от първия
       while(p->next && p->next->next) p = p->next;// и търсим предпоследния елемент
       delete p->next;                             // изтриваме ел. след него (т.е. последния)
       p->next = NULL;                             // предпоследният вече няма следващ
       size--;
       return true;
     }
   }
   
   bool List::removeAt(int aPos) {             // премахва елемента на зададена позиция
     if(aPos == 0) {                           // ако позицията е 0
       return removeFirst();                   // ползваме наготово removeFirst
     }
     ListNode* p = nodeAt(aPos-1);             // намираме предишният елемент (на позиция APos-1)
     if(!p) return false;                      // ако няма такъв, явно има грешка
     ListNode* temp = p->next;                 // насочваме временен указател към ел. който ще премахваме
     p->next = temp->next;                     // 'следващ' за елемента преди изтривания ще е 'следващия' на изтривания ел.
                                               // т.е. изключваме елемента, който ще премахваме от списъка
     delete temp;                              // изтриваме елемента
     size--;
     return true;
   }
   
   void List::removeAll() {                    // премахва всички елементи от списъка
     ListNode * temp;
     while(pStart) {                           // докато има нещо в списъка
       temp = pStart;                          // насочваме временния указател към първия елемент
       pStart = pStart->next;                  // насочваме началото към неговия 'следващ'
       delete temp;                            // изтриваме първия
     }
     size=0;
   }
   
   bool List::isEmpty() const {                // проверява дали списъка е празен
     return !pStart;                           // ако началото не сочи на никъде значи е празен
   }
   
   bool List::getValueAt(int aPos, int &aValue) const {    // прочитане на стойност на ел. на дадена позиция
     ListNode* p = nodeAt(aPos);
     if(!p) return false;
     aValue = p->value;
     return true;
   }
   
   bool List::setValueAt(int aPos, int aValue) {// промяна на стойност на ел. на дадена позиция
     ListNode* p = nodeAt(aPos);
     if(!p) return false;
     p->value = aValue;
     return true;
   }
   
   void List::print() const {      // помощен метод за отпечатване на екран
     ListNode* p = pStart;
     while(p) {
       cout << p->value << ' ';    // след последния елемент също се извежда интервал
       p = p->next;                // с малка промяна на кода това може да се избегне
     }
     cout<<endl;
   }
   
   int List::sizeOf() const{       // връща броя елементи в списъка
       return size;
   }
   
   List::~List()
   {
       ListNode* next;
       while (pStart != NULL)
       {
           next = pStart->next;
           delete pStart;
           pStart = next;
       }
   }
   
   int main(void) {
     List L;
     cout<<"insertFirst(2)\n";
     L.insertFirst(2);
     L.print();
     cout<<"insertLast(4)\n";
     L.insertLast(4);
     L.print();
     cout<<"insertAt(-1, 0)\n";
     L.insertAt(-1, 0);
     cout<<"insertAt(0, 1)\n";
     L.insertAt(0, 1);
     L.print();
     cout<<"insertAt(2, 3)\n";
     L.insertAt(2, 3);
     L.print();
     cout<<"insertAt(5, 6)\n";
     L.insertAt(5, 6);
   
     cout<<"removeAt(-1)\n";
     L.removeAt(-1);
     cout<<"removeAt(0)\n";
     L.removeAt(0);
     L.print();
     cout<<"removeAt(1)\n";
     L.removeAt(1);
     L.print();
     cout<<"removeAt(5)\n";
     L.removeAt(5);
     cout<<"removeFirst\n";
     L.removeFirst();
     L.print();
     cout<<"removeLast\n";
     L.removeLast();
     L.print();
   
     cout<<"insert(1, 2, 3)\n";
     L.insertLast(1);
     L.insertLast(2);
     L.insertLast(3);
     cout<<"Spisukut sudurja "<<L.sizeOf()<<" elementa:\n";
     L.print();
     int aValue;
     cout<<"getValueAt(1)\n";
     if(L.getValueAt(1, aValue))
     cout<<"Tam ima zapisano "<<aValue<<endl;
     cout<<"setValueAt(1, 20)\n";
     if(L.setValueAt(1, 20))
     cout<<"Uspeshen zapis\n";
     L.print();
     return 0;
   }
   

   Добавих деструктор за списъка.

   Влезте, за да отговорите
   • Данаил каза:

     14 април, понеделник в 09:05

     Да, правилно :-) В деструктора обаче може просто да извикваш removeAll…

     Влезте, за да отговорите
     • dreanor каза:

       14 април, понеделник в 10:13

       Ами да, аз почнах с идеята за деструктор и съм забравил ( не съм видял), че има вече готов метод.

       Влезте, за да отговорите