MODULE-1[CHAPTER 2]

BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT

 ARRAYS
 An Array is defined as, an ordered set of similar data items. All the data items of an
array are stored in consecutive memory locations.
 The data items of an array are of same type and each data items can be accessed using
the same name but different index value.
 An array is a set of pairs, such that each index has a value associated with it. It can be
called as corresponding or a mapping.
 Ex:
 <index, value>
 < 0 , 25 > list[0]=25
 < 1 , 15 > list[1]=15
 < 2 , 20 > list[2]=20
 < 3 , 17 > list[3]=17
 < 4 , 35 > list[4]=35
 Here, list is the name of array. By using, list [0] to list [4] the data items in list can be
accessed.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
 Structure Array is
 objects: A set of pairs <index, value> where for each value of index there
is a value from the set item.
 Index is a finite ordered set of one or more dimensions, for example, {0, … ,
n-1} for one dimension, {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)}
for two dimensions, etc.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

 Functions:
For all 𝑆 ∈ 𝑆𝑡𝑎𝑐𝑘, 𝑥 ∈ 𝐼𝑡𝑒𝑚
 Stack Create() ::=
return an empty stack
 Item Top(S) ::=
if 𝑆 ≠ empty
return the most recently inserted item in stack 𝑆
else Create() → Makes a new empty stack.
return error Top(S) → Looks at the top element.
 Stack Push(S, x) ::= Push(S, x) → Adds a new element on
return a stack that is identical to 𝑆 except top.
the new pair 𝑡 𝑜𝑝𝑥 has been inserted Pop(S) → Removes the top element.
 Stack Pop(S) ::=
if 𝑆 ≠ empty
return a stack that is identical to 𝑆 except
the most recently inserted item has been removed
else
return error
 end Stack

Abstract data type Stack

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

Procedure CreateStack()
S ← empty stack
return S
EndProcedure
Procedure Push(S, x)
add x to the top of S
EndProcedure
Procedure Pop(S)
if S is empty
print "Error: Stack Underflow"
else
remove the top element from S
EndProcedure
Procedure Top(S)
if S is empty
print "Error: Stack is empty"
else
return top element of S
EndProcedure

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

