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

Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) - C++

Восстановить пароль Регистрация
 
 
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
22.04.2013, 10:56     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #1
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <conio.h> 
struct Node
{
    int memSize;
    Node *Next;
};
Node *BegList;
using namespace std;
void MakeList(int *Sz, int n)
{
    Node *Curr,*Prev;
    int i;
    BegList=new Node;
    BegList->Next =NULL;
    BegList->memSize=Sz[0];
    cout << Sz[0] << endl;
    Prev=BegList;
    for (i=1; i<n; i++)
    {
        Curr=new Node;
        Prev->Next =Curr;
        Curr->Next =NULL;
        Curr->memSize=Sz[i];
        cout << Sz[i] << endl;
        Prev=Curr;
    }
};
 
long searchBlock(long sz)
{
    Node *Curr, *Prev, *Nxt;
    long szBlock;
    Curr=BegList;
    Prev=NULL;
    while(1)
    {
        if (Curr == NULL) 
        {
            szBlock=-1;
            break;
        }
        if (Curr->memSize >= sz) // Нашли...
        {
           
                   Nxt=Curr->Next;
                   szBlock=Curr->memSize;
           
                  if (Curr == BegList) // Блок первый
           {
               if (Nxt == NULL) // и единственный
               {
                   delete BegList;
                   cout << "Now list is empty" << endl;
                   break;
               }
               else
               {
                   delete BegList;
                   BegList=Nxt;
                   break;
               }
 
           }
           else // блок не первый
           {
               if (Nxt == NULL)  // последний
               {
                   delete Curr;
                   Prev->Next=NULL;
                   break;
               }
               else
               {
                   delete Curr;
                   Prev->Next=Nxt;
                   break;
               }
           }
           
        }
        Prev=Curr;
        Curr=Curr->Next;
    }
    return  szBlock;
};
void DeleteList()
{
    Node *Curr,*Next;
    Curr=BegList;
    while (1)
    {
      Next=Curr->Next;
      delete Curr;
      if (Next == NULL) break;
      Curr=Next;
    }
};
   
// Распечатать список
 
void PrintList()
{
    Node *Curr,*Next;
    Curr=BegList;
    while (1)
    {
      Next=Curr->Next;
      cout << Curr->memSize << endl; 
      if (Next == NULL) break;
      Curr=Next;
    }
};
           
int main(int argc, char* argv[])
{
    int szB[]={100,200,300,400,500};
    long bs,bq;
    cout << "Initial List:" << endl;
    MakeList (szB,sizeof(szB)/sizeof(int));
    cout << endl << "Enter block size: ";
    cin >> bs;
    if ((bq=searchBlock(bs)) > 0)
        cout << "Block (" << bq << " ) is found" << endl;
    else
        cout << "Block not found!" << endl;
    cout << endl;
    PrintList();
    DeleteList();
    getch();
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2013, 10:56     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю)
Посмотрите здесь:

Нужно переделать прогу! C++
Как переделать двусвязный список в циклический c++ C++
C++ Однонаправленный список: переделать код под консоль
C++ Возможно ли как-то переделать односвязный список в двусвязный?
Под С++ нужно переделать C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
22.04.2013, 11:14     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #2
Lonter, а может сначала воспользоваться поиском? Тема уже много раз поднималась.
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
22.04.2013, 12:21  [ТС]     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #3
В том и суть что не нашел то что мне надо
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
22.04.2013, 12:28     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #4
Lonter, так напишите задание лучше.
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
22.04.2013, 12:30  [ТС]     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #5
Моделирование распределения памяти в операционной системе. Дан линейный двусвязный список свободных блоков памяти (адрес начала блока, размер блока). На входе подается запрос на блок памяти определенного размера. Требуется найти в списке первый подходящий по размеру узел, произвести необходимые изменения в списке или выдать сообщение, что подходящего блока памяти в списке нет.
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
22.04.2013, 12:33     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #6
Lonter, и что именно у вас не получается? И как задавать размер каждого блока памяти?)
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
22.04.2013, 12:38  [ТС]     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #7
ну я же скинул с односвязными) а не могу под двусвязные переделать)
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
22.04.2013, 12:50     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #8
Lonter, не, ну вы смеетесь, что вам не понятно? Я так понимаю это не ваш код?
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
22.04.2013, 12:51  [ТС]     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #9
Конечно не мой=)
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
22.04.2013, 12:57     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #10
Lonter, а вам не кажется это уже наглостью? мало того что код не ваш, так вы хотите чтобы вам его еще и исправили, а вы что сделаете?
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
22.04.2013, 13:00  [ТС]     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #11
это отдельная программа.....половину уж я точно сам написал, просто товарищ подправил, где были косяки.... а теперь уже следующее задание... надо сделать тоже что с односвязным только с двусвязным, а я в двусвязных ни шлеп ногой

