Algorithms and Data Structures

Exercise 0 : (pointers as arrays and their arithmetics)

Write a program that reads two arrays of integers A and B and their dimensions N and M on the keyboard and adds the elements of B to the end of A. Use two pointers PA and PB for the transfer and display the resulting array A.

Solution

Exercise 1 : (simply linked lists)

We are now proposing a new chained list structure, which is:
Track the list of products purchased by a customer at a convenience store

Each item in the list consists of the following fields:
code_prod(9 alphanumeric),
Designation(50 car),
UM (3 cars), // Unit of measurement (U, Kg, L, end, cart, …)
PUA_HT(actual), // unit purchase price excluding tax
Qty(actual), // Quantity purchased
VAT (9% or 21%) // Value Added Tax

This program will display the following menu:

1. ADD Products At the top of the list
2. VIEW the list of products purchased
3. Display the total number of products purchased as well as the total amounts excluded taxes, total VAT and total TTC (net to be paid).
4. Ask the customer for payment and calculate the difference between the amount paid and the net amount to be paid.
5. DELETE products
6. Show max and min price
7. EMPTY the list.
8. STOPPING the program.

And will carry out the processing (functions/procedures) corresponding to the choice made.

Solution

Exo1-serie2

---

Exercise 2 : (backchaining double linked lists)

Design an algorithm that performs backchaining of a double-chained list that has only fronted chaining (with taking the possibility of a circular list)

Solution

Exo2-serie2

---

Exercise 3 : (backchaining double linked lists)

Insert and delete in a double linked list :

• Write an algorithm for inserting into a double-linked list.
• Write a deletion algorithm in a double-linked list.

Solution

Exo3-serie2

---

Exercise 4 : (backchaining double linked lists)

The department you’re enrolled in wants to manage their students’ grades. Students have their student number as their identifier. They have a first and last name. This information is stored in a linked list, each item of which also has an average field for the student’s average and an eval field that is a pointer to the student’s grade list. Each student’s grade list is also a linked list with the eval field of the student’s cell at its head. The following statements are available:

Student = Structure
No: Ch10
Name: Ch30
First name: Ch30
Avg: Nb
eval: Pn
next: Pe

Rating = Structure
note: Nb
coeff : Ent
next: Pn

Types :
Ch10 = 10-character string
Ch30 = 30 character string
Ent = integer
Nb = real
Pe = *Student
Pn = *Note

Questions:

Make a diagram of this structure.

Assume that all fields in the student list are filled in except for the avg field. It is assumed that all student grades and coefficients are filled.

Write a student averages procedure that goes through the list of students, and calculates and updates each student’s average field using the grade list that the eval field points to. The averageStudents procedure takes the top of the student list as a parameter.

Solution

Exo4-serie2

---

Exercise 4 : (circular double linked lists)

Implement a circular doubly linked list in C++. The list must allow the following operations:

1. Add an item to the end of the list.
2. Remove an item from the list.
3. View all items in the list.
4. Search for an item in the list.
   

Solution

Exo5-serie2