useing the Stack ADT we just implemented to calculate the sum of n numbers.
[Link] all numbers into the stack.
[Link] numbers one by one and add them to a sum variable.

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct {
int items[MAX];
int top;
} Stack;
// Create an empty stack
Stack CreateStack() {
Stack s;
[Link] = -1;
return s;
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
// Push an element onto stack
void Push(Stack *s, int x) {
if (s->top == MAX - 1) {
printf("Error: Stack Overflow\n");
} else {
s->top++;
s->items[s->top] = x;
}
}
// Pop the top element
int Pop(Stack *s) {
if (s->top == -1) {
printf("Error: Stack Underflow\n");
return 0; // Return 0 for safety
} else {
int x = s->items[s->top];
s->top--;
return x;
}
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

// Check if stack is empty
int isEmpty(Stack s) {
return [Link] == -1;
}

int main() {
Stack s = CreateStack();
int n, num, sum = 0;

printf("Enter the number of elements: ");

scanf("%d", &n);

// Push n numbers into the stack

for (int i = 0; i < n; i++) {
printf("Enter number %d: ", i + 1);
scanf("%d", &num);
Push(&s, num);
} PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
// Pop elements and calculate sum
while (!isEmpty(s)) {
sum += Pop(&s);
}
printf("Sum of %d numbers = %d\n", n, sum);
return 0;
}
OUTPUT—
Enter the number of elements: 5
Enter number 1: 2
Enter number 2: 4
Enter number 3: 6
Enter number 4: 8
Enter number 5: 10
Sum of 5 numbers = 30

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

ARRAYS IN C
 A one-dimensional array can be declared as follows:
int list[5]; //array of 5 integers
int *plist[5]; //array of 5 pointers to integers
 Compiler allocates 5 consecutive memory-locations for each of the variables
'list' and 'plist'.
 Address of first element list[0] is called base-address.
 Memory-address of list[i] can be computed by compiler as

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

Program to print both address of ith element of given array & the value found at that
address:
#include <stdio.h>
void print1(int *ptr, int rows)
{
/* print out a one-dimensional array using a pointer */
int i;
printf("Address Contents\n");
for (i = 0; i < rows; i++)
printf("%p %5d\n", (void *)(ptr + i), *(ptr + i));
//(ptr + i) → calculates the address of the i-th element (pointer arithmetic).
//(void *)(ptr + i) → casts it to void * so printf can safely display the address.
//*(ptr + i) → dereferences the pointer to get the value at that location.
printf("\n");
OUTPUT
}
int main(void) // standard C signature
{
int one[] = {0, 1, 2, 3, 4};
print1(one, 5); // &one[0] is same as one
return 0;
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

DYNAMICALLY ALLOCATED ARRAYS
ONE-DIMENSIONAL ARRAYS
 When writing programs, sometimes we cannot reliably
determine how large an array must be.
 A good solution to this problem is to
 → defer this decision to run-time &
 → allocate the array when we have a good estimate of
required array-size
 Dynamic memory allocation can be performed as follows:

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

#include <stdio.h>
#include <stdlib.h> // for malloc, exit
int main(void) {
int i, n, *list;
printf("Enter the number of numbers to generate: ");
scanf("%d", &n);
if (n < 1) {
printf("Improper value\n");
exit(0);
}
// dynamically allocate memory
list = (int *)malloc(n * sizeof(int));
if (list == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
} Enter the number of numbers to generate: 0
Improper value

 The above code would allocate an array of exactly the required size and hence would not result in
any wastage.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

TWO DIMENSIONAL ARRAYS
 These are created by using the concept of array of arrays.
 A 2-dimensional array is represented as a 1-dimensional array in which each
element has a pointer to a 1-dimensional array as shown below
 int x[5][7]; //we create a 1-dimensional array x whose length is 5;
//each element of x is a 1-dimensional array whose length is 7.
 Address of x[i][j] = x[i]+j*sizeof(int)

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

#include <stdio.h>
#include <stdlib.h>
int main(void) {
int **array;
int nrows, ncolumns;
int i, j;
// Ask user for rows and columns
printf("Enter number of rows: ");
scanf("%d", &nrows);
printf("Enter number of columns: ");
scanf("%d", &ncolumns);
// Allocate array of int* (row pointers)
array = malloc(nrows * sizeof(int *));
if (array == NULL) {
printf("Out of memory\n");
exit(1);
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
// Allocate each row
for (i = 0; i < nrows; i++) {
array[i] = malloc(ncolumns * sizeof(int));
if (array[i] == NULL) {
printf("Out of memory\n");
exit(1);
}
}
// Fill the array with sample values (row*col)
for (i = 0; i < nrows; i++) {
for (j = 0; j < ncolumns; j++) {
array[i][j] = i * j;
}
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

 // Print the array
printf("Generated 2D array:\n");
for (i = 0; i < nrows; i++) {
for (j = 0; j < ncolumns; j++) {
printf("%4d", array[i][j]);
}
printf("\n");
}

}// Free memory

for (i = 0; i < nrows; i++) {
free(array[i]);
}
free(array);

return 0;

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

CALLOC
 These functions → allocate user-specified amount of memory & → initialize
the allocated memory to 0.
 On successful memory-allocation, it returns a pointer to the start of the new
block. On failure, it returns the value NULL.
 Memory can be allocated using calloc as shown below:

int *p;
p=calloc(n, sizeof(int));
//where n=array size

 To create clean and readable programs, a CALLOC macro can be created as

shown below:
#define CALLOC(p,n,s)
if((p=calloc(n,s))==NULL)
{
printf("insufficient memory");
exit(1);
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

REALLOC
 These functions resize memory previously allocated by either malloc or
calloc.
 For example,
 realloc(p,s); //this changes the size of memory-block pointed at by p to s <
oldSize, the rightmost oldSize-s bytes of old block are freed..
 When s>oldSize, the additional s-oldSize have an unspecified value and when
s
 On successful resizing, it returns a pointer to the start of the new block.
 On failure, it returns the value NULL.
 To create clean and readable programs, the REALLOC macro can be created as
shown below:

#define REALLOC(p,s)
if((p=realloc(p,s))==NULL)
{
printf("insufficient memory");
exit(0);
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
STRUCTURES AND UNIONS
 Structures:
 Arrays are collections of data of the same type.
 In C there is an alternate way of grouping data that permits the data to vary
in type. This mechanism is called the struct, short for structure.
 A structure (called a record in many other programming languages) is a
collection of data items,
 where each item is identified as to its type and name.
struct {
char name[10];
int age;
float salary;
} person;

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

 Creates a variable whose name is person and that has three fields:
 a name that is a character array
 an integer value representing the age of the person
 a float value representing the salary of the individual
 Dot operator(.) is used to access a particular member of the structure.
strcpy([Link],"james") ;
[Link]
[Link] = 35000;
 We can create our own structure data types by using the typedef statement as below:

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

Variables can be declared as follows:
humanBeing person1,person2;
Structures cannot be directly checked for equality or inequality. So, we can write
a function to do this.
#include <stdio.h>
#include <string.h>
typedef struct {
char name[50];
int age;
float salary;
} HumanBeing;
// Function to check equality
int humans_equal(HumanBeing person1, HumanBeing person2) {
// Compare name (strcmp returns 0 if equal)
if (strcmp([Link], [Link]) != 0)
return 0; // FALSE
// Compare age
if ([Link] != [Link])
return 0; // FALSE
// Compare salary
if ([Link] != [Link])
return 0; // FALSE

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

// If all fields match
return 1; // TRUE
}
int main(void) {
HumanBeing person1 = {"Alice", 30, 55000.0};
HumanBeing person2 = {"Alice", 30, 55000.0};
HumanBeing person3 = {"Bob", 25, 40000.0};
The two human beings are the same
if (humans_equal(person1, person2)) The two human beings are not the same
printf("The two human beings are the same\n");
else
printf("The two human beings are not the same\n");

if (humans_equal(person1, person3))
printf("The two human beings are the same\n");
else
printf("The two human beings are not the same\n");
return 0;
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

We can embed a structure within a structure.
typedef struct {
int month;
int day;
int year; } date;
typedef struct human—being {
char name[10];
int age;
float salary;
date dob;
};
➢ A person born on February 11, 1944, would have the values for the date struct set
as:
[Link] = 2;
[Link] = 11; [Link] = 1944;

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

#include <stdio.h>
// Structure for date
typedef struct {
int month;
int day;
int year;
} Date;
// Structure for human being, embedding Date
typedef struct {
char name[10];
int age;
float salary;
Date dob; // embedded structure (date of birth)
} HumanBeing;
int main(void) {
// Initialize a human being with nested structure
HumanBeing person = {"Alice", 30, 55000.0, {5, 15, 1995}};

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

// Access and print
printf("Name: %s\n", [Link]);
printf("Age: %d\n", [Link]);
printf("Salary: %.2f\n", [Link]);
printf("Date of Birth: %02d/%02d/%d\n",
[Link], [Link], [Link]);

return 0;
} Name: Alice
Age: 30
Salary: 55000.00
Date of Birth: 15/05/1995

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

Unions
 This is similar to a structure, but the fields of a union must share their memory space.
 This means that only one field of the union is "active" at any given time.
typedef struct sex—type {
enum tag—field {female, male
} sex;
union {
int children;
int beard ;
} u;
};
typedef struct human—being {
char name[10];
int age;
float salary;
date dob;
sex—type sex—info;
};
human—being personl, person2;

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

EXAMPLE
#include <stdio.h>
// Structure for date
typedef struct {
int month;
int day;
int year;
} Date;

// Structure for sex-type

typedef struct {
enum { female, male } sex; // tag field
union {
int children; // if female
int beard; // if male
} u;
} SexType;

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

// Structure for human being
typedef struct {
char name[10];
int age;
float salary;
Date dob; // embedded structure
SexType sex_info; // embedded structure with enum + union
} HumanBeing;
int main(void) {
HumanBeing person1, person2;
// Initialize person1 (female with children)
snprintf([Link], sizeof([Link]), "Alice");
[Link] = 30;
[Link] = 55000.0;
[Link] = (Date){5, 15, 1995};
person1.sex_info.sex = female;
person1.sex_info.[Link] = 2;

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

// Initialize person2 (male with beard length)
snprintf([Link], sizeof([Link]), "Bob");
[Link] = 35;
[Link] = 60000.0;
[Link] = (Date){8, 20, 1990};
person2.sex_info.sex = male;
person2.sex_info.[Link] = 1; // 1 = has beard, could also store length

// Print results
printf("Person1: %s, %d years, Salary: %.2f, DOB: %02d/%02d/%d\n",
[Link], [Link], [Link],
[Link], [Link], [Link]);

if (person1.sex_info.sex == female)
printf("Sex: Female, Children: %d\n", person1.sex_info.[Link]);

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

printf("\nPerson2: %s, %d years, Salary: %.2f, DOB: %02d/%02d/%d\n",
[Link], [Link], [Link],
[Link], [Link], [Link]);

if (person2.sex_info.sex == male)
printf("Sex: Male, Beard: %d\n", person2.sex_info.[Link]);

return 0;
} Person1: Alice, 30 years, Salary: 55000.00, DOB: 15/05/1995
Sex: Female, Children: 2
Person2: Bob, 35 years, Salary: 60000.00, DOB: 20/08/1990
Sex: Male, Beard: 1

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

We could assign values to person!
and person2 as:
[Link]—[Link] = male;
[Link]—[Link] = FALSE;
and
[Link]—[Link] = female;
[Link]—[Link] - 4;
 we first place a value in the tag field. This allows us to
determine which field in the union is active.
 We then place a value in the appropriate field of the
union.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

Internal Implementation Of Structures
 The size of an object of a struct or union type is the
amount of storage necessary to represent the largest
component, including any padding that may be required.
 Structures must begin and end on the same type of
memory boundary, for example, an even byte boundary or
an address that is a multiple of 4, 8, or 16.
 Self-Referential Structures:
 A self-referential structure is one in which one or more of
its components is a pointer to itself.
 These require dynamic storage management routines
(malloc & free) to explicitly obtain and release memory.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

#include <stdio.h>
#include <stdlib.h>
// Define a node of the linked list
typedef struct list {
char data;
struct list *link; // pointer to the next node
} List;
int main(void) {
// Create three nodes
List item1, item2, item3;
// Assign data
[Link] = 'a';
[Link] = 'b';
[Link] = 'c';

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

// Initially, no links
[Link] = [Link] = [Link] = NULL;

// Attach them together: item1 -> item2 -> item3

[Link] = &item2;
[Link] = &item3;
Linked list contents: a b c
// Traverse and print
List *ptr = &item1;
printf("Linked list contents: ");
while (ptr != NULL) {
printf("%c ", ptr->data);
ptr = ptr->link;
}
printf("\n");

return 0;
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

POLYNOMIALS ABSTRACT DATA TYPE
 Polynomials an algebraic expression in which power of variable should
be whole number.
 A polynomial is a sum of terms, where each term has a form axe ,
where x=variable, a=coefficient and e=exponent.
 The largest(or leading) exponent of a polynomial is called its degree.
 Assume that we have 2 polynomials,

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
POLYNOMIAL REPRESENTATION: standard array-based (first
method) polynomial representation and a sketch of the polynomial
addition (padd) algorithm

#define MAX_DEGREE 100

typedef struct {
int degree;
float coef[MAX_DEGREE];
} polynomial;

polynomial a;

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

Polynomial Addition (padd algorithm)
d = Zero()
while (!IsZero(a) && !IsZero(b)) do
switch COMPARE(Lead_Exp(a), Lead_Exp(b)):
case -1: attach leading term of b → d; remove it from b
case 0: add coefficients; if sum ≠ 0 attach to d; remove from both
case 1: attach leading term of a → d; remove it from a
insert any remaining terms of a or b into d

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

Pseudocode: Polynomial Addition (Array Method)
Procedure PADD(A, B)
Input: Two polynomials A and B represented by arrays
Output: Polynomial D = A + B
// Step 1: Initialize
[Link] ← max([Link], [Link])
For i ← 0 to [Link] do
[Link][i] ← 0
// Step 2: Copy coefficients of A into D
For i ← 0 to [Link] do
[Link][i] ← [Link][i] + [Link][i]
// Step 3: Add coefficients of B into D
For i ← 0 to [Link] do
[Link][i] ← [Link][i] + [Link][i]
// Step 4: Adjust degree of D (remove leading zeros if any)
While [Link] > 0 AND [Link][[Link]] = 0 do
[Link] ← [Link] - 1
Return D
End Procedure

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

POLYNOMIAL REPRESENTATION:
SECOND METHOD
#define MAX_TERMS 100
typedef struct polynomial
{
float coef;
int expon;
}polynomial;
polynomial terms[MAX_TERMS];
int avail=0;

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

Pseudocode: Polynomial Addition
Initialize array terms[MAX_TERMS]
Initialize avail = 0

Function ATTACH(coefficient, exponent):

if avail >= MAX_TERMS:
Print "Too many terms in the polynomial"
Exit program
terms[avail].coef = coefficient
terms[avail].expon = exponent
avail = avail + 1

Function COMPARE(a, b):

if a > b: return 1
else if a == b: return 0
else: return -1

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

Function PADD(starta, finisha, startb, finishb, &startd, &finishd):
startd = avail
while starta <= finisha AND startb <= finishb:
switch COMPARE(terms[starta].expon, terms[startb].expon):
case 1: // A exponent > B exponent
ATTACH(terms[starta].coef, terms[starta].expon)
starta = starta + 1
case 0: // exponents equal
coefficient = terms[starta].coef + terms[startb].coef
if coefficient != 0:
ATTACH(coefficient, terms[starta].expon)
starta = starta + 1
startb = startb + 1
case -1: // A exponent < B exponent
ATTACH(terms[startb].coef, terms[startb].expon)
startb = startb + 1

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

// Add remaining terms of A
while starta <= finisha:
ATTACH(terms[starta].coef, terms[starta].expon)
starta = starta + 1

// Add remaining terms of B

while startb <= finishb:
ATTACH(terms[startb].coef, terms[startb].expon)
startb = startb + 1

finishd = avail - 1

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT

Main Program:
Read polynomial A and store terms using ATTACH
Record startA and finishA
Read polynomial B and store terms using ATTACH
Record startB and finishB

Call PADD(startA, finishA, startB, finishB, &startD, &finishD)

Print terms from startD to finishD as the result polynomial

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT