Форум программистов, компьютерный форум CyberForum.ru

Упорядоченный односвязный список - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
aquila
0 / 0 / 0
Регистрация: 22.05.2011
Сообщений: 4
14.01.2012, 23:47     Упорядоченный односвязный список #1
Товарищи, всем доброго времени суток!
Есть такая вот задача:
"Для класса "упорядоченный по убыванию односвязный список" определить операцию *int (умножается каждый ключ)".
Собсна говоря, сам список готов (исходный код отсюда и брался ). Ни в какую не могу понять, как можно организовать это упорядочивание. Прошу помощи И, если не лень и не трудно, наведите на правильный ход мысли, как перегрузить оператор * для списка. (не отказалась бы и от конкретного примера :] )

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
 
using namespace std;
 
struct Elem                // элемент списка
{
       int data;
       Elem *next;
};
 
class List
{
      Elem *pHead;      //первый элемент
      Elem *pPrev;      //последний элемент
      
      public:
             List();
             ~List();
             
             void addToList(int data);
             void printList();
             void delAllList();
 
};
 
List::List()
{
    pHead = NULL;
};
 
List::~List()
{
    delAllList();
};
 
void List::addToList(int data)
{
    Elem *temp = new Elem;
    if(pHead == NULL)
        pHead = temp;
    else
        pPrev->next = temp;
    temp->data = data;
    temp->next = NULL;
    pPrev = temp;
};
 
void List::printList()
{
    Elem *pTemp = pHead;
    while(pTemp != NULL)
    {
        cout << pTemp->data << " ";
        pTemp = pTemp->next;
    };
};
 
void List::delAllList()
{
    while(pHead != NULL)
    {
        Elem *pTemp = pHead;
        pHead = pHead->next;
        delete pTemp;
    };
};
 
