Solutions Exercises 1

E1. Exercises 1-2, 7-8 of Chapter 3 in Gilberg-Forouzan’s textbook.

E2. Problems 10-15 of Chapter 3 in Gilberg-Forouzan’s textbook (using pseudocode).
Solutions

Exercises

pPre = null

pLoc = list.head

Nếu sau đó ta thực hiện các câu lệnh sau:

pLoc = pLoc->link

pPre = pPre->link

Điều này sẽ làm chương trình báo lỗi vì pPre là Null nên không thể truy xuất đến pPre->Link. Hoặc nếu ban đầu danh sách là rỗng thì pLoc cũng là Null nên ta cũng không thể truy xuất đến pLoc->Link. Vì vậy ta sẽ sửa lại như sau:

1 loop (pLoc not null AND target != pLoc->data.key)

1 pPre = pLoc

2 pLoc = pLoc->link

2 end loop
7. Khi ta thực hiện câu lệnh list1 = list2 thì list1 sẽ không còn trỏ đến phần tử đầu tiên của danh sách thứ nhất nữa mà nó sẽ trỏ đến phần tử đầu tiên của danh sách thứ 2. Và chính điều này làm cho danh sách thứ nhất sẽ mất hẳn và không còn có thể truy xuất đến được.
8. Khi thực hiện các câu lệnh sau

temp = list1

loop (temp->link not null)

temp = temp->link

end loop

temp->link = list2

cho cả 2 danh sách trong câu 7 thì chương trình sẽ nối danh sách 2 vào cuối danh sách 1.

Problems

This program builds a linked list contains integers which are read from the keyboard and will be stopped when users press ‘N’

returns head pointer pList is pointed to the head of the List of Integer

createList(pList)

pPre = null;

1 valid = false

2 loop (valid false)

1 print (“Do you want to put the new integer(Y/N):”)

2 read (choice)

3 if (choice equal ‘Y’)

1 read (number)

2 insert(pList,pPre,number)

3 pPre = pPre->link

4 else

1 valid = true

3 end loop

4 printList(pList)

5 return (pList)

This algorithm accepts a link list, traverses it and returns the data in the node with the minimum key value

1 min = invalid data value

2 if (pList not null)

1 min = pList->data

2 pWalk = pList->link

3 loop (pWalk not NULL)

1 if (pWalk ->data < min)

1 min = pWalk ->data

2 end if

3 pWalk = pWalk ->link

4 end loop

3 end if

This algorithm traverses a linked list and deletes all nodes whose keys are negative

1 pLoc = pList

2 pPre = null

3 loop (pLoc not null)

1 if (pLoc ->key < 0)

1 pDel = pLoc

2 pLoc = pLoc ->link

3 deleteNode(pList, pPre, pDel, dataOut)

2 else

1 pPre = pLoc

3 end if

5 return (pList not equal null)

This algorithm traverses a linked list and deletes all nodes that are after a node with a negative key

1 pWalk = pList

2 loop (pWalk not null)

1 if (pWalk ->key < 0 AND pWalk ->link not null)

1 deleteNode(pList, pWalk, pWalk ->link, dataOut)

2 end if

3 end loop

4 return (pList not equal null)

end delAfterNegative
14. algorithm delBeforeNegative (ref pList )

This algorithm traverses a linked list and deletes all nodes that are before a node with a negative key

1 if (pList not null)

1 pWalk = pList->link

2 pDel = pList

3 pPre = null

2 else

3 endif

1 if (pWalk ->key < 0)

1 deleteNode(pList, pPre, pDel, dataOut)

2 else

3 end if

5 pWalk = pWalk ->link

5 end loop

6 return (pList not equal null)

This algorithm is basically a modified version of the Algorithm 3-16, appendTwoLists and the build and the append algorithms are unmodified. The whole algorithm creates two linked lists, appends the second to the first, and displays the count of nodes in the appended list.

1 build (pList1, file1)

2 build (pList2, file2)

3 append (pList1, pList2)

4 printList (pList1)

5 print(pList1->count)

6 return

E1. Exercises 1 and 2 of Chapter 4 in Gilberg-Forouzan’s textbook.

Hint: use a temporary stack to preserve the order.

Solutions

Exercises

Ex 1.

4.1

4.2

Ex 2.

algorithm copyStack (ref sourceStack ,

ref destStack

1 temp = createStack

2 loop (not empty (sourceStack))

1 popStack (sourceStack, x)

2 pushStack (temp, x)

3 end loop

4 loop (not empty (temp))

1 popStack (temp, x)

2 pushStack (sourceStack, x)

3 pushStack (destStack, x)

5 end loop

end copyStack

Chapter 3 – Queues

Exercises

E1. Exercises 1 to 6 of Chapter 5 in Gilberg-Forouzan’s textbook.

E2. Write the pseudocode for an algorithm called stackToQueue that creates a queue from a stack. After the queue has been created, the top of the stack should be the front of the queue and the base of the stack should be the rear of the queue. At the end of the algorithm, the stack should be empty.
E3. Write the pseudocode for an algorithm called queueToStack that creates a stack from a queue. After the stack has been created, the front of the queue should be the top of the stack and the rear of the queue should be the base of the stack. At the end of the algorithm, the queue should be empty.
E4. Write the pseudocode for an algorithm called reverseStack that reverses the contents of a stack. The algorithm must have only one parameter for the stack to be reversed.

Hint: use a temporary queue.

Solutions

Ex 1.

5.1

5.2


5.3


5.4

5.5

5.6

Ex 2.

algorithm stackToQueue (ref stack , ref queue )

This algorithm creates a queue from a stack

Pre stack already exists

Post queue created from stack--stack empty

1 queue = createQueue

2 loop (not empty (stack))

1 popStack (stack, data)

2 enqueue (queue, data)

3 end loop

end stackToQueue
Ex 3.

algorithm queueToStack (ref queue , ref stack )

This algorithm creates a stack from a queue

Pre queue already exists

Post stack created from queue--queue empty

1 stack = createStack

2 S = createStack

3 loop (not empty (queue))

1 dequeue (queue, data)

2 pushStack (S, data)

4 end loop

5 loop (not empty (S))

1 popStack (S, data)

2 pushStack (stack, data)

6 end loop

end queueToStack
Ex 4.

algorithm reverseStack (ref stack )

This algorithm reverses the contents of a queue

Pre stack is a valid stack

Post contents of stack reversed

1 Q = createQueue

2 loop (not empty (stack))

1 popStack (stack, data)

2 enqueue (Q, data)

3 end loop

4 loop (not empty (Q))

1 dequeue (Q, data)

2 pushStack (S, data)

5 end loop

end reverseStack

tải về 41.68 Kb.

Chia sẻ với bạn bè của bạn: