Data Structure and Algorithms

Tasks:

Introduction:

Using file handling with structure, a complex problem can be solved using the C programming language. But, at the time of growing data size; file size also increases. This can lead to excessive usage of memory. It also creates time and space complexity. So, in the case of growing data size, the file handling feature is fully inappropriate

In that case, the dynamic memory allocation technique is needed. So, when the data size increases, the dynamic memory allocation strategy using Link List is very much required to solve complex problems.

(a)

To design a library system for Kent Institute; the system can be divided into various modules like insert books, delete a particular book, search a specific book, view books according to ISBN code, issue a book and edit the record of a book.

Creating a book; the variables are chosen as, ISBN_code, title, author, category, price, quantity,date_receive, rackNo, issue. The different data types and ranges for the variables are:

Int ISBN_CODE; - It is a unique number

Char title [30] – It denotes the title of the Book so that it may be a maximum of 30 characters long.

Char author [30] - It represents the name of the Author for the book and can be a maximum of 30 characters long.

Char category [20]- It represents the book’s category like Literature, Engineering, Science,Comics, Story, etc.

Float price- It denotes the price for the book

Int quantity- It determines the quantity of the particular book.

Char date_receive[8]- It defines the date in dd/mm/yy format in which the datebook is received.

Int RackNo- It defines the particular Rack Number where the book is located.

Char issue- It defines whether the particular book is issued or not. Its value is ‘N' by default. When any book is issued, then it is updated as ‘Y.'

o implement the system in C programming using structure; the above variables, data types and ranges are the most appropriate option. The primary data types are chosen for the following causes,

The integer data type is chosen for ISBN_code, quantity and RackNo because these numbers are used without fractions. These are chosen as an unsigned integer as all are positive values.
The float data type is chosen for the price of a book because the book's value can be real numbers. In this system, up to 2 decimal places are considered and denoted as ‘%0.2f'.
Char data type is used for string, as C language cannot support string data type. The variables for the title, author, category and date_receive are chosen as a string data type.A maximum range is chosen after char [] for each variable
Single char for issue field is chosen as ‘Y' or ‘N.' As there is no Boolean data type in C language.

The derived data types for the system are chosen as, array, structure and pointer. The data types and variables are used for the efficient utilization of memory. Each data type has a specific memory size in the C programming language. The smallest data type(s) and range(s) are chosen to match the type of appropriate data.

To control the system, appropriate keys are,
Case 1: insert_books()
Case 2: delete_book()
Case 3: search_book()
Case 4: View-sorted-book ()
Case 5: Issue-book()
Case 6: Edit_book()

(b)

The various operations for the system can be divided as below,

Insert_ books () - This function displays various categories of books. After opening the file pointer and assigning the pointer to the end of the file; the user chooses a particular category and scans all records about a particular book from that category by the user.Then this record is appended at the end of the file.

Delete_book()- This functions accepts ISBN_code of a particular book from user. After opening the file pointer, it assigns to the beginning of the file. The ISBN_code is searched with records of the file's ISBN_code up to the end of the file. If the user's code is not matched, then message display as "Book is not found." If the record is matched, then all records are copied to another file except file pointer points that matched record. Then, the previous file is deleted and a new file is renamed as the previous one.

Search_book()- This function takes ISBN from the user and opens the file pointer. After placing the file pointer at the beginning of the file, all records (ISBN) are searched with the user's ISBN from top to end of the file. This algorithm uses a linear search technique. After finding the record, the message is displayed otherwise message "Book is not found”is displayed

View-sorted-book ()- Using a simple Mergesort algorithm, the file would be sorted according to ISBN_code. After partitioning the file into f1 and f2; reading a block from each file. After taking the 1st record from each block and write those in sorted order in a new file named m1. This process is repeated from each block but writes into another file called m2. This process continues until f1 and f2 complete reading. So, m1 and m2 store ordered a pair of records. The above process is repeated and finally getting merge pair of records. At last, sorted records of length four is achieved. Two new files, m1 and m2, are merged into m to get the sorted records

 Issue-book()- This process scans ISBN_code from user. Assign the pointer to the top of the file named, m (sorted records). The searching process continues up to end of the file using binary search technique. When the user's ISBN matches with file m's ISBN then accepts student's information and writes it into another file. The issue field of book structure is updated as ‘Y.' If the ISBN is not matched, then it displays the message "Sorry, that book is not available."

Edit_book()- This function accepts ISBN_code from user. After opening the file pointer and placing it into the m (sorted) file; the searching process begins using the Binary search technique to match the user's ISBN with m file's ISBN. If the record matches; accepts other file information like title, author, category, price, quantity, date_receive, RackNo, etc. from the user. In the current position of the file pointer, this record is overwritten. If the user’s ISBN is not found then an error message “Sorry Book is not found” is displayed. At last, close the file (Kanetkar, 2017).

(c)

Algorithm for Insert_ books ()

Step 1: file pointer declaration as FP

Step 2: various categories displayed

Step 3: User choices a category

Step 4: fp, the file pointer is opened in write mode

Step 5: fp is placed at the end of the file

Step 6: Scans all information of a book about particular category from user

Step 7: writes info into the end of the file

Step 8: closes fp

This algorithm is very efficient for time and space because records are inserted at the end of the file. There is no traversing of file pointer otherwise it is assigned at the end of the file.

Algorithm for Delete_book()-

1. Scans ISBN from the user for deleting a book
2. The file pointer is declared as fp1
3. Open file pointer fp as reading mode
4. Assigns fp beginning of the file
5. Searching each record’s ISBN with user’s ISBN using a linear search algorithm
6. Loop continues until the end of file
7. If a user's ISBN =file's ISBN
8. Open fp1
9. Copy all records of fp to fp1 except a current record of fp
10. Delete fp file and rename the fp1 as fp
11. If a record is not found, a suitable message is displayed.
12. Close fp

This algorithm first searches the particular book from file whether it is present or not. If the record is present, then that particular record is deleted. Here, the searching process is done as per the linear search algorithm because the records are not in sorted order. So, in this case, the time complexity is larger if the record is at the end of the file.

Algorithm for Search_book()

1. Displays option a.) search book by ISBN b)search book by title
2. The user chooses an option (a) or (b)
3. Open the file pointer, fp
4. Assigns fp at the starting position of the file as reading mode
5. If option (a) is chosen
6. Searching ISBN = file’s code
7. Otherwise searching title=file’s title
8. Traversing fp up to end of the file
9. If the record is found then displays "Record Found "and breaks from loop
10. If the record is not found for option (a) or (b) then displays "Sorry, the record is not found
11. Close the fp

As the records are stored into the file sequentially, then records are not in sorted order. So, this algorithm follows a linear searching technique. In case the record is found at the beginning of the file, the time complexity is smaller, the middle of the file, the time complexity is middle; otherwise, the time complexity will be larger.

Algorithm View-sorted-book ():

1. Assign an fp to the beginning of a file in reading mode
2. Assigns two file pointer fp1 and fp2 in write mode
3. Traverse the fp up to the end of the file to count the number of records.
4. Store the number of records into a variable, count
5. Reads first count/2 records and writes into fp1 file
6. Reads another half records and writes into fp2 file
7. Read a block from fp1 and fp2
8. Opens m1 and m2 as write mode
9. Read the first record from each block and writes into sorted way as m1
10. Repeats step 9 but write the sorted way into m2.
11. Repeats from step 7 to 10 until the end of the file, fp1 and fp2 reached.
12. Two files m1 and m2 are achieved as two different sorted file
13. The two files m1 and m2 are sorted and merged as m.
14. Closes fp1, fp2, m1 and m2

This algorithm is chosen as the Merge sort technique. From various sorting algorithms, this technique is chosen for the following causes,