int main()
{
  List list;
 
  list.addToList(5);
  list.addToList(7);
  list.addToList(10);
  list.addToList(4);
  list.addToList(2);
 
  cout << "Список: ";
  list.printList();
  cout << endl;
 
  return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.01.2012, 23:47     Упорядоченный односвязный список
Посмотрите здесь:

Включение нового значения в упорядоченный список C++
C++ Циклический двунаправленный список, упорядоченный по убыванию
Сформировать и ввести упорядоченный односвязный список без использования list C++
Задали односвязный линейный список с целыми числами. Создать новый список, который содержит элементы заданного списка в обратном порядке C++
Односвязный список C++
C++ Односвязный список
Односвязный список C++
C++ Сформировать список из 10 книг, используя динамическую структуру данных односвязный список
C++ Упорядоченный связный список объектов класса
C++ Создать двусвязный список групп факультета, где каждая группа представляет собой односвязный список студентов
C++ Создать базовый класс «Список» и класс-потомок «Упорядоченный список»
Создать общий упорядоченный список C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9382 / 5432 / 916
Регистрация: 25.07.2009
Сообщений: 10,428
15.01.2012, 03:40     Упорядоченный односвязный список #2
aquila, а стандартный std::set из STL вам по религиозным причинам использовать не разрешают? Вот нагородил не бог весть что, но вроде работает (значения не дублируются - так задумано)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
 
class DescendantSortedList {
    class Node {
        int value;
        Node * next;
    public:
        Node(int val) : value(val), next(0) {}
        Node * Next() const { return next; }
        void Next(Node * n) { next = n; }
        int Value() const { return value; }
        void Value(int val) { value = val; }
    };
    
    Node * head;
    
    DescendantSortedList(const DescendantSortedList &);
    DescendantSortedList & operator = (const DescendantSortedList &);
    
public:
    DescendantSortedList() : head(0) {}
    ~DescendantSortedList() {
        Node * tail;
        while ( head ){
            tail = head->Next();
            delete head;
            head = tail;
        }
    }
    void operator * (int m) {
        for ( Node * n = head; n; n = n->Next() )
            n->Value(n->Value() * m);
    }
    DescendantSortedList & operator << (int val) {
        Node * n = new Node(val);
        if ( ! head ) {
            head = n;
        }
        else if ( head->Value() < val ){
            n->Next(head);
            head = n;
        }
        else if ( head->Value() == val ){
            delete n;
        }
        else {
            Node * f;
            for ( f = head; f->Next() && f->Next()->Value() > val; f = f->Next() )
                ;
            if ( f->Next() ) {
                if ( f->Next()->Value() == val )
                    delete n;
                else {
                    n->Next(f->Next());
                    f->Next(n);
                }
            }
            else
                f->Next(n);
        }
        
        return *this;
    }
    void dump(std::ostream & ost) const {
        for ( Node * n = head; n; n = n->Next() )
            ost << n->Value() << " ";
        ost << std::endl;
    }
};
 
int main(){
    DescendantSortedList dsl;
    
    dsl << 13 << 4 << 69 << 8 << 89 << 14 << 13 << 90;
    dsl.dump(std::cout);
    dsl * 2;
    dsl.dump(std::cout);
    
    return 0;
}
Добавлено через 49 минут
Просто из спортивного интереса написал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
#include <functional>
#include <vector>
 
class DescendantSortedList : public std::multiset<int, std::greater_equal<int> > {
    DescendantSortedList(const DescendantSortedList &);
    DescendantSortedList & operator = (const DescendantSortedList &);
public:
    DescendantSortedList() : std::multiset<int, std::greater_equal<int> >() {}
    ~DescendantSortedList() {}
    DescendantSortedList & operator << (int val) {
        insert(val);
        return *this;
    }
    friend std::ostream & operator << (std::ostream & ost, const DescendantSortedList & dsl) {
        std::copy(dsl.begin(), dsl.end(), std::ostream_iterator<int>(ost, " "));
        return ost;
    }
    DescendantSortedList & operator * (int m){
        std::vector<int> vec;
        for ( std::multiset<int, std::greater_equal<int> >::const_iterator i = begin(); i != end(); ++i )
            vec.push_back(*i * m);
        clear();
        std::copy(vec.begin(), vec.end(), std::inserter(*this, begin()));
        return *this;
    }
};
 
int main(){
    DescendantSortedList dsl;
    
    dsl << 33 << 1 << 14 << 58 << 19 << 24 << 33;
    
    std::cout << dsl << std::endl << dsl * 2 << std::endl;
    
    return 0;
}
lemegeton
 Аватар для lemegeton
2913 / 1342 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
15.01.2012, 12:06     Упорядоченный односвязный список #3
Цитата Сообщение от aquila Посмотреть сообщение
Собсна говоря, сам список готов (исходный код отсюда и брался ).
Слабый код, не очень подходит для задачи.
Если список сортированный, то накладываются некоторые ограничения на данные. Например, нельзя менять данные напрямую.

Из спортивного интересу. Без удаления элементов из списка. Для удаления элементов надо написать поиск элемента и удаление элемента из списка по итератору.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
 
struct NodeBase {
  NodeBase *next;
  NodeBase() : next(this) {}
  NodeBase(NodeBase *next_) : next(next_) {}
};
 
template <class T>
struct NodeType : public NodeBase {
  NodeType(NodeBase *next_, const T &data_) : NodeBase(next_), data(data_) {}
  T data;
};
 
template <class T>
class SortedList {
 public:
  typedef NodeType<T> Node;
  class Iterator {
   public:
    Iterator(const Iterator &iterator) : node_(iterator.node_) {}
    Iterator(const NodeBase *node) : node_(node) {}
    Iterator &operator++() { node_ = node_->next; return *this; }
    const T &operator*() const { return static_cast<const Node*>(node_)->data; }
    const T &operator->() const { return static_cast<const Node*>(node_)->data; }
    bool operator==(const Iterator &other) { return other.node_ == node_; }
    bool operator!=(const Iterator &other) { return !(*this == other); }
   private:
    const NodeBase *node_;
  };
  SortedList() : base_() {}
  SortedList(const SortedList &other) : base_() {
    for (Iterator i = other.begin(); i != other.end(); ++i)
      insertSorted(*i);
  }
  ~SortedList() { clear(); }
  SortedList &operator=(const SortedList &other) {
    if (this != &other) {
      for (Iterator i = other.begin(); i != other.end(); ++i)
        insertSorted(*i);
      clear();
    }
    return *this;
  }
  void insertSorted(const T &data) {
    NodeBase *prev = &base_;
    NodeBase *next = base_.next;
    while (next != &base_ && static_cast<Node*>(next)->data < data) {
      next = next->next;
      prev = prev->next;
    }
    Node *node = new Node(next, data);
    prev->next = node;
  }
  Iterator begin() const { return Iterator(base_.next); }
  Iterator end() const { return Iterator(&base_); }  
  bool isEmpty() const {
    return base_.next == &base_;
  }
  void clear() {
    while (base_.next != &base_) {
      NodeBase *node = base_.next->next;
      delete base_.next;
      base_.next = node;
    }
  }
 private:
  NodeBase base_;
};
 
SortedList<int> operator*(const SortedList<int> &list, int multiplier) {
  SortedList<int> result;
  for (SortedList<int>::Iterator i = list.begin(); i != list.end(); ++i)
    result.insertSorted(*i * multiplier);
  return result;
}
 
template <class T>
std::ostream &operator<<(std::ostream &stream, const SortedList<T> &list) {
  for (typename SortedList<T>::Iterator i = list.begin(); i != list.end(); ++i)
    stream << *i << " ";
  return stream;
}
 
int main(int argc, char *argv[]) {
  SortedList<int> a;
  a.insertSorted(5);
  a.insertSorted(5);
  a.insertSorted(7);
  a.insertSorted(6);
  a.insertSorted(4);
  a.insertSorted(4);
  a.insertSorted(8);
  std::cout << a << std::endl;
  std::cout << (a * 2) << std::endl;
  std::cout << (a * -1) << std::endl;
  std::cout << std::endl;
}
aquila
0 / 0 / 0
Регистрация: 22.05.2011
Сообщений: 4
15.01.2012, 15:54  [ТС]     Упорядоченный односвязный список #4
Всем просто огромное спасибо! Пойду разбираться
Yandex
Объявления
15.01.2012, 15:54     Упорядоченный односвязный список
Ответ Создать тему
Опции темы

Текущее время: 00:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru