close

Se connecter

Se connecter avec OpenID

C Programming A Modern Approach

IntégréTéléchargement
C Programming
A Modern Approach
K. N. King,
C Programming
A Modern Approach,
W. W. Norton & Company, 1996.
Note About Coverage



This class has only part of the semester
dedicated to C
You already know Java, which has similar
syntax
You should be able to read the book quickly
Similarities of C to Java

/* Comments */

Variable declarations

If / else statements

For loops

While loops

Function definitions (like methods)

Main function starts program
Differences between C and Java

C does not have objects

There are “struct”ures

But data are not tied to methods

C is a functional programming language

C allows pointer manipulation

Input / Output with C

Output with printf function

Input with scanf function
C Strengths


Efficiency

Limited amount of memory

Fast
Portability

Compilers are small and easily written

C: UNIX and ANSI/ISO standard

Power

Flexibility

Standard library


Input/output, string handling, storage allocation, etc.
Integration with UNIX
C Weakness



Can be error-prone

Flexibility

C compiler doesn’t detect many
programming mistakes

Pitfalls
Can be difficult to understand

Some features are easier to be misused

Flexibility
Can be difficult to modify

No modules
Compiling and Linking
Variables and Assignments

C is case-sensitive

Compiler remembers only first 31 characters

Type

Should be declared



int height, length, width;
Declarations must precede the statements.
The value should be assigned before using the variable in
computations:

height = 8;

length = 12;

width = 5;

int volume = height * length * width;
Constants

Macro definition:


#define SCALE_FACTOR (5.0/9.0)
No semicolon at the end!
Formatted Output: printf




printf(string, expr1, expr2,…)
Format string contains both ordinary
characters and conversion specifications
Conversion specification is a placeholder
representing a value to be filled in during
printing.
The information after % specifies how the
value is converted form its internal
form(binary) to printed form (characters)
Pitfalls
Formatted Input: scanf

scanf(string, expr1, expr2,…)

Reads input according to a particular format.





Format string contains both ordinary
characters and conversion specifications
scanf(“%d%d%f%f”, &i, &j, &x, &y);
Number of conversion specification should
match number of variables.
Each conversion should be appropriate for
type of the variable.
while (scanf (“%d”, &i)==1) {
How scanf Works


For each conversion specification, tries to locate an
item of appropriate type, skipping blank spaces if
necessary.
Reads it, stopping when it encounters the symbol
that can’t belong o item.

Ignores white-space characters.

scanf(“%d%d%f%f”, &i, &j, &x, &y);
Assignment Operators


Simple assignment(right associative): =

int i=5, j=3;

int k = 5*3;

i = 72.99;

float f;

f = 136;

i = j = k = 7;

f = i = 33.3;

k = 1 + (j = i);
Compound assignments(right associative):
+=, -=, *=, /=, %=

i += j += k;

i += k;
vs
i =+ k;
Increment and Decrement
Operators

Prefix operators: ++i, --i

Postfix operators: i++, i—
Precedence and Associativity
Sub expression Evaluation

a = 5;
c = (b = a + 2) – (a = 1);

i = 2;
j = i * i ++;

Any expression can be used as a statement

i++;

i*j -1;

i + j ; /* i = j */
Relational Operators
0
(false) and 1 (true)
 Their precedence is lower than the precedence
of the arithmetic operators.
 Left associative
i < j < k
Equality Operators


0 (false) and 1 (true)
Their precedence is lower than the
precedence of the relational operators.


i < j == j < k
Left associative
Logical Operators


Logical negation: !

!expr : 1 if expr has the value 0

Right associative

The same precedence as unary plus and minus
Logical and: &&


expr1 && expr2 : 1 if both expr1 and expr2 has non-zero values
Logical or: ||

expr1 || expr2 : 1 if either expr1 or expr2 (or both) has non-zero
values

Short-circuit evaluation

Left associative

The precedence is lower that that of the relational and equality
operators
if … else Statement

if (expression) statement

if (expression) statement else statement

Statement can be compound: { statements}

if (i==0) vs if (i=0)

if (expression)
statement
else if (expression)
statement
…
else
statement
“Dangling else” Problem
if (y != 0)
if (x != 0)
result = x / y;
else
printf (“Error: y is equal to ) \n”);


