Algorithm for Adding and Removing a Node in a Circular Link:

Suppose polynomials A(x), B(x) will be represented by 2 singly linked lists pointed by A and B respectively.

Problem: Create a third linked list pointed by C to represent the polynomial:

C(x) = A(x) + B(x)

First, we write a procedure to add a node to the end of list C with the coefficient field XX and the exponent field YY. Suppose list C has the last node

is pointed by R.

CR

...........

.

void Ghep(C, R, XX, YY)//C:value,R:variable

1. Tam=new Nut; Tam->Heso=XX; Tam->Mu=YY;

Tam->Next=NULL;

2. R->Next=Tam;

R=Tam;

return;

void Formula(A, B, C)//A,B:value,C:variable

1. C=new Nut;

R=C;

p=A; q=B;

2. while ((p!=NULL) && (q!=NULL)) if (p->Mu==q->Mu)

{

XX=p->Heso+q->Heso;

if (XX!=0) Match(C, R, XX, p->Mu);

p=p->Next; q=q->Next;

}

else if (p->Mu < q->Mu)

{

}

else

{

}

Match(C, R, q->Heso, q->Mu); q=q->Tiep;

Merge(C, R, p->Heso, p->Mu); p=p->Next;

3. while (q!=NULL)

{

Match(C, R, q->Heso, q->Mu); q=q->Tiep;

}

while (p!=NULL)

{

Merge(C, R, p->Heso, p->Mu); p=p->Next;

}

Tam=C;

C=C->Next; delete Tam;

return;

5.5. Stack and Queue connection:‌

For Stack, access is always done at one end so implementing a list using Stack links is quite natural. For example, with a singly linked list with the first node pointed to by First, we can consider First as the top of the Stack.

Adding an element to the Stack is the same as adding a node to the list so that it becomes the first node in the list. Removing an element from the list

The book is the elimination

element

first. For the linked list, we

No need to check for Stack overflow because Stack using linked list is not limited in size like using array (but only limited by total memory).

 Procedure to insert an element at the beginning of the list:

void Push(&First, X)//First:parameter p=new Nut;

p->Info=X;

p->Next=First;

First=p;

return;

 Procedure to get the element at the beginning of the list:

void Pop(&First, &X)//First:parameter if (First==NULL)

{

cout << “Stack empty”; return;

}

X=First->Info; p=First; First=First->Tiep; delete p;

return;

For Queue, using linked list also follows the same method.

But if using a single linked list, 2 pointer variables First and Last are needed.

Adding an element to the Queue is adding an element immediately after Last. And removing an element from the Queue is removing the first element (First).

 Procedure to insert an element at the beginning of the list:

void Insert_Queue(&First, &Last, X) //First,Last:parameter p=new Nut;

p->Info=X;

p->Next=NULL;

if (Last==NULL) First=Last=p; else. else

{

Last->Next=p;

Last=p;

}

return;

 Function to delete elements on Queue: same as Pop procedure above.

Exercise (Practice 2):

Create dictionary: There is a menu that does the following:

1) Initialize TD dictionary from TD.DAT file:

Read the TD.DAT file as text (this file already contains words with a maximum of 7 characters). Each word has only characters in the set ['A'....'Z']. The words in the file are sorted in ABC order) and save these words into an array of linked lists. Specifically:

can: Nut * TD[26]; //save 26 lists of corresponding letters

the['A'..'Z']

In which, the Nut type is declared as follows:

Structural Nut

{

char Tu[7];

Nut *Next;

}

OLDER BROTHER

For example: TD.DAT file has 3 words: ANH, BAN, BONG.

TD[0]

BOARD

BONG

TD[1]

TD[2],..., TD[25] are all NULL.

Note: If this file does not exist, then all elements of the array are NULL.

2) List all the words in the TD:

Type in a character, then display all words whose first character is the typed character.

3) Add a word:

Type a word from the keyboard. If the word is not in the dictionary, add it to the dictionary. Otherwise, it will say: “This word already exists in the dictionary.”

4) Delete a word:

From the keyboard, type a word. If the word is in the TD, delete it from the TD, otherwise

otherwise it says: “This word is not found in TD”.

5) Update dictionary from a text file:

Read any text file containing words (a word is defined as consecutive characters in the set ['A'...'Z']) the remaining characters are considered delimiters). For each word read in this text file, do the following: If the word is not found in the TD, insert it in the appropriate position.

6) Save TD to TD.DAT file.

CHAPTER 6: TREE

6.1. Definitions and concepts:‌‌‌

6.1.1. Definition:

A node is a tree. It is also the root of this tree.

If n is a node and T1, T2,..., Tk are k trees with roots n1, n2,..., nk then a new tree will be formed by making node n the parent of n1, n2,...,nk (called the children of root n).

n

…

n

n1 n2

…

T1 T2 Tk

+

Origin

+

/

x

*

u

v

y

z

­

df df g

t

6.1.2. Related concepts:‌

a. Degree level:

The degree of a node is the number of subtrees of that node. Thus, a node with degree 0 is called a leaf, otherwise it is called a branch.

The level of a tree is the highest level of nodes in the tree.