Module 3 - Arrays , Strings and Pointers
4.4 Strings: A string is a null-terminated character array. (A null is zero.) Thus, a string contains
the characters that make up the string followed by a null. The null-terminated string is the only type of
string defined by C. While declaring a character array that will hold a string, declare it to be one
character longer than the largest string that it will hold.
For example, to declare an array str that can hold a 10-character string, Specifying 11 for the size makes
room for the null at the end of the string
char str[11];
When you use a quoted string constant in your program, you are also creating a null-terminated string. A
string constant is a list of characters enclosed in double quotes.
For example: ''hello there”
Note: No need to add the null to the end of string constants manually— the compiler does this for you
automatically
C supports a wide range of functions that manipulate strings. The most common are listed here:
Name Function
strcpy(s1, s2) Copies s2 into s1
strcat(s1, s2) Concatenates s2 onto the end of s1
strlen(s1) Returns the length of s1
strcmp(s1, s2) Returns 0 if s1 and s2 are the same; less than 0 if s1<s2; greater than 0
if s1 >s2
strchr(s1, ch) Returns a pointer to the first occurrence of ch in s1
strstr(s1, s2) Returns a pointer to the first occurrence of s2 in s1
These functions use the standard header <string.h>.
#include <stdio.h>
#include <string.h> int
main(void)
{
char s1[80], s2[80];
gets(s1);
gets (s2);
printf("lengths: %d %d\n", strlen(s1), strlen(s2));
if(!strcmp(s1, s2))
printf("The strings are equal\n");
strcat(s1, s2); printf
(''%s\n", s1);
strcpy(s1, "This is a test.\n"); printf(s1);
if(strchr("hello", 'e'))
printf("e is in hello\n");
if(strstr("hi there", "hi"))
printf("found hi");
return 0;
}
Output:
lengths: 5 5
The strings are equal
hellohello
This is a test. e
is in hello
found hi
Note: strcmp() returns false, if strings are equal.
4.5 Two Dimensional Arrays : C supports multidimensional arrays. The simplest form of the
multidimensional array is the two dimensional array.
To declare a two-dimensional integer array d of size 10,20, int
d[10][20];
To access point 1,2 of array d,
d[1] [2]
Example - loads a two-dimensional array with the numbers 1 through 12 and prints them row by row.
#include <stdio.h>
int main(void)
{
int t, i, num[3][4];
for(t=0; t<3; ++t)
for(i=0; i<4; ++i)
num[t][i] = (t*4)+i+1; }
/* now print them out */
for(t=0; t<3; ++t) {
for(i=0; i<4; ++i)
printf(''%3d ", num[t] [i]);
printf("\n"); }
return 0;
}
Arrays of Strings : To create an array of strings, use a two-dimensional character array. The size of the
left dimension determines the number of strings, and the size of the right dimension specifies the
maximum length of each string. To declare an array of 30 strings, each with a maximum length of 79
characters
char str_array[30][80]
statement calls gets( ) with the third string in str_array.
gets(str_array[2]);
The preceding statement is functionally equivalent to
gets(&str_array[2][0])
A Simple Program for array of strings #include
<stdio.h>
#define MAX 100
#define LEN 80
char text[MAX][LEN];
int main(void)
{
register int t, i, j;
printf("Enter an empty line to quit.\n");
for(t=0; t<MAX; t++) {
printf(''%d: ", t);
gets(text[t]);
if(!*text[t]) break; /* quit on blank line */
}
for(i=0; i<t; i++) {
for(j=0; text[i][j]; j++) putchar(text[i][j]);
putchar('\n');
}
return 0;
}
4.6 MultiDimensional Arrays: C allows arrays of more than two dimensions. The
general form of a multidimensional array declaration is type
name[Size1][Size2][Size3] . . .[SizeN];
Arrays of more than three dimensions are not often used because of the amount of memory they require.
For example, a four-dimensional character array with dimensions 10,6,9,4 requires 10 * 6 *9 *4 or 2,160
bytes. If the array held 2-byte integers, 4,320 bytes would be needed. If the array held doubles (assuming
8 bytes per double), 17,280 bytes would be required. The storage required increases exponentially with
the number of dimensions. For example, if a fifth dimension of size 10 was added to the preceding array,
then 172,800 bytes would be required.
In multidimensional arrays, it takes the computer time to compute each index. This means that accessing
an element in a multidimensional array can be slower than accessing an element in a single-dimension
array. When passing multidimensional arrays into functions, you must declare all but the leftmost
dimension.
For example,
array m as int m[4][3][6][5] can also be passed as argument like void
func(int d [ ] [3] [6] [5] ){ /* */ }
You can include the first dimension.
4.8 Array Initialization: C allows initialization of arrays at the time of their
[Link] general form of array initialization
type_specifier arrayname [size1] [size n] = { value_list };
value_list is comma separated list of constants whose type is compatible with the type_specifier Example
: int i[10] = { 1,2,3,4,5,6,7,8,9,10};
here i [ 0 ] = 1 and i [ 9 ] = 10
Character arrays that hold strings allow a shorthand initialization that takes the form: char
array_name[size] = ''string";
Example, this code fragment initializes str to the phrase "I like C": char
str[9] = "I like C";
This is the same as writing
char str[9] = {'I', ' ', 'l', 'i', 'k', 'e',' ', 'C', '\0'};
Multidimensional array initialization :
int sqrs[10] [2] = {
1, 1,
2, 4,
3, 9,
4, 16,
5, 25,
6, 36,
7, 49,
8, 64,
9, 81,
10, 100 };
The other way of initializing
When initializing a multidimensional array, you may add braces around the initializers for each
dimension. This is called subaggregate grouping. For example, here is another way to write the
preceding declaration:
int sqrs[10] [2] = {
{1, 1},
{2, 4},
{3, 9}
{4, 16},
{5, 25},
{6, 36},
{7, 49},
{8, 64},
{9, 81},
{10, 100} };
Unsized Array Initialization : In an array initialization statement, the size of the array is not
specified, the compiler automatically creates an array big enough to hold all the initializers present.
This is called an unsized array.
Example: char e1[] = "Read error\n";
char e2[] = "Write error\n";
char e3[] = "Cannot open file\n";
Given these initializations, this statement printf("%s
has length %d\n", e2, sizeof e2) ;
will print
Write error has
length 13
Unsized array initializations are not restricted to one-dimensional arrays. For multidimensional arrays,
you must specify all but the leftmost [Link] other dimensions are needed to allow the compiler to
index the array properly. In this way, you can build tables of varying lengths, and the compiler
automatically allocates enough storage for them.
Example, the declaration of sqrs as an unsized array is shown here:
int sqrs[] [2] = {
{1, 1),
{2, 4},
{3, 9},
{4, 16},
{5, 25},
{6, 36},
{7, 49},
{8, 64},
{9, 81},
{10, 100} };
The advantage of this declaration over the sized version is that you may lengthen or shorten the table
without changing the array dimensions
4.9 Variable-Length Arrays : An array whose dimensions are specified by any valid
expression, including those whose value is known only at run time is called a variable- length array.
However, only local arrays (that is, those with block scope or prototype scope) can be of variable length.
Example of a variable-length array: void
f(int dim)
{
char str[dim]; /* a variable-length character array */
/* */
}
the size of str is determined by the value passed to f( ) in dim. Thus, each call to f( ) can result in str
being created with a different length.
5.1 Pointers : A pointer is a variable that holds a memory address. This address is the
location of another object (typically another variable) in memory.
Example, if one variable contains the address of another variable, the first variable is said to point to the
second.
● Pointers provide the means by which functions can modify their calling arguments.
● Pointers support dynamic allocation.
● Pointers can improve the efficiency of certain routines.
● Pointers provide support for dynamic data structures, such as binary trees and linked lists
5.2 Pointer Variables : If a variable is going to be a pointer, it must be declared as such.
A pointer declaration consists of a base type, an *, and the variable name.
The general form for declaring a pointer variable is
type *name;
where type is the base type of the pointer and may be any valid type. The name
of the pointer variable is specified by name.
The base type of the pointer defines the type of object to which the pointer will point.
Example, when you declare a pointer to be of type int
*,
the compiler assumes that any address that it holds points to an integer— whether it actually does or not.
(That is, an int * pointer always ''thinks" that it points to an int object, no matter what that piece of
memory actually contains.) Therefore, when you declare a pointer, you must make sure that its type is
compatible with the type of object to which you want to point.
5.3 The Pointer Operators : . There are two pointer operators: * and &.
The & is a unary operator that returns the memory address of its operand. (a unary operator only
requires one operand.)
Example, m = &count;
places into m the memory address of the variable count. This address is the computer's internal location of
the variable. It has nothing to do with the value of count .
& is "the address of." Therefore,
"m receives the address of count .
Int count = 100; Int
*m = &count;
m contains the address of the variable count .
*m contains the value present at that address
5.4 Pointer Expression :
Pointer Assignment: Use a pointer on the right-hand side of an assignment statement to assign its
value to another pointer. When both pointers are the same type.
Example :
#include<stdio.h>
int main(void)
{
int x = 99;
int *p1, *p2;
p1 = &x;
p2 = p1; /* print the value of x twice */
printf(''Values at p1 and p2: %d % d\n", *p1, *p2); } /* print the address of x twice */
printf("Addresses pointed to by p1 and p2: %p %p", p1, p2);
return 0;
}
p1 and p2 both point to x. Thus, both p1 and p2 refer to the same object.
Values at p1 and p2: 99 99
Addresses pointed to by p1 and p2: 0063FDF0 0063FDF0
Notice that the addresses are displayed by using the %p printf( ) format specifier, which causes printf( )
to display an address in the format used by the host computer.
Pointer Conversions : One type of pointer can be converted into another type of pointer. There are
two general categories of conversion:
● those that involve void * pointers,
● those that don't.
In C, it is permissible to assign a void * pointer to any other type of pointer. It is also permissible to assign
any other type of pointer to a void * pointer. A void * pointer is called a generic pointer. The void *
pointer is used to specify a pointer whose base type is unknown. The void * type allows a function to
specify a parameter that is capable of receiving any type of pointer argument without reporting a type
mismatch. It is also used to refer to raw memory (such as that returned by the malloc( ) function) when the
semantics of that memory are not known. No explicit cast is required to convert to or from a void *
pointer.
Except for void *, all other pointer conversions must be performed by using an explicit cast. However, the
conversion of one type of pointer into another type may create undefined behavior.
One other pointer conversion is allowed: You can convert an integer into a pointer or a pointer into an
integer. However, you must use an explicit cast, and the result of such a conversion is
implementation defined and may result in undefined behavior. (A cast is not needed when converting
zero, which is the null pointer.)
Pointer Arithemetic : There are only two arithmetic operations that you can use on pointers:
● addition and
● subtraction.
let p1 be an integer pointer with a current value of 2000. Also, assume ints are 2 bytes long.
After the expression p1++;
p1 contains 2002, not 2001.
each time p1 is incremented, it will point to the next integer. The same is true of decrements.
Example, assuming that p1 has the value 2000, the expression p1--;
causes p1 to have the value 1998
Each time a pointer is incremented, it points to the memory location of the next element of its base type.
Each time it is decremented, it points to the location of the previous element.
We can also add or subtract integers to or from pointers. The expression p1 = p1
+ 12;
makes p1 point to the 12th element of p1's type beyond the one it currently points to.
subtract one pointer from another in order to find the number of objects of their base type that separate the
two. All other arithmetic operations are prohibited. Specifically, you cannot multiply or divide pointers;
you cannot add two pointers; you cannot apply the bitwise operators to them; and you cannot add or
subtract type float or double to or from pointers.
Pointer Comparison : We can compare two pointers in a relational expression. For instance, given
two pointers p and q, the following statement is perfectly valid:
if(p < q)
printf("p points to lower memory than q\n");
Generally, pointer comparisons are useful only when two pointers point to a common object, such as an
array. As an example, a set of stack functions are developed that store and retrieve integer values. As most
readers will know, a stack is a list that uses first-in, last-out accessing. It is often compared to a stack of
plates on a table—the first one set down is the last one to be used. Stacks are used frequently in
compilers, interpreters, spreadsheets, and other system- related software.
5.5 Pointer and Arrays: There is a close relationship between pointers and arrays.
Consider this program fragment:
char str[80], *p1; p1 = str;
Here, p1 has been set to the address of the first array element in str. To access the fifth element in str, you
could write
str[4] or *(p1+4)
Both statements will return the fifth element. Arrays start at 0. Although the standard array- indexing
notation is sometimes easier to understand, pointer arithmetic can be faster. Since speed is often a
consideration in programming, C programmers often use pointers to access array elements.
These two versions of putstr( )— one with array indexing and one with pointers— illustrate how you can
use pointers in place of array indexing.
The putstr( ) function writes a string to the standard output device one character at a time.
/* Index s as an array. */
void putstr(char *s)
{
register int t;
for(t=0; s[t]; ++t)
putchar(s[t]);
}
/* Access s as a pointer. */ void
putstr(char *s)
{
while(*s)
putchar(*s++);
Array of Pointers : Pointers can be arrayed like any other data type. The declaration for an int pointer
array of size 10 is
int *x[10];
To assign the address of an integer variable called var to the third element of the pointer array, x[2] =
&var;
To find the value of var, write
*x[2]
To pass an array of pointers into a function, use the same method that you use to pass other arrays: Simply
call the function with the array name without any subscripts.
Example, a function that can receive array x looks like this: void
display_array(int *q[])
{
int t;
for(t=0; t<10; t++)
printf(''%d ", *q[t]);
}
q is not a pointer to integers, but rather a pointer to an array of pointers to integers. Therefore you need to
declare the parameter q as an array of integer pointers. You cannot declare q simply as an integer pointer
because that is not what it is. Pointer arrays are often used to hold pointers to strings.
Example, you can create a function that outputs an error message given its index, void
syntax_error(int num)
{
static char *err[] = { Page 130 "Cannot Open File\n",
''Read Error\n",
"Write Error\n",
"Media Failure\n"
};
printf("%s", err[num]);
}
The array err holds a pointer to each error string. This works because a string constant used in an
expression (in this case, an initialization) produces a pointer to the string. The printf( ) function is called
with a character pointer that points to the error message whose index is passed to the function. For
example, if num is passed a 2, the message Write Error is displayed.
5.6 Multiple Indirection: A pointer point to another pointer that points to the target value.
This situation is called multiple indirection, or pointers to pointers. The value of a normal pointer is the
address of the object that contains the desired value. In the case of a pointer to a pointer, the first pointer
contains the address of the second pointer, which points to the object that contains the desired value.
Multiple indirection can be carried on to whatever extent
desired, but more than a pointer to a pointer is rarely needed. In fact, excessive indirection is difficult to
follow and prone to conceptual errors.
This is done by placing an additional asterisk in front of the variable name.
Example, the following declaration tells the compiler that newbalance is a pointer to a pointer of type
float:
float **newbalance;
newbalance is not a pointer to a floating-point number but rather a pointer to a float pointer
Example:
#include <stdio.h>
int main(void)
{
int x, *p, **q;
x = 10;
p = &x;
q = &p;
printf("%d", **q); /* print the value of x */
return 0;
}
Here, p is declared as a pointer to an integer and q as a pointer to a pointer to an integer. The call to printf(
) prints the number 10 on the screen.
5.7 Initializing Pointer: After a nonstatic, local pointer is declared but before it has been
assigned a value, it contains an unknown value. (Global and static local pointers are automatically
initialized to null.)
important convention— : A pointer that does not currently point to a valid memory location is given the
value null (which is zero). Null is used because C guarantees that no object will exist at the null address.
Thus, any pointer that is null implies that it points to nothing and should not be used.
● to give a pointer a null value is to assign zero to it
○ char *p=0;
● define the macro NULL, which is a null pointer constant.
○ P = NULL;
A null pointer can be used to mark the end of a pointer array. A routine that accesses that array knows that
it has reached the end when it encounters the null value.
#include <stdio.h>
int search(char *p[], char *name); char
*names[] = {
"Herb",
"Rex",
"Dennis",
''John ",
NULL}; /* null pointer constant ends the list */
int main(void)
{
if(search(names, "Dennis") != 1) printf
("Dennis is in list.\n");
if(search(names, "Bill") == -1)
printf("Bill not found.\n");
return 0;
} /* Look up a name. */
int search(char *p[], char *name)
{
register int t;
for(t=0; p[t]; ++t) if(!strcmp(p[t], name)) return
t;
return -1; /* not found */
}
char * pointers to point to string constants:
char *p = "hello world";
p is a pointer, not an array. The C compiler creates what is called a string table, which stores the string
constants used by the program. Therefore, the preceding declaration statement places the address of
''hello world", as stored in the string table, into the pointer p. Throughout a program, p can be used like
any other string.
Example: #include
<stdio.h>
#include < string.h> char
*p = "hello world"; int
main(void)
{
register int t;
/* print the string forward and backwards */ printf(p);
for(t=strlen(p)-1; t>-1; t--)
printf("%c", p[t]);
return 0;
}
21.1 Sorting : Sorting is the process of arranging a set of similar information into an increasing or
decreasing order. Sorting is one of the most intellectually pleasing categories of algorithms because the
process is so well defined.
21.4 The Bubble Sort : The bubble sort is an exchange sort. It involves the repeated
comparison and, if necessary, the exchange of adjacent elements. The elements are like bubbles in a tank
of water—each seeks its own level.
/* The Bubble Sort. */
void bubble(char *items, int count)
{
register int a, b;
register char t;
for(a=1; a < count; ++a)
for(b=count-1; b >= a; --b)
{
if(items[b-1] > items[b])
{
/* exchange elements */ t
= items[b-1];
items[b-1] = items[b];
items[b] = t;
}
}
}
items is a pointer to the character array to be sorted, count is
the number of elements in the array.
The bubble sort is driven by two loops. Given that there are count elements in the array, the outer loop
causes the array to be scanned count–1 times. This ensures that, in the worst case, every element is in its
proper position when the function terminates. The inner loop actually performs the comparisons and
exchanges.
/* Sort Driver */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void bubble(char *items, int count); int
main (void)
{
char s[255];
printf("Enter a string:");
gets(s);
bubble(s, strlen(s));
printf(''The sorted string is: %s.\n", s);
return 0;
}
Initial dcab
Pass 1 adcb
Pass 2 abdc
Pass 3 abcd
With the bubble sort, the number of comparisons is always the same because the two for loops repeat the
specified number of times whether the list is initially ordered or not. This means that the bubble sort
always performs 1/2(n2–n). comparisons, where n is the number of elements to be sorted. This formula is
derived from the fact that the outer loop executes n–1 times and the inner loop executes an average of n/2
times. Multiplied together, these numbers result in the preceding formula. Notice the n2 term in the
preceding formula. The bubble sort is said to be an n-squared algorithm because its execution time is
proportional to the square of the number of elements that it is sorting. An n-squared algorithm is
ineffective when applied to a large number of elements because execution time grows exponentially
relative to the number of elements being sorted.
For the bubble sort, the number of exchanges is zero for the best case— an already sorted list. However,
the number of exchanges for the average- and worst-case exchanges are also on the order of n-squared.
Execution time of an n2 sort in relation to array size
Instead of always reading the array in the same direction, alternate passes could reverse direction. In this
way, greatly out-of-place elements travel quickly to their correct position. This version of the bubble sort
is called the shaker sort, because it imparts the effect of a shaking motion to the array. The code that
follows shows how a shaker sort can be implemented.
/* The Shaker Sort. */
void shaker(char *items, int count)
{
register int a;
int exchange;
char t;
do
{
exchange = 0;
for(a=count-1; a > 0; --a) {
if(items[a-1] > items[a]) {
t = items[a-1];
items[a-1] = items[a];
items[a] = t;
exchange = 1;
}
}
}
for(a=1; a < count; ++a)
{
if(items[a-l] > items[a]) {
t = items[a-l];
items[a-1] = items[a];
items[a] = t; exchange =
1;
}
}
} while(exchange); /* sort until no exchanges take place *
}
Although the shaker sort improves the bubble sort, it still executes on the order of an n-squared
algorithm. This is because the number of comparisons has not been changed and the number of
exchanges has been reduced by only a relatively small constant. The shaker sort is better than the bubble
sort.
21.11 Searching : C compilers supply the standard bsearch( ) function as part of the standard
library. However, as with sorting, general-purpose routines are sometimes too inefficient for use in
demanding situations because of the extra overhead created by their generalization. Also, bsearch( )
cannot be applied to unsorted data
Searching Methods : Finding information in an unsorted array requires a sequential search starting at
the first element and stopping either when a match is found or at the end of the array. This method must
be used on unsorted data but can be applied to sorted data as well. However, if the data has been sorted,
can use a binary search, which helps to locate the data more quickly.
The Sequential Search : The sequential search is simple to code. The following function searches a
character array of known length until a match of the specified key is found.
int sequential_search(char *items, int count, char key)
{
register int t;
for(t=0; t < count; ++t)
if(key == items[t])
return t;
return -1; /* no match */
}
It is easy to see that a sequential search will, on the average, test n/2 elements. In the best case it tests
only one element, and in the worst case it tests n elements. If the information is stored on disk, the search
time can be lengthy. But if the data is unsorted, you can only search sequentially.
The Binary Search : If the data to be searched is sorted, use a vastly superior method to find a
match. It is the binary search, which uses the divide-and-conquer approach. To employ this method, test
the middle element. If it is larger than the key, test the middle element of the first half; otherwise, test the
middle element of the second half. Repeat this procedure until a match is found or there are no more
elements to test.
For example, to find the number 4 given the array 1 2
3456789
a binary search first tests the middle, which is 5. Since this is greater than 4, the search continues with the
first half, or
1234
The middle element is now 3. This is less than 4, so the first half is discarded. The search continues with
45
This time the match is found.
In a binary search, the number of comparisons in the worst case is log2 n .
In the average case, the number is somewhat lower, and in the best case the number of comparisons is
one.
/* The Binary search. */
int binary_search(char *items, int count, char key)
{
int low, high, mid;
low = 0;
high = count-1;
while(low <= high)
{
mid = (low+high)/2;
if(key < items[mid])
high = mid-1; else
if(key > items[mid])
low = mid+1;
else return mid; /* found */
return -1;
}