Solutions Exercises 1



tải về 41.68 Kb.
Chuyển đổi dữ liệu02.09.2016
Kích41.68 Kb.
Chapter 2 – Linked Lists

Exercises

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



1. pHead là con trỏ dùng để giữ (nhớ) phần tử đầu tiên của danh sách, vì vậy nếu ta thực thi câu lệnh pHead = pHead ->link trong thao tác search list sẽ làm thay đổi giá trị con trỏ này và như vậy nó sẽ không còn trỏ đến phần tử đầu tiên của danh sách nữa. Điều này sẽ làm cho danh sách tạo ra không còn có thể kiểm soát trong toàn bộ chương trình. Chính vì điều này mà chúng ta cần đến 2 con trỏ khác là pPre và pLoc, giúp giữ vị trí hiện tại và vị trí trước trong thao tác search mà không làm ảnh hưởng đến pHead.
2. Trong thủ tục seach list (trang 93), các con trỏ pPre và pLoc được khởi động lần đầu như sau

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


10. algorithm buildLinkedListOfInteger

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



Pre nothing

Post List has been built

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



5 endif

3 end loop

4 printList(pList)

5 return (pList)



end buildLinkedListOfInteger
11. algorithm minimum (val pList )

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



Pre pList is a valid pointer to the head of the list

Post the data with minimum key value has been returned or in case of an empty list, an invalid data value is returned

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


4 return (min)

end minimum

12. algorithm delAllNegative (ref pList )

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



Pre List is a pointer to the head of a linked list

Post returns false if empty list or true otherwise

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



2 pLoc = pLoc ->link

3 end if


4 end loop

5 return (pList not equal null)



end delAllNegative
13. algorithm delAfterNegative (ref pList )

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



Pre List is a pointer to the head of a linked list

Post returns false if empty list or true otherwise

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 pWalk = pWalk ->link

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



Pre pList is a pointer to the head of a linked list

Post returns false if empty list or true otherwise

1 if (pList not null)

1 pWalk = pList->link

2 pDel = pList

3 pPre = null

2 else


1 pWalk = null

3 endif


4 loop (pWalk not null)

1 if (pWalk ->key < 0)

1 deleteNode(pList, pPre, pDel, dataOut)

2 else


1 pPre = pDel

3 end if


4 pDel = pWalk

5 pWalk = pWalk ->link

5 end loop

6 return (pList not equal null)



end delBeforeNegative
15. algorithm appendAndCount

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.



Pre nothing

Post creates and appends the lists, prints final list and displays total count

1 build (pList1, file1)

2 build (pList2, file2)

3 append (pList1, pList2)



list2 is appended after list1 and list count updated

4 printList (pList1)

5 print(pList1->count)

6 return



end appendAndCount


Chapter 3 – Stacks

Exercises

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


E2. Write the pseudocode for an algorithm called copyStack that copies the contents of one stack into another. The algorithm must have two parameters of type stack, one for the source stack and one for the destination stack. The order of the stacks must be identical.

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


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2016
được sử dụng cho việc quản lý

    Quê hương