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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
aquila
0 / 0 / 0
Регистрация: 22.05.2011
Сообщений: 4
#1

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

14.01.2012, 23:47. Просмотров 2809. Ответов 3
Метки нет (Все метки)

Товарищи, всем доброго времени суток!
Есть такая вот задача:
"Для класса "упорядоченный по убыванию односвязный список" определить операцию *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     Упорядоченный односвязный список
Посмотрите здесь:

Сформировать и ввести упорядоченный односвязный список без использования list - C++
Подскажите, как сформировать и ввести упорядоченный односвязный список без использования list. Заранее спасибо!!!

Создать общий упорядоченный список - C++
Помогите, пожалуйста, вот с такой задачей. &quot;Имеются N линейных списков, имеющих одинаковую структуру и упорядоченных по возрастанию...

Упорядоченный связный список объектов класса - C++
Добрый вечер, вот уже третий день бьюсь в попытках создания связного списка из объектов класса. Задача: создать таблицу символов, в...

Циклический двунаправленный список, упорядоченный по убыванию - C++
Циклический двунаправленный список, упорядоченный по убыванию.

Включение нового значения в упорядоченный список - C++
помоги плиз сделать такую программку.... В составе программы описать функцию, которая включает в упорядо-ченный по убыванию список...

Односвязный список - C++
Начал читать про односвязные списки и никак не пойму, зачем мы выделяем память под первый элемент списка? Мы сначала определяем указатель...

Односвязный список - C++
Пришло время понять и разобраться со списками. Кто-то может посоветовать нормальные статьи в интернете? Сам уже искал, в большинстве...

Односвязный список - C++
Помогите пожалуйста написать функцию поиска числа заданного пользователем в односвязном списке

Односвязный список - C++
Написал программу, которая сортирует массив по неубыванию и добавляет в него элемент, не нарушая упорядоченности. Как переделать ее под...

Односвязный список - C++
Нужно составить код для односвязного списка (формирование и вывод). При этом нельзя использовать классы(( Вроде код правильный, но...

Односвязный список - C++
Дан список целых чисел , удалить все положительные. struct my_list{ int num; struct my_list*Next; } int x; my_list...

Односвязный список - C++
Дано два списка с целыми числами. Создать новый список в котором размещены элементы какие одновременно присутствуют в первых двух списках. ...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
easybudda
Эксперт С++
9458 / 5471 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
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
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
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     Упорядоченный односвязный список
Ответ Создать тему
Опции темы

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