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

Связанные списки (переделать программу) - C++

Восстановить пароль Регистрация
 
wolf1396
5 / 5 / 0
Регистрация: 07.05.2013
Сообщений: 192
18.07.2013, 15:36     Связанные списки (переделать программу) #1
Как переделать программу, чтобы можно было вводить самому ключи и не было Access Violation?
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <time.h>
#include <string.h>
using namespace std;
 
char buff[500];
 
struct str {
    str *pred;
    str *next;
    int key;
};
 
int main() {
    setlocale(LC_ALL, "Russian");
    //Задание 1     
    srand(time(NULL));
    str *a = new str;
    str *b = a;
    a->pred = 0;
    for (int i = 0; i < 10; i++) {
        cin >> b->key; //Обращаемся к key из структуры b ( заполняем его случайными числами)
        b->next = new str; //Обращаемся к next из структуры b
        b->next->pred = b; //Обращаемся к pred из структуры next, которая находится в b
        b = b->next; //переход в следующую структуру
    }
    //b->key = rand();
    //b->next = 0;
    cout << "Ключи неотсортированнного списка: " << endl;
    b = a;
    while (b) //пока есть структуры, выводятся их ключи
    {
        cout << b->key << " ";
        b = b->next;
    }
    cout << "\nКлючи отсортированного в порядке возрастания списка: " << endl;
    str *z, *y;
    b = a;
    while (b) {
        z = b;
        y = b->next;
        while (y) {
            if (z->key < y->key) {
                z = y;
            }
            y = y->next;
        }
        if (z == b) {
            b = b->next;
        }
        if (z->next != 0) {
            z->next->pred = z->pred;
        }
        z->pred->next = z->next;
        z->next = a;
        a->pred = z;
        a = z;
    }
    b = a;
    while (b) {
        cout << b->key << " ";
        b = b->next;
    }
    while (a) {
        str *kk = a;
        a = a->next;
        delete kk;
    }
    return 0;
}


помогите пожалуйста, мне срочно нужно сдать, а то на бюджетное не переведут
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.07.2013, 15:36     Связанные списки (переделать программу)
Посмотрите здесь:

C++ Односвязанные и двух-связанные списки
Динамические структуры (связанные списки) C++
C++ Переделать код из массива в списки
C++ связанные списки
Связанные списки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
18.07.2013, 19:03     Связанные списки (переделать программу) #2
Что за задание? Какие ограничения на решение?
wolf1396
5 / 5 / 0
Регистрация: 07.05.2013
Сообщений: 192
18.07.2013, 19:16  [ТС]     Связанные списки (переделать программу) #3
Цитата Сообщение от lemegeton Посмотреть сообщение
Что за задание? Какие ограничения на решение?
нужно сделать так, чтобы с клавиатуры можно было ввести ключи и не было Access Violation

мне бы найти пару алгоритмов сортировки массива по ключам и все ок будет

на данный момент у меня есть циклическое создание структур (динамически надо создать с пом. new+delete)
+ вывод на экран циклом ключей (без сортировки)

Кликните здесь для просмотра всего текста
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
// test_list.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <string.h>
using namespace std;
 
 
struct str
{
    str *pred;
    str *next;
    int key;
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL, "Russian");
    str *a = new str;
    str *b = a;
    a->pred = 0;
    for(int i = 1; i < 10; i++)
    {
        cin >> b->key;// = rand();  //Обращаемся к key из структуры b ( заполняем его случайными числами)
        b->next = new str;  //Обращаемся к next из структуры b
        b->next->pred = b;  //Обращаемся к pred из структуры next, которая находится в b
        b = b->next;    //переход в следующую структуру
    }
    cin >> b->key;// = rand();
    b->next = 0;
    cout << "Ключи неотсортированнного списка: " << endl;
    b = a;
    while(b) //пока есть структуры, выводятся их ключи
    {
        cout << b->key << " ";
        b = b->next;
    }
    b=a;
    cout << "\n Сортировка по ключам" << endl;
    
    while(a) //пока есть структуры, выводятся их ключи
    {
        cout << a->key << " ";
        a = a->next;
    }
    while(a)
    {
        str *kk = a;
        a = a->next;        
        delete kk;
    }
    return 0;
}
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
21.07.2013, 11:28     Связанные списки (переделать программу) #4
Я так понял, что вы застряли на заполнении связного списка. В процедурном стиле.