Добавлено через 54 секунды
И вообще товарищ дорогой, сарказм надо чуять за версту!
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
22.04.2013, 13:05     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #12
Lonter, так а что мешает взять книжку и почитать? Отличие двусвязного списка от односвязного в наличие указателя на предыдущий элемент.
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
22.04.2013, 13:06  [ТС]     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #13
так вот я и не могу догнать зачем он вообще нужен?
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
22.04.2013, 13:12     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #14
Lonter, я не супер спец в объяснении, но в отличие от односвязного можно идти как с начала в конец, так и с конца в начало, плюс добавление в конец не требует прохода по всему списку для поиска конца, так как конец мы сами будем знать Tail.
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
22.04.2013, 13:14  [ТС]     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #15
то есть грубо говоря, мне надо будет изменить только одну функцию, ввода и в глобальной переменной?
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
22.04.2013, 13:39     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #16
Lonter, у тебя изменяться функция добавления, удаления, вывода, смотри, когда ты добавляешь элемент, ты указываешь кто сзади и кто спереди.
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
22.04.2013, 13:41  [ТС]     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #17
Ну я еще поспрашиваю) может кто напишет еще)
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
22.04.2013, 13:55     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #18
Цитата Сообщение от Lonter Посмотреть сообщение
Ну я еще поспрашиваю) может кто напишет еще)
Да конечно напишут. Как говорил один замечательный преподаватель: "Чем меньше вы знаете, тем ценнее я как специалист".


Чета лень мне читать тот код. Да и в тэги не обернут. Да и написан скучно как-то.

С нуля:
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <stdexcept>
#include <new>
 
struct Block {
  size_t size;
  void *pointer;
  Block() : size(0), pointer(0) {}
  Block(size_t size, void *pointer) : size(size), pointer(pointer) {}
};
 
bool operator<(const Block &a, const Block &b) {
  return a.size < b.size;
}
 
class BlockList {
 public:
  BlockList() : base() {}
  virtual ~BlockList() {
    clear();
  }
  void put(const Block &block) {
    NodeBase *node = lowerBound(block.size);
    new Node(node->prev, node, block);
  }
  Block get(size_t size) {
    NodeBase *node = lowerBound(size);
    if (node != &base) {
      Block result = ((Node*)node)->data;
      delete node;
      return result;
    }
    throw std::bad_alloc();
  }
  bool isEmpty() const { return base.next == &base; }
  void clear() {
    while (!isEmpty()) {
      delete base.next;
    }
  }
  friend std::ostream &operator<<(std::ostream &stream, const BlockList &b) {
    stream << "BlockList{[";
    NodeBase *node = b.base.next;
    while (node != &(b.base)) {
      stream << ((Node*)node)->data.size;
      if (node->next != &(b.base)) {
        stream << ",";
      }
      node = node->next;
    }
    return stream << "]}";
  }
 private:
  BlockList(const BlockList&);
  BlockList &operator=(const BlockList&);
  struct NodeBase {
    NodeBase *prev, *next;
    NodeBase() : prev(this), next(this) {}
    NodeBase(NodeBase *prev, NodeBase *next) : prev(prev), next(next) {
      prev->next = next->prev = this;
    }
    virtual ~NodeBase() {
      prev->next = next;
      next->prev = prev;
    }
  };
  struct Node : public NodeBase {
    Block data;
    Node(NodeBase *prev, NodeBase *next, const Block &data)
      : NodeBase(prev, next), data(data) {}
  };
  // возвращает позицию первого блока, не меньше указанного
  NodeBase *lowerBound(size_t size) {
    NodeBase *result = base.next;
    while (result != &base && ((Node*)result)->data.size < size) {
      result = result->next;
    }
    return result;
  }
  NodeBase base;
};
 
int main(int argc, char *argv[]) {
  srand(time(0));
  
  BlockList heap;
  
  for (int i = 0; i < 15; ++i) {
    heap.put(Block(rand() % 10 + 1, 0));
  }
  
  std::cout << heap << std::endl;
  
  for (int i = 0; i < 25; ++i) {
    Block block;
    size_t size = rand() % 13;
    std::cout << "Trying to allocate " << size << " bytes: ";
    try {
      block = heap.get(size);
      std::cout << "allocated block with " << block.size << " bytes.";
      if (!(rand() % 5)) {
        std::cout << " Returning.";
        heap.put(block);
      }
    } catch (std::bad_alloc &e) {
      std::cout << "could not allocate.";
    }
    std::cout << std::endl;
  }
  
  std::cout << "Leftover:" << std::endl << heap << std::endl;
  
  return 0;
};
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
22.04.2013, 14:06  [ТС]     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #19
Спасибо, надо только разобраться )))

Добавлено через 1 минуту
а она разве в двусвязных написана?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.04.2013, 14:41     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю)
Еще ссылки по теме:

C++ Как переделать эту прогу в шаблон классов "Двусвязный список" произвольных элементов
Переделать на Двусвязный список C++
C++ Переделать программу с односвязного на двусвязный список

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

Или воспользуйтесь поиском по форуму:
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
22.04.2013, 14:41     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю) #20
Цитата Сообщение от Lonter Посмотреть сообщение
а она разве в двусвязных написана?
Да вы разбирайтесь, разбирайтесь.
Yandex
Объявления
22.04.2013, 14:41     Выручайте! Нужно переделать прогу под двусвязный список.ничего не понимаю)
Ответ Создать тему
Опции темы

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