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

Нужен совет - как сделать circular linked list? - C++

Восстановить пароль Регистрация
 
QWERY_2012
5 / 5 / 2
Регистрация: 09.09.2012
Сообщений: 227
16.03.2013, 08:26     Нужен совет - как сделать circular linked list? #1
Доброго всем времени суток!!!

У меня программа которая считает queue, мне необходимо сделать circular linked list.
Прошу помоши!!!!!

header file:
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
// TEMPLATE CLASS PROVIDED: queue<Item> (a queue of items)
//
// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the stack<Item> class:
//   The template parameter, Item, is the data type of the items in the queue,
//   also defined as queue<Item>::value_type. It may be any of the C++ built-in
//   types (int, char, etc.), or a class with a default constructor, a copy
//   constructor, and an assignment operator. The definition
//   queue<Item>::size_type is the data type of any variable that keeps track of
//   how many items are in a queue.
// NOTE:
//   Many compilers require the use of the new keyword typename before using
//   the expressions queue<Item>::value_type and queue<Item>::size_type.
//   Otherwise the compiler doesn't have enough information to realize that it
//   is the name of a data type.
//
// CONSTRUCTOR for the queue<Item> template class:
//   queue( )
//     Postcondition: The queue has been initialized as an empty queue.
//
// MODIFICATION MEMBER FUNCTIONS for the queue<Item> template class:
//   void pop( )
//     Precondition: size( ) > 0.
//     Postcondition: The front item of the queue has been removed.
//
//   void push(const Item& entry)
//     Postcondition: A new copy of entry has been inserted at the rear of the
//     queue.
//
// CONSTANT MEMBER FUNCTIONS for the queue<Item> template class:
//   bool empty( ) const
//     Postcondition: The return value is true if the queue is empty.
//
//   Item front( ) const
//     Precondition: size( ) > 0
//     Postcondition: The return value is a copy of the item at
//     the front of the queue (and the queue is unaltered).
//
//   size_type size( ) const
//     Postcondition: The return value is the total number of items in the queue.
//
// VALUE SEMANTICS for the queue<Item> template class:
//   Assignments and the copy constructor may be used with queue<Item> objects.
 
#ifndef MAIN_SAVITCH_QUEUE2_H     // Prevent duplicate definition
#define MAIN_SAVITCH_QUEUE2_H
#include <cstdlib>   // Provides std::size_t
#include "node2.h"   // Node template class
 
namespace main_savitch_8C
{
    template <class Item>
    class queue
    {
    public:
        // TYPEDEFS 
        typedef std::size_t size_type;
        typedef Item value_type;
        // CONSTRUCTORS and DESTRUCTOR
        queue( );
    queue(const queue<Item>& source);
    ~queue( );
        // MODIFICATION MEMBER FUNCTIONS
        void pop( );
        void push(const Item& entry);
    void operator =(const queue<Item>& source);
        // CONSTANT MEMBER FUNCTIONS
        bool empty( ) const { return (count == 0); }
    Item front( ) const;
    size_type size( ) const { return count; }
    private:
        main_savitch_6B::node<Item> *front_ptr;
        main_savitch_6B::node<Item> *rear_ptr; 
        size_type count;       // Total number of items in the queue
    };
}
#include "queue2.template" // Include the implementation
     
#endif
implementation:
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
// FILE: queue2.template
// TEMPLATE CLASS IMPLEMENTED: Queue<Item> (see queue2.h for documentation)
// This file is included in the header file, and not compiled separately.
// INVARIANT for the Queue class:
//   1. The number of items in the queue is stored in the member variable
//      count.
//   2. The items in the queue are stored in a linked list, with the front of
//      the queue stored at the head node, and the rear of the queue stored at
//      the final node.ГЌГі
//   3. The member variable front_ptr is the head pointer of the linked list of
//      items. For a non-empty queue, the member variable rear_ptr is the
//      tail pointer of the linked list; for an empty list, we don't care
//      what's stored in rear_ptr.
 
