程序代写代做 algorithm C data structure compiler Java CE204

CE204
Data Structures and Algorithms
Part 1
16/01/2019 CE204 Part 1
1

Recommended Reading
The most useful book for much of the material in this module is
Data Structures and Algorithm Analysis in Java (2nd ed.), M.A. Weiss (Pearson, 2007)
This book does not, however, cover in detail all of the Java programming material. Hence a recent Java programming text will be useful as additional reading, e.g.
Java How To Program (7th ed.), H.M. Deitel & P.J. Deitel (Prentice Hall, 2007)
There are many alternative programming texts – if you select a different one you should ensure that it covers Java 5.
16/01/2019 CE204 Part 1
2

Assessment
 Two hour exam in May/June (70% of the module credit)  Assignment 1 (10% of the module credit); to be handed
out in week 18, for submission by Tuesday of week 21
 Assignment 2 (10% of the module credit); to be handed out in week 22, for submission by Tuesday of week 25
 Multiple-choice test (10% of the module credit) on Friday of week 21
16/01/2019 CE204 Part 1
3

Linked Lists 1
A recursive data structure is a type that contains a reference or pointer to another object of the same type.
The simplest example is a linked list in which each object contains a data item and a reference to the next object in the list. (The last item in the list will hold a null reference, indicating there is no next object.)
16/01/2019 CE204 Part 1
4

Linked Lists 2
The traditional operations associated with linked lists are
 cons, which takes a list and a data item and constructs a new list by adding the item to the front of the list
 head, which returns the item at the front of the list
 tail, which returns the list comprising everything but the
head.
16/01/2019 CE204 Part 1
5

Linked Lists in Java 1
In Java we can declare a class ListCell whose members are a data item and a reference to the next element of the list. It is preferable to write head and tail as methods of the class and use a constructor instead of the cons function.
On the next slide we present a class for a linked list of data items of type int.
The instance variables could be made private – a decision should be made based on needs of the application for which the class will be used. For example, if it is going to be necessary to change data in some of the cells the data member will need to be public, but if it is necessary to ensure that contents cannot be changed once added to the list the members should be private.
16/01/2019 CE204 Part 1
6

Linked Lists in Java 2
class ListCell
{ int data;
ListCell next;
public ListCell(int i, ListCell c) { data = i;
next = c; }
public int head() { return data;
}
public ListCell tail() { return next;
}
}
16/01/2019 CE204 Part 1
7

Linked Lists in Java 3
An empty list in Java would be represented by null.
To create a list containing the elements 1 (at the front), 2 and 3 we could use
ListCell l1 = new ListCell(3, null);
ListCell l2 = new ListCell(2, l1);
ListCell myList = new ListCell(1, l2);
or, more concisely,
ListCell myList = new ListCell(1,
new ListCell(2, new ListCell(3, null)));
16/01/2019 CE204 Part 1
8

Linked Lists in Java 4
To obtain the third item in a list l we would use
ListCell t1 = l.tail(); ListCell t2 = t1.tail(); int answer = t2.head();
or, more concisely,
int answer = l.tail().tail().head();
Note that an exception of type NullPointerException will be thrown if the list does not contain three elements, since one of the ListCell objects (l, t1 or t2) will be null and we cannot apply methods to a null reference.
16/01/2019 CE204 Part 1
9

Linked Lists in Java 5
We could write a loop to find the nth item in a list l: int i;
ListCell c = l;
for (i = 1; i and Vector – TreeSet and Vector are generic classes.
To allow the use of linked lists of different types of item it is desirable to produce a generic linked-list class; in order to do this we have to declare the class as LList, where T is a type parameter which can be instantiated with any non-primitive type.
Note that the type parameter does not have to be T, although it is conventional to use a single upper-case letter. E would be equal suitable (indicating element type).
16/01/2019 CE204 Part 1
21

Generic Classes 3
To make our linked-list class generic we need to replace all occurrences of LList by LList and use the type parameter T wherever the name of the element type is needed. Since the type of the elements stored in the ListCell class will be T it is preferable to also make this class generic (it would be possible to use a ListCell class with elements of type Object, with downcasting used where appropriate).
A complete version of a generic linked-list class (with a back reference) is provided on the following slides. Note that the type parameter does not appear after the method name in the declaration of the constructor but it is used when constructors are called.
16/01/2019 CE204 Part 1
22

Generic Classes 4
// LList.java – generic version
class ListCell
{ T data;
ListCell next;
public ListCell(T i, ListCell c)
{ data = i;
next = c; }
}
class ListException extends RuntimeException { …………
}
16/01/2019 CE204 Part 1
23

Generic Classes 5
// generic LList.java continued
public class LList
{ private ListCell front, back;
public LList()
{ front = back = null; }
public void addToFront(T i)
{ front = new ListCell(i, front);
if (back == null)
back = front;
}
16/01/2019 CE204 Part 1
24

Generic Classes 6
// class LList continued
public void addToBack(T i)
{ if (front == null)
front = back = new ListCell(i, null); else
{ back.next = new ListCell(i, null);
back = back.next;
} }
16/01/2019 CE204 Part 1
25

Generic Classes 7
// class LList continued
public T elementAt(int n)
{ ListCell c = front;
if (n<0) throw new ListException(); for (int i = 0; i ll, int numCopies)
{ for (int i = 0; i the compiler would inform us that T has not been declared – we must explicitly specify that it is a type parameter by inserting before the return type in the method declaration:
public static void addCopies(T s, LList ll, int numCopies)
{ for (int i = 0; i