-----------------------------------

Christ1m

Tue Mar 17, 2009 6:34 pm


Java Data Structure

-----------------------------------

I need to write a recursive function that takes a linked list and an integer n, and returns a copy of the list, without the n-th element. 
 
The program should build a list containing the integers 0 to 9, then prompt the user for an input n, delete the n-th element, and print the result. So the user should see this behavior:

number of the element to delete: 5
result: 0 1 2 3 4 6 7 8 9

I need some ideas on how the structure of the program should look like.


-----------------------------------

Tony

Tue Mar 17, 2009 6:42 pm


Re: Java Data Structure

-----------------------------------

I need some ideas on how the structure of the program should look like.

write a recursive function...

Your program should be a class with a recursive method.


-----------------------------------

chili5

Tue Mar 17, 2009 6:44 pm


RE:Java Data Structure

-----------------------------------

That doesn't seem difficult.

Do you know about the ArrayList or LinkedList?

Or are you implementing your own data structure?

Either way, you shouldn't have to use a recursive function to remove the n-th element.

Just use the remove method?


-----------------------------------

Tony

Tue Mar 17, 2009 6:52 pm


Re: RE:Java Data Structure

-----------------------------------

Either way, you shouldn't have to use a recursive function to remove the n-th element.
That would defeat the purpose of the exercise; if it explicitly asks for a recursive solution. Besides, recursion is your friend ;)


-----------------------------------

Christ1m

Tue Mar 17, 2009 11:03 pm


Re: Java Data Structure

-----------------------------------

import java.util.*;
public class lp
{
public int value;
public lp next;

public lp(int value, lp next)
{
this.next = next;
this.value = value;
}


//lp copy_except(lp head,int n,int counter)
//This function returns a copy of the list at "head" except for element "n", starting the count at "counter". 
//To call it, set "head" to the input list, "n" to the element to be omitted, and counter to 0.

 
// Recursive Function
  //If the input list is empty, return null. 
  //If not, call the function recursively with the rest of the list, n, and counter+1 as arguments.
  //If counter=n, return the result of the recursive call (omitting the n-th element of the list); 
 //otherwise put the first element of the list in front of the list returned by the recursive call



  //helper method: write out the items of the linked list
    public static void write(lp node){
  
     if(node != null){
        System.out.print(node.value + "   ");
        write(node.next);
      }  
    }
     
public static void main(String

 
  

Right now im clueless. I dont know how to  start the recursive function and the method. (Some basic pseudo code maybe helpful). Even though I dont have  those functions, I  wonder if Im heading to the right direction with the main method.


Mod Edit: Remember to use syntax tags! Thanks :) Code Here


-----------------------------------

Tony

Tue Mar 17, 2009 11:23 pm


RE:Java Data Structure

-----------------------------------

you "start" a recursive function from the end -- what is the base case? (that is, what is the most simple case, to which a solution is trivial? it likely has to do with the least number of elements).

The rest of the recursive function is a step that brings current case closer to that base case (even if just by a bit).


-----------------------------------

jbking

Wed Mar 18, 2009 7:11 am


Re: Java Data Structure

-----------------------------------

I need to write a recursive function that takes a linked list and an integer n, and returns a copy of the list, without the n-th element. 
 
The program should build a list containing the integers 0 to 9, then prompt the user for an input n, delete the n-th element, and print the result. So the user should see this behavior:

number of the element to delete: 5
result: 0 1 2 3 4 6 7 8 9

I need some ideas on how the structure of the program should look like.

Are you sure about that example?  I ask because if n is 1 then you are removing the first element which is 0 and not 1.  This is being a bit nit picky but I think it is a fair question as the list isn't that the n-th element has value n but n-1, creating to my mind some confusion which I'd hope some other people may have in reading the question.


-----------------------------------

Christ1m

Wed Mar 18, 2009 1:52 pm


Re: Java Data Structure

-----------------------------------


public static  lp copyExcept(lp head,int n,int counter)
{
  //This function returns a copy of the list at "head" except for element "n", starting the count at "counter". 
//To call it, set "head" to the input list, "n" to the element to be omitted, and counter to 0.
  
   counter = 0;
if (head != null | n