VPF::Сравнение связных списков - Форум программистов

roofless

Дата 26.10.2011, 16:20 (ссылка)

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

Загрузка ...

Новичок

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

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

Даны два связных списка. Проверить, может ли быть получен второй список в результате циклического сдвига элементов первого списка.

Кое-что набросал, но не понимаю, как далее работать с этими списками, хотя бы просто сравнить элементы. Заранее спасибо =)

Код


public class Item {
    
    private int info;//элемент
    private Item link;//ссылка



public Item getLink() {
    // TODO Auto-generated method stub
    return link;
}


private int getInfo() {
    // TODO Auto-generated method stub
    return info;
}

    
    public void setLink(Item item) {
        // TODO Auto-generated method stub
        link = item;
    }
    
    
public static void newList(Item head, int[] a) {//списки передаются из массива
    Item pointer = head;
    
    pointer.setInfo(a[0]);//установка первого элемента
    for(int i = 1; i < a.length; i++){
       Item item = new Item();
       item.setInfo(a[i]);
       pointer.setLink(item);//устанавливаем ссылку на новый элемент
       pointer = item;//переходим на новый элемент
    }
    pointer = head;
    while(pointer != null){
       System.out.println(pointer.getInfo());
       pointer = pointer.getLink();
    }
}

    public void setInfo(int i) {
        // TODO Auto-generated method stub
        info = i;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Item head = new Item();//указатель на начало списка
        Item bighead = new Item();
        
        int[] a = new int [3];
        a[0]=1;
        a[1]=2;
        a[2]=3;
        
        int[] b = new int [3];
        b[0]=3;
        b[1]=2;
        b[2]=1;
        
        
        newList(head, a);
        System.out.println(" ");
        newList(bighead, b);
        

        }
}

math64

Дата 26.10.2011, 19:31 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

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

Уже есть готовый LinkedList<T> с полным функционалом.
Если нужен твой список, нужно добавить в него метод определения длины списка и итератора.
Простейший итератор - указатель на текущий Item + указатель на голову списка.
1.Если длины списков не совпадают, возвращаем false;
2.Устанавливаем итераторы ориг1 и ориг2 в начала списков список1 и список2;
3.Делаем копии копия1 и копия2 итераторов ориг1 и ориг2;
4.Сравниваем элементы копии1 и копии2 до конца списка1,
при достижении конца списка2 делаем заворот в начало;
5.Если все элементы совпали, возвращаем true;
6.Продвигаем итератор ориг2 на следующий элемент;
если не достигли конца списка, переход на 3;
7. Возвращаем false;

roofless

Дата 27.10.2011, 14:48 (ссылка)

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

Загрузка ...

Новичок

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

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

Начал с малого. Немного переделал, добавил итератор. Получилось вот что:

Код



public class Item {
    
    int element;//элемент
    Item next;//ссылка



public Item getNext() {
    // TODO Auto-generated method stub
    return next;
}


private int getElement() {
    // TODO Auto-generated method stub
    return element;
}

    
    public void setLink(Item item) {
        // TODO Auto-generated method stub
        next = item;
    }
    
    
public static void newList(Item head, int[] a) {//списки передаются из массива
    Item pointer = head;
    
    pointer.setInfo(a[0]);//установка первого элемента
    for(int i = 1; i < a.length; i++){
       Item item = new Item();
       item.setInfo(a[i]);
       pointer.setLink(item);//устанавливаем ссылку на новый элемент
       pointer = item;//переходим на новый элемент
    }
    pointer = head;
    while(pointer != null){
      // System.out.println(pointer.getElement());
       pointer = pointer.getNext();
    }
}

    public void setInfo(int i) {
        // TODO Auto-generated method stub
        element = i;
    }

    public static boolean isEmpty(Item head, int[] a ) {//проверка на пустоту
        
        return head.next == null;

    }
    
    public static LinkedListIterator zeroth(Item head, int[] a) {//метод возващает голову списка

        return new LinkedListIterator(head);

    }
    
    public LinkedListIterator first(Item head, int[] a) {//возвращает первый элемент списка

        return new LinkedListIterator(head.next);

    }
    
    public static int listSize1(Item head, int[] a) {//вывод размера списка

        LinkedListIterator itr;

        int size1 = 0;       

        for( itr = (head.zeroth(head, a)); itr.isValid(); itr.advance() )
         
            size1++;

        return size1;

    }
    
    public static int listSize2(Item bighead, int[] b) {//вывод размера списка

        LinkedListIterator itr;

        int size2 = 0;       

        for( itr = (bighead.zeroth(bighead, b)); itr.isValid(); itr.advance() )
         
            size2++;

        return size2;

    }
    
    public static void printList(Item head, int[] a) {//вывод списка

        if( Item.isEmpty(head, a))

            System.out.print( "Empty list" );

        else {

            LinkedListIterator itr = Item.zeroth(head, a);

            for(; itr.isValid( ); itr.advance( ))

                System.out.print(itr.retrieve( ) + " " );

        }

        System.out.println( );

    }
    
    public static void compareList(int  size1, int size2) {
        if (size1==size2) {
            System.out.println("Размеры списков равны");
            boolean sizeLengthEqual = true;
        }
        else {
            System.out.println("Размеры списков не равны");
            boolean sizeLengthEqual = false;
        }
    }
    
    
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Item head = new Item();//указатель на начало списка
        Item bighead = new Item();
        
        int[] a = new int [5];
        a[0]=1;
        a[1]=2;
        a[2]=3;
        a[3]=4;
        a[4]=5;
        
        int[] b = new int [3];
        b[0]=3;
        b[1]=2;
        b[2]=1;
        

        
        newList(head, a);
        System.out.println(" ");
        newList(bighead, b);
        
        printList(head, a);
        System.out.println(" ");
        printList(bighead, b);
        
        System.out.println( "Размер первого списка: " + listSize1(head, a));
        
        System.out.println( "Размер второго списка: " + listSize2(bighead, b));
        
    compareList(listSize1(head, a), listSize2(bighead, b));
    
    }
}

И код итератора:

Код



public class LinkedListIterator {

    LinkedListIterator(Item next) {

        current = next;

    }



    public boolean isValid( ) { 

        return current != null;

    }

    


    public Object retrieve( ) {

        return isValid( ) ? current.element : null;

    }

    

    public void advance( ) {//продвижение

        if( isValid( ) )

            current = current.next;

    }

    

    Item current;    // текущая позиция

}

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

Это сообщение отредактировал(а) roofless - 27.10.2011, 16:01

math64

Дата 27.10.2011, 21:16 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

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

Методы listSize1 и listSize2 дублирутся, нужна одна listSize.
При создании итератора нужно запоминать начало списка и иметь метод rewind() для повторного просмотра.

Код


bool cicledCompare(LinkedListIterator it1, LinkedListIterator it2) {
   сравнение длин, учет что оба списка пусты
   while (it1.isValid()) {
      LinkedListIterator copy1 = LinkedListIterator(it1);
      bool isSame = true;
      while(isSame && it2.isValid()) {
        if(it2.retrieve() != copy1.retrieve()) { isSame = false; break;
        it2.advance(); copy1.advance();
        if(!copy1.isValid()) rewind();
      }
      if (isSame) return true;
      it1.advance();
   }
}

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

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