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

@wolf1396 · Регистрация: 07.05.2013

Author24 — интернет-сервис помощи студентам

Как переделать программу, чтобы можно было вводить самому ключи и не было Access Violation?

Кликните здесь для просмотра всего текста

C++

#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;
}

помогите пожалуйста, мне срочно нужно сдать, а то на бюджетное не переведут

@lemegeton · 18.07.2013, 19:03

Что за задание? Какие ограничения на решение?

@wolf1396 · 18.07.2013, 19:16 **[ТС]**

Сообщение от lemegeton

Что за задание? Какие ограничения на решение?

нужно сделать так, чтобы с клавиатуры можно было ввести ключи и не было Access Violation

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

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

Кликните здесь для просмотра всего текста

C++

// 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 · 21.07.2013, 11:28

Я так понял, что вы застряли на заполнении связного списка. В процедурном стиле.

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

C++

#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++

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);
      }
    }
  }
}

@lemegeton 4857 / 2656 / 913 Регистрация: 29.11.2010 Сообщений: 5,731
	18.07.2013, 19:03	2
	Что за задание? Какие ограничения на решение? 0

	21.07.2013, 11:28