Home / Algorithm

Data Structures and Algorithms - Hanoi College of Industry - 6

Input:

L // is a variable of type list containing a list

x /* is the search key and has a data type that matches the list's key field*/

Process:


Maybe you are interested!

Step 1: Consider the cases.

- If the list is empty ( Empty function ==1): Report empty list and return(-1)

Data Structures and Algorithms - Hanoi College of Industry - 6

- If the list is not empty, go to step 2.

Step 2: Search.

- Compare the search key x with the key field value of

each element in the list, starting from the first element until it is found or the end of the list is reached.

- If found return (pos: element position)

- If not found return (-1).

Output: pos: The position of the element whose key field value matches x or -1 if not found.

Algorithm installation

int searchElement (list L, key field type x)

{

int i=0;

if (Empty (L))

{


}

else

printf("Empty list!"); return(-1);

{ while ((L.element [i].key field==x) && (i<L.count)) i++;

if (i<L.count)

return (i);

else


}

}


return(-1);

e. Insert (add) a new element to the list.

New elements can be added at the following positions: First, inside or last of the list.

To make room to add a new element, we must move the elements from the pos position to the end of the list to add the new element.

 Algorithm:

Input:

L // is a pointer of type list

pos // contains the position to insert

x // is a variable of type Item and contains the new element value

Process:

Step 1: Consider the cases:

- If the list is full (function Full ==1):

Full and end list notification.

- If pos position is invalid (pos<0 or pos>=maxlist) Invalid position message and end

- If the list is not full and the pos position is valid, go to step 2.

Step 2: Insert new element.

- Move elements from position pos to the end of the list.

- Insert new element at correct position pos.

- Increase the count variable value by one.

Output: New element x has been inserted at position pos in the list if the conditions are satisfied.

 Algorithm installation

void insertElement (list *L, int pos, Item x)

{

int i;

if (Full (*L))

printf("List here!");

else


if ((pos <0) || ( pos>= maxlist))

printf("n The insertion is not correct"); else. else

{

for (i=L->count;i>=pos;i--)

L-> element [i+1]= L-> element [i]; L-> element [pos]=x;

L->count++;

}

}

f. Delete (remove) an element from the list.

The deleted element can be at the beginning, inside or end of the list.

book.

To delete an element, we just need to move the elements from the end of the list.

back up to pos position.

 Algorithm:

Input:

L // is a pointer of type list

pos // contains the position to insert

x // is a variable of type Item and contains the value of the deleted element

Process:

Step 1: Consider the cases

- If the list is empty ( Empty function ==1): Report empty list and end

- If pos position is invalid (pos<0 or pos>maxlist) Invalid position message and end

- If the list is not empty and the pos position is valid, go to step 2.

Step 2: Delete the element and put the value of this element into variable x.

- Put the value of element pos into variable x.

- Move elements from the end of the list to the top

position

- Decrease the value of the count variable by one.

Output: The element pos is removed and x is the value of the element pos in the list if the conditions are met.

 Algorithm installation.

void deleteElement (list *L, int pos, Item *x)

{

int i;

if (Empty (*L))

printf("List is empty!");

else


if ((pos <0) || ( pos>= maxlist))

printf("n Erase position does not match!"); else

{ *x=L-> element [pos];

for (i=pos;i<L->count;i++)

L-> element [i]= L-> element [i+1]; L->count++;

}

}

g. Sort the elements in the list.

To sort the elements in a list, we must rely on the value of a key field of the element.

The sorting algorithm is performed by comparing the value of the sorting key field of 2 elements (element i with element j), if the sorting order is not correct, then swap the two elements.

 Algorithm: Input:

- L is a list to be sorted in ascending order of the Key field.

- count is the number of elements in the list L. Process:

Repeat the following work from index i=0 to index i=count-2

Repeat the following work from index j=i+1 to the last index j=count-1

- Compare the key field of element Li with Lj.

- If the key field value Li>Lj then swap the positions of elements Li and Lj.

Output: L is a list sorted in the forward direction of the key field (ascending direction for numbers, lexicographical direction for strings).

 Implement the algorithm. void sortList( list *L )