Use compound statement {}
Compiler always match the closest
unmatched if statement
Conditional Expression

expr1 ? expr2: expr3

int i, j, k;
i = 1;
j = 2;
k=i>j?i:j;
k = (i > 0 ? i : 0) + j ;

return (i > j ? i : j);

printf (“%d\n”, i > j ? i : j);
switch Statement

switch ( expression ){
case constant-expression: statements
…
case constant-expression: statements
default: statements
}



Controlling expression should be an integer expression
(characters)
Constant expression can’t contain variables or function
calls.
Statements do not require {}. Usually, the last statement
is break.
Example
while Loop

while (expression) statement

Statement can be compound: {}

while (i>0) printf (“%d\n”, i--);

while (i>0)
{
printf (“%d\n”, i);
i--;
}

Infinite loops: while(1)

Break, goto, return
Example
scanf(“%d”, &n);
do Loop

do statement while (expression);

Statement can be compound: {}

do printf (“%d\n”, i--); while (i>0) ;

do
{
printf (“%d\n”, i);
i--;
} while (i>0);
for Loop

for (expr1; expr2; expr3) statement

Statement can be compound: {}

expr1;
while (expr2) {
statement
expr3;
}

for (i=10; i>0; i--)
printf (“%d\n”, i);

Infinite loop: for (;;)

Comma operator:

for (i=1, j=2; i+j<10; i++, j++) printf (“%d\n”, i+j);
Example
Exiting From a Loop: break

for (d=2; d<n; d++)
if (n%d==0) break;
if (d<n) printf (“%d is divisible by %d\n”, n,d);
else printf(“%d is prime \n”,n);

for (;;){
printf (“Enter a number(0 to stop): ”);
scanf(“%d”,&n);
if (n==0) break;
printf(“%d cubed is %d\n”,n,n*n*n);
}

break escapes only one level of nesting.
Skipping the Rest of Iteration:
continue

n = 10;
sum = 0;
while (n-->0){
scanf(“%d”, &i);
if (i%2==0) continue;
sum+=i;
}
Null statement


;
for (d=2; d<n; d++)
if (n%d==0) break;



for (d=2; d<n && n%d !=0 ; d++);
Accidentally putting a semicolon after the
parentheses in if, while or for statement
ends the statement prematurely.
if (i==0);
printf (“Zero\n”);

while (i>0); printf (“%d\n”, i--);
Basic Types: Integers

Signedness: signed (defaut), unsigned

Size: short, long

<limits.h> holds ranges for int types.
Integer Constants

Decimal (base 10) literals

digits between 0-9, no leading zero


Octal (base 8) literals

digits between 0-7, must start with 0


15, 255, 32767
017, 0377, 077777
Hexadecimal (base 16) literals

digits between 0-9 and letters between AF (a-f), must start with 0x (0X)

0xF, 0xFF, 0x7FFF
Basic Types: Floating Types

<float.h>

Assume IEEE 754 standard

Scientific notation: sign, an exponent, a fraction

.57e2, 57, 5.7e+1, 570.0e-1
Basic Types: char

Character set: Latin (7 bit), ASCII (8 bit)

Treats as integers

unsigned (0-255) and signed (-128-127) version


Some compilers use unsigned by default, the other compilers use
signed by default.
char ch=65; /* it’s ‘A’ now */
int i = ‘a’; /* it’s 97 */
ch++; /* it’s ‘B’ now */

if (‘a’< =ch && ch <=‘z’)
ch = ch – ‘a’ + ‘A’;
/* ch=toupper(ch);*/

for (ch=‘A’; ch<=‘Z’; ch++) …

ch=‘a’ * ‘b’ / ‘c’
…
Read and Write char: Alternative

ch = getchar();

putchar(ch);

