#include <cstdio>
#include <cassert>
using namespace std;
typedef int T;
const int MAX=1000;
const int NONE=-1;
struct Item{
int prev;
int next;
T value;
Item(int a_prev, int a_next, T a_value){
prev=a_prev;
next=a_next;
value=a_value;
}
Item(T a_value){
prev=NONE;
next=NONE;
value=a_value;
}
Item(){
prev=NONE;
next=NONE;
value=0;
}
};
class List_Iterator{
Item** items;
int* first;
int* last;
int cur;
public:
List_Iterator(Item** a_items, int* a_first, int* a_last){
items = a_items;
first = a_first;
last = a_last;
cur = *a_first;
}
void begin(){
cur=*first;
}
void end(){
cur=*last;
}
bool next(){
if(cur!=NONE){
if(items[cur]->next == NONE)
return false;
else
cur=items[cur]->next;
}
return (cur!=NONE);
}
bool prev(){
if(cur!=NONE)
if(items[cur]->prev == NONE)
return false;
else
cur=items[cur]->prev;
return (cur!=NONE);
}
T get(){
if(cur!=NONE)
return items[cur]->value;
return 0;
}
};
class List{
Item* items[MAX];
int first; //индекс начального элемента
int last; //индекс конечного элемента
int num; //общее число элементов
//ищем следующее свободное место в массиве
int get_free_index(){
int i=0;
for(i=0;i<MAX;i++){
if( items[i]->prev==NONE && items[i]->next==NONE ){
return i+(num==1);
}
}
return NONE;
}
//вставляем значение перед выбранным элементом массива
void insert_before(int i, T a_value){
if(isEmpty()){
add(a_value);
return;
}
int free_index=get_free_index();
items[free_index] = new Item(a_value);
items[free_index]->next = i;
items[free_index]->prev = items[i]->prev;
if(i!=first){
items[items[i]->prev]->next=free_index;
}
items[i]->prev = free_index;
if(i == first)
first=free_index;
num++;
}
//ищем и возвращаем индекс элемента в массиве, чье значение равно аргументу
int findItem(T value){
if(isEmpty()) return NONE;
//будем возвращать первый найденный индекс
int i = first;
while(items[i]->next != NONE && items[i]->value != value){
i=items[i]->next;
}
if(items[i]->value == value)
return i;
return NONE;
}
//получить индекс на элемент по номеру его в списке
int getItem(unsigned int index){
if(isEmpty()) return NONE;
if(index==0) return first;
if(index==(num-1)) return last;
if(index>=num) return NONE;
int i;
//определяем с какого конца легче двигатся
if(index>=num/2){
i=last;
index=num-index-1;
while(index){
i=items[i]->prev;
index--;
}
}
else{
i=first;
while(index){
i=items[i]->next;
index--;
}
}
return i;
}
//удаляем элемент по его номеру в массиве
void removeItem(int i){
if(isEmpty()) return;
if(items[i]->prev != NONE)
items[items[i]->prev]->next=items[i]->next;
if(items[i]->next != NONE)
items[items[i]->next]->prev=items[i]->prev;
num--;
if(i == first){
first=items[i]->next;
}
if(i == last){
last=items[i]->prev;
}
items[i]->prev=NONE;
items[i]->next=NONE;
if(!num){
first=0;
last=0;
}
}
public:
List (){
clear();
}
~List (){
clear();
}
// добавить в конец
void add(T value){
int free_index=get_free_index();
items[free_index] = new Item(value);
if(!num){
first = free_index;
last = free_index;
}
else{
items[free_index]->prev = last;
items[last] ->next = free_index;
last = free_index;
}
num++;
}
// добавить элемент в позицию с указанным индексом
void insert(unsigned int index, T a_value){
//будем добавлять перед этим эл-том
//cначало досчитаем до этого элемента
if(!index)
return insert_before(first, a_value);
//если индекс превышает число эл-тов то добавляем в конец
if(index>num)
return add(a_value);
int i;
//определяем с какого конца легче двигатся
if(index>=num/2){
i=last;
index=num-index-1;
while(index){
i=items[i]->prev;
index--;
}
}
else{
i=first;
while(index){
i=items[i]->next;
index--;
}
}
return insert_before(i,a_value);
}
// установить значение по индексу
void set(int index, T value){
int i = getItem(index);
items[i]->value=value;
};
// получить значение по индексу
T get(int index){
int i=getItem(index);
if(i!=NONE)
return items[i]->value;
return NONE;
}
// очистить список
void clear (){
num=0;
first=0;
last=0;
for(int i=0;i<MAX;i++){
items[i]=new Item;
}
}
// получить количество
int count(){
return num;
}
// пустой ли список
bool isEmpty(){
return !num;
}
// получить индекс указаного элемента. Если: элемента нет, вернуть -1
int indexOf(T value){
if(isEmpty()) return NONE;
//будем возвращать первый найденный индекс
int i=first;
int j=0;
while(items[i]->next != NONE && items[i]->value != value){
i=items[i]->next;
j++;
}
if(items[i]->value == value)
return j;
return NONE;
}
// проверить, принадлежит ли элемент списку
bool contains(T value){
return (bool)(indexOf(value)+1);
}
// удалить все вхождения элемента из списка
void remove(T value){
if(isEmpty()) return;
while(true){
int i=findItem(value);
if(i==NONE)
break;
removeItem(i);
}
}
// удалить элемент с заданным индексом
void removeAt(int index){
if(isEmpty()) return;
int i=getItem(index);
if(i!=NONE)
removeItem(i);
}
void print(){
int i=first,j=0;
printf("\n\n Count elements: %i \n", num);
//printf(" First index: %i \n",first);
//printf(" Last index: %i \n",last);
printf("--------------------------------------------------------------------------------");
printf(" index | prev | next | value | arr_key \n");
for(int j=0;j<num;j++){
printf(" %4i | %3i | %3i | %9i | %3i \n",j,items[i]->prev,items[i]->next, items[i]->value, i);
i=items[i]->next;
}
printf("--------------------------------------------------------------------------------\n");
}
// скопировать список в массив (предполагается, что массив содержит достаточное количество элементов для выполнения операции)
void copyTo(T* arr){
int i=first;
for(int j=0;j<num;j++){
arr[j] = items[i]->value;
i = items[i]->next;
}
}
// получить итератор для обхода спискa
List_Iterator* getIterator(){
return new List_Iterator(items,&first,&last);
}
};
void task(){
}
void test(){
List* list = new List();
/*тестирование на пустоту*/
assert(list->isEmpty() ) ;
assert(list->count() == 0);
/*тестирование на дополнение в конец, изменение числа элементов, наличие элементов */
for(int i=0;i<10;i++){
list->add(i);
assert(!list->isEmpty());
assert(list->get(i)==i);
assert(list->count() == i+1);
assert(list->contains(i));
assert(list->indexOf(i)==i);
assert(!list->contains(i+1));
assert(list->indexOf(i+1)==NONE);
}
/*Тестирование удаления по значению*/
for(int i=0;i<10;i+=2){
list->remove(i);
assert(list->count() == 10-i/2-1);
assert(!list->contains(i));
}
/*Тестирование удаления по номеру элемента в списке*/
list->removeAt(4);
list->removeAt(3);
list->removeAt(2);
list->removeAt(1);
list->removeAt(0);
assert(list->isEmpty()) ;
assert(list->count() == 0);
/*Тестирование вставки в начало*/
for(int i=1;i<10;i++){
list->insert(0,i);
}
/*Тестирование очистки*/
list->clear();
assert(list->isEmpty() ) ;
assert(list->count() == 0);
/*Тестирование удаления одинаковых элементов*/
for(int i=0;i<100;i++)
list->add(486);
list->remove(486);
assert(list->isEmpty() ) ;
assert(list->count() == 0);
/*Тестирование изменения*/
list->add(1);
assert(list->get(0)==1);
list->set(0,31337);
assert(list->get(0)==31337);
list->clear();
/*Тестирование вставки элемента на место выбранного*/
list->add(0);
list->add(1);
assert(list->get(1)==1);
list->insert(1,2);
assert(list->get(1)==2);
list->insert(2,3);
assert(list->get(2)==3);
list->insert(2,4);
assert(list->get(2)==4);
list->clear();
/*Тестирование итератора*/
//заполняем список
for(int i=0;i<10;i++){
list->add(i);
}
//просим итератор
List_Iterator* it=list->getIterator();
it->begin(); //ставим итератор на начало
assert(!it->prev()); //сзади элементов нету
int i=0;
//обходим вперед
do{
assert(it->get()==i);
i++;
}while(it->next());
it->end(); //cтавим итератор в конец
assert(!it->next()); //впереди элементов нету
i=9;
do{
assert(it->get()==i);
i--;
}while(it->prev());
delete(it);
delete(list);
printf("Все тесты пройдены!\n");
}
void print_menu_header(){
printf("1 - Напечатать список\n");
printf("2 - Вставка элемента в начало\n");
printf("3 - Вставка элемента в конец\n");
printf("4 - Вставка элемента перед заданным элементом\n");
printf("5 - Удаление элемента по индексу\n");
printf("6 - Удаление элемента по значению\n");
printf("7 - Вывод числа элементов\n");
printf("8 - Добавить k экземпляров последнего элемента в начало списка\n");
printf("9 - Выход\n\n");
}
int main(){
int command=0;
int i,j;
test();
List* list = new List();
while(true){
print_menu_header();
scanf("%i", &command);
switch(command){
case 1:
list->print();
break;
case 2:
printf("Введите элемент: ");
scanf("%i",&i);
list->insert(0,i);
break;
case 3:
printf("Введите элемент: ");
scanf("%i",&i);
list->add(i);
break;
case 4:
printf("Введите элемент перед который хотите вставить: ");
scanf("%i",&j);
printf("Введите элемент для вставки: ");
scanf("%i",&i);
list->insert(j,i);
break;
case 5:
printf("Введите номер элемента для удаления (индексация с нуля): ");
scanf("%i",&j);
list->removeAt(j);
break;
case 6:
printf("Введите значение элемента для удаления: ");
scanf("%i",&i);
list->remove(i);
break;
case 7:
printf("В списке %i элементов\n",list->count());
break;
case 8:
printf("Введите число повторений: ");
scanf("%i",&j);
i=list->get(list->count()-1);
for(;j>0;j--)
list->insert(0,i);
break;
case 9:
return 0;
}
}
return 0;
}