Ваш код очень комплексен и непонятен. Давайте его сильно упростим, добавив структуру и несколько функций в пару строк каждая.

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>
#include <string>
 
/**
 * Самодобавляющийся и самоудаляющийся элемент связного списка (нода)
 * без данных, на основе которой можно создавать связный список.
 */
struct NodeBase {
  NodeBase *prev;
  NodeBase *next;
  NodeBase(NodeBase *prev, NodeBase *next) : prev(prev), next(next) {
    prev->next = this;
    next->prev = this;
  }
  NodeBase() : prev(this), next(this) {}
  virtual ~NodeBase() {
    prev->next = next;
    next->prev = prev;
  }
};
 
/**
 * Элемент связного списка (нода), содержащий данные.
 */
struct Node : public NodeBase {
  int value;
  Node(NodeBase *prev, NodeBase *next, const int &value)
    : NodeBase(prev, next), value(value) {}
};
 
/**
 * Вставка в связный список перед определенным элементом
 */
void insert(NodeBase *before, const int &value) {
  new Node(before->prev, before, value);
}
 
/**
 * Проверка связного списка, переданного параметром, на пустоту. 
 * Связный список считается пустым, если его следующий и/или предыдущий
 * элемент указывают на себя же.
 */
bool isEmpty(NodeBase *list) {
  return list->next == list;
}
 
/**
 * Очистка связного списка, удаление всех эелементов, кроме переданного
 * параметром.
 */
void clear(NodeBase *list) {
  while (!isEmpty(list)) {
    delete list->next;
  }
}
 
/**
 * Вывод списка на экран.
 */
void printIntegerList(NodeBase *list) {
  NodeBase *node = (list->next); 
  while (node != list) {
    std::cout << static_cast<Node*>(node)->value << std::endl;
    node = node->next;
  }
}
 
int main(int, char**) {
  // Элемент связного списка перед первым и (он же) после последнего
  // при создании (см. конструктор NodeBase) элементы next и prev
  // указывают на сам создаваемый элемент списка.
  // Такая "кольцевая" структура гарантирует, что элементы next и prev
  // всегда безопасны, так как отличны от 0.
  NodeBase *list = new NodeBase();
 
  // дальше все просто.
  int value; // это переменная для ввода значения с клавиатуры
  // в цикле
  do {
    // читается значение
    std::cin >> value;
    // если оно не ноль (или введено не число)
    if (value != 0) {
      // добавляется в конец списка
      insert(list, value);
    }
  // пока число не станет нулем (или не будет введено не число)
  } while (value != 0);
 
  // вывод списка на экран
  std::cout << "List:" << std::endl;
  printIntegerList(list);
 
 
  // очистка связного списка
  clear(list);
  delete list;
}
Ну и сортировка вставками, например.
Более эффективно мержем или квиксортом, но они гораздо сложнее в реализации.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void swap(int &a, int &b) {
  int c = a;
  a = b;
  b = c;
}
 
void sort(NodeBase *list) {
  if (list == 0 || isEmpty(list)) return;
  for (NodeBase *i = list->next; i != list->prev; i = i->next) {
    for (NodeBase *j = i->next; j != list; j = j->next) {
      if (static_cast<Node*>(i)->value > static_cast<Node*>(j)->value) {
        swap(static_cast<Node*>(i)->value, static_cast<Node*>(j)->value);
      }
    }
  }
}
Yandex
Объявления
21.07.2013, 11:28     Связанные списки (переделать программу)
Ответ Создать тему
Опции темы

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