Базовые навыки работы со списками (пример на C++)

и снова я
теория по спискам: .....будет тут.........

а у меня есть код:

//библиотеки
#include "cstdio"
#define _USE_MATH_DEFINES
#include "cmath"
#include "string"
#include "conio.h"
#include "iostream"
#include "ctime"
using std::cout;
using std::cin;
using std::endl;
using namespace std;

struct point{              // элемент списка
	point * previous;
	int a;
	//char A [2];
	point * next;
};

void process (point Z){                                //заполнение списка
	cout << "введите цифру" << endl;
	cin >> Z.a;
	cout << endl << "следующий элемент" << endl;

	if(Z.next != NULL)
		 process (*Z.next);
	else 
		cout << "список кончился" << endl;
	    return;
}

void process2 (point Z){                                //изменение списка
	cout << "введите цифру" << endl;
	cin >> Z.a;
	cout << endl << "следующий элемент" << endl;

	if(Z.next != NULL)
		 process (*Z.next);
	else 
		cout << "список кончился" << endl;
	    return;
}

void vivod(point Z){
	cout << endl;
	cout << Z.a;
	vivod (*Z.next);
}

void main() {
setlocale(LC_ALL, "Russian");

	point A, B, C, D, E;  // собственно список
	point * head = &A;
	//A.previous = ?????????
	A.next = &B;

	B.previous = &A;
	B.next = &C;

	C.previous = &B;
	C.next = &D;

	D.previous = &C;
	D.next = &E;

	E.previous = &D;
	E.next = NULL;

	process (*head);
	vivod (*head);
	process2 (*head);
	vivod (*head);

	getch;
}

компилируется нормально.
однако после выполнения функции "void process" программа падает
не могу догнать, в чем косяк.
падение происходит на условии:

	if(Z.next != NULL)
		 process (*Z.next);
	else 
		cout << "список кончился" << endl;
	return;

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

со списками вообще так работают?
это вообще список?

point A, B, C, D, E;  // собственно список
	point * head = &A;
	//A.previous = ?????????
	A.next = &B;

	B.previous = &A;
	B.next = &C;

	C.previous = &B;
	C.next = &D;

	D.previous = &C;
	D.next = &E;

	E.previous = &D;
	E.next = NULL;

(тот тонкий момент, что ввод и вывод должны находиться в майне а не в функциях - мне известен и будет реализован)

vedro-compota's picture

поправьте код - чтобы были видны подключаемые библиотеки - для этого нужны пробелы между их названиями и угловыми скобками - иначе они гасятся фильтром как html тэги

_____________
матфак вгу и остальная классика =)

baton's picture

кстати, ошибка при ближайшем рассмотрении выглядит так:
http://cs407327.vk.me/v407327498/8627/DbzvfCvRgyY.jpg

vedro-compota's picture

это-то понятно, выход за выделенную память. ОС сама останавливает прогу.

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

if(Z.next != NULL)

а вы явно до этого присвоили NULL последнему элементу ( точнее соответств. его полю next) ?

_____________
матфак вгу и остальная классика =)

baton's picture

ну...... конец списка типа
не вижу прямой взаимосвязи этого присвоения с ошибкой

vedro-compota's picture

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

падение происходит на условии

а в какой именно строке? здесь =

if(Z.next != NULL)

Вообще тут есть два косяка:

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

Кстати- если падение происходит при первом же обращении к условию - то всё понятно - в связи со вторым пунктом - вы отдаёте значение в другую область памяти - и лишаетесь возможности обратиться к куче.

поэтому вам надо переписать сигнатуру функции так, чтобы она принимала указатель

_____________
матфак вгу и остальная классика =)

baton's picture

в функции