while ( ( ch = getchar() ) != ‘\n’ ) …

while ((ch=getchar())==‘ ’);

printf(“Enter an integer: ”);
scanf(“%d”, &i);
printf(“Enter a command: ”);
command = getchar();
sizeof Operator





sizeof (type-name)
Unsigned integer representing the number of
bytes required to store a value of type-name
sizeof(char) is always 1
Can be applied to constants, variables,
expressions
int i, j;
int k= sizeof(i); /* k is assigned 2*/
k = sizeof (i + j );
Implicit Type Conversion


Convert operands to the “narrowest” type that will
safely accommodate both values.
If the type of either operand is a floating point:
float -> double - > long double

Otherwise:
if there are short and char operands, convert
them to int, then
int -> unsigned int -> long int -> unsigned long int

int i= -10;
unsigned int u=10;
Conversion During Assignment

char c = ‘A’;
int ind;
float f;
double d;
i = c; /* will get 65 */
f = i; /* will get 65.0 */
d = f;
i = 824.97; /* 824 */
c= 100000000;
Explicit Type Conversion: cast



(type-name) expression
Unary operator
float f = 3.45, frac;
frac = f – (int) f;

int num1=5, num2 =3;
float quotient = (float) num1/ num2;

int i=1000;
long int i = (long int) j * j;
long int i = (long int) (j * j)
Celsius vs Fahrenheit table
(in steps of 20F)

C = (5/9)*(F-32);
#include <stdio.h>
int main() {
int fahr, celsius, lower, upper, step;
lower = 0;
upper = 300;
step = 20;
fahr = lower;
while (fahr <= upper) {
celsius = 5 * (fahr - 32) / 9;
printf("%d\t%d\n",fahr, celsius);
fahr += step;
}
return 1;
}



5/9 = 0
Integer arithmetic: 0F = 17C
instead of 17.8C
%d, %3d, %6d etc for
formatting integers
New Version Using Float
#include <stdio.h>
int main() {
float fahr, celsius;
int lower, upper, step;
lower = 0;
upper = 300;
step = 20;
fahr = lower;
while (fahr <= upper) {
celsius = (5.0 / 9.0) * (fahr - 32.0);
printf("%3.0f %6.2f \n", fahr, celsius);
fahr += step;
}
return 1;
}

%6.2f 6 wide; 2 after decimal

5.0/9.0 = 0.555556

Float has 32 bits

Double has 64 bits

Long Double has 80 to 128
bits

Depends on computer
Version 3 with “for” loop
#include <stdio.h>
int main() {
int fahr;
for (fahr=0; fahr <= 300; fahr += 20)
printf("%3d %6.1f \n", fahr,
(5.0 / 9.0) * (fahr – 32.0));
return 1;
}
Version 4 with Symbolic Constants
#include <stdio.h>
#define LOWER 0
#define UPPER 300
#define STEP 20
int main() {
int fahr;
for (fahr=LOWER; fahr <= UPPER; fahr += STEP)
printf("%3d %6.1f \n", fahr,
(5.0 / 9.0) * (fahr - 32.0));
return 1;
}
One –Dimensional Array


Data structure containing a number of values of the same
type.
Declare array: type, name and number of elements


int a[10]
Subscripting:

for (i=0; i<N; i++) a[i]=0;

for (i=0; i<N; i++) scanf (“%d”, &a[i]);

i=0;
while (i<N)
a[i++] = 0;

const int month[]={31,28,31,30,31,30,31,31,30,31,30,31};
Array Initialization

int a[10] = { 1,2,3,4,5,6,7};

int a[]= { 1,2,3,4,5,6,7};
sizeof Operator for Arrays

sizeof(varName)

Determines the size of variable in bytes.

for ( i = 0; i< sizeof(a) / sizeof(a[0]); i++)
a[i]=0;
Multidimensional Array

int m[i][j]

Stores in row-major order

int m[3][3]={{1,2,3},
{4,5,6},
{7,8,9}}

int m[3][3]={{1,2},{4,5,6}}
Arrays

