Data Structures using C

A Practical Approach for Beginners

Amol M. Jagtap, Ajit S. Mali

• Publisher: Chapman and Hall/CRC
• Year: 2021
• ISBN:
  9781000470741
• Edition: 1
• Topic: Computer Science
• Subtopic: Programming Algorithms
• Index: Computer Science

The data structure is a set of specially organized data elements and functions, which are defined to store, retrieve, remove and search for individual data elements. Data Structures using C: A Practical Approach for Beginners covers all issues related to the amount of storage needed, the amount of time required to process the data, data representation of the primary memory and operations carried out with such data. Data Structures using C: A Practical Approach for Beginners book will help students learn data structure and algorithms in a focused way.

• Resolves linear and nonlinear data structures in C language using the algorithm, diagrammatically and its time and space complexity analysis

• 
  
  

• Covers interview questions and MCQs on all topics of campus readiness

• 
  
  

• Identifies possible solutions to each problem

• 
  
  

• Includes real-life and computational applications of linear and nonlinear data structures

• 
  
  

This book is primarily aimed at undergraduates and graduates of computer science and information technology. Students of all engineering disciplines will also find this book useful.

1 Fundamental Principles of Algorithm and Recursion

DOI: 10.1201/9781003105800-1

1.1 Algorithm, Its Pseudo-Code Representation and FlowChart

1.1.1 Algorithm Definition

An algorithm is a step-by-step procedure for solving a problem. A sequential solution to any program that is scripted in any natural language is called as an algorithm. The algorithm is the first step of the solving process. After the problem analysis, the developer writes the algorithm for this problem. It is largely used for data processing, computing and other related computer and mathematical operations.

The algorithm must satisfy the following five conditions:

1. Input: Zero, one or more quantities are externally provided.
2. Output: The algorithm produces at least one output as a result.
3. Definiteness: Each statement must be clear, specific, and unambiguous.
4. Finite: The algorithm should conclude after a limited number of steps.
5. Effectiveness: Every statement must be very fundamental so that it can be carried out by any individual using only paper and pencil.

1.1.2 Pseudo-Code Representation

The word “pseudo” means “fake,” so “pseudo-code” means “fake code”. Pseudo-code is an informal language used by programmers to develop algorithms. Pseudo-code describes how you would implement an algorithm without getting into syntactical details. It uses the structural conventions of a formal programming language but is proposed for human reading rather than machine reading. It is used to create an overview or outline of a program. System designers write pseudo-code to make sure the programmer understands a software project’s requirements and aligns the code accordingly. The pseudo-code contains no variable declaration.

The pseudo-code follows certain standard loop structures as follows:

1. FOR… ENDFOR
2. WHILE… ENDWHILE

Certain terms also exist for standard conditional clauses:

1. IF… ENDIF
2. WHILE… ENDWHILE (this is both a loop and a conditional clause by the way)
3. CASE… ENDCASE

The pseudo-code cannot be compiled within an executable program.

Example in C code:

if (I < 10) { I++; }

Therefore, its respective pseudo-code is:

If I is less than 10, increment I by 1.

Benefits of pseudo-code:

1. Pseudo-code is understood by every programming language developer like Java or C#. Net developer, etc.
2. Programming languages are difficult to read for most people, but pseudo-code permits non-programmers, such as business analysts, end user or customer to review the steps to approve the projected pseudo-code that matches the coding specifications.
3. By drafting the code in human language first, the programmer protects from omitting an important step.

Example 1.1: Algorithm for Identifying the Area of a Triangle

1. Step 1: Start
2. Step 2: Take input as the base and the height of the user
3. Step 3: Area = (base * height)/2
4. Step 4: Print area of triangle
5. Step 5: Stop.

Example 1.2: An Algorithm Used to Determine Number Is Odd or Even

1. Step 1: Start
2. Step 2: Enter any input number
3. Step 3: Reminder = number mod 2
4. Step 4: If reminder = 0, then

    Print "number is even" Else Print "number is odd" End if 

5. Step 5: Stop.

1.1.3 Flowchart

The graphical representation of any program is referred to as flowcharts. A flowchart is a kind of diagram that represents an algorithmic program, a workflow or operations. A flowchart aims to provide people with a common language to understand a project or process. Developers often use it as a program-planning tool for troubleshooting a problem. Each flowchart provides the solution to a specific problem. There are a few standard graphics symbols, which are used in the flowchart as follows:

1. Start and Stop or Terminal
   The circular rectangles or oval symbol indicates where the flowchart starts and ends.
2. Input and Output
   The parallelogram symbol denotes input or output operations in the flowchart.
3. Process or Instruction
   The rectangle represents a process like computations, a mathematical operation or a variable assignment operation, etc.
4. Arrows or Direction of Flow
   Arrows or direction of flow represents the flow of the sequence of steps and direction of a process.
5. Question or Decision
   The diamond symbol is used as a representation of the true or false statement tested in a decision symbol.
6. Connector
   A flowchart is divided into two or more smaller flowcharts, consistent with project requirements. This connector is most often used when a flowchart does not fit on a single page or has to be split into sections. A connector symbol, which is a small circle called an On-Page Connector, with a number inside it, allows you to connect two flowcharts on the same page.
   A connector symbol that looks like a pocket on a shirt, called off-page connector allows you to connect to a flow diagram on another page.

Guidelines for developing flowcharts:

Here are a couple of things to keep in mind when designing and developing a flowchart:

1. The arrows should not intersect during the design of a flowchart.
2. Processes or activities take place from top to bottom or from left to right in general.
3. The on-page connectors are referenced using digits in general.
4. Off-page connectors are referenced using alphabets generally.
5. The flowchart may have only one beginning symbol and a one-stop symbol.
6. The shapes, lines and texts of a flowchart need to be consistent.

Pros and cons of flowcharts:

Advantages of flowchart:

1. Flowcharts are one of the best ways of documenting programs.
2. Flowcharts are easier to understand compared to algorithms and pseudo-codes.
3. It helps us to debug and analyze processes.
4. It helps us understand how to think or make decisions to formulate the problem.

Disadvantages of flowchart:

1. Manual tracking is needed to verify the accuracy of the paper flowchart.
2. Modification of the flowchart is sometimes time-consuming.
3. It is difficult to display numerous branches and create loops in the flowchart.
4. A simple modification of the problem logic can result in a complete redesign of the flowchart.
5. It is very difficult to draw a flowchart for huge and complicated programs.

Example: Draw a flowchart to find area of triangle and odd or even number:

1.2 Abstract Data Type

Abstract data type (ADT) is a type or class of objects whose behavior is determined by a set of values and a set of functions. The definition of ADT only refers to the transactions that need to be performed, but not the way these transactions will be implemented. It does not specify how the data will be organized in memory and what algorithms will be used for the implementation of those operations. It is called “abstract” because it provides an independent perspective from the implementation. The process of supplying only the essentials and concealing details is known as abstraction.

The programmer who has used the data type may not know that how data type is implemented...