CIS-610 Data Structures and Algorithms

Home Work #5							Due:	10/21/1999


1. Implement the routines empty, push, pop, and popandtest using array and the dynamic storage implementation of linked stack.

2. Implement the routines empty, insert, and remove using a dynamic storage implementation of linked queue.

3. Implement the routines empty, pqinsert, and pqmindelete using dynamic storage implementation of a linked priority queue.

4. Write a program to interchange mth and nth element of a linked list.

5. Suppose that a character string is represented by a list of single characters. Write a set of routines to manipulate such lists as follows (in the following, l1, l2, and list are pointers to the header node of a list representing a character string,  str is an array of characters, and i1 and i2 are integers)

a. strcnvcl(str) to convert the character string str to a list. This function returns a pointer to a header node.

b. strpsl(l1, l2) to perform strpos function (C language function; this function returns an integer indicating the starting location of the first occurrence of the second parameter string within first parameter string) on two character strings represented by lists. This function returns integer.

6. Write a routine to perform each of the following operations for circular linked lists:

a. Delete every second element from a list.
b. Free all nodes in a list.
c. Return the sum of the integers in a list.

7. Write a routine to perform each of the following operations for doubly linked circular lists:

a. Append an element to the end of a list.
b. Form a list containing the intersection of the elements of two list.
c. Move node(p) forward n position in a list.