1. (Online Address Book Revisited) Programming Exercise 9 in Chapter 3 could han
ID: 3623066 • Letter: 1
Question
1. (Online Address Book Revisited) Programming Exercise 9 in Chapter 3 could handle a maximum of only 500 entries. Using linked list, redo the program to handle as many entries as required. Add the following operations to your program:a. Add or delete a new entry to the address book.
b. When the program terminates, write the data in the address book to a disk.
12. (Linked List with Header and Trailer Nodes) This chapter defined and identified various operations on a linked list with header and trailer nodes.
a. Write the definition of the class that defines a linked list with header and trailer nodes as an ADT.
b. Write the definitions of the member functions of the class defined in (a). (You may assume that the elements of the linked list with header and trailer nodes are in ascending order.)
c. Write a program to test various operations of the class defined in (a).
13. (Circular Linked List) This chapter defined and indentified various operations on a circular linked list.
a. Write the definitions of the class CircularLinkedList and its member functions. (You may assume that the elements of the circular linked list are in ascending order.)
b. Write a program to test various operations of the class defined in (a).
14. (Programming Example Video Store)
a. Complete the design and implementation of the class customerType defined in the Programming Example Video Store.
b. Design and implement the class customerLinstType to create and maintain a list of customers for the video store.
Heres what I have so far
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6
typedef struct
{
int data;
struct NODE *next;
}NODE;
NODE *deleteNode(NODE *list, int sim)
{
NODE *prevNODE, *curNODE;
prevNODE = curNODE = list;
while(curNODE != NULL)
{
if( (curNODE -> data) == sim )
{
prevNODE -> next = curNODE -> next;
if(curNODE == list)
{
list = (NODE *)prevNODE -> next;
}
printf(" Deleting NODE %d...", curNODE -> data);
free(curNODE);
return list;
}
prevNODE = curNODE;
curNODE = (NODE *)curNODE -> next;
}
printf(" NODE %d not found... ", sim);
return list;
}
/* End of deleteNode */
NODE *insertNode(NODE *list, NODE *new, int pos)
{
NODE *cur, *nxt;
int count = 0;
cur = nxt = list;
while(nxt != NULL)
{
if(count++ == pos)
{
new -> next = nxt;
if(nxt != list)
{
cur -> next = (NODE *)new;
printf(" Inserting NODE %d at %d pos", new -> data, pos);
return list;
}
printf(" Inserting NODE %d at %d pos", new -> data, pos);
return new;
}
cur = (NODE *)nxt;
nxt = (NODE *)nxt -> next;
}
printf(" Position out of bounds ...");
printf(" Unable to insert NODE %d at %d position.", new -> data, pos);
return list;
}
/* End of insertNode */
NODE *createList(int size)
{
NODE *list, *head;
list = head = NULL;
if(size <= 0)
{
printf(" Enter valid size of the linked list. ");
return list;
}
list = (NODE *)malloc(sizeof(NODE));
head = list;
list -> data = size;
while(--size)
{
list -> next = (NODE *)malloc(sizeof(NODE));
list = (NODE *)list -> next;
list -> data = size;
}
list -> next = NULL;
return head;
}
/* End of createList */
/* Reverse a single linked list non-recursively */
NODE *reverseList(NODE *list)
{
NODE *prev, *cur, *last, *next;
if(list -> next == NULL)
{
printf(" Cannot reverse list, because only one node is present in the list.");
return list;
}
printf(" Reversing the list......non-recursive mode.");
prev = cur = last = next = list;
cur = (NODE *)(list -> next);
next = (NODE *)(cur -> next);
while(cur != NULL)
{
cur -> next = prev;
last -> next = next;
prev = cur;
cur = next;
if(next)
{
next = (NODE *)(next -> next);
}
}
return prev;
}
/* End of reverseList */
NODE *reverseList_rec(NODE *list, NODE *prev, NODE *cur)
{
NODE *next, *temp;
if(cur == NULL)
{
return prev;
}
next = cur -> next;
cur -> next = prev;
list -> next = next;
temp = reverseList_rec(list, cur, next);
return temp;
}
/* End of reverseList_rec */
/* Delete nth node from back */
NODE *delete_nth_NODE_from_back(NODE *list, int node_n)
{
NODE *temp, *prev ,*cur;
int count;
if(list == NULL)
{
printf(" Not applicable, List is empty. ");
return NULL;
}
printf(" Deleting %dth node from Single list from back... ", node_n);
cur = prev = NULL;
temp = list;
count = 1;
while(count++ != node_n)
{
temp = temp -> next;
}
cur = list;
while(temp = temp -> next)
{
prev = cur;
cur = cur -> next;
}
/* End of while */
if(cur == list)
{
list = list -> next;
free(cur);
return list;
}
prev -> next = cur -> next;
free(cur);
return list;
}
/* End of delete_nth_NODE_from_back */
/* Deleting the middle node of a list */
NODE *del_mid_node(NODE *list)
{
NODE *temp, *cur, *prev;
int count = 2;
if(list == NULL)
{
printf(" Error: Empty single linked list. ");
return NULL;
}
temp = list;
temp = temp -> next;
cur = list;
while(temp)
{
count++;
if(count % 2 == 0)
{
prev = cur;
cur = cur -> next;
}
temp = temp -> next;
}
if(cur == list)
{
list = list -> next;
free(cur);
return list;
}
prev -> next = cur -> next;
free(cur);
return list;
}
/* End of del_mid_node */
void displayList(NODE *list)
{
printf(" ");
while(list != NULL)
{
printf(" %d ->", list -> data);
list = (NODE *)list -> next;
}
printf(" NULL ");
}
/* End of displayList */
void freeList(NODE *list)
{
NODE *temp;
while(list != NULL)
{
temp = list;
list = (NODE *)list -> next;
printf(" Freeing NODE %d... ", temp -> data);
free(temp);
}
}
/* End of freeList */
int main()
{
NODE *head;
head = (NODE *)createList(SIZE);
displayList(head);
head = (NODE *)deleteNode(head, 1);
displayList(head);
printf(" Deleting middle node from this list. ");
head = (NODE *)del_mid_node(head);
displayList(head);
NODE *new = (NODE *)malloc(sizeof(NODE));
new -> data = 59;
head = (NODE *)insertNode(head, new, 1);
displayList(head);
printf(" Reversing the Single list recursively...");
head = (NODE *)reverseList_rec(head, head, head -> next);
displayList(head);
head = (NODE *)deleteNode(head, 59);
head = (NODE *)deleteNode(head, 2);
displayList(head);
head = (NODE *)delete_nth_NODE_from_back(head, 1);
displayList(head);
head = (NODE *)reverseList(head);
displayList(head);
printf(" Reversing the Single list recursively...");
head = (NODE *)reverseList_rec(head, head, head -> next);
displayList(head);
freeList(head);
return 0;
}
/* End of main */
Explanation / Answer
Just make sure you understand that Linked lists allow you to add data anywhere in the list, but not for random access. For help see here: http://www.java-tips.org/java-se-tips/java.lang/linked-list-implementation-in-java.html // LinkedList class // // CONSTRUCTION: with no initializer // Access is via LinkedListIterator class // // ******************PUBLIC OPERATIONS********************* // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // LinkedListIterator zeroth( ) // --> Return position to prior to first // LinkedListIterator first( ) // --> Return first position // void insert( x, p ) --> Insert x after current iterator position p // void remove( x ) --> Remove x // LinkedListIterator find( x ) // --> Return position that views x // LinkedListIterator findPrevious( x ) // --> Return position prior to x // ******************ERRORS******************************** // No special errors /** * Linked list implementation of the list * using a header node. * Access to the list is via LinkedListIterator. * @author Mark Allen Weiss * @see LinkedListIterator */ public class LinkedList { /** * Construct the list */ public LinkedList( ) { header = new ListNode( null ); } /** * Test if the list is logically empty. * @return true if empty, false otherwise. */ public boolean isEmpty( ) { return header.next == null; } /** * Make the list logically empty. */ public void makeEmpty( ) { header.next = null; } /** * Return an iterator representing the header node. */ public LinkedListIterator zeroth( ) { return new LinkedListIterator( header ); } /** * Return an iterator representing the first node in the list. * This operation is valid for empty lists. */ public LinkedListIterator first( ) { return new LinkedListIterator( header.next ); } /** * Insert after p. * @param x the item to insert. * @param p the position prior to the newly inserted item. */ public void insert( Object x, LinkedListIterator p ) { if( p != null && p.current != null ) p.current.next = new ListNode( x, p.current.next ); } /** * Return iterator corresponding to the first node containing an item. * @param x the item to search for. * @return an iterator; iterator is not valid if item is not found. */ public LinkedListIterator find( Object x ) { ListNode itr = header.next; while( itr != null && !itr.element.equals( x ) ) itr = itr.next; return new LinkedListIterator( itr ); } /** * Return iterator prior to the first node containing an item. * @param x the item to search for. * @return appropriate iterator if the item is found. Otherwise, the * iterator corresponding to the last element in the list is returned. */ public LinkedListIterator findPrevious( Object x ) { ListNode itr = header; while( itr.next != null && !itr.next.element.equals( x ) ) itr = itr.next; return new LinkedListIterator( itr ); } /** * Remove the first occurrence of an item. * @param x the item to remove. */ public void remove( Object x ) { LinkedListIterator p = findPrevious( x ); if( p.current.next != null ) p.current.next = p.current.next.next; // Bypass deleted node } // Simple print method public static void printList( LinkedList theList ) { if( theList.isEmpty( ) ) System.out.print( "Empty list" ); else { LinkedListIterator itr = theList.first( ); for( ; itr.isValid( ); itr.advance( ) ) System.out.print( itr.retrieve( ) + " " ); } System.out.println( ); } private ListNode header; // In this routine, LinkedList and LinkedListIterator are the // classes written in Section 17.2. public static int listSize( LinkedList theList ) { LinkedListIterator itr; int size = 0; for( itr = theList.first(); itr.isValid(); itr.advance() ) size++; return size; } public static void main( String [ ] args ) { LinkedList theList = new LinkedList( ); LinkedListIterator theItr; int i; theItr = theList.zeroth( ); printList( theList ); for( i = 0; i < 10; i++ ) { theList.insert( new Integer( i ), theItr ); printList( theList ); theItr.advance( ); } System.out.println( "Size was: " + listSize( theList ) ); for( i = 0; i < 10; i += 2 ) theList.remove( new Integer( i ) ); for( i = 0; i < 10; i++ ) if( ( i % 2 == 0 ) == ( theList.find( new Integer( i ) ).isValid( ) ) ) System.out.println( "Find fails!" ); System.out.println( "Finished deletions" ); printList( theList ); } } // LinkedListIterator class; maintains "current position" // // CONSTRUCTION: Package visible only, with a ListNode // // ******************PUBLIC OPERATIONS********************* // void advance( ) --> Advance // boolean isValid( ) --> True if at valid position in list // Object retrieve --> Return item in current position /** * Linked list implementation of the list iterator * using a header node. * @author Mark Allen Weiss * @see LinkedList */ public class LinkedListIterator { /** * Construct the list iterator * @param theNode any node in the linked list. */ LinkedListIterator( ListNode theNode ) { current = theNode; } /** * Test if the current position is a valid position in the list. * @return true if the current position is valid. */ public boolean isValid( ) { return current != null; } /** * Return the item stored in the current position. * @return the stored item or null if the current position * is not in the list. */ public Object retrieve( ) { return isValid( ) ? current.element : null; } /** * Advance the current position to the next node in the list. * If the current position is null, then do nothing. */ public void advance( ) { if( isValid( ) ) current = current.next; } ListNode current; // Current position } // Basic node stored in a linked list // Note that this class is not accessible outside // of package weiss.nonstandard class ListNode { // Constructors public ListNode( Object theElement ) { this( theElement, null ); } public ListNode( Object theElement, ListNode n ) { element = theElement; next = n; } public Object element; public ListNode next; }Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.