Count #occurrences of each digit, blank, tab,
newline, other characters
#include <stdio.h>
int main() {
int c, i, nwhite, nother;
int ndigit[10];
nwhite = nother = 0;
for (i=0; i<10; ++i)
ndigit[i] = 0;
while ((c = getchar()) != EOF)
if (c > '0' && c < '9')
++ndigit[c-'0'];
else if (c == ' ' || c == '\n' || c == '\t')
++nwhite;
else
++nother;
printf("digits = ");
for (i=0; i<10; ++i)
printf("%d ",ndigit[i]);
printf(", white space = %d, other =
%d\n",nwhite, nother);
}
Functions

return type function-name (parameters)
{
declarations
statements
}

Function can not return array

If function doesn’t return value, use void.


List of parameters: type name, type name…
(void)
ex.:float average(float a, float b){ return (a+b)/2; }
Function Calls

A call of void function is a statement:

void f (int a){
printf(“%d\n”, a);
}
f(3+4*5);

A call of non-void function is an expression:

float average(float a, float b){
return (a+b)/2;
}
float av = average (3+4*5, 2);
Function Declaration


C doesn’t require to define function before its
first use.
void main() {
int i =4, k=5;
float av = average (i,k);
}
float average(float a, float b){ return (a+b)/2; }


To ensure error message, declare function
before its first call (function prototype):
return-type function-name(parameters);

float average (float a, float b);
Arguments

Parameters appear in function definition

Arguments are expressions in function calls.

In C, arguments are passed by value

int power (int x, int n);
void main {
int k=3, pow = power (2, k);
}
int power (int x, int n){
int result=1;
while (n-- >0) result*=x;
return result;
Example

void decompose (float x, int integer, float fract){
integer = (int) x;
fract = x – integer;
}

void main(){
int i=5;
float f= 3.4;
decompose (3.14, i, f);
}
Array Arguments

int f (int a[]) {…}

int sum(int[], int);

int sum(int a[], int n){
int i,sum=0;
for(i=0; i<n; i++) sum+=a[i];
return sum;
}

int a[10]={1,4,6,7,3,2,4};
int total = sum (a, 10);

int f(int a[][10]){…}
return and exit Statements

return expression;

double Largest (double x, double y){
return x>y? x : y;
}

void print_int(int i){
if (i<0) return;
printf(“%d\n”,i);
}

The value returned by main is a status code.

In <stdlib.h>: exit(expression);

Normal success: EXIT_SUCCESS (0)

Abnormal termination: EXIT_FAILURE (1)
Recursive Function

int power (int x, int n){
return n==0? 1: x*power(x, n-1);
}

int factorial(int n){
return n<=1 ? 1 : n*factorial(n-1);
}

int sum_digits(int n){
return n==0 ? 0: n%10+sum_digits(n/10);
}
Functions
#include <stdio.h>
int power(int, int);
/* function prototype */
int main() {
int i;
for (i = 0; i < 10; i++)
printf("%d %d %d\n", i, power(2,i), power(-3,i));
}
int power(int base, int n) {
int p;
for (p = 1; n > 0; --n)
p = p * base;
return p;
}
Functions

Call by value mechanism

Change in n's value not reflected in main

Using pointers, we can achieve Call by
reference effect.
External (Global) Variables




All variables declared so far are local to the
functions
External or Global variables are accessible to
all functions
These are defined once outside of functions
Must be defined once more within each function
which is going to use them
Scope Rules


Automatic/Local Variables

Declared at the beginning of functions

Scope is the function body
External/Global Variables

Declared outside functions

Scope is from the point where they are declared
until end of file (unless prefixed by extern)
Scope Rules

Static Variables: use static prefix on functions
and variable declarations to limit scope

static prefix on external variables will limit scope to
the rest of the source file (not accessible in other
files)

static prefix on functions will make them invisible to
other files

static prefix on internal variables will create
permanent private storage; retained even upon
function exit
Example
int i;
//global variable
void f1 ()
{
int j=0; //call every time when f invoked
j++;
}
void f2 ()
{
static int j=0; //only done once
j++;
}
Scope Rules

Variables can be declared within blocks too

scope is until end of the block
Data Structures (struct)


Arrays require that all elements be of the
same data type.
C and C++ support data structures that can
store combinations of character, integer
floating point and enumerated type data.
They are called a structs.
Structures (struct)



A struct is a derived data type composed of
members that are each fundamental or derived
data types.
A single struct would store the data for one
object. An array of structs would store the data
for several objects.
A struct can be defined in several ways as
illustrated in the following examples:
Declaring Structures (struct)
Struct
struct date
{
int day;
char month[3];
char year[4];
{
int day;
char month[3];
char year[4];
};
/* The name “date" is called a
structure tag
} my_date ;
*/
Struct date date1;
Struct date date2 = {3,”Jan”,”1912”};
my_date date3 = {2,”Jul”,”2010”};
User Defined Data Types (typedef)

The C language provides a facility called typedef for creating
synonyms for previously defined data type names. For
example, the declaration:
typedef int Length;
makes the name Length a synonym (or alias) for the data type
int.

The data “type” name Length can now be used in declarations
in exactly the same way that the data type int can be used:
Length a, b, len ;
Length numbers[10] ;
Winter Quarter
Lect 23 P. 75
Typedef & Struct

Often, typedef is used in combination with struct to
declare a synonym (or an alias) for a structure:
typedef struct
/* Define a structure */
{
int label ;
char letter;
char name[20] ;
} Some_name ;
/* The "alias" is Some_name */
Some_name mystruct ;
/* Create a struct variable */
Accessing Struct Members

Individual members of a struct variable may be accessed
using the structure member operator (the dot, “.”):
mystruct.letter ;

Or , if a pointer to the struct has been declared and
initialized
Some_name *myptr = &mystruct ;
by using the structure pointer operator (the “->“):
myptr -> letter ;
which could also be written as:
(*myptr).letter ;
Sample Program With Structs
/* This program illustrates creating structs
and then declaring and using struct
variables. Note that struct personal is an
included data type in struct "identity".
*/
int main ( )
{
struct identity js = {"Joe Smith"}, *ptr = &js ;
#include <stdio.h>
js.person.id = 123456789 ;
struct personal
{
long id;
float gpa;
};
//Create a struct
struct identity //Create a second struct that includes the first one.
{
char name[30];
struct personal person;
};
js.person.gpa = 3.4 ;
printf ("%s %ld %f\n", js.name, js.person.id,
js.person.gpa) ;
printf ("%s %ld %f\n", ptr->name, ptr>person.id,
ptr->person.gpa) ;
}
Enumeration: enum

enum is a type whose values are listed (enumerated) by the
programmer who creates a name (enumeration constant) for
each of the values.

enum {yellow,red, green, blue} c1,c2;

enum colors {yellow,red, green, blue};
enum colors c1,c2;

typedef enum {yellow,red, green, blue} Colors;
Colors c1,c2;

typedef enum {FALSE, TRUE} Bool;

C treats enumeration variables and constants as integers.
#include <stdio.h>
int main( )
{
int apr[5][7]={{0,0,0,0,1,2,3},{4,5,6,7,8,9,10},
{11,12,1314,15,16,17},{18,19,20,21,22,23,24},
{25,26,27,28,29,30}};
enum days {Sunday, Monday, Tuesday,
Wednesday, Thursday, Friday, Saturday};
enum week {week_1, week_2, week_3,
week_4, week_5};
printf ("Monday at the third week of April is
April %d\n“,
apr [week_3] [Monday] ); }
enum

enum dept {CS=20, MATH=10, STAT=25};

enum colors {BLACK, GRAY=7, DK_GRAY, WHITE=15} c;

int i=GRAY;
/*it’s 7 now*/
c=0;
/*it’s BLACK now*/
c+=8;
/*it’s DK_GRAY now*/
i= c+4 *2;
/* it’s 16 now */

typedef struct {
enum {RANK, DEG} kind;
union status{
int rank ;
char deg[4]; }; }status;
Pointers

Executable program consists of both code and data.

Each variable occupies one or more bytes of memory



The address of the first byte is said to be the address
of the variable.
Pointer variable is a variable storing address.
int i=1;
int *p = &i;

Declaration:

type *name;

int i, j, *p;
…
p
2000
1
…
i
The Address and Indirection
operators

& operator: returns address of a variable

int i, *p;
p = &i;






int i, *p=&i;
p is alias for i.
i=1; *p=2;
* operator : returns an object that a pointer points to.
printf(“%d\n”, *p);
int j=*&I;
Pointer Assignment

int x ,y, *p, *q;
p = &x;
q= &y;
q=p;
*p = 1;
*q= 2;

int x=1, y=2, *p, *q;
p = &x;
q= &y;
*p = *q;
Pointers as Argument

void decompose (float x, int *integer, float *fract){
*integer = (int) x;
*fract = x – *integer; }

void main(){
int i=5; float f= 3.4;
decompose (3.14, &i, &f); }

scanf(“%d”, &i);
*p= &i;
scanf(“%d”, p);
const to Protect Arguments

void f(const int *p){
int j;
p=&j;
*p=1; }

void f(int * const p){
int j;
p=&j;
*p=1; }

void f(const int * const p){
int j;
p=&j;
*p=1; }
Pointers as Return Values

double *Largest (double *x, double *y){
return *x>*y? x : y;
}

int *p, x,y;

p =max(&x, &y);


You can return pointer to one element of the
array passed as an argument, to static local
variable, to external variable.
Never return a pointer to an automatic local
variable!
Pointer Arithmetic

int a[5], *p=&a[0];
p

*p=a;
a

int *q;
p
a

p=&a[2];
q

q=p+2;
p
a

p++;
q
Pointer Arithmetic

int a[5], *q, *p=&a[4];
p
a
p

q=p-3;
a
p
a

p-=4;
q
q
Pointer Arithmetic

int a[5];
p

int *q=&a[1], *p=&a[4];
a

int i=p-q;
q
i=q-p;
 Meaningful, if pointers point to the element of
the same array.
 p<=q
 int sum=0;
for (p=&a[0];p<&a[N]; p++)
sum+=*p;

Combining * and ++ (--)
 int
sum=0, *p=&a[0];
while (p<&a[N])
sum+=*p++;
Array Name as a Pointer

int a[10], *p=a;

*a =7;

*(a+1)=12;

*(a+i) is the same as a[i]




p[i] is the same as *(p+i)
for (p=a; p<a+N; p++) sum+=*p;
Array parameter is treated as pointer, so it’s not protected
against change.
The time required to pass array to a function doesn’t depend on
its size.

int f(int a[]){…} is the same as int f(int *a){…}

int max = f(&a[5],10);
Pointer Example
$ cat ptr_example.c
#include <stdio.h>
int main() {
int x=1;
int *p; /* p points to an integer */
p = &x; /* Set p to x's address */
printf(" x is %d\n", x);
*p = 0; /* Set p's value to 0 */
printf(" x now is %d\n", x);
return 0;
}
$ gcc ptr_example.c -o ptr_example
$ ./ptr_example
x is 1
x now is 0
Using pointers to achieve Call-ByReference effect

Pass the address of a variable

Alter the value
void swap (int *px, int *py) {
int temp;
temp = *px;
*px = *py;
*py = temp;
}
int a=10,b=20;
swap(&a,&b);
Main difference between arrays and
pointers

Even though both contain addresses:

Array name is not a variable; so

pa = a; pa++
OK

a = pa; a++;
NOT OK

When an array name is passed as a parameter
to a function:

Actually the address of the first element is passed

Arrays are always passed as pointers
Strings



Double quotes
C treats string literals as character arrays, that is, a pointer of
type char *.
For string literal of length n, it stores n characters of the string
literal and null character (‘\0’) to mask the end of the string.

char ch = “abc”[1];

char digit_to_hex(int digit){
return “0123456789ABCDEF”[digit];
}

char *p=“abc”;

*p=‘b’; /* not recommended*/
String Variables

char str[length+1];

char date[8]=“June 14”;

char date[9]=“June 14”; /*2 null characters at the end*/

char date[]=“June 14”;

char *dt=“June 14”;


Characters of array date can be modified, dt points to
string literal which characters should not be modified.

date is an array name, dt is a pointer and can point to
the other string literal.
char str[length+1], *p;
p=str;
Writing Strings

printf(“%s\n”,str);

printf(“%.4s\n”,”C is a fun language”);

printf(“%10s\n”,”Hi”);

printf(“%10.4s\n”,”C is a fun language”);

puts(str);
Reading Strings

scanf(“%s”, str); / *never contain white spaces*/

scanf(“%10s”, str);

gets(str);

Reads until finds newline character

It replaces newline character with null character before
storing to a variable

Doesn’t skip leading white spaces
C String Library

char str1[10],str2[10];
str1=“abc”; /*wrong*/
str2=str1; /*wrong*/

str1==str2 compares pointers!

<string.h>

char * strcpy(char *s1, const char *s2);

strcpy(str2, “abcd”);

strcpy(str1,strcpy(str2, “abcd”));
C String Library

char * strcat(char *s1, const char *s2);

strcat(str1, “abc”); strcat(str2, “def”);

strcat(str1, strcat(str2,”gi”));

int strcmp(const char *s1, const char *s2);

Lexicographic ordering

if (strcmp(str1,str2)<0) …

size_t strlen(const char *s);

int len = strlen(“abc”);

len = strlen(“”);
String Idiom


Search for the null character at the end of a
string:

while(*s) s++;

while(*s++);
size_t strlen(const char *s){
const char *p=s;
while (*s++);
return s-p;
}
Dynamic Storage Allocation

It’s ability to allocate storage during program
execution

Available for all types of data

Mostly used for strings, arrays and structures.



Dynamically allocated structures can form lists,
trees and other data structures.
<stdlib.h>
malloc : allocates a block of memory, but doesn’t
initialize it

calloc: allocates a block of memory and clears it

free: releases the specified block of memory
NULL Pointer




If memory allocation function can’t allocate a block
of the requested size, it returns a null pointer
(NULL).
<locale.h>,<stddef.h>,<stdio.h>,<stdlib.h>,
<string.h>, <time.h>
It is responsibility of a programmer to test if
received pointer is a null pointer.
p=malloc(1000);
if (p==NULL) {
/* appropriate actions*/

if ((p=malloc(1000))==NULL) {
/*actions*/

if (p) …. is the same as if (p!=NULL)
}
}
Using malloc: Strings



void *malloc(size_t size);
Allocates a block of size bytes and returns a pointer to it; if
fails, returns NULL.
Since sizeof(char) is1, to allocate space for a string of n
characters:
char *p=malloc(n+1);



Memory allocated using malloc isn’t cleared or initialized:
strcpy(p, “abc”);
There are no checks to detect usage of memory outside the
bounds of the block
Dynamical allocation makes possible to write functions that
return a pointer to a “new” string:
char *p=
concat(“abc”,”def”);
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
char *concat(const char *s1, const char *s2 ){
char *result=malloc(strlen(s1)+strlen(s2)+1);
if (result==NULL){
printf(“malloc failed\n”);
exit(EXIT_FAILURE);
}
strcpy(result,s1);
strcpy(result,s2);
Dynamically Allocated Arrays


Elements of an array can be longer than one
byte => sizeof should be used.
int *a=malloc(n * sizeof (int));
for(i=0;i<n;i++) a[i]=0;


void *calloc(size_t nmemb, size_t size);
Allocates space for an array with nmemb
elements, each of which is size bytes; sets all
bits to 0 and returns a pointer to it.

If space is not available, returns NULL.

int *a=calloc(n, sizeof(int));

struct point {int x,y;} *p;
Deallocating Storage


Memory block are obtained from a storage pool (heap).
Garbage is a block of memory that’s no longer accessible to a
program.

A program that leaves garbage behind has a memory leak.

int *p=malloc(100), *q=malloc(100);
p=q;

void free (void *ptr);

int *p=malloc(100), *q=malloc(100);
free(p);
p=q;
Memory Leak: Examples

int *int_ptr;
for (;;) {
int_ptr = malloc(100 * sizeof(int) );
if ( int_ptr == NULL ) {
fprintf(stderr, "...");
exit(1);
}
}

for ( i = 1; i <= 5; i++)
printf("%s\n", concat(“abc”, “012345”[digit]));
Memory Leak

for ( i = 1; i <= 5; i++) {
char *str=concat(“abc”, “012345”[digit]);
printf("%s\n", str);
free(str);
}

for ( i = 1; i <= 5; i++) {
char *str=concat(“abc”, “012345”[digit]);
free(str);
printf("%s\n", str);
free(str); }
Dangling Pointers

char *p=malloc(4);
…
free(p);
…
strcpy(p,”abc”);

/*wrong*/
Several pointers may point to the same
block of memory. When the block is freed,
all these pointers are left dangling.
Memory Allocation Rules

If memory is allocated it must be freed.

Do not use memory after it is freed.




Do not free memory that will be used later.
Do not free a block of memory more than
once.
Do not free memory that was not allocated.
Do not use memory outside the bounds of an
allocated block.
Linked Lists


A linked list is a chain of structures (nodes),
with each node containing a pointer to the next
node in the chain.
The last node in the list contains a null pointer.
Declaring a Node Type

struct node{
int value;
struct node *next;
}

struct point {
double x,y;
};
struct vertex {
struct point element;
struct vertex *next;}
Building Linked List

First, create an empty list
struct node *first=NULL;

Then create nodes one by one:

Allocate memory for the node
struct node *new_node;
new_node=malloc(sizeof (struct node));
new_node
Store data into the node
(*new_node).value=10; new_node
new_node->value=10;
 Insert the node into the list

10
Inserting a Node at the Beginning of
the List

If first points to the first node of the linked list:
new_node->next=first;
first=new_node;
struct node *first=NULL, *new_node;
first
new_node
new_node=malloc(sizeof (struct node));
first
new_node
Inserting a Node at the Beginning of
the List
new_node->value=10;
first
new_node
10
new_node->next=first;
first
new_node
first=new_node;
first
new_node
10
10
Inserting a Node at the Beginning of
the List
new_node=malloc(sizeof (struct node));
10
first
new_node
new_node->value=20;
first
new_node
10
20
new_node->next=first;
first
new_node
10
first=new_node;
first
20
new_node
10
20
Searching a Linked List
for (p=first; p!=NULL; p=p->next)

{… }
first

int value=20; struct node *p;

for (p=first; p!=NULL; p=p->next)
{
if (p->value== value) return p; }
20
10

struct node *find(struct node *list, int n){
while (list!=NULL and list->value!=n )
p=p->next;
return list; }
Inserting a Node at the Middle of the List

struct *node p=first;

struct node * cur= find(p, 10);
cur
first
20
 struct
node *tmp =malloc(sizeof (struct
node));
 tmp->value= cur->value;
tmp
 tmp->next = cur->next_ptr;
 cur->value = 15;
cur
20
15
first
 cur->next = tmp;
cur
20
15
first
10
10
Deleting a Node from the List

struct *node p=first;

struct node * cur= find(p, 20);
cur
first
20

struct node *tmp;
tmp
tmp = cur->next;
 cur->value = tmp->value;
cur
tmp
15
15
first
 cur->next = tmp->next;
cur
tmp
15
15
first
15

 free(tmp);
first
15
10
10
10
10
Review

C versus Java

C data types

Functions

Control Flow

Scope

Pointers, Arrays

Strings
Auteur
Документ
Catégorie
Без категории
Affichages
4
Taille du fichier
1 434 Кб
Étiquettes
1/--Pages
signaler