Algorytmy i Struktury Danych - Implementacja listy w C++

listy.cpp

#include <iostream>
using namespace std;

struct node {
	int val;
	node * next = NULL;
};

struct list {
	node * head = NULL;
	int size = 0;
};

void add_node_head(list * & l1, node * & element) {
	if (l1->head == NULL) {
		l1->head = element;
	}
	else {
		element->next = l1->head;
		l1->head = element;
	}
	l1->size++;
}

int return_val(list * & list, int pos) {  //pos - position; Head = 1

	if (list->head != NULL) {

		node * tmp = list->head;

		for (int i = 1; i < list->size; i++) {
			if (i == pos) {
				return tmp->val;
			}
			else {
				if (tmp->next != NULL) {
					tmp = tmp->next;
				}
				else return false;
			}
		}
		return tmp->val;
	}
	else return false;
}

void add_val_list(list *& list, int nval) {
	node * tmp = new node;
	tmp->val = nval;

	if (list->head == NULL) {
		list->head = tmp;
	}
	else {
		tmp->next = list->head;
		list->head = tmp;
	}
	list->size++;
}
void show_list(list *list) {
	node * tmp = list->head;
	while (tmp) {
		cout << tmp->val << " -> ";
		tmp = tmp->next;
	}
	cout << "NULL";
}

void show_list2(list * list) {
	node * tmp = list->head;
	for (int i = 1; i <= list->size; i++) {
		cout << return_val(list, i) << " -> ";
	}
	cout << "NULL";
}

bool is_Empty(list * list) {						//funkcja zwraca prawde jak jest pusta. tak dla picu funkcja zeby nie pisac pare razy pozniej
	if (list->head) return false;
	return true;
}

bool add_2_list(list * & l1, list * l2) {
	if (l1->size != l2->size)return false;	//spr czy sa tego samego rozmiaru. Jak nie to nara. #lenistwo

	node * tmp1 = l1->head;
	node * tmp2 = l2->head;
	if (is_Empty(l1)) return false;				//wczesniej sprawdzone czy tego samego rozmiaru wiec styknie sprawdzic tylko 1 #optymalizacja
	for (int i = 1; i <= l1->size; i++) {

		tmp1->val += tmp2->val;
		tmp1 = tmp1->next;
		tmp2 = tmp2->next;
	}

	return true;
}


bool del_head(list * & list) {
	if (!is_Empty(list)) {
		node * tmp = list->head;
		tmp = tmp->next;
		list->head = tmp->next;
		list->size--;
		return true;
	}
	return false;
}


bool del_last(list * & list) {
	if (!is_Empty(list)) {
		node *tmp = list->head;
		node *tmp2 = list->head;
		while (tmp->next != NULL) {
			tmp2 = tmp;
			tmp = tmp->next;

		}

		tmp2->next = NULL;

		list->size--;
		return true;
	}
	return false;
}


bool copy_list(list * & newlist, list * & oldlist) {  //kopiuje stara liste na koniec nowej. jak pusta to od poczatku poprostu
													  // newlist: 1 -> 2 -> 4 -> NULL  oldlist: 5 -> 6 -> 7  ===>>  newlist: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL
	node * tmp = newlist->head;
	node * tmp2 = oldlist->head;
	node * nnode = new node;
	if (!is_Empty(newlist) && !is_Empty(oldlist)) {
		while (tmp->next != NULL) {
			tmp = tmp->next;
		}

		for (int i = 1; i <= oldlist->size; i++) {
			node * nnode = new node;
			tmp->next = nnode;
			nnode->val = tmp2->val;
			tmp = nnode;
			tmp2 = tmp2->next;
			newlist->size++;
		}
		return true;
	}
	else {
		if (!is_Empty(oldlist)) {
			newlist->head = nnode;
			nnode->val = tmp2->val;
			tmp2 = tmp2->next;
			tmp = nnode;
			newlist->size++;

			for (int i = 2; i <= oldlist->size; i++) {
				node * nnode = new node;
				tmp->next = nnode;
				nnode->val = tmp2->val;
				tmp = nnode;
				tmp2 = tmp2->next;
				newlist->size++;
			}
			return true;

		}
		return true;
	}



	return 0;
}
// 1 - 2- 3- 4- 5- 6- 7- 8 -> NULL
void zamienheadzdrugirm(list * & list) {
	if (list->size > 1) {
		node * first = list->head;
		node * tmp = first->next;
		first->next = tmp->next;
		tmp->next = first;

		list->head = tmp;		// 2 -1 -3 -4 - 5 -6 - 7 -8 -> NULL

	}
}

