SORU
10 Aralık 2008, ÇARŞAMBA


Java bağlı listeyi tersine çevrilmesi, ardışık

Şimdi bir süre için bir Java sınıfı için bir proje üzerinde çalışıyorum. Bağlantılı liste (burada AddressList içeren basit düğümleri ListNode adında) uygulamasıdır. Catch her şey özyinelemeli algoritmalar ile yapılması gerekir. Her şeyin bir yöntemi sans idare edebildim: public AddressList reverse()

ListNode:

public class ListNode{
  public String data;
  public ListNode next;
}

Şu anda reverse benim görevim sadece özyineleme izin vermek için bir argüman alır bir yardımcı işlevini çağırır.

public AddressList reverse(){
  return new AddressList(this.reverse(this.head));
}

Yardımcı fonksiyonu private ListNode reverse(ListNode current) imzası olması.

Şu anda yinelenen bir kullanıyorsanız ve bir yığın var, ama bu belirtimi gerektirir bir şey değildir. Yinelemeli ters C bir algoritma buldum ve elle kod Java dönüştürülür ve işe yaradı, ama hiçbir anlayış vardı.

Edit: Boşver, onu ben de düşündüm bu arada.

private AddressList reverse(ListNode current, AddressList reversedList){
  if(current == null) 
      return reversedList;
  reversedList.addToFront(current.getData());
  return this.reverse(current.getNext(), reversedList);
}

Ben burada olduğum sürece, kimse bu yol ile herhangi bir sorun görüyor mu?

CEVAP
10 Aralık 2008, ÇARŞAMBA


İşte kod bir cevap bu büyü değil, ama belki bulmak daha kolay baştan dibe kadar, soru-cevap küçük sorular (bu yaklaşım Küçük Lisper):

  1. Null (boş liste) tersi nedir? null.
  2. Bir öğe listesi ters nedir? eleman.
  3. N elemanlı bir liste tersi nedir? ilk element ardından ikinci elemanın ters.

public ListNode Reverse(ListNode list)
{
    if (list == null) return null; // first question

    if (list.next == null) return list; // second question

    // third question - in Lisp this is easy, but we don't have cons
    // so we grab the second element (which will be the last after we reverse it)

    ListNode secondElem = list.next;

    // bug fix - need to unlink list from the rest or you will get a cycle
    list.next = null;

    // then we reverse everything from the second element on
    ListNode reverseRest = Reverse(secondElem);

    // then we join the two lists
    secondElem.Next = list;

    return reverseRest;
}

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Disney Pets and Animals

    Disney Pets

    29 ŞUBAT 2012
  • LearnCode.academy

    LearnCode.ac

    20 Aralık 2012
  • Sarah's YouTube Channel

    Sarah's YouT

    27 Temmuz 2009