{ int i, j, temp;

for ( i=0; i<L->count-1;i++)

for ( j=i+1;j< L->count ;j++)

//sort in ascending order

if (L->Element[i].key field>L->Element[j].key field)

{ temp= L->Element[i];

L->element[i]= L->element[j]; L->element[j]=temp ;

}

}

h. Student score management program.

#include <stdio.h>

#include <conio.h>

#include <string.h> const int maxlist=100;

//define Student structure

Student structure

{ char masv[10]; char Hten[35];

float LaptrinhCB, KientrucMT, MangMT, DiemTB;

};

//Define list structure typedef SinhVien Item; typedef struct list

{ Item element[maxlist]; int count;

};

// function to create a large list

void initializeList(list *L)

{

L->count=0;

}

// function to check if the list is large?

int EmptyList(list L)

{

return (L.count==0);

}

// function to check if the list is large?

int FullList(list L)

{

return (L.count== maxlist);

}

//function to search for students by masv

int searchElement (list L, char x[])

{

int i=0;

while (i<L.count)

if (stricmp(x,L.element[i].masv)==0) return(i);

else


return(-1);

}


i++;

//function to add a new student to the list

void insertElement (list *L, int pos, Item x)

{

int i;

if (FullList (*L))

printf("List here!");

else

if ((pos <0) || ( pos>= maxlist))

printf("n The insertion is not correct"); else. else

{

for (i=L->count;i>=pos;i--)

L-> element [i+1]= L-> element [i]; L-> element [pos]=x;

L->count++;

}

}

//function to delete a student from the list

void deleteElement (list *L, int pos, Item *x)

{

int i;

if (EmptyList (*L))

printf("List is empty!");

else


if ((pos <0) || ( pos>= maxlist))

printf("n Erase position does not match!");

else

{ *x=L-> element [pos];

for (i=pos;i<L->count;i++)

L-> element [i]= L-> element [i+1]; L->count--;

}

}

//sort by name

void sortListHten(list *L)

{ int i, j; Student temp;

for ( i=0; i<L->count-1;i++) for ( j=i+1;j< L->count ;j++)

if (stricmp(L->element[i].Hten,L->element[j].Hten)>0)

{ temp=L->element[i];

L->element[i]= L->element[j]; L->element[j]=temp ;

}

}

//sort by average score

void sortListDTB(list *L)

{ int i, j; Student temp;

for ( i=0; i<L->count-1;i++)

for ( j=i+1;j< L->count ;j++)

if (L->element[i].DiemTB<L->element[j].DiemTB)

{ temp=L->element[i];

L->element[i]= L->element[j]; L->element[j]=temp ;

}

}

// enter student information

void NhapSinhVien (Student *p)

{ float f;

char ht[35],ma[10];

fflush(stdin); //relaxing the night view of the movie printf("n students: "); gets(ma);strcpy(p->masv,ma); fflush(stdin);

printf("n Name: "); gets(ht);strcpy(p->Hten,ht);

//Enter scores for students

printf("CB's Lap Point: "); scanf("%f",&f); p->LaptrinhCB=f; printf("MT structure: "); scanf("%f",&f); p->KientrucMT=f; printf("Diem Carry MT: "); scanf("%f",&f); p->MangMT=f;

//Calculate average score

(*p).DiemTB=( p-> LaptrinhCB+ p-> KientrucMT+ p-> MangMT )/3;

}

//Define a function to display information about a student record

void Student

{

printf ("n Student Code %10s", sv.masv); printf ("n Student Name %35s", sv.Hten);

printf ("n Lap Point of CB: %4.1f", sv.LaptrinhCB); printf ("n MT structure parameter: %4.1f", sv.KientrucMT); printf ("n Number of MT : %4.1f", sv.MangMT);

printf ("n Average score : %4.1f", sv. Average score); getch();

}

// function to create student list

void CreateList(list *L)

{ int i=0; char kt; Item sv;

by

{ printf("enter element %d:",i+1); EnterStudent(&sv); L->element[i]=sv;

L->count++;i++;

printf("Can you continue typing? "); fflush(stdin);kt=getchar();

Comment


Agree Privacy Policy *