С++, Список, односвязный список (?!)

[Abstraction]

Abstraction, рассказываю мою задумку, а вы мне скажите, пожалуйста, через что её лучше реализовывать.

Обратите внимание: Вам может понадобиться делать серию предположений "пусть в этой клетке 5 И в этой 7 И в этой 3...". Их все надо запоминать, именно вот такой цепочкой, по которой в любой момент можно сделать шаг назад. По сути, возникает структура, называемая деревом - она отличается от списка тем, что у одного узла может быть несколько "потомков".

Но, понимаете ли, возникает какая проблема - когда мы найдём нужную нам пустую ячейку, запишем туда цифру - из всех "правильных" (линии и круг на 9 клеток) пространств надо убрать эту цифру.

Вторая проблема: если мы не угадаем с ячейкой, нам нужно "стереть" цифру... и "добавить" её не в 20 других клеток, а только в те, из которых мы её убрали. Засада.

Как вариант, если брать Вашу идею за основу: сделать (двумерный) массив из 81 списка (обзовём его тип Board). А дальше как-то так:

bool TrySolution(Board b){
  int variants = 10;
  Cell cell; //Cell - структура данных "List, int, int" - клетка плюс координаты
  //Ищем "неопределённую" клетку с наименьшим числом возможных вариантов
  for(int i=0; i<9; ++i){
    for(int j=0; j<9; ++j){
      int length = List_getLength(&b[i][j]);
      if(length>1 && length<variants) Cell_init(b[i][j], i, j, &cell);
    }
  }
  //Если такой нет - ура, мы решили судоку!
  if(variants == 10) return true;
  //Иначе заводим два новых списка. Зачем? Увидим ниже.
  List decision;
  List_init(&decision);
  ListOfCells modified; //ListOfCells - список, только элементы не int, а Cell

  //Ставим вместо списка в выбранной ячейке decision
  b[Cell_getX(&cell)][Cell_getY(&cell)] = decision;
  //Теперь перебираем варианты...
  for(ListNode* cur=Cell_getList(&cell); cur!=NULL; cur=cur->next){
    decision->data = cur->data; //Пишем вариант на доску
    for(/*здесь обход всех клеток, из которых надо убрать цифру*/){
      //Если в списке такая цифра есть,
      if(List_contains(decision->data, &b[i][j])){
        //Запомнаем, что мы поправили список
        ListOfCells_add(b[i][j], i, j, &modified);
        //Правим
        List_remove(decision->data, &b[i][j]));
        //Если список остался пустым - мы зашли не туда
        if(List_empty(&b[i][j]))
          goto L_NextDecision; //Да-да, это goto
      }
    }//закончили обход клеток, из которых надо убрать цифру
    //А теперь пытаемся решить получившееся судоку:
    if(TrySolution(b)) return true;
 L_NextDecision: //метка перехода 
    //Отменяем внесённые изменения
    CancelByList(b, modified, decision->data);
  }
  //Если все попытки обломались - мы в тупике, возвращаемся на шаг назад:
  b[Cell_getX(&cell)][Cell_getY(&cell)] = Cell_getList(&cell);
  return false;
}

//В клетки из списка добавляется значение
void CancelByList(ListOfCells modified, int value){
  for(ListOfCellsNode* cur = modified, cur!=NULL; cur=cur->next){
    List toRestore = Cell_getList(&cur->data);
    List_add(value, &toRestore);
  }
}

[Fanyuus]

Abstraction, спасибо вам большое! Ваш код ещё не разбирала, но когда будет время, я вернусь к вопросу про "решение судоку" и изучу ваш код

Помогите, пожалуйста, ещё раз со списками:

Сначала я пишу это:

struct Lll
{
  Lll *next; //Указатель на след.элемент
  int ch; //Данные списка
};

Затем я пишу в main'е:

void main()
{
	setlocale(0,"");
	
	Lll St; //создаём список
	Lll *head; //указатель на голову списка
	Lll *end;  //указатель на конец списка

	cin.get();
	cin.get();
}

