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

Одноправленный линейный список - C++

Восстановить пароль Регистрация
 
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
14.02.2012, 12:30     Одноправленный линейный список #1
Дайте идею пожалуйста
создать пользовательский тип данных который создает массив переменной длины с использованием одноправленного линейного списка
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.02.2012, 12:30     Одноправленный линейный список
Посмотрите здесь:

C++ линейный список на с++
C++ Линейный список
C++ Линейный список.
C++ Линейный список
C++ [C++] Линейный список
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
14.02.2012, 13:25     Одноправленный линейный список #2
Идея, в целом, такова.
Создавать ноду, которая сама себя разместит. Для этого ей необходимо знать, за какой нодой она идет.
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
#include <iostream>
 
template <class T>
class OneLinkedList {
 public:
  struct Node {
    Node() : next(this) {}
    Node(Node *after, const T &data_) : next(after->next), data(data_) {
      after->next = this;
    }
    Node *next;
    T data;
  };
  OneLinkedList() : base(new Node()) {}
  ~OneLinkedList() {
    clear();
    delete base;
  }
  void pushFront(const T &value) {
    new Node(base, value);
  }
  void pushBack(const T &value) {
    new Node(getLastNode(), value);
  }
  const T &get(size_t n) const {
    Node *result = base->next;
    while (n--) result = result->next;
    return result->data;
  }
  bool empty() const {
    return base == base->next;
  }
  size_t size() const {
    size_t result = 0;
    for (Node *node = base; node->next != base; node = node->next)
      ++result;
    return result;
  }
  void clear() {
    while (!empty()) {
      Node *next = base->next;
      base->next = next->next;
      delete next;
    }
  }
  T &operator[](size_t n) {
    Node *result = base->next;
    while (n--) result = result->next;
    return result->data;
  }
  const T &operator[](size_t n) const {
    return get(n);
  }
 private:
  Node *getLastNode() {
    Node *result = base->next;
    while (result->next != base) result = result->next;
    return result;
  }
  OneLinkedList(const OneLinkedList&);
  OneLinkedList &operator=(const OneLinkedList&);
  Node *base;
};
 
int main(int argc, char *argv[]) {
  OneLinkedList<int> a;
  for (int i = 0; i < 10; ++i)
    if (i % 2)
      a.pushBack(i);
    else
      a.pushFront(i);
  for (size_t i = 0; i < a.size(); ++i)
    std::cout << (a[i] = a[i] + 1) << " ";
  std::cout << std::endl;
  for (size_t i = 0; i < a.size(); ++i)
    std::cout << a[i] << " ";
  std::cout << std::endl;
}
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
14.02.2012, 22:11  [ТС]     Одноправленный линейный список #3
Цитата Сообщение от lemegeton Посмотреть сообщение
Идея, в целом, такова.
Создавать ноду, которая сама себя разместит. Для этого ей необходимо знать, за какой нодой она идет.
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
#include <iostream>
 
template <class T>
class OneLinkedList {
 public:
  struct Node {
    Node() : next(this) {}
    Node(Node *after, const T &data_) : next(after->next), data(data_) {
      after->next = this;
    }
    Node *next;
    T data;
  };
  OneLinkedList() : base(new Node()) {}
  ~OneLinkedList() {
    clear();
    delete base;
  }
  void pushFront(const T &value) {
    new Node(base, value);
  }
  void pushBack(const T &value) {
    new Node(getLastNode(), value);
  }
  const T &get(size_t n) const {
    Node *result = base->next;
    while (n--) result = result->next;
    return result->data;
  }
  bool empty() const {
    return base == base->next;
  }
  size_t size() const {
    size_t result = 0;
    for (Node *node = base; node->next != base; node = node->next)
      ++result;
    return result;
  }
  void clear() {
    while (!empty()) {
      Node *next = base->next;
      base->next = next->next;
      delete next;
    }
  }
  T &operator[](size_t n) {
    Node *result = base->next;
    while (n--) result = result->next;
    return result->data;
  }
  const T &operator[](size_t n) const {
    return get(n);
  }
 private:
  Node *getLastNode() {
    Node *result = base->next;
    while (result->next != base) result = result->next;
    return result;
  }
  OneLinkedList(const OneLinkedList&);
  OneLinkedList &operator=(const OneLinkedList&);
  Node *base;
};
 
int main(int argc, char *argv[]) {
  OneLinkedList<int> a;
  for (int i = 0; i < 10; ++i)
    if (i % 2)
      a.pushBack(i);
    else
      a.pushFront(i);
  for (size_t i = 0; i < a.size(); ++i)
    std::cout << (a[i] = a[i] + 1) << " ";
  std::cout << std::endl;
  for (size_t i = 0; i < a.size(); ++i)
    std::cout << a[i] << " ";
  std::cout << std::endl;
}
спасибо большое
но к сожалению я с классами еще не знаком и познакомлюсь скорей всего только через год
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
15.02.2012, 08:22     Одноправленный линейный список #4
Цитата Сообщение от crewww Посмотреть сообщение
пользовательский тип данных который создает
Какой вопрос, такой и ответ. Единственный пользовательский тип данных, который (условно) может "что-то делать", это класс.

Тем не менее, та же самая логика справедлива и для структур. Создавайте "кольцевой" список и вставляйте ноды как в моем примере.
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
15.02.2012, 12:32  [ТС]     Одноправленный линейный список #5
Цитата Сообщение от lemegeton Посмотреть сообщение
Какой вопрос, такой и ответ. Единственный пользовательский тип данных, который (условно) может "что-то делать", это класс.

Тем не менее, та же самая логика справедлива и для структур. Создавайте "кольцевой" список и вставляйте ноды как в моем примере.
хорошо я попробую со структурами
Yandex
Объявления
15.02.2012, 12:32     Одноправленный линейный список
Ответ Создать тему
Опции темы

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