Developing.ru

форум программистов
https://www.developing.ru/

Нужен исходник программы создания односвязного списка С++3.1

https://www.developing.ru/viewtopic.php?t=3276

Страница 1 из 1

Нужен исходник программы создания односвязного списка С++3.1

Добавлено: 25 июн 2005, 13:10
BAHO
Выложите, плз, исходник НОРМАЛЬНО (без всяких прибамбасов, например сортировки и т.п.) работающей программы на C++ 3.1 СОЗДАНИЯ динамической структуры - односвязного списка; ВВОДА и ВЫВОДА элементов в этот односвязный список. Хотя бы это.
И, если, кому не лень - ПОИСК в нём элемента с определённой размерностью.
Сроки поджимают.. Буду очень благодарен за быстрый ответ.
:( З.Ы. ...ещё не выкладывайте пожалуйста алгоритмы решения или функции отдельно - я имел ввиду цельную программу. Дело в том, что я не могу до конца разобраться со списками. :roll:

Добавлено: 27 июн 2005, 07:36
Lei fang
Это программа, организовывающая работу с односвязанным списком, дополнена функцией поиска максимального элемента.

Код: Выделить всё

#include<conio.h>
#include<stdio.h>
#include<dos.h>

struct list
{
	int data;
	list *next;
}; list *first=0, *cur=0;

int IsEmpty()
{
	return first==NULL;
}

void GoToPrev()
{
	if(IsEmpty())
	{
		printf("\nСписок пуст");
		getch();
	return;
	}
	if(cur==first)
	return;
	list *tmp;
	tmp=new list;
	tmp=first;
	while(tmp->next!=cur)
	tmp=tmp->next;
	cur=tmp;
}


void AddFirst(int val)
{
	list *tmp;
	tmp=new list;
	tmp->data=val;
	tmp->next=first;
	first=cur=tmp;
}

void AddAfterCur(int val)
{
	if(IsEmpty())
	{
		AddFirst(val);
		return;
	}
	list *tmp;
	tmp=new list;
	tmp->data=val;
	tmp->next=cur->next;
	cur->next=tmp;
	cur=tmp;
}

int IsEnd()
{
	return cur->next==NULL;
}

void Move()
{
	if(IsEnd())
	{
		printf("\nДостигнут конец списка");
		getch();
		return;
	}
	cur=cur->next;
}

void GoToFirst()
{
	cur=first;
}

int GetElem()
{
	return cur->data;
}

void DeleteFirst()
{
	list *tmp;
	tmp =new list;
	tmp=first->next;
	delete first;
	first=tmp;
}

void DeleteCur()
{
	if(IsEmpty())
	{
		printf("\nСписок пуст. Удаление невозможно");
		getch();
		return;
	}
	list *tmp;
	tmp=new list;
	if(cur==first)
	{
		DeleteFirst();
		return;
	}
	else
	{
		tmp=cur;
		GoToPrev();
		cur->next=tmp->next;
		delete tmp;
	}
}

void Print()
{
	if(IsEmpty())
	return;
	list *tmp;
	tmp=first;
	do
	{
		printf("%3i",tmp->data);
		tmp=tmp->next;
	}
	while(tmp!=NULL);
}

void MaxData(int q)
{
	if(first!=0)
	{
		cur=first;
		q=first->data;
		do
		{
			if(q<cur->data)
			{
				q=cur->data;
				cur=cur->next;
			}
			else
			{
				cur=cur->next;
			}
		}
		while(cur->next!=0);
		if(q<=cur->data)
		{
			printf("Максимальный элемент равен %i",cur->data);
		}
		else
		{
			printf("Максимальный элемент равен %i",q);
		}
	}
	else
	{
		printf("Список пуст");
	}
}

main()
{
	first=NULL;
	cur->next=NULL;
	cur=first;
	int q;
	char a;
	do
	{
		delay(1000);
		clrscr();
		int val;
		Print();
		printf("\nНажмите:\n\t0 - Возврат на предыдущий элемент;\n\t1 - добавление элемента в начало списка;\n\
	2 - добавление элемента после текущего;\n\t3 - просмотр элемента;\n\
	4 - удаление текущего элемента;\n\t5 - переход к следующему элементу:\n\
	6 - переход на начало списка;\n\t7 - проверка достижения конца списка;\n\
	8 - проверка пустоты спуска;\n\t9 - Найти максимальный элемент;\n\
	Esc - Выход\n");
		a=getch();
		switch (a)
		{
			case '1':
				printf("\nВведите значение:\n");
				scanf("%i",&val);
				AddFirst(val);
			break;
			case '2':
				printf("\nВведите значение:\n");
				scanf("%i",&val);
				AddAfterCur(val);
			break;
			case '3':
				if(IsEmpty())
					printf("\nСписок пуст");
				else
					printf("\nЗначение текущего элемента равно %i",GetElem());
				getch();
			break;
			case '4':
				DeleteCur();
			break;
			case '5':
				Move();
			break;
			case '6':
				GoToFirst();
			break;
			case '7':
				if(IsEnd())
					printf("\nДостигнут конец списка");
				else
					printf("\nКонец списка не достигнут");
				getch();
			break;
			case '8':
				if(IsEmpty())
					printf("\nСписок пуст");
				else
					printf("\nВ списке есть элементы");
				getch();
			break;
			case '9':
				MaxData(q);
			break;
			case '0':
				GoToPrev();
			break;
		}
	}
	while (a!=27);
        return 0;
}
Дело в том, что я не могу до конца разобраться со списками.

По своему опыту, скажу, лучше бы тебе почитать лекции (если ты их писал, конечно), книжки или какую-нибудь другую информацию по спискам. Одни исходники тебе не очень помогут.

Добавлено: 05 июл 2005, 08:57
Lei fang
Тут же нет ничего нового! Почему мне пришло уведомление об ответе???

Добавлено: 05 июл 2005, 17:20
Serg79
Когда то приходилось делать что то подобное. Должно быть вроде этого, потправиш немного и будет самый раз:

Код: Выделить всё

/***********************************************************************

	Шаблонный класс стека.
	Создает динамический стек в памяти.

	Пример:
	struct add {
		char name[20];
		int i;
		add *next;
	};

	stack<add> a;  // Создается стек для структур add.
	stack<int> b;  // Создается стек для целых чисел.

	*********************************************************************
	Прототипы Функции:

	bool push(объект)  - помешает элимент в стек, возвращает true, если
						 элемент помешенн, и false - в противном случае.
	объект pop()       - выталкивает элемент из стека, возврашает элимент
						 стека. Элемент удаляется.
	bool empty()       - возврашает true, если стек пуст, и false -
						 в противном случае.
	size_stack size()  - возврашает текущее количество элементов,
						 находящихся в стеке.
	*********************************************************************

	В классе перегружены операторы: = и ==,!=,<,>,<=,>=.
	Операторы сравнения сравнивают длину стека.

	Функция push() помешает объект в стек. Она возврашает false если
	произошла ошивка при помешении объекта в стек.

	Если стек пуст функция pop() возвращает 0 (нуль). Но так как 0 (нуль)
	будет возврашен так же если он там находится, пример:

			stack<int> a;
    		a.push(12);       // заталкиваем 12
			a.push(0);        // заталкиваем 0
    		cout << a.pop();  // выталкиваем 0
			cout << a.pop();  // выталкиваем 12

	по этому для проверки, пуст ли стек или нет нужно использовать
	функцию empty(), она возврашает true если стек пуст.
	Пример:

			stack<int> a;
			bool b;
			int i;

			a.push(12);
			cout << "В стеке " << a.size() << " элементов.\n";
					       // В стеке 1 элементов.
			i = a.pop();   // i = 12
			cout << "В стеке " << a.size() << " элементов.\n";
					       // В стеке 0 элементов.
			i = a.pop();   // i = 0
			i = a.empty(); // i = 1
			b = a.empty(); // b = true
			i = a.pop();   // i = 0
			
************************************************************************/

/************************************************************************
	Шаблонный класс очереди.
	Создает динамическую очередь в памяти.

	Работа с очередью происходит точно так же, как и со стеком.
	Только принцип стека "Первым вошол, последним вышел", а
	очереди "Первым вошол, первым вышел".

	Пример:
			queue<int> a;
			boll b;
			int i;

			a.push(25);
			a.push(12);

            b = a.empty();	// b = false
			i = a.pop();	// i = 25
			i = a.size();	// i = 1
			i = a.pop();	// i = 12
			i = a.pop();	// i = 0
			i = a.empty();	// i = 1
			b = a.empty();	// b = true
			i = a.pop();	// i = 0
			
************************************************************************/

#include <cstdlib>
#include <new>
using std::bad_alloc;

typedef unsigned int size_stack;

template <class T=int> class stack
{
	struct Type {
		T stck;
		Type *prior;
	};
	Type *tos;
	size_stack size_stck;

public:
	stack();
	stack(const stack<T> &a);
	~stack();
	bool push(const T &i);
	T pop();
	size_stack size() { return size_stck; }
	bool empty() { return (size_stck ? false : true); }
	stack<T> operator=(const stack<T> &a);
	int operator==(const stack<T> &a) { return (size_stck==a.size_stck ? 1 : 0); }
	int operator!=(const stack<T> &a) { return (size_stck!=a.size_stck ? 1 : 0); }
	int operator<(const stack<T> &a) { return (size_stck<a.size_stck ? 1 : 0); }
	int operator>(const stack<T> &a) { return (size_stck>a.size_stck ? 1 : 0); }
	int operator<=(const stack<T> &a) { return (size_stck<=a.size_stck ? 1 : 0); }
	int operator>=(const stack<T> &a) { return (size_stck>=a.size_stck ? 1 : 0); }
};

template <class T> stack<T>::stack()
{
	try {
		tos = new Type;
	} catch (bad_alloc xa) {
		exit(1);
	}

	tos->prior = NULL;
	size_stck = 0;
}

template <class T> stack<T>::stack(const stack<T> &a)
{
	register Type *tmp1, *tmp_a;

	try {
		tos = tmp1 = new Type;
	} catch (bad_alloc xa) {
		exit(1);
	}

	tmp_a = a.tos;

	while(tmp_a->prior) {
		register Type *tmp2;

		tmp_a = tmp_a->prior;

		try {
			tmp2 = new Type;
		} catch (bad_alloc xa) {
			exit(1);
		}

		tmp1->prior = tmp2;
		tmp2->stck = tmp_a->stck;
		tmp1 = tmp2;
	}
    
    tmp1->prior = NULL;
    size_stck = a.size_stck;
}

template <class T> stack<T>::~stack()
{
	register Type *temp;

	do {
		temp = tos->prior;
		delete tos;
		tos = temp;
	} while(temp);
}

template <class T> stack<T> stack<T>::operator=(const stack<T> &a)
{
	register Type *tmp1, *tmp_a;

	do {
		tmp1 = tos->prior;
		delete tos;
		tos = tmp1;
	} while(tmp1);

	try {
		tos = tmp1 = new Type;
	} catch (bad_alloc xa) {
		exit(1);
	}

	tmp_a = a.tos;

	while(tmp_a->prior) {
		register Type *tmp2;

		tmp_a = tmp_a->prior;

		try {
			tmp2 = new Type;
		} catch (bad_alloc xa) {
			exit(1);
		}

		tmp1->prior = tmp2;
		tmp2->stck = tmp_a->stck;
		tmp1 = tmp2;
	}
    
    tmp1->prior = NULL;
    size_stck = a.size_stck;

    return *this;
}

template <class T> bool stack<T>::push(const T &i)
{
	register Type *temp;
    
    try {
		temp = new Type;
	} catch (bad_alloc xa) {
		return false;
	}

	tos->stck = i;
	temp->prior = tos;
	tos = temp;
	size_stck++;

	return true;
}

template <class T> T stack<T>::pop()
{
	register Type *temp;

	if(!tos->prior)  return 0;
	
	temp = tos->prior;
	delete tos;
	tos = temp;
	size_stck--;
	
	return tos->stck;
}

/**********************************************************************/

typedef unsigned int size_queue;

template <class T=int> class queue
{
	struct Type {
		T que;
		Type *next;
	};
	Type *first;
	Type *last;
	size_queue size_que;

public:
	queue();
	queue(const queue<T> &a);
	~queue();
	bool push(const T &i);
	T pop();
	size_queue size() { return size_que; }
	bool empty() { return (size_que ? false : true); }
	queue<T> operator=(const queue<T> &a);
	int operator==(const queue<T> &a) { return (size_que==a.size_que ? 1 : 0); }
	int operator!=(const queue<T> &a) { return (size_que!=a.size_que ? 1 : 0); }
	int operator<(const queue<T> &a) { return (size_que<a.size_que ? 1 : 0); }
	int operator>(const queue<T> &a) { return (size_que>a.size_que ? 1 : 0); }
	int operator<=(const queue<T> &a) { return (size_que<=a.size_que ? 1 : 0); }
	int operator>=(const queue<T> &a) { return (size_que>=a.size_que ? 1 : 0); }
};

template <class T> queue<T>::queue()
{
	try {
		first = last = new Type;
	} catch (bad_alloc xa) {
		exit(1);
	}

	last->next = NULL;
	size_que = 0;
}

template <class T> queue<T>::queue(const queue<T> &a)
{
	register Type *temp_a;

	try {
		first = last = new Type;
	} catch (bad_alloc xa) {
		exit(1);
	}

	temp_a = a.first;

	while(temp_a->next) {
		register Type *temp;

		try {
			temp = new Type;
		} catch (bad_alloc xa) {
			exit(1);
		}

		last->next = temp;
		last->que = temp_a->que;
		temp_a = temp_a->next;
		last = temp;
	}
    
    last->next = NULL;
    size_que = a.size_que;
}

template <class T> queue<T>::~queue()
{
	register Type *temp;

	do {
		temp = first->next;
		delete first;
		first = temp;
	} while(temp);
}

template <class T> queue<T> queue<T>::operator=(const queue<T> &a)
{
	register Type *temp_a;

	do {
		temp_a = first->next;
		delete first;
		first = temp_a;
	} while(temp_a);

	try {
		first = last = new Type;
	} catch (bad_alloc xa) {
		exit(1);
	}

	temp_a = a.first;

	while(temp_a->next) {
		register Type *temp;

		try {
			temp = new Type;
		} catch (bad_alloc xa) {
			exit(1);
		}

		last->next = temp;
		last->que = temp_a->que;
		temp_a = temp_a->next;
		last = temp;
	}
    
    last->next = NULL;
    size_que = a.size_que;

    return *this;
}

template <class T> bool queue<T>::push(const T &i)
{
	register Type *temp;

	try {
		temp = new Type;
	} catch (bad_alloc xa) {
		return false;
	}

	last->que = i;
	last->next = temp;
	temp->next = NULL;
	last = temp;
	size_que++;

	return true;
}

template <class T> T queue<T>::pop()
{
	Type temp;

	if(!first->next) return 0;

	temp = *first;
	delete first;
	first = temp.next;
	size_que--;

	return temp.que;
}
Тип данных с которыми работают эти два класса могут быть любыми, от встроенного типа до типа определенного пользователем (структуры, объекты и т.п.).
Часовой пояс: UTC+03:00
Страница 1 из 1

Создано на основе phpBB® Forum Software © phpBB Limited

Русская поддержка phpBB