Practical C Programming

Solutions for modern C developers to create efficient and well-structured programs

B.M. Harwani

• Éditeur: Packt Publishing
• Année: 2020
• ISBN:
  9781838647988
• Édition: 1
• Sujet: Computer Science
• Sous-sujet: Programming

A comprehensive guide with practical instructions for learning data structures, low-level programming, high-performance computing, networking and IoT to help you understand the latest standards in C programming such as C11 and C18

Key Features

• Tackle various challenges in C programming by making the most of its latest features
• Understand the workings of arrays, strings, functions, pointers, advanced data structures, and algorithms
• Become well-versed with process synchronization during multitasking and server-client process communication

Book Description

Used in everything from microcontrollers to operating systems, C is a popular programming language among developers because of its flexibility and versatility. This book helps you get hands-on with various tasks, covering the fundamental as well as complex C programming concepts that are essential for making real-life applications.

You'll start with recipes for arrays, strings, user-defined functions, and pre-processing directives. Once you're familiar with the basic features, you'll gradually move on to learning pointers, file handling, concurrency, networking, and inter-process communication (IPC). The book then illustrates how to carry out searching and arrange data using different sorting techniques, before demonstrating the implementation of data structures such as stacks and queues. Later, you'll learn interesting programming features such as using graphics for drawing and animation, and the application of general-purpose utilities. Finally, the book will take you through advanced concepts such as low-level programming, embedded software, IoT, and security in coding, as well as techniques for improving code performance.

By the end of this book, you'll have a clear understanding of C programming, and have the skills you need to develop robust apps.

What you will learn

• Discover how to use arrays, functions, and strings to make large applications
• Perform preprocessing and conditional compilation for efficient programming
• Understand how to use pointers and memory optimally
• Use general-purpose utilities and improve code performance
• Implement multitasking using threads and process synchronization
• Use low-level programming and the inline assembly language
• Understand how to use graphics for animation
• Get to grips with applying security while developing C programs

Who this book is for

This intermediate-level book is for developers who want to become better C programmers by learning its modern features and programming practices. Familiarity with C programming is assumed to get the most out of this book.

Working with Graphs

Graphs show information in pictorial format. In graphs, certain information is plotted and then those plotted points are connected through lines or bars. Each plotted point is called a vertex (the plural of this is vertices), and the lines connecting them are called edges. Graphs have the ability to display large volumes of data in an easy-to-understand manner. Therefore, when comparing huge or enormous data, graphs are generally preferred.

Graphs can be used in several applications that include displaying a certain route of transmission or flow of data packets. Graphs can also be used to represent a kind of connection between two cities or stations, where stations can be represented by vertices and the route can be represented by edges. On social media, even friends can be connected in the form of graphs where each person can be represented by vertices and the edges between them ensure that they are friends. Similarly, graphs can be used for representing different networks.

In this chapter, we will learn how to represent graphs using different data structures. We will also learn to traverse the graphs and create a minimum spanning tree from graphs. To be able to do so, we are going to look at the following recipes:

• Creating an adjacency matrix representation of a directed graph
• Creating an adjacency matrix representation of an undirected graph
• Creating an adjacency list representation of a directed graph
• Carrying out the breadth-first traversal of a graph
• Carrying out the depth-first traversal of a graph
• Creating minimum spanning trees using Prim's algorithm
• Creating minimum spanning trees using Kruskal's algorithm

Before we begin with the recipes, let's have a quick introduction to the two main types of graphs.

Types of graphs

Based on directions, graphs can be of two types: directed and undirected. Let's review both of them briefly.

Directed graphs

In a directed graph, the edges clearly show the direction from one vertex to another. An edge in a directed graph is usually represented as (v1, v2), which means that the edge is pointing from vertex v1 toward vertex v2. In other words, a (v1, v2) pair indicates that v1 is the starting vertex and v2 is the ending vertex. A directed graph is very useful in real-world applications and is used in the World Wide Web (WWW), Google's PageRank algorithm, and more. Consider the following directed graph:

Figure 10.1

Here, you can see an edge between vertices a and b. Because the edge is pointing from vertex a toward b, vertex a is considered to be the starting vertex and vertex b is considered the ending vertex. This edge can be represented as (a,b). Similarly, there is an edge from vertices a to c, which, in turn, can be represented as (a,c). Therefore, we can say that the preceding graph has the following set of vertices:

(V) - { a,b,c,d,e}

Additionally, the graph has the following set of edges:

(E) - {(a,b), (a,c), (c,d), (c,e), (d,b), (d,e), (e,a), (e,b)}

Undirected graphs

An undirected graph is one in which the edges are present between vertices, but there is no specific direction identified – that is, there are no arrows at the end of the edges. Therefore, we cannot know which is the starting vertex and which one is the ending vertex. Undirected graphs are widely used in real-world applications such as Facebook and neural networks.

An edge between two vertices, a and b, in an undirected graph will mean that either of them can be a starting or ending vertex. Such an edge can be written as (a,b), that is, from a to b, as well as (b,a), that is, from b to a. The following diagram shows an undirected graph:

Figure 10.2

So, for this undirected graph, the following is the set of vertices:

(V) - { a,b,c,d,e}

Additionally, the graph will have the following set of edges:

(E) - {(a,b), (b,a), (a,c), (c,a), (a,e), (e,a), (b,e), (e,b), (b,d), (d,b), (c,d), (d,c), (c,e), (e,c)}

Now, let's begin with the recipes.

Creating an adjacency matrix representation of a directed graph

An adjacency matrix is a square matrix that is used to represent a graph. The rows and columns of the matrix are labeled as per the graph vertices. So, if the graph vertices are 1,2,...5, then the rows and columns of the adjacency matrix will be labeled as 1,2,...5. Initially, the matrix is filled with all zeros (0). Then, the 0 at the mat[i][j] location (where i and j refer to the vertices) is replaced by 1 if there is an edge between the vertices of i and j. For example, if there is an edge from vertex 2 to vertex 3, then at the mat[2][3] index location, the value of 0 will be replaced by 1. In short, the elements of the adjacency matrix indicate whether pairs of vertices are adjacent or not in the graph.

Consider the following directed graph:

Figure 10.3

Its adjacency matrix representation is as follows:

5,5 1 2 3 4 5
-----------------------------------------------------------------------------
1 0 1 1 0 0
2 0 0 0 0 0
3 0 0 0 1 1
4 0 1 0 0 1
5 1 1 0 0 0

The first row and the first column represent the vertices. If there is an edge between two vertices, then there will be a 1 value at the intersection of their respective row and column. The absence of an edge between them will be represented by 0. The number of nonzero elements of an adjacency matrix indicates the number of edges in a directed graph.

Here are two drawbacks of adjacency matrix representation:

• This representation requires n² elements to represent a graph having n vertices. If a directed graph has e edges, then (n²-e) elements in the matrix would be zeros. Therefore, for graphs with a very low number of edges, the matrix becomes very sparse.
• Parallel edges cannot be represented by an adjacency matrix.

In this recipe, we will ...