This algorithm is the best efficient for handling records within the text file.
The records are sorted according to keys but not full records. Here, the records are sorted as ISBN.
For larger file sizes; this algorithm has the same consistent speed.
This algorithm is treated as external sorting as well as highly parallelizable.
This algorithm is treated as external sorting as well as highly parallelizable.

Algorithm for Issue-book ()

1. Open the file pointer, fp
1. Open the file pointer, fp
2. Assigns fp at the starting of the file, m(sorted file) as read mode
3. Accepts ISBN from user
4. Searching records as binary search process until the end of the file
5. If user’s ISBN= m’s ISBN then
6. Accepts student’s information
7. Assign another file pointer, ffp as write
8. Write student’s info into ffp and closes ffp.
9. Update the current record of fp's issue as ‘Y.'
10. Close fp

Binary_search() algorithm

1. Assigns fp at the beginning of the file as read mode
2. Assign count=0
3. Traverse fp until end of the file
4. After traversing each record, count+=1
5. Total number of records as count
6. Closes fp and again opens as well as assigns it to start of the file as read mode
7. Assign max=count-1 and min=0
8. Until max >= min then
9. pos=(max+min)/2
10. If (fp[pos]==user’s ISBN) then record found and its position is, pos and returns
11. Else If (fp[pos]>user’s ISBN) then max=pos-1 else min=pos+1
12. Goto step 8
13. Display message "record not found."

In this case, the binary search algorithm is followed as the records of the file are previously sorted and stored into m file.

This algorithm is faster than the linear search technique. When the records of the file are large,then this algorithm is very much efficient than linear search, but records should be in sorted order.

Algorithm for Edit_book()

1. Open the file pointer, fp
2. Assigns fp at the starting of the file, m(sorted file) as read mode
3. Accepts ISBN from user
4. Searching records as binary search process until the end of the file
5. If user’s ISBN= m’s ISBN then
6. Accepts other info about Book like title, author, price, quantity, receive_date, etc
7. Overwrite record of current fp by new data
8. Closes fp
9. If record not found then displays a message as "Book is not found" (Balagurusamy, 2018)(Yadav, 2015).

(d)

The above system is implemented using File handling with structure. But, in the case of large data; efficient file handling is very complex, Storing, editing, retrieving, updating, searching and sorting procedures will be very complex in text files for a large amount of data. Operations will be complex and require lots of memory spaces during operations like deleting the previous file and renaming the new file, etc.

So, I recommend that the Link list implementation will be the best way for a large amount of data. For handling large data of the University; the link list is chosen in the following reasons,

1. The link list is a dynamic data structure. Its size can shrink or grow as per needs during program execution. So, when library books are increased its size also increased as per requirements.
2. Memory space is efficiently utilized here. Memory space is allocated at the time of requirement during the execution of the program as well as de-allocated when it is no longer needed.
3. Insertion, deletion, searching, sorting, updating and editing of a node can be easily done in Link List implementation. Each node contains records of books and points to another record. Even to insert a particular book at a specified position is also possible using this data structure.
4. This data structure also allows merge sort and binary search techniques easily (Lipschutz,2018) (Karuna & Gupta, 2014)

Conclusion:

This system first implements the University Library Information system using file handling feature in C programming where Book record is considered within a structure. When a large University is considered where lots of data handling is needed, then this system is fully inappropriate.

In that case, the dynamic memory allocation procedure is taken into consideration. After taking the Link List concept, this problem is easily resolved where Book is taken as a node for the Link List.

References:

Books:

Balagurusamy. E 2018, Programming in ANSI C, the Tata McGraw-Hill Companies, New York Kanetkar. Y 2017, Let Us C, BPB Publications, Kolkata

Lipschutz .S 2018, Data Structures, the Tata McGraw-Hill Companies, New York

Journal Articles:

Karuna & Gupta G 2014, “Dynamic Implementation using Linked List.”, IJERMT, vol.1,no.5., pp.44-48.

Yadav K 2015, "Data File Handling in C++," IJIRT, Vol. 2, no.6, pp.326-329

Download full sample