Так, с этим поняла.
Дальше.
А дальше мне нужно добавить элемент к списку.

#include "stdafx.h"
#include <iostream>

using namespace std;

struct Lll
{
  Lll *next; //Указатель на след.элемент
  int ch; //Данные списка
};

void Lll_add(int a, Lll *end)
{
  Lll *Addelem = new Lll; //выделить память
  Addelem->ch = a; // присваиваем значение, ввод данных
  Addelem->next = end; //добавить к списку
  end = Addelem; //не совсем понимаю, что мы делаем в этой строчке?
}

void main()
{
	setlocale(0,"");
	int a;
	Lll St; //создаём список
	Lll *head=NULL; //указатель на голову списка
	Lll *end=NULL;  //указатель на конец списка
	cin >> a; //ввели число, которое надо добавить
	Lll_add(a,end);
	
	

	cin.get();
	cin.get();
}

Вопросы:
1) В void Lll_add(int a, Lll *end)
end = Addelem; //не совсем понимаю, что мы делаем в этой строчке?

?

2) Правильно ли я делаю? (анализирую и беру с 3 кодов, делаю что-то одно, пытаюсь в этом разобраться)

3) А как вывести значения полученного списка?

[Abstraction]

Затем я пишу в main'е:

void main()
{
	setlocale(0,"");
	
	Lll St; //создаём список
	Lll *head; //указатель на голову списка
	Lll *end;  //указатель на конец списка

	cin.get();
	cin.get();
}

Так, с этим поняла.

Не поняли. Lll - это тип "элемента", "узла" списка - но не самого списка. Простая проверка: пустой список существует, но не содержит ни одного узла.

Далее. Вы объявили три переменные, и утверждаете, что они вместе описывают один и тот же список. Если это так (т.е. если Ваш "список" - это тройка переменных), то создайте отдельную структуру. Вообще-то, отдельный указатель на конец списка - неплохая идея, но её надо суметь реализовать.
Пока я бы советовал использовать вариант "список - это указатель на Lll, который или равен NULL (это означает, что список пуст), или указывает на первый узел списка".

Возвращаясь к посту с примером:
Во все функции, меняющие список, передаётся указатель на этот список. Так, только так и никак иначе (вспомните, чем отличается "передача по значению" и "передача по указателю/ссылке"). Если сам список - "указатель на узел", то передавать надо "указатель на указатель на узел".

  Addelem->next = *list; //добавить к списку
  *list = Addelem; //не совсем понимаю, что мы делаем в этой строчке?

Неправильно поняли. Первое действие - это Addelem->next начинает указывать туда же, куда и *list. После этого *list (указатель на первый элемент списка либо NULL) указывает на первый элемент списка и Addelem->next указывает на первый элемент списка, получается эдакий "двухголовый" список. А вот вторая инструкция меняет *list, и после неё имеем:

Было:
*list => [первый элемент списка/NULL]
Стало после первой строки:
*list => [первый элемент списка/NULL]
Addelement => [первый элемент списка/NULL]
После второй строки:
*list => Addelement => [первый элемент списка/NULL]

[Fanyuus]

Во все функции, меняющие список, передаётся указатель на этот список.

Да, это я видела и поняла,

{
List l1;
  List_init(&l1);
}

void List_init(List* thiz){
  *thiz = NULL; //Передаём указатель на List - нам же его менять 
}

но я не поняла, как из Lll взять указатель?
И я подумала, что надо сделать "голова" и "конец", добавить элемент, и менять "конец".

Допустим, мне нужно сначала сделать пустой список. Значит, мне нужно взять "ссылку" на St, верно? (если да, то сразу вопрос - как эту ссылку взять и передать в head? Или куда её нужно передать\объявить?)

[uri2808]

Поскольку вопрос был всегда ли списки создаются через классы: можно список реализовать и при помощи массивов. О реализации циклического однонаправленного списка при помощи двух массивов и об операциях с ним - здесь: http://function-x.ru/cpp_list1.html