Сортиране чрез списъци

Да се напише програма, която позволява да се въвеждат числа до въвеждане на 0 и ги извежда сортирани в нарастващ ред.

Публикувано в 12в с етикети . Постоянна връзка.

2 коментара по Сортиране чрез списъци

  1. kaloyan каза:
    #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);
      ListNode* L2;
      init(L2);
      int ch, br=0;
      
      //Въвеждаме елементите
      do{
      	cin>>ch;
      	//Ди въвеждане на 0
    	if(ch==0) break;
      	else {
      	  insertFirst(L, ch);
          br++;
    	}
      } while(true);
      
      //Сортираме числата
      int swap, imax, imax2;
      for(int i=0; i<br; i++) {
      	//записваме стойността на елемента на позиция i в imax
    	getValueAt(L, i, imax);
      	for(int j=i+1; j<br; j++){
      	  //записваме стойността на елемента на позиция j в imax2
    	  getValueAt(L, j, imax2);
    	  if(imax<imax2) {
    		removeAt(L, j);
    		insertFirst(L, imax);
          	imax=imax2;
    	  }
        }
        insertFirst(L2, imax);
      }
    
      removeAll(L);
      
      while(L2){
      	cout<<L2->value<<" ";
      	L2 = L2->next;
      }
      removeAll(L2);
      
      return 0;
      
    }

Вашият коментар