VPF::Сортировка в линейном списке - Форум программистов

dark0ut

Дата 29.5.2004, 01:29 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 19
Регистрация: 20.2.2003

Репутация: нет
Всего: нет

У меня есть прога, где мне нужно отсортировать по возрастанию элементы списка. Причем, сортировать нужно не в массиве с последующим составлением списка, а сразу. Т.е. вводишь элемент и проверяешь - если он меньше, то ставишь впереди текущего, если больше, то позади. Моя прога не пашет.

Посмотрите, в чем там дело.

Код



#include "stdafx.h"
#include "iostream.h"

struct Clist
{
	int a;
	Clist *next;
};

Clist *first;
Clist *p, *q, *w;
int n,b,c;


void AddElem (int b)
{
	if (first = NULL)
	{
  first = new Clist;
  first->a = b;
  first->next = NULL;
	}
	else
	{
  //Clist *p, *q, *w;
  p = first;
  q = first->next;

  while (p!=NULL && q!=NULL)
  {
  	if (p->a<b && q->a>b)
  	{
    w = new Clist;
    w->a = b;
    w->next = q;
    p->next = w;
    return;
  	}
  	p = p->next;
  	q = p->next;
  }
  w = new Clist;
  w->a = b;
  w->next = NULL;
  p = w;
	}
}

void Input (int n)
{
	cout <<"\nVvedite kol-vo elementov";
	cin >> n;
	//int c;
	for (int t=0; t<n; t++)
	{
  cin >> c;
  AddElem(b);
	}
}

void Output()
{
	Clist *p;
	p = first;
	while (p)
	{
  cout << p->a << ' ';
  p = p->next;
	}
	cout << endl;
}

int main()
{
	//int n;
	Input(n);
	Output();
	return 0;
}

[s]

AndyY

Дата 29.5.2004, 10:28 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 316
Регистрация: 8.5.2004
Где: СПб

Репутация: 2
Всего: 4

для таких задач я сделал смешанный класс, по сути являющийся самобалансирующимся бинарным деревом, но имеющий интерфейс списка.
см. на моем сайте - awin.zip, misc_map.h, _list_map_t.

для простоты (или если данные на входе достаточно случайны) балансировку можно убрать - тогда получится банальное бинарное дерево.

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

--------------------

Андрей Ямов, проект Альтернативное программирование и форум AWIN

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »