Java Data Structure

[Christ1m]

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]

Christ1m @ Tue Mar 17, 2009 6:34 pm wrote:

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

Christ1m @ Tue Mar 17, 2009 6:34 pm wrote:

write a recursive function...

Your program should be a class with a recursive method.

[chili5]

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]

chili5 @ Tue Mar 17, 2009 6:44 pm wrote:

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]

Java:

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[]args) {                                                              int n;    // creates a Scanner    Scanner sc = new Scanner(System.in);    // Ask the user to delete the desired element.    System.out.println("number of the element to delete:");    n = sc.nextInt();    // Prints out the answer acordding to the length of the list .   if(n <= 9)    {    System.out.println("Result = " );    }   // Prints out an error message if input is out of bound   else   {     System.out.println("Error Out of Bound");    } // Build the list here lp list1 = new lp(1, new lp(2, new lp(3, new lp(4, new lp(5, new lp(6, new lp(7, new lp(8, new lp(9, null)))))))));   System.out.print("list1 = ");   lp.write(list1);      }// end of main }// end of class

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:

[syntax="java"]Code Here[/syntax]

[Tony]

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]

Christ1m @ Tue Mar 17, 2009 4:34 pm wrote:

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]

Java:

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 <head.value) {   return new lp(n,head); }   else   {    head = head.next;    head.next = copyExcept(head.next,n,counter);    counter++;    return head;   } }   //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 public  static int remove(lp head, int n, int counter) { if(head == null) {   return 0;     } else {  return remove(head.next,n, counter+1);   }

Im having problems creating the recursive functions. I need some ideas.