/*nietestowane i chyba nie działa ale chuj wi ide spać
// 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
//			tmp2 tmp tmp3
void swap(list * & list , int n1){ //1 to head
if (list->size > n1+1 && list ->size > 2){
node * tmp = list->head;
tmp = tmp->next;
node * tmp2 = list ->head;
for (int i = 1; i < n1; i++){
tmp = tmp->next;
tmp2 = tmp2->next;
}
tmp2 ->next = tmp->next;
node * tmp3 = tmp->next;
tmp3 = tmp3->next;
tmp->next = tmp3;

}
}
*/




void add_node(list * & l1, node * & element) {
	if (l1->head == NULL) {
		l1->head = element;
	}
	else {
		node * tmp = l1->head;
		for (int i = 1; i < l1->size; i++) {
			tmp = tmp->next;
		
		}
		tmp->next = element;

	}
	l1->size++;
}





/*SZTUCZNE FUNKCJE DO ZADAŃ*/


void copy3(list *& list0){
	if (is_Empty(list0))exit (0);
	list * list3 = new list;
	list * list2 = new list;

	copy_list(list3, list0);

	node * tmp = list0->head;
	for(int i =1; i < list0->size;i++){
		add_node(list2, tmp);
		tmp = tmp->next;
	}
	show_list(list2);
	//copy_list(list0, list2);
	//copy_list(list0, list3);
}



void sredniaend(list *& list1) {
	node* tmp = list1->head;
	int total = tmp->val;
	for (int i = 1; i < list1->size; i++) {
		tmp = tmp->next;
		total += tmp->val;
	}
	total = total / list1->size;
	cout << total;
	list * list3 = new list;
	tmp = list1->head;
	node * tmp2 = tmp->next;
	for (int i = 2; i < list1->size; i++) {
		if (tmp2->val > total) {
			tmp->next = tmp2->next;
			list1->size--;
		}
		tmp = tmp->next;
		tmp2 = tmp2->next;
	}

	if (list1->head->val > total) {
		del_head(list1);
	}
}

int main() {

	list * list1 = new list;	//tworzenie nowej pustej listy (domyslnie size =0 i head = NULL)
	list * list2 = new list;
	list * list3 = new list;
	node * nowy = new node;		//tworzenie nowego node
	nowy->val = 2;				//nadanie stworzonemu node wartosci 2 (next ma domyslnie NULL)


	add_val_list(list1, 1);		//dodaje do poczatku listy node z wartoscia 1.
	add_node_head(list1, nowy);	//dodaje do poczatku listy podanego node
	add_val_list(list1, 3);		//dodaje do poczatku listy node z wartoscia 3.
	add_val_list(list1, 4);		//dodaje do poczatku listy node z wartoscia 4.
	add_val_list(list1, 5);		//dodaje do poczatku listy node z wartoscia 5.
	cout << endl;
	show_list(list1); 			//Wyswietla cala liste. Wyswietla az wskaznik != NULL
								//	cout << return_val(list1,1);
								//	cout << " " << return_val(list1, 6);
								//	add_val_list(list1, 6);		
								//	cout << endl;
								//	show_list2(list1);			//Wyswietla cala liste. Wyswietla az i <= size

	add_val_list(list2, 9);		//tworze druga liste
	add_val_list(list2, 8);
	add_val_list(list2, 7);
	add_val_list(list2, 6);
	add_val_list(list2, 5);
	cout << endl;
	show_list2(list2);
	cout << "tutaj:";
	add_node(list2, nowy);
	show_list2(list2);



	cout << endl;
	cout << "lista przed zamiana: ";
	show_list2(list1);
	zamienheadzdrugirm(list1);	//zamienia head z drugim elementem


	cout << endl << "lista po zamianie: ";
	show_list2(list1);

	add_2_list(list1, list2);	//dodaje do pierwszej listy druga
	cout << endl;
	show_list2(list1);


	//	if (is_Empty(list2))cout << "pusta";		//testowanie funkcji is_Empty
	//	if (!is_Empty(list2))cout << "Nie pusta"; 



	add_val_list(list3, 1);
	add_val_list(list3, 2);
	add_val_list(list3, 3);
	add_val_list(list3, 4);
	add_val_list(list3, 5);
	cout << endl;
	show_list2(list3);
	del_head(list3);
	cout << endl;
	show_list2(list3);
	del_last(list3);
	cout << endl;
	show_list2(list3);
	cout << endl;
	list * list4 = new list;
	cout << "lista zawiera: ";
	show_list2(list1);
	cout << endl;
	copy_list(list4, list1);
	copy_list(list4, list1);
	show_list(list4);


	cout << endl;
	cout << endl;	cout << endl;	cout << endl;	cout << endl;	cout << endl;	cout << endl;	cout << endl;
	show_list2(list3); cout << endl;
	//copy3(list3);
	show_list2(list3);
	cout << endl;	cout << endl;	cout << endl;	cout << endl;	cout << endl;	cout << endl;	cout << endl;
	show_list(list1);
	cout << endl;
	cout << "srednia to: ";
	sredniaend(list1);
	cout << endl;
	show_list(list1);

	system("pause");
}