The advantages of a two-way list a circular header list may be combined into a two-way circular header list as . The list is circular because the two end nodes point back to the header node.Observe that such a two-way list requires only one list pointer variable START, which points to the header node. This is because the two pointers in the header node point to the two ends of the list.
Tuesday, March 22, 2016
Two-Way Header Lists
The advantages of a two-way list a circular header list may be combined into a two-way circular header list as . The list is circular because the two end nodes point back to the header node.Observe that such a two-way list requires only one list pointer variable START, which points to the header node. This is because the two pointers in the header node point to the two ends of the list.
Inserting into a Sorted Linked List
Suppose ITEm is to be inserted into a sorted linked LIST. Then ITEM must be inserted between nodes A and B so that
INFO(A) < ITEM <= INFO(B)
The following is a procedure which finds the location LOC of node A, that is, which finds the location LOC of the last node in LIST whose value is less that ITEM.
Traverse the list, using a pointer variable PTR and comparing ITEM with INFO[PTR] at each node. While traversing, keep track of the location preceding node by using a pointer variable SAVE
SAVE : = PTR and PTR : = LINK[PTR].
Deletion Algorithms
Algorithms which delete nodes from linked lists come up in various situations. We discuss two of them here. The first one deletes the node following a given node, and the second one deletes the node with a given ITEM of information. All our algorithms assume that the linked list is in memory in the form LIST(INFO, LINK, START, AVAIL).
All of our deletion algorithms will return the memory space of the deleted node N to the beginning of the AVAIL list. Accordingly, all of our algorithms will include the following pair of assignments, where LOC is the location of the deleted node N:
LINK[LOC] : = AVAIL and then AVAIL : = LOC
Some of the algorithms may want to delete either the first node or the last node from the list. An algorithms that does so must check to see if there is a node in the list, If not, i.e, If START = NULL, then the algorithms will print the message UNDERFLOW.
COPY(INFO, LINK, NAME1, NAME2, AVAIL)
1. Set NAME2 : = NULL. [Forms empty list]
2. [NAME1 empty?] If NAME1 = NULL, then: Exit.
3. [Insert first node of NAME1 into NAME2]
Call INSLOC(INFO, LINK, NAME2, AVAIL, NULL, INFO[NAME1]) or :
(a) If AVAIL = NULL, then : Write : OVERFLOW, and Exit.
(b) Set NEW : = AVAIL and AVAIL : = LINK[AVAIL]. [Removes first node from AVAIL list.]
(c) Set INFO[NEW] : = INFO[NAME]. [Copies data into new node]
(d) [Insert new node as first node in NAME2.]
4. [Initializes pointer PTR and LOC]
Set PTR : = LINK[NEW] and LOC : = NAME2.
5. Repeat Steps 6 and 7 while PTR != NULL.
6. Call INSLOC(INFO, LINK, NAME2, AVAIL, LOC, INFO[PTR]) or:
(a) If AVAIL = NULL, then : Write : OVERFLOW, and Exit.
(b) Set NEW : = AVAIL and AVAIL : = LINK[AVAIL].
(c) Set INFO[NEW] : = INFO[PTR]. [Copies data into new node]
(d) [Insert new node into NAME2 after the node with location LOC]
Set LINK [NEW] : = LINK[LOC], and LINK[LOC] : = NEW.
7. Set PTR : = LINK[PTR] and LOC : = LINK[LOC]. [Updates PTR and LOC]
[End of Step 5 loop]
Monday, March 21, 2016
Insertion Algorithms
(a) Checking to see if space is available in the AVAIL list. If not, that is, if AVAIL = NULL, then the algorithm will print the message OVERFLOW.
(b) Removing the first node from the AVAIL list.Using the variable NEW to keep track of the location of the new node, the step can be implemented by the pair of assignments
NEW : = AVAIL, AVAIL : = LINK[AVAIL]
(c) Copying new information into the new node.
INSERT(INFO, LINK, START, AVAIL, ITEM)
1. [Use Procedure FINDA to find location of the node preceding ITEM]
Call FINDA(INFO, LINK, START, ITEM, LOC)
2. [Use Algorithm INSLOC to insert ITEM after the node with location LOC.]
Call INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM)
FINDA(INFO, LINK, START, ITEM, LOC)
1. [List of empty?] If START = NULL, then : Set LOC : = NULL, and Return.
2. [Special case?] If ITEM < INFO[START], then : Set LOC : = NULL, and Return.
3. Set SAVE : = START and PTR : = LINK[START]. [Initializes pointers]
4. Repeat Steps 5 and 6 while PTR != NULL.
5. If ITEM < INFO[PTR], then:
Set LOC : = SAVE, and Return.
[End of If structure]
[End of If structure]
6. Set SAVE : = PTR and PTR : = LINK[PTR]. [Updates Pointers]
[End of Step 4 loop]
7. Set LOC : = SAVE
DELLOCHL(INFO, LINK, START, AVAIL, ITEM)
1. [Use Procedure FINDBHL to find the location of N and its preceding node.]
Call LINDBHL(INFO, LINK, START, ITEM, LOC, LOCP).
2. If LOC = NULL, then : Write: ITEM not in list, and Exit.
3. Set LINK[LOCP] : = LINK[LOC]. [Deletes node.]
4. [Return deleted node to the AVAIL list.]
Set LINK[LOC] : = AVAIL and AVAIL : = LOC.
FINDBHL(INFO, LINK, START, ITEM, LOC, LOCP)
Procedure: FINDBHL(INFO, LINK, START, ITEM, LOC, LOCP)
1. Set SAVE : = START and PTR : = LINK[START]. [Initializes pointer].
2. Repeat while INFO[PTR] != ITEM and PTR != START.
Set SAVE : = PTR and PTR : = LINK[PTR]. [Updates Pointers]
[End of loop]
3. If INFO[PTR] = ITEM, then:
Set LOC : = PTR and LOCP : = SAVE.
Else:
Set LOC : = NULL and LOCP : = SAVE.
[End of If structure]
SRCHHL(INFO, LINK, START, ITEM, LOC)
1. Set PTR : = LINK[START]
2. Repeat while INFO[PTR] != ITEM and PTR != START:
Set PTR : = LINK[PTR]. [PTR now points to the next node]
[End of loop]
3. If INFO[PTR] = ITEM, then:
Set LOC : = PTR.
Else :
Set LOC : = NULL.
[End of structure.]
4.Exit
Traversing a Circular Header List
(Traversing a Circular Header List) Let LIST be a circular header list in memory. This algorithm traverses LIST, applying an operation PROCESS to each node of LIST.
1. Set PTR : = LINK[START]. [Initializes the pointer PTR]
2. Repeat Steps 3 and 4 while PTR != START
3. Apply PROCESS to INFO[PTR].
4. Set PTR : = LINK[PTR]. [PTR now points to the next node]
[End of Step 2 loop.]
Traversing a Circular Header List
(Traversing a Circular Header List) Let LIST be a circular header list in memory. This algorithm traverses LIST, applying an operation PROCESS to each node of LIST.
1. Set PTR : = LINK[START]. [Initializes the pointer PTR]
2. Repeat Steps 3 and 4 while PTR != START
3. Apply PROCESS to INFO[PTR].
4. Set PTR : = LINK[PTR]. [PTR now points to the next node]
[End of Step 2 loop.]
DELETION FROM A LINKED LIST
Let LIST be a linked list with a node N between nodes A and B
Suppose node N is to be deleted from the linked list.The schematic diagram of such a deletion appears.The deletion occurs as soon as the nextpointer field of node A is changed so that it points to node B.
Suppose our linked list is maintained in memory in the form
LIST(INFO, LINK, START, AVAIL)
When a node N is deleted from our list, we will immediately return its memory space to the AVAIL list.
1. The nextpointer field of node A now points to node B. where node N previously pointed.
2. The nextpointer field of N now points to the original first node in the free pool, where AVAIL previouly pointed.
DELETION FROM A LINKED LIST
Let LIST be a linked list with a node N between nodes A and B
Suppose node N is to be deleted from the linked list.The schematic diagram of such a deletion appears.The deletion occurs as soon as the nextpointer field of node A is changed so that it points to node B.
Suppose our linked list is maintained in memory in the form
LIST(INFO, LINK, START, AVAIL)
When a node N is deleted from our list, we will immediately return its memory space to the AVAIL list.
1. The nextpointer field of node A now points to node B. where node N previously pointed.
2. The nextpointer field of N now points to the original first node in the free pool, where AVAIL previouly pointed.
Inserting after a Given Node
1. [OVERFLOW?] If AVAIL = NULL, then: Write: OVERFLOW, and Exit.
2. [Remove first node from AVAIL list.]
3. Set INFO[NEW] : = ITEM. [Copies new data into new node.]
4. If LOC = NULL, then: [Insert as first node.]
Set LINK[NEW] : = START and START : = NEW.
Else: [Insert after node with location LOC.]
Set LINK[NEW] : = LINK[LOC] and LINK[LOC] : = NEW.
[End of If structure]
5.Exit.
Inserting after a Given Node
1. [OVERFLOW?] If AVAIL = NULL, then: Write: OVERFLOW, and Exit.
2. [Remove first node from AVAIL list.]
3. Set INFO[NEW] : = ITEM. [Copies new data into new node.]
4. If LOC = NULL, then: [Insert as first node.]
Set LINK[NEW] : = START and START : = NEW.
Else: [Insert after node with location LOC.]
Set LINK[NEW] : = LINK[LOC] and LINK[LOC] : = NEW.
[End of If structure]
5.Exit.
Sunday, March 20, 2016
Inserting at the Beginning of a List
Algorithm: INSFIRST(INFO, LINK, START, AVAIL, ITEM)
1. [OVERFLOW?] If AVAIL = NULL , then : Write: OVERFLOW, and Exit.
2. [Remove first node from AVAIL list. ]
Set NEW : = AVAIL and AVAIL : = LINK[AVAIL].
3. Set INFO[NEW] : = ITEM. [Copies new data into new node]
4. Set LINK[NEW] : = START. [New node now points to original first node.]
5. Set START : = NEW. [Changes START so it points to the new node]
6. Exit
Inserting at the Beginning of a List
Algorithm: INSFIRST(INFO, LINK, START, AVAIL, ITEM)
1. [OVERFLOW?] If AVAIL = NULL , then : Write: OVERFLOW, and Exit.
2. [Remove first node from AVAIL list. ]
Set NEW : = AVAIL and AVAIL : = LINK[AVAIL].
3. Set INFO[NEW] : = ITEM. [Copies new data into new node]
4. Set LINK[NEW] : = START. [New node now points to original first node.]
5. Set START : = NEW. [Changes START so it points to the new node]
6. Exit
Deleting the Node Following a Given Node
1. If LOCP = NULL, then:
Set START : = LINK[START]. [Deletes first node]
Else:
Set LINK[LOCP] : = LINK[LOC]. [Delete node N.]
[End of structure .]
2. [Return deleted node to the AVAIL list.]
Set LINK[LOC] : = AVAIL and AVAIL : = LOC
Deleting the Node Following a Given Node
1. If LOCP = NULL, then:
Set START : = LINK[START]. [Deletes first node]
Else:
Set LINK[LOCP] : = LINK[LOC]. [Delete node N.]
[End of structure .]
2. [Return deleted node to the AVAIL list.]
Set LINK[LOC] : = AVAIL and AVAIL : = LOC
Deleting the Node with a Given ITEM of Information
This algorithm deletes from a linked list the first node N which contains given ITEM of information.
1. [Use procedure FINDB to find the location of N and its preceding node.]
2. If LOC = NULL, then : write : ITEM not in list, and Exit.
3. [Delete node.]
If LOCP = NULL, then:
Set START : = LINK[START]. [Delete first node]
Else :
Set LINK[LOCP] : = LINK[LOC]
[End of structure]
4. [Return deleted node to the AVAIL list.]
Set LINK[LOC] : = AVAIL and AVAIL : = LOC.
5. Exit.
Deleting the Node with a Given ITEM of Information
1. [List empty?] If START = NULL, then:
Set LOC: = NULL and LOCP : = NULL, and Return.
[End of If Structure.]
2. [ITEM in first node?] If INFO[START] = ITEM, then:
Set LOC : = START and LOCP = NULL, and Return.
[End of IF Structure]
3. Set SAVE : = START and PTR : = LINK[START]. [Initialize Pointer]
4. Repeat Steps 5 and 6 while PTR != NULL.
5. If INFO[PTR] = ITEM, then:
Set LOC : = PTR and LOCP : = SAVE , and Return.
[End of If Structure]
6. Set SAVE : = PTR and PTR : = LINK[PTR]. [Update Pointer]
[End of Step 4 loop]
7. Set LOC : = NULL. [Search Unsuccessful]
8. Return.
Searching A LINK LIST
1. Set PTR: = START
2. Repeat Step 3 while PTR != NULL:
3. If ITEM < INFO[PTR], then:
Set PTR : = LINK[PTR]. [PTR now points to the next node.]
Else if ITEM = INFO[PTR], then:
Set LOC : = PTR, and Exit. [Search is successful.]
Else:
Set LOC : = NULL, and Exit. [ITEM now exceeds INFO[PTR].]
[End of If Structure]
[End of Step 2 loop]
4. Set LOC : = NULL.
Searching A Link List
1. Set PTR: = START
2. Repeat Step 3 while PTR != NULL:
3. If ITEM - INFO[PTR], then:
Set LOC : = PTR, and Exit.
Else:
Set PTR : = LINK[PTR]. [PTR now points to the next node.]
[End of If Structure]
[End of Step 2 loop]
4. [Search i unsuccessful] Set LOC : = NULL.
Friday, March 18, 2016
PATH LENGTH: HUFFMAN'S ALGORITHM
An extended binary tree or 2-tree is a binary tree T which each node has either 0 or 2 node children. The nodes with 0 children are called external nodes. and the nodes with 2 children are called internal code. A 2-tree where the internal nodes are denoted by circles and the external nodes are denoted by square. In any 2-tree, the number NE of external nodes is 1 more than the number N1 of internal nodes; that is,
NE = N1 + 1;
Example: 2-tree, N1 = 6 and NE = N1 + 1 = 7
LE = 2+2+3+4+4+3+3 and L1 = 0+1+1+2+3+2 = 9
Observe That L1 + 2n = 9+2.6 = 9+12 = 21 = LE
Where n = 6 is the number of internal nodes. Formula LE = L1
+ 2n LE = 2+2+3+4+4+3+3 and L1 = 0+1+1+2+3+2 = 9
Observe That L1 + 2n = 9+2.6 = 9+12 = 21 = LE
Where n = 6 is the number of internal nodes. Formula LE = L1
is true for any 2-tree with n internal nodes.
Suppose T is a 2-tree with n external nodes, and suppose each of the external nodes is assigned a weight. The weighted path length P of the tree T is defined to be the sum of weighted path length ; i.e,
P = W1L1 + W2L2 +..............+ WnLn
Where Wi and Li denote, respectively, the weight and path length of an external node Ni
Huffman's Algorithm
Huffman's Algorithm: Suppose w1 and w2 are two minimum weights among the n given weights w1, w2,..................,wn.Find a tree T Prime which gives a solution for the n - 1 weights
w1 + w2, w3, w4, ..........., wn
Then, in the tree T Prime , replace the external node
w 1 + w2 by the subtree
The new 2-tree T Prime is desired solution
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVEw1 + w2, w3, w4, ..........., wn
Then, in the tree T Prime , replace the external node
w 1 + w2 by the subtree
The new 2-tree T Prime is desired solution
COUNT(INFO, LINK, START, NUM)
1. Set NUM : = 0. [Initialize Counter]
2. Call Algorithm Traversing a Linked List, Replace the processing Step by:
Set NUM : = NUM +1.
Thursday, March 17, 2016
Procedure: COUNT(INFO, LINK, START, NUM)
1. Set NUM : = 0 . [Initializes Counter]
2. Set PTR : = START. [Initializes Pointer]
3. Repeat Steps 4 and 5 while PTR != NULL.
5. Set PTR : = LINK[PTR]. [Update pointer..]
[End of Step 3 Loop]
6. Return.
Procedure: PRINT(INFO, LINK, START)
1. Set PTR : = START .
2. Repeat Steps 3 and 4 while PTR != NULL.
3. Write: INFO[PTR]
4. Set PTR : = LINK[PTR]. [Update pointer..]
[End of Step 2 Loop]
5. Return.
Traversing a linked List
The variable PTR points to the node currently being processed.
1. Set PTR : = START . [Initialize pointer PTR]
2. Repeat Steps 3 and 4 while PTR != NULL.
3. Apply PROCESS to INFO[PTR]
4. Set PTR : = LINK[PTR]. [PTR now points to the next node.]
[End of Step 2 Loop]
5. Exit.
TRAVERSING A LINKED LIST
TRAVERSING A LINKED LIST: Let List be a linked list in memory stored in linear arrays INFO and LINK with START pointing to the first element and NULL indicating the end of LIST. Suppose we want to traverse LIST in order to process each node exactly once. This section presents an algorithm that does so and then uses the algorithm in some applications.
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE
Our traversing algorithm uses a pointer variable PTR which points to the node that is currently being processed. Accordingly, LINK[PTR] points to the next node to be processed.
PTR : = LINK[PTR]
Initialize PTR or START. Then process INFO[PTR], the information at the first node.
Update PTR by the assignment PTR : = LINK[PTR]
PTR points at the second node. Then process INFO[PTR], the information at the second node.
Update PTR by the assignment PTR : = LINK[PTR], and
Then process INFO[PTR], the information at the third node.
Continue until PTR = NULL, which signals the end of the list.
What is Header Linked List?
Header Linked List: A header linked list is a linked list which always contains a special node, called the header node, at the beginning of the list. The following are two kinds of widely used header lists:
(2) A circular header list is a header list where the last node points back to the header node.
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE
(1) A grounded header list is a header list where the last node contains the null pointer. (The term "grounded" comes from the fact that many texts use the electrical ground sysmbol to induicate the null pointer.)
POP_LINKSTACK(INFO, LINK, TOP, AVAIL, ITEM)
1. [Stack has an item to be removed?] If TOP = NULL, then Write:
UNDERFLOW AND Exit
2. Set ITEM : = INFO[TOP] [Copies the top element of STACK ITEM into ITEM]
3. Set TEMP : = TOP and TOP = LINK[TOP] [Remember the old value of the TOP pointer in TEMP and reset TOP to point to the next element in the stack]
4. [ Return Remove node from AVAIL list]
Set LINK[TEMP] = AVAIL and AVAIL = TEMP.
5. Exit.4. [ Return Remove node from AVAIL list]
Set LINK[TEMP] = AVAIL and AVAIL = TEMP.
Posts