#include <cassert>   // Provides assert
#include "node2.h"   // Node template class
 
namespace main_savitch_8C
{
    template <class Item>
    queue<Item>::queue( )
    {
        count = 0;
        front_ptr = NULL;
    }
 
    template <class Item>
    queue<Item>::queue(const queue<Item>& source)
    // Library facilities used: node2.h
    {
    count = source.count;
    list_copy(source.front_ptr, front_ptr, rear_ptr);
    }
 
    template <class Item>
    queue<Item>::~queue( )
    {
        list_clear(front_ptr);
    }
 
    template <class Item>
    void queue<Item>::operator =(const queue<Item>& source)
    // Library facilities used: node2.h
    {
        if (this == &source) // Handle self-assignment
            return;
        list_clear(front_ptr);
        list_copy(source.front_ptr, front_ptr, rear_ptr);
        count = source.count;
    }
 
    template <class Item>
    Item queue<Item>::front( ) const
    // Library facilities used: cassert
    {
        assert(!empty( ));    
        return front_ptr->data( );
    }
    
    template <class Item>
    void queue<Item>::pop( )
    // Library facilities used: cassert, node2.h
    {
        assert(!empty( ));
    list_head_remove(front_ptr);
    --count;
    }
    
    template <class Item>
    void queue<Item>::push(const Item& entry)
    // Library facilities used: node2.h
    {
        if (empty( ))
        {   // Insert first entry.
            list_head_insert(front_ptr, entry);
            rear_ptr = front_ptr;
        }
        else
        {   // Insert an entry that is not the first.
            list_insert(rear_ptr, entry);
            rear_ptr = rear_ptr->link( );
        }
        ++count;
    }
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.03.2013, 08:26     Нужен совет - как сделать circular linked list?
Посмотрите здесь:

Связанный список (Linked list). C++
Нужен совет а то не знаю как начать C++
Нужен совет, как правильно написать клас C++
Проверить программу с linked list C++
C++ C-style Linked List
Linked List описание C++
C++ Нужен совет: как лучше всего сгенерировать документ .doc с оформлением по ГОСТу
Linked List: error C2360: initialization of 'vp' is skipped by 'case' label C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
QWERY_2012
5 / 5 / 2
Регистрация: 09.09.2012
Сообщений: 227
17.03.2013, 10:56  [ТС]     Нужен совет - как сделать circular linked list? #2
необходимо учесть что программа не имеет больше front pointer иa rear pointer, только a rear pointer.

Please, help!!!
lemegeton
 Аватар для lemegeton
2908 / 1337 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
17.03.2013, 13:01     Нужен совет - как сделать circular linked list? #3
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
template <class T>
class Queue {
 public:
  Queue() : base(), queueSize(0) {}
  virtual ~Queue() {
    while (!empty()) {
      pop();
    }
  }
  void pop() {
    NodeBase *next = base.next->next;
    delete base.next;
    base.next = next;
    --queueSize;
  }
  void push(const T &value) {
    ++queueSize;
    base.next = new Node(&base, value);
  }
  bool empty() const {
    return base.next == &base;
  }
  const T &front() const {
    return (static_cast<Node*>(base.next))->value;
  }
  size_t size() const {
    return queueSize;
  }
 private:
  // запрет копирования
  Queue(const Queue &other);             // конструктором
  Queue &operator=(const Queue &other);  // оператором "="
  struct NodeBase {
    NodeBase() : next(this) {}
    NodeBase(NodeBase *prev) : next(prev->next) {
      prev->next = this;
    }
    NodeBase *next;
  };
  struct Node : public NodeBase {
    T value;
    Node(NodeBase *prev, const T &value) : NodeBase(prev), value(value) {}
  };
  NodeBase base;
  size_t queueSize;
};
Yandex
Объявления
17.03.2013, 13:01     Нужен совет - как сделать circular linked list?
Ответ Создать тему
Опции темы

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