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.
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning...
Tuesday, March 22, 2016
Inserting into a Sorted Linked 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...
Deletion Algorithms
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...
COPY(INFO, LINK, NAME1, NAME2, AVAIL)
COPY(INFO, LINK, NAME1, NAME2, AVAIL)
This algorithm makes a copy of a list NAME1 using NAME2 as the list pointer variable of the new list.
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 : =...
Monday, March 21, 2016
Insertion Algorithms
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)
Algorithm: INSERT(INFO, LINK, START, AVAIL, ITEM)
This algorithm inserts ITEM into a sorted linked list.
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)
3. Exit
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOL...
FINDA(INFO, LINK, START, ITEM, LOC)
FINDA(INFO, LINK, START, ITEM, LOC)
This procedure finds the location LOC of the last node in a sorted list such that INFO[LOC] < ITEM, or sets LOC = NULL.
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 <...
DELLOCHL(INFO, LINK, START, AVAIL, ITEM)
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.
5. Exit.
If You want to learn about the technology, computer science & engineering, web...
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]
4. Exit.
If You want to learn about the technology, computer science & engineering,...
SRCHHL(INFO, LINK, START, ITEM, LOC)
Algorithm: SRCHHL(INFO, LINK, START, ITEM, LOC)
LIST is a circular header list in memory. This algorithm finds the location LOC of the node where ITEM first appears in LIST or sets LOC = NULL.
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
If You want to learn about...
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.]
5. Exit.
If You want to learn about the technology, computer science & engineering,...
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.]
5. Exit.
If You want to learn about the technology, computer science & engineering,...
DELETION FROM A LINKED LIST
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...
DELETION FROM A LINKED LIST
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...
Inserting after a Given Node
Algorithm: INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM)
This algorithm inserts ITEM so that ITEM follows the node with location LOC or inserts ITEM as the first node when LOC = NULL.
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.]
...
Inserting after a Given Node
Algorithm: INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM)
This algorithm inserts ITEM so that ITEM follows the node with location LOC or inserts ITEM as the first node when LOC = NULL.
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.]
...
Sunday, March 20, 2016
Inserting at the Beginning of a List
Algorithm: INSFIRST(INFO, LINK, START, AVAIL, ITEM)
This algorithm inserts ITEM as the first node in the list.
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. ...
Inserting at the Beginning of a List
Algorithm: INSFIRST(INFO, LINK, START, AVAIL, ITEM)
This algorithm inserts ITEM as the first node in the list.
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. ...
Deleting the Node Following a Given Node
Algorithm: DEL(INFO, LINK, START, AVAIL, LOC, LOCP)
This algorithm deletes the node N with location LOC, LOCP is the location of the node which precedes N or , where N is the first node, LOCP = NULL.
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. ...
Deleting the Node Following a Given Node
Algorithm: DEL(INFO, LINK, START, AVAIL, LOC, LOCP)
This algorithm deletes the node N with location LOC, LOCP is the location of the node which precedes N or , where N is the first node, LOCP = NULL.
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. ...
Deleting the Node with a Given ITEM of Information
Procedure: DELETE(INFO, LINK, START, AVAIL, ITEM)
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.]
Call FINDB(INFO, LINK, START, ITEM, LOC, LOCP)
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 :
...
Deleting the Node with a Given ITEM of Information
Procedure: FINDB(INFO, LINK, START, ITEM, LOC, LOCP)
This procedure finds the location LOC of the first node N which contains ITEM and the location LOCP of the node preceding N. If ITEM does not appear in the list, then the procedure sets LOC = NULL; and if ITEM appears in the first node, the it sets LOCP = NULL.
1. [List empty?] If START = NULL, then:
Set LOC: = NULL and LOCP : =...
Searching A LINK LIST
LIST Is Sorted:
Algorithm: SRCHSL(INFO, LINK, START, ITEM, LOC)
LIST
is a Sorted list in memory. This algorithm finds the location LOC of
the node where ITEM first appears in LIST, or sets LOC = NULL.
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...
Searching A Link List
LIST Is Unsorted:
Algorithm: SEARCH(INFO, LINK, START, ITEM, LOC)
LIST is a linked list in memory. This algorithm finds the location LOC of the node where ITEM fistn appears in LIST, or sets LOC = NULL.
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.]
...
Friday, March 18, 2016
PATH LENGTH: HUFFMAN'S ALGORITHM
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, ...
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 SO...
COUNT(INFO, LINK, START, NUM)
Procedure: 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.
3. Return.
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SO...
Thursday, March 17, 2016
Procedure: COUNT(INFO, LINK, START, NUM)
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.
4. Set NUM : = NUM + 1. [Increase NUM by 1]
5. Set PTR : = LINK[PTR]. [Update pointer..]
[End of Step 3 Loop]
6. Return.
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOL...
Procedure: PRINT(INFO, LINK, START)
Procedure: PRINT(INFO, LINK, START)
This procedure prints the information at each node of the list.
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.
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOL...
Traversing a linked List
Algorithm: (Traversing a linked List) Let LIST be a linked list in memory. This algorithm traverse LIST, applying an operation PROCESS to each element of 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.
If You want to learn about the...
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.
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.
...
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:
(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.)
(2) A circular header list is a header list where the last node points back to the header node.
If...
POP_LINKSTACK(INFO, LINK, TOP, AVAIL, ITEM)
POP_LINKSTACK(INFO, LINK, TOP, AVAIL, ITEM)
This procedure deletes the top element of a linked stack and assigns it to the variable ITEM.
1. [Stack has an item to be removed?] If TOP = NULL, then Write:
...
Posts
