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

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

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

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

14.01.2012, 23:47. Просмотров 2889. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.01.2012, 23:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Упорядоченный односвязный список (C++):

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

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

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

Задали односвязный линейный список с целыми числами. Создать новый список, который содержит элементы заданного списка в обратном порядке - C++
Задали односвязный линейный список с целыми числами. Создать новый список, который содержит элементы заданного списка в обратном порядке.

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

Создать базовый класс «Список» и класс-потомок «Упорядоченный список» - C++
Создать базовый класс «список», определив в нем функции добавления в начало списка, удаления N-го элемента списка, вывода элементов списка...

3
easybudda
Модератор
Эксперт CЭксперт С++
9663 / 5613 / 952
Регистрация: 25.07.2009
Сообщений: 10,777
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;
}
2
lemegeton
2925 / 1354 / 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;
}
1
aquila
0 / 0 / 0
Регистрация: 22.05.2011
Сообщений: 4
15.01.2012, 15:54  [ТС] #4
Всем просто огромное спасибо! Пойду разбираться
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.01.2012, 15:54
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
4
Yandex
Объявления
15.01.2012, 15:54
Ответ Создать тему
Опции темы

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