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
Chia sẻ với bạn bè của bạn: |