void vivod(point Z){

не написал условие выхода из рекурсии - затупил жестко, да. но да время позднее было, и я уставший... не суть.

со списками я разобрался - ничего сложного в этом нет, скоро предоставлю пару примеров кодов и подробные комментарии

baton's picture

код


#include <cstdio>
#define _USE_MATH_DEFINES
#include <cmath>
#include <string>
#include <conio.h>
#include <iostream>

//using std::cout;
//using std::cin;
//using std::endl;
using namespace std;

struct elem{ // тип данных элементов списка
	elem *previous;
	//int N;
	int a;
	elem *next;
};
typedef elem* pnt; // псевдоним
pnt head;

void init (elem *&p){  //ИНИЦИАЛИЗАЦИЯ ПУСТОГО СПИСКА // работает!
	p = NULL;
}

bool proverka(){ // ПРОВЕРКА НА ПУСТОТУ  // работает!      
	if( head == NULL)
		return false;
	else
		return true;
}

void add(pnt &p, int x){  //ДОБАВЛЕНИЕ НОВОГО ЭЛЕМЕНТА // работает!
//  добавляем элемент после данного 
// имеем адрес элемента, рядом с которым добавляем новый и значение - х  
//которое добавим в новый элемент
	if(head == NULL){
		p = new elem;
		p-> a = x;
		p->next = NULL;
		p->previous = head;
		head = p;
	}
	else{
		pnt r = new elem;
		r->a = x;
		r-> next = p->next;
		p->next = r;
		r->previous = p;
	}
}

int read(pnt p /*, int x*/){ // работает! 
// "считываем" значение элемента, возвращаем его в маин для дальнейших разбирательств
	if(p != NULL)
		return(p->a);
	else{
		return 0;
	}
}

bool criterion(pnt &Q, int x){ // ПРОВЕРКА
//проверяет, равно ли значение элемента заданному значению (х)
	if(read(Q) == x)
		return true;
	else
		return false;
}

void show_list(elem *list){ // ВЫВОД СПИСКА НА ЭКРАН // работает!
	cout << endl << "вывод списка" << endl; 
	while(list != NULL) {
		cout << read(list) << endl;
		list = list->next;
	}
	cout << endl << "show_list конец списка";
}

void deleter(elem **list, elem *p) { // УДАЛЕНИЕ ЭЛЕМЕНТА
	if (p == NULL)
		return;

	if (p->previous == NULL) { //удаление первого элемента
		*list = (*list)->next;
		delete p;
	}
	else if(p->next == NULL) { //удаление последнего элемента
		elem *temp = p;
		p->previous->next = NULL;
		delete temp;
	}
	else {   // удаление элемента из середины
		p->previous->next = p->next;
		p->next->previous = p->previous;
		delete p;
	}
} 

elem * find(elem *list, int x) { // ПОИСК И УДАЛЕНИЕ ПО КРИТЕРИЮ    
	elem *curr = list;
	while (curr != NULL) {
		if (curr->a == x)
			return curr;
		curr = curr -> next;
	}
}
void main(){
	setlocale(LC_ALL, "Russian");
	list A;

	A.init (A.head); // инициализация пустого списка
	cout << "введите количество элементов в списке" << endl;
	int j; // количество элементов в списке
	cin >> j;
	cout << endl << "заполните список" << endl;
	elem *Q;
	for(int i = 1; i <= j; i++){   
		// заполнение списка
		int y;
		cin >> y;
		A.add(Q, y);
		if(i > 1)
			Q = Q-> next;
	}

	A.show_list(A.head);
	int x;
	cout << endl << endl << "введите критерий удаления"<< endl;
	cin >> x;
	A.deleter(&A.head, A.find(A.head, x)); //?????????????????????
	
	A.show_list(A.head);
	
getch();
}

/* спиок есть последовательность элементов, связанных указателями на друг друга
при добавлении нового элемента необходимо связать его указателями на соседние эл.
при удалении элемента необходимо переназначить указатели элементов, указывающие на него.
если в структуре описан указатель, то обращение к нему черезх операцию "->",
а не через точку, как к простым элементам структуры */