联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codehelp

您当前位置:首页 >> CS程序CS程序

日期:2021-03-27 10:15

ADS2 2021 1 Lab Sheet 3
Algorithms and Data Structures (ADS2)
Laboratory Sheet 3
This lab sheet contains material based on Lectures 10-12. This exercise is not assessed but
should be completed to gain sufficient experience in the implementation of elementary
abstract data types, and the testing thereof.
Exercise
You are to implement the Dequeue abstract data type (ADT) using two different data structures.
Then, you will use this ADT to define generic Stack and Queue ADTs. Finally, you will use a
stack to implement a non-recursive quicksort.
Part 1
a) Implement in Java the merge sort algorithm for linked lists introduced in Lecture 10
(slide 36). Use the following class structure to implement linked lists.
public class LinkedList{
private Node head;
private static class Node{
private Item key;
private Node next;
}
public LinkedList(){
head = null;
}
...
Part 2
a) Implement in Java the Dequeue abstract data type introduced in Lecture 12 (slide 35).
Use resizable arrays in a circular fashion (slide 26) in the class below. What is the time
complexity of each operation (i.e. PUSH-BACK, PUSH-FRONT, POP-BACK, POPFRONT)?
public class ResizingDequeue{
private Item[] q;
private int n; // number of elements in the dequeue
private int tail;
private int head;
public ResizingDequeue (){
q = (Item[]) new Object[2];
n = 0;
head = 0;
tail = 0;
}
...
ADS2 2021 2 Lab Sheet 3
b) Implement the Dequeue abstract data type using a circular doubly linked list. Modify
the class structure given in 1a for singly linked lists to include prev pointers and a
sentinel. What is the time complexity of each operation?
Part 3
a) Implement the Stack ADT using the Dequeue you implemented in 2b.
b) Implement the Queue ADT using the Dequeue you implemented in 2b.
c) Implement the Queue ADT using two stacks. What is the time complexity of each
operation?
Part 4
Using an auxiliary stack, implement an iterative version of quicksort. To reduce the stack size,
first push the indexes of the smaller subarray.

版权所有:留学生编程辅导网 2021,All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。